Reindexing vertices

Hi all,

I’m trying to calculate the centroid of a mesh’s faces, add that point to the list of vertices, and then further subdivide the mesh (sort of like this). I’ve gotten as far as finding the face centroids, but I’m not sure I understand how to reindex them as vertices back into the proper order in my vertex array. Calling addVertex just tacks them on to the end, and then the edges don’t connect in the proper order.

The addVertex documentation vaguely alludes to this, and ofMesh page tries to explain, but it doesn’t really go through adding indices to an already existing mesh.

I thought setupIndicesAuto would do the trick, but it doesn’t seem to be doing the trick in this particular instance.

Here’s what I’ve got. I’m just setting up a cube, finding the centroids, and adding them back to the mesh. So how do I “reindex” the vertices so that the centroids connect properly with all of their face corners?

.h

    ofVboMesh vboMesh;
    int w,h;

    vector <ofMeshFace> faces;
    ofVec3f calculateCentroid(ofMeshFace *face);

.cpp

void testApp::setup(){
    w = 1280;
    h = 720;
    ofSetWindowShape(w,h);
    ofSetFrameRate(30);
    ofSetVerticalSync(true);
    ofBackground(0, 0, 0);
    ofEnableDepthTest();
    
    vboMesh = ofMesh::box(400, 400, 400);
    faces = vboMesh.getUniqueFaces();

    vboMesh.setupIndicesAuto();

}

void testApp::draw(){
    ofTranslate(w/2,h/2, -10);
    ofRotate(ofGetMouseY(), 1, 0, 0);
    ofRotate(ofGetMouseX(), 0, 1, 0);
    
    for(unsigned int i = 0; i< faces.size(); i++){
        ofMeshFace face = faces[i];
        ofVec3f center = calculateCentroid(&face);
        vboMesh.addVertex(center);
    }
    
    ofSetColor(255);
    vboMesh.drawWireframe();
    ofSetColor(255,0,0);
    glPointSize(4);
    vboMesh.drawVertices();
}

ofVec3f testApp::calculateCentroid(ofMeshFace *face){
	int lastPointIndex = 3;
    
	ofVec3f result;
    
	// loop trough vertices
    for (int i = 0; i < lastPointIndex; i++){
        result += face->getVertex(i);
	}
    
	result /= lastPointIndex;
    
    return result;
}

Thanks in advance for the help!

So, I’ve been working on this for the past few days and I think that I’m getting close. The mesh is mostly subdivided, except for what I can only assume is the very last vertex, which does not close. I’ve also got some vertices linking up where they should not be, and I’m certain that these two issues are related to how I’m assigning the indices.

In the image (I know it’s a bit hard to make out) below you can see the two vertices I highlighted green are not connected.

I could really use some guidance here. It seems like there should already be a library or function for something like subdividing a mesh. If anyone knows of anything I’d be very grateful to hear about it.

void testApp::setup(){
    w = 1280;
    h = 720;
    ofSetWindowShape(w,h);
    ofSetFrameRate(30);
    ofSetVerticalSync(true);
    ofBackground(0, 0, 0);
    ofEnableDepthTest();
    //setupLighting();
    
    vboMesh = ofMesh::box(150, 150, 150);

    subdivide(faces, vboMesh);
    
    
}

//--------------------------------------------------------------
void testApp::subdivide(vector<ofMeshFace> faces, ofVboMesh mesh){
	
    int lastPointIndex = 3;
    int numInd = mesh.getNumIndices();
    faces = mesh.getUniqueFaces();
    
    for(int f = 0; f<faces.size(); f++){
        
        ofMeshFace face = faces[f];
        
        ofVec3f cent;
        ofVec3f vert1;
        ofVec3f vert2;
        ofVec3f vert3;
    
        for (int i = 0; i < lastPointIndex; i++){
            cent += face.getVertex(i);
        }
        
        cent /= lastPointIndex;
        
        for(int v = 1; v<4; v++){
            vert1 = face.getVertex(0);
            vert2 = face.getVertex(1);
            vert3 = face.getVertex(2);
        
            vboMesh.addVertex(cent);
            vboMesh.addIndex((numInd+v)*f+1);
            vboMesh.addVertex(vert1);
            vboMesh.addIndex((numInd+v)*f+2);
            vboMesh.addVertex(vert2);
            vboMesh.addIndex((numInd+v)*f+3);
        
            vboMesh.addVertex(cent);
            vboMesh.addIndex((numInd+v)*f+4);
            vboMesh.addVertex(vert1);
            vboMesh.addIndex((numInd+v)*f+5);
            vboMesh.addVertex(vert3);
            vboMesh.addIndex((numInd+v)*f+6);
        
            vboMesh.addVertex(cent);
            vboMesh.addIndex((numInd+v)*f+7);
            vboMesh.addVertex(vert2);
            vboMesh.addIndex((numInd+v)*f+8);
            vboMesh.addVertex(vert3);
            vboMesh.addIndex((numInd+v)*f+9);
        }
    }
}
//--------------------------------------------------------------
void testApp::draw(){
   
    ofSetColor(255);
    ofDrawBitmapString(ofToString(vboMesh.getNumVertices()), 10, 10);
    ofPushMatrix();
    ofTranslate(w/2,h/2, 0);
    
    ofRotate(ofGetMouseY(), 1, 0, 0);
    ofRotate(ofGetMouseX(), 0, 1, 0);
    
    ofSetColor(255);
    vboMesh.drawWireframe();
    ofSetColor(255,0,0);
    glPointSize(4);
    vboMesh.drawVertices();
    
    ofPopMatrix();
    
}

