Hierarchical modeling

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

Hierarchical modeling

Postby sascha » Wed Feb 21, 2007 11:41 am

One of the things that directly affect the user experience is how to implement hierarchical modeling:

Normally you work directly on the base mesh. There are four basic operations that can be performed:
1. Changing the topology by adding or removing faces, edges or vertices (using various tools, including extrude and lathe)
2. Moving vertices (using various tools including scale, move and rotate)
3. Setting "tags". Vertices can be tagged as corners, and edges can be tagges as crease. This will change how the subdivision algorithm will treat these points. An optional integer parameter can be used to create semi-smooth corners or creases - it would tell the subdivision code to e.g. treat the point as a corner for the first 3 levels of subdivision, and as a regular point afterwards - creating a smoothed corner.
4. Assigning materials to individual faces.

Hierarchical modeling allows to manipulate vertices at higher subdivision levels. It's clear that you can't change the topology at a higher level, so (1) won't be possible in this mode.
But what about (2), (3) and (4)?
(2) is certainly a requirement, if you can't move vertices on higher levels hierarchical modeling wouldn't make much sense.
So what about (3) - should it be possible to change corner/crease flags at higher levels? I think yes - one application would be modeling a hand - you could start with a coarse base mesh, and then model joints and nails at higher levels. For the nails you might need crease edges.
What about (4) - should it be possible to change the material for individual (sub)faces at higher subdiv-levels? I think yes too - for the same reason as above. In the hand example, you might want to use a separate material for the nails.

As described earlier, vertices at level2 (after 1 level of subdivision) are already part of my Half-Edge structure, since the "Dicer" expects quadrilaterals. So it's trivial to show level2-vertices in the GUI and let the user manipulate them.
The dicer itself is able to override vertex-positions and crease/corner tags at each level of subdivision, so it's well prepared for rendering hierarchical SDS.

But I haven't yet decided how to store this information in the mesh itself, and before I can decide that I need to know how hierarchical modeling will work from a user perspective:

There are many things that need to be defined:
1. It should be possible to manipulate just a few points on a given subdivision level, the rest of the points will use the standard subdivision rules.
2. It should be possible to "override" either the position or the crease/corner tags of a higher-level point, or both. Do you think that this is important?
3. There must be a way to display higher-level points. Those with overriden values should be displayed with a different color.
4. Using "delete" on a higher-level point will reset it to it's default (subdivision) position and crease/corner level. (Is this a good idea?)
5. In "hierarchy mode", all higher-level points (of the current level) should be displayed - no matter if they are overridden or not. But even a simple object will have tens of thousands of vertices at level 4 or 5, I think this will kill the GUI. There needs to be a way to e.g. only show level-4 points of selected base faces. Does this sound reasonable?
6. In "non hierarchy" mode, overriden points at higher levels must be "first class citizens" - they can be bound to bones and can be used in morphs, so they should also be displayed (perhaps in a different color than the top-level vertices.
7. Deleting a face will discard all hierarchy information bound to that face.
8. Moving a top-level vertex will not affect points at higher levels with overridden positions.

What do you think?

My ideas for implementation are:

Each face has an array of points and an array of integers (for crease/corner tags) for each subdivision level.
If no hierarchy data is present at a given level, the array-reference is set to null to save memory. The face also knows its maximum hierarchy level (the highest level where points have been manipulated).
When a point on a hierarchy level is manipulated, the array is created if necessary and each element is set to null. The points that have been moved will be set to new position values.
The only drawback of this method is that if e.g. a single point on level 5 was moved, the face stores a 17x17 array of "nulls".
If changin the material should be possible at higher levels too, arrays for materials are also needed.

Do you have another idea?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Wed Feb 21, 2007 9:04 pm

sascha wrote:Hierarchical modeling allows to manipulate vertices at higher subdivision levels. It's clear that you can't change the topology at a higher level, so (1) won't be possible in this mode.
Have you seen the latest Blender release? You can do just that with their multi-res mesh:
    Multires meshes store multiple levels of subdivision. In contrast to the Subsurf modifier, any level of subdivision can be edited. These changes are then propagated to all the other subdivision levels.
Image
(I'll answer the other questions when I get a chance to read them in more detail.)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Wed Feb 21, 2007 9:46 pm

Oh, I didn't realize that Blender had that option.
I think I've got to play with hierarchical SDS models in Blener and in Maya before deciding on how to implement it.
If the Blender folks do all the cool stuff, why am I working on JPatch then? :?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Wed Feb 21, 2007 11:49 pm

sascha wrote:If the Blender folks do all the cool stuff, why am I working on JPatch then? :?
Sorry, I wasn't complaining. Really. :oops:

I assume that what you want out of JPatch is the same thing that I do: a fun way to do computer animation.

Blender doesn't give me that. Let's review:
  • I want to be able to model a character. JPatch's modeler is simple to use. For me, Blender's modeler isn't.
  • I want to be able to rig a character. JPatch's bones mode is dead simple to use. I can't even figure out Blender's. When I "parent" a bone, am is the child being attached to the parent, or a parent being assigned to a child? Don't even get me started.
  • I want to be able to animate a character. Blender's got a gazillion confusing modes. I can't even figure out where to begin. JPatch has no modes.
There's simply no comparison.

It's not about having more features - it's about picking the right features, and doing them right. There's no other free program out there that's really gotten as much of it right as JPatch has. Not Blender, not Art of Illusion, not LionSnake... Nobody.

I don't really care about doing a lot of "cool" stuff, and that includes editing a mesh at multiple hierarchies. I only mentioned it because you said it "couldn't be done", and I had just been reading the latest Blender release notes. I'm not asking for the feature. I doubt I'd even use it. Even the hair and cloth I've been fiddling with aren't on my "important features" list - they're probably more hassle than they're worth.

JPatch is the only computer animation program out there that's got me excited. I really want to see it finished, because (based on what you've already done) it's going to really rock.

Did that answer the question? :P
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Thu Feb 22, 2007 10:10 am

Sorry, I wasn't complaining. Really.
I wasn't complaining either. It's just my quarterly identity crisis :wink:
Sometimes I think, with the time constraints given, how JPatch should ever become a competitive animation tool (compared to other free tools).
I don't really care about doing a lot of "cool" stuff, and that includes editing a mesh at multiple hierarchies.
I tend to agree, but I also fear that if the system doesn't support it from the beginning, another rewrite is inevitable.
Did that answer the question?
Yes :)
Thanks for the optimism!
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby sascha » Thu Feb 22, 2007 10:56 am

