Page MenuHome

Subdiv: Incorrect topology comparison, leading to poor performance
Needs Triage, Unbreak Now!PublicBUG

Tokens
"Like" token, awarded by Fracture128."Party Time" token, awarded by candre."Love" token, awarded by bnzs."Love" token, awarded by Alrob."Love" token, awarded by zeddb."Love" token, awarded by 295032."Burninate" token, awarded by Frozen_Death_Knight."Burninate" token, awarded by erickblender."Love" token, awarded by Dangry."Mountain of Wealth" token, awarded by ace_dragon."Love" token, awarded by EAW."Love" token, awarded by fkytt.
Authored By
Sergey Sharybin (sergey)
Mon, May 18, 12:06 PM

Description

System Information
Operating system: Linux-5.6.0-1-amd64-x86_64-with-debian-bullseye-sid 64 Bits
Graphics card: Quadro RTX 6000/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 440.82

Blender Version
Broken: version: 2.90 (sub 2), branch: master (modified), commit date: 2020-05-18 09:05, hash: rBf3edff2d7d60
Worked: Never, not within the current subdivision surface modifier design.

Short description of error

In some models topology is compared incorrectly, leading to very poor performance by inability to re-use cached topology refiner.

The root source of this is coming from vertex sharpness comparison: comparison happens between "requested" sharpness by the user with "refined" by the OpenSubdiv. Thing here is: OpenSubdiv will assign veretx sharpness for loose, corner, and extra-ordinary vertices based on adjacent geometry, making comparison to happen between apples and oranges.

Exact steps for others to reproduce the error

Get file from T75579, open it, start playback. The performance will be very poor.
A bit hard to see whats' going on without debugger attached, but the openSubdiv_topologyRefinerCompareWithConverter() always returns false.

Event Timeline

Sergey Sharybin (sergey) triaged this task as Unbreak Now! priority.
Sergey Sharybin (sergey) created this task.
Sergey Sharybin (sergey) changed the subtype of this task from "Report" to "Bug".

Since this is set to unbreak now priority, assuming it is for 2.83.

@Brecht Van Lommel (brecht) Please talk to me before assuming. There is no safe way of fixing it at this bcon level for 2.83. Is highest priority is because i work on it immediately, and rather have it fixed ASAP to ensure our studio is not bottlenecked and that this bug does not lead to wrong decisions in the animation performance project.

@Brecht Van Lommel (brecht) on a more technical aspect I wouldn't mind having second opinion.

I've committed the fix to opensubdiv_compare branch. Code got a bit too hairy, so refactored it to make ownership more clear. All done in incremental steps, so should be fine. And looking at the final idea should still be clear from the latest snapshot state.

Long story short: keep exact topology provided by the TopologyConverter which is a glue logic for OpenSubdiv's TopologyRefinerFactory. Downside is that it uses more memory (5MiB for 100K faces in base mesh, 90MiB for 1.5M faces in base mesh). Upside is that comparison becomes straightforward and easy.

Before this change I've tried to sue OpenSubdiv's base level, but it turns out to be too tricky because base level is already "refined" (it has creases adjusted to the manifold/corner state of vertex/edge) and it has face-vertices ordered in a manifold manner. This change allows to remove the following fragile and slow aspects of comparison in master:

  • Edge/vertices creases are compared as-is (see the fragile check in master's opensubdiv_topology_refiner.cc:checkSingleEdgeSharpnessMatch).
  • Face-vertices can also be compared as-is (the O(N^2) complexity of master's opensubdiv_topology_refiner.cc:checkVerticesOfFacesMatch is gone).

So in the cost of extra memory we gain faster/robust comparison. Do you think it's acceptable memory footprint increase? Can you think of further memory saving?

I think the memory allocation and pointer per face should be avoided.

Instead have one array with all face-vertex indices, and one array with the offset into that array for each face. The number of vertices of a face can be computed with the difference with the offset of the next face.

For edges it may be possible to store just the edges with non-zero crease values or loose edges, I'm not sure.

Besides that I also don't see a better solution. If we can get the memory usage a bit lower still it seems ok.

I think the memory allocation and pointer per face should be avoided.
Instead have one array with all face-vertex indices, and one array with the offset into that array for each face. The number of vertices of a face can be computed with the difference with the offset of the next face.

Yeah, indeed. I made a mistake in original calculation and this approach didn't show much benefit, but running numbers again seems to give about 30% memory saving for meshes without creases.

For edges it may be possible to store just the edges with non-zero crease values or loose edges, I'm not sure.

There are no loose edges communicated to OpenSubdiv. It can not handle those and hence they are filtered out from Blender side (the filtering could also benefit from some optimization, but that's another story).

Non-zero creases are already avoided. This happens for both vertices and edges. Currently vertex and edge creases are stored as an array of a size of the last index of vertex/edge with crease. Benefit of such storage is that there is O(1) overhead if there are no creases at all and that there is minimal possible overhead when all geometry has crease. The downside is that if there is a single edge with crease and it happened to be the last one (from index point of view) there is no memory saving at all.

Using some tree-like structure would be better approach if there is only few edges with crease. But worst case (all semi-creased) scenario will use twice of required memory needed to store crease.

Are you aware of sparse-array-like structure which is fast and memory friendly for the case when array becomes dense?


Another optimization we should do is to not have edges array if there are no creases.
Unfortunately, we don't always know this in advance (there could be non-nullptr callback to access crease but have o creases set by user). But I think I can re-shuffle some TopologyRefinerFactory code to avoid any extra allocations but also avoid any extra access to callback (which could involve some non-trivial calculations).

@Brecht Van Lommel (brecht) did round of up updates in the branch. Basically implemented your idea of continuous arrays and my note about not storing edges.
If my calculations are correct then the memory consumption on 1.5M faces goes down to 54 MiB if there are no creases, with edge creases it is 78 MiB. With all vertex and edge creases is 96 MiB (original calculation was wrong, so before the change the worst case was 114 MiB).

P.S. Also forgot to mention that in current master comparison step creates EdgeMap, which is rather memory consuming and consists of a lot of allocations. It is not used anymore, so that's an extra performance improvement in the branch.

The code in the branch looks good to me now.

Are you aware of sparse-array-like structure which is fast and memory friendly for the case when array becomes dense?

No, except for switching between two different data structures at some point. But I'm not sure that's worth it here.