Since there still seems to be a lot of interest in it, I've updated my RoundLine code and released it on CodePlex. Here are the major changes from earlier versions:

• Updated for XNA Game Studio 3.0
• Uses shader instancing for improved performance: over 20,000 lines per frame at 60fps on the Xbox 360
• Drawing code is in a separate file from interaction code (using partial classes), so you can easily skip the latter if you don't need it
• Miscellaneous cleanup
• A small demo app is included

I hope you find it useful!

-Mike

I've been working on a little arcade game to submit to the XNA Creators Club Community Games Beta. I finally finished it last weekend and submitted it Sunday night. It passed Peer Review and went live a few hours ago -- woohoo! It's not the most amazing game of all time, but it was still a lot of work to get all the details finished. I have ideas for more ambitious games to tackle soon...

Check out "Gemini 08" in the Games Catalog. Anyone with an XNA Creators Club Premium Membership can play it on the Xbox 360 for free! If you have feedback on the game, you can submit it here.

For more info about the XNA Creators Club and the Community Games Beta, check out this tour.

-Mike

I haven't written anything about PIX in a while. But here's a great article written by Brian Richardson at GarageGames about using PIX to track down a rendering issue. Nice job, Brian!

You can find the latest version of PIX in the March 2008 DirectX SDK.

 -Mike

