Solids surface grid generation for three-dimensional topography

Abstract

A method for creating regular triangular grid representations of a solid surface from a representation comprised of a plurality of polygons. Such a regular grid is necessary in order to accurately deform a solid during simulation of a process step. The method of the preferred embodiment is comprised generally of the steps of: removing any holes defined by the polygon face; placing a new edge between a first and second vertex of the polygon face; discarding the new edge if the new edge lies outside the polygon face or if the new edge intersects an existing edge of the polygon face; adding the new edge to the polygon face if the new edge does not lie outside the polygon face; identifying a triangle being created by the new edge and existing edges of the polygon; forming a new polygon face from the edges creating a triangle; and repeating the above steps until all polygon faces are triangulated. Once the triangulation of the polygons is completed, adjustments to the triangles is made in order to have only triangles of uniform size.