BiLinear Uniform Subdivision - Consistent Behaviour Query

[adam-hartshorne]

If a take a simple quad mesh (call it BaseMesh) and apply an uniform bilinear subdivision of 2 levels and read out the resultant mesh (MeshSub1).

Now if I was to take the same Base Mesh and apply 4 levels of uniform bilinear subdivision and for MeshSub1 apply 2 levels of the same subdivision scheme. I would presume that the resultant meshes would be identical in terms of structure and vert / face numbering, because at level 2 of the BaseMeshes subdivision the structure (by this I mean face / vert numbering) is identical to MeshSub1.

What I have found is that there are a small differences in the resultant vert / face numbering. Is this correct behaviour?

[barfowl]

Just as a quick side note... The behavior here for Bilinear should be the same for Catmark since they both share the same quad-splitting operation that defines their resulting topology. So this behavior is more widely present with the Catmark scheme.

I will say the behavior of uniform subdivision is "correct" if each of the independently subdivided results is correct. There are no guarantees that the identical topological correspondence that you seek will be achieved.

Here's my best guess as to why the two results do not correspond as expected...

I'm assuming here that faces are generated in the same order, but the ordering of resulting vertices differs -- leading to the differing face / vert numbering that you observe.

When vertices are subdivided, for a variety of reasons, the vertices that result are ordered into three groups depending on how the vertices are derived. These three groups are: vertices originating from faces, vertices originating from vertices, and vertices originating from edges. Within each of these groups, the vertices will be ordered corresponding to the order of the faces, vertices or edges from which they originate in the previous level.

The ordering of vertices and faces is clearly defined in a base mesh, so we should expect the ordering of these two groups of vertices in the subdivided level to correspond, but the ordering of edges is not. In fact, unless you have used your own explicit edge list to construct the TopologyRefiner with a custom factory for your mesh class, the ordering of the constructed edge list is essentially undefined.

When applying uniform subdivision, the edge list in a subdivided level is not determined in the same way as it is for the base mesh. A subdivided edge list is much more efficiently determined from the edge list in the previous level, rather than being assembled to match the same construction technique used by the base mesh. So if you stop at level 2, discard the subdivided edge list and create a new base mesh from level 2, the ordering of subsequently subdivided vertices originating from edges is going to differ from the result of continuing to subdivide.

It is potentially possible to achieve the correspondence you desire if you retain an explicit edge list with your mesh representation and translate that to/from the TopologyRefiner. But as soon as you discard that edge list (e.g. by exporting and re-importing that level 2 mesh in a common format that does not support an explicit edge list), that correspondence will be lost.

[adam-hartshorne]

Thanks for the response / explanation.

What I have actually ended up doing to solve this problem is slightly forked my copy of the library, changing the getLevel method in the TopologyRefiner to public, added a few extra simple methods to handle things like the depth needing to be changed and then added a new TopologyRefiner constructor that takes an Internal::Level.

This appears to have done the trick.

I wonder it this functionality might be a good addition to the library in general? I can see a number of reasons why you might want to do this.

[barfowl]

Yes, that's a possibility -- and we are just finalizing the API changes for 3.4 so now would be a good time for late additions or it will be a while before a next minor version. We did add a new TopologyRefiner "constructor" to the Factory (not a true constructor) that shares a base level with a given Refiner, and another to construct from a specific level seems reasonable. It is unfortunate to have to duplicate the entire level-2 mesh though.

Would being able to add and remove refinement levels more dynamically also help address your problem, i.e. you could refine to level 2 for some purpose, then refine to level 4 for more detail temporarily and "unrefine" back to level 2? The levels were designed to be sliced away and there has been some interest in refining a level at a time, but we've never really exploited that.

[adam-hartshorne]

My particular use of OpenSubdiv is rather niche. And at the moment, I am looking at subdividing a mesh, and then extract out different "sub-ranges" of levels, which I then perform other operations (including further subdivision) on each of these individual extracted elements separately.

Therefore, the "unrefine" back to level x, would achieve what I need, but wouldn't be very efficient as I would have to create make multiple copies, which I unrefine back to different levels.

