Subdiv: Incorrect topology comparison, leading to poor performance #76855

New Issue

Sergey Sharybin · 2020-05-18T12:06:24+02:00

Sergey Sharybin commented

2020-05-18 12:06:24 +02:00

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: f3edff2d7d
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 #75579, 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.

slow_subdiv.blend

**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: `f3edff2d7d` 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 #75579, 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`. [slow_subdiv.blend](https://archive.blender.org/developer/F8462564/slow_subdiv.blend)

Sergey Sharybin commented

2020-05-18 12:06:24 +02:00

Added subscriber: @Sergey

Sergey Sharybin self-assigned this 2020-05-18 12:06:49 +02:00

Steffen Dünner commented

2020-05-18 18:46:50 +02:00

Added subscriber: @SteffenD

lucas veber commented

2020-05-18 18:57:03 +02:00

Added subscriber: @LucasVeber

Evan Wilson commented

2020-05-18 19:05:35 +02:00

Added subscriber: @EAW

Chris Kohl commented

2020-05-18 23:05:22 +02:00

Added subscriber: @ckohl_art

Sebastian Parborg commented

2020-05-20 14:20:08 +02:00

Added subscriber: @ZedDB

Brecht Van Lommel commented

2020-05-22 17:43:41 +02:00

Added subscriber: @brecht

Brecht Van Lommel commented

2020-05-22 17:43:41 +02:00

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

Bent Hillerkus commented

2020-05-23 23:19:23 +02:00

Added subscriber: @bent

Sergey Sharybin commented

2020-05-25 11:40:12 +02:00

@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.

Sergey Sharybin commented

2020-05-25 15:56:47 +02:00

@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?

@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?

Brecht Van Lommel commented

2020-05-25 19:33:47 +02:00

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. 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.

Sergey Sharybin commented

2020-05-26 08:47:44 +02:00

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).

> 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).

Sergey Sharybin commented

2020-05-26 13:02:20 +02:00

@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.

@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.

Brecht Van Lommel commented

2020-05-26 19:06:10 +02:00

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.

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.

Sergey Sharybin commented

2020-05-27 12:42:21 +02:00

Changed status from 'Needs Triage' to: 'Resolved'

Sergey Sharybin closed this issue

2020-05-27 12:42:21 +02:00

Sergey Sharybin commented

2020-05-27 12:42:21 +02:00

Is solved with latest development. The first commit which fixed the issue is 614d70a87d. There are follow up changes which further improves performance and memory usage.

Is solved with latest development. The first commit which fixed the issue is 614d70a87d. There are follow up changes which further improves performance and memory usage.

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Subdiv: Incorrect topology comparison, leading to poor performance #76855