Improving Performance

[giladdarshan]

Hello,

I've been learning how THREE-CSGMesh works in an attempt to improve the performance when dealing with a large number of objects.
As an example, making 14 holes in a plate/cube (as shown below), with the current subtract function, it will need to create a total of ~28 BSP trees (a/b nodes in the function).

By adding support for an array of CSG objects, I'm able to cut down the total operation time from ~1.9 seconds to ~0.21 seconds as it only creates ~15 BSP trees for the above example:

    subtract(csg) {
        let a = new Node(this.clone().polygons);
        a.invert();
        if (csg.isCSG) {
            csg = [csg];
        }
        for (let i = 0; i < csg.length; i++) {
            let b = new Node(csg[i].clone().polygons);
            a.clipTo(b);
            b.clipTo(a);
            b.invert();
            b.clipTo(a);
            b.invert();
            a.build(b.allPolygons());
        }
        a.invert();
        return CSG.fromPolygons(a.allPolygons());
    }

What are your thoughts on this? are there any downsides I'm not seeing?

Thanks,
Gilad

[manthrax]

Looks good to me! Yeah this is definitely a worthy optimization. There is definitely room to improve the API. I've had some thoughts about making the api more "fluent" and adding helper functions like yours, but haven't had the time.

[giladdarshan]

Nice approach but I can imagine it will have some issues with overlapping or complex meshes.
I've already run into the error "Maximum call stack size exceeded" on the Node.build(polygons) recursive function in the past when dealing with large complex meshes.

If you would like to share a more complete example of the code, I can use it for testing when I continue my attempts to make CSG faster.

[manthrax]

One way to speed these kinds of operations up, is to break them into smaller problems.
If you take the intersection of the bounding box of each input, then subtract the box from the larger object.. subtract the smaller object from the result, and then merge the result back into the larger geometry.

Otherwise any CPU/cache/de-recursion based performance improvements will still have an upper limit due to the nature of the algorithm., where currently, every triangle in each mesh has to be tested against every other triangle of the other mesh.

To get REAL big speedups I think you would have to pull in some kind of search acceleration structure like mesh-bvh or an octtree. Then you have a chance of knocking down the dot O complexity, at the cost of making the algorithm quite a bit more complicated.

But that is no easy task.

[manthrax]

You can see an example of the first approach, here:

https://manthrax.github.io/THREE-CSGMesh/v2/index.html

Here I took a complex blobby gold shape, and subtract a high poly text from it.
Doing it naively takes a LONG time.

But cutting out the area of interest into a second piece.. then subtracting the high poly text from that simpler piece, and merging the results back together is very quick.

[manthrax]

So.. there are definitely ways to improve the speed of the algorithm, but they all involve adding a TON more complexity to the algorithm, which IMO is outside the scope of the library, and should either become a fork/optimized version, or some kind of add-on library.

[giladdarshan]

@manthrax I see what you are saying, I ran into the recursion error (stack size exceeded) on the union operation even with the arrays since it still needs to add all polygons from bspB to bspA at the end.

I'm still experimenting but I was able to improve the performance by checking the intersection of all the bspA polygons against the bounding box of bspB and then exempting them from the node build flow.

I also noticed that with some geometries (extruded geometry for example), the node build flow sometimes gets stuck on the same polygons and keeps looping for thousands of times until it errors out with the stack size exceeded error, I've added some logic to check and stop these loops so now I rarely see the stack size exceeded error.

[manthrax]

@giladdarshan That's great. Yeah that sounds like a promising avenue, the intersection/bounds pre-pass.

If you come across a simple repro for the stack exceeded thing, in the form of a gltf file? Let me know and I can take a look if its something easy to fix. You can export an object using the THREE GLTFExporter... via something like this:

function downloadBinary(body, filename, extension='pdf') {
    const blob = new Blob([body]);
    const fileName = `${filename}.${extension}`;

    const link = document.createElement('a');
    // Browsers that support HTML5 download attribute
    if (link.download !== undefined) {
        const url = URL.createObjectURL(blob);
        link.setAttribute('href', url);
        link.setAttribute('download', fileName);
        link.style.visibility = 'hidden';
        document.body.appendChild(link);
        link.click();
        document.body.removeChild(link);
    }
}

import {GLTFExporter} from "threeModules/exporters/GLTFExporter.js"


