Dyntopo Improvements In Sculpt-Dev #82121

New Issue

Joseph Eagar · 2020-10-27T03:50:09+01:00

Joseph Eagar commented

2020-10-27 03:50:09 +01:00

I've been working on improving DynTopo performance and fixing some editmode multires reprojection issues. I've now merged both sets of changes into temp_multires_bmesh. I initially wrote a special-purpose triangle mesh library to replace bmesh in DynTopo but ultimately decided to abandon it. In many ways DynTopo already is a special-purpose triangle mesh library that happens to reuse the BMesh data structures, and while I think a special-purpose library would be a good idea in terms of code maintainability it would also preclude us from ever adding support for quads and/or ngons to DynTopo.

Performance Fixes

Speedups When Topologizer Isn't Running

I discovered that even without the topologizer DynTopo was quite slow. I sped it up in several ways, listed below.

Increased pbvh->leaf_limit from 100 to 3000

This sped things up quite a bit.

Wrote a wrapper around GSet that stores elements in pointer arrays for faster iteration.

Profiling revealed that iterating over GSets (specifically PBVHNode->bm_unique_verts and bm_other_verts) was a significant performance loss. I initially solved the problem by inlining all of GHash, but I figured that wasn't appropriate and might have unexpected consequences elsewhere. My solution was to write a wrapper that maintains a flat pointer array for fast iteration (which is done via macro inlining instead of function calls). Note that this wrapper is still not indexable, when elements are removed from the set their entries in the flat pointer array is simply set to NULL. Note however that the array is compacted when it is resized.

Refactored sculpt vertex "indices" into vertex references (SculptVertRef) and indices.

Profiling revealed a large amount of time was being spent maining BMesh element arrays. By creating an abstract SculptVertRef type and storing a pointer to a BMVert inside of it (instead of an index) I was able to drastically cut down the calls to BM_elem_table_ensure. SculptVertRef and indices can be converted to/from each other:

SculptVertRef *vertex = BKE_pbvh_table_index_to_vertex(pbvh, index);
int index = BKE_pbvh_vertex_index_to_table(pbvh, vertex);

PBVHVertexIter and SculptNeighborIterator now have .vertex members that refer to the currently active SculptVertRef, as well as .index.

For meshes and grid PBVHs these store the same values, but BMesh puts a pointer to a BMVert in the former.

Original Data Now Stored In Customdata Layers

Original vertex coordinates, normals and colors for bmesh PBVH are now cached as customdata layers to avoid fetching them from BMLog (which requires a GHash lookup).

New Features

Customdata Interpolation

DynTopo now performs customdata interpolation. Right now it interpolates face and vertex data, and also propagates edge flags. It attempts to preserve edge seams, though it's not quite perfect yet. The hard part is the BMLog undo system. I've refactored it to save vertex customdata blocks. The hard part is not letting performance suffer from saving blocks too often and also keeping the customdata layouts of BMLog and the mesh in sync.

Here is a demo video I made:

dyntopo customdata.mp4

Sculpt Colors

I added support for sculpt colors to DynTopo. To do this I had to fix problems in the PBVH drawing code. PBVH can now draw vertex colors (both MLoopCol and MPropCol layers) and properly handles UVs. To make this work I added a new function to the draw engine API:

DRW_make_cdlayer_attr_aliases

It adds the various aliases EEVEE needs for vertex attributes. I patterned it after extract_uvs in draw_cache_extract_mesh.c; I would appreciate
it if someone from the draw engine team took a look at it. Here's a link to the code . Note that it doesn't properly display sculpt colors in Solid mode in vertex colors mode. I'm not quite sure what the vertex attribute name for that is.

One thing I found is the PBVH drawing code is much much faster for sculpt colors. It's a pretty huge difference; as such, I think we should use PBVH drawing for mesh and multires as well as dyntopo.

Multires Fixes

I re-implemented functions to convert edit-mode multires grids into and out of global space. Thus, the BMOpFlag BMOP_UNTAN_MULTIRES flag is now respected. This hugely improved multires reprojection when changing topology in edit mode. And unlike when I coded this ten years I now properly ensure that this all happens in the highest subdivision level.

By the way I discovered that interpolating MDisps grids in imperfect tangent spaces is numerically unstable, though I'm not entirely sure why this is the case. I've not eliminated all cases of this happening, that is on the todo list. I also need to code something that detects when individual grid points explode and smooth them out. This can also happen when moving between subdivision levels outside of editmode, so we need something general here.

