Sorting Vertices

Hi all,

I’ve done a lot of work sorting pixels of a 2D image and I’d like to try applying a similar concept to a 3d mesh, and I’d like to see the sorting happen live on a per-vertex basis ( as in, an animated sort, opposed to just arriving at a completely sorted mesh).

My first stab was to use a simple bubble sort on the vertex array, but it just seems to glitch the model once, and then stops. See the image below (I’m using the balloon dog model from the vertex noise example).

Draw faces:

Wire frame:

  //simple swap function
    void testApp::smallSwap(float a[], int l, int r){
        int temp = a[l];
        a[l] = a[r];
        a[r] = temp;
    }

ofVboMesh mesh = model.getMesh(0);
//get the vertices
vector<ofVec3f>& verts = mesh.getVertices();

//loop through and swap
for(int i = 0; i<verts.size(); i++){
        if(verts[i].x<verts[i-1].x){
            smallSwap(&verts[i].x, i, i+3);
        }
        if(verts[i].y<verts[i-1].y){
            smallSwap(&verts[i].y, i, i+3);
        }
        if(verts[i].z<verts[i-1].z){
            smallSwap(&verts[i].z, i, i+3);
        }
    }

So why don’t I see more than one swap? I’m also not positive about how this data is stored in the array. Is the returned verts vector just something like [x0,y0,z0,x1,y1,z1,x2,y2,z2…]? Do the vertices maintain some sort of relationship with their nearest neighbors that swapping would break? Does this relationship need to reestablished once they reach a sorted state?

Thanks for your help!

I’m a noob, but you have to define how the vertices relate to create the faces.

