Infinite loop in BSP intersect

[curvedinf]

Love this project dude, thank you! I'm making a level editor using it, and it works great for the first few unions but then goes into an infinite loop in the BSP's intersect function. It seems to be traversing branches infinitely. Any chance you could help me out?

In my project, I am combining random AABBs to generate the infinite loop. Here is my code:

#include "qdcsg.hpp"
#include "math.h"

/*
qdcsg::mesh A;
qdcsg::mesh B;

std::shared_ptr<qdcsg::mesh> AdiffB = qdcsg::difference(A, B);
*/

void createCSGBox(qdcsg::mesh& m, float sx, float sy, float sz, float ex, float ey, float ez) {
    float t;
    if(sx>ex) {
        t = sx;
        sx = ex;
        ex = t;
    }
    if(sy>ey) {
        t = sy;
        sy = ey;
        ey = t;
    }
    if(sz>ez) {
        t = sz;
        sz = ez;
        ez = t;
    }
    float vertices[] = { // 8*3
        sx, sy, sz,
        sx, sy, ez,
        sx, ey, sz,
        sx, ey, ez,
        ex, sy, sz,
        ex, sy, ez,
        ex, ey, sz,
        ex, ey, ez
    };
    for(int i=0; i<8; i++) {
        m.vertices_.push_back(
            qdcsg::vertex(vertices[i*3],vertices[i*3+1],vertices[i*3+2])
        );
    }
    unsigned int triangles[] = { // 12*3
        0, 6, 4,
        0, 2, 6,
        0, 3, 2,
        0, 1, 3,
        2, 7, 6,
        2, 3, 7,
        4, 6, 7,
        4, 7, 5,
        0, 4, 5,
        0, 5, 1,
        1, 5, 7,
        1, 7, 3
    };
    for(int i=0; i<12; i++) {
        m.triangles_.push_back(
            qdcsg::triangle(triangles[i*3],triangles[i*3+1],triangles[i*3+2],i)
        );
    }
}

unsigned int map_list = 0;
unsigned int map_texture = 0;

void setMapTexture(unsigned int tex) {
    map_texture = tex;
}

void createMap() {
    qdcsg::mesh box1, box2;
    qdcsg::mesh* random = new qdcsg::mesh[20];
    qdcsg::mesh* random2 = new qdcsg::mesh[20];
    createCSGBox(box1, -70, -70, -70, 70, 70, 70);
    createCSGBox(box2, -400, -15, -15, 400, 15, 15);
    auto map = qdcsg::Union(box1, box2);
    for(int i=0; i<5; i++) {
        int sx = (rand() % 150)+5;
        int sy = (rand() % 150)+5;
        int sz = (rand() % 150)+5;
        int cx = (rand() % 150) - 75;
        int cy = (rand() % 150) - 75;
        int cz = (rand() % 150) - 75;
        createCSGBox(random[i], cx-sx/2, cy-sy/2, cz-sz/2, cx+sx/2, cy+sy/2, cz+sz/2);
        map = qdcsg::Union(random[i], *map);
    }
    for(int i=0; i<5; i++) {
        int sx = (rand() % 50)+5;
        int sy = (rand() % 50)+5;
        int sz = (rand() % 50)+5;
        int cx = (rand() % 150) - 75;
        int cy = (rand() % 150) - 75;
        int cz = (rand() % 150) - 75;
        createCSGBox(random2[i], cx-sx/2, cy-sy/2, cz-sz/2, cx+sx/2, cy+sy/2, cz+sz/2);
        map = qdcsg::Difference(*map, random2[i]);
    }

    map_list = glGenLists(1);
    glNewList(map_list, GL_COMPILE);
    glEnable(GL_TEXTURE_2D);
    //glBindTexture(GL_TEXTURE_2D, map_texture);
    glBegin(GL_TRIANGLES);
    for(int i=0; i< map->triangles_.size(); i++) {
        auto t = map->triangles_[i];

        Vector3 p1, p2, p3, flat_normal, v1, v2, v3;
        p1.x = map->vertices_[t.a_].x_;
        p1.y = map->vertices_[t.a_].y_;
        p1.z = map->vertices_[t.a_].z_;
        v1.copy(&p1);

        p2.x = map->vertices_[t.b_].x_;
        p2.y = map->vertices_[t.b_].y_;
        p2.z = map->vertices_[t.b_].z_;
        v2.copy(&p2);

        p3.x = map->vertices_[t.c_].x_;
        p3.y = map->vertices_[t.c_].y_;
        p3.z = map->vertices_[t.c_].z_;
        v3.copy(&p3);

        flat_normal.copy(&p3)->sub(&p1)->cross(p2.sub(&p1))->normalize();       

        bool x_aligned = v1.x == v2.x && v1.x == v3.x;
        bool y_aligned = v1.y == v2.y && v1.y == v3.y;
        bool z_aligned = v1.z == v2.z && v1.z == v3.z;

        double tscale = 0.01;

        glNormal3d(flat_normal.x,flat_normal.y,flat_normal.z);
        if(x_aligned)
            glTexCoord2f(v1.y*tscale,v1.z*tscale);
        if(y_aligned)
            glTexCoord2f(v1.x*tscale,v1.z*tscale);
        if(z_aligned)
            glTexCoord2f(v1.x*tscale,v1.y*tscale);
        glVertex3d(v1.x,v1.y,v1.z);

        glNormal3d(flat_normal.x,flat_normal.y,flat_normal.z);
        if(x_aligned)
            glTexCoord2f(v2.y*tscale,v2.z*tscale);
        if(y_aligned)
            glTexCoord2f(v2.x*tscale,v2.z*tscale);
        if(z_aligned)
            glTexCoord2f(v2.x*tscale,v2.y*tscale);
        glVertex3d(v2.x,v2.y,v2.z);

        glNormal3d(flat_normal.x,flat_normal.y,flat_normal.z);
        if(x_aligned)
            glTexCoord2f(v3.y*tscale,v3.z*tscale);
        if(y_aligned)
            glTexCoord2f(v3.x*tscale,v3.z*tscale);
        if(z_aligned)
            glTexCoord2f(v3.x*tscale,v3.y*tscale);
        glVertex3d(v3.x,v3.y,v3.z);

    }
    glEnd();
    glDisable(GL_TEXTURE_2D);
    glEndList();
}

