Rice COMP 360 - Hidden Surface Algorithms

Unformatted text preview:

Lecture 22: Hidden Surface Algorithmsthou didst hide thy face, and I was troubled. Psalm 30:71. Hidden Surface AlgorithmsSurfaces can be hidden from view by other surfaces. The purpose of hidden surface algorithms is to determine which surfaces are obstructed by other surfaces in order to display only those surfaces visible to the eye. In theory, hidden surface algorithms are required for all types of surfaces; in practice, we shall restrict our attention to polygonal models.In this lecture we shall assume that all the surfaces are planar polygons and that all the polygons are opaque. We shall not assume that the polygons necessarily enclose a solid nor that the polygons form a manifold. Our objective is: given any collection of polygons to display only those polygons visible to the eye.Polygonal models of complicated shapes may contain millions of polygons, so just like shading algorithms, the emphasis in hidden surface algorithms is on speed. A good hidden surface algorithm must be fast as well as accurate. Sorting, tailored data structures, and pixel coherence are all employed to speed up hidden surface algorithms.There are two standard types of hidden surface algorithms: image space algorithms and object space algorithms. Image space algorithms work in pixel space (the frame buffer) and are applied after pseudoperspective; object space algorithms work in model space and are applied before pseudoperspective. These algorithms have the following generic structures:Image Space Algorithm Object Space AlgorithmFor each pixel: For each polygon:Find the closest polygon. Find the unobstructed part of the polygon.Render the pixel with the color Render this part of the polygon.and intensity of this polygon.The speed of image space algorithms is € O(nN), where N is the number of pixels and n is number of polygons, because for each pixel we must examine every polygon. The speed of object space algorithms is € O(n2), where n is the number of polygons, because to determine which part of each polygon is visible, we need to compare every polygon with every other polygon.Many hidden surface algorithms have been developed, each with their own advantages and disadvantages. We shall examine five of the most common hidden surface algorithms: z-buffer,scan line, ray casting, depth sort, and bsp-tree. The z-buffer and scan line algorithms are image space algorithms; the depth sort and bsp-tree algorithms are object space algorithms. Ray casting can work both in image space and in object space. We will compare and contrast the relative merits and limitations of each of these algorithms, and we shall see that there is no single solution to the hidden surface problem that is optimal in all situations.2. The Heedless PainterThe heedless painter displays the polygons in a scene in the order in which they occur in some list. Polygons that appear early in the list can be overpainted by polygons that appear later in the list.The heedless painter is slow because the same pixel may be painted many times, once for each polygon that lies over the pixel. Worse the scene displayed by the heedless painter is often incorrect because polygons that appear later in the list may overpaint polygons that appear earlier in the list, even though the later polygons actually lie behind the earlier polygons.The heedless painter procedure is not a true hidden surface algorithm. Nevertheless, valid hidden surface algorithms can be generated by fixing the problems in the heedless painter procedure. We begin with two such hidden surface algorithms: z-buffer and scan line. 3. Z-Buffer (Depth Buffer)The z-buffer or depth buffer algorithm employs a special data structure called the z-buffer or depth buffer. The z-buffer is a large memory array which is the same size as the frame buffer -- that is, the z-buffer stores an entry for each pixel. This entry consists of the current depth as well as the current color or intensity of the corresponding pixel. Using this data structure, the z-buffer algorithm proceeds much as the heedless painter visiting each polygon in turn, but with one crucial difference: a pixel is overpainted -- that is, a new color or intensity is stored in the z-buffer -- only ifdepth of current polygon at pixel < current depth of pixel in z-buffer.The z-buffer begins with the color or intensity of each pixel initialized to the background color or intensity, and the depth of each pixel initialized to infinity. To make the z-buffer algorithm as fast as possible, the depth of the pixels in each polygon can be computed incrementally.To compute the depth of each pixel incrementally, we proceed almost exactly as we did in 2Lecture 21 for Gouraud and Phong shading, where we computed the intensities and normal vectors at the pixels of a polygon incrementally.i. First, compute the depth at the vertices of the polygon. After pseudoperspective, this depth is typically just the value of the z-coordinate at each vertex.ii. Next, compute the depth along the edges of the polygon.iii. Finally, compute the depth along scan lines for the pixels in the interior of the polygon.The explicit details of this computation are given below.Recall that for a line € L(t) passing through the points € P1,P2€ L(t) = (1− t) P1+ tP2= P1+ t(P2− P1)€ L(t + Δt) = P1+ (t + Δt )(P2− P1).Subtracting the first equation from the second equation yields€ ΔL = Δt(P2− P1)or equivalently€ Δx = Δt( x2− x1)€ Δy = Δt( y2− y1)€ Δz = Δt(z2− z1).Thus along any line we can compute depth incrementally by setting€ znext= zcurrent+ Δz.Along a scan line€ Δx = 1⇒ Δt =1x2− x1⇒ Δz =z2− z1x2− x1,and when we move to the next scan line along a polygonal edge€ Δy = 1⇒ Δt =1y2− y1⇒ Δz =z2− z1y2− y1.If these computations are not completely familiar, you should review Gouraud shading in Lecture 21, Section 3.The advantages of the z-buffer algorithm are that the z-buffer is simple to understand and easy to implement; the disadvantages are that the z-buffer is memory intensive and relatively slow, since this algorithm may repaint the same pixel many times. The next algorithm we shall study avoids both of these drawbacks by introducing more complicated data structures.4. Scan LineThe scan line


View Full Document

Rice COMP 360 - Hidden Surface Algorithms

Documents in this Course
Radiosity

Radiosity

42 pages

Radiosity

Radiosity

22 pages

Load more
Download Hidden Surface Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Hidden Surface Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Hidden Surface Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?