chris@spock.ame.arizona.edu (Chris Ott) (06/29/89)
I have a 3d graphics problem, and I was wondering if anyone could help.
I would like to take a set of coutours of a 3d object and generate
a list of polygons (preferably triangles) that could be used in a solid-
shading program to render that object. For instance, one of the objects
I'm working on is a catscan of a person's head. I take each slice and
outline the area of interest, the brain, for example. Then, using the
contours from each slice, I would like to make a set of polygons that
are a 3d representation of the brain. Another thing I'm working on is a
contour map. Given the contours of the map, I'd like to make a model of
the landscape it describes in the computer.
I have a program now, but it doesn't quite work. It has a problem
with narrow appendages (such as the ears on the head). I'm pretty sure
it would work if I had more slices, but I need it to work with what I have.
It also won't work when there is more than one contour on a level,
so the head will work okay, but the map won't because there are several
peaks.
Does anyone out there know an algorithm that would solve my problem,
or at least know of a reference I can look up? Any help would be greatly
appreciated.
Thanks,
Chris
-------------------------------------------------------------------------------
Chris Ott
Forensic Productions, Inc. Infatuation is blind, not love. A
Tucson, Arizona person in love can see the other's
faults, but loves them anyway.
Internet: chris@spock.ame.arizona.edu
UUCP: {allegra,cmcl2,hao!noao}!arizona!amethyst!spock!chris
-------------------------------------------------------------------------------foo@titan.rice.edu (Mark Hall) (06/29/89)
In article <1001@amethyst.math.arizona.edu> chris@spock.ame.arizona.edu.UUCP (Chris Ott) writes: > I would like to take a set of coutours of a 3d object and generate >a list of polygons (preferably triangles) that could be used in a solid- >shading program to render that object. For instance, one of the objects >I'm working on is a catscan of a person's head. I take each slice and >outline the area of interest, the brain, for example. Then, using the >contours from each slice, I would like to make a set of polygons that >are a 3d representation of the brain. Another thing I'm working on is a >contour map. Given the contours of the map, I'd like to make a model of >the landscape it describes in the computer. > > I have a program now, but it doesn't quite work. It has a problem >with narrow appendages (such as the ears on the head). I'm pretty sure >it would work if I had more slices, but I need it to work with what I have. > > It also won't work when there is more than one contour on a level, I have been looking at this sort of problem for a while. I think you have discovered a fundamental problem with taking 2D contours and forming a surface from them. You say your program doesn't work when there are multiple contours on a level but the head is (should be) okay. If your slices are in the xy plane (various heights for a standing person) aren't the ears sometimes disjoint from the head? If so, you have the problem described below. There are multiple references for algorithms doing what you propose. I have a file of them somewhere (lost in my desk :^) I seem to remember one by Fuchs, from SIGGRAPH 8x, but couldn't find it in a quick flip through the last few years. From what I can tell, all these algorithms have big trouble when adjacent contours are topologically different. Consider a torus (donut) shape on end (like an 'O') with slices taken in height. Between two slices, it goes from one connected contour to two separate ones. Making a program correctly and nicely create polygons to join these distinct contours is difficult, maybe impossible. The best way to get polygons from the kind of data you have is to use the fact that you have 3D data on a nice grid. There have been several techniques for finding polygons for different "level sets" in that kind of data. Some references are: Wyvil, G.,McPheeters, C., and Wyvil, B., (1986) ``Data structure for soft objects", The Visual Computer,2:227-234. Lorenson, W., and Cline, H. (1987) ``Marching Cubes: A High Resolution 3D Surface Construction Algorithm", Computer Graphics, Volume 21, No. 4, pp. 163-169. Durst, M. J. (1988), "Additional Reference to Marching Cubes", Computer Graphics, Volume 22, No. 2, pp. 72,73. Bloomenthal, J., (1988) Polygonalization of Implicit Surfaces, Computer Aided Geometric Design 5 (1988), pp. 341-355. (also Xerox Report CSL-87-2. and in SIGGRAPH course notes (87 & 88?)) - mark
ksbooth@watcgl.waterloo.edu (Kelly Booth) (06/29/89)
Some of the classic references for this are Fuchs (et al.) SIGGRAPH '77, Christiansen (et al.) SIGGRAPH '78, and Hermann (et al.) SIGGRAPH '80.