Hey I cant really help with your question but I have found the opengl forums good for questions like this http://www.opengl.org/discussion_boards/

Thanks pants, I’ll try poking around over there.

I suppose I didn’t need to be adding all those indexes in there, and instead got away adding setupIndicesAuto() after each subdivision.

I’m still getting some odd edges though, one that runs perpendicular across only one face, and one that runs diagonally across the inside of the cube. My guess is that these are from either the first or the last of the indices looping around back to the beginning?

void testApp::subdivide(vector<ofMeshFace> faces, ofVboMesh mesh, float extrude){
	
    int lastPointIndex = 3;
    int numInd = mesh.getNumIndices();
    faces = mesh.getUniqueFaces();
    for(int f = 0; f<faces.size(); f++){
        
        ofMeshFace face = faces[f];
        
        ofVec3f cent;
        ofVec3f vert1;
        ofVec3f vert2;
        ofVec3f vert3;
    
        for (int i = 0; i < lastPointIndex; i++){
            cent += face.getVertex(i);
        }
        
        cent /= lastPointIndex;
        //cent += cent/extrude;
        for(int v = 0; v<3; v++){
            
            vert1 = face.getVertex(0);
            vert2 = face.getVertex(1);
            vert3 = face.getVertex(2);
                            
            vboMesh.addVertex(vert1);
            vboMesh.addVertex(vert2);
            vboMesh.addVertex(cent);
        
            vboMesh.addVertex(vert1);
            vboMesh.addVertex(vert3);
            vboMesh.addVertex(cent);
        
            vboMesh.addVertex(vert2);
            vboMesh.addVertex(vert3);
            vboMesh.addVertex(cent);
        
        }
    }
}

The other problem now, is trying to get rid of duplicate vertices. A cube starts with 24 verts, subdivided once you get 348 . Subdivide again 3480, once more 34800, once more 348000. This is about the max I seem to be able to handle, once I go beyond 4 subdivisions I’m in the millions and it immediately crashes on the getUniqueFaces:

0x2b7d10:  movsd  (%ecx,%eax,8), %xmm0

So either I’m adding in way to many unnecessary vertices, or there must be a way to search the list and remove the duplicates. I tried doing this do remove the non-unique vertices, but it doesn’t seem to do anything. I also read that the unique() function cannot alter the size of a vector, so maybe that is why I’m not seeing any change?

vector<ofVec3f> v = vboMesh.getVertices();
v.erase(unique(v.begin(), v.end() ), v.end());
vboMesh.clear();
vboMesh.addVertices(v);

Have you checked out either the generative mesh tutorial or the openGL tutorial? They both have an explanation of indices. Indices are a way to reduce the amount of information passed to the graphics card. When you use indices, you don’t need to have duplicates vertices in your mesh because the indices are used to determine the faces. (Whereas if you weren’t using indices, the order of the vertices in your vertex array would be used to determine the faces.) Every time you subdivide a face in your code, you are adding 8 duplicate vertices. The only unique vertex that needs to be added is cent. Then you would add the appropriate indices to your mesh in order to form your three sub-faces.

This type of subdivision you are doing is something that is often done on the graphics card in the form of geometry or tessellation shaders (to take advantage of the GPU’s parallelism). It might be a fruitful route for you to explore, but it depends on what exactly you are trying to achieve.

(By the way, if you just need a higher triangle count box, the box method has resolution parameters. But I imagine you are looking for a general purpose algorithm to subdivide an arbitrary mesh, so those parameters won’t help you.)

Thanks for the advice Mike, I’ve checked out both of those tutorials before, but it was definitely helpful going over them again. Yes, indeed I’m looking for an algorithm to subdivide the mesh.

The problem I’m having is not knowing where to stick the new indices back into the original mesh. This works for about two of the cube’s sides, but everything else is really wacky.

 int numInd = mesh.getNumIndices();
 int lastInd = vboMesh.getIndex(numInd-1);

for(int f = 0; f<numInd; f++){

    vboMesh.addIndex(f);
    vboMesh.addIndex(f+1);
    vboMesh.addIndex(lastInd+2+f); // this is for the face center
    
    vboMesh.addIndex(lastInd+2+f);
    vboMesh.addIndex(f);
    vboMesh.addIndex(f+2);
    
    vboMesh.addIndex(f+2);
    vboMesh.addIndex(lastInd+2+f);
    vboMesh.addIndex(f+1);
    
    
}

