Tuesday, August 15, 2006
Offsetting and Sharp Points, part 2
I'm going to go ahead and post what I believe is a summary of the CSG algorithm coded in Java, the algorithm that I was working on, and some thoughts on how to adapt the existing algorithm to have the same qualities as my approach would have given. The image thumbnail to the left shows a slice of my 'widget' example used recently. The goal of the algorithm is to turn this into a perimiter trace. It can also be adapted to return the region that must be in-filled.
Here, I show an image that would be gotten using the CSG algorithm. I do a poor job illustrating this with my program, but Adrian added a blog earlier that details this more clearly. I'm not sure exactly how the boolean region expressions are determined; I would guess some kind of binary partition line algorithm is used? It's not too important, as long as it works and is reasonably fast.
Here, you can see how my algorithm would have accomplished the same task. The red inset line segments are calculated by intersecting each adjacent edge, offset thru an angle 90 degrees counter clockwise to the edge direction. The edges terminate at intersection points. The result can be a self-intersecting polygon; this is easily remedied by turning it into a collection of simple polygons and removing the simple polygons that turn the wrong way (They form negative areas that should not contain any thread).
This demonstrates that the two algorithms are actually doing the same mathematical operation. The only difference is how the data is organized and abstracted, and the algorithm used to process it.
This perimiter seems to me to be a weaker bond than could be possible. It introduces defects on the sides opposite an inner angle that wanders too close (Hard to see here, but the pointy angle is actually a divet). It also appears the area shown in red has quite a bit of material extruded into it twice (on separate passes with the extruder head.)
What I thought might be better approach is to clip the interior angles; in effect, it tries to 'circle' around the inner angles rather than wander too far away. Though a circle is the ideal case, a line approximation is good enough.
The perimeter extrusion should be a lot stronger, you avoid the seam, and you aren't trying to squish so much material inside while tracing the perimeter.
To solve this, I came up with a vector equation that could be used to clip these degenerate inner angles so that the thread, as closely as possible, forms a path that circles around the inner angle.
So, the question is, can the CSG algorithm be adapted (if necessary) to clip inner angles? I think the answer is yes. If an extremly tiny triangle is added to round out every inner acute angle, it would seem this would grow to the size necessary to fill in the gaps. It can even start out as an infintesimal triangle, if the boolean region partitioning algorithm doesn't choke on it.
When this triangle is included in the final inset area, it gets amplified and bridges all the separate regions, if it is reasonably possible to do so.
I don't know if my algorithm is better/faster/easier to understand, etc. To me, calculating the boolean expression in the CSG solution would appear to complicate factors a lot. If existing libraries could be used, this might reduce complexity, but I believe there are probably also libraries for polygon manipulation and decomposition (They are, after all, attacking almost identical problems.) In any case, it does appear that whatever algorithm used for perimeter and infill calculations, there is a solution for the acute angle defect if problems begin to occur because of defects in the printed parts.
*** UPDATE ***
After thinking about the boolean expression Adrian posted, I think the half plane combination can lead to problems unless you are very careful about how you compose the half plane boolean expressions. It is best if I illustrate with pictures:
The full sum of products expression for this is image's region, where '.' is an intersection, '+' is a union, and '^' is complement, for half planes that are solid in the downward direction, is:
A . B.^C .^D . E .^F 
+ A .^B. C .^D . E .^F 
+ A .^B.^C . D . E .^F 
+ A .^B. C . D . E .^F 
+ A . B. C . D . E .^F 
+ A . B. C .^D . E .^F 
Normal boolean algebra allows you to simplify this to:
A . B . ^F [Red]
+ D . E . ^F [Green]
+ ^B . ^D . C [Blue]
The yellow region represents overlap between the red and green region.
If you offset each half-plane in the away from the outer edge of the polygon, the simplified form starts to have problems:
The BDC product term is not truncated by the F half plane (It doesn't need to be in the non-offset region), and the result is a triangle that blows out past the F plane.
I could not see what form of boolean expressions would be created by the Java code, but test cases like this would expose whether it is working correctly.
In any case, special care would need to be taken before assuming applying a valid boolean combination on offset planes will result in a usable inset area. The full sum of product representation doesn't have the problem I describe here (The 'bad' triangle at the bottom gets clipped off by the F plane in this case), so it is still a valid approach, assuming you take into account every clipping half plane for every region included.
Links to this post: