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.