1 // Hxt - Copyright (C) 2 // 2016 - 2020 UCLouvain 3 // 4 // See the LICENSE.txt file for license information. 5 // 6 // Contributor(s): 7 // Célestin Marot 8 9 #ifndef HXT_VERTICES_H 10 #define HXT_VERTICES_H 11 12 #include "hxt_mesh.h" 13 #include "hxt_bbox.h" 14 15 /** 16 * \file hxt_vertices.h 17 * Compute Hilbert/Moore indices of an array of vertices and sort them. 18 * \author Célestin Marot 19 */ 20 21 /** 22 * \struct HXTVertex 23 * \brief Contain coordinates and a padding that can be used as a temporary value. 24 * 25 * We can cast mesh->vertices.coord to a HXTVertex 26 * in order to use the 4th coordinate as a temporary value 27 * of different types. It is used for sorting and for the Delaunay partitions. 28 */ 29 typedef struct { 30 double coord[3]; 31 union { 32 uint64_t hilbertDist; 33 uint32_t index; 34 HXTStatus status; 35 } padding; 36 } HXTVertex; 37 38 39 /** 40 * \struct HXTNodeInfo 41 * \brief Simple structure with a vertex index, a Hilbert/Moore coordinate and a status 42 * 43 * Simple structure with a vertex index, a Hilbert/Moore coordinate and a status 44 * For example, when vertices cannot be moved, we sort that structure instead. 45 */ 46 typedef struct { 47 uint64_t hilbertDist; 48 uint32_t node; 49 HXTStatus status; // is the vertex inserted ? true, false or try_again 50 } HXTNodeInfo; 51 52 53 /** 54 * \brief Compute the Hilbert/Moore index of each vertex in `vertices` 55 * \param bbox: a bounding box that contain all the given vertices 56 * \param vertices: the vertices coordinates 57 * \param n: the number of vertices 58 * \param shift[3]: a value between 0 and 1 that commands how the Hilbert/Moore curve is deformed in each dimension. 59 * {0.5, 0.5, 0.5} is the undeformed Hilbert/Moore curve. 60 * 61 * \details Compute the Hilbert/Moore index of each vertex in its \ref HXTVertex.padding.hilbertDist structure member. 62 * A deformation of the Hilbert/Moore curve can be done with the shift parameter 63 */ 64 HXTStatus hxtMoore(HXTBbox* bbox, HXTVertex* vertices, const uint32_t n, const double shift[3]); 65 66 67 /** 68 * Sort all the vertices following their \ref HXTVertex.padding.hilbertDist structure member. 69 * 70 * \param vertices: pointer to an array of vertices 71 * \param n: number of vertices in the array 72 * \param nbits: the maximum number of bits set in the \ref HXTVertex.padding.hilbertDist structure member. 73 */ 74 HXTStatus hxtVerticesSort(HXTVertex* const vertices, const uint32_t n); 75 76 /** 77 * Same as hxtVerticesSort(), but sort \ref HXTNodeInfo following their hilbertDist structure member. 78 */ 79 HXTStatus hxtNodeInfoSort(HXTNodeInfo* const array, const uint32_t n); 80 81 /** 82 * Shuffle vertices given in an array of \ref HXTVertex in a pseudo-random fashion (always the same random sequence). 83 */ 84 HXTStatus hxtVerticesShuffle(HXTVertex* const vertices, const uint32_t n); 85 86 /** 87 * Shuffle vertices given in an array of \ref HXTNodeInfo in a pseudo-random fashion (always the same random sequence). 88 */ 89 HXTStatus hxtNodeInfoShuffle(HXTNodeInfo* const array, const uint32_t n); 90 91 #endif 92