Assuming that every global vertex has a unique number, then for every element we have four vertices with unique global numbers:
It has been stated before that since the coordinate systems on the faces of the tetrahedra are not symmetric, it is too difficult to use these coordinate systems [19]. We have shown, however that it is possible in linear or even constant time to satisfy this constraint for any given tetrahedral mesh. This algorithm is local to each element and should be implemented at a pre-processing stage.
We now extend this approach to include meshes consisting of tetrahedra, prisms, and hexahedra. Unfortunately, in this case we find counter-examples where it is not possible to satisfy the origin alignment constraint. We have isolated the problematic cases, and they are unlikely to come up when using a mesh generator.
First we deal with the case when a quadrilateral face is shared by two elements. In this instance it is sufficient to simply make the coordinate directions agree by reversing either face coordinate if necessary.
We now investigate over-constrained meshes. These cases can occur when prisms and tetrahedra are used together in a mesh. We will use these examples to motivate the actual algorithm we propose. The cost of this algorithm also depends linearly on the number of elements in the mesh.
It is instructive to construct a chain of prisms. This is simply a long prism, with equilateral triangular faces, divided at intervals along its length into a set of prisms connected at their triangle faces. The connectivity constraint requires that the coordinate origins of the triangular faces must meet at every prism-prism interface. This condition enforces that the collapsed edge must run in a continuous line through the one edge of the original long prism. Now we twist the chain around in a loop and connect its triangle ends. The chain now forms a closed loop of prisms. The orientation of the end faces of the original chain must also satisfy the connectivity constraint when they meet. However, we can make the chain into a Mobius band by twisting it around the axis along its length. In this case the connectivity cannot be satisfied without changing the mesh.
We can construct a second counter-example, this time involving one tetrahedron and two chains of prisms. We construct two chains of prisms as outlined above, and we join the tetrahedra into the prism chain by connecting two of its faces to the prism chain triangular end faces. We repeat this operation, again connecting the remaining two faces of the tetrahedron to the end faces of the second chain of prisms. We can now repeat the twisting of the prism loops. This over-constrains the tetrahedron so that it cannot be oriented to satisfy the connectivity condition.
These two cases indicate that we cannot allow prism chains to reconnect into closed loops and still satisfy our constraints. Also, we should not allow a prism chain to connect to a tetrahedron with more than one of its triangular faces. If we only consider meshes that satisfy these two constraints, then the following algorithm will satisfy the connectivity constraints: