Tetrahedral Shell Generation

摘要

Tetrahedra can be used as primitives to represent volumetric shells because of their ease of performing geometric tests such as intersection with other geometric primitives. Each triangular face of a triangulated surface mesh can be extruded or otherwise formed into a prism, and that prism can be filled with tets (tetrahedra). An edge of a tet can be deemed to be rising if, going counterlockwise around the face, the corresponding tet-edge that splits the extruded face proceeds from the inset surface to the offset surface. To determine a valid tet orientation, each directed edge of the surface mesh is labeled as Rising or Falling (R, F). In various embodiments, one or more simple rules are used for determining whether an edge is rising or falling. In one aspect, a partial ordering of the connectivity of a surface is used in the tet generation process.

主权项

1. A method for generating a plurality of tetrahedrons from a plurality of prisms, the method comprising:
receiving, at one or more computer systems, information specifying a first surface of triangles that are connected; receiving, at the one or more computer systems, information specifying a second surface of triangles having a same connectivity as the first surface, wherein pairs of corresponding triangles of the first surface and the second surface form a prism, each prism comprising three quadrilateral surfaces; for each prism, splitting, by the one or more computer systems, the prism into three tetrahedrons by forming a diagonal edge on each of the three quadrilateral surfaces such that:
each of the diagonal edges is associated with a direction from an origin vertex to a destination vertex on the quadrilateral surface, andeach of the three tetrahedrons comprises two of the diagonal edges; and for each diagonal edge of each prism:
determining the direction of the diagonal edge to be formed by comparing the origin vertex and the destination vertex such that the diagonal edge is determined to be formed as a rising edge when an index value of the origin vertex of the diagonal edge is less than an index value of the destination vertex of the diagonal edge; and, wherein the two diagonal edges of any of the three tetrahedrons of any of the plurality of the prisms are not both rising edges.