java - bsp在java中崩溃

Question

我用java写了一个bsp函数，它似乎总是在同一行代码中崩溃，经过大约数千次迭代，它实际上是函数的第一行：

if (!tri.isEmpty()) {
             Triangle3D t= tri.get(0);

例外是：

Exception in thread "Thread-3" java.lang.StackOverflowError
        at java.util.ArrayList.get(ArrayList.java:322)
        at pythagorastree3d.Scene.BSP(Scene.java:100)

我真的很确定我正确地编写了函数。有人能帮我吗？

ArrayList<Triangle3D> tri = new ArrayList<Triangle3D>();
    if (cubeOrSphere) {
        for (int i = 0; i < p.getBinTree().toArrayList().size(); i++) {
            tri.addAll(p.getBinTree().toArrayList().get(i).getTriangles());
        }
    } else {
        for (int i = 0; i < ps.getBinTree().toArrayList().size(); i++) {
            tri.addAll(ps.getBinTree().toArrayList().get(i).getTriangles());
        }
    }
    for (int i = 0; i < ks.length; i++) {
        tri.addAll(ks[i].getList());
    }
    //left-front, right-behind
    BinTreeNode<ArrayList<Triangle3D>> bsp = new BinTreeNode<ArrayList<Triangle3D>>(new ArrayList<Triangle3D>());
    BSP(bsp, tri);


 private void BSP(BinTreeNode<ArrayList<Triangle3D>> bsp, ArrayList<Triangle3D> tri) {
    if (!tri.isEmpty()) {
         Triangle3D t= tri.get(0);
        ArrayList<Triangle3D> front, back, on;
        on = new ArrayList<Triangle3D>();
        on.add(t);
        front = new ArrayList<Triangle3D>();//i.e. left
        back = new ArrayList<Triangle3D>();//i.e. right
        Vector3D v;
        Triangle3D triangle;
        Vector3D intersection1, intersection2;

        for (int i = 1; i < tri.size(); i++) {
            v = new Vector3D(tri.get(i).getP1().getX() - t.getP1().getX(), tri.get(i).getP1().getY() - t.getP1().getY(), tri.get(i).getP1().getZ() - t.getP1().getZ());
            if (t.getNormal().dotProduct(v) > 0) {//p1 in front of plane
                v = new Vector3D(tri.get(i).getP2().getX() - t.getP1().getX(), tri.get(i).getP2().getY() - t.getP1().getY(), tri.get(i).getP2().getZ() - t.getP1().getZ());
                if (t.getNormal().dotProduct(v) > 0) {//p1 & p2 in front of plane 
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) >= 0) {//p1 & p2 & p3 in front of plane or on plane
                        front.add(tri.get(i));
                    } else {//p1 & p2 in front of plane p3 behind plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP3());
                        intersection2 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP3());

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, intersection2, tri.get(i).getP1(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, tri.get(i).getP3(), intersection2, tri.get(i).col);
                        back.add(triangle);
                    }
                } else if (t.getNormal().dotProduct(v) < 0) {// p1 in front of plane p2 behind plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {//p1 & p3 in front of plane p2 behind plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP2());
                        intersection2 = intersectionPlane(t, tri.get(i).getP3(), tri.get(i).getP2());

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, intersection2, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection2, tri.get(i).getP3(), tri.get(i).getP1(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), intersection2, tri.get(i).col);
                        back.add(triangle);
                    } else if (t.getNormal().dotProduct(v) < 0) {//p1 in front of plane p2 & p3 behind plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP1());
                        intersection2 = intersectionPlane(t, tri.get(i).getP3(), tri.get(i).getP1());

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, intersection2, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), tri.get(i).getP3(), tri.get(i).col);
                        back.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP3(), intersection2, intersection1, tri.get(i).col);
                        back.add(triangle);
                    } else {// p1 in front of plane p2 behind plane p3 on plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP1());

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, tri.get(i).getP3(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), tri.get(i).getP3(), tri.get(i).col);
                        back.add(triangle);
                    }
                } else {//p1 in front of plane p2 is on plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) >= 0) {//p1 in front of plane p2 is on plane p3 in front or on plane
                        front.add(tri.get(i));
                    } else {//p1 in front of plane p2 is on plane p3 behind plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP3());

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP2(), tri.get(i).getP3(), intersection1, tri.get(i).col);
                        back.add(triangle);
                    }
                }
            } else if (t.getNormal().dotProduct(v) < 0) {// p1 behind plane
                v = new Vector3D(tri.get(i).getP2().getX() - t.getP1().getX(), tri.get(i).getP2().getY() - t.getP1().getY(), tri.get(i).getP2().getZ() - t.getP1().getZ());
                if (t.getNormal().dotProduct(v) > 0) {// p1 behind plane p2 in front of plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {// p1 behind plane p2 & p3 in front of plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP1());
                        intersection2 = intersectionPlane(t, tri.get(i).getP3(), tri.get(i).getP1());

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), tri.get(i).getP3(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP3(), intersection2, intersection1, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, intersection2, tri.get(i).col);
                        back.add(triangle);
                    } else if (t.getNormal().dotProduct(v) < 0) {//p1 & p3 behind plane p2 in front of plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP2());
                        intersection2 = intersectionPlane(t, tri.get(i).getP3(), tri.get(i).getP2());

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), intersection2, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, intersection2, tri.get(i).col);
                        back.add(triangle);

                        triangle = new Triangle3D(intersection2, tri.get(i).getP3(), tri.get(i).getP1(), tri.get(i).col);
                        back.add(triangle);
                    } else {//p1 behind plane p2 in front of plane p3 on plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP1());

                        triangle = new Triangle3D(intersection1, tri.get(i).getP2(), tri.get(i).getP3(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, tri.get(i).getP3(), tri.get(i).col);
                        back.add(triangle);
                    }
                } else if (t.getNormal().dotProduct(v) < 0) {//p1 & p2 behind plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {//p1 & p2 behind plane p3 in front of plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP3());
                        intersection2 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP3());

                        triangle = new Triangle3D(intersection1, tri.get(i).getP3(), intersection2, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        back.add(triangle);

                        triangle = new Triangle3D(intersection1, intersection2, tri.get(i).getP1(), tri.get(i).col);
                        back.add(triangle);
                    } else if (t.getNormal().dotProduct(v) <= 0) {//p1 & p2 behind plane p3 behind or on plane
                        back.add(tri.get(i));
                    }
                } else {//p1 behind plane p2 on plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {//p1 behind plane p2 on plane p3 in front of plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP1(), tri.get(i).getP3());

                        triangle = new Triangle3D(tri.get(i).getP2(), tri.get(i).getP3(), intersection1, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        back.add(triangle);
                    } else {//p1 behind plane p2 on plane p3 behind or on plane
                        back.add(tri.get(i));
                    }
                }
            } else {//p1 on plane
                v = new Vector3D(tri.get(i).getP2().getX() - t.getP1().getX(), tri.get(i).getP2().getY() - t.getP1().getY(), tri.get(i).getP2().getZ() - t.getP1().getZ());
                if (t.getNormal().dotProduct(v) > 0) {//p1 on plane p2 in front of plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) >= 0) {//p1 on plane p2 in front of plane p3 in front or on plane
                        front.add(tri.get(i));
                    } else {//p1 on plane p2 in front of plane p3 behind plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP3());

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(intersection1, tri.get(i).getP3(), tri.get(i).getP1(), tri.get(i).col);
                        back.add(triangle);
                    }
                } else if (t.getNormal().dotProduct(v) < 0) {//p1 on plane p2 behind plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {//p1 on plane p2 behind plane p3 in front of plane
                        intersection1 = intersectionPlane(t, tri.get(i).getP2(), tri.get(i).getP3());

                        triangle = new Triangle3D(tri.get(i).getP1(), intersection1, tri.get(i).getP3(), tri.get(i).col);
                        front.add(triangle);

                        triangle = new Triangle3D(tri.get(i).getP1(), tri.get(i).getP2(), intersection1, tri.get(i).col);
                        back.add(triangle);
                    } else if (t.getNormal().dotProduct(v) <= 0) {//p1 on plane p2 behind plane p3 behind or on plane
                        back.add(tri.get(i));
                    }
                } else {//p1 & p2 on plane
                    v = new Vector3D(tri.get(i).getP3().getX() - t.getP1().getX(), tri.get(i).getP3().getY() - t.getP1().getY(), tri.get(i).getP3().getZ() - t.getP1().getZ());
                    if (t.getNormal().dotProduct(v) > 0) {//p1 & p2 on plane p3 in front of plane
                        front.add(tri.get(i));
                    } else if (t.getNormal().dotProduct(v) < 0) {//p1 & p2 on plane p3 behind plane
                        back.add(tri.get(i));
                    } else {//p1 & p2 & p3 on plane
                        on.add(tri.get(i));
                    }
                }
            }
        }
        bsp.getInfo().addAll(on);
        if (!front.isEmpty()) {
            bsp.setLeft(new BinTreeNode<ArrayList<Triangle3D>>(new ArrayList<Triangle3D>()));
            BSP(bsp.getLeft(), front);
        }
        if (!back.isEmpty()) {
            bsp.setRight(new BinTreeNode<ArrayList<Triangle3D>>(new ArrayList<Triangle3D>()));
            BSP(bsp.getRight(), back);
        }
    }
}

