Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-04-26
2004-06-01
Arnold, Adam (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S615000, C345S616000, C382S154000, C382S260000, C382S265000
Reexamination Certificate
active
06744435
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to computer graphics, and more particularly to rendering three-dimensional volume and point-sample data with splatting methods.
BACKGROUND OF THE INVENTION
Laser range and image-based scanning can produce complex and visually stunning three-dimensional (3D) images. However, scanning produces a huge number of point-samples. Hereinafter, a point-sample is defined as a zero-dimensional point in space having (x,y,z) coordinates. Typically, the point-samples do not have connectivity information. That is, the point-samples are not related or linked. This makes it difficult to render point-samples as images.
One common way to connect the point-samples is with polygon (triangle) meshes, and then to render the meshes. However, some meshes are too large to be rendered interactively, and many applications cannot tolerate the inherent loss in geometric accuracy and texture fidelity that comes from polygon reduction. Recent efforts have focused on direct rendering of unconnected point-samples. These techniques use hierarchical data structures and forward warping to render the point-samples efficiently.
One important challenge for point rendering is to properly reconstruct an image of a continuous surface from irregularly spaced point-samples. The image must be correct, and independent of the order in which the point-samples are rendered. Very often, the point-samples must appear as a continuous opaque or translucent surface while maintaining the high texture fidelity of the scanned data. In addition, point rendering should correctly handle hidden surface removal and transparency.
In the prior art, texture mapping is frequently used to “fill-in” the surface areas between the point-samples. Texture mapping increases the visual complexity of models by mapping functions for color, normals, or other material properties onto the model surfaces. If these texture functions are inappropriately band-limited, texture aliasing may occur during the projection to raster images. In addition, texture mapping is mostly used for surface rendering. Volume rendering is important for visualizing acquired and simulated data sets in scientific and engineering applications. Volume rendering reconstructs a 3D function from discrete sample points, transforms the 3D function into screen space, and then evaluates opacity integrals along line-of-sights, called “rays.”
In interactive volume rendering, splatting approximate this procedure, see Westover “Interactive Volume Rendering,” Upson, editor,
Proceedings of the Chapel Hill Workshop on Volume Visualization
, pages 9-16, University of North Carolina at Chapel Hill, Chapel Hill, N.C., May 1989. Westover does not deal with aliasing problems, which lead to noticeable artifacts such as jagged silhouette edges and Moiré patterns in textures.
With splatting, the volume data is interpreted as a field of 3D reconstruction kernels, one kernel for each particle, voxel, or discrete sample point. Each 3D reconstruction kernel absorbs and emits light. Integrals are predetermined separately across each 3D kernel, resulting in “footprint” functions. Each footprint function “spreads” the contribution of each point over nearby pixels in the image. Typically, the span of the footprint is in the order of two to five pixels. The “smeared” contributions of each discrete sample point of the 3D volume are composited, i.e., accumulated, in a front-to-back or back-to-front order to produce the pixels of the output image.
Prior art splatting suffers from inaccurate visibility determination when compositing the splats in the back-to-front order. This leads to visible artifacts such as color bleeding. This problem can be solved by using an axis-aligned sheet buffer, see Westover “Footprint Evaluation for Volume Rendering,”
Computer Graphics
, Proceedings of SIGGRAPH 90, pages 367-376, 1990. However, that solution produces disturbing “popping” artifacts in animations.
Popping is the term used to describe discontinuous intensity changes between subsequent images in the animation sequence. The sheet buffer can also be aligned parallel to the image plane, see Mueller et al. “Eliminating Popping Artifacts in Sheet Buffer-Based Splatting,”
IEEE Visualization
'98, pages 239-246, 1998. They also splat several slices of each 3D reconstruction kernel separately. Their technique is similar to slice-based volume rendering, and does not suffer from popping artifacts.
Splatting can be combined with ray casting techniques to accelerate rendering with perspective projection. Hierarchical splatting allows progressive refinement during rendering. Furthermore, splatting can also be applied on a volume data set represented as wavelets.
Aliasing artifacts may occur in areas of the volume where the sampling rate along diverging rays falls below the volume grid sampling rate. A distance-dependent function can “stretch” the footprints to make them act as low-pass filters, see Swan et al. “Anti-Aliasing Technique for Splatting,”
Proceedings of the
1997
IEEE Visualization Conference
, pages 197-204, 1997. Swan adjusts the size of the footprints according to the distance between the samples and the image plane. Swan is distinguished in greater detail below.
Additional care has to be taken when the 3D reconstruction kernels are not radially symmetric, as is the case for rectilinear, curvilinear, or irregular grids. In addition, for an arbitrary position in 3D space, contributions from all kernels must sum up to one. Otherwise, artifacts such as splotches occur in the image. For rectilinear grids, elliptical footprints can be warped to a circular footprint, see Westover “Interactive Volume Rendering,” Upson, editor,
Proceedings of the Chapel Hill Workshop on Volume Visualization
, pages 9-16. University of North Carolina at Chapel Hill, Chapel Hill, N.C., May 1989. To render curvilinear grids, a stochastic Poisson resampling can generate a set of new points whose footprints are spheres or ellipsoids, see Mao “Splatting of Non Rectilinear Volumes Through Stochastic Resampling,”
IEEE Transactions on Visualization and Computer Graphics
, 2(2):156-170, 1996.
Heckbert, in “Fundamentals in Texture Mapping and Image Warping” Master's Thesis, University of California at Berkeley, Department of Electrical Engineering and Computer Science, 1989, describes a rendering method that uses elliptical weighted average (EWA) filters to avoid aliasing of surface textures. However, that method only operates on 2D regularly sampled texture. In other words, that method can not be used directly with irregular point samples or volume data sets.
Therefore, there is a need for a splatting method that can render a volume data set including irregularly spaced sample points without blurring, aliasing, popping, and other annoying artifacts present with prior art splatting techniques.
SUMMARY OF THE INVENTION
The present invention provides a novel rendering method that combines the projection of an elliptical 3D Gaussian reconstruction kernel function with a elliptical 2D Gaussian low-pass filter to produce a single splat primitive a screen space, that is an EWA continuous resampling filter. This 2D EWA resampling filter can be applied directly to discrete sample points in screen space. The EWA resampling filter according to the invention prevents aliasing artifacts and excessive blurring in the image. Moreover, the invention works with arbitrary elliptical 3D Gaussian reconstruction kernels and arbitrary Gaussian low-pass filter functions, and efficiently supports rectilinear, curvilinear, and irregular volumes, and perspective projection.
The method according to the invention is based on a novel framework to determine the continuous 2D EWA resampling filter. Effectively, the method transforms the volume data set, or any other set of discrete sample points defined in object space, first to camera space, then to ray space, and finally to screen space. This transformation is equivalent to a projection, e.g. a perspective or orthonormal projection. By using a local affine
Baar Jeroen van
Gross Markus H.
Pfister Hanspeter
Zwicker Matthias B.
Arnold Adam
Brinkman Dirk
Curtin Andrew
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Rendering discrete sample points projected to a screen space... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rendering discrete sample points projected to a screen space..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rendering discrete sample points projected to a screen space... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3321247