Large performance cost for coplanar triangles

[MarcRuble]

Hello there,

I noticed a strong performance slowdown for CSG operations when sides of the objects lie within each other. The following example demonstrates the issue. Setting varyHeight to true results in a total processing time of about 100ms on my system. Setting varyHeight to false however results in the ends of the cylinders to overlap with many coplanar triangles and a processing time of about 300 seconds, about three thousand times slower than the version with varying heights.

const varyHeight = true;
const numCylinders = 3;
const cylinders = [];

for (let i = 0; i < numCylinders; i++) {

    const geometry = new THREE.CylinderGeometry(1.5, 1.5, 3, 48, 1);
    geometry.translate(i, varyHeight ? i * 0.01 : 0, 0);
    cylinders.push(geometry);
}

const evaluator = new CSG.Evaluator();
let result = new CSG.Brush(cylinders[0]);

console.time("CSG total");

for (let i = 1; i < numCylinders; i++) {
    console.time("CSG " + i);
    result = evaluator.evaluate(result, new CSG.Brush(cylinders[i]), CSG.ADDITION);
    console.timeEnd("CSG " + i);
}

console.timeEnd("CSG total");
scene.add(result);

Is there anything one can do to avoid this issue other than avoiding coplanar triangles at all?

Best regards, Marc

[gkjohnson]

Can you please produce a live demonstration using jsfiddle or another web editor?

[MarcRuble]

Yes, I created a jsfiddle here: https://jsfiddle.net/st2am1Lw/4/ Setting varyHeight to true or false and observing the logging in the console should show the difference.

[gkjohnson]

It looks like the triangulation isn't completely resilient to triangles being exactly on top of each other:

The number of triangles is also significantly larger after an operation when two meshes are on top of one another. And even when they are shifted you'll get a ton of resulting triangles (which isn't unexpected):

Generally triangles being coplanar and directly on top of eachother will always be a worst case but it should be able to be handled more effectively.

[ankofl]

Hi, has it been resolved at the moment?

[gkjohnson]

Hi, has it been resolved at the moment?

The issue is still open so no, it has not been resolved.

[xavierjs]

I met this issue with lacking triangles for coplanar triangles. In the Triangle Splitter, here: https://github.com/gkjohnson/three-bvh-csg/blob/f107dbb2841f19bd6dbff582eacf550d004142d1/src/core/TriangleSplitter.js#L7 I increased the EPSILON values:

const EPSILON = 1e-5;
const COPLANAR_EPSILON = 1e-5;
const PARALLEL_EPSILON = 1e-5;

It works like a charm now.

[gkjohnson]

I met this issue with lacking triangles for coplanar triangles.

This only deals with the missing triangles, is that correct? Possibly related to #188, as well.

I increased the EPSILON values:

1e-10 to 1e-5 is a fairly big jump. Have you tried any intermediate values. These are very hard values to tune, it seems 😅 I'm a little hesitant to just change them without an understanding of the side effects but maybe it's an okay thing to do. Are you seeing cases where you have triangles doubled up on top of eachother after the change?

[xavierjs]

In my case, I want to compute the floor plan from the meshes of the walls of a 3D apartment. Y is the vertical axis.

• I create a quad along X,Z that has the size of the bounding box of the apartment along X and Z, + a few feet to be sure to cover all. Y = Y ceiling - 1 foot
• I subtract all walls from the quad.

In this case:

• All faces of the plane are coplanar
• Quickly the meshing of the quad becomes quite uneven: there are huge faces and very small faces.

I got cases when I have triangles doubled but I cannot reproduce them (I tried a lot of stuff in this project). In all cases, in my case (all coplanar faces), increasing epsilons really helps a lot. There is no weird results anymore.

[gkjohnson]

I got cases when I have triangles doubled but I cannot reproduce them (I tried a lot of stuff in this project).

I expect at some point this is unavoidable in the general case with the current approach due to floating point errors. I think anything close to perfect result would require using integer calculations. Though some of the solutions laid out in #51 or #97 could help improve things a bit.

In all cases, in my case (all coplanar faces), increasing epsilons really helps a lot. There is no weird results anymore.

Perhaps it makes sense to expose these epsilon values as options on the triangulator or CSG evaluator classes? If you'd like to make a PR for something like this I can look into getting it merged so this is available.

[jteppinette]

Increasing the epsilon seems like a code smell. Shouldn’t it really be used to just avoid floating point precision issues? When you get away from that use, you are typically trading one failure for another.

Also, 1e-5 can barely be called an epsilon. You are just tuning the algorithm at that point.

If this is necessary, seems you would want to instead pass it to the evaluator as some “distanceFactor” with values 0.0001 to 1. 🤷‍♂️

[gkjohnson]

Increasing the epsilon seems like a code smell. Shouldn’t it really be used to just avoid floating point precision issues? When you get away from that use, you are typically trading one failure for another.

This is why I'm suggesting to expose this as a configurable option. This is an incredibly difficult problem - one that I don't believe is completely avoidable without integer math. Vertices further from the origin will have large floating point epsilons, floating error compounds on operations like multiplication (dot products, matrix math) so the epsilon required will change depending on the math used, and so on. I don't think there is a one-size-fits-all value for this.

Of course the code could probably be tuned to account for error more intelligently so if you're interested in contributing to help address the errors feel free to become more familiar with the code. This project was developed completely in free time and I have fixed a lot of floating pointer error-related issues. But tracking every problem down is not a priority for me. If a configuration option is a low-friction solution that enables people to do their work then I don't see the harm in adding it with a reasonable documentation note.

[xavierjs]

Hello,

It also works with the original EPSILON values, but if I replace this line: https://github.com/gkjohnson/three-bvh-csg/blob/f107dbb2841f19bd6dbff582eacf550d004142d1/src/core/TriangleSplitter.js#L210

By this one:

if ( Math.abs( startDist ) < COPLANAR_EPSILON || Math.abs( endDist ) < COPLANAR_EPSILON ) {

[xavierjs]

OK I have dig into the issue instead of f****g around. The issue is only with COPLANAR_EPSILON only and how it is used. I noticed 2 issues. I will submit a PR very very soon for a fix.

All happens in TriangleSplitter.js. With the proposed fix it works with the original values of the EPSILONs.

1st issue: coplanarity uncertainty

Let say COPLANAR_EPSILON is the uncertainty on points positions. if we have a very very small triangle, and we want to test if a very far away small edge is coplanar with this triangle, a small uncertainty on the triangle position will result in a large uncertainty in the edge neighboorhood (kind of leverage effect).

In splitByPlane(), I add 2 new arguments to evaluate the plane uncertainty:

• planeCenter (OK a plane has no center but...) This is the point used to compute the plane
• planeEdgeSize: The size of the edge used to compute the plane.

In this picture, AB is the smallest edge of the triangle used to compute the plane. To test if a point M belongs to the plane or not, we need to test if distance(M, plane) < epsilon. And epsilon is not COPLANAR_EPSILON but COPLANAR_EPSILON * distance(M, planeCenter) / planeEdgeSize. In the side view, we have the uncertainty represented by e on [AB] level which becomes E at M.

2nd issue: error propagation

I do tens of CSG operation on the same coplanar points, so the error can accumulate. I noticed that, if we detect that and edge is coplanar to a triangle, forcing the edge to belongs to the triangle plane allows to avoid artifacts.