Skip to main content
Open navigation menu
Close suggestions
Search
Search
en
Change Language, English
Upload
Sign in
Sign in
0 ratings
0% found this document useful (0 votes)
7 views
34 pages
Documents
There are some computer graphics documents attached here.
Uploaded by
Marshia Mohana
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here
.
Available Formats
Download as PDF or read online on Scribd
Download
Save
Save Documents For Later
Share
0%
0% found this document useful, Mark this document as useful
0%
0% found this document not useful, Mark this document as not useful
Print
Embed
Report
0 ratings
0% found this document useful (0 votes)
7 views
34 pages
Documents
There are some computer graphics documents attached here.
Uploaded by
Marshia Mohana
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content,
claim it here
.
Available Formats
Download as PDF or read online on Scribd
Go to previous items
Download
Save
Save Documents For Later
Share
0%
0% found this document useful, Mark this document as useful
0%
0% found this document not useful, Mark this document as not useful
Print
Embed
Report
Go to next items
Download
Chapter Ten Hidden Surfaces Opaque objects that are closer to the eye and in the line of sight of other objects will block those cies oF portions of those objects from view. In fact, some surfaces of these opaque objects themselves are not visible because they are eclipsed by the objects’ visible parts. The surfaces that ae blocked ot hidden from view must be “removed” in order to construct a realistic view of the 3D scene (see Fig, 1.3 where only three of the six faces of the cube are shown). The identification and removal of these surfaces is called the hidden-surface problem. The solution involves the determination of the closest visible surface along each projection line (Section 10.1). There are many different hidden-surface algorithms. Each can be characterized as either an image-space method, in which the pixel grid is used to guide the computational activities that determine visibility at the pixel level (Sections 10.2, 10.5 and 10.6), or an object-space method, in which surface visibility is determined using continuous models in the object space (or its transformation) without involving pixel-based operations (Sections 10.3 and 10.4), Notice that the hidden-surface problem has tis to the calculation of shadows. If we place a light source, such as a bulb, at the viewpoint, all surfaces that are vi Je from the viewpoint are lit directly by the light source and all surfaces that are hidden from the viewpoint are in the shadow of some opaque objects blocking the light, 10.1 DEPTH COMPARISONS We assume that all coordinates (x, Ys z) are described in the normalized viewing coordinate system (Chapter 8). . : Any hidden-surface algorithm must determine which edges and surfaces are visible either from the center of projection for perspective projections or along the direction of projection for parallel projections. Computer Graphics 256 The question of visibility reduces to this: given two points Py (1, Yi» 2) and Po (xp, 92, 2s dogs cither point obscure the other? This is answered in wo steps: jection line? aunt ites srrat obscures the other. IF so, depth comparison tll Us which pons front of the other For an orthographic parallel projection onto the xy plane, P; and Py are on the same Projector ig sy = sya; = Yo In this ease, depth comparison reduces to comparing 2, and zy the normalized perspective to parallel transform preserves lines, planes, and 42>! e) y ts! Hidden Surfaces a] Parallel projection of this configuration is [ABCDEFG) Perspective projection of this configuration is. > [ABCDEFG) % y ree 1 Fig. 10.2 IF our display device has display coordinates H x V, application of the scaling matrix ( H00O0 fs 0vo0o0 wvi=lo 9-10 ooo01 < 1 onto the region 0 $x H, transforms the normalized display space 0 Sx <1,0SyS1,0Sz lay transform DT,: O
0 (the angle mea Nand the z axis is less than 90°). The polygon is also classified as a back-face when C = 0, since in this case it is parallel to the line of sight and its projection is either hidden or overlapped by the edge(s) of some visible polygon(s). Although this method identifies and removes back-faces quickly it does not handle polygons that face the viewer but are hidden (partially or completely) behind other surfaces. It can be used asa preprocessing step for other algorithms. 10.4 THE PAINTER’S ALGORITHM Also called the depth sort or priority algorithm, the painter's algorithm processes polygons as if they were being painted onto the view plane in the order of their distance from the viewer. More distance polygons are painted first. Nearer polygons are painted on or over more distance polygons. panially or totally obscuring them from view. The key to implementing this concept is to find a priority ordering of the polygons in order to determine which polygons are to be painted (i.e. scan- Converted) first. Any attempt at a priority ordering based on depth sorting alone results in ambiguities that must be resolved in order to correctly assign priorities. For example, when two polygons overlap, how do we decide which one obscures the other? (See Fig. 10.4.) y 4 @, P °, ie u // Projection of Projection of polygon ie / polygon PandQ D \A— 4, B,C, and D @ — > * © (a) Fig. 10.4 Projection of Opaque Polygons 260 Computer Graphics Assigning Priorities We assign priorities to polygons by determining if a given polygon P obscures other polygons. If the answer is no, then P should be painted first. Hence the key test is to determine whether polygon P does not obscure polygon Q. The z extent of a polygon is the region between the planes 2 = Emin ANd Z = Zpay (Fig. 10.5). Here, Zin is the smallest of the = coordinates of all the polygon’s vertices, and Zax i8 the largest. Similar definitions hold for the x and y extents of a polygon. The intersection of the x, y, and z extents is called r the extent, or bounding box, of the polygon. Fig. 10.5 Testing Whether P Obscures Q Polygon P does not obscure polygon Q if any one of the followin, order, is true. Test 0: The z extents of P and Q do not overlap and Fig. 10.6. ig tests, applied in sequential Zo... of Q is smaller than zp of P. Refer to e oe x Proletionota = Projection of P Fig. 10.6 Fig. 10.7 Test I: oe 1: The y extents of P and Q do not overlap. Refer to Fig. 10.7. * x extents of P and Q do not overlap. "All the vertices of P tie-on that side of the plane containing Q which is far Viewpoint. Refer to Fig, 10.8, Test hest from Hidden Surfaces 261 Pplane Fig. 10.8 Fig. 10.9 ret dz All he vertices of Q lie on that side of the plane containing \ viewpoint. Refer to Fig. 10.9. a ining P which is closest to the rest 5: The projections of the polygons P and checked by comparing each edge of one pol search for intersections. Q onto the view plane do not overlap. This is lygon against each edge of the other polygon to The Algorithm 1, Sort all polygons into a polygon list according tO Zax polygon’s vertices). Starting from the end of the list, assign pri order, as described in steps 2 and 3 (below). 2 Find all polygons Q (preceding P) in the polygon z coordinate of each olygon P, in (the largest orities for each pi list whose z extents overlap that of P (test 3. For each Q, perform tests 1 through 5 until true. (a) If every Q passes, scan-convert polygon P. . (b) If false for some Q, swap P and Q on the IS: Ta Oe tagged, use the plane containing polygon P to divide poly and Q, [see Fig. 10.4(b)]. The polygon" ipping teciaues <6 ‘ division. Remove Q from the list and pI has already been wapped. If Q ‘on Q into two polygons lescribed in Chapter 5 can race Qy and Qs on the Uist be used to perform the in sorted order. cing th 5 a assing, thus reducing the Sometimes the polygons are subdivided int triangles before processing; ; n in step 3 COmputati, Putational effort for polygon subdivis 10 5 SCAN-LINE ALGORITHM soe A s0, 5. an x-scan loop ant ; 7 sted loops. 4" ean ieee algorithm consists essentially of two neste 262 Computer Graphics y Scan ect the polygons to be rendered with the scan plane y = g This For cach y value, say, y = @ inters : er ne se Ys and the resulting intersections are I -gments in this Plane scan plane is parallel to the xz plane, (see Fig. 10.10). Display screen Peat, B, 22) aplane line segments Fig. 10.10 x Scan the x-scan line 1, For each x value, say, x = , intersect the line segments found above with te hat lies 0” x= B lying on the y-scan plane. This intersection results in a set of points tl x-scan line. 2. Sort these points with respect to their z coordinates. The point (x, z value is visible, and the color of the polygon containing this point is the color s° pixel corresponding to this point. st yy 2) with the smal pe at the advantage of In order to reduce the amount of calculation in each scan-line loop, we try to take pris? 1 relationships and dependencies, called coherences, between different elements that ¢ scene. Hidden Surfaces fa 3 types of Coherence 1. Scan-line coherence. If a pixel on likely lie within the polygon. . Edge coherence. If an edge of a polygon i i AN a ; aoe scan lines near the given ca sMerseets a given scan line, it will most likely 3, Area coherence. A small area of an image will most likel 4, Spatial coherence. Certain properties of an object can be determined by evansining th extent of the object, that is, a geometric figure which circumscribes the given object. Usually the extent is a rectangle or rectangular solid (also called a bounding box) sien # sean Tine lies within a polygon, pixels near it will most y lie within a single polygon. Scan-line coherence and edge coherence are both used to advantage in scan-converting polygons (Chapter 3). Spatial coherence is often used as a pre-processing step. For example, when determining whether polygons intersect, we can eliminate those polygons that don’t intersect by finding the rectangular extent of each polygon and checking whether the extents intersect—a much simpler problem (see Fig. 10.11). [Note: In Fig. 10.11 objects A and B do not intersect; however, objects A and C, and B and C, do intersect. In pre-processing, corner points would be compared to determine whether there is an intersection. For example, the edge of object A is at coordinate P; = (6, 4) and the edge of object B is at coordinate P, = (7, 3).] Of course, even if the extents intersect, this does not guarantee that the polygons intersect. See Fig. 10.12 and note that the extents of A’ and B’ overlap even though the polygons do not. oanes iv 1234567891011 Fig. 10.11 Graphics 264 Computer Grap calculations by making them ‘oherences can simplify : r : is is illustrated incremental, as opposed to absolute. Thi in Solved Problem 10.13. A Scan-line Algorithm In the following algorithm, scan-line and edge coherence are used to enhance the processing done in the y-sean loop. Since the y-scan loop constructs alist of potent lly visible line segments, instead of reconstructing this list each time the y-scan line changes (absolute calculation), we keep the list and update it according to how it has hanged (incremental calculation). This processing is facilitated by the use of what is called the edge list, and its efficient construction and maintenance is at the heart of the Algorithm (see Chapter 3, Section 3. under “Scan-line Algorithm”). The following data structures are created: Fig. 10.12 1. The edge list contains all non-horizontal edges (horizontal edges are automatically displayed) of the projections of the polygons in the scene. The edges are sorted by the edge’s smaller y coordinate ()'pj,)- Each edge entry in the edge list also contains: (a) The x coordinate of the end of the edge with the smaller y coordinate. (b) The y coordinate of the edge’s other end (Ymax)+ (c) The increment Ax = I/m. (@) A pointer indicating the polygon to which the edge belongs. 2. The polygon list for each polygon, contains (a) The equation of the plane within which the polygon lies—used for depth determination, ice., to find the z value at pixel (x, y). (b) An IN/OUT flag, initialized to OUT (this flag is set depending on whether a given scan line is in or out of the polygon). (©) Color information for the polygon. The algorithm proceeds as follows. I. Initialization, ) Initialize each screen pixel to the background color, (b) Set y to the smallest y,,in value in the edge list. Repeat s . I. yan lene oe (below) until no further processing can be performed. x - Activate edges whose yin, is equal to y. Sort active edges in order of increasing I. x IH. x-scan loop. Process, from left to right, (a) inves the IN/OUT flag of the pol Sunt the number of active polygor cach active edge as follows: lygon in the polygon list which contains the edge ns whose IN/OUT flag is set to IN. If this number iS (b) 10.6 The subs Hidden Surfaces 265 1, only one polygon is v are set to the color of the polygon by the smallest z z values are found from the equation of the pt from this edge and up to the next edge are an polygon becomes obscured by another before th set the remaining pixels to the color of the obscuring polygon. If this number is 0, pixels from this edge and up to the next : h One are left unchanged. When the last active edge is Processed, we then proceed as follows: 1, Remove those edges for which the value Of Ynax Equals the present scan line value y. if no edges remain, the algorithm has finisher” . 2, For each remaining active edge, in order, intersection with the next scan line y 3. Increment y to y + 1, the next scan li SUBDIVISION ALGORITHM ‘sible. All pixel values Polygon. If this number value of each polygo from this edge and up to the next edge is greater than 1, determine the visible n at the pixel under consideration. These lane containing the polygon. The pixels to the color of this polygon, unless the le next edge is reached, in which case we replace x by x + I/m. This is the edge + 1 (see Solved Problem 10.13). ine, and repeat step II. division algorithm is a recursive procedure based on a two-step strategy that first decides which projected polygons overlap a given area A on the screen and are therefore potentially visible in that area. Second, in each area these polygons are further tested to determine which ones will be visible within this area and should therefore be displayed. If a visibility decision cannot be made, this screen area, usually a rectangular window, is further subdiv can be made, or until the screen area is a single pixel. Starti four sm: ided either until a visibility decision ing with the full screen as the initial area, the algorithm divides an area at each stage into aller areas, thereby generating a quad tree (see Fig. 10.13). Tale] [2]a[2 ‘|? | '| 2) [etetstatstaare 1 2 ajetifalifatie S\4 8/4) Blatarstarste telat feti2 1)? ] "1? | (laptapatetata 3 4 tat fati feta Efi ca Bal 3[4i3[4[slafala Initial area First subdivision Second sutavon asa (a) (o) Fig, 10.13 7 veons P with res| a given screen The processing exploits area coherence by classifying polygons P with respect oa given ser tea A ji the area 8) cont, disjoint polygon—polygon that is disjoin i iygon—polygon that completely contains ing categories: (1) surrounding polygon—polygon te i mo the een eae eiink polygon—polygon that intersects 7 area ed anes Fae ners Completely contained within the are (Fig. 10.14(e)), Fined Polygon— polyenes { from the area (Fig. 10.14(b)]. Computer Graphics 266 om) Pintersects A surrounds A Ps ae te) Pls disjoint from A Pis contained in A (d) © Fig. 10.14 The classification of the polygons within a picture is the main computational expense of the algorithm and is analogous to the clipping algorithms discussed in Chapter 5. With the use of one of these clipping algorithms, a polygon in category 2 (intersecting polygon) can be clipped into a contained polygon and a disjoint polygon (see Fig. 10.15). Therefore, we could proceed as if category 2 were eliminated. A Pi For a given screen area, we keep a potentially visible polygons list (PYPL), those in categories 1, 2, and 3. (Disjoint polygons are clearly Fig. 10.15 not visible.) Also, note that on subdivision of a screen area, surrounding and disjoint polygons remain surrounding and disjoint polygons of the ; newly formed areas. Therefore, only contained and intersecting polygons need to be reclassified. Removing Polygons Hidden by a Surrounding Polygon The key to efficient visibility computation lies in the fact that a polygon is not visible if iis bet! fh runing Polygon. Therefore, it can be removed from the PVPL. To facilitate processing. in list is sorted by zniq. the smallest z coordinate of the polygon within this area, In addition, for &#* Surrounding polygon S, we also record its largest z coordinate, zy " 7 {1 for a polygon P on the list, zp. > zs. (for a surrounding polygon 5), then P is hidée® | and thus is not visible. In addition, all other polygons after P on the list will also be hidden by Wwe can remove these polygons from the PVPL. | Hidde len Surfaces Th gptivision Algorithm 1 ste the area 0 be the whole sercen a PYPL with respect Create Place at BA: Sorted on Zaig (the smallest z coordinate of the * olygon within the area). Place the Polygons in thei Pron DY 2 surrounding polygon and ie Aa categories. Remove polygons 4. Perform the visibility decision tes Heint polygons. list is empty, set all pi {a) If the Ply, set all pixels to the backs: s Pixel ackground color. (b) I hed (eneuoy eee the list and it is a classified as intersecting (category 2) 2 aoa) Scan-convert) the polygon, and color the remaining area (o) If there is exactly one polygon on the list a is z ihe colorof the surreunine polyeod. and it is a surrounding one, color the area with @ i the ages enGeand (x, y), and neither a, b, nor ¢ applies, compute the z coordinate x(a, y) at pixel (x, y) of all polygons on the PVPL. The pixel is then set to the color of the polygon with the smallest z coordinate. 4, If none of the abov area, go to step 2. © cases has occurred, subdivide the screen area into fourths. For each 10.7 HIDDEN-LINE ELIMINATION Although there are special-purpose hidden-line algorithms, each of the above algorithms can be modified to eliminate hidden lines or edges. This is especially useful for wireframe polygonal models where the polygons are unfilled. The idea is to use a color rule which fills all the polygons with the background color—say, black—and the edges and lines a different color—say, white. The use of a hidden-surface algorithm now becomes a hidden-line algorithm. 10.8 RENDERING OF MATHEMATICAL SURFACES In plotting a mathematical surface described by an equation z= F(x, y), where pin SX $Xmax and Vain SYS Yar WE could use any of the hidden-surface algorithms so far described. However, these general algorithms are inefficient when compared to specialized algorithms that take advantage of the structure of this type of surface. | The mathematical surface is rendered as a wire frame model by drawing both the x-constant curves ’ F(const, y) and the y-constant curves 2 = pe ae (see Fig. 10.16). Each such curve Is ren red 2 F polyline, where the illusion of smoothness 1s fe ite by using a fine resolution (i.e., short line segments drawing the polyline (Chapter 3)- Computer Graphics 268 | Choose an Che N pening ron ec ant Sg envevee ding. F(x, yj). An x-constant polyline, say PAR, Yeo Similarly, the y = yy polyline has vertices Qi Os vee Oyu Yd Choosing a view plane and a center of projection or viewpoint C(a, b, c), we create a Iw S Yenax are zy = Xj, has vey The corresponding z values are Z)j = ‘ Ttices Pray, Yy) i na Perspective view of the surface onto this view plane by using the transformations developed in Chapter 7. So point [x,y FQ) projects to a point (p, q) in view plane coordinates, By apply an appropriate 2-dimensional viewing transformation (Chapter 5), we can suppose that p an Ae within the horizontal and vertical plotting dimensions of the plotting device, say, H x V pixels ad Perimeter Method for Rendering the Surface Each plotted x and y constant polyline outlines a polygonal region on the Plotting screen (Fj The algorithm is based on the following observations: (1) ordering—the x- curves (i.e. polylines) are drawn in order starting with the one closest to the (2) visibility—we draw only that part of the polyline that is outside the perimeter of all Previously drawn regions (Fig. 10.18). One implementation of the visibility condition uses a min-max aray of length H (that of the plotting device), which contains, at each horizontal Pixel position i, the maximum (and/or minimum) vertical pixel value drawn thus far at i; that is AG) = (venieal pixel values drawn so far at 4) (Fig. 10.19). Selection of the max results in a drawing of the top of the surface. The min is used to render the bottom of the surface, and the max and min yields both top and bottom. i. 10.17, and conan Viewpoint and 10} 10) u th 4 1 10 Fig. 10.17 Fig. 10.18 The Visibility Test Suppose that (p', 9’) is the de cither nt @'+ 4°) is the pixel that corresponds to the point (p, q). Then this pixel is visible” where Ais the min-max array, 1 7 4® or 4" < A(p’) 269 Hidden Surfaces @ 1 1 1 1 10 t Li 0000000000 ASsazacaae® A 1565466544 Fig. 10.19 Updating min-max Array A (Using Maximum Values Only) The visibility criteria for a line segment are: (1) the line segment is visible if both its endpoints les (2) the line segment is invisible if both its endpoints are not visible; and (3) if only one visible, the min-max array is tested to find the visible part of the line. the x or y-constant polylines thus consists of testing for the visibility of each the min-max array as necessary. Since a line segment will, in general. span 10.19), the computation of A(i) for ment or by using Bresenham’s are visibl endpoint is Drawing segment and updat several horizontal pixel positions (see segment FP; in Fig. these intermediate pixels is found by using the slope of the line seg method described in Chapter 3. Wright Algorithm for Rendering Mathematical Surfaces line F(x, y) proceeds as follows. The drawing of the surface < 1. To perform initialization, determine whether the viewpoint is closer to the x or the y axis. Suppose that it is closer to the x axis. We next locate the x-constant curve that is closest to the viewpoint at x = 1. (a) Initialize the min-max array to some base value, say, zero. (b) Start with the x-constant curve found above. 2. Repeat the following steps using the visibility test for drawing line segments and updating the min-max array each time a line segment is drawn: (a) Draw the x-constant polyline. (b) Draw those parts of each y-constant polyline that lie between the previously drawn x- constant polyline and the next one to be drawn. (¢) Proceed, in the direction of increasing x, to the next x-constant polyline. 10.9 WARNOCK’S ALGORITHM Wamoct" ; eons S algorithm divides the screen into sample areas. If there are no faces of the object within ‘oe then it is left blank. If the nearest polygon completely covers it, then it can be filled in the color of that polygon. If neither of these conditions holds, then the algorithm subdivides Computer Graphics 270 reas and considers each of them in turn. This process i, smaller sample a i : h t a ins only a single pixel or it falls into one of the ye area size remal Fig. 10.20). the sample are: repeated till the sample conditions said above (see Fig. 10.20 Subdivision of a Scene 10.10 WEILER-ATHERTON ALGORITHM Warnock’s algorithm was forced to use image precision operation for termination because it could clip a polygon only against a rectangular area. Weiler-Atherton algorithm subdivides the screen area along polygon boundaries rather than along rectangular boundaries. This requires a powerful clipping algorithm that can clip even a concave polygon against another. This involves the following steps. 1. Sort the polygons according to the depth z. 2. Clip all the polygons based on the polygon closest to the viewer. 3. Remove the polygons behind that polygon nearest to the eye point. 4. If required, use a final sorting method with respect to the depth z and recursive subdivision to remove any ambiguities, 10. : 0.1 Given points Pi(1, 2, 0), P3(3, 6, 20), and P,(2, 4, 6) and a viewpoint C(0, 0 = letermine which points obscure the others when viewed from C. Hidden Surfaces 271 soining the viewpoint C(0, 0, -10) and point P,(1, 2, 0) is (Appendix 2 The ine Jone yet ye2t ~10 + 101 i is line, we see that x = 3 when 1 = 4 P,(3, 6, 20) lies on this that ‘0 dere gent z= 20. So P, lies on the projection line throu: ait = 3.45 imine which point is in front Yext we determine which poi rarer att= 1, and P, occurs at f= ath respect to C; that is, P; obscures P), We now determine whether Ps (2, 4, 6) is on the line. Now x= 2 when = and then 4,and ¢ = 10. Thus P3 (2, 4, 6) is not on this projection line and so it nether obscures y=4and ‘ nor is obscured by P, and P>. 3, and then gh C and P,, ith respect to C. Now C occurs on the line at 3. Thus comparing 1 values, P\ is in front of P, 12. Construct the perspective to parallel transform T,, which produces an object whose parallel projection onto the xy plane yields the same image as the Perspective projection of the original object onto the normalized view plane z = ¢//(c! +b) (Chapter 8, Solved Problem 8.6) with respect to the origin as the center of projection. The perspective projection onto the plane z= (Chapter 7, Solved Problem 7.4): cic] + b) with respect to the origin is x 0 0 0 5 \0 x 0 Realy 5 z 0 0201 dos0 where 2, = c{(e! + b). The perspective projection onto the view plane of a point P(x, is the point Define the perspective to parallel transform T, to be 2 0 0 0 1 0 0 0 (where z - a 5 Ived Zr is the location of the normalized front clipping plane; see Chapter 8, Solv Problem 8.6). Computer Graphics 272 rm T;, to the point PC, ¥, 2), we get the Now, applying the perspective to parallel transfor point 7) The parallel projection of Q’ onto the xy plane produces the point of Ato) So Q’ and P’ produce the same projective image. Furthermore, 7, transforms the Normalizeg Y= UY=-Z,2= Zand cf Z= 1 to th -Zy. 2 = 0, and z= 1, ° perspective view volume bounded by x = z= rectangular volume bounded by x = z, 3. Show that the normalized perspective to parallel transform NT, preserves the relationships of the original perspective transformation while transforming the normalized perspective S view volume into the unit cube. From Solved Problem 10.2, the perspective to parallel transform 7, transforms a point P(x, ¥. 5) to a point z a4) The image under parallel projection of this point onto the xy plane is of The factor z, can be set equal to 1 without changing the relation between points Q and Q’. x YSU Tis then a) The matrix that transforms P(x, y, z) to the point of i 0 -% jo the {n addition, this matrix transforms the normalized perspective view votnme \220,and2=1 fectanguar view volume bounded by x = 1, x=-1, y= 1 = A the © next translate this view volume so that the corner point (-1, -1, 0) transla origi " gin. The translation matrix that does this is Hidden Surfaces 273 1000 0100 oo10 1101 ‘The new region is a volume bounded by x = 0, x=2, y=0,y=2,2=0,and 2<1, Finally, we scale in the x and y direction by a factor 1 so that the final view volume is = 0, and z= 1° The scaling matrix is the unit cube: x= 0, x= 1, y=0, ° 00 Sirana = 10 o1 eo oN cont The final normalized perspective to parallel transform is 1 2 0 0 0 1 Oo 0 0 2 NT, =F, Taro Sinina=|L 1 1 2.2 Inzy 00 —~o my 10.4 Why are hidden-surface algorithms needed? Hidden-surface algorithms are needed to determine which objects and surface will obscure those objects and surfaces that in back of them, thus rendering a more realistic image. 5) obscures 10.5 What two steps are required to determine whether any given point P(x. another point P3(x>, y3, 23)? (See Fig. 10.1.) It must be determined (1) whether the two points lie on the same p' (2) if they do, which point is in front of the other. rojection line and 10.6 Why is it easier to locate hidden surfaces when parallel projection is used? There are no vanishing points in parallel projection, As a result, any point P (a, 6, 2) will other point having the same x and y coordinates (a, b). line on the same projector as any £00 be compared to determine which point is closest to the Thus only the z component must viewer. Computer Graphics 274 10.7 How does the Z-butfer algorithm determine which surfaces are hidden? The Z-buffer algorithm sets dimensional array which is like the frame bute, x the Z-buffer stores the depth value at each pixel rather than the color, which stored in the frame buffer. By setting the initial values of the Z-buffer to some large Humber, usually the distance of back clipping plane, the problem of determining whe, surfaces are closer is reduced to simply comparing the present depth values stored in the Zbuffer at pixel (x, y) with the newly calculated depth value at pixel (x, y). If this ney value is less than the present Z-buffer value (i.c. closer along the line of sight), this vaty replaces the present value and the pixel color is changed to the color of the new surface. ° p a two- howev 10.8 Using a 2 x 2 pixel display, show how the Z-buffer algorithm would determine the colo of each pixel for the given objects A and B in Fig. 10.21. Display space Display screen u 1 2 x Pixe! coordinates Fig. 10.21 ‘The display space Play space for the 2 x 2 pixel display is the region 0 $x $2, 0S 1 9) and Ax? line A is o . is On the displa wean tn’ f, ce isplay sereen in front of square B. B is the square with display coordinates B (0 0! nat? er (2.0.5), ,(2.2,1). ana a,(0,2, 1) Te asve 2 Of A (after projecti T projection and scan conv ne $1. In Fig. 10.21, 4 ii ine wi + Ais the line with display space coordinates A, (3 2. ersion) would appear on a2 x 2 pixel displ Hidden Surfaces 1[y]a ofaly oT where @ is the color of A and y is the background color. We have used Section. 3.1) that a point (x, y) sean-converts (o the pixel [Floor (x). Flo sistency that 2 = 1.99...) The displayed image of B is the fact (Chapter 3, r(y)]. (We assume 1 b |b} 0 bib 0 1 where b is the color of B. We apply the Z-buffer algorithm to the piture composed of objects A and B as follows: : 1, Perform initialization. The Z-butfer is set equal to the depth of the back clipping plane 1, and the frame buffer is initialized to a background color y. - lfyTy ifiti Frame buffer = 2 Zee oly Ty so, Laoha oT 0 1 2. Apply the algorithm to object A. (a) The present Z-buffer value at pixel (0, 0) is that of the back clipping plane. ie. Zp (0, 0) = 1. The depth value of A at pixel (0, 0) is z = 0. Then Z,,,(0. 0) is changed to 0 and pixel (0, 0) has the color of A. 1 py 1 fafa Fra 3 aa Zoot = vame butfer= | FEL 2S Aue FG 01 00 (b) Object A is not seen from pixel (1, 0), so the Z-butfer value is unchanged. 1 fy Ty 1 fifi rame=§ [211 aay ts 01 ot (©) Object A is not seen from pixel (0, 1), so the Z-buffer value is unchanged: yyy Zant tj Frame=y Foo) Zu = 9 Tol Ot one cent Z-butter n the pres (€) The depth value of A at pixel (1, 1) is 0. Since this is less Value of 1, pixel (1, 1) takes the color of A. I Frame = rame = 5 76 Computer Graphics 3. Apply the algorithm to B. i = 0. So the color of pi (a) The depth value of B at pixel (0, 0) is 4, and Ziyi(0, 0) = 0. So the color of pixey (0, 0) is unchanged Tai 1 1] 0 1 [ya = Frame = 9 fa fy Sout ololi 041 oot a py F (b) The depth value of B at pixel (1, 0) is. The present Z-buffer value is 1. So the Z-buffer value is set to j and pixel (1, 0) takes the color of B. l fy ]a 1etly Frame = Zou Olalb 0 10 0 1 0 Hlri-lo (©) The depth value of B at pixel (0, 1) is 1. The present Z-but color at pixel (0, 1) is set t fer value is 1, so the fo that of B, and the Z-buffer is updated. fo pa 1Jt to Frame = ae 2 ; 0 b 0 lo “ 2 01 01 (4) The depth value of B at pixel (1, 1) is 7 - The present Z-buffer value is 0. So the color at pixel (1, 1) remains unchanged. t}ola 1 |i to Frame = Zu olelo o|t rn] oT The final form of the Z-buffer indicates th ‘at line A lines in front of B. 10.9 What is the max i r 5 z-bulfer imum number of objects that ea eeenty sing the Z-bu! algsrithm? OF objects that can be presented by using ; . itrary , The tota number of objects that can be handled by the Z-buffer algorithm is abit Ssause each object is processed one at time, a to How does the basic sean-line method determine which surfaces are hidden? 10. ? ‘The basic scan-line method looks one at a time at each of the horizoy the display area. For example, at the horizontal pixel line y = (consisting of all scan-converted polygons) is searched to horizontal (y) pixel values equal toa Next, the algorithm looks at each individual pixel in the a row. At pixel (a B), the depth values (< values) of each polygon found above are compared to find the polygon having the smallest z value at this pixel. The color of pixel (c, B) is then set tothe vole the corresponding polygon at this pixel. nal lines of pixels in @ the graphics data structure find all polygons with any he four pixel display and the graphics objects A and B from Solved Problem 10.8, show how the basic scan-line method would display these objects, 10.11 First we initialize the display to the color y of the back clipping plane (located at z = 1) lfyyy] Frame = 5 01 1, Set y = 0. The scan-converted representations of A and B contain pixels on the y = 0 scan line. (a) Set x = 0. Comparing the z values of A and B at pixel (0, 0), we find that the smaller z value is 0, which belongs to A. Thus A is seen from pixel (0, 0): that is, Pixel (0, 0) is set to the color of A. T}yly olely 0.1 () Set x= 1. Since A is not seen from pixel (1, 0) while B is seen, the color of pixel (1, 0) is set to that of B. Ifyfy Olaly 01 _ > Set y= 1. The scan-converted representations of A and B contain pixels on the» Scan line, (®) Set.x=0, Since A is not seen at pixel (0, 1) while B is seen, pixel (0, 1) is set the color of B, I}yjy ofalb xel (1, 1) (b) 6 01 y Stx= 1, Both A and B are “seen” from pixe '80, that of Bis 1 2 1 (1, 1). The depth of A at pi Thus A is visible at pixel (1, 1). 278 10.12 10.13 Computer Graphics ify ofa|s 01 This trame buffer represents the final image displayed. iona 9 How does edge coherence help to reduce computational effort? Tt is based on the assumption that, if an edge or line intersects a given scan line, it wil} most likely intersect the scan lines next to it. Thus if the pixels that intersect the edge are to be found, instead of intersecting each scan line with the edge, it is sufficient to locate only one intersection pixel and then find the others using the slope m of the edge (see Solved Problem 10.13). Show how the calculation of the intersection of an edge with a scan line can be made incremental as opposed to absolute. The absolute calculation requires that we find the x intersection value of the edge (e.g. with equation y = mx + b) with the scan line y = o for each a. The incremental solution to the problem is based on the following observations. Suppose that x, is the x intersection of the edge with the scan line @. Then the intersection Xqa OF the edge with the next scan line y= @ + 1 can be found as illustrated in Fig. 10.22. From Fig. 10.22, where m is the slope of the edge, Ay (a+l)-a@ Ax =m Nast ~ Xa Edge y=mx+b Scan tine y= a+ 1 1 Xawe+d Scan line y= ——__f/ i (av a) rime m ‘Fig. 10.22 Solving for x,.,), we obta Nas) = Xqt — ; m Thus the calculation of the next intersecti i i fro pen ion point is inci ; is, it is found the previous intersection point by E remental; that is, it adding 1/m to it, meee ae How does area coherence reduce computational effort? low S anes 10.14 Area coherence is based on the assumption that a small enough region of en inst likely tie within a single polygon. This reduces, as in the subdivaiy cen computational effort in dealing with all those polygons that are potentially vise given screen area (region of pixels). 10.18 How is spatial coherence determined? Spatial coherence is determined by examining the extent of an object. Th rectangular extent (bounding box) of an object is determined by finding the minivan and maximum and : | Surrounding Hidden Surfaces 285, 4, visibility decision. Applying tests (a) through (c), we now apply test (d) since the region is pixel size. The < coordinate of A at pixel (0, 0) is 0, and that of Bis +. Thug ‘Ais visible at pixel (0, 0): 1 Frame buffer = ole ool Region 2: pixel (0, 1). 2, Forming the PVPL. Note that A is disjoint from this region: Polygon | min Category PVPL = e x Surrounding » Visibility decision. From test (c), there is only one polygon and it is surrounding, so we color the pixel (0, 1) that of B: 1 o fats 01 Region 3: pixel (0, 1). 2. Forming the PVPL. Since A is disjoint from this region, we have Polygon | Znin | Category PVPL = B 3 Surrounding 3. Visibility decision. From test (c), there is only one polygon B and it is surrounding. So region 3 is colored b: 1[o ofalb 01 Region 4: pixel (1, 1), 2. Forming the PPL, Polygon Zain Category PVPL = A 0 Intersecting 1 : + Surrounding B 2 e Visibility decision, Having applied tests (a) through (c), we now apply test (d). The z Coordinate of A at pixel (1, 1) is less than that of B. Thus pixel (1, 1) is set to the color of A: 286 Computer Graphics l| bia Olalob ool This is the final image in the frame buffer. 10.24 How can we use the special structure of a convex polyhedron to identify its hidden faces for a general parallel or perspective projection? Suppose that on each face of the polyhedron there is an outward-pointing normal vector N, attached ata point P of the face (Fig. 10.24), For h face of the polyhedron, let the line- of-sight vector L be the vector pointing from the face to the viewer. For a parallel projection, this is the direction of projection from the object to the projection plane. For a perspective projection, it is the vector PC from the normal vector attached at point P to the viewpoint at point C (Fig. 10.24). is visible if the angle @ made by the line-of-sight vector L and the normal vector N is less than 90°. It is hidden if this angle is larger than or equal to 90°. If 0° < @ < 90°, then 0 < cos @< 1; if 90° < @< 180°, then -1 1), the first polygon written will determine the color of the pixel (see Problem 10.7). 10.3 A priority flag could be assigned to break the tie resulting from the use of Z-buffer algorithm. 10.4 A system that distinguishes 274 depth values would require three bytes of memory to represent each z value. Thus 3 x 1024 x 768 = 2304 KB of memory would be needed. 10.: in The scan-line method can take advantage of (a) scan-line coherence, (b) edge cohe- rence, (c) area coherence, and (d) spatial coherence. 10.6 Scan-line coherence is based on the assumption that if a pixel belongs to the scan-converted image of an object, the pixels next to it will (most likely) also belong to this object. 10.7 Since this figure is a polygon, we need only find the maximum and minimum coordinate values of the vertices A, 3, and C, Then Xmin Fact 2 Ymin Ymax = 2 Zin Zmax = 2 The bounding box is shown in Fig. 10.27. 10.8 Horizontal line segments (Yin ) lic on only one scan line: they are auto- matically displayed when non-horizontal edges are used in the scan-conversion proces We search the z coordinates of the vertices of the polygon for the largest value, zp,,. The depth of the polygon is then set to 10. & 10.10. Area coherence is exploited by classify- ing polygons with respect to a given screen area as either a surrounding polygon, an intersecting polygon, a contained poly- gon, or a disjoint polygon. The key fact is that a polygon is not visible if it is in back of a surrounding polygon. 10.11 When using a hidden-surface algorithm to eliminate hidden lines, we set the fill color of the polygons determined by the lines to the background color. (ETP
You might also like
Hidden Surface Removal in 3D Graphics
PDF
No ratings yet
Hidden Surface Removal in 3D Graphics
2 pages
Hidden Surface Detection in Graphics
PDF
No ratings yet
Hidden Surface Detection in Graphics
8 pages
Depth Buffer and Sorting in Graphics
PDF
No ratings yet
Depth Buffer and Sorting in Graphics
30 pages
Visible Surface Detection
PDF
No ratings yet
Visible Surface Detection
6 pages
Object vs Image Space in Graphics
PDF
No ratings yet
Object vs Image Space in Graphics
9 pages
Visible Surface Detection Algorithms
PDF
No ratings yet
Visible Surface Detection Algorithms
25 pages
Z-Buffer Method in Computer Graphics
PDF
No ratings yet
Z-Buffer Method in Computer Graphics
20 pages
CG Unit 5 New
PDF
No ratings yet
CG Unit 5 New
32 pages
Visibility and Occlusion in Computer Graphics
PDF
No ratings yet
Visibility and Occlusion in Computer Graphics
8 pages
Hidden Surface Detection in Graphics
PDF
No ratings yet
Hidden Surface Detection in Graphics
24 pages
Computer Graphics - Visible Surface Detection
PDF
No ratings yet
Computer Graphics - Visible Surface Detection
7 pages
Computer Graphics - Removal
PDF
No ratings yet
Computer Graphics - Removal
72 pages
Hidden Surface Removal Techniques
PDF
No ratings yet
Hidden Surface Removal Techniques
59 pages
Back Face Removal in Computer Graphics
PDF
No ratings yet
Back Face Removal in Computer Graphics
8 pages
3D Viewing and Projection Techniques
PDF
No ratings yet
3D Viewing and Projection Techniques
9 pages
Visible-Surface Determination Methods
PDF
No ratings yet
Visible-Surface Determination Methods
23 pages
Scan Line Method in Surface Detection
PDF
No ratings yet
Scan Line Method in Surface Detection
10 pages
Visible-Surface Detection Methods
PDF
No ratings yet
Visible-Surface Detection Methods
10 pages
Visible Surface Determination Techniques
PDF
No ratings yet
Visible Surface Determination Techniques
62 pages
Visible Surface Detection Methods in CG
PDF
No ratings yet
Visible Surface Detection Methods in CG
76 pages
Back Face Detection in Computer Graphics
PDF
No ratings yet
Back Face Detection in Computer Graphics
21 pages
Hidden Surface and Line Removal Techniques
PDF
0% (1)
Hidden Surface and Line Removal Techniques
12 pages
Chapter 10 - Hidden Surface Removal
PDF
No ratings yet
Chapter 10 - Hidden Surface Removal
24 pages
Computer Graphics Visibility Methods
PDF
No ratings yet
Computer Graphics Visibility Methods
76 pages
3D Projection Techniques and Algorithms
PDF
No ratings yet
3D Projection Techniques and Algorithms
58 pages
Visual Realism in Computer Graphics
PDF
No ratings yet
Visual Realism in Computer Graphics
69 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
30 pages
Hidden Surface Removal Techniques
PDF
No ratings yet
Hidden Surface Removal Techniques
15 pages
Object Space Hidden Surface Removal
PDF
No ratings yet
Object Space Hidden Surface Removal
10 pages
Hidden Surface Removal Techniques
PDF
No ratings yet
Hidden Surface Removal Techniques
7 pages
Visible Surface Detection Methods
PDF
No ratings yet
Visible Surface Detection Methods
12 pages
Visibility Surface Determination Techniques
PDF
No ratings yet
Visibility Surface Determination Techniques
16 pages
Realism Techniques in 3D Graphics
PDF
100% (2)
Realism Techniques in 3D Graphics
73 pages
Visible Surface Detection Methods
PDF
No ratings yet
Visible Surface Detection Methods
13 pages
Hidden Surface Removal Techniques
PDF
No ratings yet
Hidden Surface Removal Techniques
20 pages
Depth-Buffer Method in 3D Graphics
PDF
No ratings yet
Depth-Buffer Method in 3D Graphics
12 pages
Module 5 - Visible Surface Detection Methods
PDF
No ratings yet
Module 5 - Visible Surface Detection Methods
90 pages
Chapter 5 Visible Surface Detection
PDF
No ratings yet
Chapter 5 Visible Surface Detection
53 pages
Visible-Surface Detection Methods in CG
PDF
No ratings yet
Visible-Surface Detection Methods in CG
24 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
18 pages
Visible Surface Detection Algorithms
PDF
No ratings yet
Visible Surface Detection Algorithms
23 pages
3d Transformation
PDF
No ratings yet
3d Transformation
7 pages
3D Transformations and Projections in Graphics
PDF
No ratings yet
3D Transformations and Projections in Graphics
10 pages
Hidden Surface Removal in Graphics
PDF
50% (2)
Hidden Surface Removal in Graphics
35 pages
Visibility Algorithms in Computer Graphics
PDF
No ratings yet
Visibility Algorithms in Computer Graphics
18 pages
8 Hidden Surf 16
PDF
No ratings yet
8 Hidden Surf 16
29 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
38 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
19 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
131 pages
Hidden Surface Removal Techniques
PDF
100% (1)
Hidden Surface Removal Techniques
15 pages
3D Visible Surface Detection Methods
PDF
No ratings yet
3D Visible Surface Detection Methods
92 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
86 pages
Visibility Methods in Computer Graphics
PDF
No ratings yet
Visibility Methods in Computer Graphics
8 pages
3D Clipping and Rendering Techniques
PDF
No ratings yet
3D Clipping and Rendering Techniques
7 pages
Hidden Surface Elimination Techniques
PDF
No ratings yet
Hidden Surface Elimination Techniques
33 pages
3D Surface Visibility Algorithms
PDF
No ratings yet
3D Surface Visibility Algorithms
61 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
10 pages
Visible Surface Detection Techniques
PDF
No ratings yet
Visible Surface Detection Techniques
122 pages
Overview of Computer Generations and Types
PDF
No ratings yet
Overview of Computer Generations and Types
8 pages
Bangladesh Women's U-20 AFC Qualifiers
PDF
No ratings yet
Bangladesh Women's U-20 AFC Qualifiers
16 pages
B.Sc. Admission Migration List 2018-19
PDF
No ratings yet
B.Sc. Admission Migration List 2018-19
32 pages
CSE Lab Report: Programming Basics
PDF
No ratings yet
CSE Lab Report: Programming Basics
40 pages
AB Bank Complaint Management Contacts
PDF
No ratings yet
AB Bank Complaint Management Contacts
1 page
Cipher Mismatch in Network Security Lab
PDF
No ratings yet
Cipher Mismatch in Network Security Lab
6 pages
Choosing the Right Machine Learning Algorithm
PDF
No ratings yet
Choosing the Right Machine Learning Algorithm
52 pages