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:

three-bvh-csg/src/core/TriangleSplitter.js

Line 7 in f107dbb

const EPSILON = 1e-10;

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.