I've been working on improving DynTopo performance and fixing some editmode multires reprojection issues. I've now merged both sets of changes into temp_multires_bmesh. I initially wrote a special-purpose triangle mesh library to replace bmesh in DynTopo but ultimately decided to abandon it. In many ways DynTopo already *is* a special-purpose triangle mesh library that happens to reuse the BMesh data structures, and while I think a special-purpose library would be a good idea in terms of code maintainability it would also preclude us from ever adding support for quads and/or ngons to DynTopo. ![image.png](https://archive.blender.org/developer/F9106253/image.png) # Performance Fixes ## Speedups When Topologizer Isn't Running I discovered that even without the topologizer DynTopo was quite slow. I sped it up in several ways, listed below. ### Increased pbvh->leaf_limit from 100 to 3000 This sped things up quite a bit. ### Wrote a wrapper around GSet that stores elements in pointer arrays for faster iteration. Profiling revealed that iterating over GSets (specifically PBVHNode->bm_unique_verts and bm_other_verts) was a significant performance loss. I initially solved the problem by inlining all of GHash, but I figured that wasn't appropriate and might have unexpected consequences elsewhere. My solution was to write a wrapper that maintains a flat pointer array for fast iteration (which is done via macro inlining instead of function calls). Note that this wrapper is still not indexable, when elements are removed from the set their entries in the flat pointer array is simply set to NULL. Note however that the array is compacted when it is resized. ### Refactored sculpt vertex "indices" into vertex references (SculptVertRef) and indices. Profiling revealed a large amount of time was being spent maining BMesh element arrays. By creating an abstract SculptVertRef type and storing a pointer to a BMVert inside of it (instead of an index) I was able to drastically cut down the calls to BM_elem_table_ensure. SculptVertRef and indices can be converted to/from each other: ``` SculptVertRef *vertex = BKE_pbvh_table_index_to_vertex(pbvh, index); int index = BKE_pbvh_vertex_index_to_table(pbvh, vertex); ``` PBVHVertexIter and SculptNeighborIterator now have .vertex members that refer to the currently active SculptVertRef, as well as .index. For meshes and grid PBVHs these store the same values, but BMesh puts a pointer to a BMVert in the former. ### Original Data Now Stored In Customdata Layers Original vertex coordinates, normals and colors for bmesh PBVH are now cached as customdata layers to avoid fetching them from BMLog (which requires a GHash lookup). # New Features ## Customdata Interpolation DynTopo now performs customdata interpolation. Right now it interpolates face and vertex data, and also propagates edge flags. It attempts to preserve edge seams, though it's not quite perfect yet. The hard part is the BMLog undo system. I've refactored it to save vertex customdata blocks. The hard part is not letting performance suffer from saving blocks too often and also keeping the customdata layouts of BMLog and the mesh in sync. Here is a demo video I made: [dyntopo customdata.mp4](https://archive.blender.org/developer/F9106367/dyntopo_customdata.mp4) ## Sculpt Colors I added support for sculpt colors to DynTopo. To do this I had to fix problems in the PBVH drawing code. PBVH can now draw vertex colors (both MLoopCol and MPropCol layers) and properly handles UVs. To make this work I added a new function to the draw engine API: ``` DRW_make_cdlayer_attr_aliases ``` It adds the various aliases EEVEE needs for vertex attributes. I patterned it after extract_uvs in draw_cache_extract_mesh.c; I would appreciate it if someone from the draw engine team took a look at it. [Here's a link to the code ](https://developer.blender.org/diffusion/B/browse/temp_bmesh_multires/source/blender/draw/intern/draw_cache.c$477). Note that it doesn't properly display sculpt colors in Solid mode in vertex colors mode. I'm not quite sure what the vertex attribute name for that is. One thing I found is the PBVH drawing code is much *much* faster for sculpt colors. It's a pretty huge difference; as such, I think we should use PBVH drawing for mesh and multires as well as dyntopo. # Multires Fixes I re-implemented functions to convert edit-mode multires grids into and out of global space. Thus, the BMOpFlag BMOP_UNTAN_MULTIRES flag is now respected. This hugely improved multires reprojection when changing topology in edit mode. And unlike when I coded this ten years I now properly ensure that this all happens in the highest subdivision level. By the way I discovered that interpolating MDisps grids in imperfect tangent spaces is numerically unstable, though I'm not entirely sure why this is the case. I've not eliminated all cases of this happening, that is on the todo list. I also need to code something that detects when individual grid points explode and smooth them out. This can also happen when moving between subdivision levels outside of editmode, so we need something general here.

Joseph Eagar self-assigned this 2020-10-27 03:50:09 +01:00

Joseph Eagar commented

2020-10-27 03:50:09 +01:00

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

Joseph Eagar commented

2020-10-27 03:50:09 +01:00

Added subscribers: @JosephEagar, @PabloDobarro

TheRedWaxPolice commented

2020-10-27 03:57:08 +01:00

Added subscriber: @TheRedWaxPolice

thin soldier commented

2020-10-27 04:28:05 +01:00

Added subscriber: @thinsoldier

Paul Larson commented

2020-10-27 04:49:26 +01:00

Added subscriber: @GeorgiaPacific

Tobias Fuchsberger commented

2020-10-27 08:54:25 +01:00

Added subscriber: @Fux

Janne Aliu commented

2020-10-27 09:23:02 +01:00

Added subscriber: @Jaydead

Debuk commented

2020-10-27 09:47:21 +01:00

Added subscriber: @Debuk

Steffen Dünner commented

2020-10-27 12:59:23 +01:00

Added subscriber: @SteffenD

Pablo Dobarro commented

2020-10-27 13:36:11 +01:00

I created #82140 to have an overview of the functionality I would like to support in Dyntopo, so we should check the following first:

Make sure the new Face Set visibility operators and API can be implemented (if face attributes interpolation is already working I don't think supporting this is going to be a problem)
There are some operators (like the remeshers) that modify the object mesh in a single step, which require a ##SCULPT_UNDO_GEOMETRY## push. This stores the whole mesh before and after the modification. I would like these operators to work with dyntopo, so we should consider how to approach this to avoid possible conflicts with the dyntopo enter/exit undo steps.
Some of the functionality requires running the topologizer in arbitrary areas, not only limited to the brush location and radius. Is this possible to support?

If this is all OK, then I think we can start moving things to master for 2.92.

I created #82140 to have an overview of the functionality I would like to support in Dyntopo, so we should check the following first: - Make sure the new Face Set visibility operators and API can be implemented (if face attributes interpolation is already working I don't think supporting this is going to be a problem) - There are some operators (like the remeshers) that modify the object mesh in a single step, which require a ##SCULPT_UNDO_GEOMETRY## push. This stores the whole mesh before and after the modification. I would like these operators to work with dyntopo, so we should consider how to approach this to avoid possible conflicts with the dyntopo enter/exit undo steps. - Some of the functionality requires running the topologizer in arbitrary areas, not only limited to the brush location and radius. Is this possible to support? If this is all OK, then I think we can start moving things to master for 2.92.

Metin Seven commented

2020-10-27 18:41:36 +01:00

Added subscriber: @MetinSeven-1

Metin Seven commented

2020-10-27 18:41:36 +01:00

I'm wondering: looking at the tri-topology of the demo video, the triangulation structure seems to be less neatly distributed than the current Dyntopo. Does the improved Dyntopo use the same topology algorithm (maybe Delaunay or Voronoi) as Decimate modifier?

Ryan Inch commented

2020-10-27 22:45:25 +01:00

Added subscriber: @Imaginer

Brecht Van Lommel commented

2020-10-28 12:25:22 +01:00

Added subscriber: @brecht

Brecht Van Lommel commented

2020-10-28 12:25:22 +01:00

Increased pbvh->leaf_limit from 100 to 3000
Wrote a wrapper around GSet that stores elements in pointer arrays for faster iteration.
Refactored sculpt vertex "indices" into vertex references (SculptVertRef) and indices.
Original Data Now Stored In Customdata Layers

All this sounds fine.

Topologizer Speedup
I made the topologizer faster by time limiting it. The core topologizer loops now execute for a fixed amount of time, and in addition there is a limit to how often the topologizer may be called per second.

We should not time limit, for the same reasons as explained in D8508. Limiting the number of collapses may be ok, but the quality of strokes should not depend on the computer specs or if you have e.g. music playing in the background. Brushes should be more reliable than that.

For a smooth brush stroke, I imagine you want retopology to be somewhow well distributed across steps, and avoid steps that need to do a lot more work than others.

Customdata Interpolation
Sculpt Colors
Multires Fixes

This all sounds great.

> Increased pbvh->leaf_limit from 100 to 3000 > Wrote a wrapper around GSet that stores elements in pointer arrays for faster iteration. > Refactored sculpt vertex "indices" into vertex references (SculptVertRef) and indices. > Original Data Now Stored In Customdata Layers All this sounds fine. > Topologizer Speedup > I made the topologizer faster by time limiting it. The core topologizer loops now execute for a fixed amount of time, and in addition there is a limit to how often the topologizer may be called per second. We should not time limit, for the same reasons as explained in [D8508](https://archive.blender.org/developer/D8508). Limiting the number of collapses may be ok, but the quality of strokes should not depend on the computer specs or if you have e.g. music playing in the background. Brushes should be more reliable than that. For a smooth brush stroke, I imagine you want retopology to be somewhow well distributed across steps, and avoid steps that need to do a lot more work than others. > Customdata Interpolation > Sculpt Colors > Multires Fixes This all sounds great.

Joseph Eagar commented

2020-10-29 12:33:44 +01:00

In #82121#1043071, @MetinSeven-1 wrote:
I'm wondering: looking at the tri-topology of the demo video, the triangulation structure seems to be less neatly distributed than the current Dyntopo. Does the improved Dyntopo use the same topology algorithm (maybe Delaunay or Voronoi) as Decimate modifier?

It's mostly the same algorithm, but instead of running to convergence it runs for a fixed amount of time. Certain popular commercial software that shall not be named appears to do this. That said, I did try and tweak the edge collapse weights to try and make nicer geometry, I'll take a look at it again.

> In #82121#1043071, @MetinSeven-1 wrote: > I'm wondering: looking at the tri-topology of the demo video, the triangulation structure seems to be less neatly distributed than the current Dyntopo. Does the improved Dyntopo use the same topology algorithm (maybe Delaunay or Voronoi) as Decimate modifier? It's mostly the same algorithm, but instead of running to convergence it runs for a fixed amount of time. Certain popular commercial software that shall not be named appears to do this. That said, I did try and tweak the edge collapse weights to try and make nicer geometry, I'll take a look at it again.

Brecht Van Lommel commented

2020-10-29 12:37:49 +01:00

In #82121#1044178, @JosephEagar wrote:
Certain popular commercial software that shall not be named appears to do this.

Please don't bring up such things in design discussions on developer.blender.org at all, not naming the software is not some kind of legal protection. Argue why a particular behavior is good for Blender.

> In #82121#1044178, @JosephEagar wrote: > Certain popular commercial software that shall not be named appears to do this. Please don't bring up such things in design discussions on developer.blender.org at all, not naming the software is not some kind of legal protection. Argue why a particular behavior is good for Blender.

Metin Seven commented

2020-10-29 13:05:11 +01:00

In #82121#1044178, @JosephEagar wrote:

It's mostly the same algorithm, but instead of running to convergence it runs for a fixed amount of time. That said, I did try and tweak the edge collapse weights to try and make nicer geometry, I'll take a look at it again.

Thanks Joseph, appreciated. Among the noticeable differences in the video is pole-formation within triangles (like flat three-sided pyramids). I haven't seen that in the current Dyntopo.

I'm very, very happy to see Dyntopo get a much-needed upgrade. Keep up the good work!

> In #82121#1044178, @JosephEagar wrote: > > It's mostly the same algorithm, but instead of running to convergence it runs for a fixed amount of time. That said, I did try and tweak the edge collapse weights to try and make nicer geometry, I'll take a look at it again. Thanks Joseph, appreciated. Among the noticeable differences in the video is pole-formation within triangles (like flat three-sided pyramids). I haven't seen that in the current Dyntopo. I'm very, very happy to see Dyntopo get a much-needed upgrade. Keep up the good work!

Chris Kohl commented

2020-10-29 21:57:24 +01:00

Added subscriber: @ckohl_art

Pablo Dobarro commented

2020-10-30 02:17:46 +01:00

Probably this needs to be discussed in more when reviewing the time limit optimisation.

The idea is prioritising responsiveness over stroke quality and consistency, which is something I still think we should do for some brushes, tools and modes. I understand the concern of changing the spacing or time limiting any other process that affect the stroke for brushes that will define the final surface of the mesh (like draw sharp with a low spacing to define creases or wrinkles, were spacing and strength needs to be consistent in all samples). For brushes that are not intended to define the final surface, I think we should prioritise responsiveness over anything. This could be an option per brush, I’m in favor of time limiting topology updates in clay strips to make it run as fast as possible, but probably there should be a way to disable this for precise creasing brushes intended to define the final details.

Consider that if the CPU was not capable of processing the stroke step before the time limit end, the stroke will lag and the viewport will freeze. When using a non screen tablet, you will probably loose the hand coordination and you will need to undo and redo the same stroke, but slower. So the options are, not time limiting it and output a high quality stroke over an uncontrolled path, or output a random quality stroke over a controlled path. When surface quality is not the main focus, the second option is always preferable.

Also, we kind of have something similar already in Blender. The dots stroke type will only generate a new sample when the previous one ends being processed, which totally makes sample spacing depend on performance. You can try the cloth brush with regular spacing set to 10 and dots and see how much responsive it is when using dots. Of course, that makes the spacing and the solver update rate completely random and depending on the computer specs, but I don’t think any user will consider that an issue.

Probably this needs to be discussed in more when reviewing the time limit optimisation. The idea is prioritising responsiveness over stroke quality and consistency, which is something I still think we should do for some brushes, tools and modes. I understand the concern of changing the spacing or time limiting any other process that affect the stroke for brushes that will define the final surface of the mesh (like draw sharp with a low spacing to define creases or wrinkles, were spacing and strength needs to be consistent in all samples). For brushes that are not intended to define the final surface, I think we should prioritise responsiveness over anything. This could be an option per brush, I’m in favor of time limiting topology updates in clay strips to make it run as fast as possible, but probably there should be a way to disable this for precise creasing brushes intended to define the final details. Consider that if the CPU was not capable of processing the stroke step before the time limit end, the stroke will lag and the viewport will freeze. When using a non screen tablet, you will probably loose the hand coordination and you will need to undo and redo the same stroke, but slower. So the options are, not time limiting it and output a high quality stroke over an uncontrolled path, or output a random quality stroke over a controlled path. When surface quality is not the main focus, the second option is always preferable. Also, we kind of have something similar already in Blender. The dots stroke type will only generate a new sample when the previous one ends being processed, which totally makes sample spacing depend on performance. You can try the cloth brush with regular spacing set to 10 and dots and see how much responsive it is when using dots. Of course, that makes the spacing and the solver update rate completely random and depending on the computer specs, but I don’t think any user will consider that an issue.

Joseph Eagar commented

2020-10-31 02:26:43 +01:00

In #82121#1044181, @brecht wrote:

In #82121#1044178, @JosephEagar wrote:
Certain popular commercial software that shall not be named appears to do this.

Please don't bring up such things in design discussions on developer.blender.org at all, not naming the software is not some kind of legal protection. Argue why a particular behavior is good for Blender.

I shall refrain from such things in the future.

> In #82121#1044181, @brecht wrote: >> In #82121#1044178, @JosephEagar wrote: >> Certain popular commercial software that shall not be named appears to do this. > > Please don't bring up such things in design discussions on developer.blender.org at all, not naming the software is not some kind of legal protection. Argue why a particular behavior is good for Blender. I shall refrain from such things in the future.

Gabriele Macchi commented

2021-05-08 11:49:01 +02:00

Added subscriber: @Alchimista

Vyacheslav Kobozev commented

2021-06-25 13:07:26 +02:00

Added subscriber: @Vyach

Darrin Alder commented

2022-06-27 01:54:45 +02:00

Added subscriber: @DARRINALDER

Joseph Eagar changed title from ~~Dyntopo Improvements~~ to Dyntopo Improvements In Sculpt-Dev

2022-12-19 14:59:16 +01:00

Esteban commented

2022-12-19 19:16:30 +01:00

Added subscriber: @E.Meurat

Julien Kaspar added this to the Sculpt, Paint & Texture project 2023-02-08 10:20:48 +01:00

Julien Kaspar added a new dependency 2023-02-09 22:19:18 +01:00

#104544 VSE: Add retiming tool

Julien Kaspar removed a dependency 2023-02-09 22:19:24 +01:00

#104544 VSE: Add retiming tool

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Dyntopo Improvements In Sculpt-Dev #82121

Performance Fixes

Speedups When Topologizer Isn't Running

Increased pbvh->leaf_limit from 100 to 3000

Wrote a wrapper around GSet that stores elements in pointer arrays for faster iteration.

Refactored sculpt vertex "indices" into vertex references (SculptVertRef) and indices.

Original Data Now Stored In Customdata Layers

New Features

Customdata Interpolation

Sculpt Colors

Multires Fixes