Dyntopo

This patch adds a dynamic topology mode to sculpt mode.

User documentation in progress here:
http://wiki.blender.org/index.php/User:Nicholasbishop/Dyntopo

It can be more conveniently examined as a series of 20 patches in this
repository: https://github.com/nicholasbishop/blender/commits/dyntopo-9

Summary of changes follows:

=================================

    Import the RangeTree library into intern
    
    RangeTree is a simple C++ tree set for storing non-overlapping scalar
    ranges. Original source from:
    https://github.com/nicholasbishop/RangeTree
    
    Also update the build systems to include RangeTree.

=================================

    Add BM_edge_calc_squared_length() query function
    
    Same as BM_edge_calc_length(), but avoids square root for cases where
    only comparison is needed.

=================================

    Add function to find closest point in triangle to another point
    
    New function is closest_to_tri_v3() in BLI_math_geom.

=================================

    Disable fall through to global undo from paint/sculpt undo
    
    Undoing/redoing in sculpt and other paint modes should only use the
    mode-specific undo, not global undo. It is now consistent with edit
    mode and avoids tricky interaction between the two systems.

=================================

    Add BMLog for efficiently storing changes to vertices and faces
    
    The BMLog is an interface for storing undo/redo steps as a BMesh is
    modified. It only stores changes to the BMesh, not full copies.
    
    Currently it supports the following types of changes:
    - Adding and removing vertices
    - Adding and removing faces
    - Moving vertices
    - Setting vertex paint-mask values
    - Setting vertex hflags

=================================

    Add GPU_buffers support for drawing dynamic topology nodes
    
    The GPU interface for PBVH drawing gets a new pair of build/update
    buffers functions for drawing BMFaces and BMVerts.
    
    TODO: the diffuse color is hardcoded to 0.8 gray rather than using
    material color.
    
    TODO: only VBO drawing is implemented, no immediate mode.

=================================

    Code cleanup: move PBVH/PBVHNode structs into new header file

=================================

    Move layer displacements from SculptUndoNode to PBVHNode
    
    * This doesn't make much difference for regular mesh/multires
      sculpting, but for dynamic topology sculpting the undo stack isn't
      split up by PBVH nodes, so it's more convenient to store the layer
      data in PBVH nodes.
    
    * Note that the life cycle of the layer displacement data is
      unchanged -- it's only valid during a stroke with the layer brush,
      gets free'd when the undo step ends.

=================================

    Add DNA/RNA/BKE infrastructure for dynamic-topology sculpt mode
    
    * Add a detail_size field to the Sculpt struct, two new sculpt flags,
      and a Mesh flag for dynamic-topology mode; that's it for file-level
      changes needed by dynamic topology
    
    * Add RNA for the new DNA field and flags
    
    * Add a new icon for dynamic-topology created by Julio Iglesias
    
    * Add a SculptSession function for converting from BMesh to Mesh,
      handles reordering mesh elements and setting face shading

=================================

    Add BLI_buffer, an alternative to BLI_array
    
    BLI_buffer is a dynamic homogeneous array similar to BLI_array, but it
    allocates a structure that can be passed around making it possible to
    resize the array outside the function it was declared in.

=================================

    Add dynamic topology support to the PBVH
    
    * Add BLI_pbvh_build_bmesh(), similar to the other PBVH builders but
      specialized for BMesh. Whereas the PBVH leaf nodes for mesh and
      grids only store a start-index and count into the primitive indices
      array, the BMesh version uses GHashes to store the full set of faces
      and vertices in leaf nodes
    
    * Update PBVH iterator to handle BMesh
    
    * Make some of the pbvh.c functions non-static so they can be used by
      the new pbvh_bmesh code
    
    * The BLI_pbvh_bmesh_update_topology() function is the main reason for
      adding BMesh support to the PBVH. This function is used during a
      sculpt stroke to dynamically collapse edges that are particular
      short and subdivide edges that are particularly long.

