Hidden surface removal algorithm

Hidden surface removal algorithm

1. Hidden Surface Removal

2. HSR - Introduction Determine which surfaces are visible and which are not in a standard view. Display all visible surfaces, do not display any occluded surfaces .

3. Algorithm Classification Two main types of Classification: Object space: Determine which part of the object are visible Resize doesn’t require recalculation May be difficult to determine Image space: D determine which object is visible at each pixel Resize requires recalculation Object space Image space

4. Cases for hidden surface removal Occluded surfaces (partially or fully ) Back Faces

5. HSR - Algorithms Painter’s Algorithm - Object Space Algorithm Z-Buffer Algorithm - Image Space Algorithm Other Method Warnock’s Algorithm – ( Area Subdivision )

6. Painter’s Algorithm (OS) Draw surfaces from back (farthest away) to front (closest ) Sort surfaces/polygons by their depth (z value) Draw objects in order (farthest to closest) Closer objects paint over the top of farther away objects

7. Painter’s Algorithm (OS) Cyclic Overlap How do we sort these three polygons? Sorting is nontrivial Split polygons in order to get a total ordering Not easy to do in general

8. Painter’s Algorithm (OS) Advantages: Very good if a valid order is easy to establish; not so good for more complex surface topologies (e.g. presence of holes) For simple cases very easy to implement Fits well with the rendering pipeline. Disadvantages : Not very efficient – all polygons are rendered, even when they become invisible Complex processing (sorting + tests) for complex objects There could be no solution for sorting order Possibility of an infinite loop as surface order is swapped

9. Z-Buffer Algorithm (IS) Depth buffer (Z-Buffer) A secondary image buffer that holds depth values Same pixel resolution as the color buffer Why is it called a Z-Buffer? After eye space, depth is simply the z-coordinate Sorting is done at the pixel level Rule: Only draw a polygon at a pixel if it is closer than a polygon that has already been drawn to this pixel.

10. Z-Buffer Algorithm Two storage areas required: depth buffer - z value for each pixel at ( x,y ) display buffer – pixel value (colour) for each pixel at ( x,y )

11. Contd..

12. Parallel with the image plane

13. Not Parallel

14. Contd.. How do we calculate the depth values on the polygon interior? P 1 P 2 P 3 P 4 y s z a z p z b Scanline order Bilinear Interpolation

15. Contd.. Algorithm easily handles this case

16. Z-Buffer Algorithm Advantages Easy to implement Fits well with the rendering pipeline Can be implemented in hardware Always correct results Disadvantages Some inefficiency as pixels in polygons nearer the viewer will be drawn over polygons at greater depth It is a standard in many graphics packages ( e.g. Open GL)

17. Watkins Scan Line Algorithm The Watkins algorithm is a scan line image space algorithm. Also Known as “Rasterization Algorithm”. One starts at the extreme right. As new segments are taken from the x-sorted list, the right end moves left until one gets a span that is simple enough to compute which segment is visible.

18. Watkins Scan Line Build table of edges of all polygons in scenes. Maintain active edge table (AET) for each scan line in scene. It contains list of all active edges for the polygons of each scan. To maintain flag on each surface to determine whether pixel is on scan line is inside that surface.

19. Watkins Scan Line Example : Active edge table (AET) for each x scan Label P olyCount span Left Span Right ABC . active DEF. activ LA a F F LB 1 a F T LA 1 a b F T LB 2 a b T T LA 2 b c T T LB 1 b c F T

20. Other methods Area subdivision method Warnock's Algorithm Locate view areas (normally squares or rectangles) which represent a part of a single surface This is done by successively dividing the total view area into smaller rectangles Stop dividing a given rectangle when it contains a single surface or visibility precedence can be easily determined

21. Warnockʼs Algorithm An area-subdivision technique. Divide an area into four equal sub-areas At each stage, the projection of each polygon will do one of four things . Completely surround a particular area Intersect the area Be completely contained in the area Be disjoint to the area

22. Warnock's Algorithm At each stage of the algorithm, examine the areas: If no polygons lie within an area, the area is filled with the background colour If only one polygon is in part of the area, the area is first filled with the background colour and then the polygon is scan converted within the area. If one polygon surrounds the area and it is in front of any other polygons, the entire area is filled with the color of the surrounding polygon. Otherwise, subdivide the area and repeat the above 4 tests.

23. Warnock's Algorithm Initial scene Final scene

24. Warnock's Algorithm Subdivision continues until: All areas meet one of the four criteria An area is pixel size in this case, the polygon with the closest point at that pixel determines the pixel colour.

25. Thank You