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, 193 insertions, 0 deletions

diff --git a/source/blender/blenlib/intern/math_vec.cc b/source/blender/blenlib/intern/math_vec.cc
new file mode 100644
index 00000000000..865a1986214
--- /dev/null
+++ b/source/blender/blenlib/intern/math_vec.cc
@@ -0,0 +1,193 @@
+/*
+ * 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.
+ */
+
+/** \file
+ * \ingroup bli
+ */
+
+#include "BLI_double2.hh"
+#include "BLI_double3.hh"
+#include "BLI_float2.hh"
+#include "BLI_float3.hh"
+#include "BLI_hash.hh"
+#include "BLI_math_mpq.hh"
+#include "BLI_mpq2.hh"
+#include "BLI_mpq3.hh"
+#include "BLI_span.hh"
+#include "BLI_utildefines.h"
+
+namespace blender {
+
+float2::isect_result float2::isect_seg_seg(const float2 &v1,
+                                           const float2 &v2,
+                                           const float2 &v3,
+                                           const float2 &v4)
+{
+  float2::isect_result ans;
+  float div = (v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]);
+  if (div == 0.0f) {
+    ans.lambda = 0.0f;
+    ans.mu = 0.0f;
+    ans.kind = float2::isect_result::LINE_LINE_COLINEAR;
+  }
+  else {
+    ans.lambda = ((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
+    ans.mu = ((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
+    if (ans.lambda >= 0.0f && ans.lambda <= 1.0f && ans.mu >= 0.0f && ans.mu <= 1.0f) {
+      if (ans.lambda == 0.0f || ans.lambda == 1.0f || ans.mu == 0.0f || ans.mu == 1.0f) {
+        ans.kind = float2::isect_result::LINE_LINE_EXACT;
+      }
+      else {
+        ans.kind = float2::isect_result::LINE_LINE_CROSS;
+      }
+    }
+    else {
+      ans.kind = float2::isect_result::LINE_LINE_NONE;
+    }
+  }
+  return ans;
+}
+
+double2::isect_result double2::isect_seg_seg(const double2 &v1,
+                                             const double2 &v2,
+                                             const double2 &v3,
+                                             const double2 &v4)
+{
+  double2::isect_result ans;
+  double div = (v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]);
+  if (div == 0.0) {
+    ans.lambda = 0.0;
+    ans.mu = 0.0;
+    ans.kind = double2::isect_result::LINE_LINE_COLINEAR;
+  }
+  else {
+    ans.lambda = ((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
+    ans.mu = ((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
+    if (ans.lambda >= 0.0 && ans.lambda <= 1.0 && ans.mu >= 0.0 && ans.mu <= 1.0) {
+      if (ans.lambda == 0.0 || ans.lambda == 1.0 || ans.mu == 0.0 || ans.mu == 1.0) {
+        ans.kind = double2::isect_result::LINE_LINE_EXACT;
+      }
+      else {
+        ans.kind = double2::isect_result::LINE_LINE_CROSS;
+      }
+    }
+    else {
+      ans.kind = double2::isect_result::LINE_LINE_NONE;
+    }
+  }
+  return ans;
+}
+
+#ifdef WITH_GMP
+mpq2::isect_result mpq2::isect_seg_seg(const mpq2 &v1,
+                                       const mpq2 &v2,
+                                       const mpq2 &v3,
+                                       const mpq2 &v4)
+{
+  mpq2::isect_result ans;
+  mpq_class div = (v2[0] - v1[0]) * (v4[1] - v3[1]) - (v2[1] - v1[1]) * (v4[0] - v3[0]);
+  if (div == 0.0) {
+    ans.lambda = 0.0;
+    ans.mu = 0.0;
+    ans.kind = mpq2::isect_result::LINE_LINE_COLINEAR;
+  }
+  else {
+    ans.lambda = ((v1[1] - v3[1]) * (v4[0] - v3[0]) - (v1[0] - v3[0]) * (v4[1] - v3[1])) / div;
+    ans.mu = ((v1[1] - v3[1]) * (v2[0] - v1[0]) - (v1[0] - v3[0]) * (v2[1] - v1[1])) / div;
+    if (ans.lambda >= 0 && ans.lambda <= 1 && ans.mu >= 0 && ans.mu <= 1) {
+      if (ans.lambda == 0 || ans.lambda == 1 || ans.mu == 0 || ans.mu == 1) {
+        ans.kind = mpq2::isect_result::LINE_LINE_EXACT;
+      }
+      else {
+        ans.kind = mpq2::isect_result::LINE_LINE_CROSS;
+      }
+    }
+    else {
+      ans.kind = mpq2::isect_result::LINE_LINE_NONE;
+    }
+  }
+  return ans;
+}
+#endif
+
+double3 double3::cross_poly(Span<double3> poly)
+{
+  /* Newell's Method. */
+  int nv = static_cast<int>(poly.size());
+  if (nv < 3) {
+    return double3(0, 0, 0);
+  }
+  const double3 *v_prev = &poly[nv - 1];
+  const double3 *v_curr = &poly[0];
+  double3 n(0, 0, 0);
+  for (int i = 0; i < nv;) {
+    n[0] = n[0] + ((*v_prev)[1] - (*v_curr)[1]) * ((*v_prev)[2] + (*v_curr)[2]);
+    n[1] = n[1] + ((*v_prev)[2] - (*v_curr)[2]) * ((*v_prev)[0] + (*v_curr)[0]);
+    n[2] = n[2] + ((*v_prev)[0] - (*v_curr)[0]) * ((*v_prev)[1] + (*v_curr)[1]);
+    v_prev = v_curr;
+    ++i;
+    if (i < nv) {
+      v_curr = &poly[i];
+    }
+  }
+  return n;
+}
+
+mpq3 mpq3::cross_poly(Span<mpq3> poly)
+{
+  /* Newell's Method. */
+  int nv = static_cast<int>(poly.size());
+  if (nv < 3) {
+    return mpq3(0);
+  }
+  const mpq3 *v_prev = &poly[nv - 1];
+  const mpq3 *v_curr = &poly[0];
+  mpq3 n(0);
+  for (int i = 0; i < nv;) {
+    n[0] = n[0] + ((*v_prev)[1] - (*v_curr)[1]) * ((*v_prev)[2] + (*v_curr)[2]);
+    n[1] = n[1] + ((*v_prev)[2] - (*v_curr)[2]) * ((*v_prev)[0] + (*v_curr)[0]);
+    n[2] = n[2] + ((*v_prev)[0] - (*v_curr)[0]) * ((*v_prev)[1] + (*v_curr)[1]);
+    v_prev = v_curr;
+    ++i;
+    if (i < nv) {
+      v_curr = &poly[i];
+    }
+  }
+  return n;
+}
+
+uint64_t hash_mpq_class(const mpq_class &value)
+{
+  /* TODO: better/faster implementation of this. */
+  return DefaultHash<float>{}(static_cast<float>(value.get_d()));
+}
+
+uint64_t mpq2::hash() const
+{
+  uint64_t hashx = hash_mpq_class(this->x);
+  uint64_t hashy = hash_mpq_class(this->y);
+  return hashx ^ (hashy * 33);
+}
+
+uint64_t mpq3::hash() const
+{
+  uint64_t hashx = hash_mpq_class(this->x);
+  uint64_t hashy = hash_mpq_class(this->y);
+  uint64_t hashz = hash_mpq_class(this->z);
+  return hashx ^ (hashy * 33) ^ (hashz * 33 * 37);
+}
+
+}  // namespace blender