V1 : Intersection creates invalid geometries due to rounding errors

[bluelightning32]

Expected Behavior

Actual Behavior

Steps to Reproduce the Problem

This is my project: https://github.com/bluelightning32/dactyl-openjscad. Every time I make a small change, it causes small rendering glitches, which eventually turn into bigger and bigger problems as the shape is combined into something larger with unions and differences. Sometimes it even visually looks okay in openjscad, but then cura slices it wrong. The project uses lots of spheres. So by the nature of processing so many vertices, some of them happen to be very close to each other.

I spent 1.5 days trying to slightly adjust dimensions in my model to workaround the glitches, but without success.

I created a similar glitch with the below program. I think it's the same problem as what's happening in my project, but it's impossible to debug the problem in my project.

function main () {
    const left_side = cube({size: [10, 200, 10]});
    const right_piece = cube({size: [10, 10, 10]});
    let shift = 4;
    const right_pieces = [];
    for (let i = 0; i < 20; i++) {
        right_pieces.push(translate([10 + shift, i * 10, 0], right_piece));
        shift /= 2;
    }
    const fork = union(left_side, ...right_pieces);
    console.log("fork", fork);
    const split_left_side = intersection(
        translate([0, -10, -10], cube({size: [10, 600, 600], center: false})),
        fork);
    const split_right_side = intersection(
        translate([10, -10, -10], cube({size: [15, 600, 600], center: false})),
        fork);
    console.log("split_left_side", split_left_side);
    console.log("split_right_side", split_right_side);
    //return split_right_side;
    const rejoined = union(left_side, split_right_side);
    console.log("rejoined", rejoined);
    return rejoined;
}

Specifications

• Version: 1.9.0
• Platform: Firefox on Fedora 30.
• Environment: browser

[z3dev]

@bluelightning32 Thanks. I'll take a look at this.

FYI, we found a subtle bug in mayOverlap() function. See https://github.com/jscad/csg.js/issues/137

This causes issues in the resulting shape because union() didn't really 'merge' the two shapes.

[z3dev]

@bluelightning32 Nice test case. I've been looking at this.

I think that the real issue come from this union, which obvously gets some of the polygons wrong. It seems that the union is between left_side and increasing closer right_pieces.

const fork = union(left_side, ...right_pieces);

And then the intersection (later) becomes totally confused.

I'll spend a little more time on this but let me know if you have any other insights.

[bluelightning32]

I couldn't get it to render anything wrong with just unions. I tried building right_side by unioning right_pieces first, which should be about the same as split_right_side, but the union worked with right_side.

[bluelightning32]

I've narrowed it down to the exact cubes that cause the problem. My original repro is a better test case, but this new repro is helpful for debugging the problem.

function main () {
    const left_side = cube({size: [10, 20, 10]});
    const right_piece = cube({size: [10, 10, 10]});
    let shift = .00002;
    const right_pieces = [];
    for (let i = 0; i < 2; i++) {
        right_pieces.push(translate([10 + shift, i * 10, 0], right_piece));
        shift /= 2;
    }
    const right_side = right_pieces[0].unionSub(right_pieces[1]);
    console.log("right_side", right_side);
    const before = left_side.unionSub(right_pieces[0]).unionSub(right_pieces[1]);
    console.log("before", before);
    const fork = before.reTesselated();
    console.log("fork", fork);
    const fork2 = union(left_side, right_side);
    console.log("fork2", fork2);
    const split_left_side = intersection(
        translate([0, -10, -10], cube({size: [10, 600, 600], center: false})),
        fork);
    const split_right_side = intersection(
        translate([10, -10, -10], cube({size: [10, 600, 600], center: false})),
        fork);
    console.log("split_left_side", split_left_side);
    console.log("split_right_side", split_right_side);
    const rejoined = union(left_side, split_right_side);
    console.log("rejoined", rejoined);
    return split_right_side;
}

Those cubes have several points that are 0.0001 apart, which matches this from the openjscad source:

const EPS = 1e-5

From that test case, here is what the cubes look like when they are unioned (with unionSub), but before they are retesselated. Notice that the middle of the fork is missing a face.

After that gets retesselated, it still doesn't have a face in the middle of the fork.

When the right side of the fork is taken with intersection, it is missing the back left face.

After that, all other operations on the shape make the bug worse.

So it seems like the problem starts with the union, although it is so small that it isn't visible in the rendered image. Would you agree?

[z3dev]

I was suspecting something like that. Thanks again for the in-depth analysis, and diagrams!

The retesselate() function is pretty straight forward, but relies on sets of planar polygons. If those sets are slightly off then the joining of sides will not happen. Again, the key will be the union function.

I’ll see if I can reproduce with just a few very close proximity squares. It should be possible.

[bluelightning32]

The repro in my previous comment is basically already 3 very close proximity cubes. Here, I expanded the for loop to make it more obvious:

function main () {
    const left_side = cube({size: [10, 20, 10]});
    const right_piece = cube({size: [10, 10, 10]});
    const right_piece_front = translate([10.00002, 0, 0], right_piece);
    const right_piece_back = translate([10.00001, 10, 0], right_piece);

    const before_retesselation = left_side.unionSub(right_piece_front).unionSub(right_piece_back);
    console.log("before_retesselation", before_retesselation);
    const fork = before_retesselation.reTesselated();
    console.log("fork", fork);
    const split_right_side = intersection(
        translate([10, -10, -10], cube({size: [10, 600, 600], center: false})),
        fork);
    console.log("split_right_side", split_right_side);
    return split_right_side;
}

See how the back left side is missing.

It seems the algorithms were designed to consider any 2 vertexes that are 0.00001 or closer as equivalent. The problem occurs when there are 3 vertexes, and the middle vertex is 0.00001 away from both of its neighbors, but the first and second vertexes are 0.00002 apart from each other. Should all of those vertexes be considered the same?

