Geometry Nodes: Add Convex Hull Node

This commit adds a node to output the convex hull of any input geometry
as a mesh, which is an enclosing geometry around a set of points.
All geometry types are supported, besides volumes.

The code supports operating on instances to avoid copying all input
geometry before the operation. The implementation uses the same backend
as the operation in edit mode, but uses Mesh directly instead of BMesh.

Attribute transfer is not supported currently, but would be a point of
improvement for the future if it can work in a predictable way on
different geometry input types.

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

2 files changed, 36 insertions, 0 deletions

diff --git a/intern/rigidbody/RBI_hull_api.h b/intern/rigidbody/RBI_hull_api.h
index 9d2dc5034db..3bd216b92cb 100644
--- a/intern/rigidbody/RBI_hull_api.h
+++ b/intern/rigidbody/RBI_hull_api.h
@@ -31,9 +31,13 @@ typedef struct plConvexHull__ {
 plConvexHull plConvexHullCompute(float (*coords)[3], int count);
 void plConvexHullDelete(plConvexHull hull);
 int plConvexHullNumVertices(plConvexHull hull);
+int plConvexHullNumLoops(plConvexHull hull);
 int plConvexHullNumFaces(plConvexHull hull);
 void plConvexHullGetVertex(plConvexHull hull, int n, float coords[3], int *original_index);
+void plConvexHullGetLoop(plConvexHull hull, int n, int *v_from, int *v_to);
+int plConvexHullGetReversedLoopIndex(plConvexHull hull, int n);
 int plConvexHullGetFaceSize(plConvexHull hull, int n);
+void plConvexHullGetFaceLoops(plConvexHull hull, int n, int *loops);
 void plConvexHullGetFaceVertices(plConvexHull hull, int n, int *vertices);
 
 #ifdef __cplusplus
diff --git a/intern/rigidbody/rb_convex_hull_api.cpp b/intern/rigidbody/rb_convex_hull_api.cpp
index c5893a4c808..03e7580a12b 100644
--- a/intern/rigidbody/rb_convex_hull_api.cpp
+++ b/intern/rigidbody/rb_convex_hull_api.cpp
@@ -39,6 +39,12 @@ int plConvexHullNumVertices(plConvexHull hull)
   return computer->vertices.size();
 }
 
+int plConvexHullNumLoops(plConvexHull hull)
+{
+  btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
+  return computer->edges.size();
+}
+
 int plConvexHullNumFaces(plConvexHull hull)
 {
   btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
@@ -55,6 +61,19 @@ void plConvexHullGetVertex(plConvexHull hull, int n, float coords[3], int *origi
   (*original_index) = computer->original_vertex_index[n];
 }
 
+void plConvexHullGetLoop(plConvexHull hull, int n, int *v_from, int *v_to)
+{
+  btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
+  (*v_from) = computer->edges[n].getSourceVertex();
+  (*v_to) = computer->edges[n].getTargetVertex();
+}
+
+int plConvexHullGetReversedLoopIndex(plConvexHull hull, int n)
+{
+  btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
+  return computer->edges[n].getReverseEdge() - &computer->edges[0];
+}
+
 int plConvexHullGetFaceSize(plConvexHull hull, int n)
 {
   btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
@@ -69,6 +88,19 @@ int plConvexHullGetFaceSize(plConvexHull hull, int n)
   return count;
 }
 
+void plConvexHullGetFaceLoops(plConvexHull hull, int n, int *loops)
+{
+  btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));
+  const btConvexHullComputer::Edge *e_orig, *e;
+  int count;
+
+  for (e_orig = &computer->edges[computer->faces[n]], e = e_orig, count = 0;
+       count == 0 || e != e_orig;
+       e = e->getNextEdgeOfFace(), count++) {
+    loops[count] = e - &computer->edges[0];
+  }
+}
+
 void plConvexHullGetFaceVertices(plConvexHull hull, int n, int *vertices)
 {
   btConvexHullComputer *computer(reinterpret_cast<btConvexHullComputer *>(hull));