Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-08-11
2003-04-29
Jankus, Almis R. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06556199
ABSTRACT:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in its Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method and apparatus for converting three dimensional data and computer models into discrete representations and displaying the resulting discrete representation on a two-dimensional display, and more particularly to a method and apparatus for real-time voxelization of three dimensional data and subsequent real-time volume rendering.
2. Related Art
Broadly speaking, three-dimensional (3D) objects tend to have different characteristics depending on their origins as either synthetic objects or empirical objects. Typical synthetic objects include computer-aided design (CAD) models, computer-aided manufacturing (CAM) models and other computer-spawned entities. Typical empirical objects include computerized tomography (CT) and magnetic resonance imaging (MRI) 3D images formed from two-dimensional (2D) “slices” of empirical measurements. Typically, synthetic 3D objects are represented as 3D models. These 3D models typically reside in the memory of a computer, such as a graphics workstation or a personal computer. Typically, empirical objects are represented as volume data. These volume data typically reside in an embedded controller or computer in the device that obtained the data or in a separate computer such as a workstation or a personal computer. In many real world applications, these two types of objects need to interact (e.g., in a medical simulation where a body part is represented by empirical MRI volume data while the “scalpel” is a synthetic model). Typically, the results of their interaction need to be displayed on a 2D monitor. (The process of displaying a 3D object in 2D space is called rendering.)
Volume data are 3D objects from many possible sources, including synthetic objects (e.g., a CAD model) or “real world” objects, such as a sequence of CT or MRI slices. In operation, data representing the volumetric objects is stored in a volume buffer of voxels (the 3D analog to pixels in 2D). Typically volume data are used to manipulate, render and display 3D objects in two related areas, volume graphics and volume visualization. Volume graphics deals with the synthesis, modeling, manipulation, rendering and display of volumetric geometric objects. Volume visualization uses interactive graphics and imaging to extract and display useful information from volumetric data.
Recent advances in volume visualization and volume-based graphics techniques have made volume graphics a potential new paradigm for the next generation computer graphics technology. One of the main obstacles for volume graphics to achieve this goal, however, is its limited support to the modeling operations of volumetric and geometric objects.
Historically, the need for direct interaction with 3D objects, such as interactive object manipulations and design, has been an important driving force for modern 3D computer graphics. A very rich set of surface graphics techniques and algorithms have been developed to provide interactive graphical display support for applications such as solid modeling and animation. In order to achieve and even surpass the capabilities of traditional surface graphics, volume graphics needs to provide efficient rendering support for applications involving dynamic volumetric scenes and interactive manipulations and operations of volumetric and geometric objects. A good background discussion of the field of volume visualization are the seminar notes found in “Volume Visualization: Principles and Advances” by Dr. Arie E. Kaufman, Center for Visual Computing and Computer Science Department, State University of New York at Stony Brook, August, 1997, and incorporated herein by reference.
There are two main approaches to displaying volumetric 3D objects on a 2D display, surface rendering and volume rendering. Surface rendering uses geometric primitives to approximate a surface contained in the volumetric data. The geometric primitives can then be rendered (i.e., turned into 2D images) using conventional graphics accelerator hardware. This approach, however, has a few significant drawbacks. First, the use of geometric primitives is only an approximation, and one that may require a prohibitive number of such primitives to adequately approximate the object represented by the volumetric data. Moreover, certain objects (e.g., clouds, and fog) cannot be adequately represented using geometric primitives. Second, since the geometric primitives represent only the surface of the object, the geometric primitives do not convey any information contained within the object.
In contrast, volume rendering converts volumetric data directly into a 2D image, without the intermediate step of generating geometric primitives. This approach overcomes the disadvantages of the surface rendering approach outlined above, including preserving the volumetric data within the object. At present there are a number of volume rendering techniques that approach real time speeds through a combination of commercially available graphics Applications Programming Interface (API) software and graphics accelerator hardware.
In a volume representation, a scalar volume is a scale field sampled over a 3D regular grid in a regular volume space. A scalar value (i.e., intensity) is defined at each grid point representing a certain property (e.g., density) of the object at this point. The small cuboid formed by eight neighboring grid points is called a voxel. Thus, the intensity value of any point within a voxel can be obtained by trilinear interpolation from the eight vertices of the voxel. A binary volume is a volume having only 0 or 1 intensity values, with 1 representing a point inside an object and 0 representing a background point (i.e., a point outside the object).
The process of converting a 3D model into a volume representation is called voxelization. Conceptually voxelization (i.e., 3D scan conversion) can be considered as a set membership classification problem for all voxels in a regular volume against the given 3D model. It can also be considered as a 3D extension of the 2D scan conversion process, such as the polygon scan conversion algorithms widely used in computer graphics. Although hardware and software solutions for fast volume rendering have been developed for regular volume representations, voxelization algorithms that generate the volume representations from complex geometric and volumetric models are still too slow to support interactive modeling operations.
Several important theoretical issues have been addressed by experts in the computer graphics field. These issues include accuracy, separability (or tunnel-free) and minimality. However, the important issue of voxelization speed has heretofore received very little attention. As a result, existing voxelization algorithms, while generally adequate, are slow and not able to provide interactive feedback for object operations. In addition, existing algorithms are object-type specific. That is, a different algorithm needs to be employed for each different type of object (e.g., lines, circles, polygons, quadratic surfaces, etc.), making the implementation of a general volume graphics application difficult.
Broadly speaking, the existence of curve and surface voxelization algorithms aim to provide efficient ways to extend 2D scan conversion methods to a volumetric domain. This requires additional sampling in the third dimension for each scan line. One important difference between 2D scan conversion and voxelization is that voxelization is decoupled from the rendering process, and is therefore only done once each time the model is modified. Even so, fast voxelization is still a requirement for interactive systems whe
Chen Hongsheng
Fang Shiaofen
Advanced Research and Technology Institute
Gridley Doreen J.
Jankus Almis R.
Miller Ice
Sealey Lance W.
LandOfFree
Method and apparatus for fast voxelization of volumetric models does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for fast voxelization of volumetric models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for fast voxelization of volumetric models will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3006500