offset(-1, offset(1, ...)) produces "island" artifacts

[paulftw]

Steps to reproduce:

const offset = (delta, c) =>
  expansions.offset({ delta, corners: 'round', segments: 16 }, c)

export function main() {
  return [
    offset(-1, offset(1, primitives.square(4))),

    transforms.translate(
      [0, 3, 0],
      offset(-0.9, offset(1, primitives.square(4))),
    ),
  ]
}

This produces the following:

Segment of a circle should not be there.

[paulftw]

Artifacts are visually similar to #907 but that one doesn't seem to use offset

[z3dev]

@paulftw cool examples.

from looking at this, the round segments may be illformed after the first offset.

[platypii]

Notes:

1. The way that rounded edges are constructed results in the two "side" edges coming together and eating the "middle" edge. This is because the outer edge angle is less than the middle edge angles. Not a bug, just how the construction works:

Offset delta = -0.92:

Offset delta = -1:

2. Regardless of how the shape was constructed, it's a valid geometry that someone might want to offset. The problem seems to be that the code in offsetFromPoints recognizes that the middle edge needs to be removed, but fails to find the intersection point of the remaining side edges.
3. The path closure is handled differently, and that is the reason that the artifact only appears on the bottom left corner of the square, not every corner.

Continuing to investigate...

[z3dev]

@platypii take a look at line 66… I’m wondering if there’s a special condition that requires additional math to find the correct point of intersection.

[z3dev]

Yeah. Those little ‘middle’ edges will be discarded on normal corners because that edge occurs in the middle of outer segments. The normal loops removes those ‘middle’ edges. For closure to work properly, another iteration / check should be performed to adjust the outer segments if intersecting.

[z3dev]

Which brings up another question… let’s say a user has a special shaped path that has N very very small ‘middle’ sections… and offset -N is called… will the current algorithm work properly?

[platypii]

I have done some investigation, but have been more focused on other PRs. First of all I made some simpler examples to demonstrate the problem, and make it easier to debug. Here is a pretty simple one:

const jscad = require('@jscad/modeling')
const { colorize } = jscad.colors
const { offset } = jscad.expansions
const { roundedRectangle } = jscad.primitives

const main = () => {
  const rr = roundedRectangle({ size: [20, 20], segments: 4 })
  const off = offset({ delta: -2, corners: 'round' }, rr)
  return [
    colorize([.5,.5,.5], rr),
    colorize([.5,0,1], off)
  ]
}

module.exports = { main }

One of the better references I've found is: A Survey of Polygon Offseting Strategies. It talks about the problem of offsetting in general, very nicely written.

However, two kind of events might ocurr which do change the topology of the offset polygon; that is, after such events, the offset polygons hsa a different set of connected edges. An edge might contract until it vanishes, even if it started expanding. This is called an edge event. If the source polygon is non-convex, reflex vertices induce a propagation of the consecutive edges at the reflex vertex which might collide with another edge front splitting such oposite edge. This is called an split event.

The current code in jscad has no logic to handle split events. Honestly I think that's fine for now. But the example given here in #1017 is a case where the offset code fails to handle edge events. I believe that we need to "cascade" the edge events, so that when an edge is collapsed, we continue checking the adjacent edges.

[z3dev]

I’ll read the paper.

I think #782 has the same issue, where the shape contracts upon itself, and creates edges with inverted angles.

[z3dev]

I like this note…

However, two kind of events might ocurr which do change the topology of the offset polygon; that is, after such events, the offset polygons has a different set of connected edges..

Maybe one suggestion is to throw an error if the topology changes, i.e. something bad happened.

[z3dev]

However, the document also,says…

Because each event changes the topology, only initial edge events can be determined a priori with trivial local procedures

I think this is what those trivial intersections are trying to solve.

So, the final check should be… if any angles are > PI then throw. The result is junk.

But… maybe there’s a use case for even the crap.

[z3dev]

By the way, for paths, returning two or more pieces (outlines) should be a error. The offset of path is exactly that… a path… it can cross… it can be strange… it can be wrong. But it’s still a path.

Geometry 2D is another story.

[z3dev]

This is far more complex then initially coded. 😃

[paulftw]

Random idea: negative offset of a N vertices polygon is boolean difference of the polygon and N rectangles, where rectangle i is parallel to the edge i, has its length and width equal to delta (bad explanation but I think you get the idea). positive offset is boolean union of the input polygon and similar rectangles. Assuming boolean operations work better than offset and aren't too expensive (they use BSP, don't they?), we can reduce this difficult problem to an already solved one.