Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-12-22
2002-05-21
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06392646
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a solution for the local minimum length path drawn on the surface of a polyhedron opened or closed surface.
Three-dimensional surface renderings have commonly been made using a constant triangular mesh over the surface of interest. That is, a surface of interest of a computer-generated three-dimensional image representation is selected. For example, one might use a nuclear, CT (computerized tomography) scanner, or other diagnostic imaging device to generate a three-dimensional image representation of a portion of a patient's torso surrounding the liver. Using conventional techniques, such as comparing the gray scale or CT number of each pixel in the image with a characteristic gray scale or CT number for the liver, one can identify the liver and the surface of the liver. Because all of the liver surface tissue has substantially the same gray scale or CT number, if a perspective view of the liver were re-created and displayed on a video monitor, the resultant display would have the appearance of a silhouette. There would be substantially no surface texture information conveyed.
In order to convey contour information, the surface of the liver or other structure which is visible from a viewing direction is overlaid with a constant triangular mesh. That is, the surface of the liver or other object of interest is approximated by a mesh of triangles of as uniform a size as permitted by the surface texture. In a typical 512 times 512 frame for a medical diagnostic image, one might expect to find about 20,000-50,000 triangles on the surface of interest. The vector surface normals are each compared with an illumination direction vector and a viewing direction vector. Based on the vector comparison, a gray scale (or color or hue) for each triangle is selected. Typically, the gray scales are selected to approximate the lighting and shading conditions that an object of the selected configuration would have at the corresponding point on the surface when viewed from the viewing direction and illuminated from the illumination direction.
The display may represent more than just the surface of the object. In particular, one can commonly define a cut plane on a medical diagnostic image and remove the portion of the object to one side of the cut plane. The portions of the image corresponding to the interior of the liver or other object of interest are displayed with appropriate gray scales or colors which correspond to the CT numbers or pixel values of each internal pixel of the liver or other structure that is intercepted by the slice. The remaining surface portion continues to be displayed with three-dimensional surface rendering.
Typically, the operator has the ability to rotate the displayed object. Each time the object rotates an incremental distance, the surface normals are again computed and compared with the illumination and viewing direction vectors and reassigned gray scale values to each triangle in accordance with the comparison. The large number of calculations necessary to reassign the gray scales are commonly performed slowly relative to the rotation rate of the object. That is, the operator rotates the object faster than the new gray scales can be computed, causing the object to appear to rotate in jumps, rather than smoothly. For example, if an object rotates about 5 degrees in the time necessary to recalculate the gray scale values, then the object appears to rotate in 5-degree steps.
“Decimation of Triangle Meshes” by Schroeder, et al., Computer Graphics, Vol. 26, No. 22, pgs. 65-70, July 1992, describes an algorithm which reduces the number of triangles required to model a physical or abstract object. In the Schroeder technique, multiple passes are made over an existing triangular mesh, using local geometry and topology to remove vertices that pass a distance or angle criterion. Holes left by the vertex removal are patched using a local triangulation process. One difficulty with the Schroeder technique is that it is relatively slow. Running time for the technique is on the order of minutes. Commonly, radiologists expect to review CT, nuclear camera and magnetic resonance images substantially in real time and do not find waiting on the order of minutes acceptable. Arata U.S. Pat. No. 5,689,577, issued Nov. 18, 1997, teaches an improved three-dimensional triangle mesh simplification technique which overcomes the above referenced problems.
A common problem in computational science is the need to represent the geometry of an object or the structure of data. One method for representing such objects is to use a polygonal mesh. A system and method that generates a large polygonal mesh is described in Cline et al. U.S. Pat. No. 4,710,876, issued Dec. 1, 1987, and assigned to the instant assignee. Other techniques, such as automatic mesh generation or terrain mapping from satellite data, are also capable of generating large polygonal meshes. For example, the complex, curved surface of a human tooth can be approximated by using many thousands of triangles (or other polygon types) joined along their common edges. The ability to represent geometry is important for many reasons. In computer graphics, polygonal meshes are used in the lighting and shading operations to generate images. Polygonal meshes are used in numerical analyses to represent the boundary of solid objects. From these representations, equations can be developed to solve such complex problems as heat flow, structural response, or electromagnetic propagation. Another application is in geometric modeling, where polygonal meshes are often used to determine object mass, volume, surface area, center of gravity, and moments of inertia.
In the past, polygonal meshes were typically comprised of hundreds to thousands of polygons, and computer hardware and software has been designed to process the volumes of information obtainable therefrom. However, recent advances in computational science have resulted in techniques that generate hundreds of thousands or even millions of polygons. Such large numbers, while capturing the geometry of the object very precisely, often overwhelm computer systems. For example, most graphics systems presently are incapable of rendering a million polygons at a speed that is not detrimental to interactive computation.
The basic problem is that techniques that generate large polygonal meshes are extremely valuable and cannot be easily modified to produce fewer polygons. Hence a general technique for reducing, or decimating, a mesh composed of a large number of polygons to one containing fewer polygons is necessary. Furthermore, the decimation process, to be effective, must preserve the topological and shape properties of the original polygonal mesh.
Zarge et al. U.S. Pat. No. 5,590,248 (the '248 patent), issued Dec. 31, 1996 and assigned to the instant assignee, teaches a method for reducing the complexity of a polygonal mesh while preserving the topological properties and shape of the original mesh. By this method, each vertex in the mesh is analyzed to determine if it is superfluous and is removed along with all of the triangles connected to it if it is superfluous. The polygon created by removing a vertex is filled (retriangulated) with new triangles according to an algorithm disclosed herein. The method further includes the step of removing triangles (consolidation) from the mesh if the triangles are relatively small compared to neighboring triangles. The method also includes removal of edges from the mesh if those edges are relatively short as compared with neighboring edges.
The '248 patent is implemented as a computer programmed to perform the method steps disclosed. The program allows a user to specify various thresholds therein disclosed to control the representational accuracy of the resulting mesh. The program may also be run in an iterative fashion until a desired reduction in mesh complexity has been achieved.
The aforementioned U.S. Pat. No. 4,710,876 (the '876 patent) is generally directed to a system and method for di
Alyassin Abdalmajeid Musa
Yamrom Boris
Cabou Christian G.
General Electric Co.
Ingraham Donald S.
Vo Cliff N.
LandOfFree
Iterative determination of the shortest path between two... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Iterative determination of the shortest path between two..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Iterative determination of the shortest path between two... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2902400