[Bf-codereview] Dyntopo (issue 6947064)

[NicholasBishop at gmail.com]

Reviewers: bf-codereview_blender.org,

Description:
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


Please review this at https://codereview.appspot.com/6947064/

Affected files:
   doc/sculpt.org
   intern/CMakeLists.txt
   intern/SConscript
   intern/rangetree/CMakeLists.txt
   intern/rangetree/README.org
   intern/rangetree/SConscript
   intern/rangetree/range_tree.hh
   intern/rangetree/range_tree_c_api.cc
   intern/rangetree/range_tree_c_api.h
   release/datafiles/blender_icons.png
   release/scripts/startup/bl_ui/space_view3d_toolbar.py
   source/blender/blenkernel/BKE_paint.h
   source/blender/blenkernel/BKE_pbvh.h
   source/blender/blenkernel/CMakeLists.txt
   source/blender/blenkernel/intern/DerivedMesh.c
   source/blender/blenkernel/intern/cdderivedmesh.c
   source/blender/blenkernel/intern/object.c
   source/blender/blenkernel/intern/pbvh.c
   source/blender/blenkernel/intern/pbvh_bmesh.c
   source/blender/blenkernel/intern/pbvh_intern.h
   source/blender/blenkernel/intern/subsurf_ccg.c
   source/blender/blenlib/BLI_buffer.h
   source/blender/blenlib/BLI_math_geom.h
   source/blender/blenlib/CMakeLists.txt
   source/blender/blenlib/intern/buffer.c
   source/blender/blenlib/intern/math_geom.c
   source/blender/bmesh/CMakeLists.txt
   source/blender/bmesh/SConscript
   source/blender/bmesh/bmesh.h
   source/blender/bmesh/intern/bmesh_log.c
   source/blender/bmesh/intern/bmesh_log.h
   source/blender/bmesh/intern/bmesh_queries.c
   source/blender/bmesh/intern/bmesh_queries.h
   source/blender/bmesh/operators/bmo_symmetrize.c
   source/blender/editors/include/UI_icons.h
   source/blender/editors/mesh/editmesh_tools.c
   source/blender/editors/sculpt_paint/paint_hide.c
   source/blender/editors/sculpt_paint/paint_ops.c
   source/blender/editors/sculpt_paint/sculpt.c
   source/blender/editors/sculpt_paint/sculpt_intern.h
   source/blender/editors/sculpt_paint/sculpt_undo.c
   source/blender/editors/space_info/info_stats.c
   source/blender/editors/util/undo.c
   source/blender/gpu/CMakeLists.txt
   source/blender/gpu/GPU_buffers.h
   source/blender/gpu/SConscript
   source/blender/gpu/intern/gpu_buffers.c
   source/blender/makesdna/DNA_brush_types.h
   source/blender/makesdna/DNA_mesh_types.h
   source/blender/makesdna/DNA_scene_types.h
   source/blender/makesrna/RNA_enum_types.h
   source/blender/makesrna/intern/rna_brush.c
   source/blender/makesrna/intern/rna_object.c
   source/blender/makesrna/intern/rna_sculpt_paint.c
   source/creator/CMakeLists.txt