Do the indices always connect to the next declared index? I’m a bit confused at how to properly wind the indices around the faces, instead of having them traverse through the inside of the cube.

Yup - youv’e got it. The indices are just an array. The polygon mode will determine how that set of indices is processed. Since we are working with triangle mode here, every three consecutive indices in that array will form a face.

I’m having trouble piecing together what your current code is from the snippet that you posted. Definitely this line: vboMesh.addIndex(lastInd+2+f) will trip you up. The index you are looking for is not relative to the last index in the mesh’s array of indices. The index refers to the position of the vertex in the mesh’s vertex array. The index you are looking for is mesh.getNumVertices() - 1. This is likely what is causing your faces to be inside the cube. Does that make sense?

That might not be the only thing tripping you up, so below is some code that will subdivide as you are expecting. Instead of generating the cube using ofMesh::box(), I wrote out the vertices and indices. This is just for clarity to show what ofMesh::box() should be doing behind the scenes. I ran out of time before adding comments, so if something doesn’t make sense, give a shout. Hope this helps!

(Also, if you are interested in doing this subdivision in a shader, you might poke around sites like this one.)

ofMesh cubeMesh;

void testApp::setup(){
    ofSetFrameRate(30);
    ofEnableDepthTest();

    float s = 400;
    cubeMesh.setMode(OF_PRIMITIVE_TRIANGLES);
    cubeMesh.addVertex(ofVec3f(1.0 * s/2.0, 1.0 * s/2.0, -1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(-1.0 * s/2.0, 1.0 * s/2.0, -1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(-1.0 * s/2.0, 1.0 * s/2.0, 1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(1.0 * s/2.0, 1.0 * s/2.0, 1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(1.0 * s/2.0, -1.0 * s/2.0, -1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(-1.0 * s/2.0, -1.0 * s/2.0, -1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(-1.0 * s/2.0, -1.0 * s/2.0, 1.0 * s/2.0));
    cubeMesh.addVertex(ofVec3f(1.0 * s/2.0, -1.0 * s/2.0, 1.0 * s/2.0));

    cubeMesh.addColor(ofFloatColor(1.0, 0.0, 0.0));
    cubeMesh.addColor(ofFloatColor(0.0, 1.0, 0.0));
    cubeMesh.addColor(ofFloatColor(0.0, 0.0, 1.0));
    cubeMesh.addColor(ofFloatColor(1.0, 1.0, 0.0));
    cubeMesh.addColor(ofFloatColor(1.0, 0.0, 1.0));
    cubeMesh.addColor(ofFloatColor(0.0, 1.0, 1.0));
    cubeMesh.addColor(ofFloatColor(1.0, 1.0, 1.0));
    cubeMesh.addColor(ofFloatColor(0.5, 0.5, 0.5));

    cubeMesh.addIndices(new ofIndexType[3] {0, 1, 2}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {0, 2, 3}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {0, 4, 5}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {0, 5, 1}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {1, 5, 6}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {1, 6, 2}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {2, 6, 7}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {2, 7, 3}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {3, 7, 4}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {3, 4, 0}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {4, 7, 6}, 3);
    cubeMesh.addIndices(new ofIndexType[3] {4, 6, 5}, 3);

    subdivide(cubeMesh);
}

//--------------------------------------------------------------
void testApp::subdivide(ofMesh &mesh){
    int numIndices = mesh.getNumIndices();
    for(int i=0; i<numIndices; i+=3){

        int v1Index = mesh.getIndex(i);
        int v2Index = mesh.getIndex(i+1);
        int v3Index = mesh.getIndex(i+2);
        ofVec3f v1 = mesh.getVertex(v1Index);
        ofVec3f v2 = mesh.getVertex(v2Index);
        ofVec3f v3 = mesh.getVertex(v3Index);
        ofVec3f cent = (v1 + v2 + v3) / 3.0;

        mesh.addVertex(cent);
        int centIndex = mesh.getNumVertices()-1;

        mesh.addColor(ofFloatColor(0.75, 0.75, 0.75));

        mesh.addIndex(centIndex);
        mesh.addIndex(v1Index);
        mesh.addIndex(v2Index);

        mesh.addIndex(centIndex);
        mesh.addIndex(v1Index);
        mesh.addIndex(v3Index);

        mesh.addIndex(centIndex);
        mesh.addIndex(v2Index);
        mesh.addIndex(v3Index);

        mesh.getUniqueFaces();
    }
}

//--------------------------------------------------------------
void testApp::draw(){
    ofBackground(0);

    ofSetColor(255);
    ofDrawBitmapString(ofToString(cubeMesh.getNumVertices()), 10, 10);

    ofPushMatrix();
        ofTranslate(ofGetWidth()/2,ofGetHeight()/2, 0);
        ofRotate(ofGetMouseY(), 1, 0, 0);
        ofRotate(ofGetMouseX(), 0, 1, 0);

        ofSetColor(255);
        cubeMesh.drawWireframe();
        ofSetColor(255,0,0);
        glPointSize(10);
        cubeMesh.drawVertices();
    ofPopMatrix();
}