User:Samitch87111/Mesh parity

Mesh Parity in combinatorial geometry concerns the relationship between the evenness or oddness of the number of boundary faces to elements in a Polygon_mesh. For Finite_elements, meshes composed entirely of triangles, quadrilaterals, tetrahedra, or hexahedra are of special interest. The parity relationships can be seen as an application of the Euler_characteristic formula.

The number of edges bounding a triangle mesh has parity equal to the number of triangles. The number of triangles on a closed 2-manifold is even.

The number of edges bounding a quad (quadrilateral) mesh is even.

The number of triangles bounding a tetrahedral (tet) mesh is even.

The number of quadrilaterals bounding a hexahedral mesh is even.

The number of triangles bounding a tetrahedral mesh is even.

For triangles, ... add formulas here. The number of triangles on a closed 2-manifold must always be even, because there are no boundary edges, and using the same edge-counting technique, 3t = 2e. That the number of edges bounding a quad mesh is even follows from the Euler Characteristic, 4f = 2eint + ebdy, where eint are the number of interior edges, not on the boundary. For tetrahedra, ... add formulas here. For hexahedra, ... add formulas here.

An intuitive way to understand these is to consider building the mesh by adding elements one at a time, and gluing one face of it at a time to the prior elements. (Face = dimension one less than the element.)

Consider a single (odd number of) elements, with an odd number of edges. A triangle, or perhaps a pentagon, in two dimensions. If you glue a second element to it along an edge, you have increased the number of boundary edges by an odd number minus 2: an odd number for the new element's edges, and minus 2 for the common edge. It's an odd number. So the boundary edge parity flips in sync with the element count for triangle meshes. Zero is an even number, so for closed manifolds the number of triangles is always even; another way to see this is that every edge has been glue, so there must be an even number of elements.

In contrast, quadrilaterals in two-dimensions, and hexahedra and tetrahedra in three-dimensions, have an even number of boundary faces: 4, 6, and 4. Hence when you glue an element you still have an even number of boundary facets. So there is no relations between the parity of elements and the parity of the boundary.

The parity relationships are also sufficient in many cases. That is, given a closed boundary mesh of the appropriate parity, it is possible to construct a mesh of the appropriate type in the interior. Here the mesh is just defined topologically; there is no guarantee that the elements can be realized with straight edges, etc. Any even chain of edges admits a compatible triangle or quad mesh of its interior. Any odd chain admits a triangle mesh. Any closed manifold of triangles admits a compatible tetrahedral mesh. The requirements for a hex mesh are slightly stronger. ... cite existence proof paper, eppstein's page perhaps Any quadrilateral mesh of a ball with an even number of elements admits a hex mesh. If the manifold has non-trivial topology, such as a torus, the chains of edges that are null-homotopic in the interior-side of the boundary must also be even for there to exist a hex mesh.

References

add some reference to the existence proof paper

External links

• www.example.com