Page MenuHome
Differential D11003 Diff 36252 source/blender/blenlib/intern/mesh_boolean.cc

Changeset View

Standalone View

View Options

source/blender/blenlib/intern/mesh_boolean.cc

Show First 20 Lines • Show All 109 Lines • ▼ Show 20 Linesstatic std::ostream &operator<<(std::ostream &os, const Edge &e)
else { else {
os << "(" << e.v0() << "," << e.v1() << ")"; os << "(" << e.v0() << "," << e.v1() << ")";
} }
return os; return os;
} }
static std::ostream &operator<<(std::ostream &os, const Span<int> &a) static std::ostream &operator<<(std::ostream &os, const Span<int> &a)
{ {
for (int i : a.index_range()) { for (int i : iter_indices(a)) {
os << a[i]; os << a[i];
if (i != a.size() - 1) { if (i != a.size() - 1) {
os << " "; os << " ";
} }
} }
return os; return os;
} }
▲ Show 20 Lines • Show All 450 Lines • ▼ Show 20 Lines public:
int tot_cell() const int tot_cell() const
{ {
return cell_.size(); return cell_.size();
} }
IndexRange index_range() const IndexRange index_range() const
{ {
return cell_.index_range(); return iter_indices(cell_);
} }
const Cell *begin() const const Cell *begin() const
{ {
return cell_.begin(); return cell_.begin();
} }
const Cell *end() const const Cell *end() const
▲ Show 20 Lines • Show All 157 Lines • ▼ Show 20 Lines if (pinfo.tri_patch(t) == -1) {
} }
else { else {
/* e is non-manifold. Set any patch-patch incidences we can. */ /* e is non-manifold. Set any patch-patch incidences we can. */
if (dbg_level > 1) { if (dbg_level > 1) {
std::cout << " e non-manifold case\n"; std::cout << " e non-manifold case\n";
} }
const Vector<int> *etris = tmtopo.edge_tris(e); const Vector<int> *etris = tmtopo.edge_tris(e);
if (etris != nullptr) { if (etris != nullptr) {
for (int i : etris->index_range()) { for (int i : iter_indices(*etris)) {
int t_other = (*etris)[i]; int t_other = (*etris)[i];
if (t_other != tcand && pinfo.tri_is_assigned(t_other)) { if (t_other != tcand && pinfo.tri_is_assigned(t_other)) {
int p_other = pinfo.tri_patch(t_other); int p_other = pinfo.tri_patch(t_other);
if (p_other == cur_patch_index) { if (p_other == cur_patch_index) {
continue; continue;
} }
if (pinfo.patch_patch_edge(cur_patch_index, p_other).v0() == nullptr) { if (pinfo.patch_patch_edge(cur_patch_index, p_other).v0() == nullptr) {
pinfo.add_new_patch_patch_edge(cur_patch_index, p_other, e); pinfo.add_new_patch_patch_edge(cur_patch_index, p_other, e);
▲ Show 20 Lines • Show All 151 Lines • ▼ Show 20 Lines
* otherwise negative. * otherwise negative.
*/ */
static void sort_by_signed_triangle_index(Vector<int> &g, static void sort_by_signed_triangle_index(Vector<int> &g,
const Edge e, const Edge e,
const IMesh &tm, const IMesh &tm,
const Face *extra_tri) const Face *extra_tri)
{ {
Array<int> signed_g(g.size()); Array<int> signed_g(g.size());
for (int i : g.index_range()) { for (int i : iter_indices(g)) {
const Face &tri = g[i] == EXTRA_TRI_INDEX ? *extra_tri : *tm.face(g[i]); const Face &tri = g[i] == EXTRA_TRI_INDEX ? *extra_tri : *tm.face(g[i]);
bool rev; bool rev;
find_flap_vert(tri, e, &rev); find_flap_vert(tri, e, &rev);
signed_g[i] = rev ? -g[i] : g[i]; signed_g[i] = rev ? -g[i] : g[i];
} }
std::sort(signed_g.begin(), signed_g.end()); std::sort(signed_g.begin(), signed_g.end());
for (int i : g.index_range()) { for (int i : iter_indices(g)) {
g[i] = abs(signed_g[i]); g[i] = abs(signed_g[i]);
} }
} }
/** /**
* Sort the triangles \a tris, which all share edge e, as they appear * Sort the triangles \a tris, which all share edge e, as they appear
* geometrically clockwise when looking down edge e. * geometrically clockwise when looking down edge e.
* Triangle t0 is the first triangle in the top-level call * Triangle t0 is the first triangle in the top-level call
Show All 37 Lines if (dbg_level > 0) {
std::cout << "t0 = " << t0 << "\n"; std::cout << "t0 = " << t0 << "\n";
} }
Vector<int> g1{tris[0]}; Vector<int> g1{tris[0]};
Vector<int> g2; Vector<int> g2;
Vector<int> g3; Vector<int> g3;
Vector<int> g4; Vector<int> g4;
std::array<Vector<int> *, 4> groups = {&g1, &g2, &g3, &g4}; std::array<Vector<int> *, 4> groups = {&g1, &g2, &g3, &g4};
const Face &triref = *tm.face(tris[0]); const Face &triref = *tm.face(tris[0]);
for (int i : tris.index_range()) { for (int i : iter_indices(tris)) {
if (i == 0) { if (i == 0) {
continue; continue;
} }
int t = tris[i]; int t = tris[i];
BLI_assert(t < tm.face_size() || (t == EXTRA_TRI_INDEX && extra_tri != nullptr)); BLI_assert(t < tm.face_size() || (t == EXTRA_TRI_INDEX && extra_tri != nullptr));
const Face &tri = (t == EXTRA_TRI_INDEX) ? *extra_tri : *tm.face(t); const Face &tri = (t == EXTRA_TRI_INDEX) ? *extra_tri : *tm.face(t);
if (dbg_level > 2) { if (dbg_level > 2) {
std::cout << "classifying tri " << t << " with respect to " << tris[0] << "\n"; std::cout << "classifying tri " << t << " with respect to " << tris[0] << "\n";
▲ Show 20 Lines • Show All 273 Lines • ▼ Show 20 Lines while (!stack.is_empty()) {
} }
} }
} }
} }
++current_component; ++current_component;
} }
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "found " << ans.size() << " components\n"; std::cout << "found " << ans.size() << " components\n";
for (int comp : ans.index_range()) { for (int comp : iter_indices(ans)) {
std::cout << comp << ": " << ans[comp] << "\n"; std::cout << comp << ": " << ans[comp] << "\n";
} }
} }
return ans; return ans;
} }
/** /**
* Do all patches have cell_above and cell_below set? * Do all patches have cell_above and cell_below set?
▲ Show 20 Lines • Show All 540 Lines • ▼ Show 20 Linesstatic Vector<ComponentContainer> find_component_containers(int comp,
} }
Vector<ComponentContainer> ans; Vector<ComponentContainer> ans;
int test_p = components[comp][0]; int test_p = components[comp][0];
int test_t = pinfo.patch(test_p).tri(0); int test_t = pinfo.patch(test_p).tri(0);
const Vert *test_v = tm.face(test_t)[0].vert[0]; const Vert *test_v = tm.face(test_t)[0].vert[0];
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "test vertex in comp: " << test_v << "\n"; std::cout << "test vertex in comp: " << test_v << "\n";
} }
for (int comp_other : components.index_range()) { for (int comp_other : iter_indices(components)) {
if (comp == comp_other) { if (comp == comp_other) {
continue; continue;
} }
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "comp_other = " << comp_other << "\n"; std::cout << "comp_other = " << comp_other << "\n";
} }
int nearest_tri = NO_INDEX; int nearest_tri = NO_INDEX;
int nearest_tri_close_vert = -1; int nearest_tri_close_vert = -1;
▲ Show 20 Lines • Show All 74 Lines • ▼ Show 20 Linesstatic void finish_patch_cell_graph(const IMesh &tm,
if (components.size() <= 1) { if (components.size() <= 1) {
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "one component so finish_patch_cell_graph does no work\n"; std::cout << "one component so finish_patch_cell_graph does no work\n";
} }
return; return;
} }
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "components:\n"; std::cout << "components:\n";
for (int comp : components.index_range()) { for (int comp : iter_indices(components)) {
std::cout << comp << ": " << components[comp] << "\n"; std::cout << comp << ": " << components[comp] << "\n";
} }
} }
Array<int> ambient_cell(components.size()); Array<int> ambient_cell(components.size());
for (int comp : components.index_range()) { for (int comp : iter_indices(components)) {
ambient_cell[comp] = find_ambient_cell(tm, &components[comp], tmtopo, pinfo, arena); ambient_cell[comp] = find_ambient_cell(tm, &components[comp], tmtopo, pinfo, arena);
} }
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "ambient cells:\n"; std::cout << "ambient cells:\n";
for (int comp : ambient_cell.index_range()) { for (int comp : iter_indices(ambient_cell)) {
std::cout << comp << ": " << ambient_cell[comp] << "\n"; std::cout << comp << ": " << ambient_cell[comp] << "\n";
} }
} }
int tot_components = components.size(); int tot_components = components.size();
Array<Vector<ComponentContainer>> comp_cont(tot_components); Array<Vector<ComponentContainer>> comp_cont(tot_components);
for (int comp : components.index_range()) { for (int comp : iter_indices(components)) {
comp_cont[comp] = find_component_containers( comp_cont[comp] = find_component_containers(
comp, components, ambient_cell, tm, pinfo, tmtopo, arena); comp, components, ambient_cell, tm, pinfo, tmtopo, arena);
} }
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "component containers:\n"; std::cout << "component containers:\n";
for (int comp : comp_cont.index_range()) { for (int comp : iter_indices(comp_cont)) {
std::cout << comp << ": "; std::cout << comp << ": ";
for (const ComponentContainer &cc : comp_cont[comp]) { for (const ComponentContainer &cc : comp_cont[comp]) {
std::cout << "[containing_comp=" << cc.containing_component std::cout << "[containing_comp=" << cc.containing_component
<< ", nearest_cell=" << cc.nearest_cell << ", d2=" << cc.dist_to_cell << "] "; << ", nearest_cell=" << cc.nearest_cell << ", d2=" << cc.dist_to_cell << "] ";
} }
std::cout << "\n"; std::cout << "\n";
} }
} }
if (dbg_level > 1) { if (dbg_level > 1) {
write_obj_cell_patch(tm, cinfo, pinfo, false, "beforemerge"); write_obj_cell_patch(tm, cinfo, pinfo, false, "beforemerge");
} }
/* For nested components, merge their ambient cell with the nearest containing cell. */ /* For nested components, merge their ambient cell with the nearest containing cell. */
Vector<int> outer_components; Vector<int> outer_components;
for (int comp : comp_cont.index_range()) { for (int comp : iter_indices(comp_cont)) {
if (comp_cont[comp].size() == 0) { if (comp_cont[comp].size() == 0) {
outer_components.append(comp); outer_components.append(comp);
} }
else { else {
ComponentContainer &closest = comp_cont[comp][0]; ComponentContainer &closest = comp_cont[comp][0];
for (int i = 1; i < comp_cont[comp].size(); ++i) { for (int i = 1; i < comp_cont[comp].size(); ++i) {
if (comp_cont[comp][i].dist_to_cell < closest.dist_to_cell) { if (comp_cont[comp][i].dist_to_cell < closest.dist_to_cell) {
closest = comp_cont[comp][i]; closest = comp_cont[comp][i];
▲ Show 20 Lines • Show All 247 Lines • ▼ Show 20 Lines if (dbg_level > 0) {
std::cout << "\n"; std::cout << "\n";
} }
if (above_stack_cell->in_output_volume() ^ below_stack_cell->in_output_volume()) { if (above_stack_cell->in_output_volume() ^ below_stack_cell->in_output_volume()) {
bool need_flipped_tri = above_stack_cell->in_output_volume(); bool need_flipped_tri = above_stack_cell->in_output_volume();
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "need tri " << (need_flipped_tri ? "flipped" : "") << "\n"; std::cout << "need tri " << (need_flipped_tri ? "flipped" : "") << "\n";
} }
int t_to_add = NO_INDEX; int t_to_add = NO_INDEX;
for (int i : stack.index_range()) { for (int i : iter_indices(stack)) {
if (flipped[i] == need_flipped_tri) { if (flipped[i] == need_flipped_tri) {
t_to_add = pinfo.patch(stack[i]).tri(0); t_to_add = pinfo.patch(stack[i]).tri(0);
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "using tri " << t_to_add << "\n"; std::cout << "using tri " << t_to_add << "\n";
} }
r_tris.append(tm_subdivided.face(t_to_add)); r_tris.append(tm_subdivided.face(t_to_add));
break; break;
} }
▲ Show 20 Lines • Show All 622 Lines • ▼ Show 20 Linesstruct FaceMergeState {
* to the index in the above edge vector in which to find the corresponding #MergeEdge. * to the index in the above edge vector in which to find the corresponding #MergeEdge.
*/ */
Map<std::pair<int, int>, int> edge_map; Map<std::pair<int, int>, int> edge_map;
}; };
static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms) static std::ostream &operator<<(std::ostream &os, const FaceMergeState &fms)
{ {
os << "faces:\n"; os << "faces:\n";
for (int f : fms.face.index_range()) { for (int f : iter_indices(fms.face)) {
const MergeFace &mf = fms.face[f]; const MergeFace &mf = fms.face[f];
std::cout << f << ": orig=" << mf.orig << " verts "; std::cout << f << ": orig=" << mf.orig << " verts ";
for (const Vert *v : mf.vert) { for (const Vert *v : mf.vert) {
std::cout << v << " "; std::cout << v << " ";
} }
std::cout << "\n"; std::cout << "\n";
std::cout << " edges " << mf.edge << "\n"; std::cout << " edges " << mf.edge << "\n";
std::cout << " merge_to = " << mf.merge_to << "\n"; std::cout << " merge_to = " << mf.merge_to << "\n";
} }
os << "\nedges:\n"; os << "\nedges:\n";
for (int e : fms.edge.index_range()) { for (int e : iter_indices(fms.edge)) {
const MergeEdge &me = fms.edge[e]; const MergeEdge &me = fms.edge[e];
std::cout << e << ": (" << me.v1 << "," << me.v2 << ") left=" << me.left_face std::cout << e << ": (" << me.v1 << "," << me.v2 << ") left=" << me.left_face
<< " right=" << me.right_face << " dis=" << me.dissolvable << " orig=" << me.orig << " right=" << me.right_face << " dis=" << me.dissolvable << " orig=" << me.orig
<< " is_int=" << me.is_intersect << "\n"; << " is_int=" << me.is_intersect << "\n";
} }
return os; return os;
} }
Show All 10 Linesstatic void init_face_merge_state(FaceMergeState *fms,
constexpr int dbg_level = 0; constexpr int dbg_level = 0;
/* Reserve enough faces and edges so that neither will have to resize. */ /* Reserve enough faces and edges so that neither will have to resize. */
fms->face.reserve(tris.size() + 1); fms->face.reserve(tris.size() + 1);
fms->edge.reserve(3 * tris.size()); fms->edge.reserve(3 * tris.size());
fms->edge_map.reserve(3 * tris.size()); fms->edge_map.reserve(3 * tris.size());
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "\nINIT_FACE_MERGE_STATE\n"; std::cout << "\nINIT_FACE_MERGE_STATE\n";
} }
for (int t : tris.index_range()) { for (int t : iter_indices(tris)) {
MergeFace mf; MergeFace mf;
const Face &tri = *tm.face(tris[t]); const Face &tri = *tm.face(tris[t]);
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "process tri = " << &tri << "\n"; std::cout << "process tri = " << &tri << "\n";
} }
BLI_assert(tri.plane_populated()); BLI_assert(tri.plane_populated());
if (double3::dot(norm, tri.plane->norm) <= 0.0) { if (double3::dot(norm, tri.plane->norm) <= 0.0) {
if (dbg_level > 0) { if (dbg_level > 0) {
▲ Show 20 Lines • Show All 188 Lines • ▼ Show 20 Lines
*/ */
static void do_dissolve(FaceMergeState *fms) static void do_dissolve(FaceMergeState *fms)
{ {
const int dbg_level = 0; const int dbg_level = 0;
if (dbg_level > 1) { if (dbg_level > 1) {
std::cout << "\nDO_DISSOLVE\n"; std::cout << "\nDO_DISSOLVE\n";
} }
Vector<int> dissolve_edges; Vector<int> dissolve_edges;
for (int e : fms->edge.index_range()) { for (int e : iter_indices(fms->edge)) {
if (fms->edge[e].dissolvable) { if (fms->edge[e].dissolvable) {
dissolve_edges.append(e); dissolve_edges.append(e);
} }
} }
if (dissolve_edges.size() == 0) { if (dissolve_edges.size() == 0) {
return; return;
} }
/* Things look nicer if we dissolve the longer edges first. */ /* Things look nicer if we dissolve the longer edges first. */
▲ Show 20 Lines • Show All 96 Lines • ▼ Show 20 Lines for (const double3 &norm : {first_tri_normal, first_tri_normal_rev}) {
do_dissolve(&fms); do_dissolve(&fms);
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << "faces in merged result:\n"; std::cout << "faces in merged result:\n";
} }
for (const MergeFace &mf : fms.face) { for (const MergeFace &mf : fms.face) {
if (mf.merge_to == -1) { if (mf.merge_to == -1) {
Array<int> e_orig(mf.edge.size()); Array<int> e_orig(mf.edge.size());
Array<bool> is_intersect(mf.edge.size()); Array<bool> is_intersect(mf.edge.size());
for (int i : mf.edge.index_range()) { for (int i : iter_indices(mf.edge)) {
e_orig[i] = fms.edge[mf.edge[i]].orig; e_orig[i] = fms.edge[mf.edge[i]].orig;
is_intersect[i] = fms.edge[mf.edge[i]].is_intersect; is_intersect[i] = fms.edge[mf.edge[i]].is_intersect;
} }
Face *facep = arena->add_face(mf.vert, mf.orig, e_orig, is_intersect); Face *facep = arena->add_face(mf.vert, mf.orig, e_orig, is_intersect);
ans.append(facep); ans.append(facep);
if (dbg_level > 0) { if (dbg_level > 0) {
std::cout << " " << facep << "\n"; std::cout << " " << facep << "\n";
} }
▲ Show 20 Lines • Show All 142 Lines • ▼ Show 20 Linesstatic IMesh polymesh_from_trimesh_with_dissolve(const IMesh &tm_out,
Array<Vector<int>> face_output_tris(tot_in_face); Array<Vector<int>> face_output_tris(tot_in_face);
for (int t : tm_out.face_index_range()) { for (int t : tm_out.face_index_range()) {
const Face &tri = *tm_out.face(t); const Face &tri = *tm_out.face(t);
int in_face = tri.orig; int in_face = tri.orig;
face_output_tris[in_face].append(t); face_output_tris[in_face].append(t);
} }
if (dbg_level > 1) { if (dbg_level > 1) {
std::cout << "face_output_tris:\n"; std::cout << "face_output_tris:\n";
for (int f : face_output_tris.index_range()) { for (int f : iter_indices(face_output_tris)) {
std::cout << f << ": " << face_output_tris[f] << "\n"; std::cout << f << ": " << face_output_tris[f] << "\n";
} }
} }
/* Merge triangles that we can from face_output_tri to make faces for output. /* Merge triangles that we can from face_output_tri to make faces for output.
* face_output_face[f] will be new original const Face *'s that * face_output_face[f] will be new original const Face *'s that
* make up whatever part of the boolean output remains of input face f. */ * make up whatever part of the boolean output remains of input face f. */
Array<Vector<Face *>> face_output_face(tot_in_face); Array<Vector<Face *>> face_output_face(tot_in_face);
▲ Show 20 Lines • Show All 265 Lines • Show Last 20 Lines