| 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 | #ifndef GEOGRAM_MESH_MESH_SURFACE_INTERSECTION | ||
| 41 | #define GEOGRAM_MESH_MESH_SURFACE_INTERSECTION | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/mesh/mesh.h> | ||
| 45 | #include <geogram/mesh/mesh_io.h> | ||
| 46 | #include <geogram/numerics/exact_geometry.h> | ||
| 47 | #include <geogram/numerics/predicates.h> | ||
| 48 | #include <geogram/basic/process.h> | ||
| 49 | #include <geogram/basic/attributes.h> | ||
| 50 | #include <geogram/basic/debug_stream.h> | ||
| 51 | #include <functional> | ||
| 52 | #include <tuple> | ||
| 53 | |||
| 54 | /** | ||
| 55 | * \file geogram/mesh/mesh_surface_intersection.h | ||
| 56 | * \brief Functions for computing intersections between surfacic meshes and | ||
| 57 | * for boolean operations. | ||
| 58 | */ | ||
| 59 | |||
| 60 | namespace GEO { | ||
| 61 | |||
| 62 | struct IsectInfo; | ||
| 63 | |||
| 64 | /********************************************************************/ | ||
| 65 | |||
| 66 | /** | ||
| 67 | * \brief Computes surface intersections | ||
| 68 | * \details New vertices are stored with exact coordinates | ||
| 69 | */ | ||
| 70 | class GEOGRAM_API MeshSurfaceIntersection { | ||
| 71 | public: | ||
| 72 | |||
| 73 | typedef exact::vec3h ExactPoint; | ||
| 74 | |||
| 75 | MeshSurfaceIntersection(Mesh& M); | ||
| 76 | ~MeshSurfaceIntersection(); | ||
| 77 | |||
| 78 | /** | ||
| 79 | * \details A facet attribute of type index_t named "operand_bit" can | ||
| 80 | * indicate for each facet to which operand of a n-ary boolean | ||
| 81 | * operation it corresponds to (the same facet might belong to | ||
| 82 | * several operands). It is taken into account by the two variants of | ||
| 83 | * mesh_classify_intersections() | ||
| 84 | */ | ||
| 85 | void intersect(); | ||
| 86 | |||
| 87 | /** | ||
| 88 | * \brief Removes all the facets that are on the outer boundary | ||
| 89 | * \pre set_radial_sort(true) was set before calling intersect() | ||
| 90 | */ | ||
| 91 | void remove_external_shell(); | ||
| 92 | |||
| 93 | /** | ||
| 94 | * \brief Removes all the facets that are not on the outer boundary | ||
| 95 | * \pre set_radial_sort(true) was set before calling intersect() | ||
| 96 | */ | ||
| 97 | void remove_internal_shells(); | ||
| 98 | |||
| 99 | /** | ||
| 100 | * \brief Not implemented yet | ||
| 101 | * \details The goal here is to remove degenerate facet pairs that are | ||
| 102 | * attached to the border, and that may appear due to snap rounding issues. | ||
| 103 | */ | ||
| 104 | void remove_fins(); | ||
| 105 | |||
| 106 | /** | ||
| 107 | * \brief Classifies the facets and keep only | ||
| 108 | * the ones on the boundary of a combination of regions defined | ||
| 109 | * by a boolean expression. | ||
| 110 | * \details A facet attribute of type index_t named "operand_bit" | ||
| 111 | * indicates for each facet to which operand of a n-ary boolean | ||
| 112 | * operation it corresponds to (the same facet might belong to | ||
| 113 | * several operands). | ||
| 114 | * \pre set_radial_sort(true) was set before calling intersect() | ||
| 115 | * \param[in] expr the boolean function in ASCII. | ||
| 116 | * One can use the following elements, and parentheses: | ||
| 117 | * - Variables: A..Z or x0..x31, correspond to the bits of the | ||
| 118 | * "operand_bit" attribute | ||
| 119 | * - the special variable '*' corresponds to the union of everything | ||
| 120 | * - and: '&' or '*' | ||
| 121 | * - or: '|' or '+' | ||
| 122 | * - xor: '^' | ||
| 123 | * - difference: '-' | ||
| 124 | * - not: '!' or '~' | ||
| 125 | * Special values for expr: | ||
| 126 | * - "union" (union of everything), synonym of '*' | ||
| 127 | * - "intersection" (intersection of everything). | ||
| 128 | */ | ||
| 129 | void classify(const std::string& expr); | ||
| 130 | |||
| 131 | /** | ||
| 132 | * \brief Finds the operands in which a component is included | ||
| 133 | * \param[in] component a connected component | ||
| 134 | * \param[in] v a vertex of the connected component | ||
| 135 | * \return the inclusion bits of the connected component relative | ||
| 136 | * to the operands | ||
| 137 | */ | ||
| 138 | index_t compute_component_inclusion_bits(index_t component, index_t v); | ||
| 139 | |||
| 140 | /** | ||
| 141 | * \brief Like compute_component_inclusion_bits(), but when v is not an | ||
| 142 | * original vertex. | ||
| 143 | * \details Called by compute_component_inclusion_bits() | ||
| 144 | * \see compute_component_inclusion_bits() | ||
| 145 | */ | ||
| 146 | index_t compute_component_inclusion_bits_exact(index_t component, index_t v); | ||
| 147 | |||
| 148 | /** | ||
| 149 | * \brief Like compute_component_inclusion_bits(), but uses computed | ||
| 150 | * intersection mesh, and exact coordinates everywhere. | ||
| 151 | * \details Kept for reference. Does not give correct result on mesh_bowl | ||
| 152 | * (to be understood). | ||
| 153 | * \see componte_component_inclusion_bits() | ||
| 154 | */ | ||
| 155 | index_t compute_component_inclusion_bits_exact_exact( | ||
| 156 | index_t component, index_t v | ||
| 157 | ); | ||
| 158 | |||
| 159 | /** | ||
| 160 | * \brief Merge coplanar facets and retriangulate them using a | ||
| 161 | * Constrained Delaunay triangulation | ||
| 162 | * \param[in] angle_tolerance angle tolerance for detecting coplanar | ||
| 163 | * facets and colinear edges (in degrees) | ||
| 164 | */ | ||
| 165 | void simplify_coplanar_facets(double angle_tolerance = 0.0); | ||
| 166 | |||
| 167 | /** | ||
| 168 | * \brief Display information while computing the intersection. | ||
| 169 | * Default is unset. | ||
| 170 | */ | ||
| 171 | 61 | void set_verbose(bool x) { | |
| 172 | 61 | verbose_ = x; | |
| 173 |
3/4✓ Branch 0 taken 47 times.
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 47 times.
|
61 | if(!verbose_ && fine_verbose_) { |
| 174 | ✗ | fine_verbose_ = false; | |
| 175 | } | ||
| 176 | 61 | } | |
| 177 | |||
| 178 | /** | ||
| 179 | * \brief Display detailed information while computing the intersection. | ||
| 180 | * Default is unset. | ||
| 181 | */ | ||
| 182 | 57 | void set_fine_verbose(bool x) { | |
| 183 | 57 | fine_verbose_ = x; | |
| 184 |
3/4✓ Branch 0 taken 13 times.
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13 times.
|
57 | if(fine_verbose_ && !verbose_) { |
| 185 | ✗ | verbose_ = true; | |
| 186 | } | ||
| 187 | 57 | } | |
| 188 | |||
| 189 | /** | ||
| 190 | * \brief Sets the threshold from which triangle is considered | ||
| 191 | * to be a monster. | ||
| 192 | * \details Monster triangles are saved to a file for the zoo. | ||
| 193 | * \param[in] nb if a triangle has more than \p nb intersections | ||
| 194 | * in it, then it is considered to be a monster. | ||
| 195 | */ | ||
| 196 | 13 | void set_monster_threshold(index_t nb) { | |
| 197 | 13 | monster_threshold_ = nb; | |
| 198 | 13 | } | |
| 199 | |||
| 200 | /** | ||
| 201 | * \brief In dry run mode, the computed local triangulations | ||
| 202 | * are not inserted in the global mesh. This is for benchmarking. | ||
| 203 | * Default is off. | ||
| 204 | */ | ||
| 205 | 13 | void set_dry_run(bool x) { | |
| 206 | 13 | dry_run_ = x; | |
| 207 | 13 | } | |
| 208 | |||
| 209 | /** | ||
| 210 | * \brief If set, compute constrained Delaunay triangulation | ||
| 211 | * in the intersected triangles. If there are intersections | ||
| 212 | * in coplanar facets, it guarantees uniqueness of their | ||
| 213 | * triangulation. Default is set. | ||
| 214 | */ | ||
| 215 | 57 | void set_delaunay(bool x) { | |
| 216 | 57 | delaunay_ = x; | |
| 217 | 57 | } | |
| 218 | |||
| 219 | /** | ||
| 220 | * \brief detect and compute intersections between facets that share | ||
| 221 | * a facet or an edge. Set to false if input is a set of conformal | ||
| 222 | * meshes. Default is set. | ||
| 223 | */ | ||
| 224 | 57 | void set_detect_intersecting_neighbors(bool x) { | |
| 225 | 57 | detect_intersecting_neighbors_ = x; | |
| 226 | 57 | } | |
| 227 | |||
| 228 | /** | ||
| 229 | * \brief Specifies whether surfaces should be duplicated and | ||
| 230 | * radial edges sorted in order to create the volumetric | ||
| 231 | * partition yielded by the intersection | ||
| 232 | * \param[in] x true if radial edges should be sorted. Default is | ||
| 233 | * set | ||
| 234 | */ | ||
| 235 | 16 | void set_radial_sort(bool x) { | |
| 236 | 16 | use_radial_sort_ = x; | |
| 237 | 16 | } | |
| 238 | |||
| 239 | /** | ||
| 240 | * \brief Optionally save the skeleton (that is, the collection of | ||
| 241 | * non-manifold edges) to a given mesh. This option is not compatible | ||
| 242 | * with dry_run (throws an assertion fail if set). | ||
| 243 | * \param[in] skeleton a pointer to the mesh that will receive the | ||
| 244 | * skeleton. | ||
| 245 | * \param[in] trim_fins if set, do not keep bundles that have | ||
| 246 | * less than three halfedges. | ||
| 247 | */ | ||
| 248 | ✗ | void set_build_skeleton(Mesh* skeleton, bool trim_fins=false) { | |
| 249 | ✗ | skeleton_ = skeleton; | |
| 250 | ✗ | skeleton_trim_fins_ = trim_fins; | |
| 251 | ✗ | } | |
| 252 | |||
| 253 | /** | ||
| 254 | * \brief Specifies that attributes should be interpolated | ||
| 255 | * \param[in] x true if attributes should be interpolated, | ||
| 256 | * false otherwise. Default is false. | ||
| 257 | */ | ||
| 258 | ✗ | void set_interpolate_attributes(bool x) { | |
| 259 | ✗ | interpolate_attributes_ = x; | |
| 260 | ✗ | } | |
| 261 | |||
| 262 | protected: | ||
| 263 | /** | ||
| 264 | * \brief substep of intersect(), prepares the mesh | ||
| 265 | * \details Tesselates the facets if they are not triangulated, | ||
| 266 | * creates the operand bit for boolean op classification, removes | ||
| 267 | * the exactly degenerate triangles, colocate the points, | ||
| 268 | * optionally scales the coordinates and sets symbolic perturbation | ||
| 269 | * mode to lexicographic. | ||
| 270 | */ | ||
| 271 | void intersect_prologue(); | ||
| 272 | |||
| 273 | /** | ||
| 274 | * \brief substep of intersect(), finds all the intersection points | ||
| 275 | * and segments. | ||
| 276 | * \param[out] intersections the vector of IsectInfo. Each IsectInfo | ||
| 277 | * is either an intersection vertex or a pair of intersection | ||
| 278 | * vertices. Intersection vertices are represented in symbolic | ||
| 279 | * form, as a couple of triangle indices plus a couple of triangle | ||
| 280 | * subregion id (TriangleRegion). | ||
| 281 | * \details First uses a MeshFacetsAABB to detect candidate pairs | ||
| 282 | * of intersecting triangles, then calls triangles_intersection() | ||
| 283 | * in parallel. Finally, mesh facets are shuffled randomly, to | ||
| 284 | * ensure balanced multithreading for the subsequent steps. | ||
| 285 | */ | ||
| 286 | void intersect_get_intersections(vector<IsectInfo>& intersections); | ||
| 287 | |||
| 288 | /** | ||
| 289 | * \brief substep of intersect(), inserts the intersection points | ||
| 290 | * and segments into the triangles. | ||
| 291 | * \param[in,out] intersections the vector of IsectInfo. Each IsectInfo | ||
| 292 | * is either an intersection vertex or a pair of intersection | ||
| 293 | * vertices. Intersection vertices are represented in symbolic | ||
| 294 | * form, as a couple of triangle indices plus a couple of triangle | ||
| 295 | * subregion id (TriangleRegion). | ||
| 296 | * \details Uses MeshInTriangle, a class derived from CDTBase2d, | ||
| 297 | * that computes a constrained Delaunay triangulation with | ||
| 298 | * intersection points represented with exact coordinates. | ||
| 299 | * Operates in parallel. Each thread computes constrained | ||
| 300 | * Delaunay triangulations independently, and commits them in the | ||
| 301 | * resulting mesh (with a lock to protect concurrent accesses). | ||
| 302 | * The initial mesh is copied (and kept in the mesh_copy_ member), | ||
| 303 | * so that concurrent read access do not need a lock. | ||
| 304 | */ | ||
| 305 | void intersect_remesh_intersections(vector<IsectInfo>& intersections); | ||
| 306 | |||
| 307 | /** | ||
| 308 | * \brief subset of intersect(), cleans the resulting mesh and | ||
| 309 | * undoes optional geometric normalization. | ||
| 310 | * \param[in] intersections the vector of IsectInfo. Each IsectInfo | ||
| 311 | * is either an intersection vertex or a pair of intersection | ||
| 312 | * vertices. Intersection vertices are represented in symbolic | ||
| 313 | * form, as a couple of triangle indices plus a couple of triangle | ||
| 314 | * subregion id (TriangleRegion). | ||
| 315 | * \details find the intersection that landed exactly onto an | ||
| 316 | * existing mesh vertex and merges them. Removes the initial | ||
| 317 | * triangles that had intersections (they are replaced with new | ||
| 318 | * triangles). Merges duplicated triangles that come from | ||
| 319 | * coplanar regions. Undoes geometric normalizations. Restores | ||
| 320 | * initial symbolic perturbation mode. | ||
| 321 | */ | ||
| 322 | void intersect_epilogue(const vector<IsectInfo>& intersections); | ||
| 323 | |||
| 324 | |||
| 325 | /** | ||
| 326 | * \brief Acquires a lock on this mesh | ||
| 327 | * \details A single thread can have the lock. When multiple threads | ||
| 328 | * want the lock, the ones that do not have it keep waiting until | ||
| 329 | * the one that owns the lock calls unlock(). All threads that modify | ||
| 330 | * the target mesh should call this function | ||
| 331 | * \see unlock() | ||
| 332 | */ | ||
| 333 | 15505 | void lock() { | |
| 334 | 15505 | Process::acquire_spinlock(lock_); | |
| 335 | 15505 | } | |
| 336 | |||
| 337 | /** | ||
| 338 | * \brief Releases the lock associated with this mesh | ||
| 339 | */ | ||
| 340 | 15505 | void unlock() { | |
| 341 | 15505 | Process::release_spinlock(lock_); | |
| 342 | 15505 | } | |
| 343 | |||
| 344 | /** | ||
| 345 | * \brief Gets the exact point associated with a vertex | ||
| 346 | * \details If the vertex has explicit exact coordinates associated | ||
| 347 | * with it, they are returned, else an exact ExactPoint is constructed | ||
| 348 | * from the double-precision coordinates stored in the mesh | ||
| 349 | * \param[in] v a vertex of the mesh | ||
| 350 | * \return the exact coordinates of this vertex, as a vector in | ||
| 351 | * homogeneous coordinates stored as expansions | ||
| 352 | */ | ||
| 353 | ExactPoint exact_vertex(index_t v) const; | ||
| 354 | |||
| 355 | /** | ||
| 356 | * \brief Tests whether a given vertex is an original mesh vertex or an | ||
| 357 | * intersection | ||
| 358 | * \param[in] v a vertex of the mesh | ||
| 359 | * \retval true if v is an original vertex of the mesh | ||
| 360 | * \retval false if v is an intersection vertex, with exact coordinates | ||
| 361 | */ | ||
| 362 | 235650 | bool is_original_vertex(index_t v) const { | |
| 363 | 235650 | return (vertex_to_exact_point_[v] == nullptr); | |
| 364 | } | ||
| 365 | |||
| 366 | /** | ||
| 367 | * \brief Finds or creates a vertex in the mesh, by exact coordinates | ||
| 368 | * \details If there is already a vertex with coordinates \p p, then | ||
| 369 | * the existing vertex is returned, else a new vertex is constructed. | ||
| 370 | * Note that only the vertices created by find_or_create_vertex() can | ||
| 371 | * be returned as existing vertices. Mesh vertices stored as double- | ||
| 372 | * precision coordinates are not retreived by this function. | ||
| 373 | * \param[in] p the exact coordinates of a point | ||
| 374 | * \return the index of a mesh vertex with \p p as coordinates | ||
| 375 | */ | ||
| 376 | index_t find_or_create_exact_vertex(const ExactPoint& p); | ||
| 377 | |||
| 378 | /** | ||
| 379 | * \brief Gets the target mesh | ||
| 380 | * \return a modifiable reference to the mesh that was passed to | ||
| 381 | * the constructor | ||
| 382 | */ | ||
| 383 | 264199 | Mesh& target_mesh() { | |
| 384 | 264199 | return mesh_; | |
| 385 | } | ||
| 386 | |||
| 387 | /** | ||
| 388 | * \brief Gets the target mesh | ||
| 389 | * \return a const reference to the mesh that was passed to | ||
| 390 | * the constructor | ||
| 391 | */ | ||
| 392 | 190 | const Mesh& target_mesh() const { | |
| 393 | 190 | return mesh_; | |
| 394 | } | ||
| 395 | |||
| 396 | /** | ||
| 397 | * \brief Gets a copy of the initial mesh passed to the constructor | ||
| 398 | * \details It is used by the multithreaded mesh intersection algorithm. | ||
| 399 | * Each thread needs to both access the initial geometry and create | ||
| 400 | * new vertices and triangles in the target mesh. Creating new mesh | ||
| 401 | * elements can reallocate the internal vectors of the mesh, and | ||
| 402 | * change the address of the elements. This should not occur while | ||
| 403 | * another thread is reading the mesh. Copying the initial geometry | ||
| 404 | * in another mesh prevents this type of problems. | ||
| 405 | * \return a const reference to the mesh that was copied from the one | ||
| 406 | * passed to the constructor | ||
| 407 | */ | ||
| 408 | 514 | const Mesh& readonly_mesh() const { | |
| 409 | 514 | return mesh_copy_; | |
| 410 | } | ||
| 411 | |||
| 412 | class RadialSort; | ||
| 413 | |||
| 414 | /** | ||
| 415 | * \brief Builds the Weiler model | ||
| 416 | * \details The Weiler model is a volumetric representation, where each | ||
| 417 | * facet is on the boundary of a closed region. Facets are duplicated, | ||
| 418 | * so that when two regions touch each other, each region has its own | ||
| 419 | * facet on the boundary. Two facets that touch in this way are | ||
| 420 | * connected by alpha3 links. Facets on the boundary of the same | ||
| 421 | * region are connected by alpha2 links. | ||
| 422 | */ | ||
| 423 | void build_Weiler_model(); | ||
| 424 | |||
| 425 | /** | ||
| 426 | * \brief Marks all the facets that are on the external shell | ||
| 427 | */ | ||
| 428 | void mark_external_shell(vector<index_t>& on_external_shell); | ||
| 429 | |||
| 430 | /** | ||
| 431 | * \brief Gets the vertices of the initial facet (in mesh_copy_) that | ||
| 432 | * supports a facet in the intersection mesh (in mesh_) | ||
| 433 | * \param[in] f the facet in mesh_ | ||
| 434 | * \return the index of the original facet in mesh_copy_ | ||
| 435 | */ | ||
| 436 | 370476 | index_t get_initial_facet(index_t f) const { | |
| 437 | 370476 | return original_facet_id_[f]; | |
| 438 | } | ||
| 439 | |||
| 440 | /** | ||
| 441 | * \brief Indicates whether the initial facet (in mesh_copy_) that | ||
| 442 | * supports a facet in the intersection mesh (in mesh_) has same | ||
| 443 | * orientation or not. | ||
| 444 | * \param[in] f the facet in mesh_ | ||
| 445 | * \retval false if \p f and the initial facet in mesh_copy_ have the | ||
| 446 | * same orientation | ||
| 447 | * \retval true otherwise | ||
| 448 | */ | ||
| 449 | 518150 | bool initial_facet_is_flipped(index_t f) const { | |
| 450 |
4/6✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 518150 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 373633 times.
✓ Branch 8 taken 144517 times.
|
518150 | return !f_is_flipped_.is_bound() || f_is_flipped_[f]; |
| 451 | } | ||
| 452 | |||
| 453 | /** | ||
| 454 | * \brief Gets the vertices of the initial facet (in mesh_copy_) that | ||
| 455 | * supports a facet in the intersection mesh (in mesh_) | ||
| 456 | * \details Orientation is preserved. It is important, since it makes | ||
| 457 | * it possible to call predicates with points that have simpler | ||
| 458 | * coordinates | ||
| 459 | * \param[in] f the facet in mesh_ | ||
| 460 | * \return the three vertices of the initial facet in mesh_copy_ | ||
| 461 | * as a tuple of vec3 | ||
| 462 | */ | ||
| 463 | 518150 | std::tuple<vec3, vec3, vec3> get_initial_facet_vertices(index_t f) const { | |
| 464 | // All facets are duplicated before radial sort. If f is one of | ||
| 465 | // the duplicated facets then its orientation is flipped as | ||
| 466 | // compared to initial facet. | ||
| 467 |
1/2✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
|
518150 | index_t orig_f = original_facet_id_[f]; |
| 468 |
1/2✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
|
518150 | vec3 p1 = mesh_copy_.facets.point(orig_f,0); |
| 469 |
1/2✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
|
518150 | vec3 p2 = mesh_copy_.facets.point(orig_f,1); |
| 470 |
1/2✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
|
518150 | vec3 p3 = mesh_copy_.facets.point(orig_f,2); |
| 471 |
3/4✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 373633 times.
✓ Branch 4 taken 144517 times.
|
518150 | if(initial_facet_is_flipped(f)) { |
| 472 | 373633 | std::swap(p1,p3); | |
| 473 | } | ||
| 474 |
1/2✓ Branch 1 taken 518150 times.
✗ Branch 2 not taken.
|
1036300 | return std::make_tuple(p1,p2,p3); |
| 475 | } | ||
| 476 | |||
| 477 | protected: | ||
| 478 | |||
| 479 | /** | ||
| 480 | * A class for sorting triangles around their common radial edge. | ||
| 481 | */ | ||
| 482 | class GEOGRAM_API RadialSort { | ||
| 483 | public: | ||
| 484 | /** | ||
| 485 | * \brief RadialSort constructor | ||
| 486 | * \param[in] I a reference to the MeshSurfaceIntersection | ||
| 487 | */ | ||
| 488 | 190 | RadialSort(const MeshSurfaceIntersection& I) : | |
| 489 | 190 | I_(I), | |
| 490 | 190 | mesh_(I_.target_mesh()), | |
| 491 | 190 | h_ref_(NO_INDEX), | |
| 492 | 190 | degenerate_(false) | |
| 493 | { | ||
| 494 | 190 | } | |
| 495 | |||
| 496 | /** | ||
| 497 | * \brief Initializes radial sorting around a given halfedge | ||
| 498 | * \param[in] h_ref the reference halfedge | ||
| 499 | */ | ||
| 500 | void init(index_t h_ref); | ||
| 501 | |||
| 502 | /** | ||
| 503 | * \brief Compares two halfedges | ||
| 504 | * \param[in] h1 , h2 the two halfedges | ||
| 505 | * \retval true if \p h1 should be before \p h2 in radial order | ||
| 506 | * \retval false otherwise | ||
| 507 | */ | ||
| 508 | bool operator()(index_t h1, index_t h2) const; | ||
| 509 | |||
| 510 | /** | ||
| 511 | * \brief Tests if a degeneracy was encountered | ||
| 512 | * \retval true if there were two coplanar triangles on the same | ||
| 513 | * side relative to h_ref | ||
| 514 | * \retval false otherwise | ||
| 515 | */ | ||
| 516 | 3820 | bool degenerate() const { | |
| 517 | 3820 | return degenerate_; | |
| 518 | } | ||
| 519 | |||
| 520 | protected: | ||
| 521 | /** | ||
| 522 | * \brief Computes the relative orientations of two halfedges | ||
| 523 | * \param[in] h1 , h2 the two halfedges | ||
| 524 | * \retval POSITIVE if going from \p h1's triangle to | ||
| 525 | * \p h2's triangle is a left turn (with h_ref facing to you) | ||
| 526 | * \retval ZERO if \p h1 and \p h2 have co-linear normals | ||
| 527 | * \retval NEGATIVE otherwise | ||
| 528 | */ | ||
| 529 | Sign h_orient(index_t h1, index_t h2) const; | ||
| 530 | |||
| 531 | /** | ||
| 532 | * \brief Computes the normal orientation of a halfedge | ||
| 533 | * relative to h_ref | ||
| 534 | * \return the sign of the dot product between h_ref's triangle | ||
| 535 | * normal and \p h2's triangle normal. | ||
| 536 | */ | ||
| 537 | Sign h_refNorient(index_t h2) const; | ||
| 538 | |||
| 539 | /** | ||
| 540 | * \brief Computes the normal to a facet with exact coordinates | ||
| 541 | * \param[in] h an halfedge incident to the facet | ||
| 542 | * \return the normal to the facet with exact coordinates | ||
| 543 | */ | ||
| 544 | exact::vec3 normal(index_t h) const; | ||
| 545 | |||
| 546 | /** | ||
| 547 | * \brief This function is called whenever radial sort encounters | ||
| 548 | * a configuration not supposed to happen. It positions the generate_ | ||
| 549 | * flag for this RadialSort. It can happen when using the | ||
| 550 | * expansion-based open-source kernel, that can encounter | ||
| 551 | * overflows or underflows. In this case, one may need the geogram+ | ||
| 552 | * arithmetic kernel (marketed by the TESSAEL company). | ||
| 553 | */ | ||
| 554 | void report_problem(const char* message) const; | ||
| 555 | |||
| 556 | private: | ||
| 557 | const MeshSurfaceIntersection& I_; | ||
| 558 | const Mesh& mesh_; | ||
| 559 | index_t h_ref_; // reference halfedge | ||
| 560 | exact::vec3 N_ref_; // normal to reference triangle (exact) | ||
| 561 | mutable bool degenerate_; | ||
| 562 | }; | ||
| 563 | |||
| 564 | protected: | ||
| 565 | Process::spinlock lock_; | ||
| 566 | Mesh& mesh_; | ||
| 567 | Mesh mesh_copy_; | ||
| 568 | Attribute<const ExactPoint*> vertex_to_exact_point_; | ||
| 569 | Attribute<index_t> original_facet_id_; // mesh_ facet to mesh_copy_ facet | ||
| 570 | Attribute<bool> f_is_flipped_; // mesh_ facet is flipped wrt mesh_copy_ | ||
| 571 | |||
| 572 | #if defined(GEOGRAM_USE_EXACT_NT) && defined(GEOGRAM_EXACT_NT_IS_MPF_NT) | ||
| 573 | // Exact points are canonicalized | ||
| 574 | // (by Numeric::optimize_number_representation(vec3HEx)) so | ||
| 575 | // we can use this comparator that makes the global vertex map | ||
| 576 | // much much faster. | ||
| 577 | typedef vec3HExLexicoCompareCanonical ExactPointCompare; | ||
| 578 | #else | ||
| 579 | // Generic comparator for global vertex map. | ||
| 580 | typedef vec3HgLexicoCompare<exact::scalar> ExactPointCompare; | ||
| 581 | #endif | ||
| 582 | std::map<ExactPoint,index_t,ExactPointCompare> exact_point_to_vertex_; | ||
| 583 | |||
| 584 | bool verbose_; | ||
| 585 | bool fine_verbose_; | ||
| 586 | bool delaunay_; | ||
| 587 | bool detect_intersecting_neighbors_; | ||
| 588 | bool use_radial_sort_; | ||
| 589 | |||
| 590 | PCK::SOSMode SOS_bkp_; | ||
| 591 | |||
| 592 | index_t monster_threshold_; | ||
| 593 | bool dry_run_; | ||
| 594 | friend class MeshInTriangle; | ||
| 595 | friend class CoplanarFacets; | ||
| 596 | |||
| 597 | Mesh* skeleton_; | ||
| 598 | bool skeleton_trim_fins_; | ||
| 599 | bool interpolate_attributes_; | ||
| 600 | |||
| 601 | bool has_operand_bits_; | ||
| 602 | /***************************************************/ | ||
| 603 | |||
| 604 | /** | ||
| 605 | * \brief Halfedfge-like API wrappers on top of a triangulated mesh | ||
| 606 | * \details These are volumetric halfedges, also called | ||
| 607 | * combinatorial 3-map, with both volumetric links (alpha3) | ||
| 608 | * and surfacic link (alpha2). | ||
| 609 | * One may refer to this webpage for the definition of a 3-map: | ||
| 610 | * https://doc.cgal.org/latest/Combinatorial_map/ | ||
| 611 | */ | ||
| 612 | class Halfedges { | ||
| 613 | public: | ||
| 614 | |||
| 615 | /** | ||
| 616 | * \brief Halfedges constructor | ||
| 617 | * \param[in] I a reference to the MeshSurfaceIntersection | ||
| 618 | */ | ||
| 619 | 61 | Halfedges(MeshSurfaceIntersection& I) : mesh_(I.mesh_) { | |
| 620 | 61 | } | |
| 621 | |||
| 622 | /** | ||
| 623 | * \brief Halfedges destructor | ||
| 624 | */ | ||
| 625 | 61 | ~Halfedges() { | |
| 626 | // TODO: destroy alpha3 attribute (kept now for debugging | ||
| 627 | 61 | } | |
| 628 | |||
| 629 | /** | ||
| 630 | * \brief Initializes the structure | ||
| 631 | * \details Needs to be called before any other function | ||
| 632 | */ | ||
| 633 | 58 | void initialize() { | |
| 634 |
1/2✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
|
116 | facet_corner_alpha3_.bind( |
| 635 |
1/2✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
|
116 | mesh_.facet_corners.attributes(), "alpha3" |
| 636 | ); | ||
| 637 | 58 | } | |
| 638 | |||
| 639 | /** | ||
| 640 | * \brief Gets the number of halfedegs in the map | ||
| 641 | * \return the number of halfedges, that is, three times | ||
| 642 | * the number of triangles (halfedges are not stored explicitly). | ||
| 643 | */ | ||
| 644 | index_t nb() const { | ||
| 645 | return mesh_.facet_corners.nb(); | ||
| 646 | } | ||
| 647 | |||
| 648 | /** | ||
| 649 | * \brief used by range-based for | ||
| 650 | * \return a non-iterator corresponding to the first index. | ||
| 651 | */ | ||
| 652 | index_as_iterator begin() const { | ||
| 653 | return index_as_iterator(0); | ||
| 654 | } | ||
| 655 | |||
| 656 | /** | ||
| 657 | * \brief used by range-based for | ||
| 658 | * \return a non-iterator to one position past the last index. | ||
| 659 | */ | ||
| 660 | index_as_iterator end() const { | ||
| 661 | return index_as_iterator(nb()); | ||
| 662 | } | ||
| 663 | |||
| 664 | /** | ||
| 665 | * \brief Gets the facet associated to a halfedge | ||
| 666 | * \param[in] h a halfedge index | ||
| 667 | * \return the facet index, that is, h/3 | ||
| 668 | */ | ||
| 669 | 178693 | index_t facet(index_t h) const { | |
| 670 | 178693 | return h/3; | |
| 671 | } | ||
| 672 | |||
| 673 | /** | ||
| 674 | * \brief gets the surfacic neighbor of a halfedge | ||
| 675 | * \details see definition of a combinatorial 3-map | ||
| 676 | * here: https://doc.cgal.org/latest/Combinatorial_map/ | ||
| 677 | * \param[in] h a halfedge index | ||
| 678 | * \return another halfedge in the same surface, connecting the same | ||
| 679 | * vertices as \p h, but in opposite order | ||
| 680 | * \see sew2() | ||
| 681 | */ | ||
| 682 | index_t alpha2(index_t h) const { | ||
| 683 | index_t t1 = facet(h); | ||
| 684 | index_t t2 = mesh_.facet_corners.adjacent_facet(h); | ||
| 685 | if(t2 == NO_INDEX) { | ||
| 686 | return NO_INDEX; | ||
| 687 | } | ||
| 688 | for(index_t h2: mesh_.facets.corners(t2)) { | ||
| 689 | if(mesh_.facet_corners.adjacent_facet(h2) == t1) { | ||
| 690 | return h2; | ||
| 691 | } | ||
| 692 | } | ||
| 693 | geo_assert_not_reached; | ||
| 694 | } | ||
| 695 | |||
| 696 | /** | ||
| 697 | * \brief gets the volumetric neighbor of a halfedge | ||
| 698 | * \details see definition of a combinatorial 3-map | ||
| 699 | * here: https://doc.cgal.org/latest/Combinatorial_map/ | ||
| 700 | * \param[in] h a halfedge index | ||
| 701 | * \return another halfedge in a different volume, connecting | ||
| 702 | * the same vertices as \p h, but in opposite order | ||
| 703 | * \see sew3() | ||
| 704 | */ | ||
| 705 | 1956817 | index_t alpha3(index_t h) const { | |
| 706 | 1956817 | return facet_corner_alpha3_[h]; | |
| 707 | } | ||
| 708 | |||
| 709 | /** | ||
| 710 | * \brief gets the volumetric neighbor of a facet | ||
| 711 | * \param[in] f a facet | ||
| 712 | * \return a facet with the same vertices as \p f but in | ||
| 713 | * opposite index | ||
| 714 | */ | ||
| 715 | 671754 | index_t facet_alpha3(index_t f) const { | |
| 716 | 671754 | return alpha3(3*f)/3; | |
| 717 | } | ||
| 718 | |||
| 719 | /** | ||
| 720 | * \brief gets a vertex of an halfedge | ||
| 721 | * \param[in] h the halfedge | ||
| 722 | * \param[in] dlv the local index of the vertex, in {0,1,2} | ||
| 723 | * \return | ||
| 724 | * - if \p dlv = 0 returns the origin vertex of \p h | ||
| 725 | * - if \p dlv = 1 returns the destination vertex of \p h | ||
| 726 | * - if \p dlv = 2 returns the vertex of the facet adjacent to \p h | ||
| 727 | * that is neither the origin nor the destination of \p h | ||
| 728 | */ | ||
| 729 | 44658246 | index_t vertex(index_t h, index_t dlv) const { | |
| 730 | 44658246 | index_t f = h/3; | |
| 731 | 44658246 | index_t lv = (h+dlv)%3; | |
| 732 | 44658246 | return mesh_.facets.vertex(f,lv); | |
| 733 | } | ||
| 734 | |||
| 735 | |||
| 736 | /** | ||
| 737 | * \brief Creates a surfacic link between two halfedges | ||
| 738 | * \param[in] h1 , h2 the two halfedges to be connected | ||
| 739 | * \pre \p h1 and \p h2 should have the same origins and | ||
| 740 | * destinations but in reverse order (\p h1 's origin should | ||
| 741 | * be \p h2 's destination and vice-versa). | ||
| 742 | * \see alpha2() | ||
| 743 | */ | ||
| 744 | 683476 | void sew2(index_t h1, index_t h2) { | |
| 745 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 683476 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
683476 | geo_debug_assert(vertex(h1,0) == vertex(h2,1)); |
| 746 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 683476 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
683476 | geo_debug_assert(vertex(h2,0) == vertex(h1,1)); |
| 747 | 683476 | index_t t1 = h1/3; | |
| 748 | 683476 | index_t t2 = h2/3; | |
| 749 | 683476 | mesh_.facet_corners.set_adjacent_facet(h1,t2); | |
| 750 | 683476 | mesh_.facet_corners.set_adjacent_facet(h2,t1); | |
| 751 | 683476 | } | |
| 752 | |||
| 753 | /** | ||
| 754 | * \brief Creates a volumetric link between two halfedges | ||
| 755 | * \param[in] h1 , h2 the two halfedges to be connected | ||
| 756 | * \pre \p h1 and \p h2 should have the same origins and | ||
| 757 | * destinations but in reverse order (\p h1 's origin should | ||
| 758 | * be \p h2 's destination and vice-versa). | ||
| 759 | * \see alpha3() | ||
| 760 | */ | ||
| 761 | 601587 | void sew3(index_t h1, index_t h2) { | |
| 762 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 601587 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
601587 | geo_debug_assert(vertex(h1,0) == vertex(h2,1)); |
| 763 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 601587 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
601587 | geo_debug_assert(vertex(h2,0) == vertex(h1,1)); |
| 764 | 601587 | facet_corner_alpha3_[h1] = h2; | |
| 765 | 601587 | facet_corner_alpha3_[h2] = h1; | |
| 766 | 601587 | } | |
| 767 | |||
| 768 | private: | ||
| 769 | Mesh& mesh_; | ||
| 770 | Attribute<index_t> facet_corner_alpha3_; | ||
| 771 | } halfedges_; | ||
| 772 | |||
| 773 | /***************************************************/ | ||
| 774 | |||
| 775 | /** | ||
| 776 | * \brief Represents the set of radial halfedge bundles | ||
| 777 | * \details A Radial bundle corresponds to the set of halfedges | ||
| 778 | * connecting the same pair of vertices (and in the same order). | ||
| 779 | */ | ||
| 780 | class RadialBundles { | ||
| 781 | public: | ||
| 782 | |||
| 783 | /** | ||
| 784 | * \brief RadialBundles constructor | ||
| 785 | * \param[in] I a reference to the MeshSurfaceIntersectionx | ||
| 786 | */ | ||
| 787 | 61 | RadialBundles(MeshSurfaceIntersection& I) : I_(I), mesh_(I.mesh_) { | |
| 788 | 61 | } | |
| 789 | |||
| 790 | /** | ||
| 791 | * \brief Initializes the structure | ||
| 792 | * \details Needs to be called before any other function | ||
| 793 | */ | ||
| 794 | void initialize(); | ||
| 795 | |||
| 796 | /** | ||
| 797 | * \brief Gets the number of bundles | ||
| 798 | */ | ||
| 799 | 5912683 | index_t nb() const { | |
| 800 | 5912683 | return bndl_start_.size() - 1; | |
| 801 | } | ||
| 802 | |||
| 803 | /** | ||
| 804 | * \brief used by range-based for | ||
| 805 | * \return a non-iterator corresponding to the first bundle | ||
| 806 | */ | ||
| 807 | 116 | index_as_iterator begin() const { | |
| 808 | 116 | return index_as_iterator(0); | |
| 809 | } | ||
| 810 | |||
| 811 | /** | ||
| 812 | * \brief used by range-based for | ||
| 813 | * \return a non-iterator to one position past the last bundle | ||
| 814 | */ | ||
| 815 | 116 | index_as_iterator end() const { | |
| 816 |
1/2✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
|
116 | return index_as_iterator(nb()); |
| 817 | } | ||
| 818 | |||
| 819 | /** | ||
| 820 | * \brief Gets the number of halfedges in a bundle | ||
| 821 | * \param[in] bndl the bundle | ||
| 822 | * \return the number of halfedges in \p bndl | ||
| 823 | */ | ||
| 824 | 3718175 | index_t nb_halfedges(index_t bndl) const { | |
| 825 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 3718175 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
3718175 | geo_debug_assert(bndl < nb()); |
| 826 | 3718175 | return bndl_start_[bndl+1] - bndl_start_[bndl]; | |
| 827 | } | ||
| 828 | |||
| 829 | /** | ||
| 830 | * \brief Gets a halfedge in a bundle from local index | ||
| 831 | * \param[in] bndl the bundle | ||
| 832 | * \param[in] li the local index of the halfedge in the bundle, | ||
| 833 | * in [0 .. nb_halfedges(bndl)-1] | ||
| 834 | * \return the halfedge | ||
| 835 | */ | ||
| 836 | 1353043 | index_t halfedge(index_t bndl, index_t li) const { | |
| 837 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 1353043 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
1353043 | geo_debug_assert(bndl < nb()); |
| 838 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 1353043 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
1353043 | geo_debug_assert(li < nb_halfedges(bndl)); |
| 839 | 1353043 | return H_[bndl_start_[bndl] + li]; | |
| 840 | } | ||
| 841 | |||
| 842 | /** | ||
| 843 | * \brief Sets a halfedge in a bundle | ||
| 844 | * \param[in] bndl the bundle | ||
| 845 | * \param[in] li the local index of the halfedge in the bunble, | ||
| 846 | * in [0 .. nb_halfedges(bndl)-1] | ||
| 847 | * \param[in] h the new halfedge | ||
| 848 | */ | ||
| 849 | 67980 | void set_halfedge(index_t bndl, index_t li, index_t h) { | |
| 850 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 67980 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
67980 | geo_debug_assert(bndl < nb()); |
| 851 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 67980 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
67980 | geo_debug_assert(li < nb_halfedges(bndl)); |
| 852 | 67980 | H_[bndl_start_[bndl] + li] = h; | |
| 853 | 67980 | } | |
| 854 | |||
| 855 | /** | ||
| 856 | * \brief gets the halfedges in a bundle | ||
| 857 | * \param[in] bndl bundle index | ||
| 858 | * \return a modifiable sequence of halfedge indices | ||
| 859 | */ | ||
| 860 | 21836 | index_ptr_range halfedges(index_t bndl) { | |
| 861 | return index_ptr_range( | ||
| 862 | 21836 | H_, bndl_start_[bndl], bndl_start_[bndl+1] | |
| 863 | 21836 | ); | |
| 864 | } | ||
| 865 | |||
| 866 | /** | ||
| 867 | * \brief gets the halfedges in a bundle | ||
| 868 | * \param[in] bndl bundle index | ||
| 869 | * \return a non-modifiable sequence of halfedge indices | ||
| 870 | */ | ||
| 871 | const_index_ptr_range halfedges(index_t bndl) const { | ||
| 872 | return const_index_ptr_range( | ||
| 873 | H_, bndl_start_[bndl], bndl_start_[bndl+1] | ||
| 874 | ); | ||
| 875 | } | ||
| 876 | |||
| 877 | /** | ||
| 878 | * \brief gets one of the vertices at the two extremities of a bundle | ||
| 879 | * \param[in] bndl bundle index | ||
| 880 | * \param[in] lv local vertex index, in {0,1} | ||
| 881 | * \return if \p lv = 0 the source vertex, if \p lv = 1 the | ||
| 882 | * destination vertex | ||
| 883 | */ | ||
| 884 | 80082 | index_t vertex(index_t bndl, index_t lv) const { | |
| 885 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 80082 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
80082 | geo_debug_assert(bndl_start_[bndl+1] - bndl_start_[bndl] > 0); |
| 886 | 80082 | index_t h = H_[bndl_start_[bndl]]; | |
| 887 | 80082 | return I_.halfedges_.vertex(h,lv); | |
| 888 | } | ||
| 889 | |||
| 890 | /** | ||
| 891 | * \brief gets the first bundle starting from a vertex | ||
| 892 | * \param[in] v the vertex | ||
| 893 | * \details bundles starting from the same vertex are chained | ||
| 894 | * \return the index of the first bundle starting from \p v, or | ||
| 895 | * NO_INDEX if there is no such bundle | ||
| 896 | */ | ||
| 897 | 65450 | index_t vertex_first_bundle(index_t v) const { | |
| 898 | 65450 | return v_first_bndl_[v]; | |
| 899 | } | ||
| 900 | |||
| 901 | /** | ||
| 902 | * \brief gets the next bundle around a vertex | ||
| 903 | * \param[in] bndl the bundle | ||
| 904 | * \details bundles starting from the same vertex are chained | ||
| 905 | * \return the index of the next bundle that has the same origin | ||
| 906 | * vertex as \p bndl, or NO_INDEX if there is no such bundle | ||
| 907 | */ | ||
| 908 | 109701 | index_t next_around_vertex(index_t bndl) const { | |
| 909 | 109701 | return bndl_next_around_v_[bndl]; | |
| 910 | } | ||
| 911 | |||
| 912 | /** | ||
| 913 | * \brief gets the bumber of bundles around a vertex | ||
| 914 | * \param[in] v the vertex | ||
| 915 | * \return the number of bundles starting from \p v | ||
| 916 | */ | ||
| 917 | 36410 | index_t nb_bundles_around_vertex(index_t v) const { | |
| 918 | 36410 | index_t result = 0; | |
| 919 | 36410 | for( | |
| 920 | 36410 | index_t bndl = vertex_first_bundle(v); | |
| 921 |
2/2✓ Branch 0 taken 94854 times.
✓ Branch 1 taken 36410 times.
|
131264 | bndl != NO_INDEX; |
| 922 | 94854 | bndl = next_around_vertex(bndl) | |
| 923 | ) { | ||
| 924 | 94854 | ++result; | |
| 925 | } | ||
| 926 | 36410 | return result; | |
| 927 | } | ||
| 928 | |||
| 929 | /** | ||
| 930 | * \brief gets the opposite bundle | ||
| 931 | * \param[in] bndl a bundle index | ||
| 932 | * \return the bundle connecting the same vertices as a given | ||
| 933 | * bundle but in the reverse order | ||
| 934 | */ | ||
| 935 | 61385 | index_t opposite(index_t bndl) { | |
| 936 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 61385 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
61385 | geo_debug_assert(bndl < nb()); |
| 937 |
2/2✓ Branch 1 taken 30120 times.
✓ Branch 2 taken 31265 times.
|
61385 | return (bndl >= nb()/2) ? (bndl-nb()/2) : (bndl+nb()/2); |
| 938 | } | ||
| 939 | |||
| 940 | /** | ||
| 941 | * \brief gets the predecessor of a bundle along its polyline | ||
| 942 | * \return the bundle arriving at the source vertex if it exists and | ||
| 943 | * is unique, NO_INDEX otherwise | ||
| 944 | */ | ||
| 945 | 14574 | index_t prev_along_polyline(index_t bndl) { | |
| 946 | 14574 | index_t v = vertex(bndl,0); | |
| 947 |
2/2✓ Branch 1 taken 3685 times.
✓ Branch 2 taken 10889 times.
|
14574 | if(nb_bundles_around_vertex(v) != 2) { |
| 948 | 3685 | return NO_INDEX; | |
| 949 | } | ||
| 950 | 10889 | for( | |
| 951 | 10889 | index_t bndl2 = vertex_first_bundle(v); | |
| 952 |
1/2✓ Branch 1 taken 15227 times.
✗ Branch 2 not taken.
|
15227 | bndl2 != NO_INDEX; bndl2 = next_around_vertex(bndl2) |
| 953 | ) { | ||
| 954 |
2/2✓ Branch 0 taken 10889 times.
✓ Branch 1 taken 4338 times.
|
15227 | if(bndl2 != bndl) { |
| 955 | 10889 | return opposite(bndl2); | |
| 956 | } | ||
| 957 | } | ||
| 958 | ✗ | geo_assert_not_reached; | |
| 959 | } | ||
| 960 | |||
| 961 | /** | ||
| 962 | * \brief gets the successor of a bundle along its polyline | ||
| 963 | * \return the bundle originated at the destination vertex | ||
| 964 | * if it exists and is unique, NO_INDEX otherwise | ||
| 965 | */ | ||
| 966 | 21836 | index_t next_along_polyline(index_t bndl) { | |
| 967 | 21836 | index_t v = vertex(bndl,1); | |
| 968 |
2/2✓ Branch 1 taken 3685 times.
✓ Branch 2 taken 18151 times.
|
21836 | if(nb_bundles_around_vertex(v) != 2) { |
| 969 | 3685 | return NO_INDEX; | |
| 970 | } | ||
| 971 | 18151 | for( | |
| 972 | 18151 | index_t bndl2 = vertex_first_bundle(v); | |
| 973 |
1/2✓ Branch 1 taken 28660 times.
✗ Branch 2 not taken.
|
28660 | bndl2 != NO_INDEX; bndl2 = next_around_vertex(bndl2) |
| 974 | ) { | ||
| 975 |
2/2✓ Branch 1 taken 18151 times.
✓ Branch 2 taken 10509 times.
|
28660 | if(opposite(bndl2) != bndl) { |
| 976 | 18151 | return bndl2; | |
| 977 | } | ||
| 978 | } | ||
| 979 | ✗ | geo_assert_not_reached; | |
| 980 | } | ||
| 981 | |||
| 982 | /** | ||
| 983 | * \brief Sorts the halfedges of the bundle in-place | ||
| 984 | * \param[in] bndl the bundle | ||
| 985 | * \param[in] RS a RadialSort structure (that caches | ||
| 986 | * some information) | ||
| 987 | * \retval true if radial sort was successful | ||
| 988 | * \retval false otherwise (may happen with expansion_nt) | ||
| 989 | */ | ||
| 990 | 3820 | bool radial_sort(index_t bndl, RadialSort& RS) { | |
| 991 |
2/8✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3820 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
|
3820 | geo_debug_assert(bndl < nb()); |
| 992 |
2/4✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3820 times.
|
3820 | if(nb_halfedges(bndl) <= 2) { |
| 993 | ✗ | return true; | |
| 994 | } | ||
| 995 |
1/2✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
|
3820 | auto b = H_.begin() + std::ptrdiff_t(bndl_start_[bndl]); |
| 996 |
1/2✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
|
7640 | auto e = H_.begin() + std::ptrdiff_t(bndl_start_[bndl+1]); |
| 997 |
1/2✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
|
3820 | RS.init(*b); |
| 998 |
1/2✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
|
3820 | std::sort( |
| 999 | 24479 | b, e, [&RS](index_t h1, index_t h2) { | |
| 1000 | 24479 | return RS(h1,h2); | |
| 1001 | } | ||
| 1002 | ); | ||
| 1003 | 3820 | bool OK = !RS.degenerate(); | |
| 1004 |
1/2✓ Branch 1 taken 3820 times.
✗ Branch 2 not taken.
|
3820 | bndl_is_sorted_[bndl] = OK; |
| 1005 | 3820 | return OK; | |
| 1006 | } | ||
| 1007 | |||
| 1008 | /** | ||
| 1009 | * \brief Sets the halfedges of a bundle | ||
| 1010 | * \details Used when radial sorting can be replaced with | ||
| 1011 | * combinatorial propagation. | ||
| 1012 | * \param[in] bndl a bundle | ||
| 1013 | * \param[in] halfedges the sorted list of the halfedges | ||
| 1014 | * in the bundle | ||
| 1015 | */ | ||
| 1016 | 18016 | void set_sorted_halfedges( | |
| 1017 | index_t bndl, const vector<index_t>& halfedges | ||
| 1018 | ) { | ||
| 1019 |
1/6✗ Branch 2 not taken.
✓ Branch 3 taken 18016 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
|
18016 | geo_debug_assert(halfedges.size() == nb_halfedges(bndl)); |
| 1020 |
2/2✓ Branch 1 taken 67980 times.
✓ Branch 2 taken 18016 times.
|
85996 | for(index_t i=0; i<halfedges.size(); ++i) { |
| 1021 | 67980 | set_halfedge(bndl, i, halfedges[i]); | |
| 1022 | } | ||
| 1023 | 18016 | bndl_is_sorted_[bndl] = true; | |
| 1024 | 18016 | } | |
| 1025 | |||
| 1026 | /** | ||
| 1027 | * \brief Indicates where to find a chart in a bundle | ||
| 1028 | * \details the first index is a chart index, and the second index | ||
| 1029 | * indicates which halfedge in a bundle is incident to that chart. | ||
| 1030 | */ | ||
| 1031 | typedef std::pair<index_t, index_t> ChartPos; | ||
| 1032 | |||
| 1033 | /** | ||
| 1034 | * \brief Gets the sorted list of charts around bundle | ||
| 1035 | * \param[in] bndl a bundle | ||
| 1036 | * \param[out] chart_pos a list of (chart id, halfedge index) | ||
| 1037 | * couples, sorted by chart id, and where the halfedge index | ||
| 1038 | * is the original index in the bundle before sorting | ||
| 1039 | */ | ||
| 1040 | void get_sorted_incident_charts( | ||
| 1041 | index_t bndl, vector<ChartPos>& chart_pos | ||
| 1042 | ); | ||
| 1043 | |||
| 1044 | 21836 | bool is_sorted(index_t bndl) const { | |
| 1045 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 21836 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
21836 | geo_debug_assert(bndl < nb()); |
| 1046 | 21836 | return bndl_is_sorted_[bndl]; | |
| 1047 | } | ||
| 1048 | |||
| 1049 | // private: | ||
| 1050 | MeshSurfaceIntersection& I_; | ||
| 1051 | Mesh& mesh_; | ||
| 1052 | Attribute<index_t> facet_chart_; | ||
| 1053 | vector<index_t> H_; | ||
| 1054 | vector<index_t> bndl_start_; | ||
| 1055 | vector<index_t> v_first_bndl_; | ||
| 1056 | vector<index_t> bndl_next_around_v_; | ||
| 1057 | vector<char> bndl_is_sorted_; // not vector<bool>, multithread! (#308) | ||
| 1058 | } radial_bundles_; | ||
| 1059 | |||
| 1060 | /***************************************************/ | ||
| 1061 | |||
| 1062 | class RadialPolylines { | ||
| 1063 | public: | ||
| 1064 | /** | ||
| 1065 | * \brief RadialPolylines constructor | ||
| 1066 | * \param[in] I a reference to the MeshSurfaceIntersection | ||
| 1067 | */ | ||
| 1068 | 61 | RadialPolylines(MeshSurfaceIntersection& I) : I_(I), mesh_(I.mesh_) { | |
| 1069 | 61 | } | |
| 1070 | |||
| 1071 | /** | ||
| 1072 | * \brief Initializes the structure | ||
| 1073 | * \details Needs to be called before any other function | ||
| 1074 | */ | ||
| 1075 | void initialize(); | ||
| 1076 | |||
| 1077 | /** | ||
| 1078 | * \brief Sorts all the bundles of all polylines | ||
| 1079 | * \details The "chart" facet attribute needs to be initialized with | ||
| 1080 | * all surface connected components before calling this function. | ||
| 1081 | */ | ||
| 1082 | void radial_sort(); | ||
| 1083 | |||
| 1084 | /** | ||
| 1085 | * \brief Gets the number of polylines | ||
| 1086 | */ | ||
| 1087 | 11662 | index_t nb() const { | |
| 1088 | 11662 | return polyline_start_.size() - 1; | |
| 1089 | } | ||
| 1090 | |||
| 1091 | /** | ||
| 1092 | * \brief used by range-based for | ||
| 1093 | * \return a non-iterator corresponding to the first polyline | ||
| 1094 | */ | ||
| 1095 | 58 | index_as_iterator begin() const { | |
| 1096 | 58 | return index_as_iterator(0); | |
| 1097 | } | ||
| 1098 | |||
| 1099 | /** | ||
| 1100 | * \brief used by range-based for | ||
| 1101 | * \return a non-iterator to one position past the last polyline | ||
| 1102 | */ | ||
| 1103 | 58 | index_as_iterator end() const { | |
| 1104 |
1/2✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
|
58 | return index_as_iterator(nb()); |
| 1105 | } | ||
| 1106 | |||
| 1107 | /** | ||
| 1108 | * \brief gets the bundles in a polyline | ||
| 1109 | * \param[in] polyline index of the polyline | ||
| 1110 | * \return a non-modifiable sequence of bundle indices | ||
| 1111 | */ | ||
| 1112 | 11460 | const_index_ptr_range bundles(index_t polyline) const { | |
| 1113 |
1/6✗ Branch 1 not taken.
✓ Branch 2 taken 11460 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
11460 | geo_debug_assert(polyline < nb()); |
| 1114 | return const_index_ptr_range( | ||
| 1115 | 11460 | B_, polyline_start_[polyline], polyline_start_[polyline+1] | |
| 1116 | 11460 | ); | |
| 1117 | } | ||
| 1118 | |||
| 1119 | ✗ | index_t nb_bundles(index_t polyline) const { | |
| 1120 | ✗ | geo_debug_assert(polyline < nb()); | |
| 1121 | ✗ | return polyline_start_[polyline+1] - polyline_start_[polyline]; | |
| 1122 | } | ||
| 1123 | |||
| 1124 | index_t bundle(index_t polyline, index_t li) const { | ||
| 1125 | geo_debug_assert(polyline < nb()); | ||
| 1126 | geo_debug_assert(li < nb_bundles(polyline)); | ||
| 1127 | return B_[polyline_start_[polyline] + li]; | ||
| 1128 | } | ||
| 1129 | |||
| 1130 | /** | ||
| 1131 | * \brief Copies the set of polylines to a mesh | ||
| 1132 | * \details Used for visualization purposes | ||
| 1133 | * \param[out] to a mesh that will contain all the polygonal lines | ||
| 1134 | * \param[in] trim_fins if set, do not keep bundles that have | ||
| 1135 | * less than three halfedges. | ||
| 1136 | */ | ||
| 1137 | void get_skeleton(Mesh& to, bool trim_fins=false); | ||
| 1138 | |||
| 1139 | private: | ||
| 1140 | MeshSurfaceIntersection& I_; | ||
| 1141 | Mesh& mesh_; | ||
| 1142 | vector<index_t> B_; | ||
| 1143 | vector<index_t> polyline_start_; | ||
| 1144 | } radial_polylines_; | ||
| 1145 | }; | ||
| 1146 | |||
| 1147 | /********************************************************************/ | ||
| 1148 | |||
| 1149 | enum MeshBooleanOperationFlags { | ||
| 1150 | MESH_BOOL_OPS_DEFAULT = 0, | ||
| 1151 | MESH_BOOL_OPS_VERBOSE = 1, | ||
| 1152 | MESH_BOOL_OPS_ATTRIBS = 2, | ||
| 1153 | MESH_BOOL_OPS_NO_SIMPLIFY = 4, | ||
| 1154 | MESH_BOOL_OPS_NO_CHECK_NEIGHBORS = 8 | ||
| 1155 | }; | ||
| 1156 | |||
| 1157 | /** | ||
| 1158 | * \brief Computes a boolean operation with two surface meshes. | ||
| 1159 | * \details A and B need to be two closed surface | ||
| 1160 | * mesh without intersections. | ||
| 1161 | * \param[in] A , B the two operands. | ||
| 1162 | * \param[out] result the computed mesh. | ||
| 1163 | * \param[in] operation one of "A+B", "A*B", "A-B", "B-A" | ||
| 1164 | * \param[in] flags MESH_BOOL_OPS_DEFAULT or an '|'-combination of: | ||
| 1165 | * - MESH_BOOL_OPS_VERBOSE: displays additional information | ||
| 1166 | * - MESH_BOOL_OPS_ATTRIBS: interpolates attributes | ||
| 1167 | * (implies MESH_BOOL_OPS_NO_SIMPLIFY) | ||
| 1168 | * - MESH_BOOL_OPS_NO_SIMPLIFY: do not simplify coplanar facets | ||
| 1169 | * - MESH_BOOL_OPS_NO_CHECK_NEIGHBORS: do not check intersections between | ||
| 1170 | * triangles that share an edge or a vertex | ||
| 1171 | */ | ||
| 1172 | void GEOGRAM_API mesh_boolean_operation( | ||
| 1173 | Mesh& result, const Mesh& A, const Mesh& B, const std::string& operation, | ||
| 1174 | MeshBooleanOperationFlags flags = MESH_BOOL_OPS_DEFAULT | ||
| 1175 | ); | ||
| 1176 | |||
| 1177 | /** | ||
| 1178 | * \brief Computes a boolean operation with two surface meshes. | ||
| 1179 | * \details A and B need to be two closed surface | ||
| 1180 | * mesh without intersections. | ||
| 1181 | * \param[in] A , B the two operands. | ||
| 1182 | * \param[out] result the computed mesh. | ||
| 1183 | * \param[in] operation one of "A+B", "A*B", "A-B", "B-A" | ||
| 1184 | * \param[in] verbose if set, display additional information | ||
| 1185 | * during computation | ||
| 1186 | */ | ||
| 1187 | ✗ | inline void mesh_boolean_operation( | |
| 1188 | Mesh& result, const Mesh& A, const Mesh& B, const std::string& operation, | ||
| 1189 | bool verbose | ||
| 1190 | ) { | ||
| 1191 | ✗ | mesh_boolean_operation( | |
| 1192 | result, A, B, operation, | ||
| 1193 | verbose ? MESH_BOOL_OPS_VERBOSE : MESH_BOOL_OPS_DEFAULT | ||
| 1194 | ); | ||
| 1195 | ✗ | } | |
| 1196 | |||
| 1197 | /** | ||
| 1198 | * \brief Computes the union of two surface meshes. | ||
| 1199 | * \details A and B need to be two closed surface | ||
| 1200 | * mesh without intersections. | ||
| 1201 | * \param[in] A , B the two operands. | ||
| 1202 | * \param[out] result the computed mesh. | ||
| 1203 | * \param[in] flags MESH_BOOL_OPS_DEFAULT or an '|'-combination of: | ||
| 1204 | * - MESH_BOOL_OPS_VERBOSE: displays additional information | ||
| 1205 | * - MESH_BOOL_OPS_ATTRIBS: interpolates attributes | ||
| 1206 | * (implies MESH_BOOL_OPS_NO_SIMPLIFY) | ||
| 1207 | * - MESH_BOOL_OPS_NO_SIMPLIFY: do not simplify coplanar facets | ||
| 1208 | * - MESH_BOOL_OPS_NO_CHECK_NEIGHBORS: do not check intersections between | ||
| 1209 | * triangles that share an edge or a vertex | ||
| 1210 | */ | ||
| 1211 | ✗ | inline void mesh_union( | |
| 1212 | Mesh& result, const Mesh& A, const Mesh& B, | ||
| 1213 | MeshBooleanOperationFlags flags=MESH_BOOL_OPS_DEFAULT | ||
| 1214 | ) { | ||
| 1215 | ✗ | mesh_boolean_operation(result, A, B, "A+B", flags); | |
| 1216 | ✗ | } | |
| 1217 | |||
| 1218 | /** | ||
| 1219 | * \brief Computes the union of two surface meshes. | ||
| 1220 | * \details A and B need to be two closed surface | ||
| 1221 | * mesh without intersections. | ||
| 1222 | * \param[in] A , B the two operands. | ||
| 1223 | * \param[out] result the computed mesh. | ||
| 1224 | * \param[in] verbose if set, display additional | ||
| 1225 | * information during computation | ||
| 1226 | */ | ||
| 1227 | inline void mesh_union( | ||
| 1228 | Mesh& result, const Mesh& A, const Mesh& B, bool verbose | ||
| 1229 | ) { | ||
| 1230 | mesh_boolean_operation(result, A, B, "A+B", verbose); | ||
| 1231 | } | ||
| 1232 | |||
| 1233 | |||
| 1234 | /** | ||
| 1235 | * \brief Computes the intersection of two surface meshes. | ||
| 1236 | * \details A and B need to be two closed surface | ||
| 1237 | * mesh without intersections. | ||
| 1238 | * \param[in] A , B the two operands. | ||
| 1239 | * \param[out] result the computed mesh. | ||
| 1240 | * \param[in] flags MESH_BOOL_OPS_DEFAULT or an '|'-combination of: | ||
| 1241 | * - MESH_BOOL_OPS_VERBOSE: displays additional information | ||
| 1242 | * - MESH_BOOL_OPS_ATTRIBS: interpolates attributes | ||
| 1243 | * (implies MESH_BOOL_OPS_NO_SIMPLIFY) | ||
| 1244 | * - MESH_BOOL_OPS_NO_SIMPLIFY: do not simplify coplanar facets | ||
| 1245 | * - MESH_BOOL_OPS_NO_CHECK_NEIGHBORS: do not check intersections between | ||
| 1246 | * triangles that share an edge or a vertex | ||
| 1247 | */ | ||
| 1248 | ✗ | inline void mesh_intersection( | |
| 1249 | Mesh& result, const Mesh& A, const Mesh& B, | ||
| 1250 | MeshBooleanOperationFlags flags=MESH_BOOL_OPS_DEFAULT | ||
| 1251 | ) { | ||
| 1252 | ✗ | mesh_boolean_operation(result, A, B, "A*B", flags); | |
| 1253 | ✗ | } | |
| 1254 | |||
| 1255 | /** | ||
| 1256 | * \brief Computes the intersection of two surface meshes. | ||
| 1257 | * \details A and B need to be two closed surface | ||
| 1258 | * mesh without intersections. | ||
| 1259 | * \param[in] A , B the two operands. | ||
| 1260 | * \param[out] result the computed mesh. | ||
| 1261 | * \param[in] verbose if set, display additional information | ||
| 1262 | * during computation | ||
| 1263 | */ | ||
| 1264 | inline void mesh_intersection( | ||
| 1265 | Mesh& result, const Mesh& A, const Mesh& B, bool verbose | ||
| 1266 | ) { | ||
| 1267 | mesh_boolean_operation(result, A, B, "A*B", verbose); | ||
| 1268 | } | ||
| 1269 | |||
| 1270 | /** | ||
| 1271 | * \brief Computes the difference of two surface meshes. | ||
| 1272 | * \details A and B need to be two closed surface | ||
| 1273 | * mesh without intersections. | ||
| 1274 | * \param[in] A , B the two operands. | ||
| 1275 | * \param[out] result the computed mesh. | ||
| 1276 | * \param[in] flags MESH_BOOL_OPS_DEFAULT or an '|'-combination of: | ||
| 1277 | * - MESH_BOOL_OPS_VERBOSE: displays additional information | ||
| 1278 | * - MESH_BOOL_OPS_ATTRIBS: interpolates attributes | ||
| 1279 | * (implies MESH_BOOL_OPS_NO_SIMPLIFY) | ||
| 1280 | * - MESH_BOOL_OPS_NO_SIMPLIFY: do not simplify coplanar facets | ||
| 1281 | * - MESH_BOOL_OPS_NO_CHECK_NEIGHBORS: do not check intersections between | ||
| 1282 | * triangles that share an edge or a vertex | ||
| 1283 | */ | ||
| 1284 | ✗ | inline void mesh_difference( | |
| 1285 | Mesh& result, const Mesh& A, const Mesh& B, | ||
| 1286 | MeshBooleanOperationFlags flags=MESH_BOOL_OPS_DEFAULT | ||
| 1287 | ) { | ||
| 1288 | ✗ | mesh_boolean_operation(result, A, B, "A-B", flags); | |
| 1289 | ✗ | } | |
| 1290 | |||
| 1291 | /** | ||
| 1292 | * \brief Computes the difference of two surface meshes. | ||
| 1293 | * \details A and B need to be two closed surface | ||
| 1294 | * mesh without intersections. | ||
| 1295 | * \param[in] A , B the two operands. | ||
| 1296 | * \param[out] result the computed mesh. | ||
| 1297 | * \param[in] verbose if set, display additional information | ||
| 1298 | * during computation | ||
| 1299 | */ | ||
| 1300 | inline void mesh_difference( | ||
| 1301 | Mesh& result, const Mesh& A, const Mesh& B, bool verbose | ||
| 1302 | ) { | ||
| 1303 | mesh_boolean_operation(result, A, B, "A-B", verbose); | ||
| 1304 | } | ||
| 1305 | |||
| 1306 | /** | ||
| 1307 | * \brief Attempts to make a surface mesh conformal by | ||
| 1308 | * removing intersecting facets and re-triangulating the holes. | ||
| 1309 | * \param[in] verbose if set, display additional information | ||
| 1310 | * during computation | ||
| 1311 | */ | ||
| 1312 | void GEOGRAM_API mesh_remove_intersections( | ||
| 1313 | Mesh& M, index_t max_iter = 3, bool verbose=false | ||
| 1314 | ); | ||
| 1315 | |||
| 1316 | /** | ||
| 1317 | * \brief Tests whether two mesh facets have a non-degenerate intersection. | ||
| 1318 | * \details If the facets are polygonal, they are triangulated from the | ||
| 1319 | * first vertex, and intersections between each pair of triangles is | ||
| 1320 | * tested. | ||
| 1321 | * \retval true if the two facets have an intersection. If they share a | ||
| 1322 | * vertex, it does not count as an intersection. | ||
| 1323 | * \retval false otherwise. | ||
| 1324 | */ | ||
| 1325 | bool GEOGRAM_API mesh_facets_have_intersection( | ||
| 1326 | Mesh& M, index_t f1, index_t f2 | ||
| 1327 | ); | ||
| 1328 | |||
| 1329 | /**************************************************************************/ | ||
| 1330 | } | ||
| 1331 | |||
| 1332 | #endif | ||
| 1333 |