| 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_VORONOI_GENERIC_RVD_CELL | ||
| 41 | #define GEOGRAM_VORONOI_GENERIC_RVD_CELL | ||
| 42 | |||
| 43 | #include <geogram/basic/common.h> | ||
| 44 | #include <geogram/voronoi/generic_RVD_vertex.h> | ||
| 45 | #include <geogram/basic/argused.h> | ||
| 46 | #include <geogram/basic/attributes.h> | ||
| 47 | #include <iosfwd> | ||
| 48 | #include <stack> | ||
| 49 | |||
| 50 | /** | ||
| 51 | * \file geogram/voronoi/generic_RVD_cell.h | ||
| 52 | * \brief Internal representation of polyhedra for GEO::GenericVoronoiDiagram. | ||
| 53 | * \note This file contains functions and classes used by the | ||
| 54 | * internal implementation of GEO::GenericVoronoiDiagram. | ||
| 55 | * They are not meant to be used directly by client code. | ||
| 56 | * Users who whant similar functionalities may use GEO::ConvexCell instead. | ||
| 57 | */ | ||
| 58 | |||
| 59 | namespace GEOGen { | ||
| 60 | |||
| 61 | using GEO::Mesh; | ||
| 62 | |||
| 63 | /** | ||
| 64 | * \brief Computes the intersection between a set of halfspaces. | ||
| 65 | * \note This is an internal implementation class used by | ||
| 66 | * GEO::RestrictedVoronoiDiagram. It is not meant to be | ||
| 67 | * used directly by client code. | ||
| 68 | */ | ||
| 69 | class GEOGRAM_API ConvexCell { | ||
| 70 | |||
| 71 | /** \brief This class type */ | ||
| 72 | typedef ConvexCell thisclass; | ||
| 73 | |||
| 74 | public: | ||
| 75 | |||
| 76 | static constexpr index_t NO_TRIANGLE = index_t(-1); | ||
| 77 | static constexpr index_t NO_VERTEX = index_t(-1); | ||
| 78 | static constexpr index_t END_OF_LIST = index_t(-1); | ||
| 79 | |||
| 80 | /** | ||
| 81 | * \brief Represents the current state of a triangle. | ||
| 82 | */ | ||
| 83 | enum TriangleStatus { | ||
| 84 | TRI_IS_FREE = 0, | ||
| 85 | TRI_IS_CONFLICT = 1, | ||
| 86 | TRI_IS_USED = 2 | ||
| 87 | }; | ||
| 88 | |||
| 89 | /** | ||
| 90 | * \brief Represents a vertex of this ConvexCell in dual form. | ||
| 91 | * \details Each vertex of a ConvexCell is represented | ||
| 92 | * combinatorially as a Triangle, in dual form | ||
| 93 | * (in primal parlance, each vertex is | ||
| 94 | * of degree 3, and can be represented by a triangle). | ||
| 95 | * A Triangle knows its tree vertices, its tree adjacent triangles | ||
| 96 | * and the geometric point it corresponds to. | ||
| 97 | */ | ||
| 98 | |||
| 99 | struct Triangle { | ||
| 100 | |||
| 101 | /** | ||
| 102 | * \brief Creates a new triangle. | ||
| 103 | * \param[in] v0 index of the first vertex | ||
| 104 | * \param[in] v1 index of the second vertex | ||
| 105 | * \param[in] v2 index of the third vertex | ||
| 106 | * \param[in] f0 index of the triangle opposite to \p v0 | ||
| 107 | * \param[in] f1 index of the triangle opposite to \p v1 | ||
| 108 | * \param[in] f2 index of the triangle opposite to \p v2 | ||
| 109 | */ | ||
| 110 | Triangle( | ||
| 111 | index_t v0, index_t v1, index_t v2, | ||
| 112 | index_t f0, index_t f1, index_t f2 | ||
| 113 | ) : | ||
| 114 | next_(END_OF_LIST), | ||
| 115 | status_(TRI_IS_FREE), | ||
| 116 | id_(-1) { | ||
| 117 | v[0] = v0; | ||
| 118 | v[1] = v1; | ||
| 119 | v[2] = v2; | ||
| 120 | t[0] = f0; | ||
| 121 | t[1] = f1; | ||
| 122 | t[2] = f2; | ||
| 123 | } | ||
| 124 | |||
| 125 | /** | ||
| 126 | * \brief Creates a new uninitialized Triangle. | ||
| 127 | */ | ||
| 128 | ✗ | Triangle() : | |
| 129 | 10199191 | next_(END_OF_LIST), | |
| 130 | 10199191 | status_(TRI_IS_FREE), | |
| 131 | 10199191 | id_(-1) { | |
| 132 | 10199191 | v[0] = NO_VERTEX; | |
| 133 | 10199191 | v[1] = NO_VERTEX; | |
| 134 | 10199191 | v[2] = NO_VERTEX; | |
| 135 | 10199191 | t[0] = NO_TRIANGLE; | |
| 136 | 10199191 | t[1] = NO_TRIANGLE; | |
| 137 | 10199191 | t[2] = NO_TRIANGLE; | |
| 138 | } | ||
| 139 | |||
| 140 | GEOGen::Vertex dual_; | ||
| 141 | index_t v[3]; // The 3 vertices of this triangle | ||
| 142 | index_t t[3]; // The 3 triangles adjacent to this triangle | ||
| 143 | index_t next_; // Linked list management. | ||
| 144 | TriangleStatus status_; | ||
| 145 | // TRI_IS_FREE,TRI_IS_USED or TRI_IS_CONFLICT. | ||
| 146 | signed_index_t id_; | ||
| 147 | }; | ||
| 148 | |||
| 149 | /** | ||
| 150 | * \brief Represents a facet of this ConvexCell in dual form. | ||
| 151 | * \details Each facet of a ConvexCell is represented | ||
| 152 | * combinatorially as a Vertex (dual form). | ||
| 153 | * Each vertex v knows an incident triangle (v.t). | ||
| 154 | */ | ||
| 155 | class Vertex { | ||
| 156 | public: | ||
| 157 | /** | ||
| 158 | * \brief Creates a new uninitialized Vertex. | ||
| 159 | */ | ||
| 160 | 13284011 | Vertex() : | |
| 161 | 13284011 | t(-1), | |
| 162 | ✗ | id_(-1) { | |
| 163 | } | ||
| 164 | |||
| 165 | signed_index_t t; // One triangle incident to this vertex | ||
| 166 | signed_index_t id_; | ||
| 167 | }; | ||
| 168 | |||
| 169 | /** | ||
| 170 | * \brief ConvexCell constructor. | ||
| 171 | * \param[in] dim dimension of the ConvexCell, e.g. 3 for 3d | ||
| 172 | */ | ||
| 173 |
9/266✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✓ Branch 103 taken 160 times.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✓ Branch 112 taken 1 times.
✗ Branch 113 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✓ Branch 157 taken 160 times.
✗ Branch 158 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✓ Branch 166 taken 1 times.
✗ Branch 167 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✓ Branch 211 taken 160 times.
✗ Branch 212 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✓ Branch 220 taken 1 times.
✗ Branch 221 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✓ Branch 265 taken 160 times.
✗ Branch 266 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
✗ Branch 379 not taken.
✗ Branch 380 not taken.
✗ Branch 382 not taken.
✗ Branch 383 not taken.
✗ Branch 385 not taken.
✗ Branch 386 not taken.
✗ Branch 388 not taken.
✗ Branch 389 not taken.
✗ Branch 391 not taken.
✗ Branch 392 not taken.
✗ Branch 394 not taken.
✗ Branch 395 not taken.
✗ Branch 397 not taken.
✗ Branch 398 not taken.
|
662 | ConvexCell(coord_index_t dim) : |
| 174 | 662 | first_free_(END_OF_LIST), | |
| 175 |
9/266✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✓ Branch 103 taken 160 times.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✓ Branch 112 taken 1 times.
✗ Branch 113 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✓ Branch 157 taken 160 times.
✗ Branch 158 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✓ Branch 166 taken 1 times.
✗ Branch 167 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✓ Branch 211 taken 160 times.
✗ Branch 212 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✓ Branch 220 taken 1 times.
✗ Branch 221 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✓ Branch 265 taken 160 times.
✗ Branch 266 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
✗ Branch 379 not taken.
✗ Branch 380 not taken.
✗ Branch 382 not taken.
✗ Branch 383 not taken.
✗ Branch 385 not taken.
✗ Branch 386 not taken.
✗ Branch 388 not taken.
✗ Branch 389 not taken.
✗ Branch 391 not taken.
✗ Branch 392 not taken.
✗ Branch 394 not taken.
✗ Branch 395 not taken.
✗ Branch 397 not taken.
✗ Branch 398 not taken.
|
662 | v_to_t_dirty_(false), |
| 176 | intersections_(dim), | ||
| 177 | 662 | symbolic_is_surface_(false), | |
| 178 |
9/266✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✓ Branch 58 taken 1 times.
✗ Branch 59 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✓ Branch 103 taken 160 times.
✗ Branch 104 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✓ Branch 112 taken 1 times.
✗ Branch 113 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 136 not taken.
✗ Branch 137 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✓ Branch 157 taken 160 times.
✗ Branch 158 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✓ Branch 166 taken 1 times.
✗ Branch 167 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✓ Branch 211 taken 160 times.
✗ Branch 212 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✓ Branch 220 taken 1 times.
✗ Branch 221 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✓ Branch 265 taken 160 times.
✗ Branch 266 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
✗ Branch 379 not taken.
✗ Branch 380 not taken.
✗ Branch 382 not taken.
✗ Branch 383 not taken.
✗ Branch 385 not taken.
✗ Branch 386 not taken.
✗ Branch 388 not taken.
✗ Branch 389 not taken.
✗ Branch 391 not taken.
✗ Branch 392 not taken.
✗ Branch 394 not taken.
✗ Branch 395 not taken.
✗ Branch 397 not taken.
✗ Branch 398 not taken.
|
662 | cell_id_(-1) { |
| 179 | } | ||
| 180 | |||
| 181 | /** | ||
| 182 | * \brief Copies a ConvexCell. | ||
| 183 | * \details The allocated vertices are shared with \p rhs, thus | ||
| 184 | * \p rhs should not be deleted before this ConvexCell. | ||
| 185 | * \param[in] rhs a const reference to the ConvexCell to be | ||
| 186 | * copied. | ||
| 187 | */ | ||
| 188 | void copy(const ConvexCell& rhs); | ||
| 189 | |||
| 190 | /** | ||
| 191 | * \brief Gets the dimension of this ConvexCell. | ||
| 192 | * \return the dimension of this ConvexCell, e.g. 3 for 3d | ||
| 193 | */ | ||
| 194 | coord_index_t dimension() const { | ||
| 195 | return intersections_.dimension(); | ||
| 196 | } | ||
| 197 | |||
| 198 | /** | ||
| 199 | * \brief Clears this ConvexCell. | ||
| 200 | */ | ||
| 201 | 811245 | void clear() { | |
| 202 | 811245 | first_free_ = END_OF_LIST; | |
| 203 | 811245 | triangles_.resize(0); | |
| 204 | 811245 | vertices_.resize(0); | |
| 205 | 811245 | v_to_t_dirty_ = false; | |
| 206 | intersections_.clear(); | ||
| 207 | 811245 | } | |
| 208 | |||
| 209 | /** | ||
| 210 | * \brief Specifies that symbolic information is | ||
| 211 | * relative to surfacic mesh (rather than volumetric mesh). | ||
| 212 | * \details Affects the behavior of side_exact(). | ||
| 213 | * \param[in] x true if symbolic information is relative | ||
| 214 | * to surfacic mesh (triangles), false if symbolic information | ||
| 215 | * is relative to volumetric mesh (tetrahedra). | ||
| 216 | */ | ||
| 217 | void set_symbolic_is_surface(bool x) { | ||
| 218 | 18 | symbolic_is_surface_ = x; | |
| 219 | 18 | } | |
| 220 | |||
| 221 | /** | ||
| 222 | * \brief Assigns a mesh tetrahedron to this ConvexCell | ||
| 223 | * \details The tetrahedron from the initial mesh is converted into | ||
| 224 | * the internal geometric/symbolic representation. | ||
| 225 | * \param[in] mesh the mesh from which the tetrahedron is copied | ||
| 226 | * \param[in] t the index of the tetrahedron in \p mesh | ||
| 227 | * \param[in] symbolic if true, symbolic information is copied | ||
| 228 | * \param[in] vertex_weight if bound, an attribute that gives | ||
| 229 | * the weight of each vertex in \p mesh. | ||
| 230 | */ | ||
| 231 | void initialize_from_mesh_tetrahedron( | ||
| 232 | const Mesh* mesh, index_t t, bool symbolic, | ||
| 233 | const GEO::Attribute<double>& vertex_weight | ||
| 234 | ); | ||
| 235 | |||
| 236 | |||
| 237 | /** | ||
| 238 | * \brief Copies a Mesh into a ConvexCell | ||
| 239 | * \details The surface mesh in \p mesh represents the boundary | ||
| 240 | * of the ConvexCell. | ||
| 241 | * \param[in] mesh a pointer to the input Mesh | ||
| 242 | * \param[in] symbolic if true, symbolic information is copied | ||
| 243 | */ | ||
| 244 | void initialize_from_surface_mesh( | ||
| 245 | Mesh* mesh, bool symbolic | ||
| 246 | ); | ||
| 247 | |||
| 248 | |||
| 249 | /** | ||
| 250 | * \brief Copies a ConvexCell into a Mesh | ||
| 251 | * \details On exit, the output mesh is a surfacic | ||
| 252 | * mesh with the boundary of the convex cell. | ||
| 253 | * \param[out] mesh a pointer to the target mesh | ||
| 254 | * \param[in] copy_symbolic_info if true, symbolic | ||
| 255 | * information is copied. An attribute "id" is attached | ||
| 256 | * to the facets. The value of id[f] is either 1 + the index of | ||
| 257 | * the Voronoi vertex that generated with \p i the bisector that | ||
| 258 | * created the facet, or -1-g if the facet was an original facet | ||
| 259 | * of mesh \p mesh, where g is the index of the original | ||
| 260 | * facet in \p mesh. | ||
| 261 | */ | ||
| 262 | void convert_to_mesh(Mesh* mesh, bool copy_symbolic_info = false); | ||
| 263 | |||
| 264 | /** | ||
| 265 | * \brief Clips this ConvexCell with a plane. | ||
| 266 | * \details The plane is specified as a bisector | ||
| 267 | * in a Delaunay triangulation. | ||
| 268 | * \param[in] mesh input mesh, used by exact predicates | ||
| 269 | * \param[in] delaunay the Delaunay triangulation | ||
| 270 | * \param[in] i index of the first extremity of the bisector | ||
| 271 | * \param[in] j index of the second extremity of the bisector | ||
| 272 | * \param[in] exact if true, uses exact predicates (implies symbolic) | ||
| 273 | * \param[in] symbolic if true, computes symbolic information | ||
| 274 | * \return the index of the newly created vertex that corresponds to | ||
| 275 | * the dual of the new face or -1 if the input cell was completely | ||
| 276 | * on the negative side (removed everything) | ||
| 277 | * \tparam DIM dimension (specified as a template parameter for | ||
| 278 | * efficiency reasons). | ||
| 279 | * \pre DIM == dimension() | ||
| 280 | */ | ||
| 281 | template <index_t DIM> | ||
| 282 | 20065754 | signed_index_t clip_by_plane( | |
| 283 | const Mesh* mesh, const Delaunay* delaunay, | ||
| 284 | index_t i, index_t j, | ||
| 285 | bool exact, bool symbolic | ||
| 286 | ) { | ||
| 287 | index_t new_v = create_vertex(); | ||
| 288 | 20065754 | set_vertex_id(index_t(new_v), signed_index_t(j)+1); | |
| 289 | index_t conflict_begin, conflict_end; | ||
| 290 | |||
| 291 | // Phase I: Determine the conflict zone and chain the triangles | ||
| 292 | // Note: they are not immediately deleted, since we need the | ||
| 293 | // geometric information in the triangles to compute the new | ||
| 294 | // intersections. | ||
| 295 | 20065754 | get_conflict_list<DIM>( | |
| 296 | mesh, delaunay, i, j, exact, conflict_begin, conflict_end | ||
| 297 | ); | ||
| 298 | |||
| 299 | // Special case: the clipping plane did not clip anything. | ||
| 300 |
2/2✓ Branch 0 taken 6015608 times.
✓ Branch 1 taken 4030595 times.
|
20065754 | if(conflict_begin == END_OF_LIST) { |
| 301 | 12011215 | return signed_index_t(new_v); | |
| 302 | } | ||
| 303 | |||
| 304 | // Phase II: Find a triangle on the border of the conflict zone | ||
| 305 | // (by traversing the conflict list). | ||
| 306 | index_t first_conflict_t; | ||
| 307 | index_t first_conflict_e; | ||
| 308 | 8054539 | bool found_h = find_triangle_on_border( | |
| 309 | conflict_begin, conflict_end, | ||
| 310 | first_conflict_t, first_conflict_e | ||
| 311 | ); | ||
| 312 | |||
| 313 | // The clipping plane removed everything ! | ||
| 314 | // (note: cannot be empty conflict list, since this | ||
| 315 | // case was detected by previous test at the end of | ||
| 316 | // phase I) | ||
| 317 |
2/2✓ Branch 0 taken 1802 times.
✓ Branch 1 taken 4028793 times.
|
8054539 | if(!found_h) { |
| 318 | 3604 | clear(); | |
| 319 | 3604 | return -1; | |
| 320 | } | ||
| 321 | |||
| 322 | // Phase III: Triangulate hole. | ||
| 323 | 8050935 | triangulate_hole<DIM>( | |
| 324 | delaunay, i, j, symbolic, | ||
| 325 | first_conflict_t, first_conflict_e, | ||
| 326 | new_v | ||
| 327 | ); | ||
| 328 | |||
| 329 | // Phase IV: Merge the conflict zone into the free list. | ||
| 330 | merge_into_free_list(conflict_begin, conflict_end); | ||
| 331 | 8050935 | return signed_index_t(new_v); | |
| 332 | } | ||
| 333 | |||
| 334 | /** | ||
| 335 | * \brief Gets the maximum valid triangle index plus one. | ||
| 336 | * \details May be greater than nb_t() if this ConvexCell has | ||
| 337 | * some free (unused) triangles. | ||
| 338 | */ | ||
| 339 | index_t max_t() const { | ||
| 340 | return triangles_.size(); | ||
| 341 | } | ||
| 342 | |||
| 343 | /** | ||
| 344 | * \brief Gets the number of used triangles. | ||
| 345 | */ | ||
| 346 | index_t nb_t() const { | ||
| 347 | index_t result = 0; | ||
| 348 | for(index_t t = 0; t < max_t(); t++) { | ||
| 349 | if(triangle_is_used(t)) { | ||
| 350 | result++; | ||
| 351 | } | ||
| 352 | } | ||
| 353 | return result; | ||
| 354 | } | ||
| 355 | |||
| 356 | /** | ||
| 357 | * \brief Gets the maximum valid vertex index plus one. | ||
| 358 | */ | ||
| 359 | index_t max_v() const { | ||
| 360 | return vertices_.size(); | ||
| 361 | } | ||
| 362 | |||
| 363 | /** | ||
| 364 | * \brief Tests whether a given triangle is free. | ||
| 365 | */ | ||
| 366 | bool triangle_is_free(index_t t) const { | ||
| 367 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 368 | geo_debug_assert(t < max_t()); | ||
| 369 |
2/2✓ Branch 0 taken 13266 times.
✓ Branch 1 taken 111 times.
|
13377 | return triangles_[t].status_ == TRI_IS_FREE; |
| 370 | } | ||
| 371 | |||
| 372 | /** | ||
| 373 | * \brief Tests whether a given triangle is valid. | ||
| 374 | * \details A "valid" triangle is a triangle from which | ||
| 375 | * we can query information (vertices, adjacent triangles, | ||
| 376 | * embedding), therefore it is a "used" or "conflict" triangle. | ||
| 377 | * \param[in] t index of the triangle | ||
| 378 | * \pre t < max_t() | ||
| 379 | */ | ||
| 380 | bool triangle_is_valid(index_t t) const { | ||
| 381 | return !triangle_is_free(t); | ||
| 382 | } | ||
| 383 | |||
| 384 | /** | ||
| 385 | * \brief Tests whether a given triangle is used. | ||
| 386 | * \param[in] t index of the triangle | ||
| 387 | * \pre t < max_t() | ||
| 388 | */ | ||
| 389 | bool triangle_is_used(index_t t) const { | ||
| 390 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 391 | geo_debug_assert(t < max_t()); | ||
| 392 |
16/70✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✓ Branch 14 taken 141330 times.
✓ Branch 15 taken 67395 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✓ Branch 22 taken 176626 times.
✓ Branch 23 taken 89092 times.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✓ Branch 30 taken 227171 times.
✓ Branch 31 taken 118440 times.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✓ Branch 38 taken 242958 times.
✓ Branch 39 taken 126295 times.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✓ Branch 58 taken 5796881 times.
✓ Branch 59 taken 15152518 times.
✓ Branch 60 taken 7846942 times.
✓ Branch 61 taken 20039334 times.
✓ Branch 62 taken 9306098 times.
✓ Branch 63 taken 23548890 times.
✓ Branch 64 taken 9101100 times.
✓ Branch 65 taken 23520686 times.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
|
158233707 | return triangles_[t].status_ == TRI_IS_USED; |
| 393 | } | ||
| 394 | |||
| 395 | /** | ||
| 396 | * \brief Tests whether a given triangle belongs to | ||
| 397 | * the conflict zone. | ||
| 398 | * \param[in] t index of the triangle | ||
| 399 | * \pre t < max_t() | ||
| 400 | */ | ||
| 401 | bool triangle_is_conflict(index_t t) const { | ||
| 402 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 403 | geo_debug_assert(t < max_t()); | ||
| 404 | 56748116 | return triangles_[t].status_ == TRI_IS_CONFLICT; | |
| 405 | } | ||
| 406 | |||
| 407 | /** | ||
| 408 | * \brief Gets the index of a triangle vertex. | ||
| 409 | * \param[in] t the triangle index | ||
| 410 | * \param[in] iv local vertex index (0,1 or 2) in \p t | ||
| 411 | * \return the index of triangle's \p iv th vertex | ||
| 412 | * \pre t < max_t() | ||
| 413 | */ | ||
| 414 | index_t triangle_vertex(index_t t, index_t iv) const { | ||
| 415 | geo_debug_assert(iv < 3); | ||
| 416 | geo_debug_assert(triangle_is_valid(t)); | ||
| 417 | 64521722 | return triangles_[t].v[iv]; | |
| 418 | } | ||
| 419 | |||
| 420 | /** | ||
| 421 | * \brief Gets the index of a triangle adjacent to another one. | ||
| 422 | * \param[in] t the triangle index | ||
| 423 | * \param[in] e local edge index (0,1 or 2) in \p t | ||
| 424 | * \return the index of the triangle adjacent to \p t on edge \p e | ||
| 425 | */ | ||
| 426 | index_t triangle_adjacent(index_t t, index_t e) const { | ||
| 427 | geo_debug_assert(e < 3); | ||
| 428 | geo_debug_assert(triangle_is_valid(t)); | ||
| 429 | 4590309 | return triangles_[t].t[e]; | |
| 430 | } | ||
| 431 | |||
| 432 | /** | ||
| 433 | * \brief Sets a vertex of a triangle. | ||
| 434 | * \param[in] t the triangle index | ||
| 435 | * \param[in] iv local vertex index (0,1 or 2) in \p t | ||
| 436 | * \param[in] v global vertex index | ||
| 437 | */ | ||
| 438 | void set_triangle_vertex(index_t t, index_t iv, index_t v) { | ||
| 439 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 440 | geo_debug_assert(t < max_t()); | ||
| 441 | geo_debug_assert(iv < 3); | ||
| 442 | geo_debug_assert(v < max_v()); | ||
| 443 | triangles_[t].v[iv] = v; | ||
| 444 | } | ||
| 445 | |||
| 446 | /** | ||
| 447 | * \brief Sets a triangle adjacency. | ||
| 448 | * \param[in] t the triangle index | ||
| 449 | * \param[in] e local edge index (0,1 or 2) | ||
| 450 | * \param[in] t2 global triangle index | ||
| 451 | */ | ||
| 452 | void set_triangle_adjacent( | ||
| 453 | index_t t, index_t e, index_t t2 | ||
| 454 | ) { | ||
| 455 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 456 | geo_debug_assert(t < max_t()); | ||
| 457 | geo_debug_assert(e < 3); | ||
| 458 | geo_debug_assert(t2 < max_t()); | ||
| 459 |
10/14✓ Branch 0 taken 24060 times.
✓ Branch 1 taken 12288 times.
✓ Branch 2 taken 1774063 times.
✓ Branch 3 taken 935612 times.
✓ Branch 4 taken 2374376 times.
✓ Branch 5 taken 1110716 times.
✓ Branch 6 taken 2978834 times.
✓ Branch 7 taken 1237940 times.
✓ Branch 8 taken 3078200 times.
✓ Branch 9 taken 1238526 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
14764615 | triangles_[t].t[e] = t2; |
| 460 | 10735822 | } | |
| 461 | |||
| 462 | /** | ||
| 463 | * \brief Finds the local index of a triangle vertex | ||
| 464 | * \param[in] t the triangle | ||
| 465 | * \param[in] v global vertex index | ||
| 466 | * \return local vertex index (0,1 or 2) of \p v in \p t | ||
| 467 | * \pre \p t is incident to \p v | ||
| 468 | */ | ||
| 469 | index_t find_triangle_vertex(index_t t, index_t v) const { | ||
| 470 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 471 | geo_debug_assert(t < max_t()); | ||
| 472 | geo_debug_assert(v < max_v()); | ||
| 473 | |||
| 474 | // The following expression is 10% faster than using | ||
| 475 | // if() statements (multiply by boolean result of test). | ||
| 476 | // Thank to Laurent Alonso for this idea. | ||
| 477 | index_t result = index_t( | ||
| 478 |
20/114✓ Branch 0 taken 113327 times.
✓ Branch 1 taken 52341 times.
✓ Branch 2 taken 1645894 times.
✓ Branch 3 taken 825731 times.
✓ Branch 4 taken 1708237 times.
✓ Branch 5 taken 790445 times.
✓ Branch 6 taken 2128443 times.
✓ Branch 7 taken 871481 times.
✓ Branch 8 taken 2171828 times.
✓ Branch 9 taken 870978 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✓ Branch 40 taken 674526 times.
✓ Branch 41 taken 267273 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✓ Branch 54 taken 835270 times.
✓ Branch 55 taken 327055 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✓ Branch 68 taken 1051615 times.
✓ Branch 69 taken 401145 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✓ Branch 82 taken 1118319 times.
✓ Branch 83 taken 420518 times.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 111 not taken.
✓ Branch 112 taken 18462339 times.
✓ Branch 113 taken 9054430 times.
|
43791195 | (triangles_[t].v[1] == v) | ((triangles_[t].v[2] == v) * 2) |
| 479 | 43229679 | ); | |
| 480 | geo_debug_assert(triangles_[t].v[result] == v); | ||
| 481 | return result; | ||
| 482 | } | ||
| 483 | |||
| 484 | /** | ||
| 485 | * \brief Finds the edge along which two triangles are adjacent | ||
| 486 | * \param[in] t1 first triangle | ||
| 487 | * \param[in] t2 second triangle | ||
| 488 | * \return the local edge index (0,1 or 2) in \p t1 along which | ||
| 489 | * \p t2 is adjacent to \p t1 | ||
| 490 | * \pre \p t1 and \p t2 are adjacent | ||
| 491 | */ | ||
| 492 | index_t triangle_adjacent_index( | ||
| 493 | index_t t1, index_t t2 | ||
| 494 | ) const { | ||
| 495 | geo_debug_assert(t1 != NO_TRIANGLE); | ||
| 496 | geo_debug_assert(t1 < max_t()); | ||
| 497 | geo_debug_assert(t2 != NO_TRIANGLE); | ||
| 498 | geo_debug_assert(t2 < max_t()); | ||
| 499 | |||
| 500 | // The following expression is 10% faster than using | ||
| 501 | // if() statements (multiply by boolean result of test). | ||
| 502 | // Thank to Laurent Alonso for this idea. | ||
| 503 | index_t result = index_t( | ||
| 504 |
10/14✓ Branch 0 taken 24060 times.
✓ Branch 1 taken 12288 times.
✓ Branch 2 taken 1774063 times.
✓ Branch 3 taken 935612 times.
✓ Branch 4 taken 2374376 times.
✓ Branch 5 taken 1110716 times.
✓ Branch 6 taken 2978834 times.
✓ Branch 7 taken 1237940 times.
✓ Branch 8 taken 3078200 times.
✓ Branch 9 taken 1238526 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
14764615 | (triangles_[t1].t[1] == t2) | ((triangles_[t1].t[2] == t2) * 2) |
| 505 | 14764615 | ); | |
| 506 | |||
| 507 | geo_debug_assert(triangles_[t1].t[result] == t2); | ||
| 508 | |||
| 509 | return result; | ||
| 510 | } | ||
| 511 | |||
| 512 | /** | ||
| 513 | * \brief Gets one of the triangles incident to a vertex. | ||
| 514 | * \details The information is cached and reconstructed | ||
| 515 | * whenever the v_to_t_dirty_ flag is positioned. | ||
| 516 | * \param[in] v index of the vertex | ||
| 517 | * \return the index of a triangle incident to \p v | ||
| 518 | */ | ||
| 519 | signed_index_t vertex_triangle(index_t v) const { | ||
| 520 |
18/350✓ Branch 0 taken 19556 times.
✓ Branch 1 taken 316286 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✓ Branch 26 taken 141330 times.
✓ Branch 27 taken 2203502 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✓ Branch 40 taken 176626 times.
✓ Branch 41 taken 2869412 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✓ Branch 54 taken 227171 times.
✓ Branch 55 taken 3501461 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✓ Branch 68 taken 242958 times.
✓ Branch 69 taken 3561434 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 111 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✗ Branch 136 not taken.
✓ Branch 137 taken 55601 times.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✓ Branch 167 taken 2344832 times.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
✓ Branch 173 taken 71275 times.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✗ Branch 202 not taken.
✓ Branch 203 taken 3046038 times.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✗ Branch 208 not taken.
✓ Branch 209 taken 91389 times.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✗ Branch 238 not taken.
✓ Branch 239 taken 3728632 times.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✗ Branch 244 not taken.
✓ Branch 245 taken 90817 times.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 249 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✗ Branch 274 not taken.
✓ Branch 275 taken 3804392 times.
✗ Branch 276 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 279 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 306 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 333 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
|
26492712 | if(v_to_t_dirty_) { |
| 521 | 807641 | const_cast<ConvexCell*>(this)->init_v_to_t(); | |
| 522 | } | ||
| 523 | geo_debug_assert(v != NO_VERTEX); | ||
| 524 | geo_debug_assert(v < max_v()); | ||
| 525 |
26/350✓ Branch 0 taken 189722 times.
✓ Branch 1 taken 146120 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✓ Branch 26 taken 1403033 times.
✓ Branch 27 taken 941799 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✓ Branch 40 taken 1883713 times.
✓ Branch 41 taken 1162325 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✓ Branch 54 taken 2275872 times.
✓ Branch 55 taken 1452760 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✓ Branch 68 taken 2265555 times.
✓ Branch 69 taken 1538837 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 111 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✓ Branch 136 taken 32334 times.
✓ Branch 137 taken 23267 times.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✓ Branch 166 taken 1403033 times.
✓ Branch 167 taken 941799 times.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✓ Branch 172 taken 43173 times.
✓ Branch 173 taken 28102 times.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✓ Branch 202 taken 1883713 times.
✓ Branch 203 taken 1162325 times.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✓ Branch 208 taken 54903 times.
✓ Branch 209 taken 36486 times.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✓ Branch 238 taken 2275872 times.
✓ Branch 239 taken 1452760 times.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✓ Branch 244 taken 52643 times.
✓ Branch 245 taken 38174 times.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 249 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✓ Branch 274 taken 2265555 times.
✓ Branch 275 taken 1538837 times.
✗ Branch 276 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 279 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 306 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 333 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
|
26492712 | return vertices_[v].t; |
| 526 | } | ||
| 527 | |||
| 528 | /** | ||
| 529 | * \brief Stores in a vertex the index of one | ||
| 530 | * the triangles incident to it. | ||
| 531 | * \param[in] v index of the vertex | ||
| 532 | * \param[in] t index of one of the triangles incident to \p v | ||
| 533 | */ | ||
| 534 | void set_vertex_triangle(index_t v, index_t t) { | ||
| 535 | geo_debug_assert(v != NO_VERTEX); | ||
| 536 | geo_debug_assert(index_t(v) < max_v()); | ||
| 537 | 21678822 | vertices_[v].t = signed_index_t(t); | |
| 538 | } | ||
| 539 | |||
| 540 | /** | ||
| 541 | * \brief Gets the dual vertex that corresponds to a triangle. | ||
| 542 | * \details Each triangle corresponds to a vertex of the ConvexCell | ||
| 543 | * (combinatorics are stored in dual form). | ||
| 544 | * \param[in] t index of the triangle | ||
| 545 | * \return a const reference to the GEOGen::Vertex that corresponds | ||
| 546 | * to the triangle, with both geometrical and combinatorial | ||
| 547 | * representations | ||
| 548 | */ | ||
| 549 | const GEOGen::Vertex& triangle_dual(index_t t) const { | ||
| 550 | geo_debug_assert(triangle_is_valid(t)); | ||
| 551 |
0/56✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
|
788085 | return triangles_[t].dual_; |
| 552 | } | ||
| 553 | |||
| 554 | /** | ||
| 555 | * \brief Gets the dual vertex that corresponds to a triangle. | ||
| 556 | * \details Each triangle corresponds to a vertex of the ConvexCell | ||
| 557 | * (combinatorics are stored in dual form). | ||
| 558 | * \param[in] t index of the triangle | ||
| 559 | * \return a reference to the GEOGen::Vertex that corresponds | ||
| 560 | * to the triangle, with both geometrical and | ||
| 561 | * combinatorial representations | ||
| 562 | */ | ||
| 563 | GEOGen::Vertex& triangle_dual(index_t t) { | ||
| 564 | geo_debug_assert(triangle_is_valid(t)); | ||
| 565 | 77777534 | return triangles_[t].dual_; | |
| 566 | } | ||
| 567 | |||
| 568 | /** | ||
| 569 | * \brief Gets the id of this ConvexCell. | ||
| 570 | * \details The id can be used to maintain the | ||
| 571 | * correspondence with a tetrahedron in the Mesh. | ||
| 572 | * \return the id of this ConvexCell. Can be a | ||
| 573 | * negative number. | ||
| 574 | */ | ||
| 575 | signed_index_t cell_id() const { | ||
| 576 | 65551 | return cell_id_; | |
| 577 | } | ||
| 578 | |||
| 579 | /** | ||
| 580 | * \brief Sets the id of this ConvexCell. | ||
| 581 | * \details The id can be used to maintain the | ||
| 582 | * correspondence with a tetrahedron in the Mesh. | ||
| 583 | * \param[in] i the id of this ConvexCell. Can be | ||
| 584 | * a negative number. | ||
| 585 | */ | ||
| 586 | void set_cell_id(signed_index_t i) { | ||
| 587 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 809425 times.
|
809425 | cell_id_ = i; |
| 588 | } | ||
| 589 | |||
| 590 | /** | ||
| 591 | * \brief Gets the id of a triangle. | ||
| 592 | * \details Each triangle of a ConvexCell has an id, that can | ||
| 593 | * be used to maintain the correspondence with a vertex in the Mesh. | ||
| 594 | * \return The id of triangle \p t. | ||
| 595 | */ | ||
| 596 | signed_index_t triangle_id(index_t t) const { | ||
| 597 | geo_debug_assert(triangle_is_valid(t)); | ||
| 598 | return triangles_[t].id_; | ||
| 599 | } | ||
| 600 | |||
| 601 | /** | ||
| 602 | * \brief Sets the id of a triangle. | ||
| 603 | * \details Each triangle of a ConvexCell has an id, that can | ||
| 604 | * be used to maintain the correspondence with a vertex in the Mesh. | ||
| 605 | */ | ||
| 606 | void set_triangle_id(index_t t, signed_index_t id) { | ||
| 607 | geo_debug_assert(triangle_is_valid(t)); | ||
| 608 | 18002459 | triangles_[t].id_ = id; | |
| 609 | } | ||
| 610 | |||
| 611 | /** | ||
| 612 | * \brief Gets the id of a vertex. | ||
| 613 | * \details Each vertex of a ConvexCell has an id, that can | ||
| 614 | * be used to maintain the correspondence with a facet in the Mesh. | ||
| 615 | */ | ||
| 616 | signed_index_t vertex_id(index_t v) const { | ||
| 617 | geo_debug_assert(v != NO_VERTEX); | ||
| 618 | geo_debug_assert(v < max_v()); | ||
| 619 |
26/350✓ Branch 0 taken 50032 times.
✓ Branch 1 taken 75997 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✓ Branch 26 taken 349117 times.
✓ Branch 27 taken 592682 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✓ Branch 40 taken 443424 times.
✓ Branch 41 taken 718901 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✓ Branch 54 taken 588639 times.
✓ Branch 55 taken 864121 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✓ Branch 68 taken 635831 times.
✓ Branch 69 taken 903006 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✗ Branch 108 not taken.
✗ Branch 109 not taken.
✗ Branch 110 not taken.
✗ Branch 111 not taken.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✓ Branch 136 taken 8622 times.
✓ Branch 137 taken 14645 times.
✗ Branch 138 not taken.
✗ Branch 139 not taken.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✓ Branch 166 taken 556925 times.
✓ Branch 167 taken 384874 times.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✓ Branch 172 taken 10742 times.
✓ Branch 173 taken 17360 times.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✓ Branch 202 taken 675057 times.
✓ Branch 203 taken 487268 times.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✓ Branch 208 taken 14864 times.
✓ Branch 209 taken 21622 times.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✓ Branch 238 taken 808430 times.
✓ Branch 239 taken 644330 times.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✓ Branch 244 taken 15804 times.
✓ Branch 245 taken 22370 times.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✗ Branch 248 not taken.
✗ Branch 249 not taken.
✗ Branch 250 not taken.
✗ Branch 251 not taken.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✓ Branch 274 taken 842942 times.
✓ Branch 275 taken 695895 times.
✗ Branch 276 not taken.
✗ Branch 277 not taken.
✗ Branch 278 not taken.
✗ Branch 279 not taken.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✗ Branch 304 not taken.
✗ Branch 305 not taken.
✗ Branch 306 not taken.
✗ Branch 307 not taken.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✗ Branch 332 not taken.
✗ Branch 333 not taken.
✗ Branch 334 not taken.
✗ Branch 335 not taken.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
|
10443500 | return vertices_[v].id_; |
| 620 | } | ||
| 621 | |||
| 622 | /** | ||
| 623 | * \brief Sets the id of a vertex. | ||
| 624 | * \details Each vertex of a ConvexCell has an id, that can | ||
| 625 | * be used to maintain the correspondence with a facet in the Mesh. | ||
| 626 | */ | ||
| 627 | void set_vertex_id(index_t v, signed_index_t id) { | ||
| 628 | geo_debug_assert(v != NO_VERTEX); | ||
| 629 | geo_debug_assert(v < max_v()); | ||
| 630 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 809425 times.
|
10855736 | vertices_[v].id_ = id; |
| 631 | } | ||
| 632 | |||
| 633 | /** | ||
| 634 | * \brief A Corner corresponds to a vertex seen from a triangle. | ||
| 635 | * \details Corner has helper functions that facilitate traversing | ||
| 636 | * the vertices of a facet in dual form. | ||
| 637 | */ | ||
| 638 | class Corner { | ||
| 639 | public: | ||
| 640 | /** | ||
| 641 | * \brief Creates an uninitialized Corner. | ||
| 642 | */ | ||
| 643 | Corner() : | ||
| 644 | t(NO_TRIANGLE), | ||
| 645 | v(3) { | ||
| 646 | } | ||
| 647 | |||
| 648 | /** | ||
| 649 | * \brief Creates a Corner from a triangle index and | ||
| 650 | * local vertex index. | ||
| 651 | * \param[in] t_in index of the triangle | ||
| 652 | * \param[in] v_in local index (0,1 or 2) in triangle \p t_in. | ||
| 653 | */ | ||
| 654 | 5095721 | Corner(index_t t_in, index_t v_in) : | |
| 655 | 5095721 | t(t_in), | |
| 656 |
8/98✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✓ Branch 26 taken 423990 times.
✓ Branch 27 taken 517809 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✓ Branch 40 taken 529878 times.
✓ Branch 41 taken 632447 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
✓ Branch 54 taken 681513 times.
✓ Branch 55 taken 771247 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✓ Branch 68 taken 728874 times.
✓ Branch 69 taken 809963 times.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✗ Branch 80 not taken.
✗ Branch 81 not taken.
✗ Branch 82 not taken.
✗ Branch 83 not taken.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
|
5095721 | v(v_in) { |
| 657 | } | ||
| 658 | |||
| 659 | /** | ||
| 660 | * \brief Compares two corners. | ||
| 661 | * \param[in] rhs the right hand side | ||
| 662 | * \retval true if this Corner and \p rhs correspond to the same | ||
| 663 | * triangle and the same vertex | ||
| 664 | * \retval false otherwise | ||
| 665 | */ | ||
| 666 | bool operator== (const Corner& rhs) const { | ||
| 667 | return t == rhs.t && v == rhs.v; | ||
| 668 | } | ||
| 669 | |||
| 670 | /** | ||
| 671 | * \brief Compares two corners. | ||
| 672 | * \param[in] rhs the right hand side | ||
| 673 | * \retval true if this Corner and \p rhs correspond to different | ||
| 674 | * triangles or different vertices | ||
| 675 | * \retval false otherwise | ||
| 676 | */ | ||
| 677 | bool operator!= (const Corner& rhs) const { | ||
| 678 |
27/392✓ Branch 0 taken 132698 times.
✓ Branch 1 taken 428818 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 132698 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
✗ Branch 33 not taken.
✗ Branch 34 not taken.
✗ Branch 35 not taken.
✗ Branch 36 not taken.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 51 not taken.
✓ Branch 52 taken 517809 times.
✓ Branch 53 taken 2552634 times.
✗ Branch 54 not taken.
✓ Branch 55 taken 517809 times.
✗ Branch 56 not taken.
✗ Branch 57 not taken.
✗ Branch 58 not taken.
✗ Branch 59 not taken.
✗ Branch 60 not taken.
✗ Branch 61 not taken.
✗ Branch 62 not taken.
✗ Branch 63 not taken.
✗ Branch 64 not taken.
✗ Branch 65 not taken.
✗ Branch 66 not taken.
✗ Branch 67 not taken.
✗ Branch 68 not taken.
✗ Branch 69 not taken.
✗ Branch 70 not taken.
✗ Branch 71 not taken.
✗ Branch 72 not taken.
✗ Branch 73 not taken.
✗ Branch 74 not taken.
✗ Branch 75 not taken.
✗ Branch 76 not taken.
✗ Branch 77 not taken.
✗ Branch 78 not taken.
✗ Branch 79 not taken.
✓ Branch 80 taken 632447 times.
✓ Branch 81 taken 3116065 times.
✗ Branch 82 not taken.
✓ Branch 83 taken 632447 times.
✗ Branch 84 not taken.
✗ Branch 85 not taken.
✗ Branch 86 not taken.
✗ Branch 87 not taken.
✗ Branch 88 not taken.
✗ Branch 89 not taken.
✗ Branch 90 not taken.
✗ Branch 91 not taken.
✗ Branch 92 not taken.
✗ Branch 93 not taken.
✗ Branch 94 not taken.
✗ Branch 95 not taken.
✗ Branch 96 not taken.
✗ Branch 97 not taken.
✗ Branch 98 not taken.
✗ Branch 99 not taken.
✗ Branch 100 not taken.
✗ Branch 101 not taken.
✗ Branch 102 not taken.
✗ Branch 103 not taken.
✗ Branch 104 not taken.
✗ Branch 105 not taken.
✗ Branch 106 not taken.
✗ Branch 107 not taken.
✓ Branch 108 taken 771247 times.
✓ Branch 109 taken 3810239 times.
✗ Branch 110 not taken.
✓ Branch 111 taken 771247 times.
✗ Branch 112 not taken.
✗ Branch 113 not taken.
✗ Branch 114 not taken.
✗ Branch 115 not taken.
✗ Branch 116 not taken.
✗ Branch 117 not taken.
✗ Branch 118 not taken.
✗ Branch 119 not taken.
✗ Branch 120 not taken.
✗ Branch 121 not taken.
✗ Branch 122 not taken.
✗ Branch 123 not taken.
✗ Branch 124 not taken.
✗ Branch 125 not taken.
✗ Branch 126 not taken.
✗ Branch 127 not taken.
✗ Branch 128 not taken.
✗ Branch 129 not taken.
✗ Branch 130 not taken.
✗ Branch 131 not taken.
✗ Branch 132 not taken.
✗ Branch 133 not taken.
✗ Branch 134 not taken.
✗ Branch 135 not taken.
✓ Branch 136 taken 809963 times.
✓ Branch 137 taken 4010042 times.
✗ Branch 138 not taken.
✓ Branch 139 taken 809963 times.
✗ Branch 140 not taken.
✗ Branch 141 not taken.
✗ Branch 142 not taken.
✗ Branch 143 not taken.
✗ Branch 144 not taken.
✗ Branch 145 not taken.
✗ Branch 146 not taken.
✗ Branch 147 not taken.
✗ Branch 148 not taken.
✗ Branch 149 not taken.
✗ Branch 150 not taken.
✗ Branch 151 not taken.
✗ Branch 152 not taken.
✗ Branch 153 not taken.
✗ Branch 154 not taken.
✗ Branch 155 not taken.
✗ Branch 156 not taken.
✗ Branch 157 not taken.
✗ Branch 158 not taken.
✗ Branch 159 not taken.
✗ Branch 160 not taken.
✗ Branch 161 not taken.
✗ Branch 162 not taken.
✗ Branch 163 not taken.
✗ Branch 164 not taken.
✗ Branch 165 not taken.
✗ Branch 166 not taken.
✗ Branch 167 not taken.
✗ Branch 168 not taken.
✗ Branch 169 not taken.
✗ Branch 170 not taken.
✗ Branch 171 not taken.
✗ Branch 172 not taken.
✗ Branch 173 not taken.
✗ Branch 174 not taken.
✗ Branch 175 not taken.
✗ Branch 176 not taken.
✗ Branch 177 not taken.
✗ Branch 178 not taken.
✗ Branch 179 not taken.
✗ Branch 180 not taken.
✗ Branch 181 not taken.
✗ Branch 182 not taken.
✗ Branch 183 not taken.
✗ Branch 184 not taken.
✗ Branch 185 not taken.
✗ Branch 186 not taken.
✗ Branch 187 not taken.
✗ Branch 188 not taken.
✗ Branch 189 not taken.
✗ Branch 190 not taken.
✗ Branch 191 not taken.
✗ Branch 192 not taken.
✗ Branch 193 not taken.
✗ Branch 194 not taken.
✗ Branch 195 not taken.
✗ Branch 196 not taken.
✗ Branch 197 not taken.
✗ Branch 198 not taken.
✗ Branch 199 not taken.
✗ Branch 200 not taken.
✗ Branch 201 not taken.
✗ Branch 202 not taken.
✗ Branch 203 not taken.
✗ Branch 204 not taken.
✗ Branch 205 not taken.
✗ Branch 206 not taken.
✗ Branch 207 not taken.
✗ Branch 208 not taken.
✗ Branch 209 not taken.
✗ Branch 210 not taken.
✗ Branch 211 not taken.
✗ Branch 212 not taken.
✗ Branch 213 not taken.
✗ Branch 214 not taken.
✗ Branch 215 not taken.
✗ Branch 216 not taken.
✗ Branch 217 not taken.
✗ Branch 218 not taken.
✗ Branch 219 not taken.
✗ Branch 220 not taken.
✗ Branch 221 not taken.
✗ Branch 222 not taken.
✗ Branch 223 not taken.
✗ Branch 224 not taken.
✗ Branch 225 not taken.
✗ Branch 226 not taken.
✗ Branch 227 not taken.
✗ Branch 228 not taken.
✗ Branch 229 not taken.
✗ Branch 230 not taken.
✗ Branch 231 not taken.
✗ Branch 232 not taken.
✗ Branch 233 not taken.
✗ Branch 234 not taken.
✗ Branch 235 not taken.
✗ Branch 236 not taken.
✗ Branch 237 not taken.
✗ Branch 238 not taken.
✗ Branch 239 not taken.
✗ Branch 240 not taken.
✗ Branch 241 not taken.
✗ Branch 242 not taken.
✗ Branch 243 not taken.
✗ Branch 244 not taken.
✗ Branch 245 not taken.
✗ Branch 246 not taken.
✗ Branch 247 not taken.
✓ Branch 248 taken 517809 times.
✓ Branch 249 taken 621059 times.
✗ Branch 250 not taken.
✓ Branch 251 taken 517809 times.
✗ Branch 252 not taken.
✗ Branch 253 not taken.
✗ Branch 254 not taken.
✗ Branch 255 not taken.
✗ Branch 256 not taken.
✗ Branch 257 not taken.
✗ Branch 258 not taken.
✗ Branch 259 not taken.
✗ Branch 260 not taken.
✗ Branch 261 not taken.
✗ Branch 262 not taken.
✗ Branch 263 not taken.
✗ Branch 264 not taken.
✗ Branch 265 not taken.
✗ Branch 266 not taken.
✗ Branch 267 not taken.
✗ Branch 268 not taken.
✗ Branch 269 not taken.
✗ Branch 270 not taken.
✗ Branch 271 not taken.
✗ Branch 272 not taken.
✗ Branch 273 not taken.
✗ Branch 274 not taken.
✗ Branch 275 not taken.
✓ Branch 276 taken 632447 times.
✓ Branch 277 taken 740408 times.
✗ Branch 278 not taken.
✓ Branch 279 taken 632447 times.
✗ Branch 280 not taken.
✗ Branch 281 not taken.
✗ Branch 282 not taken.
✗ Branch 283 not taken.
✗ Branch 284 not taken.
✗ Branch 285 not taken.
✗ Branch 286 not taken.
✗ Branch 287 not taken.
✗ Branch 288 not taken.
✗ Branch 289 not taken.
✗ Branch 290 not taken.
✗ Branch 291 not taken.
✗ Branch 292 not taken.
✗ Branch 293 not taken.
✗ Branch 294 not taken.
✗ Branch 295 not taken.
✗ Branch 296 not taken.
✗ Branch 297 not taken.
✗ Branch 298 not taken.
✗ Branch 299 not taken.
✗ Branch 300 not taken.
✗ Branch 301 not taken.
✗ Branch 302 not taken.
✗ Branch 303 not taken.
✓ Branch 304 taken 771247 times.
✓ Branch 305 taken 855916 times.
✗ Branch 306 not taken.
✓ Branch 307 taken 771247 times.
✗ Branch 308 not taken.
✗ Branch 309 not taken.
✗ Branch 310 not taken.
✗ Branch 311 not taken.
✗ Branch 312 not taken.
✗ Branch 313 not taken.
✗ Branch 314 not taken.
✗ Branch 315 not taken.
✗ Branch 316 not taken.
✗ Branch 317 not taken.
✗ Branch 318 not taken.
✗ Branch 319 not taken.
✗ Branch 320 not taken.
✗ Branch 321 not taken.
✗ Branch 322 not taken.
✗ Branch 323 not taken.
✗ Branch 324 not taken.
✗ Branch 325 not taken.
✗ Branch 326 not taken.
✗ Branch 327 not taken.
✗ Branch 328 not taken.
✗ Branch 329 not taken.
✗ Branch 330 not taken.
✗ Branch 331 not taken.
✓ Branch 332 taken 809963 times.
✓ Branch 333 taken 884542 times.
✗ Branch 334 not taken.
✓ Branch 335 taken 809963 times.
✗ Branch 336 not taken.
✗ Branch 337 not taken.
✗ Branch 338 not taken.
✗ Branch 339 not taken.
✗ Branch 340 not taken.
✗ Branch 341 not taken.
✗ Branch 342 not taken.
✗ Branch 343 not taken.
✗ Branch 344 not taken.
✗ Branch 345 not taken.
✗ Branch 346 not taken.
✗ Branch 347 not taken.
✗ Branch 348 not taken.
✗ Branch 349 not taken.
✗ Branch 350 not taken.
✗ Branch 351 not taken.
✗ Branch 352 not taken.
✗ Branch 353 not taken.
✗ Branch 354 not taken.
✗ Branch 355 not taken.
✗ Branch 356 not taken.
✗ Branch 357 not taken.
✗ Branch 358 not taken.
✗ Branch 359 not taken.
✗ Branch 360 not taken.
✗ Branch 361 not taken.
✗ Branch 362 not taken.
✗ Branch 363 not taken.
✗ Branch 364 not taken.
✗ Branch 365 not taken.
✗ Branch 366 not taken.
✗ Branch 367 not taken.
✗ Branch 368 not taken.
✗ Branch 369 not taken.
✗ Branch 370 not taken.
✗ Branch 371 not taken.
✗ Branch 372 not taken.
✗ Branch 373 not taken.
✗ Branch 374 not taken.
✗ Branch 375 not taken.
✗ Branch 376 not taken.
✗ Branch 377 not taken.
✗ Branch 378 not taken.
✗ Branch 379 not taken.
✗ Branch 380 not taken.
✗ Branch 381 not taken.
✗ Branch 382 not taken.
✗ Branch 383 not taken.
✗ Branch 384 not taken.
✗ Branch 385 not taken.
✗ Branch 386 not taken.
✗ Branch 387 not taken.
✗ Branch 388 not taken.
✗ Branch 389 not taken.
✗ Branch 390 not taken.
✗ Branch 391 not taken.
|
22615353 | return t != rhs.t || v != rhs.v; |
| 679 | } | ||
| 680 | |||
| 681 | index_t t; | ||
| 682 | index_t v; | ||
| 683 | }; | ||
| 684 | |||
| 685 | /** | ||
| 686 | * \brief Replaces a corner by the next corner obtained by turing around | ||
| 687 | * the vertex. | ||
| 688 | * \param[in,out] c the corner | ||
| 689 | */ | ||
| 690 | 28078285 | void move_to_next_around_vertex(Corner& c) const { | |
| 691 | 28078285 | index_t t2 = triangle_adjacent(c.t, plus1mod3(c.v)); | |
| 692 | index_t v = triangle_vertex(c.t, c.v); | ||
| 693 | 28078285 | c.v = find_triangle_vertex(t2, v); | |
| 694 | 28078285 | c.t = t2; | |
| 695 | 28078285 | } | |
| 696 | |||
| 697 | /** | ||
| 698 | * \brief Updates the cache that stores for each vertex a triangle | ||
| 699 | * incident to it. | ||
| 700 | */ | ||
| 701 | 807641 | void init_v_to_t() { | |
| 702 | 807641 | v_to_t_dirty_ = false; | |
| 703 |
2/2✓ Branch 0 taken 13259736 times.
✓ Branch 1 taken 807641 times.
|
14875018 | for(index_t v = 0; v < max_v(); v++) { |
| 704 | set_vertex_triangle(v, NO_TRIANGLE); | ||
| 705 | } | ||
| 706 |
2/2✓ Branch 0 taken 10179522 times.
✓ Branch 1 taken 807641 times.
|
21166685 | for(index_t t = 0; t < max_t(); t++) { |
| 707 |
2/2✓ Branch 0 taken 7226274 times.
✓ Branch 1 taken 2953248 times.
|
10179522 | if(triangle_is_used(t)) { |
| 708 |
2/2✓ Branch 0 taken 21678822 times.
✓ Branch 1 taken 7226274 times.
|
28905096 | for(index_t iv = 0; iv < 3; iv++) { |
| 709 | set_vertex_triangle(triangle_vertex(t, iv), t); | ||
| 710 | } | ||
| 711 | } | ||
| 712 | } | ||
| 713 | 807641 | } | |
| 714 | |||
| 715 | /** | ||
| 716 | * \brief Creates a new uninitialized triangle. | ||
| 717 | * \details The created triangle is marked as used. | ||
| 718 | * \return The index of the new triangle. | ||
| 719 | */ | ||
| 720 | 18002459 | index_t create_triangle() { | |
| 721 |
2/2✓ Branch 0 taken 10199191 times.
✓ Branch 1 taken 7803268 times.
|
18002459 | if(first_free_ == END_OF_LIST) { |
| 722 | 10199191 | grow(); | |
| 723 | } | ||
| 724 | 18002459 | index_t result = first_free_; | |
| 725 | 18002459 | first_free_ = next_triangle(first_free_); | |
| 726 | mark_as_used(result); | ||
| 727 | set_triangle_id(result, -1); | ||
| 728 | 18002459 | return result; | |
| 729 | } | ||
| 730 | |||
| 731 | /** | ||
| 732 | * \brief Creates a new triangle with specified vertices. | ||
| 733 | * \details The created triangle is marked as used. Adjacent | ||
| 734 | * triangles are left uninitialized. | ||
| 735 | * \param[in] v0 index of first vertex | ||
| 736 | * \param[in] v1 index of second vertex | ||
| 737 | * \param[in] v2 index of third vertex | ||
| 738 | * \return the index of the new triangle | ||
| 739 | */ | ||
| 740 | index_t create_triangle(index_t v0, index_t v1, index_t v2) { | ||
| 741 | 14764615 | index_t t = create_triangle(); | |
| 742 | 14764615 | triangles_[t].v[0] = v0; | |
| 743 | 14764615 | triangles_[t].v[1] = v1; | |
| 744 | 14764615 | triangles_[t].v[2] = v2; | |
| 745 | return t; | ||
| 746 | } | ||
| 747 | |||
| 748 | /** | ||
| 749 | * \brief Creates a new triangles with specified vertices and | ||
| 750 | * adjacent triangles. | ||
| 751 | * \details The created triangle is marked as used. | ||
| 752 | * \param[in] v0 index of first vertex | ||
| 753 | * \param[in] v1 index of second vertex | ||
| 754 | * \param[in] v2 index of third vertex | ||
| 755 | * \param[in] t0 index of adjacent triangle opposite to \p v0 | ||
| 756 | * \param[in] t1 index of adjacent triangle opposite to \p v1 | ||
| 757 | * \param[in] t2 index of adjacent triangle opposite to \p v2 | ||
| 758 | * \return the index of the new triangle | ||
| 759 | */ | ||
| 760 | index_t create_triangle( | ||
| 761 | index_t v0, index_t v1, index_t v2, | ||
| 762 | index_t t0, index_t t1, index_t t2 | ||
| 763 | ) { | ||
| 764 |
1/2✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
|
809569 | index_t t = create_triangle(); |
| 765 | 3237844 | triangles_[t].v[0] = v0; | |
| 766 | 3237844 | triangles_[t].v[1] = v1; | |
| 767 | 3237844 | triangles_[t].v[2] = v2; | |
| 768 | 3237844 | triangles_[t].t[0] = t0; | |
| 769 | 3237844 | triangles_[t].t[1] = t1; | |
| 770 |
3/4✓ Branch 0 taken 144 times.
✗ Branch 1 not taken.
✓ Branch 5 taken 19547 times.
✓ Branch 6 taken 789878 times.
|
809569 | triangles_[t].t[2] = t2; |
| 771 | return t; | ||
| 772 | } | ||
| 773 | |||
| 774 | /** | ||
| 775 | * \brief Sets the vertices and adjacent triangles of a triangle. | ||
| 776 | * \param[in] t index of the triangle | ||
| 777 | * \param[in] v0 index of first vertex | ||
| 778 | * \param[in] v1 index of second vertex | ||
| 779 | * \param[in] v2 index of third vertex | ||
| 780 | * \param[in] t0 index of adjacent triangle opposite to \p v0 | ||
| 781 | * \param[in] t1 index of adjacent triangle opposite to \p v1 | ||
| 782 | * \param[in] t2 index of adjacent triangle opposite to \p v2 | ||
| 783 | */ | ||
| 784 | void set_triangle( | ||
| 785 | index_t t, | ||
| 786 | index_t v0, index_t v1, index_t v2, | ||
| 787 | index_t t0, index_t t1, index_t t2 | ||
| 788 | ) { | ||
| 789 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 790 | geo_debug_assert(t < max_t()); | ||
| 791 | triangles_[t].v[0] = v0; | ||
| 792 | triangles_[t].v[1] = v1; | ||
| 793 | triangles_[t].v[2] = v2; | ||
| 794 | triangles_[t].t[0] = t0; | ||
| 795 | triangles_[t].t[1] = t1; | ||
| 796 | triangles_[t].t[2] = t2; | ||
| 797 | } | ||
| 798 | |||
| 799 | /** | ||
| 800 | * \brief Creates a new triangles with specified vertices, | ||
| 801 | * adjacent triangles and geometric location at the dual | ||
| 802 | * vertex. | ||
| 803 | * \details The vertex is shared with caller. | ||
| 804 | * The created triangle is marked as used. | ||
| 805 | * \param[in] p geometric location at the dual vertex, shared with | ||
| 806 | * caller. Caller remains responsible for memory management. | ||
| 807 | * \param[in] w the weight associated with point \p p | ||
| 808 | * \param[in] v0 index of first vertex | ||
| 809 | * \param[in] v1 index of second vertex | ||
| 810 | * \param[in] v2 index of third vertex | ||
| 811 | * \param[in] t0 index of adjacent triangle opposite to \p v0 | ||
| 812 | * \param[in] t1 index of adjacent triangle opposite to \p v1 | ||
| 813 | * \param[in] t2 index of adjacent triangle opposite to \p v2 | ||
| 814 | * \return the index of the new triangle | ||
| 815 | */ | ||
| 816 | index_t create_triangle( | ||
| 817 | const double* p, | ||
| 818 | double w, | ||
| 819 | index_t v0, index_t v1, index_t v2, | ||
| 820 | index_t t0, index_t t1, index_t t2 | ||
| 821 | ) { | ||
| 822 | index_t t = create_triangle(v0, v1, v2, t0, t1, t2); | ||
| 823 | triangle_dual(t).set_point(p); | ||
| 824 | triangle_dual(t).set_weight(w); | ||
| 825 | return t; | ||
| 826 | } | ||
| 827 | |||
| 828 | /** | ||
| 829 | * \brief Creates a new triangles with specified vertices, | ||
| 830 | * adjacent triangles and geometric location at the dual | ||
| 831 | * vertex. | ||
| 832 | * \details The vertex is copied into local storage. | ||
| 833 | * The created triangle is marked as used. | ||
| 834 | * \param[in] p geometric location at the dual vertex. Vertex | ||
| 835 | * is copied into local storage. | ||
| 836 | * \param[in] v0 index of first vertex | ||
| 837 | * \param[in] v1 index of second vertex | ||
| 838 | * \param[in] v2 index of third vertex | ||
| 839 | * \param[in] t0 index of adjacent triangle opposite to \p v0 | ||
| 840 | * \param[in] t1 index of adjacent triangle opposite to \p v1 | ||
| 841 | * \param[in] t2 index of adjacent triangle opposite to \p v2 | ||
| 842 | * \return the index of the new triangle | ||
| 843 | */ | ||
| 844 | index_t create_triangle_copy( | ||
| 845 | const double* p, | ||
| 846 | index_t v0, index_t v1, index_t v2, | ||
| 847 | index_t t0, index_t t1, index_t t2 | ||
| 848 | ) { | ||
| 849 | index_t t = create_triangle(v0, v1, v2, t0, t1, t2); | ||
| 850 | double* np = intersections_.new_item(); | ||
| 851 | for(coord_index_t c = 0; c < dimension(); ++c) { | ||
| 852 | np[c] = p[c]; | ||
| 853 | } | ||
| 854 | triangle_dual(t).set_point(np); | ||
| 855 | return t; | ||
| 856 | } | ||
| 857 | |||
| 858 | /** | ||
| 859 | * \brief Creates a new vertex. | ||
| 860 | * \return the index of the new vertex | ||
| 861 | */ | ||
| 862 | 3237700 | index_t create_vertex() { | |
| 863 | 13284011 | v_to_t_dirty_ = true; | |
| 864 |
5/14✗ Branch 1 not taken.
✓ Branch 2 taken 26760 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 5060541 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2399765 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 2893972 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 2902973 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
|
13284011 | vertices_.push_back(Vertex()); |
| 865 | 13283903 | return vertices_.size() - 1; | |
| 866 | } | ||
| 867 | |||
| 868 | /** | ||
| 869 | * \brief Triangulates the conflict zone. | ||
| 870 | * \details Creates the triangles radiating from \p new_v and | ||
| 871 | * attached to the border of the conflict zone, indicated by \p t and \p e. | ||
| 872 | * \param[in] delaunay the Delaunay triangulation | ||
| 873 | * \param[in] i index of the first extremity of | ||
| 874 | * the bisector in \p delaunay. | ||
| 875 | * \param[in] j index of the first extremity of | ||
| 876 | * the bisector in \p delaunay. | ||
| 877 | * \param[in] symbolic if true, symbolic representation of the | ||
| 878 | * vertices is generated. | ||
| 879 | * \param[in] t1 a triangle adjacent to the border of the conflict zone from | ||
| 880 | * inside. | ||
| 881 | * \param[in] t1ebord the edge along which t is adjacent to the border of the conflict | ||
| 882 | * zone. | ||
| 883 | * \param[in] v_in index of the new vertex | ||
| 884 | * \return one of the created triangles | ||
| 885 | */ | ||
| 886 | template <index_t DIM> | ||
| 887 | 8050935 | index_t triangulate_hole( | |
| 888 | const Delaunay* delaunay, | ||
| 889 | index_t i, index_t j, bool symbolic, | ||
| 890 | index_t t1, index_t t1ebord, | ||
| 891 | index_t v_in | ||
| 892 | ) { | ||
| 893 | index_t t = t1; | ||
| 894 | index_t e = t1ebord; | ||
| 895 | index_t t_adj = triangle_adjacent(t,e); | ||
| 896 | geo_debug_assert(t_adj != index_t(-1)); | ||
| 897 | |||
| 898 | geo_debug_assert(triangle_is_conflict(t)); | ||
| 899 | geo_debug_assert(!triangle_is_conflict(t_adj)); | ||
| 900 | |||
| 901 | index_t new_t_first = index_t(-1); | ||
| 902 | index_t new_t_prev = index_t(-1); | ||
| 903 | |||
| 904 | do { | ||
| 905 | |||
| 906 | index_t v1 = triangle_vertex(t, plus1mod3(e)); | ||
| 907 | index_t v2 = triangle_vertex(t, minus1mod3(e)); | ||
| 908 | |||
| 909 | // Create new triangle | ||
| 910 | index_t new_t = create_triangle(v_in, v1, v2); | ||
| 911 | |||
| 912 | 29492882 | triangle_dual(new_t).intersect_geom<DIM>( | |
| 913 | 29492882 | intersections_, | |
| 914 | triangle_dual(t), | ||
| 915 | triangle_dual(triangle_adjacent(t, e)), | ||
| 916 | delaunay->vertex_ptr(i), delaunay->vertex_ptr(j) | ||
| 917 | ); | ||
| 918 | |||
| 919 |
2/2✓ Branch 0 taken 380981 times.
✓ Branch 1 taken 14383634 times.
|
29492882 | if(symbolic) { |
| 920 | 737730 | triangle_dual(new_t).sym().intersect_symbolic( | |
| 921 | triangle_dual(t).sym(), | ||
| 922 | triangle_dual(triangle_adjacent(t, e)).sym(), | ||
| 923 | j | ||
| 924 | ); | ||
| 925 | } | ||
| 926 | |||
| 927 | // Connect new triangle to triangle on the other | ||
| 928 | // side of the conflict zone. | ||
| 929 | set_triangle_adjacent(new_t, 0, t_adj); | ||
| 930 | index_t adj_e = triangle_adjacent_index(t_adj, t); | ||
| 931 | set_triangle_adjacent(t_adj, adj_e, new_t); | ||
| 932 | |||
| 933 | |||
| 934 | // Move to next triangle | ||
| 935 | e = plus1mod3(e); | ||
| 936 | t_adj = index_t(triangle_adjacent(t,e)); | ||
| 937 |
2/2✓ Branch 0 taken 10484491 times.
✓ Branch 1 taken 14764615 times.
|
50428894 | while(triangle_is_conflict(t_adj)) { |
| 938 | t = t_adj; | ||
| 939 | e = minus1mod3(find_triangle_vertex(t,v2)); | ||
| 940 | t_adj = index_t(triangle_adjacent(t,e)); | ||
| 941 | geo_debug_assert(t_adj != index_t(-1)); | ||
| 942 | } | ||
| 943 | |||
| 944 |
2/2✓ Branch 0 taken 10735822 times.
✓ Branch 1 taken 4028793 times.
|
29492882 | if(new_t_prev == index_t(-1)) { |
| 945 | new_t_first = new_t; | ||
| 946 | } else { | ||
| 947 | set_triangle_adjacent(new_t_prev, 1, new_t); | ||
| 948 | set_triangle_adjacent(new_t, 2, new_t_prev); | ||
| 949 | } | ||
| 950 | |||
| 951 | new_t_prev = new_t; | ||
| 952 | |||
| 953 |
2/2✓ Branch 0 taken 10735822 times.
✓ Branch 1 taken 4028793 times.
|
29492882 | } while((t != t1) || (e != t1ebord)); |
| 954 | |||
| 955 | // Connect last triangle to first triangle | ||
| 956 | set_triangle_adjacent(new_t_prev, 1, new_t_first); | ||
| 957 | set_triangle_adjacent(new_t_first, 2, new_t_prev); | ||
| 958 | |||
| 959 | 8050935 | return new_t_prev; | |
| 960 | } | ||
| 961 | |||
| 962 | /** | ||
| 963 | * \brief Determines the conflict zone. | ||
| 964 | * \details The conflict zone corresponds to the set of triangles | ||
| 965 | * that have their dual vertices on the negative side of a | ||
| 966 | * bisector. | ||
| 967 | * \param[in] mesh the input mesh | ||
| 968 | * \param[in] delaunay the Delaunay triangulation | ||
| 969 | * \param[in] i index of the first extremity | ||
| 970 | * of the bisector in \p delaunay | ||
| 971 | * \param[in] j index of the second extremity | ||
| 972 | * of the bisector in \p delaunay | ||
| 973 | * \param[in] exact if true, exact predicates are used | ||
| 974 | * \param[out] conflict_begin | ||
| 975 | * index of the first triangle in conflict list | ||
| 976 | * \param[out] conflict_end one position past index of the | ||
| 977 | * last triangle in conflict list | ||
| 978 | */ | ||
| 979 | template <index_t DIM> | ||
| 980 | 20065754 | void get_conflict_list( | |
| 981 | const Mesh* mesh, const Delaunay* delaunay, | ||
| 982 | index_t i, index_t j, bool exact, | ||
| 983 | index_t& conflict_begin, index_t& conflict_end | ||
| 984 | ) { | ||
| 985 | 20065754 | conflict_begin = END_OF_LIST; | |
| 986 | 20065754 | conflict_end = END_OF_LIST; | |
| 987 |
2/2✓ Branch 0 taken 255446 times.
✓ Branch 1 taken 9790757 times.
|
20065754 | if(exact) { |
| 988 | // In exact mode, we classify each vertex | ||
| 989 | // using the exact predicate. Note that | ||
| 990 | // "climbing/walking" from a random vertex | ||
| 991 | // would be more efficient, but it would require a | ||
| 992 | // "comparison" exact predicate (with 8 different | ||
| 993 | // versions according to the configuration of the | ||
| 994 | // two vertices to be compared) | ||
| 995 |
2/2✓ Branch 0 taken 42832045 times.
✓ Branch 1 taken 255446 times.
|
90939719 | for(index_t t = 0; t < max_t(); t++) { |
| 996 |
2/2✓ Branch 0 taken 42058330 times.
✓ Branch 1 taken 773715 times.
|
45226629 | if(triangle_is_used(t)) { |
| 997 | 43781018 | Sign s = side<DIM>( | |
| 998 | mesh, delaunay, | ||
| 999 | triangle_dual(t), | ||
| 1000 | i, j, | ||
| 1001 | exact | ||
| 1002 | ); | ||
| 1003 |
2/2✓ Branch 0 taken 276515 times.
✓ Branch 1 taken 41781815 times.
|
43781018 | if(s == GEO::NEGATIVE) { |
| 1004 | append_triangle_to_conflict_list( | ||
| 1005 | t, conflict_begin, conflict_end | ||
| 1006 | ); | ||
| 1007 | } | ||
| 1008 | } | ||
| 1009 | } | ||
| 1010 | } else { | ||
| 1011 | // In non-exact mode, we first detect the | ||
| 1012 | // vertex that is furthest away along the | ||
| 1013 | // normal vector of the clipping bisector, | ||
| 1014 | // and then we propagate using a flood-fill | ||
| 1015 | // algorithm. This strategy ensures that | ||
| 1016 | // the conflict zone remains connected, even | ||
| 1017 | // in the presence of numerical errors. Clearly | ||
| 1018 | // it does not ensure validity, but in practice | ||
| 1019 | // it improves resistance to degeneracies. | ||
| 1020 | index_t furthest_t = | ||
| 1021 | 19579293 | find_furthest_point_linear_scan<DIM>( | |
| 1022 | delaunay, i, j | ||
| 1023 | ); | ||
| 1024 | 19579293 | propagate_conflict_list<DIM>( | |
| 1025 | mesh, delaunay, furthest_t, | ||
| 1026 | i, j, exact, | ||
| 1027 | conflict_begin, conflict_end | ||
| 1028 | ); | ||
| 1029 | } | ||
| 1030 | 20065754 | } | |
| 1031 | |||
| 1032 | /** | ||
| 1033 | * \brief Finds the index of the vertex furthest away | ||
| 1034 | * on the negative side of a bisector. | ||
| 1035 | * \param[in] delaunay the Delaunay triangulation | ||
| 1036 | * \param[in] i index of the first extremity of the bisector | ||
| 1037 | * in \p delaunay | ||
| 1038 | * \param[in] j index of the second extremity of the bisector | ||
| 1039 | * in \p delaunay | ||
| 1040 | * \return the index of the vertex furthest away on \p j%'s side, | ||
| 1041 | * or -1 if all the vertices are on \p i%'s side. | ||
| 1042 | */ | ||
| 1043 | template <index_t DIM> | ||
| 1044 | 19579293 | index_t find_furthest_point_linear_scan( | |
| 1045 | const Delaunay* delaunay, index_t i, index_t j | ||
| 1046 | ) const { | ||
| 1047 | index_t result = NO_TRIANGLE; | ||
| 1048 | double furthest_dist = 0.0; | ||
| 1049 |
2/2✓ Branch 0 taken 104734599 times.
✓ Branch 1 taken 9790757 times.
|
454046710 | for(index_t t = 0; t < max_t(); ++t) { |
| 1050 |
2/2✓ Branch 0 taken 28685125 times.
✓ Branch 1 taken 76049474 times.
|
207444062 | if(triangle_is_used(t)) { |
| 1051 | 150082750 | double d = signed_bisector_distance<DIM>( | |
| 1052 | delaunay, i, j, triangle_dual(t).point() | ||
| 1053 | ); | ||
| 1054 |
2/2✓ Branch 0 taken 69828147 times.
✓ Branch 1 taken 6221327 times.
|
150082750 | if(d < furthest_dist) { |
| 1055 | result = t; | ||
| 1056 | furthest_dist = d; | ||
| 1057 | } | ||
| 1058 | } | ||
| 1059 | } | ||
| 1060 |
2/2✓ Branch 0 taken 3928715 times.
✓ Branch 1 taken 5862042 times.
|
19579293 | return (furthest_dist < 0) ? result : NO_TRIANGLE; |
| 1061 | } | ||
| 1062 | |||
| 1063 | /** | ||
| 1064 | * \brief Evaluates the equation of a bisector at a given point. | ||
| 1065 | * \details Positive side corresponds to vertex \p i and negative | ||
| 1066 | * side to vertex \p j. | ||
| 1067 | * \param[in] delaunay the Delaunay triangulation | ||
| 1068 | * \param[in] i index of the first extremity of the bisector | ||
| 1069 | * in \p delaunay | ||
| 1070 | * \param[in] j index of the second extremity of the bisector | ||
| 1071 | * in \p delaunay | ||
| 1072 | * \param[in] q the query point | ||
| 1073 | */ | ||
| 1074 | template <index_t DIM> | ||
| 1075 | 150082750 | static double signed_bisector_distance( | |
| 1076 | const Delaunay* delaunay, index_t i, index_t j, const double* q | ||
| 1077 | ) { | ||
| 1078 | const double* pi = delaunay->vertex_ptr(i); | ||
| 1079 | const double* pj = delaunay->vertex_ptr(j); | ||
| 1080 | double result = 0; | ||
| 1081 |
2/2✓ Branch 0 taken 415211134 times.
✓ Branch 1 taken 76049474 times.
|
974456424 | for(coord_index_t c = 0; c < DIM; ++c) { |
| 1082 | 824373674 | result += GEO::geo_sqr(q[c] - pj[c]); | |
| 1083 | 824373674 | result -= GEO::geo_sqr(q[c] - pi[c]); | |
| 1084 | } | ||
| 1085 | 150082750 | return result; | |
| 1086 | } | ||
| 1087 | |||
| 1088 | /** | ||
| 1089 | * \brief Computes the conflict list by propagation from | ||
| 1090 | * a conflict triangle. | ||
| 1091 | * \param[in] mesh the input mesh | ||
| 1092 | * \param[in] delaunay the Delaunay triangulation | ||
| 1093 | * \param[in] first_t a triangle in the conflict zone | ||
| 1094 | * \param[in] i index of the first extremity of the bisector | ||
| 1095 | * in \p delaunay | ||
| 1096 | * \param[in] j index of the second extremity of the bisector | ||
| 1097 | * in \p delaunay | ||
| 1098 | * \param[in] exact if true, exact predicates are used | ||
| 1099 | * \param[out] conflict_begin | ||
| 1100 | * index of the first triangle in conflict list | ||
| 1101 | * \param[out] conflict_end one position past index of the | ||
| 1102 | * last triangle in conflict list | ||
| 1103 | */ | ||
| 1104 | template <index_t DIM> | ||
| 1105 | 19579293 | void propagate_conflict_list( | |
| 1106 | const Mesh* mesh, const Delaunay* delaunay, | ||
| 1107 | index_t first_t, | ||
| 1108 | index_t i, index_t j, bool exact, | ||
| 1109 | index_t& conflict_begin, index_t& conflict_end | ||
| 1110 | ) { | ||
| 1111 | 19579293 | conflict_begin = END_OF_LIST; | |
| 1112 | 19579293 | conflict_end = END_OF_LIST; | |
| 1113 | |||
| 1114 | // Special case, clipping plane does not clip anything | ||
| 1115 |
2/2✓ Branch 0 taken 5862042 times.
✓ Branch 1 taken 3928715 times.
|
19579293 | if(first_t == NO_TRIANGLE) { |
| 1116 | 11724080 | return; | |
| 1117 | } | ||
| 1118 | |||
| 1119 | std::stack<index_t> S; | ||
| 1120 | S.push(first_t); | ||
| 1121 | append_triangle_to_conflict_list( | ||
| 1122 | first_t, conflict_begin, conflict_end | ||
| 1123 | ); | ||
| 1124 |
2/2✓ Branch 0 taken 10499670 times.
✓ Branch 1 taken 3928715 times.
|
28846811 | while(!S.empty()) { |
| 1125 |
1/2✓ Branch 0 taken 10499670 times.
✗ Branch 1 not taken.
|
20991598 | index_t t = S.top(); |
| 1126 | S.pop(); | ||
| 1127 |
2/2✓ Branch 0 taken 31499010 times.
✓ Branch 1 taken 10499670 times.
|
83966392 | for(unsigned int e = 0; e < 3; e++) { |
| 1128 |
2/2✓ Branch 0 taken 20954589 times.
✓ Branch 1 taken 10544421 times.
|
62974794 | index_t neigh = index_t(triangle_adjacent(t, e)); |
| 1129 |
2/2✓ Branch 0 taken 20954589 times.
✓ Branch 1 taken 10544421 times.
|
62974794 | if(!triangle_is_conflict(neigh)) { |
| 1130 |
2/2✓ Branch 0 taken 6570955 times.
✓ Branch 1 taken 14383634 times.
|
41891537 | if( |
| 1131 |
1/2✓ Branch 1 taken 20954589 times.
✗ Branch 2 not taken.
|
41891537 | side<DIM>( |
| 1132 | mesh, delaunay, triangle_dual(neigh), | ||
| 1133 | i, j, exact | ||
| 1134 | ) == GEO::NEGATIVE | ||
| 1135 | ) { | ||
| 1136 | S.push(neigh); | ||
| 1137 | append_triangle_to_conflict_list( | ||
| 1138 | neigh, conflict_begin, conflict_end | ||
| 1139 | ); | ||
| 1140 | } | ||
| 1141 | } | ||
| 1142 | } | ||
| 1143 | } | ||
| 1144 | } | ||
| 1145 | |||
| 1146 | /** | ||
| 1147 | * \brief Tests on which side a vertex is relative to | ||
| 1148 | * a bisector. | ||
| 1149 | * \param[in] mesh the input mesh | ||
| 1150 | * \param[in] delaunay the Delaunay triangulation | ||
| 1151 | * \param[in] v the query vertex | ||
| 1152 | * \param[in] i index of the first extremity of the bisector | ||
| 1153 | * in \p delaunay | ||
| 1154 | * \param[in] j index of the second extremity of the bisector | ||
| 1155 | * in \p delaunay | ||
| 1156 | * \param[in] exact if true, exact predicates are used | ||
| 1157 | * \return POSITIVE if \p v is on vertex \p i%'s side, | ||
| 1158 | * NEGATIVE otherwise. ZERO is never returned since | ||
| 1159 | * globally coherent symbolic perturbations are used | ||
| 1160 | * in exact mode. | ||
| 1161 | * \tparam DIM dimension, specified as a template | ||
| 1162 | * parameter for efficiency considerations. | ||
| 1163 | */ | ||
| 1164 | template <index_t DIM> | ||
| 1165 | 85672555 | Sign side( | |
| 1166 | const Mesh* mesh, const Delaunay* delaunay, | ||
| 1167 | const GEOGen::Vertex& v, | ||
| 1168 | index_t i, index_t j, bool exact | ||
| 1169 | ) const { | ||
| 1170 | Sign result = GEO::ZERO; | ||
| 1171 |
2/2✓ Branch 0 taken 42058330 times.
✓ Branch 1 taken 20954589 times.
|
85672555 | if(exact) { |
| 1172 | 43781018 | result = side_exact( | |
| 1173 | mesh, delaunay, v, | ||
| 1174 | delaunay->vertex_ptr(i), | ||
| 1175 | delaunay->vertex_ptr(j), | ||
| 1176 | DIM, | ||
| 1177 | 43781018 | symbolic_is_surface_ | |
| 1178 | ); | ||
| 1179 | } else { | ||
| 1180 | 41891537 | result = v.side_fast<DIM>( | |
| 1181 | delaunay->vertex_ptr(i), | ||
| 1182 | delaunay->vertex_ptr(j) | ||
| 1183 | ); | ||
| 1184 | } | ||
| 1185 | 85672555 | return result; | |
| 1186 | } | ||
| 1187 | |||
| 1188 | /** | ||
| 1189 | * \brief Tests on which side a vertex is relative to | ||
| 1190 | * a bisector using exact predicates. | ||
| 1191 | * \param[in] mesh the input mesh | ||
| 1192 | * \param[in] delaunay the Delaunay triangulation | ||
| 1193 | * \param[in] v the query vertex | ||
| 1194 | * \param[in] pi first extremity of the bisector | ||
| 1195 | * \param[in] pj second extremity of the bisector | ||
| 1196 | * \param[in] dim dimension of the points | ||
| 1197 | * \param[in] symbolic_is_surface if true, then symbolic | ||
| 1198 | * information is relative to a surface mesh (facets) | ||
| 1199 | * rather than volumetric mesh (tetrahedra). | ||
| 1200 | * \return POSITIVE if \p v is on vertex \p i%'s side, | ||
| 1201 | * NEGATIVE otherwise. ZERO is never returned since | ||
| 1202 | * globally coherent symbolic perturbations are used | ||
| 1203 | * in exact mode. | ||
| 1204 | * \note Only dimension=3 is implemented for now | ||
| 1205 | */ | ||
| 1206 | Sign side_exact( | ||
| 1207 | const Mesh* mesh, const Delaunay* delaunay, | ||
| 1208 | const GEOGen::Vertex& v, | ||
| 1209 | const double* pi, const double* pj, | ||
| 1210 | coord_index_t dim, | ||
| 1211 | bool symbolic_is_surface = false | ||
| 1212 | ) const; | ||
| 1213 | |||
| 1214 | /** | ||
| 1215 | * \brief Gets a triangle and an edge on the internal border of the conflict zone. | ||
| 1216 | * \details The returned triangle touches the conflict zone from inside. | ||
| 1217 | * \param[in] conflict_begin first triangle of the conflict zone | ||
| 1218 | * \param[in] conflict_end one element past the last triangle of | ||
| 1219 | * the conflict zone | ||
| 1220 | * \param[out] t a triangle in the conflict zone adjacent to the border of the | ||
| 1221 | * conflict zone. | ||
| 1222 | * \param[out] e the edge along which \p t is adjacent to the border of the | ||
| 1223 | * conflict zone. | ||
| 1224 | * \return true if a triangle on the border was found, false otherwise. | ||
| 1225 | */ | ||
| 1226 | 4030595 | bool find_triangle_on_border( | |
| 1227 | index_t conflict_begin, index_t conflict_end, | ||
| 1228 | index_t& t, index_t& e | ||
| 1229 | ) const { | ||
| 1230 | GEO::geo_argused(conflict_end); | ||
| 1231 | 4030595 | t = conflict_begin; | |
| 1232 | do { | ||
| 1233 |
2/2✓ Branch 0 taken 5719442 times.
✓ Branch 1 taken 43704 times.
|
5763146 | for(e = 0; e < 3; ++e) { |
| 1234 |
2/2✓ Branch 0 taken 1690649 times.
✓ Branch 1 taken 4028793 times.
|
5719442 | index_t nt = triangle_adjacent(t, e); |
| 1235 |
2/2✓ Branch 0 taken 1690649 times.
✓ Branch 1 taken 4028793 times.
|
5719442 | if(triangle_is_used(nt)) { |
| 1236 | return true; | ||
| 1237 | } | ||
| 1238 | } | ||
| 1239 |
2/2✓ Branch 0 taken 41902 times.
✓ Branch 1 taken 1802 times.
|
43704 | t = next_triangle(t); |
| 1240 | 43704 | } while(t != END_OF_LIST); | |
| 1241 | return false; | ||
| 1242 | } | ||
| 1243 | |||
| 1244 | /** | ||
| 1245 | * \brief Gets the successor of a triangle. | ||
| 1246 | * \details Triangles are linked, for instance to represent | ||
| 1247 | * the conflict zone. | ||
| 1248 | */ | ||
| 1249 | index_t next_triangle(index_t t) const { | ||
| 1250 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 1251 | geo_debug_assert(t < max_t()); | ||
| 1252 |
2/2✓ Branch 0 taken 41902 times.
✓ Branch 1 taken 1802 times.
|
3281548 | return triangles_[t].next_; |
| 1253 | } | ||
| 1254 | |||
| 1255 | /** | ||
| 1256 | * \brief Sets the successor of a triangle. | ||
| 1257 | * \details Triangles are linked, for instance to represent | ||
| 1258 | * the conflict zone. | ||
| 1259 | * \param[in] t index of the triangle | ||
| 1260 | * \param[in] t2 index of the successor | ||
| 1261 | */ | ||
| 1262 | void set_next_triangle(index_t t, index_t t2) { | ||
| 1263 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 1264 | geo_debug_assert(t < max_t()); | ||
| 1265 | 14804978 | triangles_[t].next_ = t2; | |
| 1266 | } | ||
| 1267 | |||
| 1268 | /** | ||
| 1269 | * \brief Specify that a triangle is free. | ||
| 1270 | * \details A free triangle can be reused by subsequent | ||
| 1271 | * triangle creations. | ||
| 1272 | */ | ||
| 1273 | void mark_as_free(index_t t) { | ||
| 1274 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 1275 | geo_debug_assert(t < max_t()); | ||
| 1276 | 6735748 | triangles_[t].status_ = TRI_IS_FREE; | |
| 1277 | } | ||
| 1278 | |||
| 1279 | /** | ||
| 1280 | * \brief Specify that a triangle belongs to the conflict zone. | ||
| 1281 | */ | ||
| 1282 | void mark_as_conflict(index_t t) { | ||
| 1283 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 1284 | geo_debug_assert(t < max_t()); | ||
| 1285 | 10776185 | triangles_[t].status_ = TRI_IS_CONFLICT; | |
| 1286 | } | ||
| 1287 | |||
| 1288 | /** | ||
| 1289 | * \brief Specify that a triangle is used. | ||
| 1290 | */ | ||
| 1291 | void mark_as_used(index_t t) { | ||
| 1292 | geo_debug_assert(t != NO_TRIANGLE); | ||
| 1293 | geo_debug_assert(t < max_t()); | ||
| 1294 | 18002459 | triangles_[t].status_ = TRI_IS_USED; | |
| 1295 | } | ||
| 1296 | |||
| 1297 | /** | ||
| 1298 | * \brief Appends a triangle to the conflict list. | ||
| 1299 | * \details The triangle is marked as conflict and | ||
| 1300 | * linked to the conflict list. | ||
| 1301 | * \param[in] t the triangle | ||
| 1302 | * \param[in,out] conflict_begin first triangle in the conflict list | ||
| 1303 | * \param[in,out] conflict_end one position past the last triangle | ||
| 1304 | * in the conflict list | ||
| 1305 | */ | ||
| 1306 | void append_triangle_to_conflict_list( | ||
| 1307 | index_t t, index_t& conflict_begin, index_t& conflict_end | ||
| 1308 | ) { | ||
| 1309 | geo_debug_assert(triangle_is_used(t)); | ||
| 1310 |
19/42✓ Branch 0 taken 2217 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 5525 times.
✓ Branch 4 taken 715931 times.
✓ Branch 5 taken 11050 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1180353 times.
✓ Branch 8 taken 922659 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 1570451 times.
✓ Branch 12 taken 1130742 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 1896466 times.
✓ Branch 16 taken 1161600 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 19 taken 1918160 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✓ Branch 30 taken 17626 times.
✓ Branch 31 taken 29371 times.
✓ Branch 32 taken 22418 times.
✓ Branch 33 taken 38462 times.
✓ Branch 34 taken 28587 times.
✓ Branch 35 taken 48075 times.
✓ Branch 36 taken 28815 times.
✓ Branch 37 taken 47677 times.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
|
10776185 | set_next_triangle(t, conflict_begin); |
| 1311 | mark_as_conflict(t); | ||
| 1312 | 10776185 | conflict_begin = t; | |
| 1313 |
19/42✓ Branch 0 taken 2217 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 5525 times.
✓ Branch 4 taken 715931 times.
✓ Branch 5 taken 11050 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1180353 times.
✓ Branch 8 taken 922659 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 1570451 times.
✓ Branch 12 taken 1130742 times.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 1896466 times.
✓ Branch 16 taken 1161600 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
✓ Branch 19 taken 1918160 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✓ Branch 30 taken 17626 times.
✓ Branch 31 taken 29371 times.
✓ Branch 32 taken 22418 times.
✓ Branch 33 taken 38462 times.
✓ Branch 34 taken 28587 times.
✓ Branch 35 taken 48075 times.
✓ Branch 36 taken 28815 times.
✓ Branch 37 taken 47677 times.
✗ Branch 38 not taken.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
|
10776185 | if(conflict_end == END_OF_LIST) { |
| 1314 | 4030595 | conflict_end = t; | |
| 1315 | } | ||
| 1316 | } | ||
| 1317 | |||
| 1318 | /** | ||
| 1319 | * \brief Merges a list of triangles into the free list. | ||
| 1320 | * \param[in] list_begin first triangle in the list to be freed | ||
| 1321 | * \param[in] list_end one position past the last triangle of | ||
| 1322 | * the list to be freed | ||
| 1323 | */ | ||
| 1324 | void merge_into_free_list(index_t list_begin, index_t list_end) { | ||
| 1325 | if(list_begin != END_OF_LIST) { | ||
| 1326 | geo_debug_assert(list_end != END_OF_LIST); | ||
| 1327 | |||
| 1328 | index_t cur = list_begin; | ||
| 1329 |
10/14✓ Branch 0 taken 16575 times.
✓ Branch 1 taken 6651 times.
✓ Branch 2 taken 1208868 times.
✓ Branch 3 taken 728945 times.
✓ Branch 4 taken 1605527 times.
✓ Branch 5 taken 944453 times.
✓ Branch 6 taken 1941150 times.
✓ Branch 7 taken 1158720 times.
✓ Branch 8 taken 1963628 times.
✓ Branch 9 taken 1190024 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
|
10764541 | while(cur != list_end) { |
| 1330 | mark_as_free(cur); | ||
| 1331 | cur = next_triangle(cur); | ||
| 1332 | } | ||
| 1333 | mark_as_free(list_end); | ||
| 1334 | 4028793 | set_next_triangle(list_end, first_free_); | |
| 1335 | 4028793 | first_free_ = list_begin; | |
| 1336 | } | ||
| 1337 | } | ||
| 1338 | |||
| 1339 | /** | ||
| 1340 | * \brief Allocates a new triangle. | ||
| 1341 | * \details This function is called whenever a triangle needs | ||
| 1342 | * to be created and the free list is empty. | ||
| 1343 | */ | ||
| 1344 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 10199191 times.
|
10199191 | void grow() { |
| 1345 | geo_debug_assert(first_free_ == END_OF_LIST); | ||
| 1346 | 10199191 | first_free_ = triangles_.size(); | |
| 1347 | 10199191 | triangles_.push_back(Triangle()); | |
| 1348 | 10199191 | } | |
| 1349 | |||
| 1350 | /** | ||
| 1351 | * \brief Displays the number of free,used,conflict triangles. | ||
| 1352 | * \details For debugging purposes. | ||
| 1353 | */ | ||
| 1354 | std::ostream& show_stats(std::ostream& os) const; | ||
| 1355 | |||
| 1356 | /** | ||
| 1357 | * \brief Computes a unique global facet id from a mesh | ||
| 1358 | * tetrahedron and local facet index. | ||
| 1359 | * \details If a facet is shared by two tetrahedra t1 and t2, | ||
| 1360 | * its global index determined from t1 and from t2 is the same. | ||
| 1361 | * \param[in] mesh the mesh | ||
| 1362 | * \param[in] t the index of the tetrahedron | ||
| 1363 | * \param[in] lf the local facet index (0,1,2 or 3) in tetrahedron \p t | ||
| 1364 | * \return an index that uniquely identifies the facet | ||
| 1365 | * in the tetrahedron | ||
| 1366 | */ | ||
| 1367 |
2/2✓ Branch 0 taken 35367 times.
✓ Branch 1 taken 42821 times.
|
78188 | static index_t global_facet_id( |
| 1368 | const Mesh* mesh, index_t t, index_t lf | ||
| 1369 | ) { | ||
| 1370 | index_t t2 = mesh->cells.tet_adjacent(t, lf); | ||
| 1371 |
2/2✓ Branch 0 taken 35367 times.
✓ Branch 1 taken 42821 times.
|
78188 | if(t2 != GEO::NO_CELL && t2 > t) { |
| 1372 | index_t lf2 = mesh->cells.find_tet_adjacent( | ||
| 1373 | t2, t | ||
| 1374 | ); | ||
| 1375 | geo_debug_assert(lf2 != GEO::NO_FACET); | ||
| 1376 | 35367 | return index_t(4 * t2 + lf2); | |
| 1377 | } | ||
| 1378 | return 4 * t + lf; | ||
| 1379 | } | ||
| 1380 | |||
| 1381 | private: | ||
| 1382 | GEO::vector<Triangle> triangles_; | ||
| 1383 | GEO::vector<Vertex> vertices_; | ||
| 1384 | index_t first_free_; | ||
| 1385 | bool v_to_t_dirty_; | ||
| 1386 | PointAllocator intersections_; | ||
| 1387 | bool symbolic_is_surface_; | ||
| 1388 | signed_index_t cell_id_; | ||
| 1389 | |||
| 1390 | static index_t plus1mod3_[3]; | ||
| 1391 | static index_t minus1mod3_[3]; | ||
| 1392 | |||
| 1393 | /** | ||
| 1394 | * \brief Gets the modulo-3 successor of an index. | ||
| 1395 | * \param[in] i the index | ||
| 1396 | * \return \p i plus 1 modulo 3 | ||
| 1397 | */ | ||
| 1398 | static index_t plus1mod3(index_t i) { | ||
| 1399 | geo_debug_assert(i < 3); | ||
| 1400 |
4/4✓ Branch 0 taken 374344 times.
✓ Branch 1 taken 187172 times.
✓ Branch 7 taken 18462339 times.
✓ Branch 8 taken 9054430 times.
|
57607515 | return plus1mod3_[i]; |
| 1401 | } | ||
| 1402 | |||
| 1403 | /** | ||
| 1404 | * \brief Gets the modulo-3 predecessor of an index. | ||
| 1405 | * \param[in] i the index | ||
| 1406 | * \return \p i minus 1 modulo 3 | ||
| 1407 | */ | ||
| 1408 | static index_t minus1mod3(index_t i) { | ||
| 1409 | geo_debug_assert(i < 3); | ||
| 1410 | 25249106 | return minus1mod3_[i]; | |
| 1411 | } | ||
| 1412 | }; | ||
| 1413 | } | ||
| 1414 | |||
| 1415 | #endif | ||
| 1416 |