Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Scalability Issue with csg.js #12

Open
mtippett opened this issue Feb 12, 2017 · 10 comments
Open

Scalability Issue with csg.js #12

mtippett opened this issue Feb 12, 2017 · 10 comments

Comments

@mtippett
Copy link

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.

screen shot 2017-02-12 at 1 28 29 am

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.

screen shot 2017-02-12 at 1 38 17 am

@z3dev
Copy link
Member

z3dev commented Feb 12, 2017

@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
Copy link
Author

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

image

or, more simply

image

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
Copy link
Author

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

@mtippett
Copy link
Author

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).

screen shot 2017-02-12 at 5 50 04 pm

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
Copy link
Author

mtippett commented Oct 6, 2017

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
Copy link

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
Copy link
Author

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
Copy link
Member

z3dev commented Dec 24, 2020

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
Copy link
Member

z3dev commented Jun 1, 2021

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
Copy link
Member

z3dev commented Aug 14, 2022

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants