Stackoverflow

[jimbok8]

I have many instances over stackoverflow exception Exception in thread "JavaFX Application Thread" java.lang.StackOverflowError at java.util.HashSet.add(HashSet.java:220) at java.util.stream.DistinctOps$1$2.accept(DistinctOps.java:174) at java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:175) at java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1382) at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:481) at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:471) at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708) at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:499) at eu.mihosoft.jcsg.Node.build(Node.java:244) at eu.mihosoft.jcsg.Node.build(Node.java:259) at eu.mihosoft.jcsg.Node.build(Node.java:259) at eu.mihosoft.jcsg.Node.build(Node.java:259) ...

In one run I have a success rate of about 80% with 20% failures, where the geometries are similar but different.

I have tried increasing the stack size with this runtime option: -Xss16m But this seems to make no difference.

Any thoughts or ideas please? Thanks. Jim

[jimbok8]

I think a fix to this problem might be found in a fix to the original csg.js This fix by LinJiarui can be found here: https://github.com/evanw/csg.js/pull/16 resolve the following issue: when build 2 or more coplanar polygons, the original method maybe split all the polygons into the front node (or the back node), thus leads to stackoverflow. The JavaScript differences are shown here: https://github.com/evanw/csg.js/pull/16/commits/d4efa20e8f3d98cc24c824d4367d55e44ecc3a6f

My Java interpretation of the JavaScript build method in Node.java is:

public final void build(List<Polygon> polygons) {
    Polygon myPolygon = null;
    boolean thisPlaneIsNull = false;
    if (polygons.isEmpty()) return;

    if (this.plane == null) {            
        myPolygon = polygons.get(0);            
        this.plane = polygons.get(0)._csg_plane.clone();
        this.polygons.add(myPolygon);
        thisPlaneIsNull = true;
    }

    polygons = polygons.stream().filter(p->p.isValid()).distinct().collect(Collectors.toList());

    List<Polygon> frontP = new ArrayList<>();
    List<Polygon> backP = new ArrayList<>();

    // parellel version does not work here
    for (Polygon polygon: polygons){
        if (thisPlaneIsNull && polygon==myPolygon){                
        } else {
            this.plane.splitPolygon(polygon, this.polygons, this.polygons, frontP, backP);
        }
    }

    if (frontP.size() > 0) {
        if (this.front == null) {
            this.front = new Node();
        }
        this.front.build(frontP);
    }
    if (backP.size() > 0) {
        if (this.back == null) {
            this.back = new Node();
        }
        this.back.build(backP);
    }
}

Please could someone check this new build method, to see if this is a good fix. Thanks. Jim

[altavir]

Just hit the same problem. Is it going to be fixed?

[rpc1]

Have the same issue with intersection of two shape, the problem in sphere

   CuboidMesh cuboidMesh = new CuboidMesh(200f,200f,100f);
    cuboidMesh.setTranslateX(200);
    cuboidMesh.setTranslateY(200);

    SegmentedSphereMesh sphere = new SegmentedSphereMesh(100f);
    sphere.setTranslateX(100);
    sphere.setTranslateY(100);

    CSG csgBox = MeshUtils.mesh2CSG(cuboidMesh.getMesh());
    CSG csgSphere = MeshUtils.mesh2CSG(sphere.getMesh());

    CSG intersection = csgBox.intersect(csgSphere);
    CSGMesh meshResult = new CSGMesh(intersection);

Debug shows problem during building node:

Node a = new Node(this.clone().polygons);

Error stack:

caused by: java.lang.StackOverflowError at java.base/java.util.HashMap.putVal(HashMap.java:624) at java.base/java.util.HashMap.put(HashMap.java:607) at java.base/java.util.HashSet.add(HashSet.java:220) at java.base/java.util.stream.DistinctOps$1$2.accept(DistinctOps.java:174) at java.base/java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:177) at java.base/java.util.ArrayList$ArrayListSpliterator.forEachRemaining(ArrayList.java:1654) at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:484) at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:474) at java.base/java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:913) at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234) at java.base/java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:578) at eu.mihosoft.jcsg.Node.build(Node.java:244) at eu.mihosoft.jcsg.Node.build(Node.java:265) at eu.mihosoft.jcsg.Node.build(Node.java:265) at eu.mihosoft.jcsg.Node.build(Node.java:265)

[madhephaestus]

I have a solution for this, and it is in the Plane.splitPolygon()

I discovered after a few days elbow deep in the debugger that some planes coming into the CSG system may not be as flat as the epsilon value requires. When that happens, the self plane is never added to the co-plainer node.

To fix this, we read through the points on the incoming polygon and measure the epsilon of the incoming plane. Then when the next loop checks for the front/back/coplainer of the incoming polygon against the self plane, then it passes the test appropriately.

        // search for the epsilon values of the incoming plane
        double negEpsilon = -Plane.EPSILON;
        double posEpsilon = Plane.EPSILON;
        for (int i = 0; i < polygon.vertices.size(); i++) {
            double t = polygon.plane.normal.dot(polygon.vertices.get(i).pos) - polygon.plane.dist; 
            if(t>posEpsilon) {
                //System.err.println("Non flat polygon, increasing positive epsilon "+t);
                posEpsilon=t+Plane.EPSILON;
            }
            if(t<negEpsilon) {
                //System.err.println("Non flat polygon, decreasing negative epsilon "+t);
                negEpsilon=t-Plane.EPSILON;
            }
        }
        int polygonType = 0;
        List<Integer> types = new ArrayList<>();
        boolean somePointsInfront = false;
        boolean somePointsInBack = false;
        for (int i = 0; i < polygon.vertices.size(); i++) {
            double t = this.normal.dot(polygon.vertices.get(i).pos) - this.dist; 
            int type = (t < negEpsilon) ? BACK : (t > posEpsilon) ? FRONT : COPLANAR;
            //polygonType |= type;
            if(type==BACK)
                somePointsInBack=true;
            if(type==FRONT)
                somePointsInfront = true;
            types.add(type);
        }
        if(somePointsInBack && somePointsInfront)
            polygonType=SPANNING;
        else if(somePointsInBack) {
            polygonType=BACK;
        }else if(somePointsInfront)
            polygonType=FRONT;

---

EDIT I submitted a PR to this effect: https://github.com/miho/JCSG/pull/64