# Efficient Polygon Lathe

Hey,

I’m looking for some code that will take a 2D profile of points and spin it, generating new vertices and creating connecting polygons (quads or triangles). The thing is, the vertices of the output mesh must be shared.

My current implementation generates the points and adds polygons, assuming that there are an exact number of vertices as calculated from the number of points in the profile times the number of steps in sweeping the lathe. It works, but produces way to many vertices and hurts the performance of my modelling app.

Any suggestions? I’m sure someone has done this.

My app maintains a list of vertices and a list of polygons. Each polygon has pointers to the vertices it spans.

I’m not sure what you mean by the vertices must be shared. If you rotate n 2d vertices using m segments, you’ll get n*m vertices (assuming you already share the 0 and 360 degree vertices). There is no way around this…

At best you can reduce this by sharing vertices that have a radius of 0 and a normal vector parallel to the rotation axis, but for any but the most obscure special cases, this will be the case at most two times (at the top and bottom of the model), so you will save 2*m-2 vertices at best, and that’s not really going to improve performance…

If you know how to lathe, then you surely must know how to weld a model and remove extra vertices.
The simplest brute force way is to double-loop your vertex list, check for similar vertices, tag 'em,
then delete them.

And lathing brings up a lot of problems too, like degenerate triangles, interior faces,
capping back faces, etc… There is a lot more post “cleanup” work involved for a good lathe.

Originally posted by Overmind:
[b]I’m not sure what you mean by the vertices must be shared. If you rotate n 2d vertices using m segments, you’ll get n*m vertices (assuming you already share the 0 and 360 degree vertices). There is no way around this…

At best you can reduce this by sharing vertices that have a radius of 0 and a normal vector parallel to the rotation axis, but for any but the most obscure special cases, this will be the case at most two times (at the top and bottom of the model), so you will save 2*m-2 vertices at best, and that’s not really going to improve performance…[/b]
I mean that each polygon points to the vertices it uses. Hence, mulitple polygons may be sharing the same points. And regarding efficiency, I mean that there are no two vertices in the list which occupy the same position.

Right now I’ve got a method for creating new vertices:

`````` Vertex *AddVertex(Vertex *v);
``````

which iterates through the list of vertices comparing the coordinates. If a vertex already exists in the list, that vertex is returned. Otherwise, the new vertex, v, is added to the end and returned. This way the calling function can be sure that the vertex it just created is unique and this works great for the non-lathed primitives (eg. cubes etc).

I can’t do this with the lathe because the for-loop which adds the polygons calcuates the index numbers of the vertices to use based on the number of vertices in the profile and the number of lathe-steps. The vertices are simply added to the end of the list. If I used AddVertex() as above, a lot of these vertices would not exist (as they are duplicates).

It seems I have 2 options:

1. Make the polygon-generating code smarter so that it can redirect the polys to the actual vertices it needs, rather than just assuming they exist.
2. Search the list afterwards and combine the duplicates. This is difficult because it means that for every duplicate removed, you have to find the associated polygon and redirect it to the original vertex. This implies that each vertex must maintain a list of adjacent polygons. So we have more lists, and more potential duplicates.

It’s a mess!

I still don’t understand how you get duplicate vertices in the first place.

Of course that’s assuming you don’t have any duplicate vertices or self intersections on the original 2D profile. But then it would be easier to get rid of them before doing the lathe operation.

Here is my lathe code. Vertices is a vector which contains the list of points. Hope it makes sense!

``````

void Mesh::latheProfile(vector<Vertex*> &profile, int slices)
{
for (unsigned short i = 0; i < profile.size(); i++)
{
// can't use this
verticess.push_back(profile[i]);
}

int numVertices = vertices.size()-1;
int n = vertices.size();

for (unsigned short b = 1; b < slices; b++)
{
for (unsigned short a = 0; a <= numVertices; a++)
{
Vertex *v = vertices[a];

float r = sqrt((v->local.x * v->local.x) + (v->local.z * v->local.z));

float x = r * cos(b * (2 * kPi / slices));
float y = v->local.y;
float z = r * sin(b * (2 * kPi / slices));

// can't use this
vertices.push_back(new Vertex(x,y,z));
}
}

numVertices = vertices.size();

for (unsigned short s = 0; s < slices; s++)
{
for (unsigned short t = 0; t <= n-2; t++)
{
// make 4-sided polygon from point indexes specified
// use mod to wrap around numbers at end
(t + 1 + (s * n)) % numVertices,
(t + n + 1 + (s * n)) % numVertices,
(t + n + (s * n)) % numVertices);
}
}

}
``````

Any suggestions?

Anyone?

I think I found the problem : it is because of how you implemented addQuad.

Something tells me you use GL_QUADS. Instead use GL_QUAD_STRIP, it will need twice less vertices. And use arrays instead of immediate mode, etc.

Can you post the addQuad code and how you draw it ?

Yes I use GL_QUADS and immediate-mode rendering at this point. I’m trying to keep the vertex + poly structures abstract from OpenGL because a RayTracer sits on top and uses the same data. I can’t use VertexArrays or quadstrips for this reason.

As for QuadStrips using half the vertices, well that’s not quite true. My vertices are already shared among the polygons.

AddQuad simple adds a new polygon to the polygon list, referencing the vertices at the indices supplied.

The problem with this code is that it generates one more profile slice than it should. This is necesary because of the way the polygons are constructed in the second loop. I need to find an alternative way of do this.

Just special case the last iteration of the loop, so the last slice uses the vertices (slices-1, 0) instead of (slices-1, slices).

And you should really consider implementing strip and vertex array support in your raytracer. That shouldn’t be very hard, and you gain a lot of performance.

Thanks, I’ll look into it.

I mean that each polygon points to the vertices it uses. Hence, mulitple polygons may be sharing the same points. And regarding efficiency, I mean that there are no two vertices in the list which occupy the same position.

Right now I’ve got a method for creating new vertices:

`````` Vertex *AddVertex(Vertex *v);
``````

which iterates through the list of vertices comparing the coordinates. If a vertex already exists in the list, that vertex is returned. Otherwise, the new vertex, v, is added to the end and returned. This way the calling function can be sure that the vertex it just created is unique and this works great for the non-lathed primitives (eg. cubes etc).

I can’t do this with the lathe because the for-loop which adds the polygons calcuates the index numbers of the vertices to use based on the number of vertices in the profile and the number of lathe-steps. The vertices are simply added to the end of the list. If I used AddVertex() as above, a lot of these vertices would not exist (as they are duplicates).

Hi! I’m trying to write my own lathe function and became a bit confused. As I see You are quite familiar with this issue I would like to ask you some questions.

1. how do You store glVertexes? I solved it storing the coordinates of them, and then adding glVertexes with those coordinates, but I can’t and don’t even know if it is possible to make some pointers to glVertexes or something similar. Please explain me how do You do this in your code.

2. I can’t find solution for duplicating vertices when I want to create more than one slice of my object. I always need to duplicate the profile or right/left quad side vertices. Do you know how to get rid of those extra vertices? It is connected with the previous question as I do not know how to point to the certain vertex.

I will appriciate any help.