.obj Mesh to Half-Edge Data Structure

Ideas, enhancements, feature requests and development related discussion.

.obj Mesh to Half-Edge Data Structure

Postby dcuny » Thu May 20, 2010 6:51 pm

I've posted elsewhere that I'm starting to get the bug to rewrite my Reyes renderer. One of the places where I really fell down was handling subdivision surfaces. My implementation was really, really slow. That's especially bad, since it was coupled to a really, really slow renderer. ;)

So I've started re-reading about SDS, and I think I've finally gotten a better grasp on how the JPatch SDS tesselator works.

Since one of my motivations for writing code is to understand how things work, I tend to write stuff from scratch. This is a Bad Thing (tm) is a lot of ways, and I'd like to avoid it this time around. I think I've got enough comfort with how the code works that I'd be able to integrate the tesselator without having to write it myself. 8)

But before I can use it, I have to rewrite another part of the code - the .obj file importer. The SDS code I'd written before was pretty stupid about doing things, and I really should do things right this time. Specifically, I need to be able to convert an .obj mesh into a half-edge data structure.

What's the best way to do this? Google brought up this post:
Reedbeta wrote:I think the most straightforward way is to loop through all the faces, generate each edge for each face, then merge data from pairs of edges with the same vertices. The merging step can be done by sorting the list by vertex indices, which will place edges to be merged adjacent to each other, and then doing a single pass through the list to execute the merge. Or, you can store the edges in a hash table where the hash is computed based on the vertex indices, and do the merging at the same time as edges are added to the table.

Once I've got the mesh converted, I need to walk through it and decide what can be added to the rendering queue as a beizer patch (anything with a regular valence) and what should be added as an SDS patch.

One additional complication: each SDS patch needs to be diced to micropolygon resolution - typically less than a pixel. So there's a chance that an SDS patch might have to be split again before it can be rendered. Is it fairly straight forward to read the geometry back out of the tesselator? Most of that geometry will end up being beizer patches.

Any thoughts? I really haven't looked at this in depth yet.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: .obj Mesh to Half-Edge Data Structure

Postby John VanSickle » Sat May 29, 2010 3:27 pm

dcuny wrote:But before I can use it, I have to rewrite another part of the code - the .obj file importer. The SDS code I'd written before was pretty stupid about doing things, and I really should do things right this time. Specifically, I need to be able to convert an .obj mesh into a half-edge data structure.

What's the best way to do this? Google brought up this post:
Reedbeta wrote:I think the most straightforward way is to loop through all the faces, generate each edge for each face, then merge data from pairs of edges with the same vertices. The merging step can be done by sorting the list by vertex indices, which will place edges to be merged adjacent to each other, and then doing a single pass through the list to execute the merge. Or, you can store the edges in a hash table where the hash is computed based on the vertex indices, and do the merging at the same time as edges are added to the table.

Or you can attach a list of edges to each vertex, with each list containing the edges that start or end at that vertex. Then step through the vertices and you should find the matching edges very quickly, since each list should be very short.
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: .obj Mesh to Half-Edge Data Structure

Postby dcuny » Sat May 29, 2010 4:08 pm

Ah, I'd forgotten that the .obj format already does that for you. I could probably use same indexes that the file format uses, too.

Thanks! :D
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: .obj Mesh to Half-Edge Data Structure

Postby sascha » Thu Jun 03, 2010 9:18 am

So there's a chance that an SDS patch might have to be split again before it can be rendered.

I haven't looked into this for a long time, so there's a good chance that I'm talking a lot on nonsense here :)
Anyway, I'll give it a shot:

One disadvantage of SDS is that you can't split it like a Bezier patch (in u- OR v- direction, thus creating two new patches), you can only subdivide it (i.e. split it in both directions at the same time, creating 4 new faces).

So my approach would be:
* subdivide one time (to ensure that there are only 4-sided faces)
* treat all faces with valence-4 vertices as Bezier-patches and add them to the render-queue, split as necessary, then dice
* treat the rest as SDS "patches", subdivide as necessary, then dice
* You'll somehow need to ensure that adjacent patches (Bezier and SDS) get diced to the same level, or otherwise "stitch" the boundary edge to make it waterproof.

Point 4 is the tricky part.

My implementation does not use the Bezier-patch step, which also makes point 4 a lot easier. The only thing you lose is the ability to split in either u- or v- direction, which (depending on the geometry and the camera angle) can lead to bad performance, but I wouldn't worry too much about that.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: .obj Mesh to Half-Edge Data Structure

Postby dcuny » Thu Jun 03, 2010 4:46 pm

I've been struggling with the problem of not being able to split the geometry.

