gkjohnson / three-bvh-csg

A flexible, memory compact, fast and dynamic CSG implementation on top of three-mesh-bvh
MIT License
552 stars 45 forks source link

Incorrect intersection #141

Closed gkjohnson closed 10 months ago

gkjohnson commented 10 months ago

In simple example:

x : -0.012142986465584427
y : 0.3390921921980216
z : 0.10950340016154492
image

TODO: ensure this is not a regression

gkjohnson commented 10 months ago

Intersection edge is definitely found:

image

And triangle is considered intersected:

image
gkjohnson commented 10 months ago

Triangle 803 (index 82) intersects:

image
// main triangle
new THREE.Triangle(
    new THREE.Vector3( 0.20000000298023224, -0.30000001192092896, 0.5 ),
    new THREE.Vector3( 0.30000001192092896, -0.30000001192092896, 0.5 ),
    new THREE.Vector3( 0.30000001192092896, -0.20000000298023224, 0.5 ),
),

// triangles intersecting
new THREE.Triangle(
    new THREE.Vector3( 0.28249262232672057, -0.1912378846156762, 0.5504567293670579 ),
    new THREE.Vector3( 0.2193507175553926, -0.2845100043761895, 0.45595821423796856 ),
    new THREE.Vector3( 0.28249262232672057, -0.2845100043761895, 0.4041390089538499 ),
),
new THREE.Triangle(
    new THREE.Vector3( 0.3628570135344156, -0.1912378846156762, 0.4845034001615449 ),
    new THREE.Vector3( 0.28249262232672057, -0.1912378846156762, 0.5504567293670579 ),
    new THREE.Vector3( 0.28249262232672057, -0.2845100043761895, 0.4041390089538499 ),
)
gkjohnson commented 10 months ago

These two are the culprit


const ogTris = [
    new THREE.Triangle(
        new THREE.Vector3( 0.41619066451535114, -0.8521229388252674, 0.5206621331179401 ),
        new THREE.Vector3( 0.41619066451535114, -0.7377804564390872, 0.5206621331179401 ),
        new THREE.Vector3( 0.376364833930707, -0.7586154241556492, 0.5206621331179401 ),
    )

];

const tris = [

    new THREE.Triangle(
        new THREE.Vector3( 0.5, -0.7071067690849304, 0.5 ),
        new THREE.Vector3( 0.39284747838974, -0.7071067690849304, 0.5879377722740173 ),
        new THREE.Vector3( 0.39284747838974, -0.8314695954322815, 0.39284747838974 ),
    )
];
image
gkjohnson commented 10 months ago

From three-mesh-bvh it looks like this triangle is "just touch". Likely an issue in the splitter.

image
gkjohnson commented 10 months ago

Seems to be related to here, possibly, or the epsilon size. Points are basically sitting on the surface of the plane and we report that one point sits on the positive side - but the "distanceToFunction" reports two are positive in part due to low precision. Increasing the epsilons fixes this - but we'd prefer not to do that.

                    console.log( positiveSide, arr.map( v => plane.distanceToPoint( v ) ) );
                    const singleVert = arr.findIndex( v => {

                        if ( positiveSide >= 2 ) {

                            return plane.distanceToPoint( v ) < 0;

                        } else {

                            return plane.distanceToPoint( v ) > 0;

                        }

                    } );