Geogram Version 1.8.5
A programming library of geometric algorithms
Loading...
Searching...
No Matches
periodic_delaunay_3d.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#ifndef PERIODIC_DELAUNAY_TRIANGULATION_3D
41#define PERIODIC_DELAUNAY_TRIANGULATION_3D
42
49#include <stack>
50
51namespace GEO {
52
53 typedef Numeric::uint8 thread_index_t;
54 class PeriodicDelaunay3dThread;
55
56
66 class GEOGRAM_API PeriodicDelaunay3d : public Delaunay, public Periodic {
67 public:
68
77 std::stack<index_t> S;
78 vector<index_t> incident_tets_set;
79
84 incident_tets_set.resize(0);
85 }
86
92 incident_tets_set.push_back(t);
93 }
94
102 bool has_incident_tet(index_t t) const {
103 for(index_t i=0; i<incident_tets_set.size(); ++i) {
104 if(incident_tets_set[i] == t) {
105 return true;
106 }
107 }
108 return false;
109 }
110
111 vector<index_t>::const_iterator begin() const {
112 return incident_tets_set.begin();
113 }
114
116 return incident_tets_set.end();
117 }
118 };
119
125 PeriodicDelaunay3d(bool periodic, double period=1.0);
126
131 PeriodicDelaunay3d(const vec3& period);
132
138 index_t nb_vertices, const double* vertices
139 ) override;
140
149 void set_weights(const double* weights);
150
154 void compute();
155
165 convex_cell_exact_predicates_ = x;
166 }
167
176 vec3 vertex(index_t v) const {
177 if(!periodic_) {
178 geo_debug_assert(v < nb_vertices());
179 return vec3(vertices_ + 3*v);
180 }
181 index_t instance = v/nb_vertices_non_periodic_;
182 v = v%nb_vertices_non_periodic_;
183 vec3 result(vertices_ + 3*v);
184 result.x += double(translation[instance][0]) * period_.x;
185 result.y += double(translation[instance][1]) * period_.y;
186 result.z += double(translation[instance][2]) * period_.z;
187 return result;
188 }
189
196 double weight(index_t v) const {
197 if(weights_ == nullptr) {
198 return 0.0;
199 }
200 return periodic_ ? weights_[periodic_vertex_real(v)] : weights_[v] ;
201 }
202
206 index_t nearest_vertex(const double* p) const override;
207
211 void set_BRIO_levels(const vector<index_t>& levels) override;
212
222
234 GEO::index_t i,
235 ConvexCell& C,
237 ) const;
238
248 GEO::index_t i,
249 ConvexCell& C
250 ) const {
252 copy_Laguerre_cell_from_Delaunay(i,C,W);
253 }
254
263 bool has_empty_cells() const {
264 return has_empty_cells_;
265 }
266
275 void save_cells(const std::string& basename, bool clipped);
276
277 protected:
278
295 GEO::index_t i,
296 const GEO::vec3& Pi,
297 double wi,
298 double Pi_len2,
299 GEO::index_t t,
300 ConvexCell& C,
302 ) const;
303
304
311 index_t compress(bool shrink=true);
312
319 void update_v_to_cell() override;
320
324 void update_cicl() override;
325
331
348 index_t v,
349 ConvexCell& C,
350 bool use_instance[27],
351 bool& cell_is_on_boundary,
352 bool& cell_is_outside_cube,
354 );
355
363
368
374 PeriodicDelaunay3dThread* thread(index_t t) {
375 geo_debug_assert(t < threads_.size());
376 return reinterpret_cast<PeriodicDelaunay3dThread*>(
377 threads_[t].get()
378 );
379 }
380
386 return index_t(threads_.size());
387 }
388
389 private:
390 friend class PeriodicDelaunay3dThread;
391
392 bool periodic_;
393 vec3 period_;
394
395 const double* weights_;
396 vector<signed_index_t> cell_to_v_store_;
397 vector<signed_index_t> cell_to_cell_store_;
398 vector<index_t> cell_next_;
399 vector<thread_index_t> cell_thread_;
400 ThreadGroup threads_;
401 vector<index_t> reorder_;
402 vector<index_t> levels_;
403
407 bool debug_mode_;
408
412 bool verbose_debug_mode_;
413
417 bool benchmark_mode_;
418
419
424 vector<Numeric::uint32> vertex_instances_;
425
426 bool update_periodic_v_to_cell_;
427 vector<index_t> periodic_v_to_cell_rowptr_;
428 vector<index_t> periodic_v_to_cell_data_;
429
433 bool has_empty_cells_;
434
439 index_t nb_reallocations_;
440
444 bool convex_cell_exact_predicates_;
445 };
446
447
448}
449
450#endif
#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...
Abstract interface for Delaunay triangulation in Nd.
Definition delaunay.h:71
Multithreaded implementation of Delaunay in 3d with optional periodic boundary conditions.
PeriodicDelaunay3d(const vec3 &period)
Constructs a new PeriodicDelaunay3d.
PeriodicDelaunay3d(bool periodic, double period=1.0)
Constructs a new PeriodicDelaunay3d.
void check_volume()
Checks the volume of Laguerre cells.
void compute()
Computes the Delaunay triangulation.
void use_exact_predicates_for_convex_cell(bool x)
Use exact predicates in convex cell computations.
void handle_periodic_boundaries()
Duplicates the points with Voronoi cells that cross the boundary.
void save_cells(const std::string &basename, bool clipped)
Saves the cells in an Alias-Wavefront file.
void set_BRIO_levels(const vector< index_t > &levels) override
Specifies the bounds of each level to be used when hierarchic ordering is specified from outside.
void insert_vertices(index_t b, index_t e)
Insert vertices from reorder_[b] to reorder_[e-1].
index_t compress(bool shrink=true)
Removes unused tetrahedra.
double weight(index_t v) const
Gets a weight by index.
void update_v_to_cell() override
Stores for each vertex v a cell incident to v.
void update_cicl() override
Updates the circular incident cell lists.
void get_incident_tets(index_t v, IncidentTetrahedra &W) const
computes the set of tetrahedra that are incident to a vertex.
void copy_Laguerre_cell_from_Delaunay(GEO::index_t i, ConvexCell &C, IncidentTetrahedra &W) const
Copies a Laguerre cell from the triangulation.
index_t nb_threads() const
Gets the number of threads.
index_t nearest_vertex(const double *p) const override
Computes the nearest vertex from a query point.
void copy_Laguerre_cell_from_Delaunay(GEO::index_t i, ConvexCell &C) const
Copies a Laguerre cell from the triangulation.
index_t get_periodic_vertex_instances_to_create(index_t v, ConvexCell &C, bool use_instance[27], bool &cell_is_on_boundary, bool &cell_is_outside_cube, IncidentTetrahedra &W)
Computes the periodic vertex instances that should be generated.
vec3 vertex(index_t v) const
Gets a vertex by index.
bool has_empty_cells() const
Tests whether the Laguerre diagram has empty cells.
GEO::index_t copy_Laguerre_cell_facet_from_Delaunay(GEO::index_t i, const GEO::vec3 &Pi, double wi, double Pi_len2, GEO::index_t t, ConvexCell &C, IncidentTetrahedra &W) const
Copies a Laguerre cell facet from the triangulation.
void set_weights(const double *weights)
Sets the weights.
void set_vertices(index_t nb_vertices, const double *vertices) override
Sets the vertices of this Delaunay, and recomputes the cells.
PeriodicDelaunay3dThread * thread(index_t t)
Gets a thread by index.
Utilities for managing 3D periodic space.
Definition periodic.h:57
Vector with aligned memory allocation.
Definition memory.h:623
index_t size() const
Gets the number of elements.
Definition memory.h:662
Computes the intersection between a set of halfplanes using Bowyer-Watson algorithm.
Class to compute the intersection of a set of half-spaces in 3D.
Abstract interface for Delaunay.
Geometric functions in 2d and 3d.
uint8_t uint8
Definition numeric.h:90
Global Vorpaline namespace.
Definition algorithm.h:64
std::vector< Thread_var > ThreadGroup
Collection of Threads.
Definition process.h:157
geo_index_t index_t
The type for storing and manipulating indices.
Definition numeric.h:287
Manipulation of indices for 3D periodic space.
Function and classes for process manipulation.
Gathers some structures used by some algorithms, makes multithreading more efficient by avoiding dyna...
void add_incident_tet(index_t t)
Inserts a tet into the set of incident tets.
void clear_incident_tets()
Clears the set of incident tets.
bool has_incident_tet(index_t t) const
Tests whether a tet belongs to the set of incident tets.