Procedure for the simplification of triangular surface meshes for more efficient processing

• US 5,689,577 A
• Filed: 10/14/1994
• Issued: 11/18/1997
• Est. Priority Date: 10/14/1994
• Status: Expired due to Fees

• Current Assignee: Picker International, Inc. (Koninklijke Philips N.V.)
• Original Assignee: Picker International, Inc. (Koninklijke Philips N.V.)
• Inventors: Arata, Louis K.
• Primary Examiner(s): MANCUSO, JOSEPH
• Assistant Examiner(s): Prikockis, Larry J.
• Application Number:
  US08/324,419
• Time in Patent Office: 1,131 Days
• Field of Search: 364/413.13, 364/413.22, 364/413.18, 364/474.24, 364/578, 364/723, 382/128, 382/131, 382/132, 382/154, 382/196, 382/203, 382/209, 382/217, 382/220, 382/285, 395/119, 395/120, 395/141, 395/161, 395/125, 395/127, 395/130, 395/124, 395/134, 395/121, 395/123, 395/126, 395/135
• US Class Current: 382/128
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A volume image memory (24) stores an electronic image representation of a volumetric region, such as the volumetric region examinedby a medical diagnostic scanner (10). A sub-region of interest of the volume is selected (30) and the surface of the selected region or object of interest is divided into triangular surface regions with a triangular surface processor (38). A vertex merging processor (40) examines the triangles to locate vertices spaced by less than a preselected minimum. Vertices closer than the preselected minimum are replaced with a vertex at a median position merging the triangle into adjacent triangles. A vertex removal processor (50) identifies groups of triangles having a common vertex (V_c) that form a pyramid. The surface normals (N) of the triangles which define the pyramid are examined to determine whether they are within a preselected deviation of parallel. The altitude of the pyramid, i.e., a distance between the common vertex and an average plane (P_avg) of the triangles is compared with a preselected maximum height. Triangular groups which pass the surface normal and maximum height tests have their common vertex removed (72) and are retriangulated (74) to reduce the number of triangles by two. An image processor (84) converts the relative angles of viewing and illumination directions relative to the surface normal of each visible triangle into a corresponding image value, e.g. gray scale, for display on a video monitor (34).

Claims

1. In a medical diagnostic imaging apparatus which includes a patient examination apparatus for non-invasively examining an internal volumetric region of a patient and generating views of electronic data indicative thereof, a reconstruction processor for reconstructing the views into a volumetric image representation which is stored in an image memory, a triangular surface processor for replacing a surface of a selected volumetric region of the volumetric image representation in the image memory with a triangular mesh, an image processor for comparing (i) a viewing direction, (ii) an illumination direction and (iii) a surface normal of each viewable triangle of the triangular mesh to generate a corresponding image value, and an image display device for converting the image values into a corresponding human-readable image, the improvement comprising:

a vertex merging processor which collapses long, narrow triangles to lines such that long, narrow triangles of the triangular mesh that have a dimension smaller than a preselected minimum are collapsed into a straight line with their areas being split and merged into adjoining triangles; and

a vertex removal processor for removing a vertex shared by a plurality of triangles which are within a preselected tolerance of co-planar and retriangulating a polygon defined by the remaining peripheral vertices of the triangles with a smaller number of triangles, the vertex removal processor including;

a means for identifying a vertex common to a group of triangles which define a pyramid;

a means for determining an average plane of the vertices of the pyramid;

a means for comparing deviation among the surface normal of each viewable triangle of the pyramid for a preselected maximum deviation;

a means for determining a distance between the average plane and the common vertex to determine a height of the pyramid; and

a means for comparing the pyramid height with a preselected maximum pyramid height.

2. In a medical diagnostic imaging apparatus which includes a patient examination apparatus for non-invasively examining an internal volumetric region of a patient and generating views of electronic data indicative thereof, a reconstruction processor for reconstructing the views into a volumetric image representation which is stored in an image memory, a triangular surface processor for replacing a surface of a selected volumetric region of the volumetric image representation in the image memory with a triangular mesh, an image processor for comparing:

(i) a viewing direction, (ii) an illumination direction, and (iii) a surface normal of each viewable triangle of the triangular mesh to generate a corresponding image value, and an image display device for converting the image values into a corresponding human-readable image, the improvement comprising;

a means for identifying a vertex common to a group of triangles which define a pyramid;

a means for determining an average plane of the vertices of the pyramid;

a means for determining a distance between the average plane and the common vertex to determine a height of the pyramid;

a means for comparing the pyramid height with a preselected maximum pyramid height;

a means for removing the common vertex of the group of triangles which define each pyramid whose height is less than the preselected maximum pyramid height;

a means for projecting the peripheral vertices onto the average plane to define a planar polygon;

a means for retriangulating the planar polygon on the average plane; and

a means for connecting corresponding peripheral vertices in the image memory in accordance with the retriangulating on the average plane.

3. In an imaging system as which includes a memory for storing a volumetric image representation, a triangular surface processor for replacing a surface of a selected volumetric region of the volumetric image representation in the image memory with a triangular mesh, an image processor for comparing a viewing direction, an illumination direction and a surface normal to a plane of each visible triangle of the triangular mesh to generate a corresponding image value, and an image display device for converting the image values into a corresponding human readable image, the improvement comprising:

a vertex merging means for merqing triangles of the triangular mesh that have a dimension less than a preselected minimum dimension into adjoining triangles; and

a vertex removal means for removing a vertex shared by a plurality of triangles which are within a preselected tolerance of co-planar and retriangulating a polygon defined by remaining peripheral vertices of the triangles with a smaller number of triangles, the vertex removal means further including;

a means for identifying vertices common to a group of triangles which define a pyramid;

a means for determining said surface normals to a plane of each triangle of the identified group of triangles;