let exportGLB=(root,fileName,animations=[])=>{
    let exporter = new GLTFExporter();
    let options={binary:true,animations}
    exporter.parse( root, function ( gltf ) {
        console.log( gltf );
        downloadBinary(gltf,fileName,"glb")
    }, options );
}

[giladdarshan]

@manthrax the easiest way for me to reproduce this error is with extruded geometries and then try to union it with a small cylinder, below is a simple example of the extruded geometry:

const points = [];
points.push(new THREE.Vector3(50, 0, 0));
points.push(new THREE.Vector3(-5, 0, 0));
points.push(new THREE.Vector3(-50, 10, 0));
const spline = new THREE.CatmullRomCurve3(points);
const extrudeSettings2 = {
    steps: 200,
    curveSegments: 6,
    bevelEnabled: false,
    extrudePath: spline
};
const circleRadius = 7;
const circleShape = new THREE.Shape().moveTo( 0, circleRadius ).quadraticCurveTo( circleRadius, circleRadius, circleRadius, 0 ).quadraticCurveTo( circleRadius, - circleRadius, 0, - circleRadius ).quadraticCurveTo( - circleRadius, - circleRadius, - circleRadius, 0 ).quadraticCurveTo( - circleRadius, circleRadius, 0, circleRadius );
let geometry2 = new THREE.ExtrudeGeometry(circleShape, extrudeSettings2);
// const tessellateModifier = new THREE.TessellateModifier(4, 10);
// geometry2 = tessellateModifier.modify(geometry2);
// geometry2 = BufferGeometryUtils.mergeVertices(geometry2);
const material2 = new THREE.MeshNormalMaterial({ wireframe: false });
const mesh2 = new THREE.Mesh(geometry2, material2);

With the current CSG I quickly get the error "RangeError: Maximum call stack size exceeded" on Node.build.
If I add the repetition protection to Node.build I can complete the CSG operation.
It's still work in progress but this is the function I call from Node.build if it starts identifying repetition starting:

polygonArrRepeating(parentPolygons, polygons) {
    let repeating = false;
    if (polygons.length !== parentPolygons.length) {
        repeating = false;
        return false;
    }
    for (let i = 0; i < polygons.length; i++) {
        if ((polygons[i].plane.w === parentPolygons[i].plane.w) && (polygons[i].plane.normal.equalTo(parentPolygons[i].plane.normal))) {
            if (polygons[i].vertices.length !== parentPolygons[i].vertices.length) {
                repeating = false;
                return false;
            }
            for (let j = 0; j < polygons[i].vertices.length; j++ ) {
                let childVertex = polygons[i].vertices[j];
                let parentVertex = parentPolygons[i].vertices[j];
                if ((childVertex.pos.equalTo(parentVertex.pos)) && (childVertex.normal.equalTo(parentVertex.normal))) {
                    if (childVertex.uv && parentVertex.uv) {
                        if (childVertex.uv.equalTo(parentVertex.uv)) {
                            repeating = true;
                            // console.log("polygons[i]", polygons[i]);
                            // console.log("parentPolygons[i]", parentPolygons[i]);
                        }
                        else {
                            repeating = false;
                            return false;
                        }
                    }
                    else {
                        repeating = true;
                    }
                }
                else {
                    repeating = false;
                    return false;
                }
            }
        }
        else {
            repeating = false;
            return false;
        }
    }

    return repeating;

}

[giladdarshan]

@manthrax what are your thoughts on the suggested solution here for the recursion issue in node.build?

If I use the function I posted above I end up with some missing polygons in the end geometry, with the below change I can't see holes in the geometry (so far, continuing to test).

Changing the loop in node.build from:

for (let i = 0; i < polygons.length; i++) {
        this.plane.splitPolygon(polygons[i], this.polygons, this.polygons, front, back);
}

To:

this.polygons.push(polygons[0]);
for (let i = 1; i < polygons.length; i++) {
        this.plane.splitPolygon(polygons[i], this.polygons, this.polygons, front, back);
}

[manthrax]

Your repro is missing the first part where you create the first mesh?

Can you perhaps show it in a glitch?

[manthrax]

I really need to make a test suite... if you can give me that small repro, i can start with that :)

[manthrax]

