How to create faces

Hello people,
see the specificatins below:

struct Section{
struct Section *next;
struct Points_in_Section *points;

struct Points_in_Section{
struct Points_in_Section *next
float coords[3];

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?

Thanks a lot

Best regards


did you try :


It’s the better way to draw a mesh (if u want to draw a mesh).

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:
The method is kind of involved, but it gives pretty good results.

[This message has been edited by Rob (edited 08-11-2000).]

Dear Rob,

You understood the problem, but I don’t found anything useful in the site that you posted.

About the JC post, I know the sintaxe of the function, but how can I allocate the mesh structure, something like this:

| | | | | | |
| | | | | | |
| | | | | | |
1 2 3 4 5 6 7

this is the slices, if I want to make triangles, I need to have 2 vertex from the 1st slice, and one from the 2nd slice…is it right ???

using the way that I’m allocating the memory, how can I create another structure, and how would be the function to make the triangles???

Thanks a lot

Best regards


The following code segment MIGHT help…

//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?

Section *one;
Section *two;
Points_in_Section *a, *b, *c;
Points_in_Section *o, *t;
int 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 {
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:

Hope this helps!


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.

I expect the articles to be a big help!

Thanks Wizard

I will try to implement something on this way.

Best regards


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 :slight_smile: )

[This message has been edited by bgl (edited 08-13-2000).]