OpenVDB: Voxel Remesher

The voxel remesher introduces a new workflow for sculpting without any of the limitations of Dyntopo (no geometry errors or performance penalty when blocking shapes). It is also useful for simulations and 3D printing.

This commit includes:
- Voxel remesh operator, voxel size mesh property and general remesh flags.
- Paint mask reprojection.
- Geometry undo/redo for sculpt mode. This should support remesh operations as well as future tools that modify the topology of the sculpt in a single step, like trimming tools or mesh insert brushes.
- UI changes in the sculpt topbar and the mesh properties pannel.

Reviewed By: brecht

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

4 files changed, 247 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_remesh.h b/source/blender/blenkernel/BKE_remesh.h
new file mode 100644
index 00000000000..fd99af36bdc
--- /dev/null
+++ b/source/blender/blenkernel/BKE_remesh.h
@@ -0,0 +1,46 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2019 by Blender Foundation
+ * All rights reserved.
+ */
+#ifndef __BKE_REMESH_H__
+#define __BKE_REMESH_H__
+
+/** \file
+ * \ingroup bke
+ */
+
+#include "DNA_mesh_types.h"
+
+#ifdef WITH_OPENVDB
+#  include "openvdb_capi.h"
+#endif
+
+/* OpenVDB Voxel Remesher */
+#ifdef WITH_OPENVDB
+struct OpenVDBLevelSet *BKE_remesh_voxel_ovdb_mesh_to_level_set_create(
+    Mesh *mesh, struct OpenVDBTransform *transform);
+Mesh *BKE_remesh_voxel_ovdb_volume_to_mesh_nomain(struct OpenVDBLevelSet *level_set,
+                                                  double isovalue,
+                                                  double adaptivity,
+                                                  bool relax_disoriented_triangles);
+#endif
+Mesh *BKE_remesh_voxel_to_mesh_nomain(Mesh *mesh, float voxel_size);
+
+/* Data reprojection functions */
+void BKE_remesh_reproject_paint_mask(Mesh *target, Mesh *source);
+
+#endif /* __BKE_REMESH_H__ */
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index d9bd87d97b5..1f125b93b3f 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -178,6 +178,7 @@ set(SRC
   intern/pbvh.c
   intern/pbvh_bmesh.c
   intern/pointcache.c
+  intern/remesh.c
   intern/report.c
   intern/rigidbody.c
   intern/scene.c
@@ -317,6 +318,7 @@ set(SRC
   BKE_particle.h
   BKE_pbvh.h
   BKE_pointcache.h
+  BKE_remesh.h
   BKE_report.h
   BKE_rigidbody.h
   BKE_scene.h
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 7e755e54eaa..4f39d34574e 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -536,6 +536,7 @@ void BKE_mesh_init(Mesh *me)
   me->size[0] = me->size[1] = me->size[2] = 1.0;
   me->smoothresh = DEG2RADF(30);
   me->texflag = ME_AUTOSPACE;
+  me->remesh_voxel_size = 0.1f;
 
   CustomData_reset(&me->vdata);
   CustomData_reset(&me->edata);
diff --git a/source/blender/blenkernel/intern/remesh.c b/source/blender/blenkernel/intern/remesh.c
new file mode 100644
index 00000000000..4dd38c900c0
--- /dev/null
+++ b/source/blender/blenkernel/intern/remesh.c
@@ -0,0 +1,198 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2019 by Blender Foundation
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup bke
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+#include <time.h>
+#include <float.h>
+#include <ctype.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+
+#include "DNA_object_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "BKE_mesh.h"
+#include "BKE_mesh_runtime.h"
+#include "BKE_library.h"
+#include "BKE_customdata.h"
+#include "BKE_bvhutils.h"
+#include "BKE_remesh.h"
+
+#ifdef WITH_OPENVDB
+#  include "openvdb_capi.h"
+#endif
+
+#ifdef WITH_OPENVDB
+struct OpenVDBLevelSet *BKE_remesh_voxel_ovdb_mesh_to_level_set_create(
+    Mesh *mesh, struct OpenVDBTransform *transform)
+{
+  BKE_mesh_runtime_looptri_recalc(mesh);
+  const MLoopTri *looptri = BKE_mesh_runtime_looptri_ensure(mesh);
+  MVertTri *verttri = MEM_callocN(sizeof(*verttri) * BKE_mesh_runtime_looptri_len(mesh),
+                                  "remesh_looptri");
+  BKE_mesh_runtime_verttri_from_looptri(
+      verttri, mesh->mloop, looptri, BKE_mesh_runtime_looptri_len(mesh));
+
+  unsigned int totfaces = BKE_mesh_runtime_looptri_len(mesh);
+  unsigned int totverts = mesh->totvert;
+  float *verts = (float *)MEM_malloc_arrayN(totverts * 3, sizeof(float), "remesh_input_verts");
+  unsigned int *faces = (unsigned int *)MEM_malloc_arrayN(
+      totfaces * 3, sizeof(unsigned int), "remesh_intput_faces");
+
+  for (unsigned int i = 0; i < totverts; i++) {
+    MVert *mvert = &mesh->mvert[i];
+    verts[i * 3] = mvert->co[0];
+    verts[i * 3 + 1] = mvert->co[1];
+    verts[i * 3 + 2] = mvert->co[2];
+  }
+
+  for (unsigned int i = 0; i < totfaces; i++) {
+    MVertTri *vt = &verttri[i];
+    faces[i * 3] = vt->tri[0];
+    faces[i * 3 + 1] = vt->tri[1];
+    faces[i * 3 + 2] = vt->tri[2];
+  }
+
+  struct OpenVDBLevelSet *level_set = OpenVDBLevelSet_create(false, NULL);
+  OpenVDBLevelSet_mesh_to_level_set(level_set, verts, faces, totverts, totfaces, transform);
+
+  MEM_freeN(verts);
+  MEM_freeN(faces);
+  MEM_freeN(verttri);
+
+  return level_set;
+}
+
+Mesh *BKE_remesh_voxel_ovdb_volume_to_mesh_nomain(struct OpenVDBLevelSet *level_set,
+                                                  double isovalue,
+                                                  double adaptivity,
+                                                  bool relax_disoriented_triangles)
+{
+#  ifdef WITH_OPENVDB
+  struct OpenVDBVolumeToMeshData output_mesh;
+  OpenVDBLevelSet_volume_to_mesh(
+      level_set, &output_mesh, isovalue, adaptivity, relax_disoriented_triangles);
+#  endif
+
+  Mesh *mesh = BKE_mesh_new_nomain(
+      output_mesh.totvertices, 0, output_mesh.totquads + output_mesh.tottriangles, 0, 0);
+  int q = output_mesh.totquads;
+
+  for (int i = 0; i < output_mesh.totvertices; i++) {
+    float vco[3] = {output_mesh.vertices[i * 3],
+                    output_mesh.vertices[i * 3 + 1],
+                    output_mesh.vertices[i * 3 + 2]};
+    copy_v3_v3(mesh->mvert[i].co, vco);
+  }
+
+  for (int i = 0; i < output_mesh.totquads; i++) {
+    mesh->mface[i].v4 = output_mesh.quads[i * 4];
+    mesh->mface[i].v3 = output_mesh.quads[i * 4 + 1];
+    mesh->mface[i].v2 = output_mesh.quads[i * 4 + 2];
+    mesh->mface[i].v1 = output_mesh.quads[i * 4 + 3];
+  }
+
+  for (int i = 0; i < output_mesh.tottriangles; i++) {
+    mesh->mface[i + q].v4 = 0;
+    mesh->mface[i + q].v3 = output_mesh.triangles[i * 3];
+    mesh->mface[i + q].v2 = output_mesh.triangles[i * 3 + 1];
+    mesh->mface[i + q].v1 = output_mesh.triangles[i * 3 + 2];
+  }
+
+  BKE_mesh_calc_edges_tessface(mesh);
+  BKE_mesh_convert_mfaces_to_mpolys(mesh);
+  BKE_mesh_tessface_clear(mesh);
+  BKE_mesh_calc_normals(mesh);
+
+  MEM_freeN(output_mesh.quads);
+  MEM_freeN(output_mesh.vertices);
+
+  if (output_mesh.tottriangles > 0) {
+    MEM_freeN(output_mesh.triangles);
+  }
+
+  return mesh;
+}
+#endif
+
+Mesh *BKE_remesh_voxel_to_mesh_nomain(Mesh *mesh, float voxel_size)
+{
+  Mesh *new_mesh = NULL;
+#ifdef WITH_OPENVDB
+  struct OpenVDBLevelSet *level_set;
+  struct OpenVDBTransform *xform = OpenVDBTransform_create();
+  OpenVDBTransform_create_linear_transform(xform, (double)voxel_size);
+  level_set = BKE_remesh_voxel_ovdb_mesh_to_level_set_create(mesh, xform);
+  new_mesh = BKE_remesh_voxel_ovdb_volume_to_mesh_nomain(level_set, 0.0, 0.0, false);
+  OpenVDBLevelSet_free(level_set);
+  OpenVDBTransform_free(xform);
+#endif
+  return new_mesh;
+}
+
+void BKE_remesh_reproject_paint_mask(Mesh *target, Mesh *source)
+{
+  BVHTreeFromMesh bvhtree = {
+      .nearest_callback = NULL,
+  };
+  BKE_bvhtree_from_mesh_get(&bvhtree, source, BVHTREE_FROM_VERTS, 2);
+  MVert *target_verts = CustomData_get_layer(&target->vdata, CD_MVERT);
+
+  float *target_mask;
+  if (CustomData_has_layer(&target->vdata, CD_PAINT_MASK)) {
+    target_mask = CustomData_get_layer(&target->vdata, CD_PAINT_MASK);
+  }
+  else {
+    target_mask = CustomData_add_layer(
+        &target->vdata, CD_PAINT_MASK, CD_CALLOC, NULL, target->totvert);
+  }
+
+  float *source_mask;
+  if (CustomData_has_layer(&source->vdata, CD_PAINT_MASK)) {
+    source_mask = CustomData_get_layer(&source->vdata, CD_PAINT_MASK);
+  }
+  else {
+    source_mask = CustomData_add_layer(
+        &source->vdata, CD_PAINT_MASK, CD_CALLOC, NULL, source->totvert);
+  }
+
+  for (int i = 0; i < target->totvert; i++) {
+    float from_co[3];
+    BVHTreeNearest nearest;
+    nearest.index = -1;
+    nearest.dist_sq = FLT_MAX;
+    copy_v3_v3(from_co, target_verts[i].co);
+    BLI_bvhtree_find_nearest(bvhtree.tree, from_co, &nearest, bvhtree.nearest_callback, &bvhtree);
+    if (nearest.index != -1) {
+      target_mask[i] = source_mask[nearest.index];
+    }
+  }
+  free_bvhtree_from_mesh(&bvhtree);
+}