## 2D Sideways Offset Using Weaves

Monday, May 12th, 2014 at 7:32 pm

Most CADCAM systems have about half a dozen 2D polygon offsetting algorithms somewhere about inside them. None of them work very well because the trickiness of the problem is notoriously easy to underestimate. The naive method is to offset each line segment perpendicularly sideways and then insert an arc where the angle between two adjacent lines is convex, or otherwise trim them back when the angle is concave, like so:

This seems attractive because it’s going to work whenever the offset distance is very small. Once you offset further than half the minimum distance between any two vertices, then you start to get multiple self-intersections, some of which involve intersections with the inserted arcs. A little bit of thought and you’ll see that this quickly enters a quagmire and you’ll be debugging it for the next 20 years. This is not an exaggeration.

An alternative method is to use Voronoi diagrams. These are great if you want to offset the same polygon by numerous different values, for example if you are producing some offset area clearing passes. The API into such algorithms (if you’ve got one) is daunting, and it’s going to be very time-consuming to add features such as allowing offset to be on only one side.

When all else fails, there’s my machining method, where we repurpose one of the waterline machining algorithms to give the answer that we want. Here we imagine converting the contour we would like to offset into a vertical wall of rectangles, and then we run a flat-bottomed cutter against it. My weave sub-sampling waterline algorithm delivers the structure shown in cyan with a contour going all the way round it on both sides.

Now the trick is to break the contour so it gives only the right hand side (the yellow curve). We have filters for tracing out partial waterline contours based on the contact angle with the tool-tip — for example producing z-constant toolpaths only where the tool is in contact with the surface at greater than 75degrees so they only appear on the walls.

So we could fake this by tilting the vertical wall to one side so that on the upper side the tool tip makes contact with a slope at an angle of less than 75degrees, and on the undercut side the tool shaft hits the top edge giving an effective slope of 90degrees.
But this gets messy. It’s better to add in a special toolpath filtering case that simply works for this application and sets the flags to filter out the toolpath when the contact direction either on the left hand side of the contour, or in contact with one of the end-points of the contour if the contour is not closed.

The disadvantage of this method is that your offset contour is made up of hundreds of little line segments that only approximate the offset with regards to the endpoints of straight sections and linearizations of the arcs. But does this matter? Graphically it looks exactly the same. It might be good enough — especially if we don’t have to debug it for the next 20 years.

If I was starting this fresh and not trying to get it done in a day, I could encode which line segment or vertex each point of the offset shape was offset from, and then try to rejoin sequences of segments into the same line or arc where they came from the same entity. Then, after that, for segments that jump the gap between a offset point from entity A to a offset point from entity B, I’d extend the two offset passes to the true intersection between A and B. This would be robust almost all the time. And it would be fail-safe because wherever there was a problem it would fall back to the approximate offset — which is almost always going to be better than crashing or giving a properly screwed up result.

### 1 Comment

• 1. anders replies at 17th May 2014, 8:05 am :

since floating-point operations are inherently unreliable, what tricks do you use to keep the topology (“connectedness”) of the weave consistent?
I would guess you need to somehow “march” along the X/Y-fibers of the weave and have some consistency checks on the topology when you subdivide a cell?

There are two open-source voronoi diagram implementations I know of.
One in the boost.polygon.voronoi project apparently sponsored by Intel for VLSI and chip design. It takes only integer coordinates and point/line input.
The other is openvoronoi where I’ve tried to implement Held’s topology-oriented algorithm (Held’s commercial VRONI code is apparently what many CAD/CAM kernels use!?). This algorithm takes float-coordinates and in addition to points and lines could support also circular arc input if I had the time to code that together..

Anders