Volumes: support selection and outlines in viewport

Previously, one could only select a volume object in the outliner
or by clicking on the object origin. This patch allows you to click
on the actual volume.

Furthermore, the generated (invisible) mesh that is used for
selection is also used to draw an outline for the volume object now.

Reviewers: brecht

Differential Revision: https://developer.blender.org/D9022

1 files changed, 294 insertions, 158 deletions

diff --git a/source/blender/blenkernel/intern/volume_render.cc b/source/blender/blenkernel/intern/volume_render.cc
index 98d3617c822..b773452b6a8 100644
--- a/source/blender/blenkernel/intern/volume_render.cc
+++ b/source/blender/blenkernel/intern/volume_render.cc
@@ -20,8 +20,11 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array.hh"
+#include "BLI_float3.hh"
 #include "BLI_math_matrix.h"
 #include "BLI_math_vector.h"
+#include "BLI_vector.hh"
 
 #include "DNA_volume_types.h"
 
@@ -166,107 +169,223 @@ void BKE_volume_grid_dense_voxels(const Volume *volume,
 /* Wireframe */
 
 #ifdef WITH_OPENVDB
-struct VolumeWireframe {
-  std::vector<openvdb::Vec3f> verts;
-  std::vector<openvdb::Vec2I> edges;
-
-  template<typename GridType>
-  void add_grid(openvdb::GridBase::ConstPtr gridbase, const bool points, const bool coarse)
-  {
-    using TreeType = typename GridType::TreeType;
-    using Depth2Type = typename TreeType::RootNodeType::ChildNodeType::ChildNodeType;
-    using NodeCIter = typename TreeType::NodeCIter;
-    using GridConstPtr = typename GridType::ConstPtr;
-
-    GridConstPtr grid = openvdb::gridConstPtrCast<GridType>(gridbase);
-    const openvdb::math::Transform &transform = grid->transform();
-    const int depth = (coarse) ? 2 : 3;
-
-    NodeCIter iter = grid->tree().cbeginNode();
-    iter.setMaxDepth(depth);
-
-    for (; iter; ++iter) {
-      if (iter.getDepth() == depth) {
-        openvdb::CoordBBox coordbbox;
-
-        if (depth == 2) {
-          /* Internal node at depth 2. */
-          const Depth2Type *node = nullptr;
-          iter.getNode(node);
-          if (node) {
-            node->evalActiveBoundingBox(coordbbox, false);
-          }
-          else {
-            continue;
-          }
-        }
-        else {
-          /* Leaf node. */
-          if (!iter.getBoundingBox(coordbbox)) {
-            continue;
-          }
-        }
-
-        /* +1 to convert from exclusive to include bounds. */
-        coordbbox.max() = coordbbox.max().offsetBy(1);
-        openvdb::BBoxd bbox = transform.indexToWorld(coordbbox);
-
-        if (points) {
-          add_point(bbox);
-        }
-        else {
-          add_box(bbox);
-        }
+
+/** Returns bounding boxes that approximate the shape of the volume stored in the grid. */
+template<typename GridType>
+static blender::Vector<openvdb::CoordBBox> get_bounding_boxes(openvdb::GridBase::ConstPtr gridbase,
+                                                              const bool coarse)
+{
+  using TreeType = typename GridType::TreeType;
+  using Depth2Type = typename TreeType::RootNodeType::ChildNodeType::ChildNodeType;
+  using NodeCIter = typename TreeType::NodeCIter;
+  using GridConstPtr = typename GridType::ConstPtr;
+
+  GridConstPtr grid = openvdb::gridConstPtrCast<GridType>(gridbase);
+  blender::Vector<openvdb::CoordBBox> boxes;
+  const int depth = coarse ? 2 : 3;
+
+  NodeCIter iter = grid->tree().cbeginNode();
+  iter.setMaxDepth(depth);
+
+  for (; iter; ++iter) {
+    if (iter.getDepth() != depth) {
+      continue;
+    }
+
+    openvdb::CoordBBox box;
+    if (depth == 2) {
+      /* Internal node at depth 2. */
+      const Depth2Type *node = nullptr;
+      iter.getNode(node);
+      if (node) {
+        node->evalActiveBoundingBox(box, false);
       }
+      else {
+        continue;
+      }
+    }
+    else {
+      /* Leaf node. */
+      if (!iter.getBoundingBox(box)) {
+        continue;
+      }
+    }
+
+    /* +1 to convert from exclusive to inclusive bounds. */
+    box.max() = box.max().offsetBy(1);
+
+    boxes.append(box);
+  }
+
+  return boxes;
+}
+
+static blender::Vector<openvdb::CoordBBox> get_bounding_boxes(VolumeGridType grid_type,
+                                                              openvdb::GridBase::ConstPtr grid,
+                                                              const bool coarse)
+{
+  switch (grid_type) {
+    case VOLUME_GRID_BOOLEAN: {
+      return get_bounding_boxes<openvdb::BoolGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_FLOAT: {
+      return get_bounding_boxes<openvdb::FloatGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_DOUBLE: {
+      return get_bounding_boxes<openvdb::DoubleGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_INT: {
+      return get_bounding_boxes<openvdb::Int32Grid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_INT64: {
+      return get_bounding_boxes<openvdb::Int64Grid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_MASK: {
+      return get_bounding_boxes<openvdb::MaskGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_VECTOR_FLOAT: {
+      return get_bounding_boxes<openvdb::Vec3fGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_VECTOR_DOUBLE: {
+      return get_bounding_boxes<openvdb::Vec3dGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_VECTOR_INT: {
+      return get_bounding_boxes<openvdb::Vec3IGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_STRING: {
+      return get_bounding_boxes<openvdb::StringGrid>(grid, coarse);
+      break;
+    }
+    case VOLUME_GRID_POINTS:
+    case VOLUME_GRID_UNKNOWN: {
+      break;
+    }
+  }
+  return {};
+}
+
+static void boxes_to_center_points(blender::Span<openvdb::CoordBBox> boxes,
+                                   const openvdb::math::Transform &transform,
+                                   blender::MutableSpan<blender::float3> r_verts)
+{
+  BLI_assert(boxes.size() == r_verts.size());
+  for (const int i : boxes.index_range()) {
+    openvdb::Vec3d center = transform.indexToWorld(boxes[i].getCenter());
+    r_verts[i] = blender::float3(center[0], center[1], center[2]);
+  }
+}
+
+static void boxes_to_corner_points(blender::Span<openvdb::CoordBBox> boxes,
+                                   const openvdb::math::Transform &transform,
+                                   blender::MutableSpan<blender::float3> r_verts)
+{
+  BLI_assert(boxes.size() * 8 == r_verts.size());
+  for (const int i : boxes.index_range()) {
+    const openvdb::CoordBBox &box = boxes[i];
+
+    /* The ordering of the corner points is lexicographic. */
+    std::array<openvdb::Coord, 8> corners;
+    box.getCornerPoints(corners.data());
+
+    for (int j = 0; j < 8; j++) {
+      openvdb::Coord corner_i = corners[j];
+      openvdb::Vec3d corner_d = transform.indexToWorld(corner_i);
+      r_verts[8 * i + j] = blender::float3(corner_d[0], corner_d[1], corner_d[2]);
     }
   }
+}
 
-  void add_point(const openvdb::BBoxd &bbox)
-  {
-    verts.push_back(bbox.getCenter());
+static void boxes_to_edge_mesh(blender::Span<openvdb::CoordBBox> boxes,
+                               const openvdb::math::Transform &transform,
+                               blender::Vector<blender::float3> &r_verts,
+                               blender::Vector<std::array<int, 2>> &r_edges)
+{
+  /* TODO: Deduplicate edges, hide flat edges? */
+
+  const int box_edges[12][2] = {
+      {0, 1},
+      {0, 2},
+      {0, 4},
+      {1, 3},
+      {1, 5},
+      {2, 3},
+      {2, 6},
+      {3, 7},
+      {4, 5},
+      {4, 6},
+      {5, 7},
+      {6, 7},
+  };
+
+  int vert_offset = r_verts.size();
+  int edge_offset = r_edges.size();
+
+  const int vert_amount = 8 * boxes.size();
+  const int edge_amount = 12 * boxes.size();
+
+  r_verts.resize(r_verts.size() + vert_amount);
+  r_edges.resize(r_edges.size() + edge_amount);
+  boxes_to_corner_points(boxes, transform, r_verts.as_mutable_span().take_back(vert_amount));
+
+  for (int i = 0; i < boxes.size(); i++) {
+    for (int j = 0; j < 12; j++) {
+      r_edges[edge_offset + j] = {vert_offset + box_edges[j][0], vert_offset + box_edges[j][1]};
+    }
+    vert_offset += 8;
+    edge_offset += 12;
   }
+}
 
-  void add_box(const openvdb::BBoxd &bbox)
-  {
-    /* TODO: deduplicate edges, hide flat edges? */
-    openvdb::Vec3f min = bbox.min();
-    openvdb::Vec3f max = bbox.max();
-
-    const int vert_offset = verts.size();
-    const int edge_offset = edges.size();
-
-    /* Create vertices. */
-    verts.resize(vert_offset + 8);
-    verts[vert_offset + 0] = openvdb::Vec3f(min[0], min[1], min[2]);
-    verts[vert_offset + 1] = openvdb::Vec3f(max[0], min[1], min[2]);
-    verts[vert_offset + 2] = openvdb::Vec3f(max[0], max[1], min[2]);
-    verts[vert_offset + 3] = openvdb::Vec3f(min[0], max[1], min[2]);
-    verts[vert_offset + 4] = openvdb::Vec3f(min[0], min[1], max[2]);
-    verts[vert_offset + 5] = openvdb::Vec3f(max[0], min[1], max[2]);
-    verts[vert_offset + 6] = openvdb::Vec3f(max[0], max[1], max[2]);
-    verts[vert_offset + 7] = openvdb::Vec3f(min[0], max[1], max[2]);
-
-    /* Create edges. */
-    const int box_edges[12][2] = {{0, 1},
-                                  {1, 2},
-                                  {2, 3},
-                                  {3, 0},
-                                  {4, 5},
-                                  {5, 6},
-                                  {6, 7},
-                                  {7, 4},
-                                  {0, 4},
-                                  {1, 5},
-                                  {2, 6},
-                                  {3, 7}};
-
-    edges.resize(edge_offset + 12);
-    for (int i = 0; i < 12; i++) {
-      edges[edge_offset + i] = openvdb::Vec2I(vert_offset + box_edges[i][0],
-                                              vert_offset + box_edges[i][1]);
+static void boxes_to_cube_mesh(blender::Span<openvdb::CoordBBox> boxes,
+                               const openvdb::math::Transform &transform,
+                               blender::Vector<blender::float3> &r_verts,
+                               blender::Vector<std::array<int, 3>> &r_tris)
+{
+  const int box_tris[12][3] = {
+      {0, 1, 4},
+      {4, 1, 5},
+      {0, 2, 1},
+      {1, 2, 3},
+      {1, 3, 5},
+      {5, 3, 7},
+      {6, 4, 5},
+      {7, 5, 6},
+      {2, 0, 4},
+      {2, 4, 6},
+      {3, 7, 2},
+      {6, 2, 7},
+  };
+
+  int vert_offset = r_verts.size();
+  int tri_offset = r_tris.size();
+
+  const int vert_amount = 8 * boxes.size();
+  const int tri_amount = 12 * boxes.size();
+
+  r_verts.resize(r_verts.size() + vert_amount);
+  r_tris.resize(r_tris.size() + tri_amount);
+  boxes_to_corner_points(boxes, transform, r_verts.as_mutable_span().take_back(vert_amount));
+
+  for (int i = 0; i < boxes.size(); i++) {
+    for (int j = 0; j < 12; j++) {
+      r_tris[tri_offset + j] = {vert_offset + box_tris[j][0],
+                                vert_offset + box_tris[j][1],
+                                vert_offset + box_tris[j][2]};
     }
+    vert_offset += 8;
+    tri_offset += 12;
   }
-};
+}
+
 #endif
 
 void BKE_volume_grid_wireframe(const Volume *volume,
@@ -274,79 +393,96 @@ void BKE_volume_grid_wireframe(const Volume *volume,
                                BKE_volume_wireframe_cb cb,
                                void *cb_userdata)
 {
-#ifdef WITH_OPENVDB
-  VolumeWireframe wireframe;
-
   if (volume->display.wireframe_type == VOLUME_WIREFRAME_NONE) {
-    /* Nothing. */
+    cb(cb_userdata, NULL, NULL, 0, 0);
+    return;
   }
-  else if (volume->display.wireframe_type == VOLUME_WIREFRAME_BOUNDS) {
-    /* Bounding box. */
-    float min[3], max[3];
-    BKE_volume_grid_bounds(volume_grid, min, max);
 
-    openvdb::BBoxd bbox(min, max);
-    wireframe.add_box(bbox);
+#ifdef WITH_OPENVDB
+  openvdb::GridBase::ConstPtr grid = BKE_volume_grid_openvdb_for_read(volume, volume_grid);
+
+  if (volume->display.wireframe_type == VOLUME_WIREFRAME_BOUNDS) {
+    /* Bounding box. */
+    openvdb::CoordBBox box;
+    blender::Vector<blender::float3> verts;
+    blender::Vector<std::array<int, 2>> edges;
+    if (grid->baseTree().evalLeafBoundingBox(box)) {
+      boxes_to_edge_mesh({box}, grid->transform(), verts, edges);
+    }
+    cb(cb_userdata,
+       (float(*)[3])verts.data(),
+       (int(*)[2])edges.data(),
+       verts.size(),
+       edges.size());
   }
   else {
-    /* Tree nodes. */
-    openvdb::GridBase::ConstPtr grid = BKE_volume_grid_openvdb_for_read(volume, volume_grid);
-    const bool points = (volume->display.wireframe_type == VOLUME_WIREFRAME_POINTS);
-    const bool coarse = (volume->display.wireframe_detail == VOLUME_WIREFRAME_COARSE);
-
-    switch (BKE_volume_grid_type(volume_grid)) {
-      case VOLUME_GRID_BOOLEAN: {
-        wireframe.add_grid<openvdb::BoolGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_FLOAT: {
-        wireframe.add_grid<openvdb::FloatGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_DOUBLE: {
-        wireframe.add_grid<openvdb::DoubleGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_INT: {
-        wireframe.add_grid<openvdb::Int32Grid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_INT64: {
-        wireframe.add_grid<openvdb::Int64Grid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_MASK: {
-        wireframe.add_grid<openvdb::MaskGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_VECTOR_FLOAT: {
-        wireframe.add_grid<openvdb::Vec3fGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_VECTOR_DOUBLE: {
-        wireframe.add_grid<openvdb::Vec3dGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_VECTOR_INT: {
-        wireframe.add_grid<openvdb::Vec3IGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_STRING: {
-        wireframe.add_grid<openvdb::StringGrid>(grid, points, coarse);
-        break;
-      }
-      case VOLUME_GRID_POINTS:
-      case VOLUME_GRID_UNKNOWN: {
-        break;
-      }
+    blender::Vector<openvdb::CoordBBox> boxes = get_bounding_boxes(
+        BKE_volume_grid_type(volume_grid),
+        grid,
+        volume->display.wireframe_detail == VOLUME_WIREFRAME_COARSE);
+
+    blender::Vector<blender::float3> verts;
+    blender::Vector<std::array<int, 2>> edges;
+
+    if (volume->display.wireframe_type == VOLUME_WIREFRAME_POINTS) {
+      verts.resize(boxes.size());
+      boxes_to_center_points(boxes, grid->transform(), verts);
     }
+    else {
+      boxes_to_edge_mesh(boxes, grid->transform(), verts, edges);
+    }
+
+    cb(cb_userdata,
+       (float(*)[3])verts.data(),
+       (int(*)[2])edges.data(),
+       verts.size(),
+       edges.size());
+  }
+
+#else
+  UNUSED_VARS(volume, volume_grid);
+  cb(cb_userdata, NULL, NULL, 0, 0);
+#endif
+}
+
+static void grow_triangles(blender::MutableSpan<blender::float3> verts,
+                           blender::Span<std::array<int, 3>> tris,
+                           const float factor)
+{
+  /* Compute the offset for every vertex based on the connected edges.
+   * This formula simply tries increases the length of all edges. */
+  blender::Array<blender::float3> offsets(verts.size(), {0, 0, 0});
+  for (const std::array<int, 3> &tri : tris) {
+    offsets[tri[0]] += factor * (2 * verts[tri[0]] - verts[tri[1]] - verts[tri[2]]);
+    offsets[tri[1]] += factor * (2 * verts[tri[1]] - verts[tri[0]] - verts[tri[2]]);
+    offsets[tri[2]] += factor * (2 * verts[tri[2]] - verts[tri[0]] - verts[tri[1]]);
+  }
+  /* Apply the computed offsets. */
+  for (const int i : verts.index_range()) {
+    verts[i] += offsets[i];
   }
+}
+
+void BKE_volume_grid_selection_surface(const Volume *volume,
+                                       VolumeGrid *volume_grid,
+                                       BKE_volume_selection_surface_cb cb,
+                                       void *cb_userdata)
+{
+#ifdef WITH_OPENVDB
+  openvdb::GridBase::ConstPtr grid = BKE_volume_grid_openvdb_for_read(volume, volume_grid);
+  blender::Vector<openvdb::CoordBBox> boxes = get_bounding_boxes(
+      BKE_volume_grid_type(volume_grid), grid, true);
+
+  blender::Vector<blender::float3> verts;
+  blender::Vector<std::array<int, 3>> tris;
+  boxes_to_cube_mesh(boxes, grid->transform(), verts, tris);
+
+  /* By slightly scaling the individual boxes up, we can avoid some artifacts when drawing the
+   * selection outline. */
+  const float offset_factor = 0.01f;
+  grow_triangles(verts, tris, offset_factor);
 
-  cb(cb_userdata,
-     (float(*)[3])wireframe.verts.data(),
-     (int(*)[2])wireframe.edges.data(),
-     wireframe.verts.size(),
-     wireframe.edges.size());
+  cb(cb_userdata, (float(*)[3])verts.data(), (int(*)[3])tris.data(), verts.size(), tris.size());
 #else
   UNUSED_VARS(volume, volume_grid);
   cb(cb_userdata, NULL, NULL, 0, 0);