Easy performance improvement - better choice of cutting plane about csg.js HOT 9 CLOSED

Haha well, it was actually related to npm link and my local copy of csg.js not liking each other , but similar results :)

Btw I tried out the various random functions, and the lookup or min/max seem to yield the best results for the examples that I tried !
This is exciting, I am going to dig a bit further :)

from csg.js.

@jallwine Wow! That's an ambitious project. Very interesting indeed.

I agree with you about the choice. Trees balancing and traversal improves with good choices.

And your point about order is well taken. We hope to improve the order of polygons and points even further in the future as well. So, the choice may become even more important in large designs.

Thanks!

from csg.js.

@jallwine that is very impressive work !
Take a look at your code now: it seems you not do anything special with the input STL files or just use the vertices & polygons directly ? If that is really the case any performance gains should also be present in any other model.
We were planning to add performance benchmarks to lay groundwork for future changes & improvements without impacting perfs so this is very fitting timing :)
I will play around with your solution without hard metrics first to see if we get the same benefits. But a potential 2X speedup would be huge thanks!

from csg.js.

Yeah, I'm just reading in two STL files and performing a CSG operation between them, so I would think most other models would see the same gains.

This is the source file for stl_boolean, the interface that initiates the CSG operations from the command line: https://github.com/AllwineDesigns/stl_cmd/blob/master/src/stl_boolean.cpp

This is where I choose a random index (not actually random, but good enough for this purpose). Just changing the pick variable to 0 about doubles the time to execute the same stl_boolean command. https://github.com/AllwineDesigns/stl_cmd/blob/89879385af7d04ccba6c30005a6139f66663c9b1/src/csgjs/Trees.cpp#L30

This is the random function: https://github.com/AllwineDesigns/stl_cmd/blob/89879385af7d04ccba6c30005a6139f66663c9b1/src/csgjs/util.cpp#L135

Which uses this function from stackoverflow: https://stackoverflow.com/questions/1640258/need-a-fast-random-generator-for-c

from csg.js.

I'm seeing similar performance improvements with CSG.js: https://github.com/AllwineDesigns/csgjs_test

I've included two models (a sphere and a torus), where I've seen the best improvement (~2x). Other models often see an improvement, though maybe not that extreme.

from csg.js.

you are fantastic @jallwine ! Thanks for all the information and the js test code !
I will take it for a spin !
Strangely enough I did a quick test with randomised (using basic math.random) access for the index, and I did not see any visible perf change with the various examples of OpenJSCAD. I did it quite late in the day so I might have missed something, but it seemed like most examples did not cause addPolygonTreeNodes to be called in the first place.

from csg.js.

In my example, I cache the random calls and just use a lookup table, but there are other examples in there to test with.

from csg.js.

@jallwine my bad ! turns out my dev setup keeps reusing a cached version of csg.js for the browser side. In node.js I was able to run a few tests with your changes, and the performance gains are really great !

from csg.js.

Glad to hear it! I've been bit by the browser caching old code so many times. I almost always do a shift+refresh these days :)

from csg.js.