Your 2 line fix looks promising but I want to understand/see the problem before I try to fix it.
If it's not an infinite recursion and instead is just a stack limitation, it might be better to find a way to unroll the recursion.

[manthrax]

@giladdarshan :)

[giladdarshan]

@manthrax, here are the two meshes and the union operation:

const points = [];
points.push(Utils.Vector3(50, 0, 0));
points.push(Utils.Vector3(-5, 0, 0));
points.push(Utils.Vector3(-50, 10, 0));
const spline = new THREE.CatmullRomCurve3(points);
const extrudeSettings2 = {
    steps: 200,
    curveSegments: 12,
    bevelEnabled: false,
    extrudePath: spline
};
const circleRadius = 7;
const circleShape = new THREE.Shape().moveTo( 0, circleRadius ).quadraticCurveTo( circleRadius, circleRadius, circleRadius, 0 ).quadraticCurveTo( circleRadius, - circleRadius, 0, - circleRadius ).quadraticCurveTo( - circleRadius, - circleRadius, - circleRadius, 0 ).quadraticCurveTo( - circleRadius, circleRadius, 0, circleRadius );
let geometry1 = new THREE.ExtrudeGeometry(circleShape, extrudeSettings2);
const material1 = new THREE.MeshBasicMaterial({ color: 0xffff00 });
const mesh1 = new THREE.Mesh(geometry1, material1);
let cubeGeometry = new THREE.CylinderGeometry(5, 5, 10, 6);
let cubeMesh = new THREE.MeshBasicMaterial({color: 0xff0000});
let cube = new THREE.Mesh(cubeGeometry, cubeMesh);
cube.position.y -= 7.5;
mesh1.updateMatrix();
cube.updateMatrix();
let bspA = CSG.fromMesh(mesh1);
bspA.boundingBox.setFromObject(mesh1);
let bspB = CSG.fromMesh(cube);
bspB.boundingBox.setFromObject(cube);
let csgUnion = bspA.union(bspB);
let csgMesh = CSG.toMesh(csgUnion, mesh1.matrix, mesh1.material);
scene.add(csgMesh);

If I change mesh1 from an extruded geometry to a cube or some other simple geometry it will work fine.

If it's not an infinite recursion and instead is just a stack limitation, it might be better to find a way to unroll the recursion.

Do you mean converting the recursion to a regular loop? something like this?

I believe it will run into the same issue of infinite looping unless we solve the issue of the splitPolygon function returning the same front / back arrays after a while with some geometries (which from what I can see is what is happening with extruded geometries).

[manthrax]

interesting yeah. I do mean something like that. and yeah.. I want to understand why it's happening before I attempt to fix it pull a fix. :D

There are limits to this technique which I don't advertise because they don't always matter. Like.. ideally this should only be done with manifold meshes, but you can get away without manifold meshes sometimes.

btw: if you feel like making a fork with bleeding edge improvements, I'm totally on board!

[giladdarshan]

I plan on updating a fork with the improvements, doing some more tests and then.
I'm trying to find an algorithm for triangulating polygons with 4+ vertices as I believe it will help solve the issue, but so far I only found methods for 2D polygons.

I'm also looking into using Octree for CSG, Three.js already has an Octree class so it helps.

[manthrax]

afaik polygons in the algorithm are always triangles.. they are extracted from threejs buffergeometries which only support triangles.

[giladdarshan]

@manthrax right, the incoming geometry always results in triangles, but, the splitPolygon function sometimes creates polygons with 4+ vertices when it hits the spanning type case.

[giladdarshan]

In the toGeometry function you are handling it with the below code, line #171

for (let j = 3; j <= pvlen; j++) {
    (p.shared !== undefined) && (grps[p.shared].push(vertices.top / 3, (vertices.top / 3) + 1, (vertices.top / 3) + 2));
    vertices.write(pvs[0].pos)
    vertices.write(pvs[j - 2].pos)
    vertices.write(pvs[j - 1].pos)
    ....
}

I tried using the same logic in the splitPolygon function when the f/b arrays are bigger than 3 but the result didn't look good, so I assume another / better algorithm is needed for the triangulation.

[giladdarshan]

@manthrax I've updated the changes I made in my fork, still need to do more testing.
There is still room for a lot of improvement, mainly in the split polygon logic.

