Computer graphics processing and selective visual display system – Computer graphics processing – Graphic manipulation
Reexamination Certificate
1999-08-16
2002-03-12
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graphic manipulation
C345S421000
Reexamination Certificate
active
06356280
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention pertains to the field of 3D image construction.
Creating 3D objects in computer graphics is a complex task, which usually requires special equipment and tools. Conventionally, high quality 3D objects are created in two stages: at the first stage, the geometry is created and at the second stage, this geometry is digitally painted or texture mapped. Both stages are time consuming and expensive. This is typically accomplished using a 3D graphics pipeline.
U.S. patent application Ser. No. 09/361,470, filed Jul. 27, 1999, incorporated herein by reference in its entirety, describes a method and apparatus for receiving a 2D image, generating a 3D geometry, and digitally painting the 2D image over that 3D geometry. It is possible for the method of our '470 Application to result in certain unnecessary or anomalous geometric features. The present invention pertains to a method for excising those features.
In order to facilitate an explanation of the present invention, we will first describe how a 3D graphics pipeline generates a 3D image. We will then describe a method in accordance with the '470 Application for taking a 2D image and generating in response thereto a 3D image. We will then describe a method in accordance with the present invention for removing undesired geometric elements generated during the method in accordance with the '470 Application.
Description of a 3D Graphics Pipeline
The following is a simplified, general description of 3D graphics pipelines. It is not intended to describe any specific product (e.g. products mentioned later in this patent). Rather, the following description is merely a general explanation of 3D graphics pipelines to assist the reader's understanding.
Currently, when creating an image of an object with a 3D graphics pipeline, one provides as inputs to the pipeline a set of geometric surfaces and a “texture” that is used to “paint” the geometric surfaces. One way of constructing a geometric surface in a graphics pipeline is to create a “mesh” of “primitives.” A “primitive” is a small geometric surface that can be defined by a set of vertices. For example, the primitive can be a polygon (e.g. a triangle or quadrilateral) defined within the pipeline in terms of the locations (in x, y and z coordinate space) of its comers or vertices. A set of primitives is used to define a larger 3D surface.
A 3D graphics pipeline constructs a 3D image of an object from a 2D texel array (typically called a “texture map”).
FIG. 1A
illustrates a 2D image
2
of a set of “textures.” (As will be explained below, this texture map is used to create the image of an object—in this case, a house. Image
2
includes a portion
2
a
, which has the appearance of bricks, portion
2
b
, which has the appearance of roof shingles, portion
2
c
, which has the appearance of a door, and portion
2
d
which has the appearance of a window.) 2D image
2
is stored in a digital memory in the form of an array of texels. Each location in the memory stores a texel, which is one or more words of data indicating the color, color saturation and brightness corresponding to that texel. The location of the texels within the array is typically referred to as u, v coordinates (not to be confused with the Y, U and V signal names used to describe certain video signals). The u, v coordinates are similar to x, y coordinates of the Cartesian coordinate system. In
FIG. 1A
, the texel array is an n by m array, where n and m are integers.
As mentioned above,
FIG. 1A
represents a texel array. Physically, the array comprises data loaded into a memory. The texel array is not displayed as such on a CRT. Rather, as explained below, the texel array is used to create an image that is eventually displayed.
The next step in the process is to provide or prepare a geometric surface. In this example, the geometric surface is in the form of a mesh
4
of primitives
5
in three dimensional space (FIG.
1
B). In the case of
FIG. 1B
, the primitives are triangles, but other types of polygons can be used. The mesh of primitives represents a three-dimensional shape of an object O in 3D space (in the case of
FIG. 1B
, the shape of a house). The position of each vertex of each triangle within mesh
4
is stored in a memory in the form of x, y and z Cartesian coordinates, relative to the object. These coordinates are sometimes referred to as model coordinates (“MC”). The process of preparing such a mesh is well-known, and described in standard graphics libraries, such as Real 3D, published by Real 3D, a Lockheed Martin Corporation, in 1996, and Direct 3D, published by New Riders Publishing in 1997.
The mesh of
FIG. 1B
is not displayed as such. Rather, the mesh of
FIG. 1B
is a representation of what is stored in a digital memory. Specifically, the memory stores the locations, in terms of x, y and z coordinates, of each vertex within mesh
4
.
The next step is to map or “bind” the two-dimensional texture map of
FIG. 1A
onto mesh
4
of FIG.
1
B. This is accomplished by mapping each triangle vertex to a location in the texture map. In effect, a list of data points is prepared that associates each vertex of mesh
4
to the u, v coordinates of a particular point (texel) in the texture map of FIG.
1
A. (The locations in the texture map to which the vertices are bound are sometimes referred to as “control points.”)
This portion of the process is roughly analogous to an upholsterer choosing a piece of fabric, and binding it with a few nails to the comer of a couch being upholstered (the nails are like control points). The upholsterer subsequently asks his apprentice to finish attaching the fabric to the couch. In this case, the 3D graphics pipeline finishes the task instead of an apprentice.
FIGS. 1A and 1B
describe the process by which one texture map (
FIG. 1A
) is mapped onto one mesh
4
representing one object O. A graphics pipeline can, and often does, map one or several texture maps onto the same or several different objects.
The next step in the process is to set up a “world coordinate model” of the various objects to be displayed. This requires establishing a position and directional orientation for each object to be displayed. For example, supposing that instead of a house, two objects are to be viewed: a tetrahedron T and a cube C (FIG.
1
C). During this portion of the process the pipeline is instructed that cube C is to be facing in a certain direction, and is to be located partially in front of tetrahedron T relative to a certain frame of reference. Again, the structure of
FIG. 1C
is not displayed per se. Rather, the graphics pipeline sets up processing of the model coordinates in accordance with the parameters of the position and orientation of the object.
The next step is to select a frame of reference. For example, it might be decided that the “viewer” will want to observe the objects from a position corresponding to a corner of the world coordinate model (e.g. position P in FIG.
1
D). Thus, a virtual viewpoint, viewing direction and aperture will be selected. The parameters associated with this “viewer” define the screen coordinate (SC) system. Further, it might be decided the viewer will observe these objects with a light source located at a position L. The graphics pipeline will set up another processing pipe to process the world coordinate data into the screen coordinate data which will cause a computer screen to display the image as it would be perceived by the observer at position P (e.g. the image of FIG.
1
D). In other words, the computer screen will provide an image of tetrahedron T and cube C as they would be observed by a viewer if he were standing at position P, and a light source were present at location L. This image will be provided initially as a pixel array in a frame buffer and then displayed by the computer screen. The image in the frame buffer is refreshed, i.e. regenerated according to the specifications programmed into the pipeline, typically at about 50 to 120 times per second. There are many different methods
Kamen Yakov
Shirman Leon
Brier Jeffery
isurfTV
LandOfFree
Mechanism and apparatus for realistic 3D model creation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Mechanism and apparatus for realistic 3D model creation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Mechanism and apparatus for realistic 3D model creation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878445