Triangulation error near precision limit

[elalish]

@pca006132 I'm breaking you're repro out here, since I think it's separate from the issue it's in currently, but definitely worth looking into. I can also repro it locally, which is helpful.

Copied from #139 (comment), which was inspired from #141 (comment)

TEST(Boolean, Close) {
  Manifold a = Manifold::Sphere(10, 256);
  Manifold result = a;
  for (int i = 0; i < 10; i++) {
    std::cout << i << std::endl;
    result ^= a.Translate({a.Precision()/10 * i, 0.0, 0.0});
    EXPECT_TRUE(result.IsManifold());
    EXPECT_TRUE(result.MatchesTriNormals());
  }
}

What I need to check: is this polygon actually epsilon-overlapped, or does the triangulator just have a bug? If it is overlapped, this may imply the precision is not well-bounded (due to nearly-parallel planes?), in which case it may be better to look into making the triangulator robust to overlapping input rather than intentionally failing.

[elalish]

The first problem polygon is not overlapped, but it is entirely colinear within precision. It's an error in my handling of uncertain East/West positioning. Once I fix that we'll see if this test exposes any other errors.

[pca006132]

Some thoughts about tracking precision:

If we consider the precision as 2 terms: inherent error and floating point error, the updated precision after transformation M should probably be oldPrecision * det(M), kTolerence*bbox.Scale() because the inherent error is scaled according to the transformation and is independent of the floating point error, while the floating point error is independent of the percentage error in the original model. (Not sure if we should use determinant or the max of norms of the 3x3 translation matrix)

The current way of scaling the precision by glm::max(1.0f, newScale / oldScale) looks a bit weird to me: consider a line (0, 0, 0) to (0, 0, 1) with precision 0.01, if we transform it to (0, 0, -1) to (0, 0, 1), the precision should be 0.02, but the current calculation will only give 0.01 because the maximum absolute coordinate is still 1. Also, when we scale the model down, we should get better precision.

[pca006132]

Also, when we perform boolean operations, should we take the precision into account? It seems that the boolean operation code do not use precision when checking for overlaps, including both the shadow code and the bounding box overlap check.

[elalish]

The Boolean operation does not account for precision; its robustness is based on exact comparisons and ensuring that floating-point equality is handled consistently. The precision is only used in the triangulation and decimation steps at the end.

You make a good point regarding my precision calculations; I don't think I spent as much time thinking about that as I should have. Probably a good idea to add a few more simple tests like you lay out and update the math until they all pass. I'm pretty sure you're on the right track.

[pca006132]

If we want to change the precision calculation, we might as well want to change some APIs because we do not have the precision information for them. For example, we currently don't track precision for polygons which we probably should, and the precision after the Warp operation is user defined. We probably want to allow the users to set the precision as well, which the function is currently not exposed to users.

[elalish]

Agreed that the precision should be settable. I don't think we want to track precision per face, as it gets too complicated in the API.

[pca006132]

I don't mean to track precision per face, just precision for some polygons, and use that as the precision for models constructed by extruding/revolving the polygon. When we extract a polygon from a solid, either its face or through some slice API, it will inherit the precision of the model. Although we may need to do some scaling for the precision if the face is not axis aligned.

[elalish]

Oh, interesting. Yes, that's a good idea too.

[fire]

Yay!