Remove call stack size restriction

[thehans]

Rendering spheres or other round objects with high detail can result in "Maximum call stack size exceeded" exceptions due to highly recursive functions involved.
By rewriting these functions to be iterative and effectively handle their own call stack, detail can be set arbitrarily high.

[joostn]

Nice work! But I think there's still a little bug, http://thehans.github.io/OpenJsCad/processfile.html is hanging on one of my jscad files. It's hanging in addPolygonTreeNodes. if(polygontreenodes.length === 0) continue; is causing an endless loop there.

Here's my jscad file:

function main()
{
OpenJsCad.log(new Date()+": 10");
    var hidetopbottomplates=false;
    var pcbthickness=1.7;
    var pcbwidth=38.5+49.5+3*5;
    var pcbdepth=49.5+2+15;
    var pcbsideclearance=0;
    var pcbtopclearance=25; // absolutely necessary
    var pcbtopextraclearance=2;
    var pcbbottomclearance=8; // maximum height below pcb

    var caseouterroundradius=4;
    var casesidethickness=3;
    var casetopbottomthickness=2;
    var caseinnerroundradius=caseouterroundradius-casesidethickness;
    if(caseinnerroundradius < 0.1) caseinnerroundradius=0.1;
    var caseshellsplitz=0;

    var caseoutertopz=pcbthickness/2 + pcbtopclearance + pcbtopextraclearance + casetopbottomthickness;
    var caseouterbottomz=-pcbthickness/2 - pcbbottomclearance - casetopbottomthickness;
    OpenJsCad.log("outer height: "+(caseoutertopz-caseouterbottomz));
    var caseouterdimensions=new CSG.Vector3D(pcbwidth+2*pcbsideclearance+2*casesidethickness, pcbdepth+2*pcbsideclearance+2*casesidethickness, caseoutertopz-caseouterbottomz);
    var casecenter=new CSG.Vector3D(0,0,(caseoutertopz+caseouterbottomz)/2);

    var pcb=CSG.cube({
        center: [0,0,0],
        radius: [pcbwidth/2, pcbdepth/2, pcbthickness/2],
    });
    var pcbcutout=CSG.cube({
        center: [0,0,0],
        radius: [pcbwidth/2, pcbdepth/2, pcbthickness/2],
    });
    var caseouterfootprint=CAG.roundedRectangle({
        center: [0,0],
        radius: [caseouterdimensions.x/2, caseouterdimensions.y/2],
        roundradius: caseouterroundradius,
    });
    var caseinnerfootprint=CAG.roundedRectangle({
        center: [0,0],
        radius: [caseouterdimensions.x/2-casesidethickness, caseouterdimensions.y/2-casesidethickness],
        roundradius: caseinnerroundradius,
    });
    var caseshellfootprint=caseouterfootprint.subtract(caseinnerfootprint);
    var casebottomshell=caseshellfootprint.extrude({
        offset: [0,0,caseshellsplitz-caseouterbottomz],
    }).translate([0,0,caseouterbottomz]);
    var casebottomplate=caseinnerfootprint.extrude({
        offset: [0,0,casetopbottomthickness],
    }).translate([0,0,caseouterbottomz]);
    var casetopshell=caseshellfootprint.extrude({
        offset: [0,0,caseoutertopz - caseshellsplitz],
    }).translate([0,0,caseshellsplitz]);
    var casetopplate=caseinnerfootprint.extrude({
        offset: [0,0,casetopbottomthickness],
    }).translate([0,0,caseoutertopz-casetopbottomthickness]);
    var topcase=casetopshell;
    var bottomcase=casebottomshell;
    if(!hidetopbottomplates)
    {
        bottomcase=bottomcase.union(casebottomplate);
        topcase=topcase.union(casetopplate);
    }
OpenJsCad.log(new Date()+": 20");

    var studx1=-pcbwidth/2+5+38.5/2-33.3/2;
    var studx2=studx1 + 33.3;
    var studx3=-pcbwidth/2+5+38.5+5+49.5/2-41.8/2;
    var studx5=studx3 + 41.8;
    var studx4=studx5 - 31.6;
    var study1=pcbdepth/2-50.6/2-2+44.5/2;
    var study2=study1-44.5;
    var study3=pcbdepth/2-49.5/2-2+42/2;
    var study4=study3-42;

    var studspositions=[
        [studx1, study1],
        [studx2, study1],
        [studx1, study2],
        [studx2, study2],
        [studx3, study3],
        [studx5, study3],
        [studx4, study4],
        [studx5, study4],
    ];

    var nutheight=5;
    var nutextra=2;
    var nutwidth=5.4 + 0.3;
    var screwradius=1.6 + 0.4;
    var boltheight=9;
    var boltextra=2;
    var boltradius=5.5/2 + 1;
    var studbottomadd=CSG.cylinder({
        start: [0,0,caseouterbottomz],
        end: [0,0,caseouterbottomz + nutheight + nutextra],
        radius: 6
    }).union(CSG.cylinder({
        start: [0,0,caseouterbottomz],
        end: [0,0,-pcbthickness/2],
        radius: 4
    }));
    var studbottomsubtract=hexnutcutout(nutwidth).extrude({
        offset: [0,0,nutheight],
    }).translate([0,0,caseouterbottomz]).union(CSG.cylinder({
        start: [0,0,caseouterbottomz],
        end: [0,0,-pcbthickness/2],
        radius: screwradius
    }));
    var studbottomadds=[];
    var studbottomsubtracts=[];
    var studtopadd=CSG.cylinder({
        start: [0,0,caseoutertopz],
        end: [0,0,caseoutertopz - boltheight - boltextra],
        radius: 6
    }).union(CSG.cylinder({
        start: [0,0,caseoutertopz],
        end: [0,0,pcbthickness/2],
        radius: 4
    }));
    var studtopsubtract=CSG.cylinder({
        start: [0,0,caseoutertopz],
        end: [0,0,caseoutertopz - boltheight],
        radius: boltradius
    }).union(CSG.cylinder({
        start: [0,0,caseoutertopz],
        end: [0,0,pcbthickness/2],
        radius: screwradius
    }));
    var studtopadds=[];
    var studtopsubtracts=[];
    studspositions.forEach(function(pos){
        pos=new CSG.Vector2D(pos);
        studbottomadds.push(studbottomadd.translate([pos.x, pos.y, 0]));
        studbottomsubtracts.push(studbottomsubtract.translate([pos.x, pos.y, 0]));
        studtopadds.push(studtopadd.translate([pos.x, pos.y, 0]));
        studtopsubtracts.push(studtopsubtract.translate([pos.x, pos.y, 0]));
    });
    bottomcase=bottomcase.union(studbottomadds);
    bottomcase=bottomcase.subtract(studbottomsubtracts);
    topcase=topcase.union(studtopadds);
    topcase=topcase.subtract(studtopsubtracts);

    topcase=topcase.subtract(CSG.cube({
        corner1: [-pcbwidth/2+5+38.5/2-31/2, pcbdepth/2-50.6-2+4.20, pcbthickness/2],
        corner2: [-pcbwidth/2+5+38.5/2+31/2, pcbdepth/2-2-4.20, pcbthickness/2+15],
    }));
OpenJsCad.log(new Date()+": 30");

    var usbx1=-pcbwidth/2+5+38.5+5+49.5-25;
    var usbx2=-pcbwidth/2+5+38.5+5+49.5-11;
    var usbz1=pcbthickness/2 + 1;
    var usbz2=-pcbthickness/2 - 7.5;
    var usbcutout=CSG.cube({
        corner1: [usbx1, pcbdepth/2, usbz1],
        corner2: [usbx2, pcbdepth/2+100, usbz2],
    });
    var piperadius=8.5;
    var pipecutoutx=-pcbwidth/2+5+14;
    var pipecutoutz=caseouterbottomz+casetopbottomthickness+piperadius;
    var pipecutout=CSG.cylinder({
        start: [pipecutoutx, -pcbdepth/2, pipecutoutz],
        end: [pipecutoutx, -pcbdepth/2-100, pipecutoutz],
        radius: piperadius,
    });

    var wirecutoutx1=-pcbwidth/2+5+38.5+5+18;
    var wirecutoutx2=wirecutoutx1 + 20;
    var wirecutoutz1=caseshellsplitz;
    var wirecutoutz2=wirecutoutz1+2;
    var wirecutout=CSG.cube({
        corner1: [wirecutoutx1, -pcbdepth/2, wirecutoutz1],
        corner2: [wirecutoutx2, -pcbdepth/2-100, wirecutoutz2],
    });

    var antennaconnectorradius=3.1;
    var antennaconnectorcutoutx=-pcbwidth/2+5+38.5+5+49.5-20;
    var antennaconnectorcutoutz=16;
    var antennaconnectorcutout=CSG.cylinder({
        start: [antennaconnectorcutoutx, pcbdepth/2, antennaconnectorcutoutz],
        end: [antennaconnectorcutoutx, pcbdepth/2+100, antennaconnectorcutoutz],
        radius: antennaconnectorradius,
    });
OpenJsCad.log(new Date()+": 40");

    var d1=10;
    var d2=12;
    var d3=2;
    var d4=2;
    var d5=1;
    var sidetabtop=CAG.rectangle({
        corner1: [-d1,0],
        corner2: [d1,d2]
    }).subtract(CAG.rectangle({
        corner1: [-d3,d3+d5],
        corner2: [d3,d2]        
    })).subtract(CAG.circle({center: [0,d3+d5], radius: d3}));  
    var d6=7;
    var d7=10;
    var d8=3;
    var sidetabside=CAG.fromPoints([[0,d6], [d7,0], [0,0]]);
    var sidetabside3d=sidetabside.extrudeInPlane("Y","Z", d8);
    var sidetab=sidetabtop.extrudeInPlane("X","Y", d4)
        .union([sidetabside3d.translate([-d1+d8/2,0,d4/2]), sidetabside3d.translate([d1-d8/2,0,d4/2])])
        .translate([0, 0, d4/2 + caseouterbottomz]);
    var sidetab1=sidetab.translate([0,caseouterdimensions.y/2,0]);
    var sidetab2=sidetab1.mirroredY();
    bottomcase=bottomcase.union([sidetab1, sidetab2]);

OpenJsCad.log(new Date()+": 50");

//bottomcase=bottomcase.intersect(CSG.cube({center: [studspositions[6][0], studspositions[6][1], caseouterbottomz], radius: [10,10,1000]}));

    topcase=topcase.subtract([usbcutout, pipecutout, wirecutout, antennaconnectorcutout]);
    bottomcase=bottomcase.subtract([usbcutout, pipecutout, wirecutout, antennaconnectorcutout]);

    var result=bottomcase.union(topcase);
OpenJsCad.log(new Date()+": 60");
    return [result, bottomcase, topcase];
}

