Segmentation fault when trying to use ofxDelaunay

I’ve been trying to generate a 3D object based on the superformula for some time, and came to the realization I needed something to help wrap meshes around a series of points. I am able to generate a series of 3D points no problem, but I need to create a 3D object out of those points, so I’ve been playing with the ofxDelaunay addon to help with that.

In my code, I add about 100 points to the Delaunay object, then try to run .triangulate() on it. However, every time the program hits that call to triangulate, the program freezes and sometimes throws a segmentation fault.

My code is quite simple, so I’ll post it here:

#include “testApp.h”

//--------------------------------------------------------------
void testApp::setup(){
// Generate the supershape
a = 1;
b = 1;
m1 = 5;
m2 = 3;
n1_1 = 1;
n2_1 = 2;
n3_1 = 1;
n1_2 = 1;
n2_2 = 5;
n3_2 = 3;
xres = 10;
yres = 10;
scaleFactor = 100;

// Delaunay
buildSupershape();
}

//--------------------------------------------------------------
void testApp::update(){
ofBackground(0);
}

//--------------------------------------------------------------
void testApp::draw(){

}

// Actual superformula implementation
float testApp::superformula(float a, float b, float m, float n1, float n2, float n3, float angle) {
float r;
float t1,t2;

t1 = cos(m * angle / 4) / a;
t1 = abs(t1);
t1 = pow(t1, n2);

t2 = sin(m * angle / 4) / b;
t2 = abs(t2);
t2 = pow(t2, n3);

r = pow(t1+t2, 1/n1);

return r;
}

// Calculations a 3D supershape point based on polar coordinates
ofPoint testApp::calculatePoint(float theta, float phi) {

// Run superformula for given values
float r1 = superformula(a, b, m1, n1_1, n2_1, n3_1, theta);
float r2 = superformula(a, b, m2, n1_2, n2_2, n3_2, phi);

// Calculate coordinates
float x = r1 * cos(theta) * r2 * cos(phi);
float y = r1 * sin(theta) * r2 * cos(phi);
float z = r2 * sin(phi);

// Return the resulting vector
return ofPoint(x*scaleFactor, y*scaleFactor, z*scaleFactor);
}

void testApp::buildSupershape() {
// Reset the Delaunay points
delaunay.reset();

// Determine resolution of shape
int thetaStep = 360 / xres;
int phiStep = 180 / yres;

// Generate each point
int index = 1;
for (float i = -180; i < 180; i += thetaStep) {
for (float j = -90; j < 90; j += phiStep) {
ofPoint p = calculatePoint(i, j);
float zz = delaunay.addPoint§;

cout << p.z << “\n”;
index++;
}
}

delaunay.triangulate();
delaunay.draw();

}

As I say, the call to delaunay.triangulate seems to be the issue. I haven’t found any documentation for this addon, but have seen a few people use it, so I was hoping someone could provide some insight :slight_smile: Let me know if I can provide anything else!

Somewhere you’re trying to access a vertex pointer that hasn’t been allocated, which version of the addon are you using (there’s a few floating around) and can you step through the execution more closely to see where it actually throws?

That might be part of the problem - I’m still stuck with the Java mindset when allocating objects and whatnot. I’m not sure how to get the ofPoint object in the right format to feed into the Delaunay object. How do I supply the pointer of the ofPoint object I want to the Delaunay class?

I know the problem is with the .triangulate() method, but I don’t know where inside of the call the error is happening, since no errors come out through the console.

When I comment out my ofPoint lines and supply the .addPoint() method with three calls to ofRandom(100), the program works as intended. In other words, this works:

float zz = delaunay.addPoint(ofRandom(100), ofRandom(100), ofRandom(100));

But when I supply my ofPoint, or even explicitly supply the .x, .y and .z properties of my point object in addPoint, it crashes.

I’ve also noticed that even though the code for Delaunay uses 3D points for much of its data structures and calculations, the draw method only outputs 2D triangles. I’m trying to wrap a mesh around a set of 3D points, am I using the wrong addon?

Yes, you are using the wrong toolset for your problem. Delaunay triangulation works only for 2Dish coordinates.