with/without indeces (http://www.opengl-tutorial.org/intermediate-tutorials/tutorial-9-vbo-indexing/)

since the indices refer to the index of the vertice in the vertice array, when you change the vertices arround you can expect that the result is going to be messed up, this without reindexing them all(i would do this), or correcting the previous ones.

Roger

Thanks for the help! I actually did figure this out, I think my problem was as simple as not calling my sort function in the draw loop. The results are not so spectacular though. What I’ve ended up with is just a 3d squiggly line, but the act of watching them get sorted turned out to be interesting enough.

I’m curious about “reindexing” the vertices though. How can I read the shortest distance between vertex a and vertex b and make reindex the vertices using that information? As it is now, the vertices start moving around and then drag the wireframe lines far apart from each other. Looks great when only the vertices are displayed but once you draw the wireframe or the faces it gets crazy.

Here’s what I’m doing so far, just reading out the vertices and sending them through a bubble sort.
.h

#pragma once
#include "ofMain.h"
#include "ofxAssimpModelLoader.h"
class testApp : public ofBaseApp{
public:

void setup();
void update();
void draw();
void keyPressed  (int key);
void keyReleased(int key);
void mouseMoved(int x, int y );
void mouseDragged(int x, int y, int button);
void mousePressed(int x, int y, int button);
void mouseReleased(int x, int y, int button);
void windowResized(int w, int h);
void dragEvent(ofDragInfo dragInfo);
void gotMessage(ofMessage msg);

//this is our model we'll draw	
ofxAssimpModelLoader model;

ofMesh mesh;
ofVec3f * vert;
bool drawWire, drawVerts, drawFaces;
};

.cpp

void testApp::setup(){

ofSetFrameRate(60);
ofSetVerticalSync(true);
ofBackground(10,10,10);
ofEnableAlphaBlending();
glEnable(GL_DEPTH_TEST);
model.loadModel("dog/dog.3ds", true);

model.calculateDimensions();
model.setPosition(ofGetWidth()/2, ofGetHeight()/2.5, 0);

mesh = model.getMesh(0);

for(int i = 0; i<mesh.getNumVertices(); i++){
vert = mesh.getVerticesPointer();
}

drawFaces = false;
drawVerts = true;
drawWire = false;
}


void testApp::draw(){    
ofPushMatrix();
ofTranslate(ofGetWidth()/2,ofGetHeight()/2,500);
ofRotate(ofGetMouseX(), 0, 1, 0);
ofRotate(ofGetMouseY(), 1, 0, 0);
ofScale(20,20,20);
ofSetColor(255);

for(int i = 0;i<mesh.getNumVertices(); i++ ){
        
    //do bubble sort on vertices
    if(vert[i].x>vert[i+1].x){
        float t = vert[i].x;
        vert[i].x = vert[i+1].x;
        vert[i+1].x = t;
    }
    
    if(vert[i].y>vert[i+1].y){
        float u = vert[i].y;
        vert[i].y = vert[i+1].y;
        vert[i+1].y = u;
    }
    
    if(vert[i].z>vert[i+1].z){
        float v = vert[i].z;
        vert[i].z = vert[i+1].z;
        vert[i+1].z = v;
    }
     
}

if(drawVerts){
mesh.drawVertices();
}
else if(drawWire){
    mesh.drawWireframe();
}
else if (drawFaces){
    mesh.drawFaces();
}

ofPopMatrix();
}


void testApp::keyPressed(int key){
if (key == '1') {
    drawVerts = true;
    drawWire = false;
    drawFaces = false;
}
if (key == '2') {
    drawVerts = false;
    drawWire = true;
    drawFaces = false;
}
if (key == '3') {
    drawVerts = false;
    drawWire = false;
    drawFaces = true;
}
}

Also calling mesh.setupIndicesAuto after my sort seems to keep the mesh from getting out of hand. The lines seem to go to the closest neighbor, but as the sort goes on, the mesh starts to disappear. Perhaps this is because the faces are so close together they can no longer be seen? It also gives me some pretty crazy flickering.

Hey @aferriss ,

I saw your post and i gave it a try… I didn’t get too far though, I just apply some sorting and reverse it. it is very simple but i thought you might find it interesting. Actually i think swapping normals is a lot more fun than vertices :smile: Notice that I’m not evaluating anything inside the for loop… Please let me know if you find something interesting. It would be nice to keep the ball rolling!

void ofApp::swapVerticesUp(){
	for(int i = 0;i<mesh.getNumVertices(); i++ ){
		//sort vertices
		ofPoint temp = vert[i];
		vert[i]= vert[i+1];
		vert[i+1] = temp;
	}
}
void ofApp::swapVerticesDown(){
	for(int i = mesh.getNumVertices();i>0; i-- ){
		//sort vertices
		ofPoint temp = vert[i];
		vert[i]= vert[i-1];
		vert[i-1] = temp;
	}
}

void ofApp::swapNormalsUp(){
	for(int i = 0;i<mesh.getNumNormals(); i++ ){
		//sort normals
		ofPoint temp = norm[i];
		norm[i]= norm[i+1];
		norm[i+1] = temp;
	}
}

void ofApp::swapNormalsDown(){
	for(int i = mesh.getNumVertices();i>0; i-- ){
		//sort normals
		ofPoint temp = norm[i];
		norm[i]= norm[i-1];
		norm[i-1] = temp;
	}
}

void ofApp::swapIndicesUp(){
	for(int i = 0;i<mesh.getNumIndices()-1; i++ ){
		//sort indices
		ofIndexType ind = index[i];
		index[i] = index[i+1];
		index[i+1] = ind;
	}
}

void ofApp::swapIndicesDown(){
	for(int i = mesh.getNumIndices()-1;i>0; i-- ){
		//sort indices
		ofIndexType ind = index[i];
		index[i] = index[i-1];
		index[i-1] = ind;
	}
}

Awesome! I’m glad you found it fun to play with. If you’re not evaluating, it’s not really sorting right? All you are seeing is a swap (correct me if I’m wrong).

I’m a little confused about how to move normals or indices, I tried something like this in setup

for(int i = 0; i<mesh.getNumNormals(); i++){
    norm = mesh.getNormalsPointer();
}

norm is like this in the .h

ofVec3f * norm;

and then went on with your function, but I don’t see anything moving. Am I missing something? Same deal with the indices.

yeah that’s right it’s not really sorting just moving the first element to the last position of the vector. ah and about the normals I forgot to say it does something if you have lighting in your scene
you can check out my messy code here:
https://github.com/wasawi/my_examples/tree/master/11_sortingMesh

The problem i see with sorting xyz separatelly is that the resulting position can be anywhere… loosing the initial mesh appearance completely. What I try to say is that sorting vertices is way more agressive than sorting pixels where you can still keep some idea of the reference image… but It is a good place to start experimenting :smile: let me know if that code brings you somewhere, I’ll be happy to see crazy algorithms to glitch meshes :smiley: