[Bf-blender-cvs] [eb0231f20f3] newboolean: Handle cases of nested meshes.
Howard Trickey
noreply at git.blender.org
Sun Aug 2 00:26:06 CEST 2020
Commit: eb0231f20f3a5eff366787e9f2991d50be691bca
Author: Howard Trickey
Date: Sat Aug 1 18:24:16 2020 -0400
Branches: newboolean
https://developer.blender.org/rBeb0231f20f3a5eff366787e9f2991d50be691bca
Handle cases of nested meshes.
This fixes some "implement me" crashes and also case where one
moves a cutter completely inside the cut mesh.
Also fixed a bug in the implementation of mpq3::distance_squared.
===================================================================
M source/blender/blenlib/BLI_mpq3.hh
M source/blender/blenlib/intern/boolean.cc
M tests/gtests/blenlib/BLI_boolean_test.cc
===================================================================
diff --git a/source/blender/blenlib/BLI_mpq3.hh b/source/blender/blenlib/BLI_mpq3.hh
index 9f507ed44b0..cfe75b1d4c5 100644
--- a/source/blender/blenlib/BLI_mpq3.hh
+++ b/source/blender/blenlib/BLI_mpq3.hh
@@ -232,7 +232,8 @@ struct mpq3 {
static mpq_class distance_squared(const mpq3 &a, const mpq3 &b)
{
- return mpq3::dot(a, b);
+ mpq3 diff(a.x - b.x, a.y - b.y, a.z - b.z);
+ return mpq3::dot(diff, diff);
}
static mpq3 interpolate(const mpq3 &a, const mpq3 &b, mpq_class t)
diff --git a/source/blender/blenlib/intern/boolean.cc b/source/blender/blenlib/intern/boolean.cc
index 6372c86b153..6f5dfd0652b 100644
--- a/source/blender/blenlib/intern/boolean.cc
+++ b/source/blender/blenlib/intern/boolean.cc
@@ -161,7 +161,7 @@ TriMeshTopology::TriMeshTopology(const Mesh &tm)
{
const int dbg_level = 0;
if (dbg_level > 0) {
- std::cout << "TriMeshTopology construction\n";
+ std::cout << "TRIMESHTOPOLOGY CONSTRUCTION\n";
}
/* If everything were manifold, F+V-E=2 and E=3F/2.
* So an likely overestimate, allowing for non-manifoldness, is E=2F and V=F.
@@ -255,6 +255,7 @@ class Patch {
int cell_above{NO_INDEX};
int cell_below{NO_INDEX};
+ int component{NO_INDEX};
};
static std::ostream &operator<<(std::ostream &os, const Patch &patch)
@@ -364,6 +365,7 @@ static bool apply_bool_op(int bool_optype, const Array<int> &winding);
class Cell {
Vector<int> patches_;
Array<int> winding_;
+ int merged_to_{NO_INDEX};
bool winding_assigned_{false};
/* flag_ will be true when this cell should be in the output volume. */
bool flag_{false};
@@ -379,6 +381,11 @@ class Cell {
patches_.append(p);
}
+ void add_patch_non_duplicates(int p)
+ {
+ patches_.append_non_duplicates(p);
+ }
+
const Vector<int> &patches() const
{
return patches_;
@@ -423,6 +430,16 @@ class Cell {
return zero_volume_;
}
+ int merged_to() const
+ {
+ return merged_to_;
+ }
+
+ void set_merged_to(int c)
+ {
+ merged_to_ = c;
+ }
+
/* Call this when it is possible that this Cell has zero volume,
* and if it does, set zero_volume_ to true.
*/
@@ -528,6 +545,30 @@ class CellsInfo {
}
};
+static void merge_cells(int merge_to, int merge_from, CellsInfo &cinfo, PatchesInfo &pinfo)
+{
+ Cell &merge_from_cell = cinfo.cell(merge_from);
+ Cell &merge_to_cell = cinfo.cell(merge_to);
+ int final_merge_to = merge_to;
+ while (merge_to_cell.merged_to() != NO_INDEX) {
+ final_merge_to = merge_to_cell.merged_to();
+ merge_to_cell = cinfo.cell(final_merge_to);
+ }
+ for (int p : pinfo.index_range()) {
+ Patch &patch = pinfo.patch(p);
+ if (patch.cell_above == merge_from) {
+ patch.cell_above = final_merge_to;
+ }
+ if (patch.cell_below == merge_from) {
+ patch.cell_below = final_merge_to;
+ }
+ }
+ for (int cell_p : merge_from_cell.patches()) {
+ merge_to_cell.add_patch_non_duplicates(cell_p);
+ }
+ merge_from_cell.set_merged_to(final_merge_to);
+}
+
/* Partition the triangles of tm into Patches. */
static PatchesInfo find_patches(const Mesh &tm, const TriMeshTopology &tmtopo)
{
@@ -885,7 +926,7 @@ static void find_cells_from_edge(const Mesh &tm,
{
const int dbg_level = 0;
if (dbg_level > 0) {
- std::cout << "find_cells_from_edge " << e << "\n";
+ std::cout << "FIND_CELLS_FROM_EDGE " << e << "\n";
}
const Vector<int> *edge_tris = tmtopo.edge_tris(e);
BLI_assert(edge_tris != nullptr);
@@ -961,8 +1002,7 @@ static void find_cells_from_edge(const Mesh &tm,
}
else {
if (*r_follow_cell != *rnext_prev_cell) {
- std::cout << "IMPLEMENT ME: MERGE CELLS\n";
- // BLI_assert(false);
+ merge_cells(*r_follow_cell, *rnext_prev_cell, cinfo, pinfo);
}
}
}
@@ -992,6 +1032,27 @@ static CellsInfo find_cells(const Mesh &tm, const TriMeshTopology &tmtopo, Patch
}
}
}
+ /* Some patches may have no cells at this point. These are either:
+ * (a) a closed manifold patch only incident on itself (sphere, torus, klein bottle, etc.).
+ * (b) an open manifold patch only incident on itself (has non-manifold boundaries).
+ * Make above and below cells for these patches. This will create a disconnected patch-cell
+ * bipartite graph, which will have to be fixed later.
+ */
+ for (int p : pinfo.index_range()) {
+ Patch &patch = pinfo.patch(p);
+ if (patch.cell_above == NO_INDEX) {
+ int c = cinfo.add_cell();
+ patch.cell_above = c;
+ Cell &cell = cinfo.cell(c);
+ cell.add_patch(p);
+ }
+ if (patch.cell_below == NO_INDEX) {
+ int c = cinfo.add_cell();
+ patch.cell_below = c;
+ Cell &cell = cinfo.cell(c);
+ cell.add_patch(p);
+ }
+ }
if (dbg_level > 0) {
std::cout << "\nFIND_CELLS found " << cinfo.tot_cell() << " cells\nCells\n";
for (int i : cinfo.index_range()) {
@@ -1005,41 +1066,55 @@ static CellsInfo find_cells(const Mesh &tm, const TriMeshTopology &tmtopo, Patch
return cinfo;
}
-static bool patch_cell_graph_connected(const CellsInfo &cinfo, const PatchesInfo &pinfo)
+/* Find the connected patch components (connects are via intermediate cells), and put
+ * component numbers in each patch.
+ * Return a Vector of components - each a Vector of the patch ids in the component.
+ */
+static Vector<Vector<int>> find_patch_components(const CellsInfo &cinfo, PatchesInfo &pinfo)
{
- if (cinfo.tot_cell() == 0 || pinfo.tot_patch() == 0) {
- return false;
- }
- Array<bool> cell_reachable(cinfo.tot_cell(), false);
- Array<bool> patch_reachable(pinfo.tot_patch(), false);
- Stack<int> stack; /* Patch indexes to visit. */
- stack.push(0);
- while (!stack.is_empty()) {
- int p = stack.pop();
- if (patch_reachable[p]) {
+ constexpr int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "FIND_PATCH_COMPONENTS\n";
+ }
+ if (pinfo.tot_patch() == 0) {
+ return Vector<Vector<int>>();
+ }
+ int current_component = 0;
+ Stack<int> stack; /* Patch indices to visit. */
+ Vector<Vector<int>> ans;
+ for (int pstart : pinfo.index_range()) {
+ Patch &patch_pstart = pinfo.patch(pstart);
+ if (patch_pstart.component != NO_INDEX) {
continue;
}
- patch_reachable[p] = true;
- const Patch &patch = pinfo.patch(p);
- for (int c : {patch.cell_above, patch.cell_below}) {
- if (cell_reachable[c]) {
- continue;
- }
- cell_reachable[c] = true;
- for (int p : cinfo.cell(c).patches()) {
- if (!patch_reachable[p]) {
- stack.push(p);
+ ans.append(Vector<int>());
+ ans[current_component].append(pstart);
+ stack.push(pstart);
+ patch_pstart.component = current_component;
+ while (!stack.is_empty()) {
+ int p = stack.pop();
+ Patch &patch = pinfo.patch(p);
+ BLI_assert(patch.component == current_component);
+ for (int c : {patch.cell_above, patch.cell_below}) {
+ for (int pn : cinfo.cell(c).patches()) {
+ Patch &patch_neighbor = pinfo.patch(pn);
+ if (patch_neighbor.component == NO_INDEX) {
+ patch_neighbor.component = current_component;
+ stack.push(pn);
+ ans[current_component].append(pn);
+ }
}
}
}
+ ++current_component;
}
- if (std::any_of(cell_reachable.begin(), cell_reachable.end(), std::logical_not<>())) {
- return false;
- }
- if (std::any_of(patch_reachable.begin(), patch_reachable.end(), std::logical_not<>())) {
- return false;
+ if (dbg_level > 0) {
+ std::cout << "found " << ans.size() << " components\n";
+ for (int comp : ans.index_range()) {
+ std::cout << comp << ": " << ans[comp] << "\n";
+ }
}
- return true;
+ return ans;
}
/* Do all patches have cell_above and cell_below set?
@@ -1049,6 +1124,9 @@ static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo
{
for (int c : cinfo.index_range()) {
const Cell &cell = cinfo.cell(c);
+ if (cell.merged_to() != NO_INDEX) {
+ continue;
+ }
if (cell.patches().size() == 0) {
std::cout << "Patch/Cell graph disconnected at Cell " << c << " with no patches\n";
return false;
@@ -1072,20 +1150,83 @@ static bool patch_cell_graph_ok(const CellsInfo &cinfo, const PatchesInfo &pinfo
return false;
}
}
- if (!patch_cell_graph_connected(cinfo, pinfo)) {
- std::cout << "Patch/Cell graph not connected\n";
- return false;
- }
return true;
}
+/* Find which of the cells around edge e contains point p.
+ * Do this by inserting a dummy triangle containing v and sorting the
+ * triangles around the edge to find out where in the sort order
+ * the dummy triangle lies, then finding which cell is between
+ * the two triangles on either side of the dummy.
+ */
+static int find_cell_for_point_near_edge(mpq3 p,
+ const Edge &e,
+ const Mesh &tm,
+ const TriMeshTopology &tmtopo,
+ const PatchesInfo &pinfo,
+ MArena *arena)
+{
+ constexpr int dbg_level = 0;
+ if (dbg_level > 0) {
+ std::cout << "FIND_CELL_FOR_POINT_NEAR_EDGE, p=" << p << " e=" << e << "\n";
+ }
+ const Vector<int> *etris = tmtopo.edge_tris(e);
+ Vertp dummy_vert = arena->add_or_find_vert(p, NO_INDEX);
+ Facep dummy_tri = arena->add_face({e.v0(), e.v1(), dummy_vert},
+ NO_INDEX,
+ {NO_INDEX, NO_INDEX, NO_INDEX},
+ {false, false, false});
+ Array<int> edge_tris(etris->size() + 1);
+ std::copy(etris->begin(), etris->end(), edge_tris.begin());
+ edge_tris[edge_tris.size() - 1] = EXTRA_TRI_INDEX;
+ Array<int> sorted_tris = sort_tris_around_edge(
+ tm, tmtopo, e, edge_tris, edge_tris[0], dummy_tri);
+ if (dbg_level > 0) {
+ std::cout << "sorted tris = " << sorted_tris << "\n";
+ }
+ int *p_sorted_dummy = std::find(sorted_tris.begin(), sorted_tris.end(), EXTRA_TRI_INDEX);
+ BLI_assert(p_sorted_dummy != sorted_tris.end());
+ int dummy_index = p_sorted_dummy - sorted_tris.begin();
+ int
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list