Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2002-07-19
2004-12-14
Nguyen, Phu K. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06831642
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer graphics.
2. Related Art
A wide variety of applications rely on computer graphics to generate images. An image is made up of an array of picture elements (pixels) and can be displayed on a display unit, such as, a monitor, screen, or cathode ray tube. Images often include graphical representations of objects. Many different types of computing devices with graphics capabilities are used to generate images. Such computing devices use graphics processing. A combination of software, firmware and/or hardware is used to implement graphics processing. For example, graphics processing including rendering can be carried out in a graphics card, graphics subsystem, graphics processor, graphics or rendering pipeline, and/or a graphics application programming interface (API) and libraries, such as, OPENGL.
In computer graphics, the geometry of an object is represented by primitives. Common primitives are points, lines, and polygons such as triangles or quads. Each primitive is made up of points called vertices. Each vertex includes information relating to the object and its graphical display as an image. For example, vertex information can include, but is not limited to, vertex coordinates, texture coordinates, an alpha value, and a depth value. Vertex coordinates define the location of a respective vertex in a three-dimensional coordinate space (x,y,z), such as, an object coordinate space or a world coordinate space. In this way, vertex coordinates define the geometry of an object surface. Texture coordinates are coordinates that map to an image in a two-dimensional space (s,t) or a three-dimension space (r,s,t). One way this image (also called a texture) is used in graphics processing is to provide additional surface detail to the object. An alpha value is used to represent transparency information. The depth value is used to define depth information.
Increasing demands are being made upon graphics processing. These demands include realism, speed and cost. Realistic images are desired to be rendered at real-time, interactive rates while avoiding burdensome graphics processing or hardware requirements. One way to achieve more realism is to use complex objects. Complex objects, however, can involve a large number of primitives. For example, hundred, thousands, or millions of triangles may be needed to represent complex objects. This increases the number of calculations and other processing work required to render the object.
One approach to accommodating these demands is to approximate geometric information by forming an object proxy. Conventional approaches to forming an object proxy, however, have been limited. For example, Buehler et al. describes use of geometric proxies based on a progressive hull technique described by Sander et al. See, Buehler et al., “Unstructured Lumigraph Rendering,” SIGGRAPH 2001, Los Angeles, Calif., August 2001 (pages 1-8); and Sander et al., “Silhouette Clipping,” SIGGRAPH 2000, New Orleans, La., July 2000 (pages 1-8). The progressive hull approach described in the Buehler and Sander articles has significant deficiencies. At the very least, the approach does not apply generally to all types of object shapes. This progressive hull approach cannot handle concave proxies, or objects that have parts close to each other or touching each other. In addition, this approach is not well suited for mixing image-based rendering (ibr) objects with regular scenes.
What is needed is a method and system for forming object proxies which can be used with all types of object shapes.
SUMMARY OF THE INVENTION
The present invention overcomes each of the above-identified problems and has additional advantages as described herein. The present invention provides a system, method and computer program product for forming object proxies. In one embodiment, a method forms an object proxy that approximates the geometry of an object. The method includes forming a volume that encompasses the object, forming an isosurface within the volume, adjusting the isosurface relative to a surface of the object, and pruning the isosurface to obtain the object proxy. The formed volume is made up of voxels that encompass the object. The isosurface forming step includes determining sets of vertices for the voxels such that the sets of vertices define polygons representing the isosurface at a first distance from the surface of the object.
According to a feature of the method of the present invention, the isosurface adjusting step includes adjusting at least some of the vertices of the isosurface until each vertex is at or near a second distance from the surface of the object. In one embodiment, each vertex is iteratively advanced by an amount based on a first distance, a second distance, and direction information.
According to a further feature, the isosurface pruning step includes pruning the isosurface based on a distance condition and an intersection condition. In one embodiment, a list of vertices of the isosurface is iteratively pruned. This pruning includes selecting a vertex, and determining whether the selected vertex can be eliminated from the isosurface based on a distance condition and an intersection condition. When a selected vertex can be eliminated, the vertex is eliminated and new edges are created using remaining vertices.
Another feature of the method includes a step of iteratively moving vertices in the initial object proxy closer to the surface of the object. In one example, after pruning to obtain an initial object proxy, the distance of a respective vertex to the object surface is computed. Each vertex of the initial object proxy is advanced toward the object surface until each vertex is on or near the object surface with no polygons deeper than a predetermined distance or until a predetermined number of iterations has been reached.
According to further feature, object proxy formation parameters can be user-specified and/or predetermined. These object proxy formation parameters include: a grid resolution (N
1
×N
2
×N
3
) representing the resolution of voxels in a volume, a first distance value (D
1
) representing the first distance between an initial isosurface and the object surface, a second distance value (D
2
) representing the distance between an initial object proxy obtained after pruning and the object surface, a third distance value (D
3
) representing the maximum allowed distance between a vertice in the isosurface and the object surface during pruning, and a fourth distance value (D
4
) representing a maximum depth for vertices from the object surface.
The present invention also provides an apparatus for forming an object proxy that approximates the geometry of an object. The apparatus includes an isosurface former that forms an isosurface within a volume encompassing an object, and an isosurface shaper that adjusts the isosurface relative to the surface of the object and prunes the isosurface to obtain the object proxy.
Other embodiments include a system and a computer program product. The system forms an object proxy that approximates the geometry of an object. The system includes: means for forming a volume that encompasses the object; means for forming an isosurface within the volume; means for adjusting the isosurface relative to a surface of the object; and means for pruning the isosurface to obtain the object proxy. The computer program product includes computer usable media having computer readable program code embodied in said media for causing a processor to form an object proxy. The computer readable program code has first program code that enables the processor to form a volume that encompasses the object; second program code that enables the processor form an isosurface within the volume; third program code that enables the processor to adjust the isosurface relative to a surface of the object; and fourth program code that enables the processor to prune the isosurface to obtain the object proxy.
The present invention has general application as it can be
Nguyen Phu K.
Silicon Graphics Inc.
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Method and system for forming an object proxy 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 system for forming an object proxy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for forming an object proxy will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304884