Using qhull

At first glance turning a bunch of points into some kind of mesh should be an easy task. However look a bit closer and its a different matter. This is where qhull comes in really handy, designed specifically to do this and other closely related tasks, it comes as a stand alone application and also a library.

Here’s some example code

    int numpoints = 6;
    coordT points[] = {
        0.000, 0.000, 0.000,
        0.001, 0.251, 0.001,
        1.002, 0.002, 0.002,
        0.003, 1.003, 0.003,
        0.004, 0.004, 1.004,
        0.005, 4.005, 0.005
    };
    int dim = 3;  // points have 3 dimensions 
    char flags[25];
    sprintf (flags, "qhull ");  // no flags
    qh_new_qhull(dim, numpoints, points, 0, flags, NULL, NULL);
    qh_getarea(qh facet_list);    
    printf("total vol %f", qh totvol);
    printf("total area %f", qh totarea);
    facetT *facet;
    vertexT *vertex, **vertexp;
    FORALLfacets {
        if (!facet->upperdelaunay) {
            printf ("set size %d ", qh_setsize (facet->vertices));
            FOREACHvertex_(facet->vertices)
                printf ("point id %d ", qh_pointid (vertex->point));
            printf ("\n");
            FOREACHvertex_(facet->vertices) {
                printf ("point id %d coordinates %f %f %f\n", qh_pointid (vertex->point), vertex->point[0], vertex->point[1], vertex->point[2]);
            }
        }
    }
    qh_freeqhull(!qh_ALL);

Take a look at the points going in, first of all I’ve added 0.001 * the point number, just to verify the coordinates coming out make sense! I’ve also added a point that should be inside the resulting shape (0.001, 0.251, 0.001) – which we shouldn’t see in the output.

The output looks consistent with what’s expected…

INFO: total vol 0.671500
INFO: total area 7.393362

set size 3 -  point ids:  5  2  0
point id 5 coordinates 0.005000 4.005000 0.005000
point id 2 coordinates 1.002000 0.002000 0.002000
point id 0 coordinates 0.000000 0.000000 0.000000

set size 3 -  point ids:  4  2  0
point id 4 coordinates 0.004000 0.004000 1.004000
point id 2 coordinates 1.002000 0.002000 0.002000
point id 0 coordinates 0.000000 0.000000 0.000000

set size 3 -  point ids:  4  5  0
point id 4 coordinates 0.004000 0.004000 1.004000
point id 5 coordinates 0.005000 4.005000 0.005000
point id 0 coordinates 0.000000 0.000000 0.000000

set size 3 -  point ids:  4  5  2
point id 4 coordinates 0.004000 0.004000 1.004000
point id 5 coordinates 0.005000 4.005000 0.005000
point id 2 coordinates 1.002000 0.002000 0.002000

Notice in this list of triangles there is no point id 1, and all the coordinate values make sense looking at the third decimal place. As a bonus it’s also possible to find the volume of the output shape, something in my case I’ll be using to help keep score…

Due to the structuring of the vertex data, its not suitable for OpenGL vertex buffer (alas!) So having creating a shape with qhull you’ll have to copy the data into a format suitable for GL buffers.

Leave a Reply

Your email address will not be published. Required fields are marked *