Looking at your code it should be simple to create a mesh from your points, perhaps ofMesh is suitable. All you need is to construct the triangle-indices referencing the correct vertices.

cheers,
Stephan

I actually started this app in Processing, but ran into the same fundamental problem. It seems that the superformula in 3D actually creates points in a fairly unpredictable way - ‘rows’ show up like rings of points, and ‘columns’ can appear out of order (polar coordinates), such that when I tried applying a simple mesh, there is tons of overlap and strange behavior (inside out faces, messed up normals, etc.). Furthermore, as the various superformula parameters are tweaked, columns move around even more, so meshes would have to be recalculated and reapplied over time.

I was hoping the Delaunay algorithm could help sort these points and apply a mesh, but it doesn’t look that way now. At first glance, ofMesh looks like a really helpful wrapper for native OpenGL functionality, but doesn’t help with my fundamental problem of sorting a set of 3D points in preparation for wrapping a mesh. Of course, I could be thinking of the problem incorrectly! Any suggestions?

At the given link you’ll find some sample code using the superformula to create a mesh with the help of OpenScenGraph. The concepts of OpenSceneGraph’s Geometry-object are similar to the ofMesh-object and should be easy to port.

http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=618&view=markup

I have to be honest, I don’t really understand the code in that link. The actual superformula implementation looks more or less the same as I what I’m doing, but there’s more advanced stuff than I understand right now. It looks like vertices may be being sorted by comparisons to a value called “epsilon”, but without documentation of the author’s intent, I’m a bit lost. Can you elaborate a little bit about what is going on there?

Just to see what would happen, I removed all my Delaunay-related code and tried to use ofMesh. However, I end up with the same results that I was getting initially in Processing - unsorted vertices resulting in utter chaos. Attached is a screenshot of what it looks like.

epsilon is a threshold-value, so that the code doesn’t create to many triangles. The vertices are not sorted in any way.

The example creates 4 vertices for 2 triangles, instead of one vertice as done in your code. the four vertices are used two triangles forming a aquad if they are not to small.

HTH,

Stephan

Hm, I’m having trouble understanding how this approach helps, but I thought I’d give it a shot to see if any light bulbs went off anyway.

No segfaults, but just a black screen, nothing happening.

Here is my code, maybe I missed some big important step somewhere. I left out all of the epsilon stuff, because I didn’t quite understand it, in an attempt to keep things simple to help me track bugs. When I output x/y/z components of the ofVec3fs I am getting, I see exceedingly small numbers (like -1.709e-005).

Can you post some sample values for a, b, m1, m2, etc etc so I can see if maybe my superformula parameters are just crazy?

#include “testApp.h”

//--------------------------------------------------------------
void testApp::setup(){
// Generate the supershape
a = 1;
b = 1;
m1 = 10;
m2 = 10;
n1_1 = 1;
n2_1 = 2;
n3_1 = 1;
n1_2 = 1;
n2_2 = 5;
n3_2 = 3;
xres = 50;
yres = 50;
scaleFactor = 1;

// Delaunay
buildSupershape();
}

//--------------------------------------------------------------
void testApp::update(){
ofBackground(0);
}

//--------------------------------------------------------------
void testApp::draw(){
ofFill();
ofSetColor(255,255,255);

mesh.draw();
}

// Actual superformula implementation
float testApp::superformula(float a, float b, float m, float n1, float n2, float n3, float angle) {
float r;
float t1,t2;

t1 = cos(m * angle / 4) / a;
t1 = abs(t1);
t1 = pow(t1, n2);

t2 = sin(m * angle / 4) / b;
t2 = abs(t2);
t2 = pow(t2, n3);

r = pow(t1+t2, 1/n1);

return r;
}

void testApp::buildSupershape() {

// Determine resolution of shape
int thetaStep = (2 * PI) / xres;
int phiStep = PI / yres;

// Generate each point
for(int lat_count = 0; lat_count < xres; lat_count++) {
float phi1 = lat_count * phiStep - (PI*2);
float phi2 = phi1 + phiStep;

for(int long_count; long_count < yres; long_count++) {
float theta1 = long_count * thetaStep - PI;
float theta2 = theta1 + thetaStep;

// Following code adapted from http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=604&content-type=text%2Fplain
float r1_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, theta1);
float r2_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, phi1);
float r1_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, theta2);
float r2_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, phi2);

