| 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 | |||
| 41 | #ifndef GEOGRAM_DELAUNAY_CAVITY | ||
| 42 | #define GEOGRAM_DELAUNAY_CAVITY | ||
| 43 | |||
| 44 | #include <geogram/basic/common.h> | ||
| 45 | #include <geogram/basic/memory.h> | ||
| 46 | #include <geogram/basic/numeric.h> | ||
| 47 | #include <string.h> | ||
| 48 | |||
| 49 | // Uncomment to display histogram of | ||
| 50 | // number of collisions per set() and | ||
| 51 | // get() operations. | ||
| 52 | // There is probably room for improvement | ||
| 53 | // in my hash function, but for large | ||
| 54 | // pointsets, more then 99% of queries are | ||
| 55 | // in the first slot (seems to be good enough). | ||
| 56 | //#define CAVITY_WITH_STATS | ||
| 57 | #ifdef CAVITY_WITH_STATS | ||
| 58 | #define CAVITY_STATS(x) x | ||
| 59 | #else | ||
| 60 | #define CAVITY_STATS(x) | ||
| 61 | #endif | ||
| 62 | |||
| 63 | namespace GEO { | ||
| 64 | |||
| 65 | /** | ||
| 66 | * \brief Represents the set of tetrahedra on the boundary | ||
| 67 | * of the cavity in a 3D Delaunay triangulation. | ||
| 68 | */ | ||
| 69 | class Cavity { | ||
| 70 | |||
| 71 | public: | ||
| 72 | |||
| 73 | /** | ||
| 74 | * \brief Type used for local indices. | ||
| 75 | */ | ||
| 76 | typedef Numeric::uint8 local_index_t; | ||
| 77 | |||
| 78 | /** | ||
| 79 | * \brief Cavity constructor. | ||
| 80 | */ | ||
| 81 | 22 | Cavity() { | |
| 82 | clear(); | ||
| 83 | #ifdef CAVITY_WITH_STATS | ||
| 84 | Memory::clear(stats_set_, sizeof(stats_set_)); | ||
| 85 | Memory::clear(stats_get_, sizeof(stats_get_)); | ||
| 86 | #endif | ||
| 87 | } | ||
| 88 | |||
| 89 | /** | ||
| 90 | * \brief Clears this cavity. | ||
| 91 | */ | ||
| 92 | void clear() { | ||
| 93 | 4281 | nb_f_ = 0; | |
| 94 | 4281 | OK_ = true; | |
| 95 |
3/5✓ Branch 0 taken 221 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
|
4281 | ::memset(h2t_, END_OF_LIST, sizeof(h2t_)); |
| 96 | } | ||
| 97 | |||
| 98 | ~Cavity() { | ||
| 99 | #ifdef CAVITY_WITH_STATS | ||
| 100 | for(index_t i=0; i<MAX_H; ++i) { | ||
| 101 | std::cerr << i << ": get=" << stats_get_[i] | ||
| 102 | << " set=" << stats_set_[i] << std::endl; | ||
| 103 | } | ||
| 104 | #endif | ||
| 105 |
2/4✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
|
2 | } |
| 106 | |||
| 107 | /** | ||
| 108 | * \brief Tests whether this Cavity is valid. | ||
| 109 | * \retval true if this Cavity is valid. | ||
| 110 | * \retval false otherwise. A Cavity is not valid | ||
| 111 | * when there was overflow. | ||
| 112 | */ | ||
| 113 | bool OK() const { | ||
| 114 |
2/2✓ Branch 0 taken 4250 times.
✓ Branch 1 taken 9 times.
|
4259 | return OK_; |
| 115 | } | ||
| 116 | |||
| 117 | /** | ||
| 118 | * \brief Inserts a new boundary facet in the structure. | ||
| 119 | * \param[in] tglobal global tetrahedron index | ||
| 120 | * \param[in] boundary_f index of the facet that is on the boundary | ||
| 121 | * \param[in] v0 , v1 , v2 the three vertices of the facet that | ||
| 122 | * is on the boundary | ||
| 123 | */ | ||
| 124 | 107314 | void new_facet( | |
| 125 | index_t tglobal, index_t boundary_f, | ||
| 126 | index_t v0, index_t v1, index_t v2 | ||
| 127 | ) { | ||
| 128 |
2/2✓ Branch 0 taken 106975 times.
✓ Branch 1 taken 339 times.
|
107314 | if(!OK_) { |
| 129 | return; | ||
| 130 | } | ||
| 131 | |||
| 132 | geo_debug_assert(v0 != v1); | ||
| 133 | geo_debug_assert(v1 != v2); | ||
| 134 | geo_debug_assert(v2 != v0); | ||
| 135 | |||
| 136 | 106975 | local_index_t new_t = local_index_t(nb_f_); | |
| 137 | |||
| 138 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 106966 times.
|
106975 | if(nb_f_ == MAX_F) { |
| 139 | 9 | OK_ = false; | |
| 140 | 9 | return; | |
| 141 | } | ||
| 142 | |||
| 143 | set_vv2t(v0, v1, new_t); | ||
| 144 | set_vv2t(v1, v2, new_t); | ||
| 145 | set_vv2t(v2, v0, new_t); | ||
| 146 | |||
| 147 |
1/2✓ Branch 0 taken 106966 times.
✗ Branch 1 not taken.
|
106966 | if(!OK_) { |
| 148 | return; | ||
| 149 | } | ||
| 150 | |||
| 151 | 106966 | ++nb_f_; | |
| 152 | 106966 | tglobal_[new_t] = tglobal; | |
| 153 | 106966 | boundary_f_[new_t] = boundary_f; | |
| 154 | 106966 | f2v_[new_t][0] = v0; | |
| 155 | 106966 | f2v_[new_t][1] = v1; | |
| 156 | 106966 | f2v_[new_t][2] = v2; | |
| 157 | } | ||
| 158 | |||
| 159 | /** | ||
| 160 | * \brief Gets the number of facets. | ||
| 161 | * \return the number of facets. | ||
| 162 | */ | ||
| 163 | index_t nb_facets() const { | ||
| 164 |
4/4✓ Branch 0 taken 105814 times.
✓ Branch 1 taken 4250 times.
✓ Branch 2 taken 105814 times.
✓ Branch 3 taken 4250 times.
|
220128 | return nb_f_; |
| 165 | } | ||
| 166 | |||
| 167 | /** | ||
| 168 | * \brief Gets the tetrahedron associated with a facet. | ||
| 169 | * \param[in] f the facet | ||
| 170 | * \return the tetrahedron associated with \p f. | ||
| 171 | */ | ||
| 172 | index_t facet_tet(index_t f) const { | ||
| 173 | geo_debug_assert(f < nb_facets()); | ||
| 174 | 105814 | return tglobal_[f]; | |
| 175 | } | ||
| 176 | |||
| 177 | /** | ||
| 178 | * \brief Sets the tetrahedron associated with a facet. | ||
| 179 | * \param[in] f the facet. | ||
| 180 | * \param[in] t the tetrahedron to be associated with \p f. | ||
| 181 | */ | ||
| 182 | void set_facet_tet(index_t f, index_t t) { | ||
| 183 | geo_debug_assert(f < nb_facets()); | ||
| 184 | 105814 | tglobal_[f] = t; | |
| 185 | } | ||
| 186 | |||
| 187 | /** | ||
| 188 | * \brief Gets the local tetrahedron facet that corresponds | ||
| 189 | * to a facet. | ||
| 190 | * \param[in] f the facet. | ||
| 191 | * \return the local index of the tetrahedron facet associated | ||
| 192 | * with \p f, in 0..3 | ||
| 193 | */ | ||
| 194 | index_t facet_facet(index_t f) const { | ||
| 195 | geo_debug_assert(f < nb_facets()); | ||
| 196 | 105814 | return boundary_f_[f]; | |
| 197 | } | ||
| 198 | |||
| 199 | /** | ||
| 200 | * \brief Gets the vertex of a facet. | ||
| 201 | * \param[in] f a facet. | ||
| 202 | * \param[in] lv local index of the vertex, in 0..2. | ||
| 203 | * \return the global vertex index. | ||
| 204 | */ | ||
| 205 | index_t facet_vertex(index_t f, index_t lv) const { | ||
| 206 | geo_debug_assert(f < nb_facets()); | ||
| 207 | geo_debug_assert(lv < 3); | ||
| 208 | 105814 | return f2v_[f][lv]; | |
| 209 | } | ||
| 210 | |||
| 211 | /** | ||
| 212 | * \brief Gets the neighbors of a facet. | ||
| 213 | * \param[in] f a facet | ||
| 214 | * \param[out] t0 , t1 , t2 the global tetrahedron | ||
| 215 | * indices that correspond to the neighbors of \p f. | ||
| 216 | */ | ||
| 217 | 105814 | void get_facet_neighbor_tets( | |
| 218 | index_t f, index_t& t0, index_t& t1, index_t& t2 | ||
| 219 | ) const { | ||
| 220 | 105814 | index_t v0 = f2v_[f][0]; | |
| 221 | 105814 | index_t v1 = f2v_[f][1]; | |
| 222 | 105814 | index_t v2 = f2v_[f][2]; | |
| 223 | 105814 | t0 = tglobal_[get_vv2t(v2,v1)]; | |
| 224 | 105814 | t1 = tglobal_[get_vv2t(v0,v2)]; | |
| 225 | 105814 | t2 = tglobal_[get_vv2t(v1,v0)]; | |
| 226 | 105814 | } | |
| 227 | |||
| 228 | private: | ||
| 229 | static constexpr index_t MAX_H = 1033; | ||
| 230 | static constexpr local_index_t END_OF_LIST = 255; | ||
| 231 | static constexpr index_t MAX_F = 128; | ||
| 232 | |||
| 233 | /** | ||
| 234 | * \brief Computes the hash code associated with an oriented | ||
| 235 | * edge. | ||
| 236 | * \param[in] v1 , v2 the global indices of the two vertices | ||
| 237 | * \return the hash code, in 0 .. MAX_H -1 | ||
| 238 | */ | ||
| 239 | index_t hash(index_t v1, index_t v2) const { | ||
| 240 | return ( | ||
| 241 | 638340 | ((index_t(v1+1) * 73856093) ^ | |
| 242 | (index_t(v2+1) * 83492791)) % MAX_H | ||
| 243 | 320898 | ); | |
| 244 | } | ||
| 245 | |||
| 246 | /** | ||
| 247 | * \brief Sets the local facet associated with an oriented | ||
| 248 | * edge. | ||
| 249 | * \param[in] v1 , v2 the global indices of the two vertices | ||
| 250 | * \param[in] f the local face index. | ||
| 251 | */ | ||
| 252 | void set_vv2t( | ||
| 253 | index_t v1, index_t v2, local_index_t f | ||
| 254 | ) { | ||
| 255 | CAVITY_STATS(index_t cnt = 0;) | ||
| 256 | index_t h = hash(v1,v2); | ||
| 257 | index_t cur = h; | ||
| 258 | do { | ||
| 259 |
6/6✓ Branch 0 taken 106966 times.
✓ Branch 1 taken 5699 times.
✓ Branch 2 taken 106966 times.
✓ Branch 3 taken 5775 times.
✓ Branch 4 taken 106966 times.
✓ Branch 5 taken 5842 times.
|
338214 | if(h2t_[cur] == END_OF_LIST) { |
| 260 | 320898 | h2t_[cur] = f; | |
| 261 | #ifdef GARGANTUA | ||
| 262 | h2v_[cur][0] = v1; | ||
| 263 | h2v_[cur][1] = v2; | ||
| 264 | #else | ||
| 265 | 320898 | h2v_[cur] = (Numeric::uint64(v1+1) << 32) | | |
| 266 | 320898 | Numeric::uint64(v2+1); | |
| 267 | #endif | ||
| 268 | CAVITY_STATS(++stats_set_[cnt];) | ||
| 269 | 320898 | return; | |
| 270 | } | ||
| 271 | 17316 | cur = (cur+1)%MAX_H; | |
| 272 | CAVITY_STATS(++cnt;) | ||
| 273 |
3/6✓ Branch 0 taken 5699 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 5775 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5842 times.
✗ Branch 5 not taken.
|
17316 | } while(cur != h); |
| 274 | ✗ | OK_ = false; | |
| 275 | } | ||
| 276 | |||
| 277 | /** | ||
| 278 | * \brief gets the local facet associated with an oriented | ||
| 279 | * edge. | ||
| 280 | * \param[in] v1 , v2 the global indices of the two vertices | ||
| 281 | * \return the local facet index. | ||
| 282 | */ | ||
| 283 | 317442 | local_index_t get_vv2t(index_t v1, index_t v2) const { | |
| 284 | #ifndef GARGANTUA | ||
| 285 | 317442 | Numeric::uint64 K = (Numeric::uint64(v1+1) << 32) | | |
| 286 | 317442 | Numeric::uint64(v2+1); | |
| 287 | #endif | ||
| 288 | CAVITY_STATS(index_t cnt = 0;) | ||
| 289 | index_t h = hash(v1,v2); | ||
| 290 | index_t cur = h; | ||
| 291 | do { | ||
| 292 | #ifdef GARGANTUA | ||
| 293 | if((h2v_[cur][0] == v1) && (h2v_[cur][1] == v2)) { | ||
| 294 | #else | ||
| 295 |
2/2✓ Branch 0 taken 317442 times.
✓ Branch 1 taken 16298 times.
|
333740 | if(h2v_[cur] == K) { |
| 296 | #endif | ||
| 297 | CAVITY_STATS(++stats_get_[cnt];) | ||
| 298 | 317442 | return h2t_[cur]; | |
| 299 | } | ||
| 300 | 16298 | cur = (cur+1)%MAX_H; | |
| 301 | CAVITY_STATS(++cnt;) | ||
| 302 |
1/2✓ Branch 0 taken 16298 times.
✗ Branch 1 not taken.
|
16298 | } while(cur != h); |
| 303 | ✗ | geo_assert_not_reached; | |
| 304 | } | ||
| 305 | |||
| 306 | /** \brief Hash index to local facet id. */ | ||
| 307 | local_index_t h2t_[MAX_H]; | ||
| 308 | |||
| 309 | /** \brief Hash index to global vertex id. */ | ||
| 310 | #ifdef GARGANTUA | ||
| 311 | index_t h2v_[MAX_H][2]; | ||
| 312 | #else | ||
| 313 | Numeric::uint64 h2v_[MAX_H]; | ||
| 314 | #endif | ||
| 315 | |||
| 316 | /** \brief Number of facets. */ | ||
| 317 | index_t nb_f_; | ||
| 318 | |||
| 319 | /** \brief Local facet index to tetrahedra index. */ | ||
| 320 | index_t tglobal_[MAX_F]; | ||
| 321 | |||
| 322 | /** \brief Local facet index to facet on border index. */ | ||
| 323 | index_t boundary_f_[MAX_F]; | ||
| 324 | |||
| 325 | /** \brief Local facet index to three global vertex indices. */ | ||
| 326 | index_t f2v_[MAX_F][3]; | ||
| 327 | |||
| 328 | |||
| 329 | /** | ||
| 330 | * \brief True if the structure is correct, false | ||
| 331 | * otherwise, if capacity was exceeded. | ||
| 332 | */ | ||
| 333 | bool OK_; | ||
| 334 | |||
| 335 | CAVITY_STATS(mutable index_t stats_set_[MAX_H];) | ||
| 336 | CAVITY_STATS(mutable index_t stats_get_[MAX_H];) | ||
| 337 | }; | ||
| 338 | |||
| 339 | } | ||
| 340 | |||
| 341 | #endif | ||
| 342 |