Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-01-22
2001-12-04
Vo, Cliff N. (Department: 2772)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S473000
Reexamination Certificate
active
06326963
ABSTRACT:
FIELD OF THE INVENTION
The present invention is generally related to computer graphics, and more specifically, to computer graphics collision detection. Still more specifically, the present invention relates to systems, methods and techniques for efficiently detecting collision by transforming a potentially colliding object into another object's local coordinate system.
BACKGROUND AND SUMMARY OF THE INVENTION
Importance of Collision Detection
In interactive computer graphics systems such as video games, it is often important to determine when different objects collide. For example, the video game player may operate a hand-held controller, joystick or other user input device to control the placement of a graphical character within a three-dimensional graphics “world.” As the main character moves about in the imaginary world under player control, the computer graphics system must rapidly determine which terrain the character stands on, what walls he bumps into, etc. Detecting when the character collides with a part of the “world” is important to the progression of the video game and the game playing experience.
As one example, realism requires that the main character must not move through solid walls, trees or other solid objects. Also, progress of video game play often depends on collision detection. For example, in a tennis video game, collision between the tennis ball and different parts of the tennis court (e.g., the net, the rackets, etc.) determines who wins and who loses a point, and also determines where the ball goes next. In a driving game, collision of the player's car against a wall or other object may cause the car to crash or experience some other effect. In a fighting game, contact between characters may have consequences in terms of who wins the fight. Many interactive computer graphics systems have similar collision detection requirements.
Collision detection can be a very processor-intensive operation. Often, for example, a moving object such as a main character is moved under player control within a terrain or landscape of arbitrary complexity. Detecting collisions with large or irregular objects of arbitrary complexity can require lots of processing resources.
Computer Graphics Systems Often Have Limited Resources
Video games and other interactive graphics systems need to perform graphics operations in real time—often within the {fraction (1/30)}th or {fraction (1/60)}th of a second frame time of a conventional video display. This rapid response time places a premium on system processing resources. In many interactive graphics systems, there may not be enough processing resources to satisfy demand. This problem can be especially acute in relatively inexpensive, resource-constrained real time interactive graphics systems such as, for example, home video game systems.
In low cost systems, processing resources may be nearly or completely occupied generating the interactive video game or other real-time video graphics and sound display effects. Video game designers sometimes must sacrifice desirable image effects for fear of overwhelming available processing resources. Further, such systems are often resource constrained in other areas as well—for example, the amount of available storage. In such resource-constrained environments, it is desirable to maximize efficiency whenever possible to provide interesting visual effects without overloading available resources. As will be explained below, collision detection can require more resources than are available.
Collision Detection Relies on Transformations
For objects to interact, it is necessary to bring them into the same coordinate system—since otherwise, mathematical comparisons will be meaningless. Geometrical transformations allow a computer graphics system to mathematically change the position, orientation and size of objects for display or other purposes. It is well known in the computer graphics art to use geometrical transformations to efficiently manipulate graphical objects for display and other purposes. See, for example, Foley et al,
Computer Graphics: Principles and Practice
(2d Ed. Addison-Wesley 1990), Chapters 5 and 7.
One way to think about a transformation is as a change in coordinate systems. For example, each object can be defined within its own, “local” coordinate system—and transformations can be used to express the objects' coordinates within a single, global (“world”) coordinate system. This is analogous to providing several pieces of paper, each with an object on it; and shrinking, stretching, rotating and/or placing the various papers as desired onto a common world-coordinate plane.
To illustrate,
FIG. 1
shows an object
50
being transformed from its own “local space” coordinate system
52
into a “world space” coordinate system
54
. In this simplified example, object
50
is a three-dimensional object defined within its own 3-D (x.y,z) local space coordinate system
52
. Object
50
may, for example, conveniently be defined as having one of its points (e.g., a corner point or vertex) at the xyz origin of local space coordinate system
52
.
A transformation matrix
56
(“M
1
”) is used to flexibly transform the object to the purely hypothetical “world space” coordinate system
54
. Transform
56
can:
move the object around within the world space coordinate system
54
,
rotate the object in any of three dimensions within the world space coordinate system, and/or
make the object larger or smaller in any of its three dimensions within the world space coordinate system.
In the particular example shown, transform
56
displaces object
50
′ from the origin in the world space coordinate system
54
. By changing the parameters of transform
56
, it is possible to move, reorient and/or resize object
50
′ anywhere in world space
54
. By changing the parameters of transform
56
over time, one can animate object
50
′ in the world space coordinate system
54
.
The local space object definition shown in the left-hand side of
FIG. 1
can remain constant. Only the object's parameters in local space
52
need to be represented in a stored image database. It is not necessary to maintain a separate database containing the object
50
′ transformed into world space
54
because the world space representation of the object
50
′ can be generated on demand by mathematically applying transformation matrix M
1
to the stored, local space parameters. This saves storage, and also has other advantages—including the ability to perform “instancing.”
Instancing is Useful
Instancing is a very useful technique for reducing the amount of data the computer graphics system must store at any given time. Instancing is especially useful in cases where it is possible to build images out of multiple “versions” of the same basic or “primitive” object(s) (for example, four identical tires on a car). One can maintain only a single representation of the object. Each displayed instance of the object can be generated using a different transformation.
The
FIG. 2
example shows two different transformations
56
a,
56
b
(“M
1
” and “M
2
”) used to transform two instances
50
a,
50
b
of the same object
50
into world space coordinate system
54
. Because it is not necessary to change the actual shape of object
50
, it is efficient to describe the object only once in a local space coordinate system
52
, and then generate multiple instances of the object in world space coordinate system
54
—generating each different instance
50
a,
50
b
using a different respective transform
56
a,
56
b.
The ability to describe object
50
only once and generate multiple instances of it having different world space locations, orientations and/or sizes saves data storage.
How Transformations Have Been Used for Collision Detection
Prior video game and other computer graphics systems often performed collision detection by testing for object overlap in the common “world space” coordinate system
54
.
FIG. 3
shows an example of this. There are two different objects
60
,
62
shown in
Nintendo Co. Ltd.
Nixon & Vanderhye P.C.
Vo Cliff N.
LandOfFree
Method and apparatus for efficient animation and collision... 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 apparatus for efficient animation and collision..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient animation and collision... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2588996