### Wednesday, August 16, 2006

## Polygons and CSG

My code turns polygon outlines into CSG using Tony Woo's alternating sum of volumes algorithm. Roughly this goes:

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

3. Cuts

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.

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.

----0----

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

3. Cuts

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.

----0----

Once you have those two algorithms implemented you can flip between CSG polygons and the "natural" linked-list-of-vertex-points polygon representation. For plotting a picture (and outlining an object in the RepRap machine) the vertex list is favourite. For offsetting, cross hatching, and (obviously) doing booleans to work out where support material needs to go under the layer above, the CSG representation is much the best. It is also the "master" representation as it is so much more numerically and geometrically robust.

Comments:

Links to this post:

<< Home

Thanks for the explanation! That is a really cool algorithm. I hadn't seen it before.

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:

A.E.F.(B+C+D+G+H)

This expression describes the outline exactly as my polygon approach would have yielded.

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:

A.E.F.(B+C+D+G+H)

This expression describes the outline exactly as my polygon approach would have yielded.

If you want to follow up your neat idea of using arcs too to get real constant distance offsetting, see my comment on Woodwark's GLADES data structure in the comments on my hatching post of a few days ago on the other blog.

Post a Comment
Links to this post:

<< Home