Mesh Oriented datABase  (version 5.5.1)
An array-based unstructured mesh library
CN.hpp
Go to the documentation of this file.
1 /**
2  * MOAB, a Mesh-Oriented datABase, is a software component for creating,
3  * storing and accessing finite element mesh data.
4  *
5  * Copyright 2004 Sandia Corporation. Under the terms of Contract
6  * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government
7  * retains certain 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  */
15 
16 /**
17  * \class moab::CN
18  * \author Tim Tautges
19  * \date April 2004
20  *
21  * \brief Canonical numbering data and functions
22  * This class represents canonical ordering of finite-element meshes.
23  * Elements in the finite element "zoo" are represented. Canonical numbering
24  * denotes the vertex, edge, and face numbers making up each kind of element,
25  * and the vertex numbers defining those entities. Functions for evaluating
26  * adjacencies and other things based on vertex numbering are also provided.
27  * By default, this class defines a zero-based numbering system.
28  * For a complete description of this class, see the document "MOAB Canonical
29  * Numbering Conventions", Timothy J. Tautges, Sandia National Laboratories
30  * Report #SAND2004-xxxx.
31  */
32 #ifndef MOAB_CN_HPP
33 #define MOAB_CN_HPP
34 
35 #include <vector>
36 #include <algorithm>
37 #include <cassert>
38 
39 #include "moab/EntityType.hpp"
40 
41 #include "moab/win32_config.h"
42 
43 namespace moab
44 {
45 
46 enum
47 {
48  //! the maximum number n-1 dimension adjacencies a element may have
50  //! the maximum number of nodes an n-1 dimensional element may have
52 };
53 
54 typedef std::pair< EntityType, EntityType > DimensionPair;
55 
56 class CN
57 {
58  private:
59  //! entity names
60  static MOAB_EXPORT const char* entityTypeNames[];
61 
62  //! declare private constructor, since we don't want to create any of these
63  CN();
64 
65  //! the basis of the numbering system (normally 0 or 1, 0 by default)
66  static MOAB_EXPORT short int numberBasis;
67 
68  //! switch the basis
69  static void SwitchBasis( const int old_basis, const int new_basis );
70 
71  static MOAB_EXPORT short increasingInts[];
72 
73  public:
74  enum
75  {
77  };
78  enum
79  {
80  MID_EDGE_BIT = 1 << 1,
81  MID_FACE_BIT = 1 << 2,
82  MID_REGION_BIT = 1 << 3
83  };
84 
85  //! enum used to specify operation type
86  enum
87  {
88  INTERSECT = 0,
89  UNION
90  };
91 
92  // each entity type has two ConnMap objects, holding information about the bounding
93  // edges and faces for each entity; see comment for mConnectivityMap
94  // (this struct not documented with Doxygen)
95  struct ConnMap
96  {
97  // Topological dimension of this entry
98  short int topo_dimension;
99 
100  // Number of sub-elements of this dimension
101  short int num_sub_elements;
102 
103  // Number of nodes in each sub-element of this dimension
105 
106  // Type of each sub-element
108 
109  // Connectivity of each of the sub-elements
111  };
112 
113  // mConnectivityMap[i=entity type][j=0,1,2]:
114  // num_sub_elements = # bounding edges(j=0) or faces(j=1) for entity type i, or self (j=2)
115  // num_corners_per_sub_element[k] (k=0..num_sub_elements-1) = number of nodes in sub-facet k
116  // (can vary over sub-facets, e.g. faces bounding a pyramid) or self (j=2)
117  // target_type[k] = entity type of sub-facet k (e.g. MBTRI or MBQUAD bounding a pyramid) or
118  // self (j=2) conn[k][l] (l=0..CN::VerticesPerEntity[target_type[k]]) = vertex connectivity of
119  // sub-facet k,
120  // with respect to entity i's canonical vertex ordering, or self (j=2)
121  // (not documented with Doxygen)
123 
124  // structure used to define reverse canonical ordering information
125  // (not documented with Doxygen)
126  struct UpConnMap
127  {
128  // Number of higher-dimensional entities using each sub-entity
130 
131  // Higher-dimensional entities using each sub-entity
133  };
134 
135  // Reverse canonical numbering, duplicates data in mConnectivityMap, but
136  // connectivity data in this table must be in ascending order (used for
137  // efficient sorting)
138  // (not documented with Doxygen)
139  static const UpConnMap mUpConnMap[MBMAXTYPE][4][4];
140 
141  // Mid-node bits indexed by number of nodes in element
142  static MOAB_EXPORT const unsigned char midNodesPerType[MBMAXTYPE][MAX_NODES_PER_ELEMENT + 1];
143 
144  //! Permutation and reverse permutation vectors
145  static short int permuteVec[MBMAXTYPE][3][MAX_SUB_ENTITIES + 1];
146  static short int revPermuteVec[MBMAXTYPE][3][MAX_SUB_ENTITIES + 1];
147 
148  //! this const vector defines the starting and ending EntityType for
149  //! each dimension, e.g. TypeDimensionMap[2] returns a pair of EntityTypes
150  //! bounding dimension 2.
152 
153  /// Get the dimension pair corresponding to a dimension
154  static DimensionPair getDimPair( int entity_type );
155 
156  //! get the basis of the numbering system
157  static short int GetBasis();
158 
159  //! set the basis of the numbering system
160  static void SetBasis( const int in_basis );
161 
162  //! return the string type name for this type
163  static const char* EntityTypeName( const EntityType this_type );
164 
165  //! given a name, find the corresponding entity type
166  static EntityType EntityTypeFromName( const char* name );
167 
168  //! return the topological entity dimension
169  static short int Dimension( const EntityType t );
170 
171  //! return the number of (corner) vertices contained in the specified type.
172  static short int VerticesPerEntity( const EntityType t );
173 
174  //! return the number of sub-entities bounding the entity.
175  static short int NumSubEntities( const EntityType t, const int d );
176 
177  //! return the type of a particular sub-entity.
178  //! \param this_type Type of entity for which sub-entity type is being queried
179  //! \param sub_dimension Topological dimension of sub-entity whose type is being queried
180  //! \param index Index of sub-entity whose type is being queried
181  //! \return type Entity type of sub-entity with specified dimension and index
182  static EntityType SubEntityType( const EntityType this_type, const int sub_dimension, const int index );
183 
184  //! return the vertex indices of the specified sub-entity.
185  //! \param this_type Type of entity for which sub-entity connectivity is being queried
186  //! \param sub_dimension Dimension of sub-entity
187  //! \param sub_index Index of sub-entity
188  //! \param sub_entity_conn Connectivity of sub-entity (returned to calling function)
189  static void inline SubEntityVertexIndices( const EntityType this_type,
190  const int sub_dimension,
191  const int sub_index,
192  int sub_entity_conn[] );
193 
194  //! return the vertex indices of the specified sub-entity.
195  //! \param this_type Type of entity for which sub-entity connectivity is being queried
196  //! \param sub_dimension Dimension of sub-entity
197  //! \param sub_index Index of sub-entity
198  //! \param num_sub_ent_vertices the number of vertices in the sub-entity
199  static const short* SubEntityVertexIndices( const EntityType this_type,
200  const int sub_dimension,
201  const int sub_index,
202  EntityType& sub_type,
203  int& num_sub_ent_vertices );
204 
205  //! return the node indices of the specified sub-entity.
206  //! \param this_topo The topology of the queried element type
207  //! \param num_nodes The number of nodes in the queried element type.
208  //! \param sub_dimension Dimension of sub-entity
209  //! \param sub_index Index of sub-entity
210  //! \param sub_entity_topo (Output) Topology of requested sub-entity.
211  //! \param num_sub_entity_nodes (Output) Number of nodes in the requested sub-entity.
212  //! \param sub_entity_conn (Output) Connectivity of sub-entity
213  static void SubEntityNodeIndices( const EntityType this_topo,
214  const int num_nodes,
215  const int sub_dimension,
216  const int sub_index,
217  EntityType& sub_entity_topo,
218  int& num_sub_entity_nodes,
219  int sub_entity_conn[] );
220 
221  //! return the vertices of the specified sub entity
222  //! \param parent_conn Connectivity of parent entity
223  //! \param parent_type Entity type of parent entity
224  //! \param sub_dimension Dimension of sub-entity being queried
225  //! \param sub_index Index of sub-entity being queried
226  //! \param sub_entity_conn Connectivity of sub-entity, based on parent_conn and canonical
227  //! ordering for parent_type
228  //! \param num_sub_vertices Number of vertices in sub-entity
229  static void SubEntityConn( const void* parent_conn,
230  const EntityType parent_type,
231  const int sub_dimension,
232  const int sub_index,
233  void* sub_entity_conn,
234  int& num_sub_vertices );
235 
236  //! For a specified set of sides of given dimension, return the intersection
237  //! or union of all sides of specified target dimension adjacent to those sides.
238  //! \param this_type Type of entity for which sub-entity connectivity is being queried
239  //! \param source_indices Indices of sides being queried
240  //! \param num_source_indices Number of entries in <em>source_indices</em>
241  //! \param source_dim Dimension of source entity
242  //! \param target_dim Dimension of target entity
243  //! \param index_list Indices of target entities (returned)
244  //! \param operation_type Specify either CN::INTERSECT or CN::UNION to get intersection
245  //! or union of target entity lists over source entities
246  static short int AdjacentSubEntities( const EntityType this_type,
247  const int* source_indices,
248  const int num_source_indices,
249  const int source_dim,
250  const int target_dim,
251  std::vector< int >& index_list,
252  const int operation_type = CN::INTERSECT );
253 
254  //! return the side index represented in the input sub-entity connectivity in the input
255  //! parent entity connectivity array.
256  //! \param parent_conn Connectivity of parent entity being queried
257  //! \param parent_type Entity type of parent entity
258  //! \param child_conn Connectivity of child whose index is being queried
259  //! \param child_num_verts Number of vertices in <em>child_conn</em>
260  //! \param child_dim Dimension of child entity being queried
261  //! \param side_number Side number of child entity (returned)
262  //! \param sense Sense of child entity with respect to order in <em>child_conn</em> (returned)
263  //! \param offset Offset of <em>child_conn</em> with respect to canonical ordering data
264  //! (returned) \return status Returns zero if successful, -1 if not
265  static short int SideNumber( const EntityType parent_type,
266  const int* parent_conn,
267  const int* child_conn,
268  const int child_num_verts,
269  const int child_dim,
270  int& side_number,
271  int& sense,
272  int& offset );
273  static short int SideNumber( const EntityType parent_type,
274  const unsigned int* parent_conn,
275  const unsigned int* child_conn,
276  const int child_num_verts,
277  const int child_dim,
278  int& side_number,
279  int& sense,
280  int& offset );
281  static short int SideNumber( const EntityType parent_type,
282  const long* parent_conn,
283  const long* child_conn,
284  const int child_num_verts,
285  const int child_dim,
286  int& side_number,
287  int& sense,
288  int& offset );
289  static short int SideNumber( const EntityType parent_type,
290  const unsigned long* parent_conn,
291  const unsigned long* child_conn,
292  const int child_num_verts,
293  const int child_dim,
294  int& side_number,
295  int& sense,
296  int& offset );
297  static short int SideNumber( const EntityType parent_type,
298  const unsigned long long* parent_conn,
299  const unsigned long long* child_conn,
300  const int child_num_verts,
301  const int child_dim,
302  int& side_number,
303  int& sense,
304  int& offset );
305  static short int SideNumber( const EntityType parent_type,
306  void* const* parent_conn,
307  void* const* child_conn,
308  const int child_num_verts,
309  const int child_dim,
310  int& side_number,
311  int& sense,
312  int& offset );
313 
314  //! return the side index represented in the input sub-entity connectivity
315  //! \param parent_type Entity type of parent entity
316  //! \param child_conn_indices Child connectivity to query, specified as indices
317  //! into the connectivity list of the parent.
318  //! \param child_num_verts Number of values in <em>child_conn_indices</em>
319  //! \param child_dim Dimension of child entity being queried
320  //! \param side_number Side number of child entity (returned)
321  //! \param sense Sense of child entity with respect to order in <em>child_conn</em> (returned)
322  //! \param offset Offset of <em>child_conn</em> with respect to canonical ordering data
323  //! (returned) \return status Returns zero if successful, -1 if not
324  static short int SideNumber( const EntityType parent_type,
325  const int* child_conn_indices,
326  const int child_num_verts,
327  const int child_dim,
328  int& side_number,
329  int& sense,
330  int& offset );
331 
332  //! return the dimension and index of the opposite side, given parent entity type and child
333  //! dimension and index. This function is only defined for certain types of parent/child types:
334  //! (Parent, Child dim->Opposite dim):
335  //! (Tri, 1->0), (Tri, 0->1), (Quad, 1->1), (Quad, 0->0),
336  //! (Tet, 2->0), (Tet, 1->1), (Tet, 0->2),
337  //! (Hex, 2->2), (Hex, 1->1)(diagonally across element), (Hex, 0->0) (diagonally across
338  //! element)
339  //! All other parent types and child dimensions return an error.
340  //!
341  //! \param parent_type The type of parent element
342  //! \param child_type The type of child element
343  //! \param child_index The index of the child element
344  //! \param opposite_index The index of the opposite element
345  //! \return status Returns 0 if successful, -1 if not
346  static short int OppositeSide( const EntityType parent_type,
347  const int child_index,
348  const int child_dim,
349  int& opposite_index,
350  int& opposite_dim );
351 
352  //! given two connectivity arrays, determine whether or not they represent the same entity.
353  //! \param conn1 Connectivity array of first entity
354  //! \param conn2 Connectivity array of second entity
355  //! \param num_vertices Number of entries in <em>conn1</em> and <em>conn2</em>
356  //! \param direct If positive, entities have the same sense (returned)
357  //! \param offset Offset of <em>conn2</em>'s first vertex in <em>conn1</em>
358  //! \return bool Returns true if <em>conn1</em> and <em>conn2</em> match
359  static bool ConnectivityMatch( const int* conn1,
360  const int* conn2,
361  const int num_vertices,
362  int& direct,
363  int& offset );
364  static bool ConnectivityMatch( const unsigned int* conn1,
365  const unsigned int* conn2,
366  const int num_vertices,
367  int& direct,
368  int& offset );
369  static bool ConnectivityMatch( const long* conn1,
370  const long* conn2,
371  const int num_vertices,
372  int& direct,
373  int& offset );
374  static bool ConnectivityMatch( const unsigned long* conn1,
375  const unsigned long* conn2,
376  const int num_vertices,
377  int& direct,
378  int& offset );
379  static bool ConnectivityMatch( const unsigned long long* conn1,
380  const unsigned long long* conn2,
381  const int num_vertices,
382  int& direct,
383  int& offset );
384  static bool ConnectivityMatch( void* const* conn1,
385  void* const* conn2,
386  const int num_vertices,
387  int& direct,
388  int& offset );
389 
390  //! Set permutation or reverse permutation vector
391  //! Forward permutation is from CN's numbering into application's ordering;
392  //! that is, if i is CN's index, pvec[i] is application's index. This
393  //! function stores the permutation vector for this type and facet dimension,
394  //! which then is used in calls to permuteThis or revPermuteThis.
395  //! \param t EntityType for which to set permutation
396  //! \param dim Dimension of facets whose permutation array is being set
397  //! \param pvec Permutation array
398  //! \param num_entries Number of indicies in permutation array
399  //! \param is_reverse Array is reverse permutation
400  static inline void setPermutation( const EntityType t,
401  const int dim,
402  short int* pvec,
403  const int num_entries,
404  const bool is_reverse = false );
405 
406  //! Reset permutation or reverse permutation vector
407  //! \param t EntityType whose permutation vector is being reset
408  //! \param dim Dimension of facets being reset; if -1 is input, all dimensions are reset
409  static inline void resetPermutation( const EntityType t, const int dim );
410 
411  //! Permute a handle array according to permutation vector set with setPermute;
412  //! permutation is done in-place
413  //! \param t EntityType of handles in pvec
414  //! \param dim Dimension of handles in pvec
415  //! \param pvec Handle array being permuted
416  //! \param indices_per_ent Number of indices per entity
417  //! \param num_entries Number of entities in pvec
418  static int permuteThis( const EntityType t,
419  const int dim,
420  int* pvec,
421  const int indices_per_ent,
422  const int num_entries );
423  static int permuteThis( const EntityType t,
424  const int dim,
425  unsigned int* pvec,
426  const int indices_per_ent,
427  const int num_entries );
428  static int permuteThis( const EntityType t,
429  const int dim,
430  long* pvec,
431  const int indices_per_ent,
432  const int num_entries );
433  static int permuteThis( const EntityType t,
434  const int dim,
435  void** pvec,
436  const int indices_per_ent,
437  const int num_entries );
438 
439  //! Reverse permute a handle array according to reverse permutation vector set with setPermute;
440  //! reverse permutation is done in-place
441  //! \param t EntityType of handles in pvec
442  //! \param dim Dimension of handles in pvec
443  //! \param pvec Handle array being reverse permuted
444  //! \param indices_per_ent Number of indices per entity
445  //! \param num_entries Number of entities in pvec
446  static int revPermuteThis( const EntityType t,
447  const int dim,
448  int* pvec,
449  const int indices_per_ent,
450  const int num_entries );
451  static int revPermuteThis( const EntityType t,
452  const int dim,
453  unsigned int* pvec,
454  const int indices_per_ent,
455  const int num_entries );
456  static int revPermuteThis( const EntityType t,
457  const int dim,
458  long* pvec,
459  const int indices_per_ent,
460  const int num_entries );
461  static int revPermuteThis( const EntityType t,
462  const int dim,
463  void** pvec,
464  const int indices_per_ent,
465  const int num_entries );
466 
467  //! true if entities of a given type and number of nodes indicates mid edge nodes are present.
468  //! \param this_type Type of entity for which sub-entity connectivity is being queried
469  //! \param num_verts Number of nodes defining entity
470  //! \return bool Returns true if <em>this_type</em> combined with <em>num_nodes</em> indicates
471  //! mid-edge nodes are likely
472  static inline bool HasMidEdgeNodes( const EntityType this_type, const int num_verts );
473 
474  //! true if entities of a given type and number of nodes indicates mid face nodes are present.
475  //! \param this_type Type of entity for which sub-entity connectivity is being queried
476  //! \param num_verts Number of nodes defining entity
477  //! \return bool Returns true if <em>this_type</em> combined with <em>num_nodes</em> indicates
478  //! mid-face nodes are likely
479  static inline bool HasMidFaceNodes( const EntityType this_type, const int num_verts );
480 
481  //! true if entities of a given type and number of nodes indicates mid region nodes are present.
482  //! \param this_type Type of entity for which sub-entity connectivity is being queried
483  //! \param num_verts Number of nodes defining entity
484  //! \return bool Returns true if <em>this_type</em> combined with <em>num_nodes</em> indicates
485  //! mid-region nodes are likely
486  static inline bool HasMidRegionNodes( const EntityType this_type, const int num_verts );
487 
488  //! true if entities of a given type and number of nodes indicates mid edge/face/region nodes
489  //! are present.
490  //! \param this_type Type of entity for which sub-entity connectivity is being queried
491  //! \param num_verts Number of nodes defining entity
492  //! \param mid_nodes If <em>mid_nodes[i], i=1..2</em> is non-zero, indicates that mid-edge
493  //! (i=1), mid-face (i=2), and/or mid-region (i=3) nodes are likely
494  static inline void HasMidNodes( const EntityType this_type, const int num_verts, int mid_nodes[4] );
495 
496  //! Same as above, except returns a single integer with the bits, from
497  //! least significant to most significant set to one if the corresponding
498  //! mid nodes on sub entities of the least dimension (0) to the highest
499  //! dimension (3) are present in the elment type.
500  static inline int HasMidNodes( const EntityType this_type, const int num_verts );
501 
502  //! given data about an element and a vertex in that element, return the dimension
503  //! and index of the sub-entity that the vertex resolves. If it does not resolve a
504  //! sub-entity, either because it's a corner node or it's not in the element, -1 is
505  //! returned in both return values.
506  //! \param elem_type Type of entity being queried
507  //! \param num_nodes The number of nodes in the element connectivity
508  //! \param ho_node_index The position of the HO node in the connectivity list (zero based)
509  //! \param parent_dim Dimension of sub-entity high-order node resolves (returned)
510  //! \param parent_index Index of sub-entity high-order node resolves (returned)
511  static void HONodeParent( EntityType elem_type,
512  int num_nodes,
513  int ho_node_index,
514  int& parent_dim,
515  int& parent_index );
516 
517  //! for an entity of this type with num_verts vertices, and a specified subfacet
518  //! (dimension and index), return the index of the higher order node for that entity
519  //! in this entity's connectivity array
520  //! \param this_type Type of entity being queried
521  //! \param num_verts Number of vertices for the entity being queried
522  //! \param subfacet_dim Dimension of sub-entity being queried
523  //! \param subfacet_index Index of sub-entity being queried
524  //! \return index Index of sub-entity's higher-order node
525  static short int HONodeIndex( const EntityType this_type,
526  const int num_verts,
527  const int subfacet_dim,
528  const int subfacet_index );
529 };
530 
531 //! get the basis of the numbering system
532 inline short int CN::GetBasis()
533 {
534  return numberBasis;
535 }
536 
537 //! return the connectivity of the specified sub-entity.
538 inline void CN::SubEntityVertexIndices( const EntityType this_type,
539  const int sub_dimension,
540  const int index,
541  int sub_entity_conn[] )
542 {
543  EntityType type;
544  int n;
545  const short* indices = SubEntityVertexIndices( this_type, sub_dimension, index, type, n );
546  std::copy( indices, indices + n, sub_entity_conn );
547 }
548 
549 inline bool CN::HasMidEdgeNodes( const EntityType this_type, const int num_nodes )
550 {
551  const int bits = HasMidNodes( this_type, num_nodes );
552  return static_cast< bool >( ( bits & ( 1 << 1 ) ) >> 1 );
553 }
554 
555 inline bool CN::HasMidFaceNodes( const EntityType this_type, const int num_nodes )
556 {
557  const int bits = HasMidNodes( this_type, num_nodes );
558  return static_cast< bool >( ( bits & ( 1 << 2 ) ) >> 2 );
559 }
560 
561 inline bool CN::HasMidRegionNodes( const EntityType this_type, const int num_nodes )
562 {
563  const int bits = HasMidNodes( this_type, num_nodes );
564  return static_cast< bool >( ( bits & ( 1 << 3 ) ) >> 3 );
565 }
566 
567 inline int CN::HasMidNodes( const EntityType this_type, const int num_nodes )
568 {
569  assert( (unsigned)num_nodes <= (unsigned)MAX_NODES_PER_ELEMENT );
570  return midNodesPerType[this_type][num_nodes];
571 }
572 
573 inline void CN::HasMidNodes( const EntityType this_type, const int num_nodes, int mid_nodes[4] )
574 {
575  const int bits = HasMidNodes( this_type, num_nodes );
576  mid_nodes[0] = 0;
577  mid_nodes[1] = ( bits & ( 1 << 1 ) ) >> 1;
578  mid_nodes[2] = ( bits & ( 1 << 2 ) ) >> 2;
579  mid_nodes[3] = ( bits & ( 1 << 3 ) ) >> 3;
580 }
581 
582 //! Set permutation or reverse permutation vector
583 inline void CN::setPermutation( const EntityType t,
584  const int dim,
585  short int* pvec,
586  const int num_entries,
587  const bool is_reverse )
588 {
589  short int *this_vec = permuteVec[t][dim], *that_vec = revPermuteVec[t][dim];
590  if( is_reverse )
591  {
592  this_vec = revPermuteVec[t][dim];
593  that_vec = permuteVec[t][dim];
594  }
595 
596  for( short int i = 0; i < num_entries; i++ )
597  {
598  this_vec[i] = pvec[i];
599  that_vec[pvec[i]] = i;
600  }
601 
602  this_vec[MAX_SUB_ENTITIES] = that_vec[MAX_SUB_ENTITIES] = (short)num_entries;
603 }
604 
605 //! Reset permutation or reverse permutation vector
606 inline void CN::resetPermutation( const EntityType t, const int dim )
607 {
608  if( -1 == dim )
609  {
610  for( unsigned int i = 0; i < 3; i++ )
611  resetPermutation( t, i );
612  return;
613  }
614 
615  for( short unsigned int i = 0; i < MAX_SUB_ENTITIES; i++ )
616  {
617  revPermuteVec[t][dim][i] = permuteVec[t][dim][i] = i;
618  }
619 
621 }
622 
623 } // namespace moab
624 
625 #endif