=================================

    Add dynamic topology support to sculpt mode
    
    * Add SCULPT_OT_dynamic_topology_toggle operator to enable or disable
      dynamic topology mode
    
    * Most brushes need little modification for dynamic topology, but for
      some it won't work well and is disabled. This decision is made in
      sculpt_stroke_dynamic_topology().
    
    * For brushes that need original data (e.g. grab brush) the topology
      is not updated during the stroke, but some changes to original
      vertex data is accessed were made since BMesh works a little
      differently from mesh/multires. This is abstracted with
      SculptOrigVertData and associated functions.
    
    * Smooth brush gets yet another set of functions, for mesh and
      multires and dynamic topology and, separetely, masking
    
    * For most brushes, the topology is updated during the stroke right
      before the regular brush action takes place. This is handled in
      sculpt_topology_update().
    
    * Exiting sculpt mode also disables dynamic topology
    
    * Sculpt undo works differently with BMesh. Since the contents of
      nodes in the PBVH do not remain static during a sculpt session, the
      SculptUndoNodes do not correspond with PBVHNodes if dynamic topology
      is enabled. Rather, each SculptUndoNode is associated with a
      BMLogEntry.
    
    * Sculpt undo gets a few new cases: entering and exiting dynamic
      topology does an undo push of all mesh data. Symmetrize will
      similarly push a full copy of BMesh data, although it does so
      through the BMLog API.
    
    * Undo and redo in dynamic-topology mode will do a full recalculation
      of the PBVH.
    
    * Add some documentation to doc/sculpt.org. This could stand to be
      expanded a lot more, for now it mostly contains test cases for the
      undo system.
    
    * Add SCULPT_OT_optimize operator to recalculate the BVH. The BVH gets
      less optimal more quickly with dynamic topology than regular
      sculpting. There is no doubt more clever stuff we can do to optimize
      it on the fly, but for now this gives the user a nicer way to
      recalculate it than toggling modes.

=================================

    Modify info stats for dynamic-topology sculpt mode
    
    Format is like this: "Verts:8 | Tris:12 | Cube"

=================================

    Update DerivedMesh for dynamic-topology sculpt mode
    
    * Build bmesh PBVH in CDDM when dyntopo is enabled
    
    * Disable all modifiers when dyntopo is enabled

=================================

    Hiding support for dynamic topology

=================================

    Use GPU_Buffers to draw wireframe when in dynamic-topology sculpt mode
    
    This adds an override to the CDDM edge drawing function that switches
    to GPU_Buffers drawing for PBVHes of type PBVH_BMESH.
    
    Within the GPU_Buffers code, glPolygonMode() is used to draw lines
    instead of faces.

=================================

    Add simplify brush for sculpt mode

=================================

    Add symmetrize operator for dynamic-topology sculpt mode

=================================

    Add UI and keybindings for dynamic-topology sculpt mode
    
    * New topology panel in 3D view toolbar with the enable/disable button
      for dynamic topology and other controls
    
    * Ctrl+DKEY to toggle dynamic topology
    
    * Shift+DKEY to show a radial control for detail size

[sergey.vfx, 2012-12-17 14:18:45]

Did initial review.

In general seems to be fine, but would need to compile patch first and see how
it works (mainly not sure from code if CD layers like UV will be preserved by
BMLog).

Do have note about code style -- we're not actually using style where function
arguments are split onto different lines, one per line. See
http://wiki.blender.org/index.php/Dev:Doc/CodeStyle#Indentation

Also seems pbvh changes weren't fully ported onto new trunk -- functions are
still using BLI_ prefix, however functions are in blenkernel already.

Also, why range tree is intern? Unless it's a library you're gonna to maintain,
think extern/ is better place?

Will report back when will compile patch, do have some places not sure about
atm. Stay tuned :)

https://codereview.appspot.com/6947064/diff/1/release/scripts/startup/bl_ui/s...
File release/scripts/startup/bl_ui/space_view3d_toolbar.py (right):

https://codereview.appspot.com/6947064/diff/1/release/scripts/startup/bl_ui/s...
release/scripts/startup/bl_ui/space_view3d_toolbar.py:884: col.active =
context.sculpt_object.use_dynamic_topology_sculpting
Pedantic: active flag is usually set before filling layout with a properties.

