| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Copyright (c) 2000-2022 Inria | ||
| 3 | * All rights reserved. | ||
| 4 | * | ||
| 5 | * Redistribution and use in source and binary forms, with or without | ||
| 6 | * modification, are permitted provided that the following conditions are met: | ||
| 7 | * | ||
| 8 | * * Redistributions of source code must retain the above copyright notice, | ||
| 9 | * this list of conditions and the following disclaimer. | ||
| 10 | * * Redistributions in binary form must reproduce the above copyright notice, | ||
| 11 | * this list of conditions and the following disclaimer in the documentation | ||
| 12 | * and/or other materials provided with the distribution. | ||
| 13 | * * Neither the name of the ALICE Project-Team nor the names of its | ||
| 14 | * contributors may be used to endorse or promote products derived from this | ||
| 15 | * software without specific prior written permission. | ||
| 16 | * | ||
| 17 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" | ||
| 18 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | ||
| 19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | ||
| 20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE | ||
| 21 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR | ||
| 22 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF | ||
| 23 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS | ||
| 24 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN | ||
| 25 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | ||
| 26 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE | ||
| 27 | * POSSIBILITY OF SUCH DAMAGE. | ||
| 28 | * | ||
| 29 | * Contact: Bruno Levy | ||
| 30 | * | ||
| 31 | * https://www.inria.fr/fr/bruno-levy | ||
| 32 | * | ||
| 33 | * Inria, | ||
| 34 | * Domaine de Voluceau, | ||
| 35 | * 78150 Le Chesnay - Rocquencourt | ||
| 36 | * FRANCE | ||
| 37 | * | ||
| 38 | */ | ||
| 39 | |||
| 40 | #include <exploragram/hexdom/quad_dominant.h> | ||
| 41 | #include <exploragram/hexdom/meshcomesh.h> | ||
| 42 | #include <exploragram/hexdom/PGP.h> | ||
| 43 | #include <exploragram/hexdom/basic.h> | ||
| 44 | #include <exploragram/hexdom/extra_connectivity.h> | ||
| 45 | #include <geogram/numerics/matrix_util.h> | ||
| 46 | #include <geogram/basic/permutation.h> | ||
| 47 | #include <algorithm> | ||
| 48 | #include <geogram/mesh/triangle_intersection.h> | ||
| 49 | |||
| 50 | #include <geogram/mesh/mesh_tetrahedralize.h> | ||
| 51 | #include <geogram/delaunay/delaunay.h> | ||
| 52 | |||
| 53 | #include <geogram/points/nn_search.h> | ||
| 54 | #include <geogram/points/colocate.h> | ||
| 55 | #include <queue> | ||
| 56 | |||
| 57 | #include <exploragram/hexdom/mesh_inspector.h> | ||
| 58 | #include <exploragram/hexdom/intersect_tools.h> | ||
| 59 | #include <exploragram/hexdom/polygon.h> | ||
| 60 | |||
| 61 | namespace GEO { | ||
| 62 | |||
| 63 | ✗ | bool find_self_intersections(Mesh* facets_with_quads_and_tri_only, vector<index_t> &intersections) { | |
| 64 | ✗ | intersections.resize(0); | |
| 65 | Mesh* m = facets_with_quads_and_tri_only; | ||
| 66 | vector<BBox> inboxes(m->facets.nb()); | ||
| 67 | ✗ | FOR(f, m->facets.nb()) { | |
| 68 | index_t nbv = m->facets.nb_vertices(f); | ||
| 69 | ✗ | geo_assert(4 == nbv || 3 == nbv); | |
| 70 | ✗ | FOR(fv, nbv) { | |
| 71 | ✗ | inboxes[f].add(X(m)[m->facets.vertex(f, fv)]); | |
| 72 | } | ||
| 73 | } | ||
| 74 | ✗ | HBoxes hb(inboxes); | |
| 75 | |||
| 76 | bool conflict_detected = false; | ||
| 77 | ✗ | FOR(f, m->facets.nb()) { | |
| 78 | vector<index_t> primitives; | ||
| 79 | ✗ | hb.intersect(inboxes[f], primitives); | |
| 80 | ✗ | FOR(i, primitives.size()) { | |
| 81 | ✗ | index_t opp_f = primitives[i]; | |
| 82 | ✗ | if (f==opp_f) continue; | |
| 83 | vector<vec3> P; | ||
| 84 | ✗ | FOR(fv, m->facets.nb_vertices(f)) { | |
| 85 | ✗ | P.push_back(X(m)[m->facets.vertex(f, fv)]); | |
| 86 | } | ||
| 87 | vector<vec3> Q; | ||
| 88 | ✗ | FOR(fv, m->facets.nb_vertices(opp_f)) { | |
| 89 | ✗ | Q.push_back(X(m)[m->facets.vertex(opp_f, fv)]); | |
| 90 | } | ||
| 91 | |||
| 92 | bool conflict = false; | ||
| 93 | ✗ | FOR(trP, 4) { | |
| 94 | ✗ | FOR(trQ, 4) { | |
| 95 | ✗ | if (trP > 0 && P.size() == 3) continue; | |
| 96 | ✗ | if (trQ > 0 && Q.size() == 3) continue; | |
| 97 | TriangleIsects trash; | ||
| 98 | ✗ | conflict = conflict || triangles_intersections( | |
| 99 | ✗ | P[quad_split[trP][0]], P[quad_split[trP][1]], P[quad_split[trP][2]], | |
| 100 | ✗ | Q[quad_split[trQ][0]], Q[quad_split[trQ][1]], Q[quad_split[trQ][2]], | |
| 101 | trash | ||
| 102 | ); | ||
| 103 | } | ||
| 104 | } | ||
| 105 | |||
| 106 | ✗ | if (conflict) { | |
| 107 | intersections.push_back(f); | ||
| 108 | intersections.push_back(opp_f); | ||
| 109 | } | ||
| 110 | ✗ | conflict_detected = conflict_detected || conflict; | |
| 111 | } | ||
| 112 | } | ||
| 113 | ✗ | sort( intersections.begin(), intersections.end() ); | |
| 114 | ✗ | intersections.erase( unique( intersections.begin(), intersections.end() ), intersections.end() ); | |
| 115 | ✗ | geo_assert((conflict_detected && intersections.size()) || (!conflict_detected && !intersections.size())); | |
| 116 | ✗ | return conflict_detected; | |
| 117 | ✗ | } | |
| 118 | |||
| 119 | |||
| 120 | /* | ||
| 121 | // test for self-intersection | ||
| 122 | // input : a surface with only triangles and quads allowed | ||
| 123 | // output : push_back into regions_to_lock BBoxes of self-intersections | ||
| 124 | bool lock_self_intersecting_regions(Mesh* mesh, Attribute<bool> &verts_to_remove, Attribute<index_t> &undo) { | ||
| 125 | vector<index_t> intersections; | ||
| 126 | bool conflict = find_self_intersections(mesh, intersections); | ||
| 127 | FOR(f, intersections.size()) { | ||
| 128 | if (undo[intersections[f]]!=NOT_AN_ID) verts_to_remove[undo[intersections[f]]] = false; | ||
| 129 | } | ||
| 130 | geo_assert(!conflict || intersections.size()>0); | ||
| 131 | return intersections.size()>0; | ||
| 132 | } | ||
| 133 | |||
| 134 | bool lock_self_intersecting_regions(Mesh* mesh, vector<BBox>& regions_to_lock) { | ||
| 135 | Attribute<bool> conflict(mesh->facets.attributes(), "conflict"); | ||
| 136 | vector<index_t> intersections; | ||
| 137 | find_self_intersections(mesh, intersections); | ||
| 138 | // sort( intersections.begin(), intersections.end() ); | ||
| 139 | // intersections.erase( unique( intersections.begin(), intersections.end() ), intersections.end() ); | ||
| 140 | |||
| 141 | FOR(f, intersections.size()) { | ||
| 142 | BBox inbox; | ||
| 143 | index_t nbv = mesh->facets.nb_vertices(intersections[f]); | ||
| 144 | geo_assert(4 == nbv || 3 == nbv); | ||
| 145 | FOR(fv, nbv) { | ||
| 146 | inbox.add(X(mesh)[mesh->facets.vertex(intersections[f], fv)]); | ||
| 147 | } | ||
| 148 | regions_to_lock.push_back(inbox); | ||
| 149 | conflict[intersections[f]] = true; | ||
| 150 | } | ||
| 151 | std::cerr << "[CONFLICTING FACETS] " << intersections.size() << "\n"; | ||
| 152 | return intersections.size()>0; | ||
| 153 | } | ||
| 154 | */ | ||
| 155 | // compute light connectivity (vertex to facets) | ||
| 156 | ✗ | vector<vector<index_t> > generate_v2f(Mesh *m) { | |
| 157 | vector<vector<index_t> > v2f(m->vertices.nb()); | ||
| 158 | ✗ | FOR(f, m->facets.nb()) { | |
| 159 | ✗ | geo_assert(m->facets.nb_vertices(f) == 3); | |
| 160 | ✗ | FOR(lc, m->facets.nb_corners(f)) { | |
| 161 | ✗ | v2f[m->facets.vertex(f, lc)].push_back(f); | |
| 162 | } | ||
| 163 | } | ||
| 164 | ✗ | return v2f; | |
| 165 | } | ||
| 166 | |||
| 167 | ✗ | static void fan_asserts(Mesh *m, vector<vector<index_t> > &v2f, Attribute<index_t> &chart) { | |
| 168 | ✗ | std::cerr << "sanity check: triangulated surface with 3 distinct vertid for each triangle..."; | |
| 169 | ✗ | FOR(f, m->facets.nb()) { | |
| 170 | ✗ | geo_assert(3 == m->facets.nb_corners(f)); | |
| 171 | ✗ | FOR(c1, m->facets.nb_corners(f)) { | |
| 172 | ✗ | FOR(c2, m->facets.nb_corners(f)) { | |
| 173 | ✗ | if (c1 == c2) continue; | |
| 174 | ✗ | geo_assert(m->facets.vertex(f, c1) != m->facets.vertex(f, c2)); | |
| 175 | } | ||
| 176 | } | ||
| 177 | } | ||
| 178 | ✗ | std::cerr << "ok\n"; | |
| 179 | |||
| 180 | ✗ | std::cerr << "sanity check: all fans are correct and for complete fans valency >= 3..."; | |
| 181 | ✗ | geo_assert(v2f.size()==m->vertices.nb()); | |
| 182 | ✗ | FOR(v, m->vertices.nb()) { | |
| 183 | ✗ | if (!v2f[v].size()) continue; | |
| 184 | ✗ | TrFan fan = TrFan(v, m, v2f, chart); | |
| 185 | ✗ | geo_assert(fan.incomplete_ || v2f[v].size() >= 3); | |
| 186 | |||
| 187 | ✗ | } | |
| 188 | ✗ | std::cerr << "ok\n"; | |
| 189 | ✗ | } | |
| 190 | |||
| 191 | ✗ | bool try_simplify(Mesh* m, Attribute<index_t> &chart, Attribute<bool> &verts_to_remove, Attribute<index_t> &undo) { | |
| 192 | // std::cerr << "NVERTS= " << m->vertices.nb() << "\n"; | ||
| 193 | ✗ | vector<index_t> to_kill(m->facets.nb(), false); | |
| 194 | ✗ | vector<vector<index_t> > v2f = generate_v2f(m); | |
| 195 | bool mesh_is_modified = false; | ||
| 196 | |||
| 197 | ✗ | fan_asserts(m, v2f, chart); | |
| 198 | |||
| 199 | ✗ | FOR(v, m->vertices.nb()) { | |
| 200 | ✗ | if (!verts_to_remove[v] || !v2f[v].size()) continue; | |
| 201 | ✗ | TrFan fan = TrFan(v, m, v2f, chart); | |
| 202 | |||
| 203 | ✗ | fan.triangulate(); | |
| 204 | // if (!fan.triangulate()) continue; | ||
| 205 | |||
| 206 | { // block of geometrical and topological sanity checks, allows to reject the triangulation | ||
| 207 | bool non_manifold_edge = false; | ||
| 208 | ✗ | FOR(ichart, fan.ncharts()) { | |
| 209 | vector<index_t> &tri = fan.triangles[ichart]; | ||
| 210 | ✗ | FOR(t, tri.size()/3) { | |
| 211 | ✗ | FOR(iv, 3) { | |
| 212 | ✗ | index_t a = tri[3*t + iv]; | |
| 213 | ✗ | index_t b = tri[3*t + (iv+1) % 3]; | |
| 214 | |||
| 215 | // (a,b) is an edge in new triangulation, let us check whether it is on the boundary of the chart | ||
| 216 | bool fan_boundary = false; | ||
| 217 | ✗ | FOR(i, fan.nb_fan_triangles()) { | |
| 218 | ✗ | fan_boundary = fan_boundary || (a == fan[i].org && b == fan[i].dest); | |
| 219 | } | ||
| 220 | ✗ | if (fan_boundary) continue; | |
| 221 | |||
| 222 | // here we know that (a,b) is an interior edge | ||
| 223 | ✗ | FOR(f, v2f[a].size()) { | |
| 224 | ✗ | FOR(c, m->facets.nb_corners(v2f[a][f])) { | |
| 225 | ✗ | non_manifold_edge = non_manifold_edge || (b == m->facets.vertex(v2f[a][f], c)); | |
| 226 | } | ||
| 227 | } | ||
| 228 | } | ||
| 229 | } | ||
| 230 | } | ||
| 231 | ✗ | if (non_manifold_edge) { | |
| 232 | ✗ | error("this triangulation would introduce a non manifold edge, rejecting"); | |
| 233 | continue; | ||
| 234 | } | ||
| 235 | } | ||
| 236 | |||
| 237 | mesh_is_modified = true; | ||
| 238 | |||
| 239 | ✗ | FOR(ichart, fan.ncharts()) { | |
| 240 | vector<index_t> &tri = fan.triangles[ichart]; | ||
| 241 | ✗ | FOR(t, tri.size() / 3) { | |
| 242 | ✗ | index_t new_f = m->facets.create_triangle(tri[3*t + 0], tri[3*t + 1], tri[3*t + 2]); | |
| 243 | ✗ | m->facets.attributes().copy_item(new_f, fan[fan.chart_offset[ichart]].f); | |
| 244 | ✗ | undo[new_f] = v; | |
| 245 | ✗ | to_kill.push_back(false); | |
| 246 | |||
| 247 | ✗ | FOR(lc, 3) { | |
| 248 | ✗ | v2f[m->facets.vertex(new_f, lc)].push_back(new_f); | |
| 249 | } | ||
| 250 | } | ||
| 251 | } | ||
| 252 | |||
| 253 | // update light connection info | ||
| 254 | ✗ | FOR(i, v2f[fan.v_].size()) { | |
| 255 | ✗ | to_kill[v2f[fan.v_][i]] = true; | |
| 256 | } | ||
| 257 | v2f[fan.v_].clear(); | ||
| 258 | |||
| 259 | ✗ | FOR(i, fan.nb_fan_triangles()) { | |
| 260 | ✗ | index_t f = fan[i].f; | |
| 261 | ✗ | index_t org = fan[i].org; | |
| 262 | ✗ | index_t dest = fan[i].dest; | |
| 263 | |||
| 264 | ✗ | index_t vopp[2] = { org, dest }; | |
| 265 | |||
| 266 | ✗ | FOR(j, 2) { | |
| 267 | ✗ | FOR(fi, v2f[vopp[j]].size()) { | |
| 268 | ✗ | if (v2f[vopp[j]][fi] != f) continue; | |
| 269 | ✗ | v2f[vopp[j]][fi] = v2f[vopp[j]].back(); | |
| 270 | v2f[vopp[j]].pop_back(); | ||
| 271 | break; | ||
| 272 | } | ||
| 273 | } | ||
| 274 | } | ||
| 275 | ✗ | } | |
| 276 | |||
| 277 | ✗ | fan_asserts(m, v2f, chart); | |
| 278 | |||
| 279 | // std::cerr << "NVERTS= " << m->vertices.nb() << "\n"; | ||
| 280 | ✗ | m->facets.delete_elements(to_kill, false); | |
| 281 | // kill_isolated_vertices(m); | ||
| 282 | // std::cerr << "NVERTS= " << m->vertices.nb() << "\n"; | ||
| 283 | // std::cerr << "modified " << mesh_is_modified << "\n"; | ||
| 284 | ✗ | return mesh_is_modified; | |
| 285 | } | ||
| 286 | |||
| 287 | } | ||
| 288 |