Datastructures to represent a polygon mesh (and/or) SDS

This forum is used to discuss the architecture and design of the next JPatch development version (Jpatch 0.7).

Datastructures to represent a polygon mesh (and/or) SDS

Postby sascha » Tue Feb 20, 2007 4:17 pm

I've created this topic to discuss the datastructures used to represent a polygon mesh (and/or) subdivision surface.
The current implementation is (more or less) a Half-Edge structure. It can store the base mesh and vertices on the first subdivision level.
I've not yet decided how to store vertices on deeper subdivision levels (for hierarchical modeling).

I've setup a Wiki page to describe the current implementation. It can be found here: http://wiki.jpatch.com/doku.php?id=dev:halfedge

The code can (currently) by found in the SVN trunk, in package "sds". If you check out the trunk, please excuse the dust - it's full of parially working experiments. I think once I know which way to go I'll move the classes I need into a new project and discard the rest.

The following constraints apply to surfaces represented this way:
1) The surface must be a 2-manifold.
2) The surface must be oriened.
1) means that each edge must be adjacent to at least 1 and at most 2 faces. Topologies where an edge touches three or more faces are not allowed.
It also means that all faces adjacent to a vertex must be connected with edges.
2) means that, when viewed from the outside, the edges of each face must be enumerated in clockwise order, or - in other words - that all the surface normals must point "outwards".

Note that the surface is not required to be a closed polyhedron.


I chose the Half-Edge structure because it's relative simplicity. It's easy to understand and queries and modifications are straightforward. It's not a very performant solution, so a time-critical task like realtime subdivision does not use it (for subdivision). It's merely used to as an internal representation of the mesh.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Tue Feb 20, 2007 6:48 pm

From the end user point of view, I only care about a couple of things:
  • I can created n-sided polygons, instead of being restricted to triangles or quadrilaterals.
  • I can work with unrestricted mesh, instead of surfaces having to be closed, holes not being allowed, and so on.
  • I can import mesh exported from other modelers.
  • I can export models from JPatch, in case I'd like to use them with another tool.
My initial concern was that we'd be locked into manifold surfaces, couldn't have holes in the mesh, be restricted to using quads, and so on. From what you've written, this appears not to be the case, but I don't (currently) understand it well enough to understand it. I'm working on it, though. :D

I found the flipcode tutorial on the half-edge structure very helpful. But I need to work out some structures on paper.

Since your design gets around the limitations of the half-edge structure - I can see edge11 is filled with null pointers - my immediate question is why that limitation is placed on the half-edge structure in the first place? Is there some hidden "gotcha" to that approach? It's just the first question I ask when I think I've got a cool approach: Why aren't other people doing this, too?

The flipcode tutorial mentions the "radial-edge data structure" as an alternative, but I can't seem to find any good tutorials on that.

You mention:
The code that dices (i.e. tesselates) the faces of the subdivision surface requires that each face has exactly four sides. Fortunately, after one level of subdivision, all faces are quadrilaterals...
This is sort of "magic" to me. All n-sided polys will be automatically converted to quads?
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Tue Feb 20, 2007 10:41 pm

My initial concern was that we'd be locked into manifold surfaces, couldn't have holes in the mesh, be restricted to using quads, and so on. From what you've written, this appears not to be the case, but I don't (currently) understand it well enough to understand it. I'm working on it, though.

There's no reason why the Half-Edge structure would restrict faces to quads. The only restrictions are that the surface must be a 2 manifold and must be orientable. It's a result of how an edge is represented: It's split into exactly two half-edges - thus each edge is adjacent to two faces. Since the two halfes of the edge have opposite directions, it's also clear that all faces must have the same orientation. Both limitations are perfectly reasonable because the Catmull Clark algorithm has exactly the same constraints.
Here's an example of two topologies that are not allowed:
Image
The left one shows an edge (red) that's adjectent to three faces, which is not allowed.
The right one shows two neighbor faces, one facing forward, one backward. As you can see, the two half-edges of the common edge would have the same direction, which is also impossible.

Since your design gets around the limitations of the half-edge structure - I can see edge11 is filled with null pointers - my immediate question is why that limitation is placed on the half-edge structure in the first place? Is there some hidden "gotcha" to that approach?

Hmmm... good question. I can't see why it shouldn't work, but admittedly I haven't tried it yet. The original half-edge structure has only pair- and next-edge pointers, my implementation also has a prev-edge. The other limitation is that in the original implementation a vertex can point to any of its edges. In my implementation, if the vertex is on a boundary, the edge it points to has to be choosen with care - it has to be the first edge, otherwise the iterator would not iterate over all edges (that's why the validate() method for Vertices is there). Note that holes in general should work, what is not allowed is something like this:
Image
But you're right, I need to test it with an open polyhedron as soon as possible.
Note that faces need neither to be flat nor concave, but if they are far from being flat or "very" convex, the results of the SDS algorithm might look strange.
This is sort of "magic" to me. All n-sided polys will be automatically converted to quads?

Yes! Check out this page for a description of the Catmull Clark subdivision algorithm. Since each new face-point is connected to all new edge-points (of that face), every new face will be a quadrilateral:
Image
Moreover, two of the four vertices of each new face are guaranteed to be of valence 4 (i.e. are adjacent to 4 edges). After this step, every new vertex is of valence 4. This means that only two of the four courner points of a quadrilateral need special treatment, the rest of the subdivision code in my Dicer class just uses a few array lookups and multiplications (I'll explain the algorithm in detail later).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Wed Feb 21, 2007 12:04 am

Sascha wrote:I can't see why it shouldn't work, but admittedly I haven't tried it yet.
Heh.

With the two illegal topologies, I assume that JPatch will take care of the second case automagically? It's not the sort of thing thing you'd want to expose to a user.

For the first case, I can imagine trying to create it for something like a fin on a rocket or arrow. The issue there (for the end user) is having them understand why what they're trying to do won't work, and offering some sort of workaround.

Have you looked at how Blender has implemented their mesh system? I know that in the last couple of years, it's gone through some serious reworking. I suspect you'll find some interesting information there.

Obviously, you'll want to implement this ASAP, so you can get an idea what sort of pitfalls the design might have.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am