ofVec3f pa = ofVec3f(r1_1*cosf(theta1)*r2_1*cosf(phi1)*scaleFactor, r1_1*sinf(theta1)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);
ofVec3f pb = ofVec3f(r1_2*cosf(theta2)*r2_1*cosf(phi1)*scaleFactor, r1_2*sinf(theta2)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);
ofVec3f pc = ofVec3f(r1_2*cosf(theta2)*r2_2*cosf(phi2)*scaleFactor, r1_2*sinf(theta2)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);
ofVec3f pd = ofVec3f(r1_1*cosf(theta1)*r2_2*cosf(phi2)*scaleFactor, r1_1*sinf(theta1)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);

cout << pa.z << “\n”;

mesh.addVertex(pa);
mesh.addVertex(pb);
mesh.addVertex(pc);

mesh.addVertex(pc);
mesh.addVertex(pd);
mesh.addVertex(pa);
}
}

cout << mesh.getNumVertices() << “\n”;

}

You are missing:

  
  
    mesh.setupIndicesAuto();  
    mesh.setMode(OF_PRIMITIVE_TRIANGLES);  
  

without these two lines no triangles get drawn. And there are some other errors in your code:

  
  
void testApp::buildSupershape() {  
  
    // Determine resolution of shape  
    float thetaStep = (2 * PI) / xres; // needs to be float!  
    float phiStep = PI / yres; // needs to be float!  
  
    // Generate each point  
    for(int lat_count = 0; lat_count < xres; lat_count++) {  
        float phi1 = lat_count * phiStep - (PI*2);  
        float phi2 = phi1 + phiStep;  
        // missing start-value for long_count!  
        for(int long_count = 0; long_count < yres; long_count++) {  
            float theta1 = long_count * thetaStep - PI;  
            float theta2 = theta1 + thetaStep;  
  
            // Following code adapted from [http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=604&content-type=text%2Fplain](http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=604&content-type=text%2Fplain)  
            float r1_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, theta1);  
            float r2_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, phi1);  
            float r1_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, theta2);  
            float r2_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, phi2);  
  
            ofVec3f pa = ofVec3f(r1_1*cosf(theta1)*r2_1*cosf(phi1)*scaleFactor, r1_1*sinf(theta1)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);  
            ofVec3f pb = ofVec3f(r1_2*cosf(theta2)*r2_1*cosf(phi1)*scaleFactor, r1_2*sinf(theta2)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);  
            ofVec3f pc = ofVec3f(r1_2*cosf(theta2)*r2_2*cosf(phi2)*scaleFactor, r1_2*sinf(theta2)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);  
            ofVec3f pd = ofVec3f(r1_1*cosf(theta1)*r2_2*cosf(phi2)*scaleFactor, r1_1*sinf(theta1)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);  
  
            cout << pa << "\n";  
  
            mesh.addVertex(pa);  
            mesh.addVertex(pb);  
            mesh.addVertex(pc);  
  
            mesh.addVertex(pc);  
            mesh.addVertex(pd);  
            mesh.addVertex(pa);  
        }  
    }  
    mesh.setupIndicesAuto();  
    mesh.setMode(OF_PRIMITIVE_TRIANGLES);  
    cout << mesh.getNumVertices() << "\n";  
  
}  
  

and your scale-factor is too small.

hth,
stephan

So close! lol. I’m surprised the compiler didn’t toss a fit about long_count not being initialized; C++ can be quirky sometimes :stuck_out_tongue:

Looks like I’ve got a nice complete mesh now! Its hard to tell without any shading / lighting, but it doesn’t appear to have any artifacts or strangeness. I inserted a call to ofEnableLighting() in the draw() function and the mesh turned gray, with no shadows or anything, but I suspect I need to spend some more time learning about how to use lights in OF. Here’s a new screenshot (attached).

Do I need to explicitly set up the normals in ofMesh in order for lights to work, or does it do it automatically?

You’ll need to set up the normals to get specular highlights but just positioning the light correctly should give you a basic illumination. Calculating normals can be a bit of a headache, I’ve used something like this:

  
  
