I'm wondering what the best way of going about this would be: I have a path, a series of x,y coords defining a polygon. I want to turn this path into 'walls' offset from this path so that I can move a sprite within but enclosed by these 'walls'. Here is an Image, the redline being the original polygon and the white line the 'wall' Any ideas on how this might work?

Do you want to actually construct the walls, or do you just want the sprite to not leave the track more than the distance where virtual walls would be?

It may be easier to think of as having the sprite constrained to the path rather than having 'walls'. I'd still like to draw the walls though also it may be diffucult to control the sprite at intersections.

I don't know whether the following is the most efficient method of constructing the walls. The main problem seems me that it is possible that more than 2 lines may emanate from a vertex. Here we go ... err, I handle the problem in 2 dimensions, just for the case you wonder.

Iterate over all vertices of the path. Make the vertex to the local origin and compute all line segments with this origin. Compute the angle that each segment makes with e.g. the positive x axis. Then sort the lines accordingly to this angle, so that you have the line segments in circular order around the vertex.

Now iterate the line segments, e.g. starting with those with the smallest angle and advancing to the one with the next greater angle. Look at the segments so that they start at the local origin and end at the distant point, i.e. as a vector emanating from the origin. Then the unknown edge to the left of the current segment and the unknown edge to the right of the following segment hit at a point that denotes one of the new vertices.

The direction of the vector to that vertex is obviously given by half the angle between the two segments. One way to compute that direction is to use the 2 angles of the belonging segments as follows:
β := ( αn + αn+1 ) / 2
d := [ cos( β ), sin( β ) ]T
where αn denotes the angle of segment n.

(Please notice that n+1 has to wrap around to 0 for the last segment.)

Another way would be to use the perp vectors. If
vn := [ xn, yn ]T
denotes the distant vertex of segment n, then
ln := [ -yn, xn ]T / |vn|
is the normalized perp vector to the left, and
rn := [ yn, -xn ]T / |vn|
is the normalized perp vector to the right. The said direction vector would then be
d := ( ln + rn+1 ) / |ln + rn+1|

Now that the direction is known, the missing part is the distance of the new vertex. What we know is that the wall should be W units away from the path segments. Then the length of the vector would be
|v'| := 1 / sin( ( αn+1 - αn ) / 2 )
You'll have to handle the wrap around at 0° accordingly; I left this to you ;)

Then the vector to the new vertex (still in the local space!) would be
v' := d * |v'|
and undoing the translation by the current vertex gives you the actual new vertex position.


Another way, totally ignoring trigonometry but using vector math, would be to demand that the projection of the vector to the new vertex onto the both perp vectors should be W:
EDIT: Hmmm, no longer sure whether this works as wanted, so it is removed for now! /EDIT


What is left is to concatenate the new vertices in the correct way. You can do so because the topology of the path can be followed by using the ordering computed at the beginning of the algorithm. So the sequence of new vertices at the inner side of each path segment loop can be found and used to build edges for the walls.

[Edited by - haegarr on March 8, 2010 2:03:05 PM]

Thanks for the help. I'm a bit new at this - could you tell me what the superscript T stands for?

1. Maybe consider computing the Minkowski sum of your path and some small polygon which more-or-less approximates a disk? There are efficient algorithms for computing Minkowski sums of polygons...

2. Alternatively, it may be easier to constrain your sprite to be within a certain distance of the path, as haegarr said, and then solve the drawing problem separately. For instance, you might be able to just draw overlapping capsules around your line segments and let the stencil or z-buffer sort them out to make outlines...

E.g., off the top of my head (you might be able to do this more efficiently):


1. Clear stencil buffer to zero; enable stencil buffer writes but disable stencil tests.

2a. Set stencil draw mode to "one, always."
2b. Draw large capsules around line segments, of radius R.

3a. Set stencil draw mode to "zero,always."
3b. Draw small capsules around line segments, of radius r.

4a. Disable stencil writes and enable stencil tests; set the test to only draw where the buffer is 1.
4b. Draw large capsules (or just quads large enough to bound the capsules) of radius R+epsilon around your segments, in the color that you want your walls to be drawn.

Now you will have outlines around your segments at a distance (R+r)/2 and with thickness R-r.

[EDIT: Actually, depth sprites may be the better way to do this: Render distance fields into your depth buffer; then draw a quad with depth-testing, only drawing those pixels at a depth equal to the desired radius plus-or-minus half the desired outline width... (My inspiration here is the old method for drawing Voronoi diagrams using graphics hardware by rendering intersecting cones... here it is... but I'm noting that you don't actually need to use polygonal representations of cones; you can instead use depth sprites or even pixel shaders (to analytically compute distance for each pixel).)]

[Edited by - Emergent on March 27, 2010 10:43:33 AM]

This can be a complicated problem to solve, if you want to explicitly calculate the inflated/offset geometry, and you want it to work in general (i.e not just for "well behaved" nice input).

For instance, your example image doesn't have any really acute corners. At acute corners, you'll need to bevel or round the inflated geometry, because otherwise the inflated surface shoots off to infinity. Or for example imagine if your input path was made of segments which were much shorter/smaller than the inflation radius.. this can also cause problems.

Here's a link and two threads that might be of interest:

http://fcacciola.50webs.com/Offseting%20Methods.htm

http://www.gamedev.net/community/forums/topic.asp?topic_id=552378&PageSize=25&WhichPage=2

http://www.gamedev.net/community/forums/topic.asp?topic_id=562159


As mthicke pointed out, if you can avoid requiring the actual offset geometry explicitly, that would make life easier. But less interesting :)