Branch data Line data Source code
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 : : [email protected]
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 : : static const char* name( EntityTopology topo )
44 : : {
45 : : return topo > MIXED ? 0 : instance.longNames[topo];
46 : : }
47 : 0 : static const char* short_name( EntityTopology topo )
48 : : {
49 [ # # ]: 0 : return topo > MIXED ? 0 : instance.shortNames[topo];
50 : : }
51 : :
52 : : /** \brief Dimension of element topology */
53 : 74395927 : static unsigned dimension( EntityTopology topo )
54 : : {
55 [ + - ]: 74395927 : return topo >= MIXED ? 0 : instance.dimMap[topo];
56 : : }
57 : :
58 : : /** \brief Number of adjacent entities of a specified dimension
59 : : *
60 : : * For a given element topology, get the number of adjacent entities
61 : : * of the specified dimension.
62 : : */
63 : 268794145 : static unsigned adjacent( EntityTopology topo, unsigned dimension )
64 : : {
65 [ + + ]: 268794145 : return ( topo >= MIXED ) ? 0 : instance.adjMap[topo][dimension];
66 : : }
67 : :
68 : : /** \brief Get number of sides a given topology type has
69 : : *
70 : : * Get the number of sides for a given element topology. Returns
71 : : * the number of adjacent entities of one less dimension. The number
72 : : * of faces for a volume element and the number of edges for a face
73 : : * element
74 : : */
75 : 0 : static unsigned sides( EntityTopology topo )
76 : : {
77 [ # # ][ # # ]: 0 : return ( topo >= MIXED || instance.dimMap[topo] < 1 ) ? 0 : instance.adjMap[topo][instance.dimMap[topo] - 1];
78 : : }
79 : :
80 : : /** \brief Get the number of defining vertices for a given element topology
81 : : *
82 : : * Get the number of corner vertices necessary to define an element
83 : : * of the specified topology. This is the number of nodes a linear
84 : : * element of the specified topology will have.
85 : : */
86 : 152507369 : static unsigned corners( EntityTopology topo )
87 : : {
88 : 152507369 : return adjacent( topo, 0 );
89 : : }
90 : :
91 : : /** \brief Get the number of edges in a given topology */
92 : 76577433 : static unsigned edges( EntityTopology topo )
93 : : {
94 : 76577433 : return adjacent( topo, 1 );
95 : : }
96 : :
97 : : /** \brief Get the number of faces in a given topology */
98 : 39340372 : static unsigned faces( EntityTopology topo )
99 : : {
100 : 39340372 : return adjacent( topo, 2 );
101 : : }
102 : :
103 : : /** \brief Check which mid-nodes a higher-order element has.
104 : : *
105 : : * Assuming at most one mid-node per sub-entity per dimension
106 : : * (i.e. at most one mid-node per edge, at most one mid-node per face, etc.)
107 : : * determine which mid-nodes are present given the topology
108 : : * and total number of nodes.
109 : : */
110 : : static void higher_order( EntityTopology topo, unsigned num_nodes, bool& midedge, bool& midface, bool& midvol,
111 : : MsqError& err );
112 : :
113 : : /** \brief Check which mid-nodes a higher-order element has.
114 : : *
115 : : * Assuming at most one mid-node per sub-entity per dimension
116 : : * (i.e. at most one mid-node per edge, at most one mid-node per face, etc.)
117 : : * determine which mid-nodes are present given the topology
118 : : * and total number of nodes. This function is similar to the
119 : : * previous one, except that that it returns a set of bits, one per
120 : : * side dimension, rather than separate bool values. If the bit at position
121 : : * one (the second least significant bit) has a value of one, then the
122 : : * element has mid-edge nodes. If the bit at position two (the third to
123 : : * least signficiant bit) has a value of one then the element has mid-face
124 : : * nodes.
125 : : *\code
126 : : * int ho = TopologyInfo::higher_order( topo, num_nodes, err );
127 : : * bool have_midedge = !!(ho & 1<<1);
128 : : * bool have_midface = !!(ho & 1<<2);
129 : : * bool have_midvol = !!(ho & 1<<3);
130 : : *\endocde
131 : : *
132 : : * The advantange of this form of the function over the previous is
133 : : * that a) it is possible to check for mid-nodes on sub-entities of
134 : : * a varialbe dimension 'd':
135 : : *\code
136 : : * if (ho & (1<<d)) { ... }
137 : : *\code
138 : : * and b) it is convienent to test if an element has any higher-order
139 : : * nodes:
140 : : *\code
141 : : * int ho = TopologyInfo::higher_order( topo, num_nodes, err );
142 : : * if (!ho) // if linear element
143 : : * { ... }
144 : : *\endocde
145 : : */
146 : : static int higher_order( EntityTopology topo, unsigned num_nodes, MsqError& err );
147 : :
148 : : /**\brief Given a side, return index of mid-vertex for that side.
149 : : *
150 : : * Given a side specification (e.g. the first edge), return the
151 : : * index of of the correponding mid-side node in the canoncial
152 : : * ordering of the element connectivity. Returns -1 if the element
153 : : * doesn't have the specified mid-side node.
154 : : *
155 : : *\param topo The element topology
156 : : *\param num_nodes The number of nodes in the element type.
157 : : *\param side_dimension The dimension of the side (e.g. 1 = edge, 2 = face)
158 : : *\param side_number The number of the side (e.g. 0 for first edge/face, etc.)
159 : : *\return Index (zero-based position) of higher-order node in canonical
160 : : * ordering of element connectivity, or -1 of element type contains
161 : : * no such node.
162 : : */
163 : : static int higher_order_from_side( EntityTopology topo, unsigned num_nodes, unsigned side_dimension,
164 : : unsigned side_number, MsqError& err );
165 : :
166 : : /**\brief Get side given a higher-order node */
167 : : static void side_from_higher_order( EntityTopology topo, unsigned num_nodes, unsigned node_number,
168 : : unsigned& side_dim_out, unsigned& side_num_out, MsqError& err );
169 : :
170 : : /** Get logical position given an element type node node index*/
171 : 4655 : static inline Sample sample_from_node( EntityTopology topo, unsigned num_nodes, unsigned node_number,
172 : : MsqError& err )
173 : : {
174 : : unsigned dim, num;
175 [ + - ]: 4655 : side_from_higher_order( topo, num_nodes, node_number, dim, num, err );
176 [ + - ]: 4655 : return Sample( dim, num );
177 : : }
178 : : /** Get node index from logical position */
179 : : static inline int node_from_sample( EntityTopology topo, unsigned num_nodes, Sample sample, MsqError& err )
180 : : {
181 : : return higher_order_from_side( topo, num_nodes, sample.dimension, sample.number, err );
182 : : }
183 : : /**\brief Get indices of edge ends in element connectivity array
184 : : *
185 : : * Given an edge number in (0,edges(type)], return which positions
186 : : * in the connectivity list for the element type correspond to the
187 : : * end vertices of that edge.
188 : : */
189 : : static const unsigned* edge_vertices( EntityTopology topo, unsigned edge_number, MsqError& err );
190 : : static const unsigned* edge_vertices( EntityTopology topo, unsigned edge_number );
191 : :
192 : : /**\brief Get face corner indices in element connectivity array
193 : : *
194 : : * Given an face number in (0,faces(type)], return which positions
195 : : * in the connectivity list for the element type correspond to the
196 : : * vertices of that face, ordered in a counter-clockwise cycle
197 : : * around a vector pointing out of the element for an ideal element.
198 : : */
199 : : static const unsigned* face_vertices( EntityTopology topo, unsigned face_number, unsigned& num_vertices_out,
200 : : MsqError& err );
201 : : static const unsigned* face_vertices( EntityTopology topo, unsigned face_number, unsigned& num_vertices_out );
202 : :
203 : : /**\brief Get corner indices of side
204 : : *
205 : : * Get the indices into element connectivity list for the
206 : : * corners/ends of the specified side of the element.
207 : : * edge_vertices() and face_vertices() are special cases
208 : : * of this method.
209 : : *
210 : : * If the passed dimension equals that of the specified topology,
211 : : * the side number is ignored and all the corners of the
212 : : * element are returned. Fails if side dimension
213 : : * greater than the dimension of the specified topology type.
214 : : */
215 : : static const unsigned* side_vertices( EntityTopology topo, unsigned side_dimension, unsigned side_number,
216 : : unsigned& num_verts_out, MsqError& err );
217 : : static const unsigned* side_vertices( EntityTopology topo, unsigned side_dimension, unsigned side_number,
218 : : unsigned& num_verts_out );
219 : :
220 : : /**\brief Return which side the specified mid-node lies on
221 : : *
222 : : * Given an non-linear element type (specified by the
223 : : * topology and length of the connectiivty array) and the
224 : : * index of a node in the element's connectivity array,
225 : : * return the lower-dimension entity (side) of the element
226 : : * the mid-node lies on.
227 : : *
228 : : *\param topo Element topology
229 : : *\param connectivity_length Number of nodes in element
230 : : *\param node_index Which node of the element
231 : : *\param side_dimension_out The dimension of the side containing the
232 : : * midnode (0 = vertex, 1 = edge, 2 = face, 3 = volume)
233 : : *\param side_number_out The canonical number of the side
234 : : */
235 : : static void side_number( EntityTopology topo, unsigned connectivity_length, unsigned node_index,
236 : : unsigned& side_dimension_out, unsigned& side_number_out, MsqError& err );
237 : :
238 : : /**\brief Get adjacent corner vertices
239 : : *
240 : : * Given the index of a vertex in an element, get the list of
241 : : * indices corresponding to the adjacent corner vertices.
242 : : *
243 : : * Adjcent corner vertex indices are returned in the proper
244 : : * order for constructing the active matrix for the corner.
245 : : *
246 : : * Given the array v of all vertices in the patch, the array v_i
247 : : * containing the connectivity list for an element as
248 : : * indices into v, and adj as the result of this function for some
249 : : * corner of the element, the corresponding active matrix A for
250 : : * that corner can be constructed as:
251 : : * Matrix3D A;
252 : : * A.set_column( 0, v[v_i[adj[0]]] - v[v_i[0]] );
253 : : * A.set_column( 1, v[v_i[adj[1]]] - v[v_i[0]] );
254 : : * A.set_column( 2, v[v_i[adj[2]]] - v[v_i[0]] );
255 : : *
256 : : *\param topo The element type
257 : : *\param index The index of a corner vertex
258 : : *\param num_adj_out The number of adjacent vertices (output)
259 : : *\return The array of vertex indices
260 : : */
261 : : static const unsigned* adjacent_vertices( EntityTopology topo, unsigned index, unsigned& num_adj_out );
262 : :
263 : : /**\brief Get reverse adjacency offsets
264 : : *
265 : : * Get reverse mapping of results from adjacent_vertices().
266 : : *
267 : : * Let i be the input vertex index. For each vertex index j
268 : : * for which the result of adjacent_vertices() contains i, return
269 : : * the offset into that result at which i would occur. The
270 : : * results are returned in the same order as each j is returned
271 : : * in the results of adjacent_vertices(...,i,...). Thus the
272 : : * combination of the results of adjacent_vertices(...,i,...)
273 : : * and this method provide a reverse mapping of the results of
274 : : * adjacent_vertices(...,j,...) for i in all j.
275 : : *
276 : : * Given:
277 : : * const unsigned *a, *b, *r;
278 : : * unsigned n, nn, c = corners(type);
279 : : * a = adjacent_vertices( type, i, n ); // for any i < c
280 : : * r = reverse_vertex_adjacency_offsets( type, i, n );
281 : : * b = adjacent_vertices( type, a[k], nn ); // for any k < n
282 : : * Then:
283 : : * b[r[k]] == i
284 : : */
285 : : static const unsigned* reverse_vertex_adjacency_offsets( EntityTopology topo, unsigned index,
286 : : unsigned& num_idx_out );
287 : :
288 : : /**\brief Find which edge of an element has the passed vertex indices
289 : : *
290 : : * Find which edge of the element cooresponds to a list of positions
291 : : * in the canonical element ordering.
292 : : *\param topo The element type
293 : : *\param edge_vertices The array of side vertex indices
294 : : *\param reversed_out True if edge is reversed wrt edge_vertices
295 : : *\return The edge number.
296 : : */
297 : : static unsigned find_edge( EntityTopology topo, const unsigned* edge_vertices, bool& reversed_out, MsqError& err );
298 : :
299 : : /**\brief Find which face of an element has the passed vertex indices
300 : : *
301 : : * Find which face of the element cooresponds to a list of positions
302 : : * in the canonical element ordering.
303 : : *\param topo The element type
304 : : *\param face_vertices The array of face vertex indices
305 : : *\param num_face_vertices The length of face_vertices
306 : : *\param reversed_out True if face is reversed wrt face_vertices
307 : : *\return The face number.
308 : : */
309 : : static unsigned find_face( EntityTopology topo, const unsigned* face_vertices, unsigned num_face_vertices,
310 : : bool& reversed_out, MsqError& err );
311 : :
312 : : /**\brief Find which side of an element has the passed vertex indices
313 : : *
314 : : * Find which side of the element cooresponds to a list of positions
315 : : * in the canonical element ordering.
316 : : *\param topo The element type
317 : : *\param side_vertices The array of side vertex indices
318 : : *\param num_vertices The length of side_vertices
319 : : *\param dimension_out The dimension of the side
320 : : *\param number_out The enumerated index for the side
321 : : *\param reversed_out True if side is reversed wrt side_vertices
322 : : */
323 : : static void find_side( EntityTopology topo, const unsigned* side_vertices, unsigned num_vertices,
324 : : unsigned& dimension_out, unsigned& number_out, bool& reversed_out, MsqError& err );
325 : :
326 : : /**\brief Test if two elements share lower-order topology
327 : : *
328 : : * Test if two elements share lower-order topology (e.g.
329 : : * whether or not two tetrahedra share an edge.)
330 : : *
331 : : * That is compare the 'element_1_side_number'-th lower order
332 : : * topology of dimension 'side_dimension' on element 1 with the
333 : : * 'element_2_side_number'-th lower order topology of dimension
334 : : *'side_dimension' on element 2
335 : : *
336 : : *\param element_1_vertices The connectivity of the first element
337 : : *\param element_1_topology The type of the first element
338 : : *\param element_1_side_number Which lower-order topology to compare
339 : : *\param element_2_vertices The connectivity of the second element
340 : : *\param element_2_topology The type of the second element
341 : : *\param element_2_side_number Whcih lower-order topology to compare
342 : : *\param side_dimension The dimension of the lower-order topology
343 : : */
344 : : static bool compare_sides( const size_t* element_1_vertices, EntityTopology element_1_topology,
345 : : unsigned element_1_side_number, const size_t* element_2_vertices,
346 : : EntityTopology element_2_topology, unsigned element_2_side_number,
347 : : unsigned side_dimension, MsqError& err );
348 : :
349 : : private:
350 : : enum
351 : : {
352 : : MAX_CORNER = 8,
353 : : MAX_EDGES = 12,
354 : : MAX_FACES = 6,
355 : : MAX_FACE_CONN = 5,
356 : : MAX_VERT_ADJ = 4,
357 : : FIRST_FACE = TRIANGLE,
358 : : LAST_FACE = QUADRILATERAL,
359 : : FIRST_VOL = TETRAHEDRON,
360 : : LAST_VOL = PYRAMID
361 : : };
362 : :
363 : : unsigned char dimMap[MIXED]; /**< Get dimension of entity given topology */
364 : : unsigned char adjMap[MIXED][4]; /**< Get number of adj entities of dimension 0, 1 and dimension 2 */
365 : : /** Vertex indices for element edges */
366 : : unsigned edgeMap[LAST_VOL - FIRST_FACE + 1][MAX_EDGES][2];
367 : : /** Vertex indices for element faces */
368 : : unsigned faceMap[LAST_VOL - FIRST_VOL + 1][MAX_FACES][MAX_FACE_CONN];
369 : : /** Vertex-Vertex adjacency map */
370 : : unsigned vertAdjMap[LAST_VOL - FIRST_FACE + 1][MAX_CORNER][MAX_VERT_ADJ + 1];
371 : : /** Reverse Vertex-Vertex adjacency index map */
372 : : unsigned revVertAdjIdx[LAST_VOL - FIRST_FACE + 1][MAX_CORNER][MAX_VERT_ADJ + 1];
373 : :
374 : : const char* longNames[MIXED + 1];
375 : : const char* shortNames[MIXED + 1];
376 : :
377 : : TopologyInfo();
378 : :
379 : : static TopologyInfo instance;
380 : : };
381 : :
382 : : } // namespace MBMesquite
383 : :
384 : : #endif
|