function hex2d(r)
{
    var points=[0,1,2,3,4,5].map(function(i){
        return CSG.Vector2D.fromAngleDegrees(i*60).times(r);
    });

    return CAG.fromPoints(points);
}

function hexnutcutout(edgedistance)
{
    var d=edgedistance/2;
    var r1=d/Math.cos(10*Math.PI/180);
    var r2=d/Math.cos(30*Math.PI/180) * 1.1;
    var points=[];
    for(var i=0; i < 18; i++)
    {
        var r=((i%3) == 0)? r2:r1;
        var angle=i*20;
        points.push(CSG.Vector2D.fromAngleDegrees(angle).times(r));
    }
    return CAG.fromPoints(points);
}

[thehans]

ok it should be fixed now

[bebbi]

Very useful, thanks Hans. I'll merge tomorrow if no further input.

[joostn]

Hi Hans, It's working fine now. The only drawback is that it is slower than the original. I only tested my project (see above) which ran in ~4400ms but now takes ~8000ms, basically negating hours I've spent optimizing csg.js..

I did a quick run in Chrome's profiler, it looks like addPolygonTreeNodes is indeed running slower in your version. I don't see a problem with the code so it just seems that the JIT can better optimize the recursive version.

Maybe a hybrid approach would be the solution: allow addPolygonTreeNodes to recurse up to a certain depth. Pass the 'stack' variable as a parameter between calls so that when the maximum stack depth is reached it will just push onto the 'stack' variable instead of further recursing. Back at level 0 we can continue processing the remainder. I'd be happy to give a shot at this but I don't have time at the moment.

