Surface triangles

I would like to understand the process of extracting 3D surface triangle patches from an object in 3D space for STL file generation.

So, given a 3D volume which contains some object, how would I go about finding the patches?

I hope this the proper forum to ask this type of a question…

Thank you!

That’s a fairly hard problem. What kind of data do you have? If you have voxels, look up “marching cubes” algorithm.

If you have your 3d object as a point cloud then there are algorithms that attempt to reconstruct the surface. You can look at Delaunay triangulation as a starting point - although personally I haven’t been able to find an actual algorithm to use in 3 dimensions. Are the points noisy or not? That complicates things.

Thanks Budric,

I know how to do this with marching cubes, but then I could do it all without using OpenGL. Yes the system is voxel-based. And the surface is quite clean, barely any noise and I see the object in a 3D cube in front of me. So with that the challenge is to tesselate that object surface in 3D space and I was curious what a good OpenGL-based approach would be for this job.

If the object were all convex it’d be pretty easy, but it has concave sections, so something like a convex hull won’t do :frowning:


umugl, OpenGL is an API for rendering polygonal objects, nothing else. If you know how to solve your problem “without GL”, do it. GL is just there to draw it.

As said Zengar.
There are some domains of computing that can be interesting to do with a GPU (see the GPGPU stuff, image filtering, feature tracking, matrix computations, CFD, etc) but tesselating a point cloud does not really fit to a stream processor.

Well, there are GPU implementations of the marching cubes (CUDA) and marching tetrahedra (OpenGL) algorithms available…

Oh already ?
Do you have links, about performance, features, implementation … ?

There’s code for marching cubes in the CUDA SDK and code for marching tetrahedra in NVidia SDK 10 (look for Cg Isosurf).
Some background information on Cg Isosurf can be found in this whitepaper.

I decided to answer the question in the way I did based on umugls position in this and other threads. While I don’t doubt that it is possible to solve this problems on GPU, it appeared to me that he doesn’t want to use shaders and indeed has a misconception about GL: it seems he wants it to solve his problems “automatically”, with a minimal effort from his side. This won’t be possible.

You’re right. Being afraid to use shaders is so 20th century :wink:

I created a 2D version using the geometry shader to plot implicit 2D plots ( :smiley: ):

With my 8800 GTS, and with 500x500 divisions with this particular implicit plot (I found the inequality on a website, I didn’t come up with it!), it renders at 331 fps.

The inequality is something like this:

(cos(p.y - p.x) - sin(p.y)) * (p.x * p.x * p.x * p.x - 2.0 * p.x * p.x * cos(2.0 * p.y + 2.4 + time) + 0.9) + pow(0.62 * p.x, 1000.0) < 0.0;

with appropriate scaling on p.

Wow! You have found THE FORMULA!

Nah, I got the formula from here.


Now that you are done bickering about the limitations I have to pose, I know it is possible to do this using a GPU’s pipeline, and I will find a way. There ain’t no mountain high enough.

The reason for my posting here was simply to see if anyone had any prior experience or pointers on this topic, not to fire off a round of sentiments.


If you don’t want using shaders, do it on the CPU. Doing stuff like that with plain GL is like trying to build a house using a screwdriver only. I mean, you could, but why should you? It won’t be fast or nice anyway. Just face it: OpenGL is not designed with such things in mind: it is an API to draw triangles.