Recursive Subdivision

[onesvenus]

Hi all!
I'm trying to implement the Doo&Sabin recursive subdivison algorithm as an assignement but I've some problems.
The mesh data comes as a shared list of vertices and a list of faces storing pointers for its vertices.
What I'm doing is:
- Calculate the new vertex position to create each face-face.
- Look at each pair of vertices in each face (what would be an edge) and check if a edge-face was created previously, if it's not done I look at each face of the model looking for the same pair of vertices but reversed (the edge should be in the opposite direction) and create a face with these two pairs.
And the problem comes because I don't know how to create the vertex-face. I'm thinking of using a list to store which vertices derive from an original vertex but I don't know how to choose the right order to create a well oriented polygon.

I've searched some examples and haven't found anything, in some places they say the most efficient way of doing subdivision is using the half-edge data structure but even using it, I don't know how to create the vertex-faces.

Anyone can help??

 

[Simon F]

I haven't tried Doo-Sabin but I have implemented Catmull-Clark. One warning though - It's been a long while so I'm probably a bit rusty on this.

Are you doing each step completely before moving on to the next? (Apologies if I get the order wrong but...) i.e. computing all the, say, face vertices, then all the edge verts and then updating the original vertices?

 

[Simon F]

..or is your problem just how to maintain a data structure to manage the mesh updates?

 

[onesvenus]

Yes I'm doing each step completely before moving next, is it better to do it in another way?
And maybe the structure is a problem too, I'm just using an array where I store the new vertices formed by the original vertex i, this way I know the vertices that would form a vertex-face and a list of edge-faces already made.

 

[onesvenus]

Well, it's done. There is some places where it could be optimized but I have to check with my teacher if I can modify the mesh data structure they gave us.

 

[onesvenus]

Now I have another problem
Until now I've been subdividing solids without holes(cubes, pyramids, ...) but my next step is to subdivide solids with holes (something like a window) and I'm facing one new problem. Before I was using the euler equation to calculate the number of new vertices (number of edges+number of faces+number of vertices) because I didn't have the number of edges but now I can't because this equation is only valid in solids without holes.
I suppose that the way around this is to count the number of edges in the model, is there an efficient way of calculating it???

 

[Simon F]

I think I would have just maintained counts of faces, edges, and vertices at each step and used those to determine how many new vertices etc you will get after a refinement step.

 

[onesvenus]

Well, yes, that's what I wanted to do but how can I count the edges in a mesh? The only way I can think of is this:
- When I read the mesh with every pair of vertices of any face, store them as an edge and for every new pair of vertices, check if that edge was counted before or not.

Is that the good way?

 

[Simon F]

Well, yes, that's what I wanted to do but how can I count the edges in a mesh? The only way I can think of is this:
- When I read the mesh with every pair of vertices of any face, store them as an edge and for every new pair of vertices, check if that edge was counted before or not.

Is that the good way?

Well, it is a way, assuming you don't have a separate list of your edges. I'm guessing that you only have a list of the faces and each face has a list of vertices in some consistent order, e.g clockwise.