void renderMap() {
    glCallList(map_list);
}

The loop happens on either map = qdcsg::Union(random[i], *map); or map = qdcsg::Difference(random[i], *map);

For the purposes of your testing, all of the GL code is irrelevant and can be removed.

Also, I noticed that if I reuse the memory for the primitive AABBs after combining them, it causes issues with the resulting mesh (thus I am allocating memory for each primitive in the example above). Is this expected? Would it be possible to allocate the resulting mesh's verts separately in some way?

If you have any time to help it would be appreciated! Thank you again!

edit: BTW I'm using g++ to compile the project.

[spiroyster]

Hello, yes happy to have a look at this over the next few days :). I suspect I know what the problem is and if so, then it might be a limitation of this algorithm for CSG. However I am currently working on open sourcing another (different algorithm) which is far more robust, threaded and should not be limited in the way this one is. Watch this space.

[loic-jourdan]

Hi, I've also experienced such issue, I've found that there's a copy-paste error line 496: else if (splitResult->outsideTriangles_.size() == 1 && splitResult->outsideTriangles_.empty()) should be else if (splitResult->outsideTriangles_.size() == 1 && splitResult->insideTriangles_.empty()) This library is awesome, very clean, congrats and thanks a lot!

[spiroyster]

Very good spot! That is indeed a typo, and prob copy-paste ;).

Thanks I will update. Glad you like it and I hope the comments helped.

[loic-jourdan]

Very good spot! That is indeed a typo, and prob copy-paste ;).

Thanks I will update. Glad you like it and I hope the comments helped.

I've experienced another case where the code is entering an infinite loop, I'm barely able to reproduce it (it seems to happen with complex meshes) but once I'm able to debug it correctly you'll get some news from me : )

[spiroyster]

Thanks, however I fear there may be numerous occasions when this results in infinite loops. In my experience it was mainly around the BSP tree population when spliting triangles. I was yet to isolate a condition to break out of the while loop which was valid in different cases. Many times it was the result of fp precision, however when I adjusted, results were mixed for other data.

When implementing this (from the white paper) it assumed that manifolds to perform the CSG on where always cleanly intersecting and not touching with some triangles being coplanar to others in the other input mesh (nothing was mentioned about the case of coplanar triangles, and these were assumed 'inside' in the BSP algorithm). It was this flaw in the algorithm (along with some other shortcomings) that made me write the other https://github.com/spiroyster/csg lib.

I was thinking about deprecating this since I feel it is almost at it's limits.

[loic-jourdan]

Ok, I'll keep your warning in mind, it's indeed tough when it hits fp precision issues. Seeing what you already did, I don't think I'll be able to help that much but I won't give up too early and I'll do some other pass on debugging : ) If I find some interesting fixes, I'll update you. I must dive into your new csg lib but for now, I find qdcsg worth keeping alive, it has wonderful features: it's fast as hell, it keeps track about originating triangles, this make me able to modify my meshes instead of rebuilding them from scratch. Note: I would be interested by the whitepaper this lib is based on, is it available? Thanks again for your awesome work!