ofVec3f calculateNormal( const ofVec3f &p1, const ofVec3f &p2, const ofVec3f &p3 )  
{  
    ofVec3f V1= (p2 - p1);  
    ofVec3f V2 = (p3 - p1);  
    ofVec3f surfaceNormal;  
    surfaceNormal.x = (V1.y*V2.z) - (V1.z-V2.y);  
    surfaceNormal.y = - ( (V2.z * V1.x) - (V2.x * V1.z) );  
    surfaceNormal.z = (V1.x-V2.y) - (V1.y-V2.x);  
    return surfaceNormal;  
}  
  
  

HTH

Be sure to normalize your normals, or the lighting calculations can go mad.

  
  
ofVec3f calculateNormal( const ofVec3f &p1, const ofVec3f &p2, const ofVec3f &p3 )  
{  
    ofVec3f p12 = (p2 - p1);  
    ofVec3f p13 = (p3 - p1);  
    ofVec3f surfaceNormal = p12.getCrossed(p13);  
    return surfaceNormal.normalize();  
}  
  
  

cheers,

Stephan

I always forget that part :slight_smile: The canonical normalization functions are here: http://www.opengl.org/wiki/Calculating-a-Surface-Normal

but I like Stephans code better than mine, easier to read.

Uh oh, calculating normals revealed that actually the mesh issue is not fixed! I had a suspicion, because whenever I adjust the xres or yres of my model, the mesh gets completely messed up again.

I actually tried replacing my superformula implementation with the one provided by sth, but I get the exact same mesh.

  
  
  
#include "testApp.h"  
  
//--------------------------------------------------------------  
void testApp::setup(){  
    // Generate the supershape  
    a = 1;  
    b = 1;  
    m1 = 5;  
    m2 = 10;  
    n1_1 = 10;  
    n2_1 = 2;  
    n3_1 = 1;  
    n1_2 = 1;  
    n2_2 = 5;  
    n3_2 = 3;  
    xres = 5;  
    yres = 5;  
    scaleFactor = 100;  
  
    // Delaunay  
    buildSupershape();  
  
    // Setup mesh  
    mesh.setupIndicesAuto();  
    mesh.setMode(OF_PRIMITIVE_TRIANGLES);  
  
    cam.enableMouseInput();  
    cam.begin();  
}  
  
//--------------------------------------------------------------  
void testApp::update(){  
    ofBackground(0);  
}  
  
//--------------------------------------------------------------  
void testApp::draw(){  
    ofFill();  
    ofSetColor(255,255,255);  
  
    light.enable();  
  
    cam.begin();  
  
    ofRotateY( ofGetFrameNum() * .1);  
  
    mesh.draw();  
}  
  
// Actual superformula implementation  
float testApp::superformula(float a, float b, float m, float n1, float n2, float n3, float angle) {  
    /*  
    float r;  
    float t1,t2;  
  
    t1 = cos(m * angle / 4) / a;  
    t1 = abs(t1);  
    t1 = pow(t1, n2);  
  
    t2 = sin(m * angle / 4) / b;  
    t2 = abs(t2);  
    t2 = pow(t2, n3);  
  
    r = pow(t1+t2, 1/n1);  
  
    return r;  
    */  
  
    return powf(powf(fabsf(cosf(m*angle/4)/a), n2_1)  
                + powf(fabsf(sinf(m*angle/4)/b), n3_1), 1.0f/n1_1 );  
}  
  
