bebbi
commented
9 years ago Looks good to me, thanks Hans. I'll merge unless there are comments.
On 21.02.2015, at 20:25, Hans L notifications@github.com wrote:
By combining csg in separate pairs, then combining those pairs, etc, this helps minimize the average complexity of unionSub calls
here is a menger sponge function designed sepcifically to torture test the union operation:
function mengerSponge(x,y,z, s, i) { if (i) { var s = s / 3; i--; return mengerSponge(x - s, y - s, z - s, s, i).concat( mengerSponge(x , y - s, z - s, s, i), mengerSponge(x + s, y - s, z - s, s, i), mengerSponge(x - s, y , z - s, s, i), //mengerSponge(x , y , z - s, s, i), mengerSponge(x + s, y , z - s, s, i), mengerSponge(x - s, y + s, z - s, s, i), mengerSponge(x , y + s, z - s, s, i), mengerSponge(x + s, y + s, z - s, s, i), mengerSponge(x - s, y - s, z , s, i), //mengerSponge(x , y - s, z , s, i), mengerSponge(x + s, y - s, z , s, i), //mengerSponge(x - s, y , z , s, i), //mengerSponge(x , y , z , s, i), //mengerSponge(x + s, y , z , s, i), mengerSponge(x - s, y + s, z , s, i), //mengerSponge(x , y + s, z , s, i), mengerSponge(x + s, y + s, z , s, i), mengerSponge(x - s, y - s, z + s, s, i), mengerSponge(x , y - s, z + s, s, i), mengerSponge(x + s, y - s, z + s, s, i), mengerSponge(x - s, y , z + s, s, i), //mengerSponge(x , y , z + s, s, i), mengerSponge(x + s, y , z + s, s, i), mengerSponge(x - s, y + s, z + s, s, i), mengerSponge(x , y + s, z + s, s, i), mengerSponge(x + s, y + s, z + s, s, i) ); } else { return [CSG.cube({center: [x,y,z], radius: s / 2})]; } }
function main(params) { var spongeBlobs = mengerSponge(0,0,0, 1, params.iterations); //return CSG.cube(); return spongeBlobs.pop().union(spongeBlobs); }
function getParameterDefinitions() { return [ { name: 'iterations', caption: 'Iterations:', type: 'int', default: 3 }, ]; } An iteration 3 took 1727033ms on my computer after changes it took 6596ms
A less torturous menger sponge implementation unioning 20 objects at a time instead of all 20^n at once, still sees decent gains (3638ms vs 2671ms at 3 iterations)
function mengerSpongeUnion(iterations) { var result = CSG.cube({}); var size = 2; for (var i = 0; i < iterations; i++) { result = result.translate([-size, -size, -size]).union([ result.translate([ 0, -size, -size]), result.translate([ size, -size, -size]), result.translate([-size, 0, -size]), //result.translate([ 0, 0, -size]), result.translate([ size, 0, -size]), result.translate([-size, size, -size]), result.translate([ 0, size, -size]), result.translate([ size, size, -size]), result.translate([-size, -size, 0]), //result.translate([ 0, -size, 0]), result.translate([ size, -size, 0]), //result.translate([-size, 0, 0]), //result.translate([ 0, 0, 0]), //result.translate([ size, 0, 0]), result.translate([-size, size, 0]), //result.translate([ 0, size, 0]), result.translate([ size, size, 0]), result.translate([-size, -size, size]), result.translate([ 0, -size, size]), result.translate([ size, -size, size]), result.translate([-size, 0, size]), //result.translate([ 0, 0, size]), result.translate([ size, 0, size]), result.translate([-size, size, size]), result.translate([ 0, size, size]), result.translate([ size, size, size]), ]) size *= 3; } return result; }
function main(params) { return mengerSpongeUnion(params.iterations); }
function getParameterDefinitions() { return [ { name: 'iterations', caption: 'Iterations:', type: 'int', default: 3 }, ]; } You can view, comment on, or merge this pull request online at:
https://github.com/joostn/OpenJsCad/pull/53
Commit Summary
optimize CSG.union for array input File Changes
M src/csg.js (16) Patch Links:
https://github.com/joostn/OpenJsCad/pull/53.patch https://github.com/joostn/OpenJsCad/pull/53.diff — Reply to this email directly or view it on GitHub.
By combining csg in separate pairs, then combining those pairs, etc, this helps minimize the average complexity of unionSub calls
here is a menger sponge function designed sepcifically to torture test the union operation:
An iteration 3 took 1727033ms on my computer after changes it took 6596ms
A less torturous menger sponge implementation unioning 20 objects at a time instead of all 20^n at once, still sees decent gains (3638ms vs 2671ms at 3 iterations)