Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-12-21
2001-08-14
Luu, Matthew (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C345S426000, C345S440000, C345S440000, C345S440000
Reexamination Certificate
active
06275235
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of computer graphics and, more particularly, to a method and device for providing high precision texture wrapping.
In modern computer graphics, images or objects are typically modeled by graphics primitives such as points, line segments, polygons, etc. Among the primitives, polygons, particularly triangles, have been commonly used in modeling 2D and 3D images of objects. The underlying reason for this is that polygons such as triangles are generally easier to generate and simpler to support in hardware than other primitives.
The conventional polygon modeling method, however, presents a problem in modeling images or objects having intricate and fine surface details. In particular, modeling such intricate and fine details requires smaller polygons. For example, a large flat wall, which in actuality is a single rectangle, might require thousands of individual bricks to model the intricate and fine details of the surface. Thus, the need to use smaller polygons significantly increases the number polygons that must be used to model an image or object. In computer graphics, processing cost is proportional to the number of polygons used in modeling an image. The reason that the processing cost increases as the number of polygons used increases is that each additional polygon requires more data processing, more data transformation, and more data storage. Hence, modeling of fine and intricate scenes or objects using micro-polygons has been an expensive and impractical process for all but the most expensive graphics systems.
Various alternatives to the micro-polygon modeling method have been devised in modeling images and objects having fine and intricate surface details such as, for example, dense vegetation, walls, etc. One such alternative approach is a method referred to as texture mapping or pattern mapping. In this method an image is applied to a polygon and this polygon with the applied image is drawn as a single polygon. The image is sometimes referred to as a texture or a texture map and its individual elements are sometimes referred to as texels. The texture map typically consists of rectangular arrays of texels, which are associated with data such as color, luminance, color, alpha value, etc. Alternatively, the texture map may be defined by procedural methods.
In texture mapping, a rectangular texture is generally mapped onto the surface of a polygon modeling an object. When mapping a rectangular texture onto a polygon, however, the size of the rectangular texture is often smaller than the size of the polygon. In such cases, a conventional method, which is commonly known as “texture wrapping,” is typically used to apply the texture onto the polygon repeatedly until the polygon is entirely covered with the texture.
FIG. 1A
illustrates a schematic diagram of an exemplary texture wrapping method. In this example, a rectangular texture
102
of intensity values is defined in a two-dimensional texture coordinate space (s, t) with s and t each ranging from 0 to 1. A polygon
104
has texture coordinates that are twice as large as the texture coordinates of the rectangular texture
102
. In this arrangement, rectangular texture
102
is replicated four times onto polygon
104
, thereby generating detailed and repeating surface images on the polygon.
When a relatively large number of polygons is used to model a large image or object such as, for example, a field of vegetation or grass, a rectangular texture may be applied thousands of times onto the polygon to generate an image of vegetation with a realistic appearance. Unfortunately in these cases, conventional texture wrapping methods generally do not provide a detailed texture surface due to the lack of precision at the higher texture space coordinates.
For example,
FIG. 1B
shows a schematic diagram of a conventional texture wrapping method as applied to a triangle
106
having large texture coordinates. Specifically, the triangle
106
is characterized by vertices &agr;, &bgr;, and &ggr;, which have (s, t) texture coordinates of (99998, 1234), (99999, 1234.1), and (99999.17, 1235.769867), respectively. In this texture coordinate arrangement, the texture
102
from the lower texture coordinate may not be applied properly onto the triangle due to a lack of sufficient precision at the higher texture coordinate space. For example, even though the texture coordinates only differ by one or two units, over 20 integer bits may be needed to attain visual accuracy using conventional techniques.
A computer system typically implements texture mapping by assigning a specified number of bits to texture coordinates. For example, texture coordinate variables “s” and “t” may be represented as an 8-bit number. In this configuration, the 8-bit texture coordinate variables do not provide sufficient precision for higher texture coordinates such as (999, 999), to distinguish from neighboring texture coordinates. That is, the 8-bit texture coordinate may distinguish only the first 2
8
, i.e., 256, texture coordinate blocks. Thus, the remaining texture coordinates may not be accurately replicated onto the polygon
106
, thereby resulting in unrealistic images.
Conventional texture application techniques often employ a well-known barycentric coordinate system based on the areas of sub-triangles within a triangle. For example, a barycentric coordinate system is defined in OpenGL®, version 1.1, available from Silicon Graphics, Inc.
FIG. 2
illustrates an exemplary triangle
200
for implementing the barycentric coordinate system. The triangle
200
includes three sides
202
,
204
, and
206
. The triangle
200
is defined by three vertices &agr;, &bgr;, and &ggr;, which have three-dimensional texture coordinates (s
&agr;
, t
&agr;
, r
&agr;
), (s
&bgr;
, t
&bgr;
, r
&bgr;
), and (s
&ggr;
, t
&ggr;
, r
&ggr;
), respectively.
An arbitrary point P within the triangle
200
is characterized by a coordinate (s
P
, t
P
, r
P
). The point P and the vertices &agr;, &bgr;, and &ggr; define three sides
208
,
210
, and
212
, respectively. The sides
202
,
204
, and
206
of the triangle
200
and the sides
208
,
210
, and
212
form three sub-triangles
214
,
216
, and
218
. In this configuration, the coordinate (s
P
, t
P
, r
P
) of the point P is uniquely defined by the areas A, B, and C of sub-triangles
214
,
216
, and
218
, respectively. The areas A, B, and C form the basic coordinate units in the barycentric coordinate system.
To further simplify the barycentric coordinate system, if the area of the triangle
200
is normalized to 1, then the point P can be uniquely defined by the areas of any two sub-triangles. For example, if the areas of sub-triangles
214
,
216
, and
218
are A, B, and C, respectively, then A+B+C=1. Hence, the area C can be defined in terms of the other two areas: C=1−(A+B). Consequently, the coordinate (s, t, r) of the point P can then be defined by the following barycentric equations based on barycentric coordinates (A, B):
s
p
=(s
&agr;
−s
&ggr;
)A+(s
&bgr;
−s
&ggr;
)B+s
&ggr;
; Equation 1.1
t
p
=(t
&agr;
−t
&ggr;
)A+(t
&bgr;
−t
&ggr;
)B+t
&ggr;
; Equation 1.2
and
r
p
32
(r
&agr;
−r
&ggr;
)A+(r
&bgr;
−r
&ggr;
)B+r
&ggr;
. Equation 1.3
One drawback of using the conventional barycentric equations in a texture wrapping operation is that they may not provide sufficient precision for large texture coordinates. For example, if s
&agr;
, s
&bgr;
, and s
&ggr;
are floating point numbers 1005.1, 1010.5, and 1006, respectively, a computer system that implements the barycentric equations may not provide sufficient precision to generate distinct and unique coordinates. In addition, computing s
P
, t
P
, and r
P
using such large floating point numbers requires a substantial number of subtraction operations, which require a significant number of subtractors to implement in hardware.
Thus, what is needed is a method a
Chung Daniel J
Luu Matthew
Martine & Penilla LLP
Silicon Graphics Inc.
LandOfFree
High precision texture wrapping method and device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High precision texture wrapping method and device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High precision texture wrapping method and device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463250