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

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.

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.

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.

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.

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.

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.