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

Postby pndragon » Wed Feb 21, 2007 2:23 pm

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.

From an artistic point of view, this would almost certainly not be used for a rocket or an arrow. At least, not as it stands. You would use three rectangular solids, for depth. The problem, in this example, is a non-problem and self-correcting.

--- Jim
"We're so sorry, Uncle Albert,
But we haven't done a bloody thing all day."
--- Paul McCartney
pndragon
 
Posts: 591
Joined: Sun Dec 05, 2004 1:27 am
Location: North Carolina

Postby dcuny » Wed Feb 21, 2007 8:51 pm

pndragon wrote:From an artistic point of view, this would almost certainly not be used for a rocket or an arrow.
I agree. But it's not an unreasonable thing for the user to try. For one of the first animations I did in Blender, I did exactly that, extruding fins from the mesh.

But I'm not defending it as a good thing, I'm just saying that if the UI disallows certain things to happen, it needs to be clear to the user why it's prohibited, or they'll think the program is broken.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Thu Feb 22, 2007 11:34 am

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

Ok, I did try it and it works well - here's the proof :) :
Image

Note that I haven't implemented "interpolate boundary" yet, so the SDS algorithm causes boundary faces to collapse (that's why some faces appear to be missing). This was only intended to test whether my version of Half-Edge structure supports surfaces with boundaries (i.e. non-closed surfaces).

"Interpolate boundary" will treat the boundaries as b-splines (just if they were tagged as "crease", so it requires the crease-tags - I'm working on it.

pndragon wrote:From an artistic point of view, this would almost certainly not be used for a rocket or an arrow. At least, not as it stands. You would use three rectangular solids, for depth. The problem, in this example, is a non-problem and self-correcting.

I agree. The users should think in terms of "solid" objects, not in terms of surfaces. You can have an "open" surface, you can have holes in it, you just can't it connect in the two ways described above.
Since the SDS algorithm can't cope with such topologies, I think it is reasonable to impose the same restrictions on JPatchs internal representation. If you tried to connect a third face to an existing edge, the modeler simply won't let you.

The problem with front- and backfacing polygons is also inherently solved: JPatch must automatically align all new faces. If you try to create a non-orientable surface like a Möbius-Strip or a Klein-Bottle, JPatch will simply refuse to connect the last face.
The workaround is easy: Think in solids. It's no problem to create a solid Möbius Strip (which has a well-defined inside and outside), you just can't create an infinitesimal thin "single surface" Möbius-Strip, since it lacks a well-defined front- and back-side.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Thu Feb 22, 2007 9:08 pm

Excellent! :D

I also agree that the user should "think in solids"; I'm just suggesting the interface give them some sort of cue (color the line segments differently?) to let them know they have an illegal construct. Sort of like the red faces JPatch shows for the face's normals.

I'm looking forward to playing with this!

Will the mesh editor be able to work like it currently does? The reason I got excited about the LionSnake modeler was that it showed you could still do very JPatch-like modelling with SDS. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Thu Feb 22, 2007 9:33 pm

I'm just suggesting the interface give them some sort of cue (color the line segments differently?) to let them know they have an illegal construct.

The thing is that all limitations are also inheritent to how Jpatch internally stores the mesh - so it can never represent an illegal topology. I'd say that it should silently ignore commands that would lead to illegal topologies. Alternatively there could be a kind of learning mode, where it would rise an alert window in such a situation, explaining what's going on (with a "don't show this message again" checkbox).

Will the mesh editor be able to work like it currently does?

From the tutorials I've seen, polygon or SDS modeling is quite different. You have several ways to extrude surfaces, and I think the extrude tool is the most often used one. But of course it could have a mode where you just add edges (like curves in the old JPatch modeler) and connect the vertices just as before. There won't be a face-finder though, so you'd have to manually select edges and tell JPatch to create a face. Alternatively I can add a "mini" face finder that finds all 3- and 4-edge loops in all selected edges and creates faces of them.
But again, most tutorials I've seen start with a cube or another simple object (like a lathed curve) and use extrude or subdivide tools to add more details.
There will also be a more sophisticated lathe tool.

One limitation I forgot to mention comes from the Dicer: It has a maximum valence. The point in the center of the teapots cap is of valence 16, which is the current maximum. It's a hard-coded constant that can be set at compile time - making it higher will consume more memory. It's like with patches, a lathe of 8 segments is usually smooth enough (it's never exactly circular, but you can't see that), so I thought with 16 there's a little safety margin. I can set it to 32 if required though (or make it a user-changeable property).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Thu Feb 22, 2007 11:27 pm

sascha wrote:Alternatively there could be a kind of learning mode, where it would rise an alert window in such a situation, explaining what's going on (with a "don't show this message again" checkbox).
I like this idea. More specifically, I like anything in the UI that alerts the user why something failed, instead of silently failing and having the user be puzzled by the result.

Have you seen how Firefox and IE do alerts on popups? A small status bar appears under the menubar with a message. I like it, because it's not modal, so it doesn't interrupt the workflow, but it's more visible than displaying it on the status bar, which is pretty much invisible. (It also "bumps" down the main window to make room, so that helps its visibility).
From the tutorials I've seen, polygon or SDS modeling is quite different. You have several ways to extrude surfaces, and I think the extrude tool is the most often used one.
I think the term is "box modeling", because you typically start with a box as the base shape. I've used Wings (and before that, Nendo), and it's a nice way to model. Extrude, adjust, split face, repeat.

I agree that it's the preferred way to model with SDS.

But of course it could have a mode where you just add edges (like curves in the old JPatch modeler) and connect the vertices just as before. There won't be a face-finder though, so you'd have to manually select edges and tell JPatch to create a face.
That's why I was pointing to the LionSnake modeler. There's no "finder" involved - you explicitly create one face at a time.

What I like about that way of doing things is that there's no "guessing" involved. Currently in JPatch, you create a mesh, then click the "calculate" button and hope that a face appears. In the LionSnake model, you connect the vertices, and when the last vertex connects to the first, the modeler knows there's supposed to be a face, and tries to build one. If it can't, you can pop a message to the user saying why it failed, and highlight the errant edge. I don't think you can give that kind of interaction with a finder model, so the user has to puzzle out what the problem with the model is himself, with no feedback from the program.

Alternatively I can add a "mini" face finder that finds all 3- and 4-edge loops in all selected edges and creates faces of them.
Why only 3 and 4 edge? Aren't polys with more than four edges allowed? :? (I know you've said they are, I just want to make sure).

