Patent ID: 7305121

Claim:
A method of creating a surface representation of a three-dimensional object from a cloud of points, each point having three-dimensional spatial coordinates, comprising the steps of: a) storing the cloud of points in a memory of a computer; b) storing, in the memory of the computer, a list of points comprising the cloud of points; c) storing, in the memory of the computer, a list of open edges, said open edges comprising a line segment joining two points in which the line segment is not a common edge of two adjacent triangle constructed from the cloud of points; and d) providing machine executable instructions for said computer that operate on said cloud of points, said instructions: 1) constructing an initial open edge from points in the cloud of points; 2) constructing a triangle forming a portion of said surface representation from the open edge using predetermined rules for generating triangles forming said surface representation; 3) adjusting the list of open edges in view of the construction of said triangle; 4) checking to see if the are open edges that not been tried yet to form a triangle forming a portion of said surface representation, and if so repeating steps 2) and 3); 5) as steps 2), 3) and 4) execute, adjusting the list of points by deleting points in the list of points that are used to generate vertices of triangles in step 2); and 6) repeatedly iterating steps 2), 3), 4) and 5) until all open edges have been attempted to generate triangles in accordance with said predetermined rules for generating triangles and all remaining points in the list of points have been attempted to generate a vertex of a new triangle in accordance within predetermine rules for generating vertices of triangles forming said surface.