a means for determining for each pyramid an average plane of the triangles;

a means for determining for each pyramid a distance between the average plane and the common vertex to determine a height of the pyramid; and

a means for comparing each pyramid height with a preselected maximum pyramid height.

4. In the imaging system as set forth in claim 3, the improvement further comprising:

a means for removing the common vertex of the group of triangles which define each pyramid whose surface normals diverge less than the preselected divergence and whose height is less than the preselected maximum pyramid height;

a means for retriangulating peripheral vertices into a smaller number of triangles without a common vertex.

5. In an imaging systme which includes a memory for storing a volumetric image representation, a triangular surface processor for replacing a surface of a selected volumetric region of the volumetric image representation in the image memory with a triangular mesh, an image processor for comparing a viewing direction, an illumination direction and a surface normal of each visible triangle of the triangular mesh to generate a corresponding image value, and an image display device for converting the image values into a corresponding human readable image, the improvement comprising:

a means for removing a common vertex shared by a plurality of non-coplanar triangles defined by the common vertex and a plurality of peripheral vertices to create a three-dimensional polygon;

a means for projecting the peripheral vertices of the three-dimensional polygon onto a plane to define a two-dimensional polygon;

a means for triangulating the two-dimensional polygon projection on the plane in two dimensions; and

a means for connecting corresponding peripheral vertices of the three-dimensional polygon in the image memory in accordance with the two-dimensional triangulation of the two-dimensional polygon projection on the plane such that the peripheral vertices are three-dimensionally retriangulated.

6. An imaging system comprising:

an image memory which selectively stores a three-dimensional electronic image representation;

a triangular surface processor which replaces a selected surface or a surface of a selected volumetric region of the three-dimensional electronic image representation in the image memory with a mesh of triangular surfaces;

a vertex removal processor for removing a vertex shared by a plurality of triangular surfaces which are within a preselected tolerance of coplanar and without replacing the removed vertex retriangulating a polygon defined by remaining peripheral vertices of the triangular surfaces with a smaller number of triangular surfaces, whereby a number of the triangular surfaces in the mesh is reduced, the vertex removal processor including;

a means for identifying an apex vertex common to each group of triangular surfaces which define a pyramid,

a means for determining an average plane of the vertices composing each pyramid,

a means for determining a normal to each triangular surface defined by the mesh;

a means for determining deviation among the surface normals of the triangular surfaces of the pyramid,

a means for removing the apex vertex of a group of triangular surfaces which define a pyramid whose surface normals diverge less than a preselected divergence and whose height is less than a preselected maximum height to define a polygon,

a means for projecting the polygon onto the average plane,

a means for triangulating a polygon defined by peripheral vertices of each group after the apex vertex removal;

an image processor which compares viewing and illumination directions with the surface normals of the triangular surfaces of the mesh to determine a corresponding image value; and

an image display device for converting the image values into a corresponding human-readable image.

7. The imaging system as set forth in claim 6 further including:

a non-invasive examination apparatus for non-invasively examining a three-dimensional volume of a subject and generating views of electronic data indicative thereof; and

a reconstruction processor for reconstructing the views into the three-dimensional image representation for storage in the image memory.

8. The imaging system as set forth in claim 7 wherein the non-invasive examination apparatus includes one of a nuclear camera, a CT scanner, and a magnetic resonance imaging apparatus.

9. The imaging system as set forth in claim 6 further including:

a means for comparing a distance between adjoining pairs of vertices with a preselected minimum distance;

a means for calculating a median position between the pairs of vertices which are separatedby less than the preselected minimum distance, placing a new vertex at the median position, and removing the pair of vertices, whereby the triangular surfaces defined in part by vertices with less than the preselected minimum dimension are merged into adjoining triangular surfaces.

10. An imaging method comprising:

replacing a surface of a selected volumetric region of a volumetric image representation with a mesh of triangles;

identifying vertices common to a group of triangles which define a pyramid;

determining an average plane of the group of triangles;

comparing deviation among surface normals of the identified group of triangles that define the pyramid with a preselected deviation;

determining a distance between the average plane and the common vertex to determine the height of the pyramid;

comparing the pyramid height with a preselected maximum pyramid height;

removing the vertex common to each identified group of triangles whose surface normals deviate by less than the preselected deviation and whose pyramid height is less than the preselected maximum pyramid height;

projecting the peripheral vertices onto the average plane to define a planar polygon on the average plane;

triangulating the planar polygon on the average plane;

connecting the peripheral vertices which were projected onto the average plane in accordance with the triangulating of the planar polygon;

comparing viewing and illumination directions with the surface normal of each viewable triangle to generate a corresponding image value; and

converting the image values into a corresponding image.

11. An imaging method comprising:

replacing a surface of a selected volumetric region of a volumetric image representation with a triangular mesh;

merging triangles with a dimension less than a preselected minimum dimension into adjoining triangles, the merging step including;

comparing a distance between each pair of adjacent vertices with a preselected minimum distance;

calculating a median position between the adjacent vertices which are separated by less than the minimum distance;

placing a new vertex at the median position;

removing the pair of vertices;

removing a vertex shared by a group of triangles which are within a preselected tolerance of coplanar;

projecting the remaining vertices of the group of triangles onto a common plane;

on the common plane, retriangulating a polygon defined by projections of the remaining peripheral vertices of the group of triangles with a smaller number of triangles;

connecting the remaining peripheral vertices in accordance with the retriangulation on the common plane;

comparing viewing and illumination directions with a surface normal of each viewable triangle to generate a corresponding image value; and

converting the image values into a corresponding image.

12. The imaging method as set forth in claim 11 further including:

non-invasively examining an internal volumetric region of a patient and generating views of electrical data indicative thereof;

reconstructing the views into the volumetric image representation.