HIDDEN SURFACE ELIMINATION
Hidden Surface Removal
When drawing lots of polygons, we want to draw only those ``visible'' to viewer. There are a variety of algorithms with different strong points.
o Device independent
o Memory requirements
o Easy to implement in hardware
Backface CullingA simple way to perform hidden surface is to remove all ``backfacing'' polygons. The observation is that if polygon normal is facing away from the viewer then it is ``backfacing.'' For solid objects, this means the polygon will not be seen by the viewer.
· Thus, if N.V > 0 , then cull polygon.
· Note that V is vector from eye to point on polygon
You cannot use the view direction for this.
Not a complete solution
· If objects not convex, need to do more work.
· If polygons two sided (i.e., they do not enclose a volume) then we can't use it.
· A HUGE speed advantage if we can use it since the test is cheap and we expect at least half the polygons will be discarded.
· Usually performed in conjunction with a more complete hidden surface algorithm.
· Easy to integrate into hardware (and usually improves performance by a factor of 2).
Idea: Draw polygons as an oil painter might: The farthest one first. o Sort polygons on farthest z
o Resolve ambiguities where z's overlap
o Scan convert from largest z to smallest z
Since closest drawn last, it will be on top (and therefore it will be seen).
Need all polygons at once in order to sort.
•The z or depth buffer–stores the depth of the closest object at each pixel
found so far As we render each polygon, compare the depth ofeach pixel to depth in z buffer
–If less, place the shade of pixel in the color buffer and update z buffer
Function setpixel(int i, int j, rgb c, real z) If z > z-buffer(i, j) then
z-buffer(i, j) = z screen(i,j) = c
•Avoid rendering an object when it’s unnecessary
–In many real-time applications, we want to eliminateas many objects as possible within the application.
Why do we use BSP trees?
•Hidden surface removal
–A back-to-front painter’s algorithm
•Partition space with Binary Spatial Partition (BSP)Tree
Binary Space Partitioning Tree
•Can continue recursively
–Plane of C separates B from A
–Plane of D separates E and F
•Can put this information in a BSP tree
–Use for visibility and occlusion testing
Key Idea of BSP
•Assume T2 not cross the plane of T1
•If e and T2 on the same side, T1 won’t block
•If e and T2 on different sides, T2 may block
Creating a BSP tree