[Bf-blender-cvs] [cd9b38005ed] newboolean: Performance tuning: early rejection of trivial intersections.
Howard Trickey
noreply at git.blender.org
Fri Jul 17 04:27:15 CEST 2020
Commit: cd9b38005eda0c75abe44f9698881408c2418e5a
Author: Howard Trickey
Date: Thu Jul 16 22:23:18 2020 -0400
Branches: newboolean
https://developer.blender.org/rBcd9b38005eda0c75abe44f9698881408c2418e5a
Performance tuning: early rejection of trivial intersections.
Starting to use floating filters to avoid expensive gmp operations
when possible. These changes speed up the sphere-sphere test with
n=64 to 5s (now 17 times slower than BMesh on this test, down from
100 times slower. But answer is correct.
Also make format.
===================================================================
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/makesrna/intern/rna_access_internal.h
M source/blender/modifiers/intern/MOD_boolean.c
M tests/gtests/blenlib/BLI_mesh_intersect_test.cc
===================================================================
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 8e6e1752fa3..15012ff9342 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -35,8 +35,17 @@
#include "BLI_mesh_intersect.hh"
+// #define PERFDEBUG
+
namespace blender::meshintersect {
+#ifdef PERFDEBUG
+static void perfdata_init(void);
+static void incperfcount(int countnum);
+static void doperfmax(int maxnum, int val);
+static void dump_perfdata(void);
+#endif
+
Vert::Vert(const mpq3 &mco, const double3 &dco, int id, int orig)
: co_exact(mco), co(dco), id(id), orig(orig)
{
@@ -883,6 +892,495 @@ struct ITT_value {
static std::ostream &operator<<(std::ostream &os, const ITT_value &itt);
+/* Project a 3d vert to a 2d one by eliding proj_axis. This does not create
+ * degeneracies as long as the projection axis is one where the corresponding
+ * component of the originating plane normal is non-zero.
+ */
+static mpq2 project_3d_to_2d(const mpq3 &p3d, int proj_axis)
+{
+ mpq2 p2d;
+ switch (proj_axis) {
+ case (0): {
+ p2d[0] = p3d[1];
+ p2d[1] = p3d[2];
+ } break;
+ case (1): {
+ p2d[0] = p3d[0];
+ p2d[1] = p3d[2];
+ } break;
+ case (2): {
+ p2d[0] = p3d[0];
+ p2d[1] = p3d[1];
+ } break;
+ default:
+ BLI_assert(false);
+ }
+ return p2d;
+}
+
+/* Is a point in the interior of a 2d triangle or on one of its
+ * edges but not either endpoint of the edge?
+ * orient[pi][i] is the orientation test of the point pi against
+ * the side of the triangle starting at index i.
+ * Assume the triangele is non-degenerate and CCW-oriented.
+ * Then answer is true if p is left of or on all three of triangle a's edges,
+ * and strictly left of at least on of them.
+ */
+static bool non_trivially_2d_point_in_tri(const int orients[3][3], int pi)
+{
+ int p_left_01 = orients[pi][0];
+ int p_left_12 = orients[pi][1];
+ int p_left_20 = orients[pi][2];
+ return (p_left_01 >= 0 && p_left_12 >= 0 && p_left_20 >= 0 &&
+ (p_left_01 + p_left_12 + p_left_20) >= 2);
+}
+
+/* Given orients as defined in non_trivially_2d_intersect, do the triangles
+ * overlap in a "hex" pattern? That is, the overlap region is a hexagon, which
+ * one gets by having, each point of one triangle being strictly rightof one
+ * edge of the other and strictly left of the other two edges; and vice versa.
+ */
+static bool non_trivially_2d_hex_overlap(int orients[2][3][3])
+{
+ for (int ab = 0; ab < 2; ++ab) {
+ for (int i = 0; i < 3; ++i) {
+ bool ok = orients[ab][i][0] + orients[ab][i][1] + orients[ab][i][2] == 1 &&
+ orients[ab][i][0] != 0 && orients[ab][i][1] != 0 && orients[i][2] != 0;
+ if (!ok) {
+ return false;
+ }
+ }
+ }
+ return true;
+}
+
+/* Given orients as defined in non_trivially_2d_intersect, do the triangles
+ * have one shared edge in a "folded-over" configuration?
+ * As well as a shared edge, the third vertex of one triangle needs to be
+ * rightof one and leftof the other two edges of the other triangle.
+ */
+static bool non_trivially_2d_shared_edge_overlap(int orients[2][3][3],
+ const mpq2 *a[3],
+ const mpq2 *b[3])
+{
+ for (int i = 0; i < 3; ++i) {
+ int in = (i + 1) % 3;
+ int inn = (i + 2) % 3;
+ for (int j = 0; j < 3; ++j) {
+ int jn = (j + 1) % 3;
+ int jnn = (j + 2) % 3;
+ if (*a[i] == *b[j] && *a[in] == *b[jn]) {
+ /* Edge from a[i] is shared with edge from b[j]. */
+ /* See if a[inn] is rightof or on one of the other edges of b.
+ * If it is on, then it has to be rightof or leftof the shared edge,
+ * depending on which edge it is.
+ */
+ if (orients[0][inn][jn] < 0 || orients[0][inn][jnn] < 0) {
+ return true;
+ }
+ if (orients[0][inn][jn] == 0 && orients[0][inn][j] == 1) {
+ return true;
+ }
+ if (orients[0][inn][jnn] == 0 && orients[0][inn][j] == -1) {
+ return true;
+ }
+ /* Similarly for b[jnn]. */
+ if (orients[1][jnn][in] < 0 || orients[1][jnn][inn] < 0) {
+ return true;
+ }
+ if (orients[1][jnn][in] == 0 && orients[1][jnn][i] == 1) {
+ return true;
+ }
+ if (orients[1][jnn][inn] == 0 && orients[1][jnn][i] == -1) {
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+}
+
+/* Are the triangles the same, perhaps with some permutation of vertices? */
+static bool same_triangles(const mpq2 *a[3], const mpq2 *b[3])
+{
+ for (int i = 0; i < 3; ++i) {
+ if (a[0] == b[i] && a[1] == b[(i + 1) % 3] && a[2] == b[(i + 2) % 3]) {
+ return true;
+ }
+ }
+ return false;
+}
+
+/* Do 2d triangles (a[0], a[1], a[2]) and (b[0], b[1], b2[2]) intersect at more than just shared
+ * vertices or a shared edge? This is true if any point of one tri is non-trivially inside the
+ * other. NO: that isn't quite sufficient: there is also the case where the verts are all mutually
+ * outside the other's triangle, but there is a hexagonal overlap region where they overlap.
+ */
+static bool non_trivially_2d_intersect(const mpq2 *a[3], const mpq2 *b[3])
+{
+ /* TODO: Could experiment with trying bounding box tests before these.
+ * TODO: Find a less expensive way than 18 orient tests to do this.
+ */
+ /* orients[0][ai][bi] is orient of point a[ai] compared to seg starting at b[bi].
+ * orients[1][bi][ai] is orient of point b[bi] compared to seg starting at a[ai].
+ */
+ int orients[2][3][3];
+ for (int ab = 0; ab < 2; ++ab) {
+ for (int ai = 0; ai < 3; ++ai) {
+ for (int bi = 0; bi < 3; ++bi) {
+ if (ab == 0) {
+ orients[0][ai][bi] = mpq2::orient2d(*b[bi], *b[(bi + 1) % 3], *a[ai]);
+ }
+ else {
+ orients[1][bi][ai] = mpq2::orient2d(*a[ai], *a[(ai + 1) % 3], *b[bi]);
+ }
+ }
+ }
+ }
+ return non_trivially_2d_point_in_tri(orients[0], 0) ||
+ non_trivially_2d_point_in_tri(orients[0], 1) ||
+ non_trivially_2d_point_in_tri(orients[0], 2) ||
+ non_trivially_2d_point_in_tri(orients[1], 0) ||
+ non_trivially_2d_point_in_tri(orients[1], 1) ||
+ non_trivially_2d_point_in_tri(orients[1], 2) || non_trivially_2d_hex_overlap(orients) ||
+ non_trivially_2d_shared_edge_overlap(orients, a, b) || same_triangles(a, b);
+ return true;
+}
+
+/* Does triangle t in tm non-trivially non-coplanar intersect any triangle
+ * in CoplanarCluster cl? Assume t is known to be in the same plane as all
+ * the triangles in cl, and that proj_axis is a good axis to project down
+ * to solve this problem in 2d.
+ */
+static bool non_trivially_coplanar_intersects(const Mesh &tm,
+ uint t,
+ const CoplanarCluster &cl,
+ int proj_axis)
+{
+ const Face &tri = *tm.face(t);
+ mpq2 v0 = project_3d_to_2d(tri[0]->co_exact, proj_axis);
+ mpq2 v1 = project_3d_to_2d(tri[1]->co_exact, proj_axis);
+ mpq2 v2 = project_3d_to_2d(tri[2]->co_exact, proj_axis);
+ if (mpq2::orient2d(v0, v1, v2) != 1) {
+ mpq2 tmp = v1;
+ v1 = v2;
+ v2 = tmp;
+ }
+ for (const uint cl_t : cl) {
+ const Face &cl_tri = *tm.face(cl_t);
+ mpq2 ctv0 = project_3d_to_2d(cl_tri[0]->co_exact, proj_axis);
+ mpq2 ctv1 = project_3d_to_2d(cl_tri[1]->co_exact, proj_axis);
+ mpq2 ctv2 = project_3d_to_2d(cl_tri[2]->co_exact, proj_axis);
+ if (mpq2::orient2d(ctv0, ctv1, ctv2) != 1) {
+ mpq2 tmp = ctv1;
+ ctv1 = ctv2;
+ ctv2 = tmp;
+ }
+ const mpq2 *v[] = {&v0, &v1, &v2};
+ const mpq2 *ctv[] = {&ctv0, &ctv1, &ctv2};
+ if (non_trivially_2d_intersect(v, ctv)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+/* Keeping this code for a while, but for now, almost all
+ * trivial intersects are found before calling intersect_tri_tri now.
+ */
+#if 0
+/* Do tri1 and tri2 intersect at all, and if so, is the intersection
+ * something other than a common vertex or a common edge?
+ * The itt value is the result of calling intersect_tri_tri on tri1, tri2.
+ */
+static bool non_trivial_intersect(const ITT_value &itt, Facep tri1, Facep tri2)
+{
+ if (itt.kind == INONE) {
+ return false;
+ }
+ Facep tris[2] = {tri1, tri2};
+ if (itt.kind == IPOINT) {
+ bool has_p_as_vert[2] {false, false};
+ for (int i = 0; i < 2; ++i) {
+ for (Vertp v : *tris[i]) {
+ if (itt.p1 == v->co_exact) {
+ has_p_as_vert[i] = true;
+ break;
+ }
+ }
+ }
+ return !(has_p_as_vert[0] && has_p_as_vert[1]);
+ }
+ if (itt.kind == ISEGMENT) {
+ bool has_seg_as_edge[2] = {false, false};
+ for (int i = 0; i < 2; ++i) {
+ const Face &t = *tris[i];
+ for (uint pos : t.index_range()) {
+ uint nextpos = t.next_pos(pos);
+ if ((itt.p1 == t[pos]->co_exact && itt.p2 == t[nextpos]->co_exact) ||
+ (itt.p2 == t[pos]->co_exact && itt.p1 == t[nextpos]->co_exact)) {
+ has_seg_as_edge[i] = true;
+ break;
+ }
+ }
+ }
+ return !(has_seg_as_edge[0] && has_seg_as_edge[1]);
+ }
+ BLI_assert(itt.kind == ICOPLANAR);
+ /* TODO: refactor this common code with code above. */
+ int proj_axis = mpq3::dominant_axis(tri1->plane.norm_exact);
+ mpq2 tri_2d[2][3];
+ for (int i = 0; i < 2; ++i) {
+ mpq2 v0 = project_3d_to_2d((*tris[i])[0]->co_exact, proj_axis);
+ mpq2 v1 = project_3d_to_2d((*tris[i])[1]->co_exact, proj_axis);
+ mpq2 v2 = project_3d_to_2d((*tris[i])[2]->co_exact, proj_axis);
+ if (mpq2::orient2d(v0, v1, v2) != 1) {
+ mpq2 tmp = v1;
+ v1 = v2;
+ v2 = tmp;
+ }
+ tri_2d[i][0] = v0;
+ tri_2d[i][1] = v1;
+ tri_2d[i][2] = v2;
+ }
+ const mpq2 *va[] = {&tri_2d[0][0], &tri_2d[0][1], &tri_2d[0][2]};
+ const mpq2 *vb[] = {&tri_2d[1][0], &tri_2d[1][1], &tri_2d[1][2]};
+ return non_trivially_2d_intersect(va, vb);
+}
+#endif
+
+/* The sup and index functions are defined in the paper:
+ * EXACT GEOMETRIC COMPUTATION USING CASC
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list