Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-12-14
2002-03-12
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S420000, C345S421000, C345S422000
Reexamination Certificate
active
06356264
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image processing device utilized by a computer and in particular to an image processing device and method thereof that can efficiently determine a shadow region of an object.
2. Description of the Related Art
Shadow polygon methods have been proposed which allow a shadow of an object to be drawn utilizing hidden-surface cancellation processing hardware that uses the Z-value in image processing. For example, this method is proposed in unexamined patent publication, KOKAI HEI 2-73479. This type of shadow polygon method utilizes a virtual object for the purpose of shadow-casting. This is called shadow volume. A shadow volume is a shadow space produced by a light source and an object that shields the light. The inner side of this shadow volume is the region that becomes the shadow for an object and the outer side is the region irradiated by the light from the light source.
A shadow volume is a semi-infinite polyhedron and the plurality of sidewalls comprising this polyhedron are semi-infinite polygons called shadow polygons. Therefore, a shadow volume is comprised by a plurality of shadow polygons. The shadow polygons are handled in like manner to ordinary polygons thereby allowing shadowing.
FIG. 1
shows a shadow process utilizing shadow volumes and shadow polygons which comprise the shadow volumes. In this example, shadow volumes SV
1
, SV
2
and SV
3
are formed by means of blocking light from the light source by opaque polygons P
1
, P
2
and P
3
. Because the light source is on the left side in the figure, shadow volumes SV
1
, SV
2
and SV
3
are generated on the right sides of opaque polygons P
1
, P
2
and P
3
, respectively. Further, cross sections of the shadow volumes are shown in the figure. Therefore, shadow volume SV
1
is formed by shadow polygons SP
11
and SP
12
, shadow volume SV
2
is formed by shadow polygons SP
21
and SP
22
, and shadow volume SV
3
is formed by shadow polygons SP
31
and SP
32
.
At the present, the position of the view point is temporarily at view point
1
of a position outside the shadow volumes. In order to detect either the region of a shadow inside a shadow volume or the region irradiated by outside light, shadow polygons passing through in the direction of the Z-axis (direction of arrow) from view point
1
to a normal polygon are counted and then that count value is detected as either an even number or an odd number. As shown in
FIG. 1
, when view point
1
is positioned at the outer side of a shadow volumes, it is understood that if the count value is an even number, the region is outside a shadow volume and if the count value is an odd number, the region is inside a shadow volume.
Therefore, in order to judge whether the surface of a certain polygon is a region of a shadow, the number of shadow polygons existing in front of the position of that certain polygon, namely, between the position of that polygon and the position of the view point can be counted and then if that count value is an even number, the region is inside a shadow and if the count value is an odd number, the region is outside a shadow.
For example, if ordinary polygon OP exists intersecting shadow volume SV
3
as shown in
FIG. 1
, two shadow polygons SP
31
and SP
32
exist between the a-b region of ordinary polygon OP and the view point
1
. Because of this, the region a-b is judged to be a region outside shadow volume SV
3
. Furthermore, one shadow polygon SP
32
exists between the b-c region of ordinary polygon OP and the view point
1
. Because of this, the b-c region is judged to be a region inside shadow volume SV
3
. Even further, because no shadow polygons exist between the c-d region and the view point
1
, the c-d region is judged to be a region outside shadow volume SV
3
.
As described above, shadow processing that utilizes shadow volumes and shadow polygons utilize a method similar to a hidden-surface cancellation method that uses Z-values, allowing the number of shadow polygons which exist between a certain polygon and a view point to be counted.
However, when the view point is positioned inside a shadow volume as seen by view point
2
in
FIG. 1
, if the number of shadow polygons between the view point
2
and the ordinary polygons is an odd number, the region is outside a shadow volume and if it is an even number, the region is inside a shadow volume. In other words, when the view point is positioned inside a shadow volume, the relationship between a region outside a shadow and a region inside a shadow for an odd number and an even number of polygons up to the view point is reversed compared to when the view point is positioned outside a shadow volume.
Therefore, in a conventional shadow processing method, it is necessary to judge whether the position of the view point is outside the shadow volume or inside the shadow volume. This judgment is, for example, necessary to carry out complicated calculations such as finding an equation of the surfaces of a shadow polygon. Further, depending on the results of the judgment, it must be necessary to change the relationship between the even/odd number of shadow polygons positioned between an ordinary polygon and an view point and whether the region is inside or outside a shadow.
SUMMARY OF THE INVENTION
Thereupon, the object of the present invention is to solve the above-mentioned conventional problems and provide an image processing device and method thereof that can carry out shadow processing to produce shadows with even more efficiency.
A further object of the present invention is to provide a recording medium that records a program that can carry out shadow processing to produce shadows with even more efficiency.
In order to achieve the above-mentioned objectives, provided is an image processing device comprising:
a pixel data generation step for generating position data and depth data in a display screen for pixels of first ordinary polygons, and generating position data and depth data in a display screen for pixels of shadow polygons which specify a shadow space produced by second ordinary polygon blocking light from a light source;
a step for storing the depth data for pixels the first ordinary polygons with the shortest depth at each pixel position;
a shadow determination step for detecting whether said shadow polygons exist between the stored depth position of pixels and an infinite position for each pixel position, detecting either an odd or even number of shadow polygons existing between the two positions, and determining that a shadow exists at said pixel when the number of shadow polygons is an odd number and;
a rendering step for carrying out a shadowing process for pixels judged to have shadow by said shadow determination step.
According to the image processing method above, when the number of shadow polygons existing between a depth position of pixels of ordinary polygons subject to shadowing and an infinite position is counted and that number is an odd number, those pixels are unconditionally judged to be positioned inside a region of shadow volume. Therefore, regions to undergo shadowing can be efficiently detected by judging whether the number is an odd number or an even number at all pixel positions.
Furthermore, in order to achieve the above-mentioned objectives, provided is an image processing device comprising:
a pixel data generation step for generating position data and depth data in a display screen for pixels of first ordinary polygons, and generating position data and depth data in a display screen for pixels of shadow polygons which specify a shadow space produced by second ordinary polygon blocking light from a light source;
a step for storing the depth data for pixels of the first ordinary polygons with the shortest depth at each pixel position;
a shadow determination step for detecting whether said shadow polygons exist between the stored depth position of pixels and an infinite position for each pixel position, and determining whether a shadow exists at said pixel in accordance with t
Okubo Jun
Yasui Keisuke
Nguyen Kimbinh T.
Sega Enterprises Ltd.
Zimmerman Mark
LandOfFree
Image processing device and image processing method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing device and image processing method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing device and image processing method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2841998