Adaptive subdivision of mesh models

• US 6,356,263 B2
• Filed: 01/27/1999
• Issued: 03/12/2002
• Est. Priority Date: 01/27/1999
• Status: Expired due to Term

• Current Assignee: Andreas Acquisitions, LLC
• Original Assignee: Viewpoint Mhc
• Inventors: Paskhaver, Victor, Migdal, Alexander A., Lebedev, Alexei
• Primary Examiner(s): Vo, Cliff N.
• Assistant Examiner(s): Nguyen, Kimbinh T.
• Application Number:
  US09/238,232
• Publication Number:
  US 20010013866A1
• Time in Patent Office: 1,140 Days
• Field of Search: 345/423, 345/420, 345/425, 345/418, 345/442, 345/581, 345/421
• US Class Current: 345/423
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A computer-based system and method for refining of mesh model of a three-dimensional (3D) object or surface through adaptive subdivision that results in a smooth interpolation of the mesh surface. In one example, the system operates upon a triangulated mesh model and analyzes each edge of the triangle in question to determine whether that particular edge should be subdivided based on a predetermined subdivision criteria. After an analysis of each of the edges of that triangle (using the adaptive subdivision criteria) the system and method may make one of several different types of subdivisions—e.g. dividing the mesh triangle into two, three or four smaller triangles.

Claims

1. A computer-based system for smoothing a mesh model of a three-dimensional object or surface, the mesh model having a set of connected faces, each face being a geometric shape with a predetermined number of vertices and a corresponding number of edges, each edge connecting two of the predetermined number of vertices, each vertex being a data point describing the object or surface, the computer, including a processor coupled to a memory, the system comprising:

a subdivision element to check a first edge against a predetermined subdivision criteria;

an insertion element to insert a new subdivision point along the first edge, the new subdivision point being inserted depending on whether or not the first edge meets the predetermined subdivision criteria; and

an extrusion element to extrude the new subdivision point so that it lies on a curve, wherein the curve passes through the vertices connected by the first edge orthogonal to normal vectors at the vertices.

2. The computer-based system according to claim 1, wherein the subdivision criteria includes a procedure that determines whether a square of a distance between vertex coordinates of the first edge is greater than a threshold value, the insertion element inserting the new subdivision point if the distance is greater than the threshold value.

3. The computer-based system according to claim 1, wherein the subdivision criteria includes a procedure that determines vertex normals of vertices of the first edge, the insertion element inserting the new subdivision point if an angle between the vertex normals is greater than a threshold value.

4. A method for refining a mesh model of a three-dimensional object or shape, the mesh model including a plurality of first geometric shapes, comprising the steps of:

selecting at least one of the first geometric shapes;

recursively subdividing each of the selected first geometric shapes into a plurality of second geometric shapes; and

displaying each of the plurality of second geometric shapes.

5. The method according to claim 4, wherein the step of recursively subdividing includes the steps of:

for each respective edge of each of the first geometric shapes, determining whether to subdivide the edge as a function of a predetermined subdivision criteria, and subdividing the respective edge if a square of a distance between vertex coordinates of the respective edge is greater than a threshold value.

6. The method according to claim 4, wherein the step of recursively subdividing includes the steps of:

for each respective edge of each of the first geometric shapes, determining vertex normals of vertices of the first edge, and subdividing the respective edge if an angle between the vertex normals is greater than a threshold value.

7. A method for refining a mesh model of a three-dimensional object or shape, the mesh model including a plurality of first geometric shapes having edges, comprising the steps of:

selecting at least one of the first geometric shapes;

for each one of the edges of the selected geometric shapes;

i) determining if the one of the edges meets a predetermined subdivision criteria; and

ii) if the one of the edges meets the predetermined criteria, subdividing the one of the edges; and

subdividing each of the selected first geometric shapes into a plurality of second geometric shapes as a function of the subdivided edges.

8. The method according to claim 7, wherein the determining step includes comparing a square of a distance between vertex coordinates of the one of the edges to a threshold value, and wherein the one of the edges is subdivided if the square of the distance is greater than the threshold value.

9. The method according to claim 7, wherein the determining step includes comparing an angle between vertex normals of the one of the edges to a threshold value, wherein the one of the edges is subdivided if the angle is greater than the threshold value.