Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-09-01
2002-01-29
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S419000, C345S619000
Reexamination Certificate
active
06342886
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to graphics systems, and more particularly, to interactively modeling graphic objects that are represented by connected zero-dimensional points.
BACKGROUND OF THE INVENTION
In computer graphics, one can represent objects in 3D space in many different ways using various primitive graphic elements. The known representations that are commonly used to represent graphic objects are implicit, geometric, volumetric, and particle.
Implicit
In an implicit representation, the graphic object can be generated from arbitrary mathematical and/or physical functions. For example, to draw the outline of a hollow sphere one simply supplies the rendering engine with the function (in Cartesian coordinates) x
2
+y
2
+z
2
=r, and for a solid sphere the function is x
2
+y
2
+z
2
≧r. Color and other material properties can similarly be synthetically generated. Functions can be used to describe various geometric shapes, physical objects, and real or imaginary models. Implicit functions are not suitable for synthesizing complex objects, for example, a human figure.
Geometric Representation
Classically, 3D objects have been geometrically modeled as a mesh of polygonal facets. Usually the polygons are triangles. The size of each facet is made to correspond to the degree of curvature of the object in the region of the facet. Many polygons are needed where the object has a high degree of curvature, fewer for relatively flat regions. Polygon models are used in many applications, such as, virtual training environments, 3D modeling tools, and video games. As a characteristic, geometric representations only deal with the surface features of graphic objects.
However, problems arise when a polygon model is deformed because the size of the facets may no longer correspond to local degrees of curvature in the deformed object. Additionally, deformation may change the relative resolution of local regions. In either case, it becomes necessary to re-mesh the object according to the deformed curvature. Because re-meshing (polygonization) is relatively expensive in terms of computational time, it is usually done as a preprocessing step. Consequently, polygon models are not well suited for objects that need to be deformed dynamically.
Volumetric Representation
In an alternative representation, the object is sampled in 3D space to generate a volumetric data set, for example, a MRI or CT scan. Each sample is called a voxel. A typical data set may include millions of voxels. To render a volumetric data set, the object is typically segmented. Iso-surfaces can be identified to focus on specific volumetric regions. For instance, a volumetric data set of the human head may segment the voxels according to material properties, such as bone and soft tissue.
Because of the large number of voxels, physically-based modeling and the deformation of volumetric data sets is still a very computationally expensive operation. Often, one is only interested in surface features, and the interior of the object can effectively be ignored.
Particle Representation
A particle representation of objects is often used to model fluid flows, for example, in wind tunnel simulations. Certain attributes, such as orientation velocity, are given to particles in order to track individual particles through the fluid flow, or to visualize the complete flow.
Another application of particle representation is in the visualization of “cloud like” objects, such as smoke, dust or mist. A shading model can be applied to particles that emit light to render cloud like objects. Also, particles can be constrained to subspaces with the help of energy functions to model surfaces. An advantage of particle clouds is that the clouds are very deformable. As a disadvantage, the particles in the cloud are unconnected and behave individually when exposed to forces. Furthermore, particles are quite unsuitable to represent surface structures of solid objects or models.
Modeling Considerations
A number of techniques are known for non-physical and physical modeling of graphic objects in the various representations. Non-physically based models often use splines, Bezier curves, and the like. There, control points are manipulated to achieve the desired degree of deformation.
The physical techniques generally fall into two categories, rigid body mechanics, and dynamic deformation. Rigid body mechanics usually solve differential equations that follow from Newtonian mechanics. In computer systems, numerically integrators can be used to solve the differential equations. Dynamic deformation can be modeled by finite element methods (FEM), or mass-spring systems.
Rendering Considerations
The rendering time for these conventional primitives depends on the complexity of the objects modeled. For example, with a geometric representation of a complex object, the polygons are typically very small in size, about the size of a pixel, and the object is represented by many polygons. The polygons are usually represented with vertices that define a triangle.
To render a polygon, the projection of the triangle is scan-converted (rasterized) to calculate the intensity of each pixel that falls within the projection. This is a relatively time consuming operation when about one pixel or less is covered by the polygon. Replacing the polygons with point samples and projecting the point samples to the screen can be a more efficient technique to render objects.
A number of techniques are known for rendering volumes. In general, volume rendering is quite complex. Unless the number of voxels is limited, real-time rendering can be time consuming.
A real-time rendering system, described in U.S. Pat. No. 5,781,194 “Real-time Projection of Voxel-based Object,” issued to Ponomarov et al. on Jul. 14, 1998, constructs a chain of surface voxels using incremental vectors between surface voxels. That representation succeeds in modeling and displaying objects showing highly detailed surface regions. The modeling of rigid body motion is done with the aid of scripting mechanisms that lacks realism because physically-based methods are not used. This approach does not include the possibility of realistic deformation of objects. The objects act as rigid bodies in space that are unresponsive to collisions and other deforming forces.
In the prior art, discrete particles or points have been used as a meta-primitive in graphic systems, see, Levoy et al, “The Use of Points as a Display Primitive,” University of North Carolina Technical Report 85-022, 1985. They described a process for converting an object to a point representation. There, each point has a position and a color. They also describe a process to render the points as a smooth surface.
The points are modeled as zero-dimensional density samples and are rendered using an object-order projection. When rendering, multiple points can project to the same pixel and the intensities of these points may need to be filtered to obtain a final intensity for the pixel under consideration. This filtering is done by weighing the intensity proportional to the distance from the projected point position on the screen to the corresponding pixel-center. The weighing is modeled with a Gaussian filter. An enhanced depth-buffer (Z-buffer) allows for depth comparisons with a tolerance that enables the blending of points in a small region of depth-values. As an advantage, their point representation allows one to render the object from any point of view.
In another technique, as described by Grossman et al. in “Sample Rendering,” Proceedings of the Eurographics Workshop '98, Rendering Techniques 1998, Drettakis, G., Max, N.(eds.), pages 181-192, July 1998, the point samples are obtained by sampling orthographic projections of triangle meshes on an equilateral triangle lattice. For each triangle of the lattice that is covered by the projection of the triangle mesh, a sample point is added. An equilateral triangle lattice was chosen to provide an adequate sampling which is dense enough to guarantee that each pixel i
Baar Jeroen van
Oosterbaan Collin E.
Pfister Hanspeter
Brier Jeffery
Brinkman Dirk
Harrison Chante
Mitsubishi Electric Research Laboratories, INC
LandOfFree
Method for interactively modeling graphical objects with... 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 for interactively modeling graphical objects with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for interactively modeling graphical objects with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2856690