However, I appreciate that my needs are not exactly the mainstream of required functionality. At this stage, I can't say too much more on a public forum.

[barfowl]

Too bad about the copies associated with possible unrefining to a specific level (though aren't you creating copies of levels with your current solution?).

Back to your question about potentially adding the new constructor to create a base level from a given level... while I was initially optimistic about the idea, I have more reservations after looking into it further. It may be working fine for you in the case of uniform refinement, but it definitely cannot be applied to a level that was adaptively refined without more work and complication that will impact usage. The fact that its not as generally useful as desired is a bit of a deterrent.

It is still possible to publish a solution that is specific to uniform subdivision. Rather than a constructor added to the TopologyRefiner, the library convention is to create instances of these objects with their Factory classes, so we could add a new factory method there, e.g. CreateFromUniformLevel(...) to make it clear. But usage would probably be pretty limited and there are other ways of accomplishing it with the existing interface, which is why I'd prefer to find an alternate solution that provides something more if possible.

[adam-hartshorne]

I am creating copies, but I take a layers out, process and refine. So I only ever have to create one copy that contains a subdivision down to a max level.

The unrefine back to level x, I would be having to create copies that are all max level, then unrefine each back to the level I require. That's not the end of the world for me, especially as I am acutely aware the way in which I am utilizing OpenSubdiv is in a manner that is not its intended purpose. Having a properly implemented unrefineToLevelX functionality is going to better than my current hack.

I thought it might well be a lot more problematic for adaptive subdivision. Again for my very niche requirement, I am only extracting layers for a uniform subdivision.

[jtran56]

Filed as internal issue #OSD-255.

[barfowl]

Rather than us adding new constructors, I'm leaning in the direction of using the existing API and writing a TopologyRefinerFactory that builds a TopologyRefiner from an existing TopologyLevel. It can use the edge list from the TopologyLevel (and everything else available to it) so it should provide the desired topological consistency while still being reasonably efficient given the way the topology vectors will be allocated and populated by this factory. It will also ensure the base level tags are all initialized as expected for a base level.

This is something you can use for any 3.x version while we decide if its something we want to add in future. If you'd rather use this than a custom fork of the library, let me know and I can provide something on a branch for you -- I have a similar factory that preserves the edge list elsewhere that would just need minor changes. Come to think of it, I could provide it as another tutorial example for writing the factories.

[adam-hartshorne]

Yes, that would be great.

[adam-hartshorne]

Just wondering if there is any update on this idea?

[barfowl]

Not really. I have some work in progress that got put aside as we started putting more effort into the upcoming 3.4 release, which is the current priority. I'll try to pick that up again soon. I just see now that its been 4 months since my last post -- that's plenty of time to have finished this, so sorry for not getting back to you sooner.

[adam-hartshorne]

No apology needed. Thank you for the update.

[barfowl]

I've run into some unexpected problems preparing the code I had wanted for a tutorial, so I'm going to make it available on a branch of my fork until I figure out what to do.

Have a look at my branch far_tutorial_3_2 -- specifically the customRefinerFactory.* files in the single commit, which should encapsulate what you need.

The complications in adding this to the repository have to do with the way that documentation for the tutorials is tied to their source: the docs really want the source in a single, specifically named file, while the code for a custom factory really warrants a separate header and source file. There's also more overlap with this example and the existing far/tutorial_3_1 than I was expecting. I may eventually end up using this code to revise that tutorial instead of creating a new one. And I may deal with limitations of the documentation -- not sure yet. Regardless, I'll be putting this off for a while.

So let me know if the TopologyRefinerFactory in the branch meets your needs. It shouldn't depend on any new features and so should work with any 3.x version of OpenSubdiv. Aside from the definition of the factory, the main tutorial code really just validates the factory by comparing the results of uniform refinement to continued refinement from a particular level to make sure they match.

[adam-hartshorne]

Thanks for the update.

I am currently bogged down with something, so it might take me a week or two before I get to this. I will reply again when I have had chance to have a look.