Wednesday, August 16, 2006
Polygons and CSG
1. Compute the convex hull of the polygons you've got.
2. Let A = intersection of all hull edges that are also polygon edges.
3. Compute the convex hull of the edges that are left.
4. Let B = the union of all those hull edges that are also polygon edges.
5. Object = A . B
In fact you have to do it recursively as there may be bits left over after step 4 (the union and intersection operations alternate as you go down the recursion), and also step 4 can give more than one disjoint shape. If you start with multiple disjoint objects and nested polygons things are a bit more complicated too, but that's the essence of it.
For the red object below that gives
object = A . E . F . (B + C + D)
I think that's the simplest expression for the shape, and it's what the algorithm makes automatically. I think it also offsets correctly.
To turn the CSG representation back into a polygon I use an algorithm called MEG (model edge generator) devised by my old chum John Woodwark.
One of the nice things about CSG is that quad-tree division gives you a real handle on it. Imagine a complicated CSG expression and a rectangle. Classify all the half-planes against the rectangle into three categories:
1. All solid
2. All null
You can now massively simplify the expression inside the rectangle: 1 is the universal set, 2 is the null set, and 3 stays as it is; when you make this substitution the CSG expression collapses right down to unions and intersections of just those half-planes in category 3. This is called pruning the CSG expression to the rectangle.
You recursively divide a quad tree of rectangles over your object, pruning as you go, and stop when a quad has two or fewer half-planes in it. Those quads with two in may be a corner (it's easy to work out if they really are or not from the position of their intersection point). You join those corners up in the right order and you've got your polygons.
I think you're right, too. Edges as they offset will always be bounded by the nested 'shell' of convex polygons.
In terms of inner acute concave angles and the issues I noted, if ever it becomes necessary, it should be really easy to include at step 4, into the union, a set of generated planes passing thru the common vertex, normal to the angle bisector.
In the red polygon example, a new plane G passing thru angle BC splitting regions 1, 2 and 4, and a new plane H, passing thru angle DC, splitting regions 2, 3, and 6 would be added to yield:
This expression describes the outline exactly as my polygon approach would have yielded.
Links to this post: