1 /* 2 * Copyright (c) 2012-2014, Bruno Levy 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 * If you modify this software, you should include a notice giving the 30 * name of the person performing the modification, the date of modification, 31 * and the reason for such modification. 32 * 33 * Contact: Bruno Levy 34 * 35 * Bruno.Levy@inria.fr 36 * http://www.loria.fr/~levy 37 * 38 * ALICE Project 39 * LORIA, INRIA Lorraine, 40 * Campus Scientifique, BP 239 41 * 54506 VANDOEUVRE LES NANCY CEDEX 42 * FRANCE 43 * 44 */ 45 46 #ifndef GEOGRAM_DELAUNAY_DELAUNAY 47 #define GEOGRAM_DELAUNAY_DELAUNAY 48 49 #include <geogram/basic/common.h> 50 #include <geogram/basic/counted.h> 51 #include <geogram/basic/smart_pointer.h> 52 #include <geogram/basic/packed_arrays.h> 53 #include <geogram/basic/factory.h> 54 #include <stdexcept> 55 56 /** 57 * \file geogram/delaunay/delaunay.h 58 * \brief Abstract interface for Delaunay 59 */ 60 61 namespace GEO { 62 63 class Mesh; 64 65 /************************************************************************/ 66 67 /** 68 * \brief Abstract interface for Delaunay triangulation in Nd. 69 * \details 70 * Delaunay objects are created using method create() which 71 * uses the Factory service. New Delaunay triangulations can be 72 * implemented and registered to the factory using 73 * geo_register_Delaunay_creator(). 74 * \see DelaunayFactory 75 * \see geo_register_Delaunay_creator 76 */ 77 class GEOGRAM_API Delaunay : public Counted { 78 public: 79 /** 80 * \brief Invalid dimension exception 81 * \details This exception is thrown by the Delaunay derived 82 * constructors if the dimension in the constructor is not supported 83 * by the implementation 84 */ 85 struct InvalidDimension : std::logic_error { 86 /** 87 * \brief Creates a invalid dimension exception 88 * \param[in] dimension the specified dimension 89 * \param[in] name the name of the Delaunay implementation 90 * \param[in] expected the expected dimension 91 */ 92 InvalidDimension( 93 coord_index_t dimension, 94 const char* name, 95 const char* expected 96 ); 97 98 /** 99 * \brief Gets the string identifying the exception 100 */ 101 virtual const char* what() const GEO_NOEXCEPT; 102 }; 103 104 105 /** 106 * \brief Invalid input exception 107 * \details This exception is thrown by Delaunay implementations 108 * in constrained mode, when constraints self-intersect. 109 */ 110 struct InvalidInput : std::logic_error { 111 112 /** 113 * \brief InvalidInput constructor. 114 * \param[in] error_code_in an implementation-dependent error code 115 */ 116 InvalidInput(int error_code_in); 117 118 /** 119 * \brief InvalidInput copy constructor. 120 * \param[in] rhs a const reference to the InvalidInput to be copied 121 */ 122 InvalidInput(const InvalidInput& rhs); 123 124 virtual ~InvalidInput() GEO_NOEXCEPT; 125 126 /** 127 * \brief Gets the string identifying the exception 128 */ 129 virtual const char* what() const GEO_NOEXCEPT; 130 131 /** 132 * \brief An implementation-dependent error code. 133 */ 134 int error_code; 135 136 /** 137 * \brief The indices of the constrained facets that 138 * have an intersection (or that are duplicated). 139 */ 140 vector<index_t> invalid_facets; 141 }; 142 143 /** 144 * \brief Creates a Delaunay triangulation of the 145 * specified dimension. 146 * \param[in] dim dimension of the triangulation 147 * \param[in] name name of the implementation to use: 148 * - "tetgen" - Delaunay with the Tetgen library (dimension 3 only) 149 * - "BDEL" - Delaunay in 3D (dimension 3 only) 150 * - "BPOW" - Weighted regular 3D triangulation (dimension 4 only) 151 * - "NN" - Delaunay with NearestNeighborSearch (any dimension) 152 * - "default" - uses the command line argument "algo:delaunay" 153 * \retval nullptr if \p format is not a valid Delaunay algorithm name. 154 * \retval otherwise, a pointer to a Delaunay algorithm object. The 155 * returned pointer must be stored in an Delaunay_var that does 156 * automatic destruction: 157 * \code 158 * Delaunay_var handler = Delaunay::create(3, "default"); 159 * \endcode 160 */ 161 static Delaunay* create( 162 coord_index_t dim, const std::string& name = "default" 163 ); 164 165 166 /** 167 * \brief This function needs to be called once before 168 * using the Delaunay class. 169 * \details registers the factories. 170 */ 171 static void initialize(); 172 173 /** 174 * \brief Gets the dimension of this Delaunay. 175 * \return the dimension of this Delauna 176 */ dimension()177 coord_index_t dimension() const { 178 return dimension_; 179 } 180 181 /** 182 * \brief Gets the number of vertices in each cell 183 * \details Cell_size = dimension + 1 184 * \return the number of vertices in each cell 185 */ cell_size()186 index_t cell_size() const { 187 return cell_size_; 188 } 189 190 /** 191 * \brief Sets the vertices of this Delaunay, and recomputes the cells. 192 * \param[in] nb_vertices number of vertices 193 * \param[in] vertices a pointer to the coordinates of the vertices, as 194 * a contiguous array of doubles 195 */ 196 virtual void set_vertices( 197 index_t nb_vertices, const double* vertices 198 ); 199 200 201 /** 202 * \brief Specifies whether vertices should be reordered. 203 * \details Reordering is activated by default. Some special 204 * usages of Delaunay3d may require to deactivate it (for 205 * instance if vertices are already known to be ordered). 206 * \param[in] x if true, then vertices are reordered using 207 * BRIO-Hilbert ordering. This improves speed significantly 208 * (enabled by default). 209 */ set_reorder(bool x)210 void set_reorder(bool x) { 211 do_reorder_ = x; 212 } 213 214 215 /** 216 * \brief Specifies the bounds of each level to be used 217 * when hierarchic ordering is specified from outside. 218 * \details This function is used by some implementation 219 * when set_reorder(false) was called. 220 * \param[in] levels specifies the bounds of each level 221 * used by the hierarchical index. First level has 222 * indices between levels[0] ... levels[1]. 223 */ 224 virtual void set_BRIO_levels(const vector<index_t>& levels); 225 226 /** 227 * \brief Gets a pointer to the array of vertices. 228 * \return A const pointer to the array of vertices. 229 */ vertices_ptr()230 const double* vertices_ptr() const { 231 return vertices_; 232 } 233 234 /** 235 * \brief Gets a pointer to a vertex by its global index. 236 * \param[in] i global index of the vertex 237 * \return a pointer to vertex \p i 238 */ vertex_ptr(index_t i)239 const double* vertex_ptr(index_t i) const { 240 geo_debug_assert(i < nb_vertices()); 241 return vertices_ + vertex_stride_ * i; 242 } 243 244 /** 245 * \brief Gets the number of vertices. 246 * \return the number of vertices in this Delaunay 247 */ nb_vertices()248 index_t nb_vertices() const { 249 return nb_vertices_; 250 } 251 252 /** 253 * \brief Tests whether constraints are supported 254 * by this Delaunay. 255 * \retval true if constraints are supported 256 * \retval false otherwise 257 */ 258 virtual bool supports_constraints() const; 259 260 /** 261 * \brief Defines the constraints. 262 * \details The triangulation will be constrained 263 * to pass through the vertices and triangles of 264 * the mesh. This function should be called 265 * before set_vertices(). 266 * \param[in] mesh the definition of the constraints 267 * \pre constraints_supported() 268 */ set_constraints(const Mesh * mesh)269 virtual void set_constraints(const Mesh* mesh) { 270 geo_assert(supports_constraints()); 271 constraints_ = mesh; 272 } 273 274 /** 275 * \brief Specifies whether the mesh should be refined. 276 * \details If set, then the mesh elements are improved 277 * by inserting additional vertices in the mesh. 278 * It is not taken into account by all implementations. 279 * This function should be called before set_vertices(). 280 * \param[in] x true if the mesh should be refined, false 281 * otherwise. 282 */ set_refine(bool x)283 void set_refine(bool x) { 284 refine_ = x; 285 } 286 287 /** 288 * \brief Tests whether mesh refinement is selected. 289 * \retval true if mesh refinement is selected 290 * \retval false otherwise 291 * \see set_refine() 292 */ get_refine()293 bool get_refine() const { 294 return refine_; 295 } 296 297 /** 298 * \brief Specifies the desired quality for mesh elements 299 * when refinement is enabled (\see set_refine). 300 * \details 301 * Only taken into account after set_refine(true) is called. 302 * It is not taken into account by all implementations. 303 * This function should be called before set_vertices(). 304 * \param[in] qual typically in [1.0, 2.0], specifies 305 * the desired quality of mesh elements (1.0 means maximum 306 * quality, and generates a higher number of elements). 307 */ set_quality(double qual)308 void set_quality(double qual) { 309 quality_ = qual; 310 } 311 312 /** 313 * \brief Gets the constraints. 314 * \return the constraints or nullptr if no constraints 315 * were definied. 316 */ constraints()317 const Mesh* constraints() const { 318 return constraints_; 319 } 320 321 /** 322 * \brief Gets the number of cells. 323 * \return the number of cells in this Delaunay 324 */ nb_cells()325 index_t nb_cells() const { 326 return nb_cells_; 327 } 328 329 /** 330 * \brief Gets the number of finite cells. 331 * \pre this function can only be called if 332 * keep_finite is set 333 * \details Finite cells have indices 0..nb_finite_cells()-1 334 * and infinite cells have indices nb_finite_cells()..nb_cells()-1 335 * \see set_keeps_infinite(), keeps_infinite() 336 */ nb_finite_cells()337 index_t nb_finite_cells() const { 338 geo_debug_assert(keeps_infinite()); 339 return nb_finite_cells_; 340 } 341 342 /** 343 * \brief Gets a pointer to the cell-to-vertex incidence array. 344 * \return a const pointer to the cell-to-vertex incidence array 345 */ cell_to_v()346 const signed_index_t* cell_to_v() const { 347 return cell_to_v_; 348 } 349 350 /** 351 * \brief Gets a pointer to the cell-to-cell adjacency array. 352 * \return a const pointer to the cell-to-cell adjacency array 353 */ cell_to_cell()354 const signed_index_t* cell_to_cell() const { 355 return cell_to_cell_; 356 } 357 358 /** 359 * \brief Computes the nearest vertex from a query point. 360 * \param[in] p query point 361 * \return the index of the nearest vertex 362 */ 363 virtual index_t nearest_vertex(const double* p) const; 364 365 /** 366 * \brief Gets a vertex index by cell index and local vertex index. 367 * \param[in] c cell index 368 * \param[in] lv local vertex index in cell \p c 369 * \return the index of the lv-th vertex of cell c. 370 */ cell_vertex(index_t c,index_t lv)371 signed_index_t cell_vertex(index_t c, index_t lv) const { 372 geo_debug_assert(c < nb_cells()); 373 geo_debug_assert(lv < cell_size()); 374 return cell_to_v_[c * cell_v_stride_ + lv]; 375 } 376 377 /** 378 * \brief Gets an adjacent cell index by cell index and 379 * local facet index. 380 * \param[in] c cell index 381 * \param[in] lf local facet index 382 * \return the index of the cell adjacent to \p c accros 383 * facet \p lf if it exists, or -1 if on border 384 */ cell_adjacent(index_t c,index_t lf)385 signed_index_t cell_adjacent(index_t c, index_t lf) const { 386 geo_debug_assert(c < nb_cells()); 387 geo_debug_assert(lf < cell_size()); 388 return cell_to_cell_[c * cell_neigh_stride_ + lf]; 389 } 390 391 /** 392 * \brief Tests whether a cell is infinite. 393 * \retval true if cell \p c is infinite 394 * \retval false otherwise 395 * \see keeps_infinite(), set_keeps_infinite() 396 */ 397 bool cell_is_infinite(index_t c) const; 398 399 /** 400 * \brief Tests whether a cell is finite. 401 * \retval true if cell \p c is finite 402 * \retval false otherwise 403 * \see keeps_infinite(), set_keeps_infinite() 404 */ cell_is_finite(index_t c)405 bool cell_is_finite(index_t c) const { 406 return !cell_is_infinite(c); 407 } 408 409 /** 410 * \brief Retrieves a local vertex index from cell index 411 * and global vertex index. 412 * \param[in] c cell index 413 * \param[in] v global vertex index 414 * \return the local index of vertex \p v in cell \p c 415 * \pre cell \p c is incident to vertex \p v 416 */ index(index_t c,signed_index_t v)417 index_t index(index_t c, signed_index_t v) const { 418 geo_debug_assert(c < nb_cells()); 419 geo_debug_assert(v < (signed_index_t) nb_vertices()); 420 for(index_t iv = 0; iv < cell_size(); iv++) { 421 if(cell_vertex(c, iv) == v) { 422 return iv; 423 } 424 } 425 geo_assert_not_reached; 426 } 427 428 /** 429 * \brief Retrieves a local facet index from two adacent 430 * cell global indices. 431 * \param[in] c1 global index of first cell 432 * \param[in] c2 global index of second cell 433 * \return the local index of the face accros which 434 * \p c2 is adjacent to \p c1 435 * \pre cell \p c1 and cell \p c2 are adjacent 436 */ adjacent_index(index_t c1,index_t c2)437 index_t adjacent_index(index_t c1, index_t c2) const { 438 geo_debug_assert(c1 < nb_cells()); 439 geo_debug_assert(c2 < nb_cells()); 440 for(index_t f = 0; f < cell_size(); f++) { 441 if(cell_adjacent(c1, f) == signed_index_t(c2)) { 442 return f; 443 } 444 } 445 geo_assert_not_reached; 446 } 447 448 /** 449 * \brief Gets an incident cell index by a vertex index. 450 * \details Can only be used if set_stores_cicl(true) was called. 451 * \param[in] v a vertex index 452 * \return the index of a cell incident to vertex \p v 453 * \see stores_cicl(), set_store_cicl() 454 */ vertex_cell(index_t v)455 signed_index_t vertex_cell(index_t v) const { 456 geo_debug_assert(v < nb_vertices()); 457 geo_debug_assert(v < v_to_cell_.size()); 458 return v_to_cell_[v]; 459 } 460 461 462 /** 463 * \brief Traverses the list of cells incident to a vertex. 464 * \details Can only be used if set_stores_cicl(true) was called. 465 * \param[in] c cell index 466 * \param[in] lv local vertex index 467 * \return the index of the next cell around vertex \p c or -1 if 468 * \p c was the last one in the list 469 * \see stores_cicl(), set_store_cicl() 470 */ next_around_vertex(index_t c,index_t lv)471 signed_index_t next_around_vertex(index_t c, index_t lv) const { 472 geo_debug_assert(c < nb_cells()); 473 geo_debug_assert(lv < cell_size()); 474 return cicl_[cell_size() * c + lv]; 475 } 476 477 /** 478 * \brief Gets the one-ring neighbors of vertex v. 479 * \details Depending on store_neighbors_ internal flag, the 480 * neighbors are computed or copied from the previously computed 481 * list. 482 * \param[in] v vertex index 483 * \param[out] neighbors indices of the one-ring neighbors of 484 * vertex \p v 485 * \see stores_neighbors(), set_stores_neighbors() 486 */ get_neighbors(index_t v,vector<index_t> & neighbors)487 void get_neighbors( 488 index_t v, vector<index_t>& neighbors 489 ) const { 490 geo_debug_assert(v < nb_vertices()); 491 if(store_neighbors_) { 492 neighbors_.get_array(v, neighbors); 493 } else { 494 get_neighbors_internal(v, neighbors); 495 } 496 } 497 498 /** 499 * \brief Saves the histogram of vertex degree (can be 500 * visualized with gnuplot). 501 * \param[out] out an ASCII stream where to output the histogram. 502 */ 503 void save_histogram(std::ostream& out) const; 504 505 /** 506 * \brief Tests whether neighbors are stored. 507 * \details Vertices neighbors (i.e. Delaunay 1-skeleton) can be 508 * stored for faster access (used for instance by 509 * RestrictedVoronoiDiagram). 510 * \retval true if neighbors are stored. 511 * \retval false otherwise. 512 */ stores_neighbors()513 bool stores_neighbors() const { 514 return store_neighbors_; 515 } 516 517 /** 518 * \brief Specifies whether neighbors should be stored. 519 * \details Vertices neighbors (i.e. Delaunay 1-skeleton) can be 520 * stored for faster access (used for instance by 521 * RestrictedVoronoiDiagram). 522 * \param[in] x if true neighbors will be stored, else they will not 523 */ set_stores_neighbors(bool x)524 void set_stores_neighbors(bool x) { 525 store_neighbors_ = x; 526 if(store_neighbors_) { 527 set_stores_cicl(true); 528 } 529 } 530 531 /** 532 * \brief Tests whether incident tetrahedra lists 533 * are stored. 534 * \retval true if incident tetrahedra lists are stored. 535 * \retval false otherwise. 536 */ stores_cicl()537 bool stores_cicl() const { 538 return store_cicl_; 539 } 540 541 /** 542 * \brief Specifies whether incident tetrahedra lists 543 * should be stored. 544 * \param[in] x if true, incident trahedra lists are stored, 545 * else they are not. 546 */ set_stores_cicl(bool x)547 void set_stores_cicl(bool x) { 548 store_cicl_ = x; 549 } 550 551 552 /** 553 * \brief Tests whether infinite elements are kept. 554 * \retval true if infinite elements are kept 555 * \retval false otherwise 556 */ keeps_infinite()557 bool keeps_infinite() const { 558 return keep_infinite_; 559 } 560 561 /** 562 * \brief Sets whether infinite elements should be kept. 563 * \details Internally, Delaunay implementation uses an 564 * infinite vertex and infinite simplices indicent to it. 565 * By default they are discarded at the end of set_vertices(). 566 * \param[in] x true if infinite elements should be kept, 567 * false otherwise 568 */ set_keeps_infinite(bool x)569 void set_keeps_infinite(bool x) { 570 keep_infinite_ = x; 571 } 572 573 /** 574 * \brief Tests whether thread-safe mode is active. 575 * \return true if thread-safe mode is active, false otherwise. 576 */ thread_safe()577 bool thread_safe() const { 578 return neighbors_.thread_safe(); 579 } 580 581 /** 582 * \brief Specifies whether thread-safe mode should be used. 583 * \param[in] x if true then thread-safe mode will be used, else 584 * it will not. 585 */ set_thread_safe(bool x)586 void set_thread_safe(bool x) { 587 neighbors_.set_thread_safe(x); 588 } 589 590 /** 591 * \brief Sets the default number of stored neighbors. 592 * \details Storage of neighbors is optimized for a default 593 * neighborhood size. 594 * \see store_neighbors() 595 * \param[in] x default number of stored neighbors 596 */ set_default_nb_neighbors(index_t x)597 void set_default_nb_neighbors(index_t x) { 598 default_nb_neighbors_ = x; 599 } 600 601 /** 602 * \brief Gets the default number of stored neighbors. 603 * \details Storage of neighbors is optimized for a default 604 * neighborhood size. 605 * \see store_neighbors() 606 * \return The default number of stored neighbors. 607 */ default_nb_neighbors()608 index_t default_nb_neighbors() const { 609 return default_nb_neighbors_; 610 } 611 612 /** 613 * \brief Frees all memory used for neighbors storage. 614 */ clear_neighbors()615 void clear_neighbors() { 616 neighbors_.clear(); 617 } 618 619 /** 620 * \brief Specifies whether all internal regions should be kept. 621 * \details Only relevant in constrained mode. 622 * \param[in] x if true, all internal regions are kept, else only 623 * the outer most region is kept (default). 624 */ set_keep_regions(bool x)625 void set_keep_regions(bool x) { 626 keep_regions_ = x; 627 } 628 629 /** 630 * \brief Gets the region id associated with a tetrahedron. 631 * \details Only callable if set_keep_region(true) was called before 632 * set_vertices() in constrained mode. 633 * \param[in] t a tetrahedron index. 634 * \return the region associated with \p t. 635 */ 636 virtual index_t region(index_t t) const; 637 638 639 protected: 640 /** 641 * \brief Creates a new Delaunay triangulation 642 * \details This creates a new Delaunay triangulation for the 643 * specified \p dimension. Specific implementations of the Delaunay 644 * triangulation may not support the specified \p dimension and will 645 * throw a InvalidDimension exception. 646 * \param[in] dimension dimension of the triangulation 647 * \throw InvalidDimension This exception is thrown if the specified 648 * \p dimension is not supported by the Delaunay implementation. 649 * \note This function is never called directly, use create() 650 */ 651 Delaunay(coord_index_t dimension); 652 653 /** 654 * \brief Delaunay destructor. 655 */ 656 virtual ~Delaunay(); 657 658 /** 659 * \brief Internal implementation for get_neighbors (with vector). 660 * \param[in] v index of the Delaunay vertex 661 * \param[in,out] neighbors the computed neighbors of vertex \p v. 662 * Its size is used to determine the number of queried neighbors. 663 */ 664 virtual void get_neighbors_internal( 665 index_t v, vector<index_t>& neighbors 666 ) const; 667 668 /** 669 * \brief Sets the arrays that represent the combinatorics 670 * of this Delaunay. 671 * \param[in] nb_cells number of cells 672 * \param[in] cell_to_v the cell-to-vertex incidence array 673 * \param[in] cell_to_cell the cell-to-cell adjacency array 674 */ 675 virtual void set_arrays( 676 index_t nb_cells, 677 const signed_index_t* cell_to_v, const signed_index_t* cell_to_cell 678 ); 679 680 /** 681 * \brief Stores for each vertex v a cell incident to v. 682 */ 683 virtual void update_v_to_cell(); 684 685 /** 686 * \brief Updates the circular incident cell lists. 687 * \details Used by next_around_vertex(). 688 */ 689 virtual void update_cicl(); 690 691 /** 692 * \brief Computes the stored neighbor lists. 693 */ 694 virtual void update_neighbors(); 695 696 /** 697 * \brief Sets the circular incident edge list. 698 * \param[in] c1 index of a cell 699 * \param[in] lv local index of a vertex of \p c1 700 * \param[in] c2 index of the next cell around \p c1%'s vertex \p lv 701 */ set_next_around_vertex(index_t c1,index_t lv,index_t c2)702 void set_next_around_vertex( 703 index_t c1, index_t lv, index_t c2 704 ) { 705 geo_debug_assert(c1 < nb_cells()); 706 geo_debug_assert(c2 < nb_cells()); 707 geo_debug_assert(lv < cell_size()); 708 cicl_[cell_size() * c1 + lv] = signed_index_t(c2); 709 } 710 711 public: 712 /** 713 * \brief Stores the neighbors of a vertex. 714 * \details Used internally for parallel 715 * computation of the neighborhoods. 716 * \param[in] i index of the vertex for which the 717 * neighbors should be stored. 718 */ 719 virtual void store_neighbors_CB(index_t i); 720 721 protected: 722 /** 723 * \brief Sets the dimension of this Delaunay. 724 * \details Updates all the parameters related with 725 * the dimension. This includes vertex_stride (number 726 * of doubles between two consecutive vertices), 727 * cell size (number of vertices in a cell), 728 * cell_v_stride (number of integers between two 729 * consecutive cell vertex arrays), 730 * cell_neigh_stride (number of integers 731 * between two consecutive cell adjacency arrays). 732 * \param[in] dim the dimension 733 */ set_dimension(coord_index_t dim)734 void set_dimension(coord_index_t dim) { 735 dimension_ = dim; 736 vertex_stride_ = dim; 737 cell_size_ = index_t(dim) + 1; 738 cell_v_stride_ = cell_size_; 739 cell_neigh_stride_ = cell_size_; 740 } 741 742 coord_index_t dimension_; 743 index_t vertex_stride_; 744 index_t cell_size_; 745 index_t cell_v_stride_; 746 index_t cell_neigh_stride_; 747 748 const double* vertices_; 749 index_t nb_vertices_; 750 index_t nb_cells_; 751 const signed_index_t* cell_to_v_; 752 const signed_index_t* cell_to_cell_; 753 vector<signed_index_t> v_to_cell_; 754 vector<signed_index_t> cicl_; 755 bool is_locked_; 756 PackedArrays neighbors_; 757 bool store_neighbors_; 758 index_t default_nb_neighbors_; 759 760 /** 761 * \brief If true, uses BRIO reordering 762 * (in some implementations) 763 */ 764 bool do_reorder_; 765 766 const Mesh* constraints_; 767 768 bool refine_; 769 double quality_; 770 771 /** 772 * \brief It true, circular incident tet 773 * lists are stored. 774 */ 775 bool store_cicl_; 776 777 /** 778 * \brief If true, infinite vertex and 779 * infinite simplices are kept. 780 */ 781 bool keep_infinite_; 782 783 /** 784 * \brief If keep_infinite_ is true, then 785 * finite cells are 0..nb_finite_cells_-1 786 * and infinite cells are 787 * nb_finite_cells_ ... nb_cells_ 788 */ 789 index_t nb_finite_cells_; 790 791 bool keep_regions_; 792 }; 793 794 /** 795 * \brief Smart pointer that refers to a Delaunay object 796 * \relates Delaunay 797 */ 798 typedef SmartPointer<Delaunay> Delaunay_var; 799 800 /** 801 * \brief Delaunay Factory 802 * \details 803 * This Factory is used to create Delaunay objects. 804 * It can also be used to register new Delaunay 805 * implementations. 806 * \see geo_register_Delaunay_creator 807 * \see Factory 808 * \relates Delaunay 809 */ 810 typedef Factory1<Delaunay, coord_index_t> DelaunayFactory; 811 812 /** 813 * \brief Helper macro to register a Delaunay implementation 814 * \see DelaunayFactory 815 * \relates Delaunay 816 */ 817 #define geo_register_Delaunay_creator(type, name) \ 818 geo_register_creator(GEO::DelaunayFactory, type, name) 819 } 820 821 #endif 822 823