Patent ID: 7280109

Claim:
A computer-implemented method for evaluating a plurality of proposed edge collapse transformations for simplification of a mesh M, such mesh defined by plural original vertices interconnected by plural edges, such interconnections defining polygon faces, the method comprising: determining a reference surface for the plural vertices of M; performing a proposed edge collapse transformation out of the plurality of proposed edge collapse transformations for a first and a second vertex joined by an edge, such transformation defining a resultant vertex; determining an open neighborhood of the proposed edge collapse transformation, the neighborhood having multiple elements, at least one element of the neighborhood comprising at least one point not on the plural edges or the plural original vertices; determining, for at least two of the multiple elements, the height deviation from the reference surface provided by the proposed edge collapse transformation; identifying the maximum height deviation from among the at least two height deviations determined; associating the maximum height deviation with the proposed edge collapse transformation; comparing the plurality of proposed edge collapse transformations, wherein the comparing identifies a proposed edge collapse transformation out of the plurality of proposed edge collapse transformations having the smallest maximum height deviation; collapsing the identified proposed edge collapse transformation; and storing the smallest maximum height deviation in memory associated with the computer.