With this data structure I’m allocating a model, that is scanned in slices by a 3D digitizer, but now I would like to render it, so I need to create the faces , and may be the normals also, to use the rendering options from OpenGL, does anyone know a way to calculate the faces, in triangles or quads?
Just to make sure that I understand the question, you have a bunch of points which make up planar slices of an object which you are trying to reconstruct as polygonal data, right?
Unless you know something about the points and where they are placed, this is a pretty tough problem. One solution can be found in Chek T. Lim’s doctoral dissertation from the University of Washington. Take a look at his publications listed in his resume at: http://www.me.washington.edu/~cdam/PEOPLE/CHEK/resume/resume.html
The method is kind of involved, but it gives pretty good results.
[This message has been edited by Rob (edited 08-11-2000).]
//one = first slice
//two = adjacent slice
//a,b,c = 3 points (which become the
// triangle)
//o,t = placeholders for where we are.
//last = did we take a vertex from
// one or two last?
one = firstsection;
o = one->points;
two = firstsection->next;
t = two->points;
do {
a = o;
o = o->next;
b = o;
o = o->next;
c = t;
t = t->next;
//Even though we took the last vertex from
//two, last MUST BE one here for the
//rest of the code to work.
last = 1;
do {
Draw_Triangle(a,b,c);
a = b;
b = c;
if (last == 1) {
c = t;
t = t->next;
last = 2;
} else {
c = o;
o = o->next;
last = 1;
}
} until (a == NULL | | b == NULL | | c == NULL);
one = two;
o = one->points;
two = two->next;
t = two->points;
} until (one == NULL | | two == NULL);
This loop basically goes through each pair of adjacent slices and makes triangles out of it. The order in which the triangles are drawn is something like:
1
2
3
4
5
6
7
8
…
Rob, thanks for your post -I’m going to search for those journals. I need an algorithm that can form a surface from contours with irregular vertex locations and variable number of vertices.
If the contours are all slices parallell to some common plane, one way of figuring out how to draw the mesh is to calculate a center vector (which is a normal to the plane). Then walk each slice and calculate the angle (rotation) of the sampled vertexes relative to the intersection of the contour plane as intersected by the center vector. Then “connect” vertexes from plane N to the vertex(es) in plane N+1 which have the closest-to-equal angles. This works best when your center vector actually lies “inside” all of the contours, else you will get angle inversion where the contours are too concave.
Good luck!
postscript: you don’t need to use the same center vector for all contours, only for each adjacent pair of contours. I e when calculating the angle values for contour N and N+1 to connect them, use the same center vector for both. Then when calculating the angles for N+1 to N+2, you can use another center vector, at the expense of having to re-calculate the values for slice N+1. To make it really interesting, you can extrapolate this to find one “center vector” per pair of slices which is not necessarily normal to the parallell plane, as long as it’s convex for each slice where it intersects the slice; this may be useful when the distance between slices is “large” and there is little or no overlap between the slices (as projected onto the parallell plane).
(When I say “parallell plane,” do I really mean “co-planar” ? I haven’t taken geometry for ten years )
[This message has been edited by bgl (edited 08-13-2000).]