Generating surfaces algorithmically

Hello,

I have an application that draws a nice shape (a molecule). This is accomplished through calls to gluSphere for each atom in the molecule. Some of the spheres are completely culled, as they are in the “interior” of the molecule. In other views, I draw certain aspects of the molecule in “schematic” form, with 3-D arrows and coils representing certain molecular features.

I would like to generate a surface shape (a mesh) that defines the exterior of the molecule, whether it’s been drawn exclusively with spheres or whether I’ve included some schematic representations as well. A triangle mesh would be ideal, as I will eventually ship the triangles off to another application. (I can get the triangles that are generated through any OpenGL primative by using the feedback buffer, so defining the mesh as triangles during the algorithm is not absolutely necessary – if I can draw the mesh through any means, then I can get OpenGL to give me the tesselated triangles).

Is there an algorithm that is suited for someone starting where I am (already have tons of code that draws the molecular structures) and needing to get where I’m going (a surface mesh)? Or will I have to write tons of additional code to compose the mesh instead of drawing the spheres/schematic structures?

If my code looks like this:

for each atom a
{
draw a sphere at a.x, a.y. a.z
}

And OpenGL culls all the internal faces, etc., when thousands of atoms are drawn, then it would seem that I should be able to
benefit from the culling etc. that OpenGL does. Otherwise my code becomes much more sophisticated (read “more work for me”):

for each atom a
{
if sphere is not already completly culled
{
convert sphere to triangles
determine which triangles contribute to surface
add them to the surface
determine which previous triangles from surface no longer belong there
remove them
recompute normals
blah, blah, blah…
}
}

Alternativley, this algorithm could start with a list of triangles (and normals) – the input would be a list of triangles, some of which are “interior” and should be culled. The output would be a (much smaller!) list of triangles that describes the surface of solid implied by the original list, with all its interior triangles removed.

Your help, as always, is most appreciated …

[This message has been edited by ghassett (edited 01-18-2002).]

OpenGL is a gray box. You put geometry in on one side, and pixels come out on the other side. More specifically, geometry does NOT come out on the other side.

If you want to do CSG on your geometry, you should look into some web searches for the various CSG and mesh manipulation toolkits that are out there.

Generating pixels from geomety primatives is the most common and, arguably, the most useful application of OpenGL. But it is not the only application. OpenGL can also be used, for example, to generate tesselated triangles from graphics primatives, through the use of its Feedback Buffer (the feedback buffer is a very useful “leak” in the gray box).

This is the “advanced programming” board where I frequently find people like myself who occasionally push the capabilities of OpenGL past its “intended purpose” to achieve creative solutions to certain graphics problems.

I agree, though, that this is really a geometry problem, so I’ll politely ask the question a different way:

If I have a list of triangles that together represent a solid, how could I derive a new list of triangles that represents just the surface of that solid? Anyone know of any algorithms that might help me? I’ve downloaded QHULL and got it working with my data, but it produces a “tautly stretched saran wrap” surface that wraps around my solid, when what I need is a a “heat-shrunk plastic” surface that clings to every nook and cranny. Helpful replies, as always, are much appreciated!

Originally posted by jwatte:
[b]OpenGL is a gray box. You put geometry in on one side, and pixels come out on the other side. More specifically, geometry does NOT come out on the other side.

If you want to do CSG on your geometry, you should look into some web searches for the various CSG and mesh manipulation toolkits that are out there.[/b]

>>>OpenGL can also be used, for example, to generate tesselated triangles <<<

How exactly does it tesselate using the feedback buffer? It does return geometry, among other things.

About your question:
Shrink wrapping a molecule made of spheres is a problem I think, unless if the spheres are intersecting as opposed to looking like bowling balls touching each other.
Something like a marching cube algorithm is needed

The “isoelectric map” (isosurface) look should be what you are looking for.
“Modelling the Surface of the Human Cortex”
is my favorite at http://astronomy.swin.edu.au/pbourke/modelling/cortex/impl.html

Do a search for marching cubes as well. Superb web site!

V-man

Thanks for the tips, V-man.

OpenGL’s feeback buffer tesselates like this:

  1. Set the feedback buffer up to return 3D points.

  2. Call any number of graphics primatives(gluSphere, gluCylinder…).

  3. Walk the feedback buffer.

On most implementations, the feedback buffer will contain a series of GL_POLYGON_TOKEN’s, with three vertices. Voila – you have the tesselated triangles that comprise the shape you drew with the graphics primatives.

// greg //

Originally posted by V-man:
[b]>>>OpenGL can also be used, for example, to generate tesselated triangles <<<

How exactly does it tesselate using the feedback buffer? It does return geometry, among other things.

About your question:
Shrink wrapping a molecule made of spheres is a problem I think, unless if the spheres are intersecting as opposed to looking like bowling balls touching each other.
Something like a marching cube algorithm is needed

The “isoelectric map” (isosurface) look should be what you are looking for.
“Modelling the Surface of the Human Cortex”
is my favorite at http://astronomy.swin.edu.au/pbourke/modelling/cortex/impl.html

Do a search for marching cubes as well. Superb web site!

V-man[/b]