# Triangulating a surface constructed by 3D curves

I have a 3D polygon (i wonder if polygon is the correct term here) that is constructed from 3D curves. These curves are basically lists of 3D points.

I would like to triangulate this surface so i could draw it using OpenGL.

Are there any recommended algorithms and/or code libraries (preferably in c++) that i could use?

The example that I provided (creating a sphere from a single triangle strip) in this forum sounds close to what you are trying to do.
assume:
float curve[n][npoints]; // this assumes that all curves have the same number of points
int i, j;
curve[i][j] = x;
curve[i][j] = y;
curve[i][j] = z

for(i=0; i , (n-1); i++){
glBegin(GL_TRIANGLE_STRIP);
for(j=0; j < npoints; j++){
glVertex3fv(curve[i]j]);
glVertex(3v([i+1][j]);
}
glEnd();
}

This is just the code fragment that draws the triangles.
If curves intersect (share common vertices) you could have problems. One simple way to avoid that is to move one of those common vertices just a bit.

[QUOTE=esapir;1258017]I have a 3D polygon (i wonder if polygon is the correct term here) that is constructed from 3D curves. These curves are basically lists of 3D points.

I would like to triangulate this surface so i could draw it using OpenGL.

Are there any recommended algorithms and/or code libraries (preferably in c++) that i could use?[/QUOTE]

[QUOTE=wmelgaard;1258025]The example that I provided (creating a sphere from a single triangle strip) in this forum sounds close to what you are trying to do.
assume:
float curve[n][npoints]; // this assumes that all curves have the same number of points
int i, j;
curve[i][j] = x;
curve[i][j] = y;
curve[i][j] = z

for(i=0; i , (n-1); i++){
glBegin(GL_TRIANGLE_STRIP);
for(j=0; j < npoints; j++){
glVertex3fv(curve[i]j]);
glVertex(3v([i+1][j]);
}
glEnd();
}

This is just the code fragment that draws the triangles.
If curves intersect (share common vertices) you could have problems. One simple way to avoid that is to move one of those common vertices just a bit.[/QUOTE]

I think this kind of solution will work only for planar polygons. I don’t think it will work for real 3D polygons

I doubt if you will find source code for this. My son was working on a similar project recently for his company. He found quite a few papers on algorithms but had to implement it himself. The basic idea is to expand each edge line into a quad but avoid overlapping quads. For optimum performance and shape definition the quads should be approximately the same area.

It was also my intuition - that i need to construct quads. However, there are several problems that i am not sure how to solve:

1. Number of points on the curves is not equal and more than that - the distance between every two samples is not the same.
2. I am not sure how this algorithm should work. At first my idea was to start on one of the polygon edges (i cam assume for simplicity that the polygon always has exactly 4 curves) and iteratively build the grid. However, i think that the grid will look different if i will start for different edges. Am i correct? How i should approach to this problem?

Again without having seen your data, it sounds like the same problem as meshing a Finite Element Analysis (FEA) model. The Finite Element Method Its Basis And Fundamentals , by Ziendiewicz, Taylor & Zhu has an entire chapter on that subject.

[QUOTE=esapir;1258032]It was also my intuition - that i need to construct quads. However, there are several problems that i am not sure how to solve:

1. Number of points on the curves is not equal and more than that - the distance between every two samples is not the same.
2. I am not sure how this algorithm should work. At first my idea was to start on one of the polygon edges (i cam assume for simplicity that the polygon always has exactly 4 curves) and iteratively build the grid. However, i think that the grid will look different if i will start for different edges. Am i correct? How i should approach to this problem?[/QUOTE]