It's a hard-coded constant that can be set at compile time - making it higher will consume more memory.
Of course, the first thing I'll ask is that if can be set by the user. ;)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby dcuny » Fri Feb 23, 2007 6:57 am

The point where this is likely to be an issue is when you import models created with other programs. For example, I recall using 32 as a lathe value is fairly typical in Blender.

Since JPatch can adjust to this, I guess part of the question is whether this should be hidden from the user, or if JPatch should silently adjust the maximum value behind the scenes.

For importing an object, you really don't have a choice - the model has already been built, so either JPatch will automatically adjust, or you can't load the model. There seems to be little point in even telling the user about it - why do they care?

On the other hand, if it's going to cause performance problems, you probably would want to issue some "Don't warn me about this again" sort of thing to the user if they select a large value for a Lathe command, so they can be aware of the consequences.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Fri Feb 23, 2007 3:52 pm

The limitation comes from the dicer. So it would be no problem to import or export such a model - it would simply not show surfaces with points of valence > 16 (or whatever).

But: using lathes with 16, 32 or even more segments is very, very counterproductive. This technique was used in polygon-only modelers to make the surfaces appear smooth (a cube doesn't look much like a sphere after all). Patches as well as SDS are smooth per definition, so by all means, keep the patch/face count as low as possible. The final objects will look smoother, too many faces will add undulation (this is also true for SDS - the center of a lated objects with e.g. 16 or more segments doesn't look very smooth). And you keep the modeler responsive. This is not a polygon modeler, and it has to draw 64 quadrilaterals for every face in average. Computing these vertices requires a lot of floating point multiplications. I think my code is quite fast, but still, importing a high-poly object and using it as SDS will almost certainly kill it.

I could use an option that allows to import polygon models and treat them as polygon models. You could still rig and animate them - perhaps even edit them (all but the hierarchy and edge/corner tagging tools should be applicable to any polygon model). This way you could import your favorite polygon models and continue to use them - you could even export them as Catmull-Clark or Loop SDS - but the interactive editor would simply display them as plain old polygon objects, not as SDS.

Why only 3 and 4 edge? Aren't polys with more than four edges allowed?

Yes, they are allowed, but are more tricky to find :)

In the LionSnake model, you connect the vertices, and when the last vertex connects to the first, the modeler knows there's supposed to be a face, and tries to build one.

Wait a minute. What if the user doesn't connect the last vertice to the first one, but to some other vertex? There are potentially hundreds of faces that could be formed using the newly added edges, how could the modeler possibly guess which faces it should create? It could (as an option), automatically look out for 3- or 4-edge loops and make a face if it finds one, but looking for 5-, 6-, 100- edge loops is a) expensive and b) dangerous (see above).

My approach would be:
* The user can either start with some primitive (like a box), or can draw a face. Whenever edges that are not yet connected to any face form a loop, it will create a new face, which can then be used with e.g. the extrude tool.
* Using the extrude tool will always automatically create new faces.
* You can add new edges wherever you want (and connect them to existing vertices), but JPatch won't create any face automatically in this case - you'd have to select the edge loop and create the face manually. I'd even use separate classes to represent such "pseudo edges" - vertices could be "points" and the edges could be "wires". When you make a new face (and the topology allows it), they are converted to real vertices and edges.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Fri Feb 23, 2007 7:19 pm

sascha wrote:Wait a minute. What if the user doesn't connect the last vertice to the first one, but to some other vertex? There are potentially hundreds of faces that could be formed using the newly added edges, how could the modeler possibly guess which faces it should create?
No, no, no.

No. :)

Trace out one face, get one face. Take another look at LionSnake. If you trace out an edge and don't connect it back, you only get an edge. You don't get a face until you do a full circuit.

That's a big part of the appeal of the design for me: there's no "guessing" on the part of JPatch. You could still have a finder, but the basic behavior would be building faces one at a time.

That's why you've got better user feedback - if there's something illegal with that face, you can immediately tell the user. It makes it easy to create n sided faces, too. Again, you don't have to "find" them - if the user makes a circuit of 33 sides, they want a 33 sided polygon.

It sounds like your last bullet point.
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Fri Feb 23, 2007 8:14 pm

Ok, I see.
It sounds like your last bullet point

No, actually that's what I meant with the first one:
Whenever edges that are not yet connected to any face form a loop, it will create a new face, which can then be used with e.g. the extrude tool


Another possiblity would be to add just edges (without a loop) and then use extrude (or lathe) to create the faces.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Fri Feb 23, 2007 9:08 pm

sascha wrote:Another possiblity would be to add just edges (without a loop) and then use extrude (or lathe) to create the faces.
That's exactly the workaround I was thinking about. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Next

Return to JPatch 0.7 development

Who is online

Users browsing this forum: No registered users and 1 guest

cron