I took another look at the description of Blenders "multi-res" mesh, and it's not quite the same. They simply store the entire mesh at different levles, an propagate changes made on lower levels to the higher levels.

JPatch, on the other hand, will store higher-level vertices only if they have been modifier. JPatch also uses adaptive subdivision for the inertactive rendering - so when zooming in and out the subdivision level does adapt automatically.

I admit that I like the idea of propagating changes from lower levels to higher levels though, I'll have to look into this.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Hierarchical modeling

Postby dcuny » Fri Feb 23, 2007 7:25 am

Sascha wrote:Hierarchical modeling allows to manipulate vertices at higher subdivision levels.

It's been a while since I've edited an SDS, but I don't recall ever being able to manipulate anything other than the "base" mesh.

My feeling (and understanding) is that there should only be one level to the mesh. If you want a fingernail to have more resolution, subdivide the mesh only at that location. Isn't one of the features of SDS to be able to locally increase the resolution of the mesh?

Here's an image I stole from the LionSnake modeler; The display shows two things: the base mesh, and the subdivided mesh. There's no other "level" that can be selected:
Image


Here's another example from another site:
Image
Image

And from a tutorial on another site:
Image
Image

In all these examples, there's only a single "level" of editable mesh.

Even if you could create multiple levels, I'm not sure it's a good idea. As you've hinted, it raises a lot of implementation questions, and could quickly eat up your computer's memory.

So I guess my idea is: don't implement subdivision levels, they aren't needed. The function of the subdivision level is to control the "smoothness" of the output, not to create editable levels. (Despite what you can do in Blender).

Perhaps you could offer a good counterexample to show what you want? (Preferably with graphics!)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

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

If you want a fingernail to have more resolution, subdivide the mesh only at that location. Isn't one of the features of SDS to be able to locally increase the resolution of the mesh?

Well, not really. Of course you could just subdivide parts of the mesh, but then the modeler has to reconnect the high-details part with the low-details part. Practically this will introduce a lot of 5-sided faces, although both, base- and detailed- meshes are made of quadrilaterals only:
Image
The 5-sided faces would still connect smoothly, but just not as perfect as with the hierarchy. This is comparable to patch modeling: you could connect a high-detail region (made of 4-point patches) to a low-detail region using five-point patches (just like in the upper right image above), but the better solution is to use hooks (just like in the lower right image above).

Perhaps you could offer a good counterexample to show what you want? (Preferably with graphics!)

But of course! :D
Check out this tutorial: http://plissken.fatalunity.com/tutorials/subdiv/
It's about modeling an SDS hand in Maya. Here are some images:
They start with a very coarse box model:
ImageImage
And extrude the thumb:
ImageImage
Then they convert the polygon-mode into an SDS:
ImageImage
The interesting thing here is that the SDS has twice the resolution of the base polygon-mesh. Perhaps Maya doesn't like non-quadrilaterals, so it performs one level of subdivision first. But can the base (poly) mesh be changed afterwards? Maybe a Maya user can shed some light on this.
Anyway, they continue to model the nails on level 2 and 3:
ImageImageImage
After adjusting some other points on level 2 and 3, the index finger looks like this:
Image
The whole process looks very intuitive to me, and I think that modeling such a detailed hand would be much more complicated using patches.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

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

I guess the only question I've got is why you need multiple levels? That is, if you wanted the mesh to be higher resolution at one point, why not select that portion and subdivide it into a finer mesh?

You're right about it being an easy way to model though - you can quickly crank out a model with this process. Creating a model that animates well, on the other hand, requires a bit more work. But (almost as importantly) box modeling is a lot of fun, and that's a big bonus. :)
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Fri Feb 23, 2007 9:36 pm

