Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
cavity.h
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
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
63namespace GEO {
64
69 class Cavity {
70
71 public:
72
77
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
92 void clear() {
93 nb_f_ = 0;
94 OK_ = true;
95 ::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] << " set=" << stats_set_[i] << std::endl;
102 }
103#endif
104 }
105
112 bool OK() const {
113 return OK_;
114 }
115
124 index_t tglobal, index_t boundary_f,
126 ) {
127 if(!OK_) {
128 return;
129 }
130
131 geo_debug_assert(v0 != v1);
132 geo_debug_assert(v1 != v2);
133 geo_debug_assert(v2 != v0);
134
135 local_index_t new_t = local_index_t(nb_f_);
136
137 if(nb_f_ == MAX_F) {
138 OK_ = false;
139 return;
140 }
141
142 set_vv2t(v0, v1, new_t);
143 set_vv2t(v1, v2, new_t);
144 set_vv2t(v2, v0, new_t);
145
146 if(!OK_) {
147 return;
148 }
149
150 ++nb_f_;
151 tglobal_[new_t] = tglobal;
152 boundary_f_[new_t] = boundary_f;
153 f2v_[new_t][0] = v0;
154 f2v_[new_t][1] = v1;
155 f2v_[new_t][2] = v2;
156 }
157
163 return nb_f_;
164 }
165
173 return tglobal_[f];
174 }
175
183 tglobal_[f] = t;
184 }
185
195 return boundary_f_[f];
196 }
197
206 geo_debug_assert(lv < 3);
207 return f2v_[f][lv];
208 }
209
217 index_t f, index_t& t0, index_t& t1, index_t& t2
218 ) const {
219 signed_index_t v0 = f2v_[f][0];
220 signed_index_t v1 = f2v_[f][1];
221 signed_index_t v2 = f2v_[f][2];
222 t0 = tglobal_[get_vv2t(v2,v1)];
223 t1 = tglobal_[get_vv2t(v0,v2)];
224 t2 = tglobal_[get_vv2t(v1,v0)];
225 }
226
227 private:
228 static const index_t MAX_H = 1024;
229 static const local_index_t END_OF_LIST = 255;
230 static const index_t MAX_F = 128;
231
238 index_t hash(signed_index_t v1, signed_index_t v2) const {
239 return ((index_t(v1+1) ^ (419*index_t(v2+1))) % MAX_H);
240 }
241
248 void set_vv2t(
250 ) {
251 CAVITY_STATS(index_t cnt = 0;)
252 index_t h = hash(v1,v2);
253 index_t cur = h;
254 do {
255 if(h2t_[cur] == END_OF_LIST) {
256 h2t_[cur] = f;
257#ifdef GARGANTUA
258 h2v_[cur][0] = v1;
259 h2v_[cur][1] = v2;
260#else
261 h2v_[cur] = (Numeric::uint64(v1+1) << 32) | Numeric::uint64(v2+1);
262#endif
263 CAVITY_STATS(++stats_set_[cnt];)
264 return;
265 }
266 cur = (cur+1)%MAX_H;
267 CAVITY_STATS(++cnt;)
268 } while(cur != h);
269 OK_ = false;
270 }
271
278 local_index_t get_vv2t(signed_index_t v1, signed_index_t v2) const {
279#ifndef GARGANTUA
280 Numeric::uint64 K = (Numeric::uint64(v1+1) << 32) | Numeric::uint64(v2+1);
281#endif
282 CAVITY_STATS(index_t cnt = 0;)
283 index_t h = hash(v1,v2);
284 index_t cur = h;
285 do {
286#ifdef GARGANTUA
287 if((h2v_[cur][0] == v1) && (h2v_[cur][1] == v2)) {
288#else
289 if(h2v_[cur] == K) {
290#endif
291 CAVITY_STATS(++stats_get_[cnt];)
292 return h2t_[cur];
293 }
294 cur = (cur+1)%MAX_H;
295 CAVITY_STATS(++cnt;)
296 } while(cur != h);
298 }
299
301 local_index_t h2t_[MAX_H];
302
304#ifdef GARGANTUA
305 signed_index_t h2v_[MAX_H][2];
306#else
307 Numeric::uint64 h2v_[MAX_H];
308#endif
309
311 index_t nb_f_;
312
314 index_t tglobal_[MAX_F];
315
317 index_t boundary_f_[MAX_F];
318
320 signed_index_t f2v_[MAX_F][3];
321
322
327 bool OK_;
328
329 CAVITY_STATS(mutable index_t stats_set_[MAX_H];)
330 CAVITY_STATS(mutable index_t stats_get_[MAX_H];)
331 };
332
333}
334
335#endif
336
#define geo_assert_not_reached
Sets a non reachable point in the program.
Definition assert.h:177
#define geo_debug_assert(x)
Verifies that a condition is met.
Definition assert.h:195
Common include file, providing basic definitions. Should be included before anything else by all head...
Represents the set of tetrahedra on the boundary of the cavity in a 3D Delaunay triangulation.
Definition cavity.h:69
Cavity()
Cavity constructor.
Definition cavity.h:81
index_t nb_facets() const
Gets the number of facets.
Definition cavity.h:162
Numeric::uint8 local_index_t
Type used for local indices.
Definition cavity.h:76
bool OK() const
Tests whether this Cavity is valid.
Definition cavity.h:112
void clear()
Clears this cavity.
Definition cavity.h:92
signed_index_t facet_vertex(index_t f, index_t lv) const
Gets the vertex of a facet.
Definition cavity.h:204
index_t facet_facet(index_t f) const
Gets the local tetrahedron facet that corresponds to a facet.
Definition cavity.h:193
void set_facet_tet(index_t f, index_t t)
Sets the tetrahedron associated with a facet.
Definition cavity.h:181
void get_facet_neighbor_tets(index_t f, index_t &t0, index_t &t1, index_t &t2) const
Gets the neighbors of a facet.
Definition cavity.h:216
void new_facet(index_t tglobal, index_t boundary_f, signed_index_t v0, signed_index_t v1, signed_index_t v2)
Inserts a new boundary facet in the structure.
Definition cavity.h:123
index_t facet_tet(index_t f) const
Gets the tetrahedron associated with a facet.
Definition cavity.h:171
Types and functions for memory manipulation.
void clear(void *addr, size_t size)
Clears a memory block.
Definition memory.h:104
uint8_t uint8
Definition numeric.h:90
uint64_t uint64
Definition numeric.h:99
Global Vorpaline namespace.
Definition algorithm.h:64
geo_signed_index_t signed_index_t
The type for storing and manipulating indices differences.
Definition numeric.h:301
geo_index_t index_t
The type for storing and manipulating indices.
Definition numeric.h:287
Types and functions for numbers manipulation.
Functions for string manipulation.