V2 : 2D union does not create a closed path

[MatzeS]

Occurs on current V2 branch, please label V2.

Given the following example:

const { circle, rectangle } = require('@jscad/modeling').primitives
const { extrudeLinear } = require('@jscad/modeling').extrusions
const { union } = require('@jscad/modeling').booleans
const { translate } = require('@jscad/modeling').transforms

const main = params => {

    var c = circle({ radius: 2, segments: 4 });
    var r = translate([1, 1], rectangle({ size: [2, 2] }));
    var geometries = [r, c];
    const newgeometries = geometries.map((geometry) => extrudeLinear({ height: 1 }, geometry));

    return union(geometries);
}

module.exports = { main }

And rendering it with cli: node cli.js test.js -of svg -o test.svg
Produced the following error:

Error: the given geometry is not closed. verify proper construction
    at Object.toOutlines (/opt/jscad/packages/modeling/src/geometry/geom2/toOutlines.js:81:15)
    at convertGeom2 (/opt/jscad/packages/io/svg-serializer/index.js:118:33)
    at /opt/jscad/packages/io/svg-serializer/index.js:108:21
    at Array.forEach (<anonymous>)
    at convertObjects (/opt/jscad/packages/io/svg-serializer/index.js:104:11)
    at Object.serialize (/opt/jscad/packages/io/svg-serializer/index.js:70:24)
    at prepareOutput (/opt/jscad/packages/io/io/prepareOutput.js:49:45)
    at solidsAsBlob (/opt/jscad/packages/io/io/index.js:19:56)
    at /opt/jscad/packages/cli/src/generateOutputData.js:74:14
    at processTicksAndRejections (internal/process/task_queues.js:97:5)

I would expect the following image rendering:

However, OpenJSCAD is not able to render this correctly, since... well the path is not closed...

Let me explain:
We are combining a circle and a rectangle by a union operation. The circle has a segment count of 4 which ultimately degenerates it to a diamond. However, the coordinates of this diamond are due to construction from sin/cos functions not perfect. The corner points would be ideally [2,0], [0,2],[-2,0],[0,-2], but due to floating point arithmetic and sin/cos we get something like e.g. 1.2246468525851679e-16 for 0.
In general this is totally expected and no problem as these numbers are essentially zero.
However, when the outline of this union shape is computed the edge of the rectangle and the circle do not perfectly meet. The rectangle hits [2,0] perfectly and the circle hits say [2, 0.000000001].

In packages/modeling/src/geometry/geom2/toOutlines.js the algorithm walks around the the union connecting the edges and fails at this critical point. In particular in line 79 when looking up the next edge through the vertex map. This map lookup is obviously based on equality of points, which is not met.

Now, in my opinion there are two solutions.

1. The problem does not occur on 3D geometries, although the 2D case is based on the 3D union operation. We can conclude that it should be possible to improve the reduction of the 3D case to the 2D case somehow that the path turns out to meet perfectly with all edges. (this would be a good solution.

2. We could change the algorithm to account for an epsilon region around points when walking through the edges. I have implemented this locally and it works, but in my opinion this is a very ugly fix.

Thoughts? Comments?

[z3dev]

It’s a rounding issue introduced by the union function (BSP logic). I’ve seen this before in other reported issues. There’s no way to eliminate the rounding produced by the BSP logic, as there are bound to be side cases of all kinds.

The fix is basically ‘snap’ the 2D points to a specific precision. This eliminates all the extra unless precision.

Thanks for the test case... I’ll add to the test suite.

[z3dev]

By the way, we could swap ideas on a fix. I have some code as well.

[MatzeS]

  function epsilonTest(a, b) {
    return Math.abs(a - b) < 0.001;
  }
  function getNext(map, vertex) {
    var candidates = Array.from(map.keys())
      .filter(point => point.map((coordinate, index) => epsilonTest(vertex[index], coordinate))
        .reduce((acc, cur) => acc && cur, true));
    return map.get(candidates[0]);
  }

And in line 79: let nextpossiblesides = getNext(vertexMap, nextvertex);

I haven't shared yet because this is not good code. I am not a JS developer.
But I think you can see the idea...

[z3dev]

Correct. That’s were the precision must match in toOutlines There are other places in the library where precision also matters.

The best solution must produce 2D geometry with perfect precision.

I’ll add my solution to a branch so reviews are possible.

[z3dev]

#408 3D precision issues
#354 3D precision issues
jscad/csg.js#194 precision issues
jscad/csg.js#93 precision issues

And here’s a hint about the real issue inside the BSP trees.

Dirk Gegorius wrote a document about QuickHull. Page 30 (2d) and 77 (3d) have a formula for creating an epsilon value.

[z3dev]

And here’s the issue that led to my solution. jscad/csg.js#15

[z3dev]

@MatzeS please review the changes in pull request #535

You can try those changes by

• git pull
• git checkout v2-2d-snap-to-eps

[MatzeS]

Solved with #535