void testApp::buildSupershape() {  
  
    // Determine resolution of shape  
    float thetaStep = (2 * PI) / xres;  
    float phiStep = PI / yres;  
  
    // Generate each point  
    for(int lat_count = 0; lat_count < xres; lat_count++) {  
        float phi1 = lat_count * phiStep - (PI*2);  
        float phi2 = phi1 + phiStep;  
  
        for(int long_count = 0; long_count < yres; long_count++) {  
            float theta1 = long_count * thetaStep - PI;  
            float theta2 = theta1 + thetaStep;  
  
            // Following code adapted from [http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=604&content-type=text%2Fplain](http://osgtoy.svn.sourceforge.net/viewvc/osgtoy/osgtoy/trunk/src/osgToy/SuperShape3D.cpp?revision=604&content-type=text%2Fplain)  
            float r1_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, theta1);  
            float r2_1 = superformula(a, b, m1, n1_1, n2_1, n3_1, phi1);  
            float r1_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, theta2);  
            float r2_2 = superformula(a, b, m2, n1_2, n2_2, n3_2, phi2);  
  
            ofVec3f pa = ofVec3f(r1_1*cosf(theta1)*r2_1*cosf(phi1)*scaleFactor, r1_1*sinf(theta1)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);  
            ofVec3f pb = ofVec3f(r1_2*cosf(theta2)*r2_1*cosf(phi1)*scaleFactor, r1_2*sinf(theta2)*r2_1*cosf(phi1)*scaleFactor, r2_1*sinf(phi1)*scaleFactor);  
            ofVec3f pc = ofVec3f(r1_2*cosf(theta2)*r2_2*cosf(phi2)*scaleFactor, r1_2*sinf(theta2)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);  
            ofVec3f pd = ofVec3f(r1_1*cosf(theta1)*r2_2*cosf(phi2)*scaleFactor, r1_1*sinf(theta1)*r2_2*cosf(phi2)*scaleFactor, r2_2*sinf(phi2)*scaleFactor);  
  
            mesh.addVertex(pa);  
            mesh.addVertex(pb);  
            mesh.addVertex(pc);  
  
            mesh.addNormal( calculateNormal(pa, pb, pc) );  
  
            mesh.addVertex(pc);  
            mesh.addVertex(pd);  
            mesh.addVertex(pa);  
  
            mesh.addNormal( calculateNormal(pc, pd, pa) );  
        }  
    }  
  
}  
  
ofVec3f testApp::calculateNormal( const ofVec3f &p1, const ofVec3f &p2, const ofVec3f &p3 )  
{  
    ofVec3f V1 = (p2 - p1);  
    ofVec3f V2 = (p3 - p1);  
    ofVec3f surfaceNormal;  
    surfaceNormal.x = (V1.y*V2.z) - (V1.z-V2.y);  
    surfaceNormal.y = - ( (V2.z * V1.x) - (V2.x * V1.z) );  
    surfaceNormal.z = (V1.x-V2.y) - (V1.y-V2.x);  
    return surfaceNormal;  
}  
  

replace

  
  
float phi1 = lat_count * phiStep - (PI*2);    
  

with

  
  
float phi1 = lat_count * phiStep - (PI*0.5);    
  

hth,
Stephan

Hmm, made the change and indeed the shape changes, but its still having issues. Now any number I use for xres and yres results in spiky and strange meshes.

Am I adding the normals correctly? Add three vertices, then one normal to my ofMesh object?

Strange that the mesh isn’t rendering correctly yet - almost 100% of the code isn’t even mine anymore! :stuck_out_tongue: Hopefully by figuring out what is going on I can get some good insight into how to make meshes in general, I’ll bet there is something fundamentally wrong with what I’m trying to do.

Here’s a screenshot (attached), let me know if you want me to post the code (same as before, with addition of change from sth).

I don’t now the ofMesh internals, but usually you provide one normal/color/tex-coord per vertex. This will affect lighting but not the overall form of your mesh.

How about this: when I bump the resolution (xres and yres) up to about 50 or 100, I do see something that COULD be a supershape, but instead of each vertex connecting into a complete mesh, the form is made of a bunch of quads that are all perpendicularly oriented to the shape. As I rotate the shape about the Y axis, one can see many, many ‘slivers’ pointing inwards, rather than connecting together. It’s quite obvious when you see the motion yourself, but here is a screenshot for now (attached). Seems to be more of a matter of orientation rather than superformula math at this point, which is good.

I’ve never made meshes out of a set of 3D points before, and am having a hard time finding resources to learn about how. I’ve found plenty of OpenGL references and raw docs on OF functions and so on, but no information about HOW to use them. Can anyone recommend a way for me to build up an intuitive idea of how to tackle this kinds of problems myself through practical examples? I see some workshops pop up in big cities once in a while, but not much help online.