Scalability Issue with csg.js

[mtippett]

Hi,

It looks like the scalability of csg.js is O(n^2). See code in https://github.com/mtippett/jscad-test/tree/master/jscad-csg-perf, this includes both the nodejs application and a svg created with Brendan Gregg's flamegraph tool.

Basically this is an array of coplanar cubes.

Looking at the flamegraph generated for a 40x40 square (1600 elements), the scalability issue is clear in the code searching for a union. The original npm jscad code would not re-tesselate and optimize, so would result in larger files. The file size is workable with jscad/csg.js, however the scalability needs to be improved.

[z3dev]

@mtippett This is really interesting. I'm still learning the world of NODE, and this is another good example of what's possible. Thanks.

It seems that you are working with conversions to STL. Can you just provide some background on why you are choosing this particular functionality?

[mtippett]

I'm not that experienced in nodejs myself. It's more of a convenience language to get me started, however my appraisal of programmatic constructive geometry didn't yeild anything much better than OpenJSCad.org.

In terms of my usage, I'm looking at generating X3D based on data - with the intent to full color 3d print them through shapeways, an example of this might be rendering a 3D visualization of a frequency spectrum

or, more simply

Arguably, I could use a mesh overlay, and might need to look at moving to that. However, the aesthetics of a the blockiness is part of the appeal. I'm of course open to other suggestions on how to achieve this.

The over all pipeline is "2D Data" -> extrusion -> Color export -> Print

Looking at the performance, it is likely that some sort of O(1) or O(n) lookup should be used instead of a linear scan of the existing vertex information. Note that an older version of OpenJSCad (as captured in https://www.npmjs.com/package/jscad would actually work considerably faster. Its clearly didn't optimize the mesh before generating the STL (resulting in huge files). But the performance was about O(N).

I'd want to process and render in 3D data in the 400x400 (160000) range. I'm assuming that CSG want to scale at O(n) or better.

[mtippett]

Hmm.. I just pushed a new version of the test case. It looks like I'm re-using something I shouldn't be.

[mtippett]

No version pushed to jscad. There is minimal performance impact of "cube.union()" for each cube, or doing an array and letting generateOutput do the generation. I've also regenerated the flamegraph to demonstrate the scalability issues, svg is attached in the repo at https://github.com/mtippett/jscad-test/blob/master/jscad-csg-perf/out.nodestacks01.svg (download and view it in a browser for the dynamic controls).

The updated image inline shows that 97% of the 150 or seconds is spent in "union". After generate blob. More insight into how the geometry are "union"ised, would probably help. Note that in this test, there is an array of geometry created, and the generateOutput will iterate over the array of objects and find the union.

Although my use case needs cubes that are co-planer with no gaps, I've seen that overlaps actually help the performance a reasonable amount.

[mtippett]

loadtest.txt

Attached is a quick and dirty benchmark that approximates what I'm doing.

Run it similar to "nodejs loadtest.js a b"

a is the x&y used for a coplanar union operation.

b is the x&y used for a disconnected shell union operation.

My general use case would have a "b" of around 7. Anything with a high "a" ~100, will run out memory and run slowly.

I'm assuming that coplanar or disconnected shells should be able to be optimized for the operations that are done.

[deckar01]

None of the bars actually overlap right? No vertex traversing should really need occur, but the O(n^2) seems to suggest that it did.

It looks like mayOverlap is only effective on the first few iterations of a union. Once the bounding boxes start spanning "grouped" shapes, it produces false positives and the expensive union operations start traversing all the vertexes.

The objects could be partitioned into disjoint sets, united separately, then grouped with the non-overlapping union at the end.

no overlaps	mayOverlap (shapes)	union (vertices)
current	O(s)	O(v^2)
partition	O(s^2)	O(1)

all overlaps	mayOverlap (shapes)	union (vertices)
current	O(s)	O(v^2)
partition	O(s)	O(v^2)

[mtippett]

Hi.

I think I'm actually dealing with the evil area between non-overlapping and overlapping sets. Using the 3D column chart above as a base. I have each column having each face co-planar with another column.

Or from a 3d coordinate space, it can be considered as cubes with corner extents at [[0,0],[1,1]] up against [[0,1],[1,2]]. Similar i guess in concept to z-fighting.

[z3dev]

It looks like mayOverlap is only effective on the first few iterations of a union. Once the bounding boxes start spanning "grouped" shapes, it produces false positives and the expensive union operations start traversing all the vertexes.

Yup. There’s a bug in V1 mayOverlap() Fixed and tested as part of V2.

And as @mtippett has identified, the union of geometries is fastest if THERE ARE OVERLAPS.

In addition, the current algorithm uses the hard coded ESP for determining polygon intersections. So, super large or super small polygons are going to have poor results. And those poor results will cause further issues.

[z3dev]

Just one more note… There’s no reason to union those cubes together, as the conversion to X3D converts each cube (geometry) into an X3D shape. This will be vastly faster.

IF union is required then union everything at the same time. The union logic is optimized for a given set versus union for each new cube.

[z3dev]

@mtippett please try the latest at OpenJSCAD.org

Also, there's a performance test running continuously now. There have been several improvements in the performance of the booleans.