Computer Graphics
|
Visible-Surface
Detection Methods
|
·
Object
space algorithm: Back-Face removal
·
No
faces on the back of the object are displayed.
·
In
general - about half of objects faces are back faces
·
Algorithm
will remove about half of the total polygons in the image.
NOTE: Right Handed coordinate System
If
n·V > 0 then
polygon is backface
n·V = |n| |V| cos q
cos q = n·V / (|n| |V|)
where |n| and |V| are the
magnitudes of the vector
|V|
= sqrt(
Vx2
+ Vy2
+ Vz2
)
Determining Surface |
|||
|
x |
y |
z |
1 |
0.750 |
0.250 |
0.000 |
2 |
0.250 |
0.750 |
0.000 |
3 |
0.125 |
0.750 |
0.217 |
4 |
0.375 |
0.250 |
0.650 |
|
|
|
|
|
center |
0.438 |
0.500 |
0.108 |
Point 2 - 1 |
P |
-0.500 |
0.500 |
0.000 |
Point 3 - 2 |
Q |
-0.125 |
0.000 |
0.217 |
Magnitude of P |
|P| |
0.7071 |
|
|
Magnitude of Q |
|Q| |
0.2500 |
|
|
|
P(Norm) |
-0.7071 |
0.7071 |
0.0000 |
|
Q(Norm) |
-0.5000 |
0.0000 |
0.8660 |
|
Normal Vector |
nx |
ny |
nz |
|
CrossProd (PxQ) |
0.1083 |
0.1083 |
0.0625 |
|
n(Norm) |
0.6547 |
0.6547 |
0.3780 |
cos RQ |
0.00 |
cos RP |
0.00 |
|n| |
0.165359 |
L(n) |
1 |
RlS = (RxSx+RySy+RzSz)=|R||S|cosθ |
|||
|
|
|
|
R=PxQ |
|
|
|
Rx = PyQz - PzQy
|
|
|
|
Ry = PzQx -PxQz |
|
|
|
Rz = PxQy - PyQx |
|
|
Standard equation of a
plane in 3 space : Ax + By + Cz + D = 0 |
|
Given three points in space (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) the equation of the plane through these points is given by
Ax1 + By1 + Cz1 + D =
0
Ax2 + By2 + Cz2 + D =
0
Ax3 + By3 + Cz3 + D =
0
in counter-clockwise
order, and solving for
A’xk
+ B’yk + C’zk = 1
where k = 1,2.3
A’ = -(A/D),
B’ = -(B/D), and C’ = -(C/D)
Use Cramer’s rule for solving simultaneous equations:
Begin with a system of linear equations, for example, a system involving three variables -
A’x1 + B’y1 + C’z1 = 1
A’x2 + B’y2 + C’z2 = 1
A’x3 + B’y3 + C’z3 = 1
that may be expressed in matrix form as
Here the coordinates constitute a coefficient matrix (A) and the vector components (A’,B’,C’) are the unknowns.
Generally, this is written as
a11x + a12 y = c1
a21x + a22 y = c2
for the 2D case and expressed in matrix form
the square matrix A, with real number entries,
can be expressed by a real number called the determinant of the matrix.
The determinant is written as -
and is defined by det A = a11a22
- a12a22
There are two other matrices obtained by replacing the coefficients in each column by the constants c1 and c2 respectively
Their determinants are det Ax and det Ay respectively.
For a 3 x 3 matrix of coefficients the determinant may be expressed as either:
or as a cofactor expansion
Cramer's Rule states that
For our system, the result
is
Expanding the above gives
A
= y1 (z2 - z3) + y2 (z3 - z1) + y3 (z1 - z2)
B = z1 (x2 - x3) + z2 (x3 - x1) + z3 (x1 - x2)
C = x1 (y2 - y3) + x2 (y3 - y1) + x3 (y1 - y2)
D = -x1 (y2 z3 - y3 z2) - x2 (y3 z1 - y1 z3) - x3 (y1 z2 - y2 z1)
If the 3 points are collinear then the normal (A,B,C) will be (0,0,0).
The sign of S = Ax + By + Cz + D determines which side the point (x,y,z) lies with respect to the plane.
· If s > 0 then the point lies on the same side as the normal (A,B,C).
· If s < 0 then it lies on the opposite side
· If s = 0 then the point (x,y,z) lies on the plane.
Calculating |
||||
|
|
X |
y |
z |
Original Data |
1 |
0.750 |
0.250 |
0.000 |
|
2 |
0.250 |
0.750 |
0.000 |
|
3 |
0.125 |
0.750 |
0.217 |
|
4 |
0.375 |
0.250 |
0.650 |
|
|
|
|
|
use 3 points in succession |
|
|
||
|
A |
0.1083 |
|
|
|
B |
0.1083 |
|
|
|
C |
0.0625 |
|
|
|
D |
-0.1083 |
|
|
|
S |
0.171 |
|
|
Same as with normal vector
e.g. partially hidden face will not be
eliminated by Back-face removal.
·
Image-Space
Algorithm also known as z-buffer method
·
Test
z - depth of each surface to determine the surface closest to observer.
o Declare an array z buffer(x, y) with
one entry for each pixel position.
o Initialize array to the maximum depth.
o The algorithm is:
for each polygon P
for each pixel (x, y) in P
compute z_depth at x, y
if z_depth < z_buffer (x, y) then
set_pixel (x, y, color)
z_buffer (x, y) <= z_depth
·
Polygon
scan-conversion procedure is modified to add the z-buffer test.
- At a surface position (x,y) the depth is calculated from the plane equation:
-
the
depth of the next position z’ becomes, for each successive position along scanline:
note: A/C is a constant, so successive z values are only
an addition
Possible algorithm:
1.Begin
at top vertex of polygon
2.Recursively
calculate x-coordinate values down left edge of polygon
3.Subsequent
x-values for each scanline calculated from starting
x-value
and depth values become
·
Advantage
Always works and is simple to implement => used in
hardware
·
Disadvantages
o Large memory requirements
o E.g. (640 x 480 )
§
real (4 bytes): 4bytes/pixel = 1,228,000
bytes.
§
usually use a 24-bit z-buffer = 900,000 bytes
§
may need additional z - buffers for special
effects, e.g. shadows.
·
Extension
of z-buffer -> accumulation buffer
·
Each
buffer position can reference a linked-list of surfaces
·
Allows
pixel color to be computed as combination of surface colors for transparency,
anti-aliasing, etc.
·
Each
position has 2 fields:
1.depth
field – real number
2.surface
data field
If depth field >= 0
depth at pixel location stored
Surface color and pixel coverage
else
(multiple surface contributions to pixel color)
surface color filed contains pointer to linked list of
surface data comprising:
·
·
Opacity
parameter
·
Depth
·
Percent
of area coverage
·
Surface
identifier
·
Other
surface rendering parameters
·
Based
on depth sorting
·
Object
space algorithm
Simplest to use maximum z value
·
Problems
with simple Painter's algorithm:
·
P’ has a greater depth than P
·
P’ will be drawn first.
·
P’ and P intersect
·
A
binary space
partitioning tree (bsp–tree)
is a binary tree whose nodes contain polygons.
·
Binary
space partitioning, or BSP, divides space into distinct sections by building a
tree representing that space.
·
Used
to sort polygons.
·
A BSP
takes the polygons and divides them into two groups bychoosing a plane, usually taken from the set of polygons,
and divides the world into two spaces.
·
It
decides which side of the plane each polygon is on, or it may also be on the
plane.
·
If
a polygon intersects the splitting plane it must be split into two separate
polygons, one on each side of the plane.
·
The
tree is built by choosing a partitioning plane and dividing the remaining
polygons into two or three lists: Front, Back and On
lists – done by comparing the normal vector of the plane with that of each
polygon.
·
For
each node in a bsp-tree the polygons in the left subtree lie behind the polygon at the node while the
polygons in the right subtree lie in front of the
polygon at the node.
·
Each
polygon has a fixed normal vector, and front and back are measured relative to
this fixed normal.
·
Once
a bsp-tree is constructed for a scene, the polygons
are rendered by an in order traversal of the bsp-tree.
·
Recursive
algorithms for generating a bsp-tree and then using
the bsp-tree to render a scene are presented below.
Algorithm for Generating a BSP–Tree
BSP-Tree Rendering Algorithm (In order tree traversal)
If
the eye is in front of the root, then
Display
the left subtree (behind)
Display
the root
Display
the right subtree (front)
If
eye is in back of the root, then
Display
the right subtree (front)
Display
the root
Display
the left subtree (back)
·
The
ray casting algorithm for hidden surfaces employs no special data structures.
·
A
ray is fired from the eye through each pixel on the screen in order to locate
the polygon in the scene closest to the eye.
·
The
color and intensity of this polygon is displayed at the pixel.
Ray
casting is easy to implement for polygonal models because the only calculation
required is the intersection of a line with a plane.
Ray Casting Algorithm