https://codereview.appspot.com/6947064/diff/1/source/blender/blenkernel/inter...
File source/blender/blenkernel/intern/pbvh.c (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/blenkernel/inter...
source/blender/blenkernel/intern/pbvh.c:1531: void BLI_pbvh_node_draw(PBVHNode
*node, void *data_v)
This is actually should be BKE_. Some other functions are also seems not be
using proper prefix after recent changes in trunk.

https://codereview.appspot.com/6947064/diff/1/source/blender/blenkernel/inter...
source/blender/blenkernel/intern/pbvh.c:1674: node->layer_disp =
MEM_callocN(sizeof(float) * totvert, "layer disp");
Not sure yet if this name conflicts with do_layer_brush. If so, better to use
more unique name here.

https://codereview.appspot.com/6947064/diff/1/source/blender/blenkernel/inter...
File source/blender/blenkernel/intern/pbvh_intern.h (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/blenkernel/inter...
source/blender/blenkernel/intern/pbvh_intern.h:27: } BB;
Since it became more or less public, i would call structures in more verbose
manner and use more verbose prefix for functions. To avoid possible shadow
declarations or other possible confusion in the future.

https://codereview.appspot.com/6947064/diff/1/source/blender/blenlib/BLI_math...
File source/blender/blenlib/BLI_math_geom.h (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/blenlib/BLI_math...
source/blender/blenlib/BLI_math_geom.h:76: void closest_to_tri_v3(float r[3],
const float p[3], const float t1[3], const float t2[3], const float t3[3]);
Don't think name actually corresponds what this functions is doing: name says it
searches point closest to triangle, not point on triangle. Better naming could
be:
- closest_on_tri_v3
- closest_on_tri_to_point_v3

https://codereview.appspot.com/6947064/diff/1/source/blender/blenlib/intern/b...
File source/blender/blenlib/intern/buffer.c (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/blenlib/intern/b...
source/blender/blenlib/intern/buffer.c:53: void BLI_buffer_free(BLI_Buffer
*buffer)
Should this function reset allocated/used counters?

https://codereview.appspot.com/6947064/diff/1/source/blender/bmesh/intern/bme...
File source/blender/bmesh/intern/bmesh_log.c (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/bmesh/intern/bme...
source/blender/bmesh/intern/bmesh_log.c:131:
assert(BLI_ghash_haskey(log->id_to_elem, key));
Would use BLI_assert, so it'll be possible to avoid aborts even in debug builds.

https://codereview.appspot.com/6947064/diff/1/source/blender/editors/sculpt_p...
File source/blender/editors/sculpt_paint/sculpt.c (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/editors/sculpt_p...
source/blender/editors/sculpt_paint/sculpt.c:4056: origco = (void*)0x1;
Hrm, sounds a bit nasty =\

https://codereview.appspot.com/6947064/diff/1/source/blender/editors/sculpt_p...
source/blender/editors/sculpt_paint/sculpt.c:4665: static void
SCULPT_OT_optimize(wmOperatorType *ot)
Are there plans of avoiding this operator? :)

https://codereview.appspot.com/6947064/diff/1/source/blender/makesrna/intern/...
File source/blender/makesrna/intern/rna_sculpt_paint.c (right):

https://codereview.appspot.com/6947064/diff/1/source/blender/makesrna/intern/...
source/blender/makesrna/intern/rna_sculpt_paint.c:44: #include "bmesh.h"
Not sure why bmesh.h is needed here?

[sergey.vfx, 2012-12-21 10:55:30]

Made some tests with blender itself.

Custom data layers are erasing, also seems textured mode doesn't work with
dyntopo.

However perhaps CD issue isn't so big issue from sculpting pipeline POV? Also
perhaps textured mode could be fixed after merge.

[nicholasbishop, 2012-12-22 20:49:31]

Thanks for doing reviews Sergey. End-of-year sickness and holiday stuff is
delaying me from making the updates, will hopefully have time to address your
comments in the next few days though.

-Nicholas

On 2012/12/21 10:55:30, sergey.vfx wrote:
> Made some tests with blender itself.
> 
> Custom data layers are erasing, also seems textured mode doesn't work with
> dyntopo.
> 
> However perhaps CD issue isn't so big issue from sculpting pipeline POV? Also
> perhaps textured mode could be fixed after merge.

[nicholasbishop, 2012-12-25 05:18:00]

Review updates

[nicholasbishop, 2012-12-25 05:22:08]

On 2012/12/25 05:18:00, nicholasbishop wrote:
> Review updates

Uploaded a new patch that addresses many of your code comments, although not the
issues of custom-data layers and texture drawing mode.

One code thing I didn't change yet was the naming of the BB/BBC structures and
functions. Agree these could be better named, but they're still internal to pbvh
so not urgent.