Page MenuHome

Dyntopo Improvements
Confirmed, NormalPublicDESIGN

Authored By
Joseph Eagar (joeedh)
Oct 27 2020, 3:50 AM
Tokens
"Love" token, awarded by rbx775."Love" token, awarded by mindinsomnia."Love" token, awarded by rpserge."100" token, awarded by NAS."Love" token, awarded by g.ndre."Love" token, awarded by gilberto_rodrigues."Love" token, awarded by gritche."Love" token, awarded by tiagoffcruz."Love" token, awarded by brilliant_ape."Love" token, awarded by tux21b."Like" token, awarded by Imaginer."Party Time" token, awarded by Torrent."Burninate" token, awarded by Regnas."Love" token, awarded by erickblender."Like" token, awarded by lokashev."Like" token, awarded by cfnjrey."Love" token, awarded by sick."100" token, awarded by MetinSeven."100" token, awarded by 616."Love" token, awarded by manitwo."Haypence" token, awarded by lopoIsaac."Love" token, awarded by andruxa696."Love" token, awarded by Kronk."Love" token, awarded by 14AUDDIN."Like" token, awarded by IPv6."Love" token, awarded by julperado."Love" token, awarded by ebarranco."Party Time" token, awarded by Alrob."Love" token, awarded by HooglyBoogly."Like" token, awarded by GeorgiaPacific."Love" token, awarded by xrg."Like" token, awarded by TheRedWaxPolice.

Description

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

== 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. This helped quite a bit and seems to be in line with how other software behaves.

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:

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.

Event Timeline

Joseph Eagar (joeedh) changed the task status from Needs Triage to Confirmed.Oct 27 2020, 3:50 AM
Joseph Eagar (joeedh) created this task.

I created T82140 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'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?

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.

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.

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.

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!

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.

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.