Merge newboolean branch into master.

This is for design task T67744, Boolean Redesign.
It adds a choice of solver to the Boolean modifier and the
Intersect (Boolean) and Intersect (Knife) tools.
The 'Fast' choice is the current Bmesh boolean.
The new 'Exact' choice is a more advanced algorithm that supports
overlapping geometry and uses more robust calculations, but is
slower than the Fast choice.
The default with this commit is set to 'Exact'. We can decide before
the 2.91 release whether or not this is the right choice, but this
choice now will get us more testing and feedback on the new code.

1 files changed, 72 insertions, 13 deletions

diff --git a/source/blender/blenlib/BLI_delaunay_2d.h b/source/blender/blenlib/BLI_delaunay_2d.h
index a826a6b2677..7027477ac7f 100644
--- a/source/blender/blenlib/BLI_delaunay_2d.h
+++ b/source/blender/blenlib/BLI_delaunay_2d.h
@@ -18,6 +18,9 @@
 
 /** \file
  * \ingroup bli
+ *
+ *  This header file contains both a C interface and a C++ interface
+ *  to the 2D Constrained Delaunay Triangulation library routine.
  */
 
 #ifdef __cplusplus
@@ -107,11 +110,6 @@ extern "C" {
  * If zero is supplied for epsilon, an internal value of 1e-8 used
  * instead, since this code will not work correctly if it is not allowed
  * to merge "too near" vertices.
- *
- * Normally, if epsilon is non-zero, there is an "input modify" pass which
- * checks to see if some vertices are within epsilon of other edges, and
- * snapping them to those edges if so. You can skip this pass by setting
- * skip_input_modify to true. (This is also useful in some unit tests.)
  */
 typedef struct CDT_input {
   int verts_len;
@@ -123,7 +121,6 @@ typedef struct CDT_input {
   int *faces_start_table;
   int *faces_len_table;
   float epsilon;
-  bool skip_input_modify;
 } CDT_input;
 
 /**
@@ -150,12 +147,9 @@ typedef struct CDT_input {
  * - faces_orig, faces_orig_start_table, faces_orig_len_table
  *
  * For edges, the edges_orig triple can also say which original face
- * edge is part of a given output edge. If an index in edges_orig
- * is greater than the input's edges_len, then subtract input's edges_len
- * from it to some number i: then the face edge that starts from the
- * input vertex at input's faces[i] is the corresponding face edge.
- * for convenience, face_edge_offset in the result will be the input's
- * edges_len, so that this conversion can be easily done by the caller.
+ * edge is part of a given output edge. See the comment below
+ * on the C++ interface for how to decode the entries in the edges_orig
+ * table.
  */
 typedef struct CDT_result {
   int verts_len;
@@ -207,4 +201,69 @@ void BLI_delaunay_2d_cdt_free(CDT_result *result);
 
 #ifdef __cplusplus
 }
-#endif
+
+/* C++ Interface. */
+
+#  include "BLI_array.hh"
+#  include "BLI_double2.hh"
+#  include "BLI_math_mpq.hh"
+#  include "BLI_mpq2.hh"
+#  include "BLI_vector.hh"
+
+namespace blender::meshintersect {
+
+/* vec2<Arith_t> is a 2d vector with Arith_t as the type for coordinates. */
+template<typename Arith_t> struct vec2_impl;
+template<> struct vec2_impl<double> {
+  typedef double2 type;
+};
+
+#  ifdef WITH_GMP
+template<> struct vec2_impl<mpq_class> {
+  typedef mpq2 type;
+};
+#  endif
+
+template<typename Arith_t> using vec2 = typename vec2_impl<Arith_t>::type;
+
+template<typename Arith_t> class CDT_input {
+ public:
+  Array<vec2<Arith_t>> vert;
+  Array<std::pair<int, int>> edge;
+  Array<Vector<int>> face;
+  Arith_t epsilon{0};
+};
+
+template<typename Arith_t> class CDT_result {
+ public:
+  Array<vec2<Arith_t>> vert;
+  Array<std::pair<int, int>> edge;
+  Array<Vector<int>> face;
+  /** For each output vert, which input verts correspond to it? */
+  Array<Vector<int>> vert_orig;
+  /**
+   * For each output edge, which input edges does it overlap?
+   * The input edge ids are encoded as follows:
+   *   if the value is less than face_edge_offset, then it is
+   *      an index into the input edge[] array.
+   *   else let (a, b) = the quotient and remainder of dividing
+   *      the edge index by face_edge_offset; "a" will be the input face + 1,
+   *      and "b" will be a position within that face.
+   */
+  Array<Vector<int>> edge_orig;
+  /** For each output face, which original faces does it overlap? */
+  Array<Vector<int>> face_orig;
+  /** Used to encode edge_orig (see above). */
+  int face_edge_offset;
+};
+
+CDT_result<double> delaunay_2d_calc(const CDT_input<double> &input, CDT_output_type output_type);
+
+#  ifdef WITH_GMP
+CDT_result<mpq_class> delaunay_2d_calc(const CDT_input<mpq_class> &input,
+                                       CDT_output_type output_type);
+#  endif
+
+} /* namespace blender::meshintersect */
+
+#endif /* __cplusplus */