Visible Surfaces Determination
Goal
visibility from a view point
HLHSR
Assumptions
objects are made of polygonal patches all patches are opaque
Computer Graphics
OpenGL
Very simple, you need to do only two things Prepare buffer
glutInitDisplay(GLUT_DEPTH | …); distance to the view point is recorded glClear(GL_DEPTH_BUFFER_BIT);
clear to the far clipping plan distance (1.0) Enable depth comparison
glEnable(GL_DEPTH_TEST);
Tell OpenGL how to do the depth comparison
glDepthFunc(); default is GL_LESS (in front of the far clipping plane)
Visible z values are negative, but distance (depth) is positive
Computer Graphics
Depth comparison
at 3D
before projection
after modeling, normalization, etc. transform
Parallel
Perspective YY
ZZ XX
if(X==X&&Y==Y) 1212
XXYY if(1== 2&&1==2)
compare Z1 and Z2
Z1 Z2 Z1 Z2 compare Z1 and Z2
Computer Graphics
General Approaches
Image Space
for (each pixel in the image) {
determine the object closest to the viewer draw the object at that particular pixel }
Object Space
for (each object in the scene) {
Hybrid
determine which parts of the object whose views are unobstructed
draw those parts of the object }
Computer Graphics
Useful techniques
Coherence
parts of an object or an environment exhibit local
similarity
Bounding volumes
simplifies intersection tests Hierarchy
e.g., hierarchical bounding volumes Spatial partitioning
exploit spatial coherency Back face culling
e.g. convex objects viewing from outside Computer Graphics
Image space
Scan-line Algorithm
Exploit scan-line coherency
Image is generated one scan line at a time
keep all active polygons (edges) determine their Z-ordering
ordering can change when cross edges
Computer Graphics
Edge table
Polygon table
– sorted by smallbest y into buckets (scan lines) – x coor at smallest y
– y coor at largest y
– x increment
– coefficients of plane equation – shading and color info
– IN/OUT flag
– polygon ID
Active Edge table
– At each scan line
– delete edges no long intersect current scan – update x coordinates of active edges
– add new edges from the current bucket
– sort x coordinates of all active edges
Computer Graphics
Y
Scan in none – background Scan in one – paint
Scan in multiple – order test
Computer Graphics
X
ZZ
Non-intersecting polygons – order change at edges
Intersecting polygons
– order change at edges & intersections
– re-compute when scan leaving occluding polygons
– splitting polygons may be necessary
Don’t care
XX
Computer Graphics
Initialization
} }
ZB<- most distant Z;
IB <- background color; for each polygon {
for each pixel in polygon { compute Z(x,y);
if Z(x,y) is closer then ZB(x,y) {
ZB(x,y) = Z(x,y);
IB(x,y) = polygon color; }
Z Buffer
Simplest (and most widely used) Object space Amenable to hardware implementation
Computer Graphics
Hybrid
Initialization
Depth-Sort (List-Priority)
sort polygons in order of decreasing distance
Resolve Ambiguity
Pick the polygon (P) at the front (most distant) of the list
and for all polygon (Q) whose Z-extent overlap that of P’s
1. Do the polygons’ x extent not overlap?
2. Do the polygons’ y extent not overlap?
3. Is P entirely on the opposite side of Q’s plane from the viewpoint? 4. Is Q entirely on the same side of P’s plane as the viewpoint?
5. Do the projections of the polygons not overlap? Switch P and Q if all above fail
Scan Conversion
Computer Graphics
ZZ P
Q
Q XX
ZZ
R PP
QQ XX
Computer Graphics
P
BSP-Tree (Object Space)
Based on a simple observation
if the space is divided in half, then polygons on the side that does not contain the observer cannot obscure polygons on the same side as the observer
Computer Graphics
BSP Tree (cont.)
Record the spatial adjacency info in a tree
choose a scene polygon and use its plane to partition the
space into two halves
scene polygons are put in one half
split polygons that straddle the partition plane
recursively apply the algorithm until no more polygons can be used
good for
static scene structures moving observer locations
e.g. fly-through, walk-through
Computer Graphics
2 1
3
3 1
5 5a
5b
3 24
5
4
Example of BSP Tree
5a 4
1
5b
Computer Graphics
2
IN OUT
IN OUT
1
IN OUT
IN OUT 2
4
2
5
4
Iterate through the list of vertices
Output vertices based on IN/OUT relations
Computer Graphics
Original
3
3
1
6
An in-order traversal
Rendering
At each node
traverse the subtree not containing the observer render polygons at the node
traverse the subtree containing the observer
Computer Graphics
Surrounding
Area Sub-division
Divide-and-Conquer
Divide an image region until it is easy to decide which polygon or polygons are visible
Intersecting Contained Disjoint
Computer Graphics
Area Sub-division
Disjoint
render background color
One intersecting or contained render background then polygon
One surrounding
render polygon color
More than one surrounding, intersecting, contained
if the surrounding polygon is in front Otherwise, recursive subdivision
Computer Graphics
} }
Visible Surface Ray Tracing
for (each scan line) {
for (each pixel in scan line) {
compute ray direction from COP (eye) to pixel for (each object in scene) {
if (intersection and closest so far) { record object and intersection point
}
set pixels color to that at closet object intersection }
Computer Graphics
Compute Intersection
A (low-order) implicit representation (f(x,y,z) =0) can be useful
>0 (outside), =0 (surface), <0 (inside)
Two examples
Spheres (implicit representation) Polygons (parametric representation)
Computer Graphics
sphere:(X−a)2 +(Y−b)2 +(Z−c)2 −r2 =0 X = Xo +t∆X
r a y : Y = Y o + t ∆ Y Z = Z o + t ∆ Z
X2 −2aX+a2 +Y2 −2bY+b2 +Z2 −2cZ+c2 −r2 =0 (Xo +t∆X)2 −2a(Xo +t∆X)+a2 +
(Yo +t∆Y)2 −2b(Yo +t∆Y)+b2 +
(Zo +t∆Z)2 −2c(Zo +t∆Z)+c2 −r2 =0
(∆X2 +∆Y2 +∆Z2)t2 +
2{∆X(Xo −a)+∆Y(Yo −b)+∆Z(Zo −c)}t+
(Xo −a)2 +(Yo −b)2 +(Zo −c)2 −r2 =0 Computer Graphics
(∆X2 +∆Y2 +∆Z2)t2 +
2{∆X(X −a)+∆Y(Y −b)+∆Z(Z −c)}t+
ooo
(X −a)2 +(Y −b)2 +(Z −c)2 −r2 =0 ooo
At2 +Bt+C=0 ∆=B2 −4AC
∆ > 0 t∆ = 0 ∆ < 0
insersecting grazing
n o n i n s e r s e c t i n g
Computer Graphics
plane : aX + bY + cZ + d = 0 X = Xo +t∆X
r a y : Y = Y o + t ∆ Y Z = Z o + t ∆ Z
a(Xo +t∆X)+b(Yo +t∆Y)+c(Zo +t∆Z)+d =0 t=−aXo +bYo +cZo +d
a∆X + b∆Y + c∆Z
There will be a reasonable t value, unless the denominator
is zero (the line and the plane are parallel)
But is the intersection point actually inside the polygon?
Computer Graphics
Point-in-polygon test (point must be on the inside relative to all polygon edges)
Can be done in 2D Y
X
Computer Graphics
Z
Avoid intersection computation
Bounding volume Object hierarchy
Spatial partitioning
Computer Graphics
Slab : aX + bY + cZ + d = 0 X = Xo +t∆X
A:perrayperslabset B:perrayperslabset D: per slab
ray:Y =Yo +t∆Y Z = Z o + t ∆ Z
Bounding Volume
t=−aXo +bYo +cZo +d = A+D a∆X +b∆Y +c∆Z B
Computer Graphics
Bounding Volume (cont.)
All the maximum (circle) intersections must be after all the minimum (square) intersections
Computer Graphics
Hierarchical Bounding Volume
Computer Graphics
Spatial Partitioning
Ray can be advanced from cell to cell
Only those objects in the cells lying on the path of
the ray need be considered
First intersection terminates the search
Computer Graphics