In my repro, that situation occurs before retesselation. Face number 14 from the first diagram in my previous comment is 0.00001 away from face 4 in the x direction. Sorry, I didn't draw that gap in the diagram. The left edge of face 9 is shifted another 0.00001 away from face 14 in the x direction.

What should retesselation do in that case? Should retesselation consider face 9 to be touching face 4, even though they are 0.00002 apart?

[z3dev]

Its my opinion that union should bring the sides together because...

• faces are planar (a difficult calculation when close)
• points are within EPS of each other

Thanks again. I’ll look some more into this but we are approaching some difficult precision issues.

By the way, we want retesselate() to be very specific... join planar adjacent polygons... period. Let’s focus on union.

[bluelightning32]

Sorry, can you be more specific on which sides union should be bringing together?

You mentioned points being within eps of each other. Which points are you referring to? A big part of the problem is that the vertices of faces 10 and 5 are 2*eps apart.

Is there a more real time form of communication I could use to discuss this with you? My Google Hangouts id is bluelightning32@gmail.com.

[z3dev]

The issue is really choosing the correct EPS (precision) used when detecting coplanar polygons. The Boolean arithmetic is based on float (not integer) math so there is a limit in the precision of comparisons.

I will retry your examples using a slightly modified version of V2. It should be interesting.

[z3dev]

@bluelightning32 still there?

i took a look at this issue within V2 JSCAD. Here's the equivalent code of your last example.

const { primitives, colors, transforms, booleans } = require('@jscad/modeling')

const {colorizeGeom3} = require('./colorizeGeom3') // SPECIAL ROUTINE

const main = (params) => {
  const left_side = colors.colorize([0, 0, 0], primitives.cuboid({size: [10, 20, 10]}))
  const right_piece = colors.colorize([1, 1, 1], primitives.cuboid({size: [10, 10, 10]}))
  const right_piece_front = colors.colorize([1, 0, 0], transforms.translate([10.00002, 0, 0], right_piece))
  const right_piece_back = colors.colorize([0, 1, 0], transforms.translate([10.00001, 10, 0], right_piece))
//return [left_side, right_piece, right_piece_front, right_piece_back]

  const fork = booleans.union(left_side, right_piece_front, right_piece_back)
//return colorizeGeom3(fork)

  const block = transforms.translate([10, -10, -10], primitives.cuboid({size: [10, 600, 600]})) // ADJUST X
//return [fork, block]

  const split_right_side = booleans.intersect(block, fork)

  return colorizeGeom3(split_right_side)
}

module.exports = { main }

It seems that V2 is better behaved about the 'paralell' polygons. The results were good, up to 9.9999 for ADJUST X.

[bluelightning32]

I'm glad you're making progress.

It seems like you ported a very specific repro of the problem to V2. I'm worried that that repro may be too specific to V1. The first comment in this bug has a more general reproduction of the problem. Have you tried porting that to V2?

Since I filed this bug, I've been doing research on boolean intersection algorithms. I'm very slowly trying to write my own algorithm in C++. I now have more appreciation for the difficulty of the problem.

[z3dev]

@bluelightning32 yeah. good luck on the C++ implementation. there was a guy that ported JSCAD to C++ once. maybe you can find his code.

anyway, V2 is the future, so you'll have to move to the newer version. there are no planned bug fixes for V1.

i'll try the full example, but don't wait. try V2.

[z3dev]

@bluelightning32 there’s been a lot of progress since we last talked. V2 JSCAD has been released, which includes improvements in many areas. Have you tried any of your designs with the latest versions?

[bluelightning32]

I updated the repro for the V2 API:

const jscad = require('@jscad/modeling')
const { primitives, transforms, booleans } = require('@jscad/modeling')

const main = (params) => {
  const left_side = primitives.cuboid({size: [10, 200, 10], center: [5, 100, 5]});
  const right_piece = primitives.cuboid({size: [10, 10, 10], center: [5, 5, 5]});
  let shift = 4;
  const right_pieces = [];
  for (let i = 0; i < 20; i++) {
    right_pieces.push(transforms.translate([10 + shift, i * 10, 0], right_piece));
    shift /= 2;
  }
  const fork = booleans.union(left_side, ...right_pieces);
  const split_left_side = booleans.intersect(
        primitives.cuboid({size: [10, 600, 600], center: [5, 300, 300]}),
        fork);
  const split_right_side = booleans.intersect(
        transforms.translate([10 + 15/2, 0, 0], primitives.cuboid({size: [15, 600, 600]})),
        fork);
  const rejoined = booleans.union(left_side, split_right_side);
  return rejoined;
}

module.exports = { main }

V2 is a little better, but the test still fails.

Expected

Actual

[z3dev]

@bluelightning32 Interesting indeed. I will take another look at this when I get some band width.

[z3dev]

FYI, 3D hulls are supported now. :)

[z3dev]

@bluelightning32 try this...

  let fork = booleans.union(left_side, ...right_pieces);
  fork = modifiers.snap(fork)

Basically, this adjust the vertices to a calculated 'EPS' based on the size of the shape. So, all those vertices with really really small precision (0.00000762939453125) are snapped to the EPS of the shape.

And, the given test case works now.

[bluelightning32]

I finished writing a 3d boolean operation library in C++ that uses exact arithmetic, and as such doesn't have rounding problems like this.

The project includes a thorough design doc. If you're interested, I'd love feedback on it. https://github.com/bluelightning32/walnut/

[hrgdavor]

@bluelightning32 it is very interesting. care to chat on discord ? https://discord.gg/UXtQcA6 is it related to this ? https://arxiv.org/pdf/2103.02486.pdf ?