1 /* ***************************************************************** 2 MESQUITE -- The Mesh Quality Improvement Toolkit 3 4 Copyright 2004 Lawrence Livermore National Laboratory. Under 5 the terms of Contract B545069 with the University of Wisconsin -- 6 Madison, Lawrence Livermore National Laboratory retains certain 7 rights in this software. 8 9 This library is free software; you can redistribute it and/or 10 modify it under the terms of the GNU Lesser General Public 11 License as published by the Free Software Foundation; either 12 version 2.1 of the License, or (at your option) any later version. 13 14 This library is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 Lesser General Public License for more details. 18 19 You should have received a copy of the GNU Lesser General Public License 20 (lgpl.txt) along with this library; if not, write to the Free Software 21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 22 23 kraftche@cae.wisc.edu 24 25 ***************************************************************** */ 26 27 #ifndef MESQUITE_TOPOLOGY_INFO_HPP 28 #define MESQUITE_TOPOLOGY_INFO_HPP 29 30 #include "Mesquite.hpp" 31 #include "Sample.hpp" 32 #include <string.h> 33 34 namespace MBMesquite 35 { 36 37 class MsqError; 38 39 /** \brief Information about different element topologies */ 40 class MESQUITE_EXPORT TopologyInfo 41 { 42 public: 43 name(EntityTopology topo)44 static const char* name( EntityTopology topo ) 45 { return topo > MIXED ? 0 : instance.longNames[topo]; } short_name(EntityTopology topo)46 static const char* short_name( EntityTopology topo ) 47 { return topo > MIXED ? 0 : instance.shortNames[topo]; } 48 49 /** \brief Dimension of element topology */ dimension(EntityTopology topo)50 static unsigned dimension( EntityTopology topo ) 51 { return topo >= MIXED ? 0: instance.dimMap[topo]; } 52 53 /** \brief Number of adjacent entities of a specified dimension 54 * 55 * For a given element topology, get the number of adjacent entities 56 * of the specified dimension. 57 */ adjacent(EntityTopology topo,unsigned dimension)58 static unsigned adjacent( EntityTopology topo, unsigned dimension ) 59 { return (topo >= MIXED) ? 0 : instance.adjMap[topo][dimension]; } 60 61 /** \brief Get number of sides a given topology type has 62 * 63 * Get the number of sides for a given element topology. Returns 64 * the number of adjacent entities of one less dimension. The number 65 * of faces for a volume element and the number of edges for a face 66 * element 67 */ sides(EntityTopology topo)68 static unsigned sides( EntityTopology topo ) 69 { return (topo >= MIXED || instance.dimMap[topo] < 1) ? 0 : 70 instance.adjMap[topo][instance.dimMap[topo]-1]; } 71 72 /** \brief Get the number of defining vertices for a given element topology 73 * 74 * Get the number of corner vertices necessary to define an element 75 * of the specified topology. This is the number of nodes a linear 76 * element of the specified topology will have. 77 */ corners(EntityTopology topo)78 static unsigned corners( EntityTopology topo ) 79 { return adjacent(topo, 0); } 80 81 /** \brief Get the number of edges in a given topology */ edges(EntityTopology topo)82 static unsigned edges( EntityTopology topo ) 83 { return adjacent(topo, 1); } 84 85 /** \brief Get the number of faces in a given topology */ faces(EntityTopology topo)86 static unsigned faces( EntityTopology topo ) 87 { return adjacent(topo, 2 ); } 88 89 /** \brief Check which mid-nodes a higher-order element has. 90 * 91 * Assuming at most one mid-node per sub-entity per dimension 92 * (i.e. at most one mid-node per edge, at most one mid-node per face, etc.) 93 * determine which mid-nodes are present given the topology 94 * and total number of nodes. 95 */ 96 static void higher_order( EntityTopology topo, unsigned num_nodes, 97 bool& midedge, bool& midface, bool& midvol, 98 MsqError &err ); 99 100 /** \brief Check which mid-nodes a higher-order element has. 101 * 102 * Assuming at most one mid-node per sub-entity per dimension 103 * (i.e. at most one mid-node per edge, at most one mid-node per face, etc.) 104 * determine which mid-nodes are present given the topology 105 * and total number of nodes. This function is similar to the 106 * previous one, except that that it returns a set of bits, one per 107 * side dimension, rather than separate bool values. If the bit at position 108 * one (the second least significant bit) has a value of one, then the 109 * element has mid-edge nodes. If the bit at position two (the third to 110 * least signficiant bit) has a value of one then the element has mid-face 111 * nodes. 112 *\code 113 * int ho = TopologyInfo::higher_order( topo, num_nodes, err ); 114 * bool have_midedge = !!(ho & 1<<1); 115 * bool have_midface = !!(ho & 1<<2); 116 * bool have_midvol = !!(ho & 1<<3); 117 *\endocde 118 * 119 * The advantange of this form of the function over the previous is 120 * that a) it is possible to check for mid-nodes on sub-entities of 121 * a varialbe dimension 'd': 122 *\code 123 * if (ho & (1<<d)) { ... } 124 *\code 125 * and b) it is convienent to test if an element has any higher-order 126 * nodes: 127 *\code 128 * int ho = TopologyInfo::higher_order( topo, num_nodes, err ); 129 * if (!ho) // if linear element 130 * { ... } 131 *\endocde 132 */ 133 static int higher_order( EntityTopology topo, unsigned num_nodes, MsqError &err ); 134 135 /**\brief Given a side, return index of mid-vertex for that side. 136 * 137 * Given a side specification (e.g. the first edge), return the 138 * index of of the correponding mid-side node in the canoncial 139 * ordering of the element connectivity. Returns -1 if the element 140 * doesn't have the specified mid-side node. 141 * 142 *\param topo The element topology 143 *\param num_nodes The number of nodes in the element type. 144 *\param side_dimension The dimension of the side (e.g. 1 = edge, 2 = face) 145 *\param side_number The number of the side (e.g. 0 for first edge/face, etc.) 146 *\return Index (zero-based position) of higher-order node in canonical 147 * ordering of element connectivity, or -1 of element type contains 148 * no such node. 149 */ 150 static int higher_order_from_side( EntityTopology topo, 151 unsigned num_nodes, 152 unsigned side_dimension, 153 unsigned side_number, 154 MsqError& err ); 155 156 /**\brief Get side given a higher-order node */ 157 static void side_from_higher_order( EntityTopology topo, 158 unsigned num_nodes, 159 unsigned node_number, 160 unsigned& side_dim_out, 161 unsigned& side_num_out, 162 MsqError& err ); 163 164 /** Get logical position given an element type node node index*/ 165 static inline sample_from_node(EntityTopology topo,unsigned num_nodes,unsigned node_number,MsqError & err)166 Sample sample_from_node( EntityTopology topo, 167 unsigned num_nodes, 168 unsigned node_number, 169 MsqError& err ) 170 { 171 unsigned dim, num; 172 side_from_higher_order( topo, num_nodes, node_number, dim, num, err ); 173 return Sample(dim, num); 174 } 175 /** Get node index from logical position */ 176 static inline node_from_sample(EntityTopology topo,unsigned num_nodes,Sample sample,MsqError & err)177 int node_from_sample( EntityTopology topo, 178 unsigned num_nodes, 179 Sample sample, 180 MsqError& err ) 181 { 182 return higher_order_from_side( topo, num_nodes, sample.dimension, 183 sample.number, err ); 184 } 185 /**\brief Get indices of edge ends in element connectivity array 186 * 187 * Given an edge number in (0,edges(type)], return which positions 188 * in the connectivity list for the element type correspond to the 189 * end vertices of that edge. 190 */ 191 static const unsigned* edge_vertices( EntityTopology topo, 192 unsigned edge_number, 193 MsqError& err ); 194 static const unsigned* edge_vertices( EntityTopology topo, 195 unsigned edge_number ); 196 197 /**\brief Get face corner indices in element connectivity array 198 * 199 * Given an face number in (0,faces(type)], return which positions 200 * in the connectivity list for the element type correspond to the 201 * vertices of that face, ordered in a counter-clockwise cycle 202 * around a vector pointing out of the element for an ideal element. 203 */ 204 static const unsigned* face_vertices( EntityTopology topo, 205 unsigned face_number, 206 unsigned& num_vertices_out, 207 MsqError& err ); 208 static const unsigned* face_vertices( EntityTopology topo, 209 unsigned face_number, 210 unsigned& num_vertices_out ); 211 212 /**\brief Get corner indices of side 213 * 214 * Get the indices into element connectivity list for the 215 * corners/ends of the specified side of the element. 216 * edge_vertices() and face_vertices() are special cases 217 * of this method. 218 * 219 * If the passed dimension equals that of the specified topology, 220 * the side number is ignored and all the corners of the 221 * element are returned. Fails if side dimension 222 * greater than the dimension of the specified topology type. 223 */ 224 static const unsigned* side_vertices( EntityTopology topo, 225 unsigned side_dimension, 226 unsigned side_number, 227 unsigned& num_verts_out, 228 MsqError& err ); 229 static const unsigned* side_vertices( EntityTopology topo, 230 unsigned side_dimension, 231 unsigned side_number, 232 unsigned& num_verts_out ); 233 234 235 236 /**\brief Return which side the specified mid-node lies on 237 * 238 * Given an non-linear element type (specified by the 239 * topology and length of the connectiivty array) and the 240 * index of a node in the element's connectivity array, 241 * return the lower-dimension entity (side) of the element 242 * the mid-node lies on. 243 * 244 *\param topo Element topology 245 *\param connectivity_length Number of nodes in element 246 *\param node_index Which node of the element 247 *\param side_dimension_out The dimension of the side containing the 248 * midnode (0 = vertex, 1 = edge, 2 = face, 3 = volume) 249 *\param side_number_out The canonical number of the side 250 */ 251 static void side_number( EntityTopology topo, 252 unsigned connectivity_length, 253 unsigned node_index, 254 unsigned& side_dimension_out, 255 unsigned& side_number_out, 256 MsqError& err ); 257 258 /**\brief Get adjacent corner vertices 259 * 260 * Given the index of a vertex in an element, get the list of 261 * indices corresponding to the adjacent corner vertices. 262 * 263 * Adjcent corner vertex indices are returned in the proper 264 * order for constructing the active matrix for the corner. 265 * 266 * Given the array v of all vertices in the patch, the array v_i 267 * containing the connectivity list for an element as 268 * indices into v, and adj as the result of this function for some 269 * corner of the element, the corresponding active matrix A for 270 * that corner can be constructed as: 271 * Matrix3D A; 272 * A.set_column( 0, v[v_i[adj[0]]] - v[v_i[0]] ); 273 * A.set_column( 1, v[v_i[adj[1]]] - v[v_i[0]] ); 274 * A.set_column( 2, v[v_i[adj[2]]] - v[v_i[0]] ); 275 * 276 *\param topo The element type 277 *\param index The index of a corner vertex 278 *\param num_adj_out The number of adjacent vertices (output) 279 *\return The array of vertex indices 280 */ 281 static const unsigned* adjacent_vertices( EntityTopology topo, 282 unsigned index, 283 unsigned& num_adj_out ); 284 285 /**\brief Get reverse adjacency offsets 286 * 287 * Get reverse mapping of results from adjacent_vertices(). 288 * 289 * Let i be the input vertex index. For each vertex index j 290 * for which the result of adjacent_vertices() contains i, return 291 * the offset into that result at which i would occur. The 292 * results are returned in the same order as each j is returned 293 * in the results of adjacent_vertices(...,i,...). Thus the 294 * combination of the results of adjacent_vertices(...,i,...) 295 * and this method provide a reverse mapping of the results of 296 * adjacent_vertices(...,j,...) for i in all j. 297 * 298 * Given: 299 * const unsigned *a, *b, *r; 300 * unsigned n, nn, c = corners(type); 301 * a = adjacent_vertices( type, i, n ); // for any i < c 302 * r = reverse_vertex_adjacency_offsets( type, i, n ); 303 * b = adjacent_vertices( type, a[k], nn ); // for any k < n 304 * Then: 305 * b[r[k]] == i 306 */ 307 static const unsigned* reverse_vertex_adjacency_offsets( 308 EntityTopology topo, 309 unsigned index, 310 unsigned& num_idx_out ); 311 312 /**\brief Find which edge of an element has the passed vertex indices 313 * 314 * Find which edge of the element cooresponds to a list of positions 315 * in the canonical element ordering. 316 *\param topo The element type 317 *\param edge_vertices The array of side vertex indices 318 *\param reversed_out True if edge is reversed wrt edge_vertices 319 *\return The edge number. 320 */ 321 static unsigned find_edge( EntityTopology topo, 322 const unsigned* edge_vertices, 323 bool& reversed_out, 324 MsqError& err ); 325 326 /**\brief Find which face of an element has the passed vertex indices 327 * 328 * Find which face of the element cooresponds to a list of positions 329 * in the canonical element ordering. 330 *\param topo The element type 331 *\param face_vertices The array of face vertex indices 332 *\param num_face_vertices The length of face_vertices 333 *\param reversed_out True if face is reversed wrt face_vertices 334 *\return The face number. 335 */ 336 static unsigned find_face( EntityTopology topo, 337 const unsigned* face_vertices, 338 unsigned num_face_vertices, 339 bool& reversed_out, 340 MsqError& err ); 341 342 /**\brief Find which side of an element has the passed vertex indices 343 * 344 * Find which side of the element cooresponds to a list of positions 345 * in the canonical element ordering. 346 *\param topo The element type 347 *\param side_vertices The array of side vertex indices 348 *\param num_vertices The length of side_vertices 349 *\param dimension_out The dimension of the side 350 *\param number_out The enumerated index for the side 351 *\param reversed_out True if side is reversed wrt side_vertices 352 */ 353 static void find_side( EntityTopology topo, 354 const unsigned* side_vertices, 355 unsigned num_vertices, 356 unsigned& dimension_out, 357 unsigned& number_out, 358 bool& reversed_out, 359 MsqError& err ); 360 361 /**\brief Test if two elements share lower-order topology 362 * 363 * Test if two elements share lower-order topology (e.g. 364 * whether or not two tetrahedra share an edge.) 365 * 366 * That is compare the 'element_1_side_number'-th lower order 367 * topology of dimension 'side_dimension' on element 1 with the 368 * 'element_2_side_number'-th lower order topology of dimension 369 *'side_dimension' on element 2 370 * 371 *\param element_1_vertices The connectivity of the first element 372 *\param element_1_topology The type of the first element 373 *\param element_1_side_number Which lower-order topology to compare 374 *\param element_2_vertices The connectivity of the second element 375 *\param element_2_topology The type of the second element 376 *\param element_2_side_number Whcih lower-order topology to compare 377 *\param side_dimension The dimension of the lower-order topology 378 */ 379 static bool compare_sides( const size_t* element_1_vertices, 380 EntityTopology element_1_topology, 381 unsigned element_1_side_number, 382 const size_t* element_2_vertices, 383 EntityTopology element_2_topology, 384 unsigned element_2_side_number, 385 unsigned side_dimension, 386 MsqError& err ); 387 388 private: 389 390 enum { 391 MAX_CORNER = 8, 392 MAX_EDGES = 12, 393 MAX_FACES = 6, 394 MAX_FACE_CONN = 5, 395 MAX_VERT_ADJ = 4, 396 FIRST_FACE = TRIANGLE, 397 LAST_FACE = QUADRILATERAL, 398 FIRST_VOL= TETRAHEDRON, 399 LAST_VOL = PYRAMID 400 }; 401 402 unsigned char dimMap[MIXED]; /**< Get dimension of entity given topology */ 403 unsigned char adjMap[MIXED][4]; /**< Get number of adj entities of dimension 0, 1 and dimension 2 */ 404 /** Vertex indices for element edges */ 405 unsigned edgeMap[LAST_VOL-FIRST_FACE+1][MAX_EDGES][2] ; 406 /** Vertex indices for element faces */ 407 unsigned faceMap[LAST_VOL-FIRST_VOL+1][MAX_FACES][MAX_FACE_CONN]; 408 /** Vertex-Vertex adjacency map */ 409 unsigned vertAdjMap[LAST_VOL-FIRST_FACE+1][MAX_CORNER][MAX_VERT_ADJ+1]; 410 /** Reverse Vertex-Vertex adjacency index map */ 411 unsigned revVertAdjIdx[LAST_VOL-FIRST_FACE+1][MAX_CORNER][MAX_VERT_ADJ+1]; 412 413 const char* longNames[MIXED+1]; 414 const char* shortNames[MIXED+1]; 415 416 TopologyInfo(); 417 418 static TopologyInfo instance; 419 420 }; 421 422 } //namespace Mesquite 423 424 #endif 425