Surface simplification preserving a solid volume

Details Surface simplification preserving a solid volume Surface simplification preserving a solid volume

1999-01-04

2002-07-02

Zimmerman, Mark (Department: 2671)

Computer graphics processing and selective visual display system

Computer graphics processing

Adjusting level of detail

C345S419000

Reexamination Certificate

active

06414683

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates generally to computer graphics systems, and, particularly, to computer graphics systems that provide real-time interactive and/or scientific visualization of complex geometric models.
2. Description of the Related Art
Traditional computer graphics systems are used to create a model of three-dimensional objects and render the model for display on a two-dimensional display device such as a cathode ray tube or liquid crystal display. Typically, the three-dimensional objects of the model are each represented by a multitude of polygons (or primitives) that approximate the shape of the object. The primitives that define an object are typically defined by coordinates in a local coordinate system. For example, one of the primitives that may be used to define an object is a triangle, which is defined by the coordinates of three vertices in the local coordinate system.
Such polygonal surfaces may be sued for generating pictures and animations, and may also be used in scientific visualization, in geometric computing as well as in medical imaging. More specifically, polygonal surfaces have been used for measuring volumes, for aligning three dimensional scans such as Computed Tomography or Magnetic Resonance scans, or for finite element applications. IBM Visualization Data Explorer is an example of software that generates and visualizes polygonal surfaces.
The rendering of a polygonal surfaces is divided into two stages: geometry processing and rasterization. Geometry processing typically includes a modeling transformation, lighting calculations, a viewing transformation, a clipping function, and viewport mapping. The modeling transformation transforms the primitives from the local coordinate system to a world coordinate system. The lighting calculations evaluate an illumination model at various locations: once per primitive for constant shading, once per vertex for Gouraud shading, or once per pixel for Phong shading. The viewing transformation transforms the primitives in world coordinates to a 3D screen coordinate system (sometimes referred to as the normalized projection coordinate system). The clipping function determines the primitives (or portions of the primitives) that are within the viewing frustrum. And viewport mapping maps the coordinates of the clipped primitives to the normalized device coordinate system (sometimes referred to as the 2D device coordinate system).
Rasterization is the process which converts the description of the clipped primitives generated during geometry processing into pixels for display. A typical primitive, as shown in
FIG. 1A
, is a triangle T
1
. Other area or surface primitives conventionally are converted into one or more triangles prior to rasterization. Consequently, the conventional rasterization process need only to handle triangles. The triangle T
1
is represented by the (x, y, z) coordinates at each of its vertices. The (x, y) coordinates of a vertex tell its location in the plane of the display. The z coordinate tells how far the vertex is from the selected view point of the three-dimensional model. Rasterization is typically divided into three tasks: scan conversion, shading, and visibility determination.
Scan conversion utilizes the (x, y) coordinates of the vertices of each triangle to compute a set of pixels S which is covered by the triangle. Shading computes the colors of the set of pixels S covered by each triangle. There are numerous schemes for computing colors, some of which involve computationally intensive techniques such as texture mapping. Shading typically utilizes the lighting calculations described above with respect to geometric processing.
Visibility determination utilizes the z coordinate of each triangle to compute the set of pixels S
v
(a subset of S) which are “visible” for the triangle. The set S
v
will differ from the set S if any of the pixels in set S are covered by previously rasterized triangles whose z values are closer to the selected view point. Thus, for each triangle in the model, a pixel is “visible” if it is in the set S
v
or “hidden” if it is the set S but not in the set S
v
. Moreover, a triangle is “all visible” if the set S
v
is identical to set S, “partially hidden” if the set S
v
is not identical to set S and set S
v
is not empty, or “all hidden” if set S
v
is empty. For example,
FIG. 1B
shows two triangles, triangle T
1
and T
2
, wherein triangle T
1
is partially hidden by triangle T
2
. Visibility determination is traditionally accomplished using a z-buffer technique. The Z-buffer stores an entry for each pixel that represents the z-value of the visible primitive at the given pixel. The z-value (Znew) of a set of pixels covered by a given triangle is determined through interpolation. For each pixel within the set, Znew at the given pixel is compared to the z-value (Zold) stored as an entry in the Z-buffer corresponding to the given pixel, and the entry Zold is updated with Znew according to results of the compare operation.
Rasterization is completed by writing the colors of the set of visible pixels S
v
to an image buffer for display.
As models become more and more complex, traditional rendering techniques are too computationally intensive for many graphics systems and result in degraded performance. For example, it is not rare in medical imaging applications that a surface may contain hundreds of thousands of triangles. In such a case, traditional rendering techniques are not sufficient using current computer hardware and software. In order to solve this problem, several simplification techniques have been developed that construct an approximation of the original surface, and thus reduce the level of detail of the graphical representation of the surface.
An example of such simplification techniques is described Kalvin et al. “Superfaces: Polygonal Mesh Simplification with Bounded Error”, Computer Graphics and Applications, Vol. 16, No. 3, May 1996, pp.64-77, Cohen et al., “Simplification Envelopes”, ACM SIGGRAPH 96, August 1996, Addison Wesley, pp. 119-128, and Ronfard et al., “Full-Range Approximation of Triangulated Polyhedra”, Computer Graphics Forum, Vol. 15, 1996, pp.67-76. All three algorithms do not undo any simplification that was previously made.
The simplification technique of Kalvin et al. attempts to merge surface triangles to quasi-planar “superfaces”. Each original triangle is merged with one superface, possibly limited to one single triangle. Each superface is guaranteed to lie within a given distance to the triangles that were merged into the superface. However, because the algorithm does not give priorities to triangles before merging them, the algorithm does not produce economical simplifications for a given amount of processing time. In addition, the algorithm does not preserve the volume of a solid. Finally, the algorithm does not attempt to optimize the aspect ratios of triangles.
The simplification technique of Cohen et al. begins by constructing an envelope around the original surface, whose width corresponds to the maximum distance that is allowed between the simplified surface and the original surface. The envelope does not intersect itself. The surface vertices are then selected as candidates for removal and the hole left by the vertex removal is triangulated. The simplification algorithm ends when no more removal is possible. A verification process verifies that each new triangle is inside the envelope and that it does not intersect other surface triangles. This algorithm is computationally intensive and does not preserve the volume of a solid.
The simplification technique of Ronfard et al. places the edges of the surface in a priority queue, ordered by a key that measures the approximation error after the edge collapse. Until the key exceeds a user specified value, the edge with the highest priority is collapsed. This algorithm is computationally intensive because each time an edge collapse is performed, the simplification error must be re-estimated for each edge that was adjacent to the

Affiliated with

Also associated with

Rating

Surface simplification preserving a solid volume does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Surface simplification preserving a solid volume, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Surface simplification preserving a solid volume will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2827941