If I'm not using buckets, it's not a huge problem - I can dice the patch and be done with it. But if I've split the scene using fairly small buckets, that means that the grids are likely to bound a lot of buckets, and that's a lot of geometry to be hanging around. :(

So some sort of geometric solution is preferable. There are two leading contenders: Approximate Catmull-Clark (ACC) surfaces, and c-patches.

The ACC approach creates bicubic patches, and then creates another set of patches to approximate the surface normals. The math is a bit hairy for me, but I'm working through it. This is a favored approach by many, including Valve and ILM. There are variants which allow for sharp creases as well.

The c-patch approach is newer, and creates a new structure which on the edges is a bezier patch, but internally better approximates Catmull-Clark. This approach looks interesting, because it generates "true" normals along with the surface, and can be extended to handle patches other than quads.

I'm a bit fuzzy on how to implement both of them. I'm slow when it comes to math, which doesn't help. :(

With ACC, I'm, not sure how to specify the weights, especially at extraordinary vertices. John's done this before, so I'm hoping he can clue me in. (For the moment, I'm ignoring surface normals).

I'm also a bit fuzzy on how the surface of the c-patch is supposed to be evaluated. I've read the paper a couple of times, and they show a recursive approach of some type. Again, if someone has a clue here, it would be helpful. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: .obj Mesh to Half-Edge Data Structure

Postby John VanSickle » Fri Jun 04, 2010 1:55 pm

dcuny wrote:With ACC, I'm, not sure how to specify the weights, especially at extraordinary vertices. John's done this before, so I'm hoping he can clue me in. (For the moment, I'm ignoring surface normals).

Well, I just do what the paper says on page 5 :).

To recapitulate, you render the final surface for each quadrilateral face using a bicubic Bezier patch. The four interior control points (b11, b12, b21, and b22) are derived from the four vertices of the face. The vertex nearest the control point is weighted by its valence (4 for regular patches), the two vertices adjacent to this are weighted by 2, and the opposing vertex is weighted by one.

There are two control points for each edge, making for a total of eight control points for each patch (they are shared across borders) They are numbered b01, b02, b10, b20, b13, b23, b31 and b32 in the figure on page 4. For smooth edges the simplest thing to do is to average the interior control points on either side of the edge, one from each patch. (This works out to the same calculation as the mask shown in the middle diagrams of pages 5 and 6. For crease or border edges, the control point is equal to 2/3 of the nearer vertex on that edge, plus 1/3 of the farther vertex.

The control points at the corners of the patch (b00, b03, b30, and b33) are easy to calculate. If the vertex is a corner vertex (that is, three or more sharp edges meet there), use the original vertex. If the vertex is a crease vertex (two sharp or two border edges meet there), average the nearer control points of the two sharp/border edges that meet there. If the vertex is a dart (one sharp edge) or smooth (no sharp edges), then you can either average the nearest interior control points of the patches that meet there, or average the nearer control points of the edges that meet there (do whichever is easiest to code, the results are equal).

Feeding the resulting patches to OpenGL results in patches that are smooth except along the edges that lead to extraordinary vertices (valence != 4). If both ends of an edge have a valence of 4, the edge is perfectly smooth. If one end is valence 4, but the other is valence !=4, the edge will appear slightly sharp at the valence!=4 vertex, but fade to smooth at the valence=4 vertex.

The paper says to subdivide twice so that each face has no more than one extraordinary vertex, but I only subdivided once for my modeler and the creasing is not a problem for me. For other users I might go ahead and implement as directed, since they may not want to be distracted by edges that look sharp but aren't supposed to be.

I'm also a bit fuzzy on how the surface of the c-patch is supposed to be evaluated. I've read the paper a couple of times, and they show a recursive approach of some type. Again, if someone has a clue here, it would be helpful. :)

I'll have a look at the paper in the hope that c-patches are piecewise and don't use too many control points (the latter criterion is a shortcoming of s-patches).
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: .obj Mesh to Half-Edge Data Structure

Postby John VanSickle » Sat Jun 05, 2010 11:16 pm

I looked at the c-patches, and am decided that it's all rather complex for a simple modeling preview. The only advantage I see is that there is no need for faking a set of normals for the patches, but since I'm already not faking a set of normals, there's no gain for me.

As far as rendering the c-patch goes, apparently the renderer simply iterates (u,v) coordinates in a grid over the patch, and these coordinates are fed to some formula that I presume is hiding in the paper somewhere, but without a flag of some sort so that those of us who do not hold math degrees can see it for what it is.

I am wondering if the ring of quads around an extraordinary vertex can be converted into an s patch that mimics with sufficient accuracy the limit surface of a C-C SDS. Subdividing twice, to ensure that all of the extraordinary vertices have nothing but ordeinary vertices for neightbors, is probably an essential step to keep this as simple as possible. And of course, sharp edges complicate things even further...
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am


Return to Development

Who is online

Users browsing this forum: No registered users and 1 guest

cron