I guess the only question I've got is why you need multiple levels? That is, if you wanted the mesh to be higher resolution at one point, why not select that portion and subdivide it into a finer mesh?

But that's exactly what hierarchical modeling does. You can't just subdivide a portion of the model. Without hierarchies you can only subdivide the entire mesh. If you'd disconnect a part of the model, then subdivide it, and then reconnect it to the rest (of course this could be automated), you'd end up with the 5-sided faces in the first image above, which works, but isn't optimal.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Postby dcuny » Sat Feb 24, 2007 6:34 am

OK, I understand. I had been under the impression that you could actually subdivide a face, and keep the resolution of the remainder of the mesh at the same level. :roll:

Sascha wrote:The only drawback of this method is that if e.g. a single point on level 5 was moved, the face stores a 17x17 array of "nulls".
It sounds like one of those memory vs. speed tradeoffs. You could set up a variable size array, and use a bitmask at the front to indicate which vertices were stored.

I hate stuff like that, because it's always a pain to support and expand. :?

Perhaps a list of pairs (point id/point value) instead of a full array would be a better idea?
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Postby sascha » Sat Feb 24, 2007 10:15 am

It sounds like one of those memory vs. speed tradeoffs. You could set up a variable size array, and use a bitmask at the front to indicate which vertices were stored.
I hate stuff like that, because it's always a pain to support and expand.

Yes, I guess it would be quite slow, and performance really is an issue here.

Perhaps a list of pairs (point id/point value) instead of a full array would be a better idea?

I like that idea. I think memory wise the two solutions (arrays with possibly lots of nulls and a point-index/value list) are comparable - if just a few points on a level were moved, the list is better, if all points of a level were manipulated, the array is better.
Since this is a performance critical part (I need to update the geometry and the stencil arrays of the Dicer with this information during the dicing-process) I think I'll test which one is faster and go with it. But I could imagine that the list method is actually faster because it doen't need the if (pointArray[index] != null) { ... } in the main loop, and if the list is sorted, looping over it should be quite cache friendly too.
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Hierarchical modeling

Postby sascha » Sat Nov 08, 2008 10:24 am

I think I'll change the way how hierarchical modeling is done once more. Right now you'll have to set a maximum subdivision level for the entire model and can then move vertices on all levels. While this works fine for simple models, it will lead to problems with complex models. You might end up with a base model with 1000 or more faces, yet want to edit fine details on e.g. level 2 or 3 (e.g. finger nails). This would mean that JPatch might have to deal with 100,000 level 3 faces although you'll only edit a few of them - JPatch can handle that, but it will make the UI unnecessarily slow and unresponsive.

My idea now is to not set the max-subdiv-level for the entire model, but let the user "refine" individual parts of the model. For example, on the same 1000 faces model, you might want to edit some details on the hands and fingers. You could select the hand, click on "refine", and it would create the level-1 hierarchy - but just for that hand. Later you could select e.g. the fingertips and click on refine again, which would create the level-2 hierarchy (but only for the fingertips), so you could edit details like finger-nails.

As everything is evaluated lazily, all surrounding high-level vertices that need to be created would be created automatically. You could even delete unneeded hierarchy vertices later (e.g. high-level vertices that have not been edited and are not needed to support edited vertices).

The only tricky part is rendering such a multi-layer mesh, i.e. to seamlessly connect low-level faces with surrounding high-level faces. But it should be doable, and in a first version I could simply ignore it (you'd see cracks where a low-level and a high-level face meet, but I think one could live with that, at least for now).

What do you think?
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Re: Hierarchical modeling

Postby dcuny » Sat Nov 08, 2008 12:04 pm

That's a tough one... less memory intensive, faster response time, and no foreseeable downside... What's not to like? ;)

(Well, there is more coding complexity for you).
dcuny
 
Posts: 2902
Joined: Fri May 21, 2004 6:07 am

Re: Hierarchical modeling

Postby sascha » Sat Nov 08, 2008 1:00 pm

Well, actually it even simplifies a few things, like undo/redo. Until now I thought how I could keep modifications of high-level vertices consistent with undo/redo when the actual vertex has been deleted (due to the user switching max-level e.g. from 3 to 2). Correctly recreating the state of such a vertex can be tricky, it depends on seemingly unimportant things like the order of edges, which is difficult to recreate. This new option enables me to simply keep the vertices in memory - as I don't need the full hierarchy, but only the parts the user selected for "refinement".

The only difficult thing is to modify the rendering code to correctly stitch low-level faces adjacent high-level faces, but there's no hurry, and I think people will forgive a few cracks in the realtime-renderings in a first version, especially if that means an earlier release-date ;-) (photorealistic renderings will have watertight surfaces of course).
sascha
Site Admin
 
Posts: 2792
Joined: Thu May 20, 2004 9:16 am
Location: Austria

Next

Return to JPatch 0.7 development

Who is online

Users browsing this forum: No registered users and 1 guest

cron