Commit: 77242de80e483d89fd72fac1cc5a80aa9fc0ab05
Author: Howard Trickey
Date: Wed Aug 26 06:59:58 2020 -0400
Branches: newboolean
https://developer.blender.org/rB77242de80e483d89fd72fac1cc5a80aa9fc0ab05
Refactor to defer building Plane for Faces until later.
This is a precursor to a big speed optimization in the "finding clusters"
code. Right now there is no speedup, maybe even a bit of a slowdown,
but following commits should lead to nice speed increases.
===================================================================
M release/datafiles/locale
M release/scripts/addons
M source/blender/blenlib/BLI_double3.hh
M source/blender/blenlib/BLI_mesh_intersect.hh
M source/blender/blenlib/intern/math_vec.cc
M source/blender/blenlib/intern/mesh_boolean.cc
M source/blender/blenlib/intern/mesh_intersect.cc
M source/blender/blenlib/tests/BLI_mesh_boolean_test.cc
M source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
M source/blender/bmesh/tools/bmesh_boolean.cc
M source/tools
===================================================================
diff --git a/release/datafiles/locale b/release/datafiles/locale
index bc6623180ae..260b439d0fb 160000
--- a/release/datafiles/locale
+++ b/release/datafiles/locale
@@ -1 +1 @@
-Subproject commit bc6623180aee561cba84ac11f5959b31016612ef
+Subproject commit 260b439d0fb15e3cd1efe5c120cf24f91d13d855
diff --git a/release/scripts/addons b/release/scripts/addons
index 1bc96468a14..26ba60a3f0c 160000
--- a/release/scripts/addons
+++ b/release/scripts/addons
@@ -1 +1 @@
-Subproject commit 1bc96468a144750348ea6b134d4aaf457d7cc6cf
+Subproject commit 26ba60a3f0c8dd229a0ac8f36190490a1ebf5145
diff --git a/source/blender/blenlib/BLI_double3.hh
b/source/blender/blenlib/BLI_double3.hh
index fb9823c3ec0..4884b8f287c 100644
--- a/source/blender/blenlib/BLI_double3.hh
+++ b/source/blender/blenlib/BLI_double3.hh
@@ -19,6 +19,7 @@
#include <iostream>
#include "BLI_math_vector.h"
+#include "BLI_span.hh"
namespace blender {
@@ -226,6 +227,16 @@ struct double3 {
return double3(fabs(a.x), fabs(a.y), fabs(a.z));
}
+ static int dominant_axis(const double3 &a)
+ {
+ double x = (a.x >= 0) ? a.x : -a.x;
+ double y = (a.y >= 0) ? a.y : -a.y;
+ double z = (a.z >= 0) ? a.z : -a.z;
+ return ((x > y) ? ((x > z) ? 0 : 2) : ((y > z) ? 1 : 2));
+ }
+
+ static double3 cross_poly(Span<double3> poly);
+
/* orient3d gives the exact result, using multiprecision artihmetic when
result
* is close to zero. orient3d_fast just uses double arithmetic, so may be
* wrong if the answer is very close to zero.
diff --git a/source/blender/blenlib/BLI_mesh_intersect.hh
b/source/blender/blenlib/BLI_mesh_intersect.hh
index d7cf0b01823..6e2a9a6424b 100644
--- a/source/blender/blenlib/BLI_mesh_intersect.hh
+++ b/source/blender/blenlib/BLI_mesh_intersect.hh
@@ -74,7 +74,12 @@ struct Vert {
std::ostream &operator<<(std::ostream &os, const Vert *v);
-/* A Plane whose equation is dot(nprm, p) + d = 0. */
+/* A Plane whose equation is dot(norm, p) + d = 0.
+ * The norm and d fields are always present, but the norm_exact
+ * and d_exact fields may be lazily populated. Since we don't
+ * store degenerate planes, we can tell if a the exact versions
+ * are not populated yet by having norm_exact == 0.
+ */
struct Plane {
mpq3 norm_exact;
mpq_class d_exact;
@@ -83,6 +88,7 @@ struct Plane {
Plane() = default;
Plane(const mpq3 &norm_exact, const mpq_class &d_exact);
+ Plane(const double3 &norm, const double d);
/* Test equality on the exact fields. */
bool operator==(const Plane &other) const;
@@ -91,9 +97,11 @@ struct Plane {
uint64_t hash() const;
void make_canonical();
+ bool exact_populated() const;
+ void populate_exact();
};
-std::ostream &operator<<(std::ostream &os, const Plane &plane);
+std::ostream &operator<<(std::ostream &os, const Plane *plane);
/* A Face has a sequence of Verts that for a CCW ordering around them.
* Faces carry an index, created at allocation time, useful for making
@@ -107,13 +115,14 @@ std::ostream &operator<<(std::ostream &os, const Plane
&plane);
* for each edge whether or not it is the result of intersecting
* with another face in the intersect algorithm.
* Since the intersect algorithm needs the plane for each face,
- * a Face also stores the Plane of the face.
+ * a Face also stores the Plane of the face, but this is only
+ * populate later because not all faces will be intersected.
*/
-struct Face {
+struct Face : NonCopyable {
Array<const Vert *> vert;
Array<int> edge_orig;
Array<bool> is_intersect;
- Plane plane;
+ Plane *plane = nullptr;
int id = NO_INDEX;
int orig = NO_INDEX;
@@ -122,7 +131,7 @@ struct Face {
Face() = default;
Face(Span<const Vert *> verts, int id, int orig, Span<int> edge_origs,
Span<bool> is_intersect);
Face(Span<const Vert *> verts, int id, int orig);
- ~Face() = default;
+ ~Face();
bool is_tri() const
{
@@ -169,6 +178,13 @@ struct Face {
{
return IndexRange(vert.size());
}
+
+ void populate_plane(bool need_exact);
+
+ bool plane_populated() const
+ {
+ return plane != nullptr;
+ }
};
std::ostream &operator<<(std::ostream &os, const Face *f);
@@ -203,12 +219,12 @@ class IMeshArena : NonCopyable, NonMovable {
const Vert *add_or_find_vert(const mpq3 &co, int orig);
const Vert *add_or_find_vert(const double3 &co, int orig);
- const Face *add_face(Span<const Vert *> verts,
- int orig,
- Span<int> edge_origs,
- Span<bool> is_intersect);
- const Face *add_face(Span<const Vert *> verts, int orig, Span<int>
edge_origs);
- const Face *add_face(Span<const Vert *> verts, int orig);
+ Face *add_face(Span<const Vert *> verts,
+ int orig,
+ Span<int> edge_origs,
+ Span<bool> is_intersect);
+ Face *add_face(Span<const Vert *> verts, int orig, Span<int> edge_origs);
+ Face *add_face(Span<const Vert *> verts, int orig);
/* The following return nullptr if not found. */
const Vert *find_vert(const mpq3 &co) const;
@@ -226,19 +242,19 @@ class IMeshArena : NonCopyable, NonMovable {
*/
class IMesh {
- Array<const Face *> face_;
+ Array<Face *> face_; /* Not const so can lazily populate
planes. */
Array<const Vert *> vert_; /* Only valid if vert_populated_. */
Map<const Vert *, int> vert_to_index_; /* Only valid if vert_populated_. */
bool vert_populated_ = false;
public:
IMesh() = default;
- IMesh(Span<const Face *> faces) : face_(faces)
+ IMesh(Span<Face *> faces) : face_(faces)
{
}
- void set_faces(Span<const Face *> faces);
- const Face *face(int index) const
+ void set_faces(Span<Face *> faces);
+ Face *face(int index) const
{
return face_[index];
}
@@ -297,9 +313,9 @@ class IMesh {
return Span<const Vert *>(vert_);
}
- Span<const Face *> faces() const
+ Span<Face *> faces() const
{
- return Span<const Face *>(face_);
+ return Span<Face *>(face_);
}
/* Replace face at given index with one that elides the
diff --git a/source/blender/blenlib/intern/math_vec.cc
b/source/blender/blenlib/intern/math_vec.cc
index 501b26da862..cfeee6266a9 100644
--- a/source/blender/blenlib/intern/math_vec.cc
+++ b/source/blender/blenlib/intern/math_vec.cc
@@ -122,6 +122,29 @@ mpq2::isect_result mpq2::isect_seg_seg(const mpq2 &v1,
return ans;
}
+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. */
diff --git a/source/blender/blenlib/intern/mesh_boolean.cc
b/source/blender/blenlib/intern/mesh_boolean.cc
index aba7102e2dd..a628cfa500f 100644
--- a/source/blender/blenlib/intern/mesh_boolean.cc
+++ b/source/blender/blenlib/intern/mesh_boolean.cc
@@ -1778,7 +1778,7 @@ static Vector<ComponentContainer>
find_component_containers(int comp,
for (int p : components[comp_other]) {
const Patch &patch = pinfo.patch(p);
for (int t : patch.tris()) {
- const Face tri = *tm.face(t);
+ const Face &tri = *tm.face(t);
if (dbg_level > 1) {
std::cout << "tri " << t << " = " << &tri << "\n";
}
@@ -2062,7 +2062,7 @@ static bool apply_bool_op(BoolOpType bool_optype, const
Array<int> &winding)
* triangles that are part of stacks of geometrically identical
* triangles enclosing zero volume cells.
*/
-static void extract_zero_volume_cell_tris(Vector<const Face *> &r_tris,
+static void extract_zero_volume_cell_tris(Vector<Face *> &r_tris,
const IMesh &tm_subdivided,
const PatchesInfo &pinfo,
const CellsInfo &cinfo,
@@ -2170,7 +2170,7 @@ static void extract_zero_volume_cell_tris(Vector<const
Face *> &r_tris,
tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
std::array<bool, 3> flipped_is_intersect = {
tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
- const Face *flipped_f = arena->add_face(
+ Face *flipped_f = arena->add_face(
flipped_vs, f->orig, flipped_e_origs, flipped_is_intersect);
r_tris.append(flipped_f);
}
@@ -2197,7 +2197,7 @@ static IMesh extract_from_in_output_volume_diffs(const
IMesh &tm_subdivided,
if (dbg_level > 0) {
std::cout << "\nEXTRACT_FROM_FLAG_DIFFS\n";
}
- Vector<const Face *> out_tris;
+ Vector<Face *> out_tris;
out_tris.reserve(tm_subdivided.face_size());
bool any_zero_volume_cell = false;
for (int t : tm_subdivided.face_index_range()) {
@@ -2219,15 +2219,15 @@ static IMesh extract_from_in_output_volume_diffs(const
IMesh &tm_subdivided,
if (dbg_level > 0) {
std::cout << "need tri " << t << " flip=" << flip << "\n";
}
- const Face *f = tm_subdivided.face(t);
+ Face *f = tm_subdivided.face(t);
if (flip) {
- const Face &tri = *f;
+ Face &tri = *f;
std::array<const Vert *, 3> flipped_vs = {tri[0], tri[2], tri[1]};
std::array<int, 3> flipped_e_origs = {
tri.edge_orig[2], tri.edge_orig[1], tri.edge_orig[0]};
std::array<bool, 3> flipped_is_intersect = {
tri.is_intersect[2], tri.is_intersect[1], tri.is_intersect[0]};
- const Face *flipped_f = arena->add_face(
+ Face *flipped_f = arena->add_face(
flipped_vs, f->orig, flipped_e_origs, flipped_is_intersect);
out_tris.append(flipped_f);
}
@@ -2366,7 +2366,7 @@ static IMesh gwn_boolean(const IMesh &tm,
std::cout << "GWN_BOOLEAN\n";
}
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