Or maybe you have another idea?

[joostn]

BTW I see one easy optimization: stack.push is always followed by stack.pop, so it could be rewritten to something like this (addPolygonTreeNodes):

if (frontnodes.length > 0) {
    if(!node.front) node.front = new CSG.Node(node);
    args={'node': node.front, 'polygontreenodes': frontnodes};
    if (backnodes.length > 0) {
        if(!node.back) node.back = new CSG.Node(node);
        stack.push({'node': node.back, 'polygontreenodes': backnodes});
    }
}
else if (backnodes.length > 0) {
    if(!node.back) node.back = new CSG.Node(node);
    args={'node': node.back, 'polygontreenodes': backnodes};
}
else
{
    args = stack.pop();
}

And probably you can even bypass going through the args struct, every little bit will help here because it's the hottest code part. No time to test this right now though

[thehans]

Thanks for the feedback, from my testing I had not noticed such a significant difference in execution time.

I suspected my version was slightly slower. I did some basic comparison (I was being lazy and just manually counting seconds) but the added time seemed to be < 10% which seemed acceptable for the increase in functionality.

I'll do more testing with proper timestamps and profiling etc and see what I can do to improve the execution time.

I was already planning on trying some optimizations to the code in general as my next step, just didn't want to change too much at once and confuse the issue.

On Mon, Feb 2, 2015 at 3:14 PM, joostn notifications@github.com wrote:

BTW I see one easy optimization: stack.push is always followed by stack.pop, so it could be rewritten to something like this (addPolygonTreeNodes):

if (frontnodes.length > 0) { if(!node.front) node.front = new CSG.Node(node); args={'node': node.front, 'polygontreenodes': frontnodes}; if (backnodes.length > 0) { if(!node.back) node.back = new CSG.Node(node); stack.push({'node': node.back, 'polygontreenodes': backnodes}); } }else if (backnodes.length > 0) { if(!node.back) node.back = new CSG.Node(node); args={'node': node.back, 'polygontreenodes': backnodes}; }else { args = stack.pop(); }

And probably you can even bypass going through the args struct, every little bit will help here because it's the hottest code part. No time to test this right now though

— Reply to this email directly or view it on GitHub https://github.com/joostn/OpenJsCad/pull/52#issuecomment-72539177.

[bebbi]

just noticed the additional commits. Performance now appears same as recursive version. Is there anything left before we pull this?

[joostn]

Same here: seems to work fine, and no speed differences anymore!

[thehans]

Sorry for late reply. I agree, I think it is good for pull now. Thanks for reviewing.