Answer 1

我没有费心去检查算法的实现是否正确，但这里是你的代码的清理版本，它使用 while 循环而不是递归调用：

private void BSP(BinTreeNode<ArrayList<Triangle3D>> bsp,
        ArrayList<Triangle3D> triangles) {
    if (triangles.isEmpty()) {
        return;
    }
    // Add work item
    Stack<BSPWorkItem> bspWorkItems = new Stack<BSPWorkItem>();
    bspWorkItems.add(new BSPWorkItem(bsp, triangles));

    while (!bspWorkItems.isEmpty()) {
        // Get work item
        BSPWorkItem bspWorkItem = bspWorkItems.pop();
        triangles = bspWorkItem.getTriangles();
        bsp = bspWorkItem.getBSP();

        Iterator<Triangle3D> triangleIterator = triangles.iterator();

        Triangle3D pivotTriangle = triangleIterator.next();
        // left
        ArrayList<Triangle3D> front = new ArrayList<Triangle3D>();
        // right
        ArrayList<Triangle3D> back = new ArrayList<Triangle3D>();
        ArrayList<Triangle3D> on = new ArrayList<Triangle3D>();
        on.add(pivotTriangle);

        while (triangleIterator.hasNext()) {
            Triangle3D currentTriangle = triangleIterator.next();
            Vector3D v = new Vector3D(currentTriangle.getP1().getX()
                    - pivotTriangle.getP1().getX(), currentTriangle.getP1()
                    .getY() - pivotTriangle.getP1().getY(), currentTriangle
                    .getP1().getZ() - pivotTriangle.getP1().getZ());
            if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                // p1 in front of plane
                v = new Vector3D(currentTriangle.getP2().getX()
                        - pivotTriangle.getP1().getX(), currentTriangle
                        .getP2().getY() - pivotTriangle.getP1().getY(),
                        currentTriangle.getP2().getZ()
                                - pivotTriangle.getP1().getZ());
                if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                    // p1 & p2 in front of plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) >= 0) {
                        // p1 & p2 & p3 in front of plane or on plane
                        front.add(currentTriangle);
                    } else {
                        // p1 & p2 in front of plane p3 behind plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP3());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D front2Triangle = new Triangle3D(
                                intersection1, intersection2,
                                currentTriangle.getP1(),
                                currentTriangle.col);
                        front.add(front2Triangle);

                        Triangle3D backTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP3(),
                                intersection2, currentTriangle.col);
                        back.add(backTriangle);
                    }
                } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                    // p1 in front of plane p2 behind plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 & p3 in front of plane p2 behind plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP2());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP3(),
                                currentTriangle.getP2());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                intersection2, currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D front2Triangle = new Triangle3D(
                                intersection2, currentTriangle.getP3(),
                                currentTriangle.getP1(),
                                currentTriangle.col);
                        front.add(front2Triangle);

                        Triangle3D backTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                intersection2, currentTriangle.col);
                        back.add(backTriangle);
                    } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                        // p1 in front of plane p2 & p3 behind plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP1());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP3(),
                                currentTriangle.getP1());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                intersection2, currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        back.add(backTriangle);

                        Triangle3D back2Triangle = new Triangle3D(
                                currentTriangle.getP3(), intersection2,
                                intersection1, currentTriangle.col);
                        back.add(back2Triangle);
                    } else {
                        // p1 in front of plane p2 behind plane p3 on plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP1());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        back.add(backTriangle);
                    }
                } else {
                    // p1 in front of plane p2 is on plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) >= 0) {
                        // p1 in front of plane p2 is on plane p3 in front
                        // or on plane
                        front.add(currentTriangle);
                    } else {
                        // p1 in front of plane p2 is on plane p3 behind
                        // plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP2(),
                                currentTriangle.getP3(), intersection1,
                                currentTriangle.col);
                        back.add(backTriangle);
                    }
                }
            } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                // p1 behind plane
                v = new Vector3D(currentTriangle.getP2().getX()
                        - pivotTriangle.getP1().getX(), currentTriangle
                        .getP2().getY() - pivotTriangle.getP1().getY(),
                        currentTriangle.getP2().getZ()
                                - pivotTriangle.getP1().getZ());
                if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                    // p1 behind plane p2 in front of plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 behind plane p2 & p3 in front of plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP1());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP3(),
                                currentTriangle.getP1());

                        Triangle3D frontTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D front2Triangle = new Triangle3D(
                                currentTriangle.getP3(), intersection2,
                                intersection1, currentTriangle.col);
                        front.add(front2Triangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                intersection2, currentTriangle.col);
                        back.add(backTriangle);
                    } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                        // p1 & p3 behind plane p2 in front of plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP2());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP3(),
                                currentTriangle.getP2());

                        Triangle3D frontTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                intersection2, currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                intersection2, currentTriangle.col);
                        back.add(backTriangle);

                        Triangle3D back2Triangle = new Triangle3D(
                                intersection2, currentTriangle.getP3(),
                                currentTriangle.getP1(),
                                currentTriangle.col);
                        back.add(back2Triangle);
                    } else {
                        // p1 behind plane p2 in front of plane p3 on plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP1());

                        Triangle3D frontTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP2(),
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        back.add(backTriangle);
                    }
                } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                    // p1 & p2 behind plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 & p2 behind plane p3 in front of plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP3());
                        Vector3D intersection2 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP3(),
                                intersection2, currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        back.add(backTriangle);

                        Triangle3D back2Triangle = new Triangle3D(
                                intersection1, intersection2,
                                currentTriangle.getP1(),
                                currentTriangle.col);
                        back.add(back2Triangle);
                    } else {
                        // p1 & p2 behind plane p3 behind or on plane
                        back.add(currentTriangle);
                    }
                } else {
                    // p1 behind plane p2 on plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 behind plane p2 on plane p3 in front of plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP1(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP2(),
                                currentTriangle.getP3(), intersection1,
                                currentTriangle.col);
                        front.add(frontTriangle);

                        frontTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        back.add(frontTriangle);
                    } else {
                        // p1 behind plane p2 on plane p3 behind or on plane
                        back.add(currentTriangle);
                    }
                }
            } else {
                // p1 on plane
                v = new Vector3D(currentTriangle.getP2().getX()
                        - pivotTriangle.getP1().getX(), currentTriangle
                        .getP2().getY() - pivotTriangle.getP1().getY(),
                        currentTriangle.getP2().getZ()
                                - pivotTriangle.getP1().getZ());
                if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                    // p1 on plane p2 in front of plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) >= 0) {
                        // p1 on plane p2 in front of plane p3 in front or
                        // on plane
                        front.add(currentTriangle);
                    } else {
                        // p1 on plane p2 in front of plane p3 behind plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                intersection1, currentTriangle.getP3(),
                                currentTriangle.getP1(),
                                currentTriangle.col);
                        back.add(backTriangle);
                    }
                } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                    // p1 on plane p2 behind plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 on plane p2 behind plane p3 in front of plane
                        Vector3D intersection1 = intersectionPlane(
                                pivotTriangle, currentTriangle.getP2(),
                                currentTriangle.getP3());

                        Triangle3D frontTriangle = new Triangle3D(
                                currentTriangle.getP1(), intersection1,
                                currentTriangle.getP3(),
                                currentTriangle.col);
                        front.add(frontTriangle);

                        Triangle3D backTriangle = new Triangle3D(
                                currentTriangle.getP1(),
                                currentTriangle.getP2(), intersection1,
                                currentTriangle.col);
                        back.add(backTriangle);
                    } else {
                        // p1 on plane p2 behind plane p3 behind or on plane
                        back.add(currentTriangle);
                    }
                } else {// p1 & p2 on plane
                    v = new Vector3D(currentTriangle.getP3().getX()
                            - pivotTriangle.getP1().getX(), currentTriangle
                            .getP3().getY() - pivotTriangle.getP1().getY(),
                            currentTriangle.getP3().getZ()
                                    - pivotTriangle.getP1().getZ());
                    if (pivotTriangle.getNormal().dotProduct(v) > 0) {
                        // p1 & p2 on plane p3 in front of plane
                        front.add(currentTriangle);
                    } else if (pivotTriangle.getNormal().dotProduct(v) < 0) {
                        // p1 & p2 on plane p3 behind plane
                        back.add(currentTriangle);
                    } else {
                        // p1 & p2 & p3 on plane
                        on.add(currentTriangle);
                    }
                }
            }
        }

        bsp.getInfo().addAll(on);
        if (!front.isEmpty()) {
            bsp.setLeft(new BinTreeNode<ArrayList<Triangle3D>>(
                    new ArrayList<Triangle3D>()));
            bspWorkItems.push(new BSPWorkItem(bsp.getLeft(), front));
        }
        if (!back.isEmpty()) {
            bsp.setRight(new BinTreeNode<ArrayList<Triangle3D>>(
                    new ArrayList<Triangle3D>()));
            bspWorkItems.push(new BSPWorkItem(bsp.getRight(), back));
        }
    }
}

private static class BSPWorkItem {
    private final BinTreeNode<ArrayList<Triangle3D>> bsp;
    private final ArrayList<Triangle3D> triangles;

    public BSPWorkItem(BinTreeNode<ArrayList<Triangle3D>> bsp,
            ArrayList<Triangle3D> triangles) {
        this.bsp = bsp;
        this.triangles = triangles;
    }

    public BinTreeNode<ArrayList<Triangle3D>> getBSP() {
        return bsp;
    }

    public ArrayList<Triangle3D> getTriangles() {
        return triangles;
    }
}