I've started reading about Octree-Embedded BSPs so I'm going to try and implement something similar (couldn't find code examples for it).
Are you interested to collab on it? I assume you want to keep this library separate and not convert it to Octrees.

[manthrax]

@giladdarshan Sorry for the late response. :) That does sound interesting... I have also been mulling over the idea of using this library https://github.com/gkjohnson/three-mesh-bvh as an acceleration structure.. Curious about your impression of https://arxiv.org/abs/2103.02486 as well?
There is definitely space in the threejs/webgl ecosystem for more CSG implementations! I would be interested. :)

[giladdarshan]

Hey @manthrax, I looked into gkjohnson's BVH implementation (I use it in my website for other things), they also have a question there regarding CSG (Issue #281).

I didn't find code examples for the Octree-Embedded BSPs so I decided to create a new CSG implementation using Octrees from scratch.

There is still more room for improvement and testing but so far it's performing faster and generating less triangles than BSP based CSG libraries.
In the below comparison between BSP CSG (this library) in red (left) and my new Octree CSG library in blue (right).
Octree CSG (mesh3) generated 3687 triangles while BSP CSG (csgTest) generated 1183747 triangles:

It can also be used in combination with gkjohnson's three-mesh-bvh for faster raycasting.

I will invite you later to the project, looking forward for your input and feedback :)

[gkjohnson]

@giladdarshan nice work! Once the project is public do let me know, as well. Getting CSG going using three-mesh-bvh as a traversal structure had been on my list for awhile but I never got the chance to start.

There were other non-BSP approaches I was looking at to help improve perf and memory overall. Happy to contribute ideas, too. I'm interested to see more of this! I'll have to dig through my notes to find other references I was looking at at the time.

[giladdarshan]

Awesome, I've invited both of you and will appreciate any feedback you have.
It's getting late here so tomorrow I will add more documentation there with the logic behind it.

@manthrax I think the changes in my fork are still useful for this library -

• CSG.checkBounds - Flag to determine whether the CSG functions will check for boundaries and filter out non-intersecting polygons to reduce size of BSP tree
• CSG.meshUnion / CSG.meshSubtract / CSG.meshIntersect - Helper functions that accepts the second parameter as a mesh or array of meshes and handles appropriately
• CSG.computeBoundingBox - Computes the bounding box from the BSP tree polygons (used in the helper functions when used with arrays)
• Changes to the CSG class to support the boundary checking
• Changes to the Plane class to support splitting polygons with 4+ vertices
• Changes to the Node class for improving the build function
• Node.polygonArrRepeating - Used in the Node.build function to prevent the build function getting stuck in a recursion loop with the same polygons

[manthrax]

Wow that's looking fantastic @giladdarshan!!
I'd love to see it on a textured example and get a feel for performance.. but just from your wireframe, it looks amaazing!!
A+
I'm going to try to fire yours up locally and take a peek. :)

[giladdarshan]

Thank you :)

Do you happen to have an example that uses the latest Three.js versions? If I try to use "CSGDemo" with the latest Three.js it complains about missing RGBEEncoding / RGBEFormat.

[vanboxsel-engineering]

@giladdarshan I've created a pull request for easier version bumping.
It uses dev-server to resolve the node_modules. I did not take the building of this package into consideration.

[Fyrestar]

If i could suggest some a further improvement relatively simple to add: object pooling would be quite relevant here as there are a lot objects created and cloned through the process, it basically just needs a create-method and "flush" method at the end the user would call when the process is done, to push Polygon, Vertex etc. into an cache array, and instead calling new Vertex etc, a create-function on each class such has:

Vertex.cache = [];
Vertex.new = function ( pos, normal, uv ) {

    const instance = Vertex.cache.pop() || new Vertex;
    
    instance.set( pos, normal, uv );

    return instance;
}

A CSG.flush() could push them back to their cache.

This drastically increases general performance regarding GC and memory, a manual CSG.flushCache() user could call when their app isn't going to use it for now anymore,.

For a bit more advanced solution CSG.flushCache( force = false ), where a average length count is tracked on each class, after every CSG.flush(), and without force = true it would only crop the cache arrays to a reasonable count, freeing memory from rare or a single higher demand, but not clearing them totally empty.

Also having a optional "without A" or "without B" option would be nice if the new polygons from subtraction are not required to be in the final geometry.