CSGOffsetting
Offsetting 2D geometry
-- Main.AdrianBowyer - 25 Feb 2008
After the RepRapHostSoftware does CSGEvaluation, it does CSGOffsetting.
You can think of the CSGOffsetting stage as (virtually) dunking the part as-designed in acid and melting away 1/2 the width of the extrusion, creating a smaller "core". Later in the process, when the extruder head is actually squirting out plastic at every point of the (virtual) "core", the plastic expands to 1/2 the width of the extrusion(1) in every direction from that point, enough to (hopefully) touch the original part as-designed.
"inward" is something that's pretty easy for a human to understand, but a bit complicated to explain to a computer.
- offsetting always makes the plastic-filled *area* of a part smaller.
- offsetting *usually* makes perimeter edges shorter.
- offsetting makes the area of internal holes larger.
- offsetting *usually* makes edges in internal holes longer.
- offsetting occasionally makes some edges disappear.
- For example, if the original as-designed part is basically a rectangle with a small chamfer on the 4 corners (it has 8 edges), one or more iterations of offsetting will eventually make the chamfer disappear, resulting in a core that is a sharp-cornered rectangle (4 edges).
- For example, if the original as-design part is a dumbbell -- two circles connected by a long, thin bar -- one or more iterations of offsetting will eventually make the long edges of the bar disappear, resulting in a core that is two isolated circles.
The previous CSGEvaluation gives us a representation of the entire layer as desired perimeter edges -- unions and intersections of linear half-planes. The CSGOffsetting nudges all those half-planes "inward" by 1/2 the width of extrusion to get "perimeter path edges".
(While you might think that we could directly nudge the line segments produced by the "EndMatching" stage, there's a lot of fiddly work involved getting the ends of the line segments to match back up again -- especially when line segments entirely disappear. It's easier to convert those line segments to the half-plane representation, nudge them, and then convert back to line segments.)
Typically the edges produced by doing this CSGOffsetting once become a toolpath to draw the perimeter of the part(s).
In principle, we could continue this CSGOffsetting indefinitely -- the first time offsetting by 1/2 the extrusion width; then later iterations offsetting by 1 full extrusion width, until we've eroded the core to practically nothing. Each iteration we generate a toolpath, and all these toolpaths together fill up the interior of the part. However, people prefer to do this CSGOffsetting only once or perhaps a few times, then switch to CrossHatching to fill up the rest of the interior.
(1) Alas, that's a bit of an over-simplification. Hopefully a bit of ArcCompensation is all we need to get "close enough".
Further reading
- The BooleanGridList class source code at SourceForge includes the offset() method.
- Hyun-Chul Kim; Sung-Gun Lee; Min-Yang Yang. "A new offset algorithm for closed 2D lines with Islands". 2004. [1].
- The CGAL project has implemented a variety of geometric algorithms, including offsetting "2D polygons with holes" [2]
- "Mandoline is a lightning-fast command-line program that slices 3D files into toolpaths for home-build thermoplastic-extrusion 3D printers like the RepRap or MakerBot. (in Alpha)" [3]
- CGProjects09 has implemented a bunch of geometric algorithms.[4]