(Insert standard gosh-I-haven't-blogged-in-a-while blurb here)

(UPDATE: If you get an out-of-video-memory exception when starting the program, find the line of code that says "public const int numNodesToAllocate = 250;" and change 250 to a smaller number.)

I decided to improve my old XNA Mandelbrot set explorer to take advantage of the GPU horsepower available on PCs and the Xbox. It was a fair bit of work, but the end result is much more interactive and fun to use than the old version.

The core Mandelbrot set algorithm is a natural fit for a pixel shader. The harder part is making it incremental. Once you're zoomed in a fair bit, it can take hundreds or thousands of iterations to determine if a point is in the set or not, and it's more fun if you can zoom and pan around while progressively improving the image. So you want a program that can iterate a little, then move and draw, then iterate a little more. That is a little off the beaten path of the standard rendering pipeline.

I decided to use render-to-texture and ping-pong between two 256x256 textures. So for the first frame, the shader reads from texture A, computes some iterations, and writes to texture B. Then texture B is rendered onscreen. Then in the next frame, the shader reads from texture B, computes some further iterations, and writes to texture A. Then texture A is rendered onscreen. Then we repeat the whole process. (Life would be easier if we could read to and write to the same texture, but Direct3D doesn't work that way).

But instead of there just being one texture A and one texture B, there are a whole lot of them. The two-dimensional space is subdivided with a quadtree, and each node in the quadtree has a "texture A" and a "texture B." The program both iterates on and draws all visible nodes, every frame.

Also, what I'm calling "texture A" for one node is actually more than one Direct3D texture. I need to maintain four pieces of state for each texel: the current calculated "x", the current calculated "y", the iteration count, and whether the point is "done." Ideally I'd use floats for "x" and "y", a uint for "iterations", and a boolean for "done." SurfaceFormat.Vector4 would have been sufficient (albeit a bit wasteful), but the Xbox doesn't support it. I decided to use three SurfaceFormat.Single textures, and encode "done" into the iterations count by negating the value if the texel is done.

I had never tried using multiple render targets (MRT) before, but it worked fine. Instead of having the pixel shader output a float4, it needs to output a structure with values for each render target:

// MRT output. Even though each RT only has a red channel,
// we have to write out a four-component vector to each RT.
struct PS_OUTPUT
{
    float4 x : COLOR0;
    float4 y : COLOR1;
    float4 iterations : COLOR2;
};

The shader also needs to read from three textures, but that's just a matter of using three samplers, with a different texture bound to each sampler:

Okay, so each node consists of six 256x256 32 bpp textures, or 1.5MB of texture memory. How many of these nodes do we need around, to be able to view a frame at full screen resolution? At 1280x720, there are generally about 50 to 100 nodes recalculated per frame. Since we want to zoom and pan around, it's helpful to have a few extra nodes. So I allocate a pool of 250 nodes up front when the program starts, and purge least-recently-used nodes when I need fresh ones for newly-exposed areas of the screen. So, yeah, that's 375MB of textures altogether, and 75-150MB of that is read/written per frame. That's a lot of texture memory to eat up, especially on an Xbox, but it works.

There are actually three key pixel shaders. One is used to set the initial values for x, y, and iterations/done when a node is initialized. A second shader does the iterations. A third shader just reads the iterations/done info and translates it into a color for display.

You can use the "B" button to tell the "CalcCore" pixel shader to perform 1, 4, or 16 iterations per pixel per frame. More iterations makes a given node calculate faster, and is nice if you're not panning/zooming, but the frame rate suffers a bit. As with previous versions of Wendybrot, you can use the right stick to play around with the color palette.

The attached zip file contains all the source code, plus prebuilt ccgame packages for both Xbox and Windows. You can undefine "USE_RTT" in the source code to make Wendybrot use the old method of performing the iterations on the CPU instead of with the pixel shader -- but it's much slower! Also, you can try rendering at 1920x1080, but the frame rate struggles a bit here. Still, it's staggering to think about how much math and memory transfer is happening per frame.

I hope you enjoy playing with the program and learn a few things from the code.

-Mike

The discs of light used by my XNA 2D lighting code look decent, but shadows would really add to the realism. Shadows are a bit tricky because they are non-local: an object half-way across the screen can make the difference in whether a pixel should be light or dark. And you have to take account of every object in the scene in order to determine whether a point is in shadow. But there's a reasonable way to do 2D shadows that works well with my approach of drawing the lighting in a separate render target.

Shadow volumes are a popular technique for doing shadows in 3D. It's not too hard to see how to use a similar technique in 2D. Basically, for each object that casts a shadow, modulate that object's shape based on the light source's position and, by rendering the updated shape, mark every pixel that is in shadow (the stencil buffer is often used for this). Then when you draw the lighting for a pixel, you check the shadow information to tell whether the point should be in shadow or not. Since I'm drawing the lighting in its own render target, I can also do it in the other order: draw the light beam first, then black out the pixels that are in shadow.

Consider a point light that casts light for a finite distance, so its area of influence is a disc (shown in white below). Now consider a line segment that intersects the disc of light, and thus obstructs some of the light. Visualize a ray extending from the light to each endpoint of the line segment, and on to the edge of the disc. We want to black out the interior of that shape (shown in red below):

There's probably a proper mathematical term for that kind of shape -- but I'm calling it a shadow wedge. The inside points are just the endpoints of the line segment -- call them p0 and p1. It's round on the outside, lining up with the light disc's perimeter, but with a slightly larger radius so there are no sparkles due to different tessellation than the light disc. I'm using 6 outer points (but of course you could use more if necessary) -- call them v0, v1, v2, v3, v4, and v5:

v0 is the extension of the ray through p0, and v5 is the extension of the ray through p1. The other "p"s are at equal divisions of the angle between v0 and v5.

Note that I'm trying to make the shadow wedge as "tight" as possible, so we don't waste pixel bandwidth. I could have made the shape a triangle with the light source as one vertex and the other two being projections through the endpoints out some great distance, and done a line test in the pixel shader to see whether to black out the pixel or not. But I'm trying to be efficient so I touch as few pixels as possible, and make it quicker to draw lots of shadow wedges.

Here's where it gets fun. Given p0, p1, the light position, and the light radius, can you generate the shadow wedge in a vertex shader? It's a slightly strange job for a vertex shader, because the shader needs to do different things for the different points. (It's a better match for a D3D10 geometry shader, but that'll have to wait for another day). Here's how I did it...

For the input vertices, instead of storing literal position info, I store the "p-ness vs. v-ness" in the x coordinate, and the "0-ness vs. 1-ness" in the y coordinate. So p0 has an x value of 1.0 (all p, no v) and a y value of 0.0 (all 0, no 1). v5 has an x value of 0.0 (no p, all v) and a y value of 1.0 (all 1, no 0). v1 through v4 have y values between 0 and 1, reflecting their increasing "1-ness."

            numVertices = 8; // p0, p1, v0, v1, v2, v3, v4, v5
            vertices[0] = new VertexPositionTexture(new Vector3(1, 0.0f, 0), new Vector2(0, 0));
            vertices[1] = new VertexPositionTexture(new Vector3(1, 1.0f, 0), new Vector2(0, 0));
            vertices[2] = new VertexPositionTexture(new Vector3(0, 0.0f, 0), new Vector2(0, 0));
            vertices[3] = new VertexPositionTexture(new Vector3(0, 0.2f, 0), new Vector2(0, 0));
            vertices[4] = new VertexPositionTexture(new Vector3(0, 0.4f, 0), new Vector2(0, 0));
            vertices[5] = new VertexPositionTexture(new Vector3(0, 0.6f, 0), new Vector2(0, 0));
            vertices[6] = new VertexPositionTexture(new Vector3(0, 0.8f, 0), new Vector2(0, 0));
            vertices[7] = new VertexPositionTexture(new Vector3(0, 1.0f, 0), new Vector2(0, 0));

VS_OUTPUT MyVS(
    float4 pos  : POSITION )
{
    VS_OUTPUT Out = (VS_OUTPUT)0;
    float vVsP = pos.x; // v vs. p
    float zeroVsOne = pos.y; // v0 vs. v5, or p0 vs. p1

    // Use "lightspace", a coordinate system where the light source is at the origin
    float2 lineP0LightSpace = lineP0 - lightPos;
    float2 lineP1LightSpace = lineP1 - lightPos;
 
    float theta0 = atan2(lineP0LightSpace.y, lineP0LightSpace.x);
    float theta1 = atan2(lineP1LightSpace.y, lineP1LightSpace.x);

    // Make sure our lerp takes the shortest path from theta0 to theta1
    // (make sure theta0 and theta1 are <= PI apart from each other) 
    if( theta1 - theta0 > 3.14159 )
        theta1 -= 2 * 3.14159;
    if( theta0 - theta1 > 3.14159 )
        theta0 -= 2 * 3.14159;
 
    float theta = lerp(theta0, theta1, zeroVsOne);
    float2 vLightSpace = float2(lightRadius * cos(theta), lightRadius * sin(theta));

    // clamp p0 and p1 to the light's radius...otherwise things get weird
    if( distance( lineP0LightSpace, float2(0,0) ) > lightRadius )
    {
       lineP0LightSpace = float2( lightRadius * cos(theta0), lightRadius * sin(theta0) );
    }
    if( distance( lineP1LightSpace, float2(0,0) ) > lightRadius )
    {
       lineP1LightSpace = float2( lightRadius * cos(theta1), lightRadius * sin(theta1) );
    }
 
    float2 pLightSpace = lerp(lineP0LightSpace, lineP1LightSpace, zeroVsOne);
 
    // Translate back from "lightspace" to worldspace
 
    float2 v = vLightSpace + lightPos;
    float2 p = pLightSpace + lightPos;

    float2 mergedPos = lerp(v, p, vVsP);
    float4 mergedPos4 = float4(mergedPos.x, mergedPos.y, 0, 1);

    Out.position = mul(mergedPos4, viewProj);

    return Out;
}

Computing the shadow wedge in the vertex shader makes it possible to draw a whole lot of them quickly, so a light can be occluded by any shape whose silohouette is a series of line segments. I just pass in a list of my Line objects, plus the light position and radius, and the shadow wedges get drawn for each Line.

In my case, I want to have my RoundLines cast shadows, rather than idealized "thin" lines. The code above is fine if the line has a radius of 0 (or "close enough" to 0), but what if it's thick? I solved this by drawing three shadow wedges instead of one, per RoundLine. The larger, middle wedge goes between the RoundLine's "endpoints". The other points I need are the tangents to the end discs where the ray from the light source just grazes them. This requires some trigonometry.

We know the coordinates of p0 (one of the endpoints of the RoundLine), and we want to find p0-prime (the tangent point to the RoundLine). The tangent line is at a right angle to the radius line from p0 to p0-prime. We know the distance from the light to p0 (the hypotenuse), and the distance from p0 to p0-prime (the opposite side). sin(theta) = opposite/hypotenuse, so asin(opp/hyp) = theta. Once we have theta we can quickly find the length of the adjacent side, and thus p0-prime. Do the same thing for p1 to find p1-prime, and you're done! I call the little shadow wedges from p0 to p0-prime, and from p1 to p1-prime, the "sideburns" and have an option to turn them off if you're not using RoundLines. It might even work (and be faster) to simply draw a single shadow wedge from p0-prime to p1-prime.

I tried some options to have the far half of the RoundLine be dark (in shadow), and the near half be properly lit by the light source. Because the endpoints of the RoundLines overlap, this had issues, and the sideburns were causing problems too. I decided to make the walls not be affected by the shadow -- I actually draw them on the final render target after the fullbright scene is multiplied by the light scene. This is a little less "realistic" than I originally had in mind, but as I was rambling about last time, it's not really clear how the walls should be lit in 2D anyway.

My test app shows the fullbright scene, the lighting scene, and the combined scene all side by side at once. Press "A" to go to wireframe, and "B" to go to a mode that shows the shadow regions more clearly. I'm very happy with the final result. I've got the shadows working in the BentMaze app too -- I'll show that code next time.

-Mike

Man, I totally jinxed myself when I predicted that hooking up my RoundLine collision detection / sliding code to my XNA maze game wouldn't be painful. It was. But after a lot of hours of debugging, I've got it working well enough to call done and usable, though not perfect.

The main problem arises because collision management is all about that exact threshold where an equation changes state, i.e., the moment at which we go from being just outside the wall to just inside the wall. If different parts of the code express insideness/outsideness slightly differently (different algorithms, different coordinate systems, etc.), things that are mathematically equivalent actually give different results due to floating-point rounding error. For instance, I could call my FindFirstIntersection() routine to get the parametric "t" value at which the disc exactly intersects the wall, then call my distance-to-line function and discover that moving to "t" would put me just slightly (like, 0.000000162 units) inside the wall. So the next time I try to move away from the wall, my FindFirstIntersection might return a tiny "t" number, indicating that I'm tapping on the wall's edge from the inside, and thus can't move away.

I first tried to accommodate this by adding little tolerance fudge factors to a bunch of my equations. If you're within 0.00001 of the line, you can probably consider yourself exactly in contact with it, right? But this approach just shifted the breaking point around, and lead to endless random tweaking of these tolerances. And you still need to treat exact contact with the wall carefully. If you are "in contact" and trying to move closer to the wall, you need to set t=0 to stop further motion. If you are moving away from the wall, you need to not do this or else you'll be stuck to the wall forever.

I decided to avoid tolerances as much as possible and instead use a single uniform collision test as a backup to verify the results from all other tests and calculations. The collision test I chose was that the distance squared from the disc to the line, as measured by one piece of code, absolutely must be greater than or equal to zero. Usually, this test would agree with my other results. But in the cases where the other tests were telling me to go to a point that would penetrate the line (according to my standard test), I would instead do a binary search between a known-good (non-penetrating) value and the known-bad (penetrating) value until I had a point that was very close to the line, but still passed my standard test. Eww -- my original vision of a clean, near-constant-time algorithm was suddenly very messy and variable in terms of execution time. There's still an upper bound -- I never iterate more than 10 times -- but it's frustrating because my whole objective with using algebra to compute these intersection points was to avoid the need to stab around with various values until finding an answer that was "close enough." However, I don't think a completely iterative solution would be sufficient. There's always going to be a need for some higher-level analysis. A straight binary search for collision is dangerous because t=0 might not intersect the line, t=1 might not intersect the line, and even t=0.5 might not intersect the line, but there is still some "t" value at which the disc does intersect the line, so some mathematical analysis of the situation is necessary. I couldn't find many useful resources on this topic on the Web, so it's hard to know how near or far my solution is to being optimal.

But enough gloominess. What I've got works pretty well. If you collide with the rounded end of a line, you roll around it in a natural way. If you move into a corner of two walls, you snug right up into that corner and don't wobble around until you change direction. You can slide happily along the wall's edge. And I haven't yet found a case where the disc misses a collision. If you zoom way out so you can see most of the maze, the disc moves much faster in world-space units, yet it never fails to bang up against any walls in its way.

That was more than enough collision code for me. I'm ready to get back to coding up some whizzy graphics.

-Mike

The next thing I want to add to my XNA maze game is collision detection, so my little orange disc can't go right through the maze walls. There seem to be two alternate general approaches that can be taken regarding collision detection:

1. After reading the user input, determine whether moving the disc the way that the user requested would cause it to penetrate a wall. If so, alter the disc's path before applying it, so as to not penetrate the wall.
2. After reading the user input, move the disc the way that the user requested, then determine whether that motion caused it to penetrate a wall. If so, "back up" the motion so it no longer penetrates the wall.

Since using Latin phrases makes everything sound more scientific, these two approaches are termed a priori and a posteriori. The a priori approach seems more clean and straightforward to me, so I'm going to wander down that road and see how things go.

Here is a careful breakdown of the problem I want to solve: We have a disc D, with radius Dr, which is at position Dp0 at time t=0. User input indicates that we are considering moving the disc (with constant velocity) to position Dp1 at time t=1, but a line might be in the way. For any (thick, round) line L, which also has a radius and two endpoints, compute the following:

1. Will disc D overlap line L at any point, as it moves from Dp0 to Dp1?
2. If so, at what time t between t=0 and t=1 does the overlap first occur?

This problem has two twists in comparison to the usual point vs. line geometry problems. Firstly, both the disc and line have nonzero thickness, so these have to be accounted for. That is, we aren't looking for the "t" value where the mathematical point intersects the mathematical line, but rather the value where the distance between them first reaches a value equal to the sum of their radii. Secondly, the line is not infinite, but is more correctly a line segment with two endpoints. So the distance from the disc to the line is not a single polynomial equation.

These twists make the problem complex enough mathematically that I was having a hard time getting my head around all the issues, let alone how to compute the solution. There's always the option of using brute force or some sort of binary search to find the first intersection. But it seems that a direct derivation of "t" shouldn't be that hard, and would be much more efficient, so I pressed on.

I decided it was worth taking the time to write a program that would let me interactively explore, and graphically represent, the problem. So I wrote a program that lets me move a disc and its linear path around a target line, and graph "t vs. d" where "t" is the parametric position along the disc's path, and "d" is the distance between the disc and the line. The resulting program was quite helpful. Here's a look:

The red line is the "target line" that we are measuring distance to.  The green line is the path taken by the disc (it's a happy coincidence that a disc, swept along a line, produces a RoundLine).  The orange line shows the shortest distance from the disc to the target line.  By pressing B and moving the right stick, you can arrange the disc's path however you want.  Then you can sweep the disc along its path and see the correlating point on the graph (marked in green).

I wrote a Graph class to handle drawing graphs in a general way. For a while I had grandiose visions of making this class totally general and reusable and bursting with clever features, but in the end I only hooked up some basic functionality, and you have to specify some things (like grid size) manually. What's there is useful, but it would need more work to be a complete and reusable component. Here's a shot of it graphing y = x * sin(x), and that equation's first derivative:

One great feature in C# is delegates, which are similar to function pointers. The graph class takes a "ComputeY" delegate, which it calls to evaluate the Y coordinate for every X value. The really slick thing about delegates is that they can be a class member function which references member variables -- to do this requires in C++ hoop-jumping, but it "just works" in C#. This is a huge help, since my "LineDistance" function needs to access class information about the disc position, target line, and graph mode.

Back to the problem at hand. We are trying to find the "t" value at which the distance first drops below the value which is the sum of the disc's radius and the line's radius. In my program, the target line has radius 0.2, and the disc has radius 0.1, so we're looking for the place where the graph dips below 0.3 (the dark blue gridlines are spaced 0.1 units apart). When the target line's endpoints aren't relevant to the problem, the distance (graphed in white) is a simple linear function of t, so its derivative (graphed in gray) is a constant (well, two constants -- it flips when the disc crosses the target line):

When the endpoint determines the distance, the distance is nonlinear. I thought it was quadratic at first, but it's hyperbolic, which means that even its derivative is nonlinear:

In the most complex case, the distance goes from hyperbolic, to linear, to hyperbolic:

Yuck. But look at what happens when we graph distance-squared, rather than distance:

It becomes quadratic, with a sequence of linear derivatives, regardless of whether the endpoints are involved! The slope of the derivative is the only thing that changes for the various phases of the graph. It looks like it will be easier to compute the value of t at which d-squared first drops below (0.3)-squared.

To someone with better mathematical intuition than me, this all may have been obvious.  But it didn't click for me til I could visualize it and tweak the variables.

You might find this program a useful starting point for creating visualizations for other geometric/mathematical problems. In any case, it's fun to play with. Many people use Java to create similar visualizations -- this site is particularly impressive. Using XNA instead of Java (or MFC, or Mathematica, or Applesoft, or whatever) has pros and cons, but it got the job done for me, and that's the important thing. Oh, and it was fun -- that's important too.

-Mike