1、中國地質大學計算機學院Visible Surface Detection中國地質大學計算機學院Visible Surface DetectionGoal: Determine which surfaces are visible and which are not. Other names:Hidden-surface removal Hidden-surface eliminationDisplay ALL visible surfaces, do not display ANY non-visible surfaces.We can categorize intoObject-space

2、methods（景物空間消隱、物空間）Image-space methods（圖像空間消隱、像空間）中國地質大學計算機學院Hidden Surface EliminationObject space algorithms: determine which objects are in front of othersResize doesnt require recalculationWorks for static scenesMay be difficult to determineImage space algorithms: determinewhich object is visibl

3、e at each pixelResize requires recalculationWorks for dynamic scenes中國地質大學計算機學院Dont draw surfaces facing away from viewpoint: Assumes objects are solid polyhedraUsually combined with additional method(s)Compute polygon normal n:Assume counter-clockwise vertexorderFor a triangle (a, b, c): n = (b a)

4、(c a)Compute vector from viewpoint to anypoint p on polygon v:For orthographic projection: v = 0 0 1TFor perspective projection: v = p - eyeFacing away (dont draw) if angle betweenn and v is less than 90 dot product n v 0Back-Face Cullingabcnxyz中國地質大學計算機學院 Back-Face Culling ExampleV = (-1, 0, -1)N2=

5、(-3, 1, -2)N1 V = (2, 1, 2) (-1, 0, -1) = -4, so N1 V 0so N2 back facing polygon中國地質大學計算機學院List Priority AlgorithmsA visibility ordering is placed on the objectsObjects are rendered back to front based on that orderingProblems:overlapping polygonsxz中國地質大學計算機學院Painters Algorithm（畫家算法）Object-space alg

6、orithmDraw 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 objectsNeed special processing if polygons overlap in depth中國地質大學計算機學院Depth Sort Algorithm（深度排

7、序算法）An extension to the painters algorithmPerforms a similar algorithm but attempts to resolve overlapping polygonsAlgorithm:Sort objects by their minimum z value (farthest from the viewer)Resolve any ambiguities caused by overlapping polygons, splitting polygons if necessary（重疊多邊形處理，分割）Scan convert

8、 polygons in ascending order of their z values (back to front)中國地質大學計算機學院Depth-Sort AlgorithmDepth-Sort test for overlapping polygons:Let P be the polygon furthest back in the sorted listBefore scan converting P, we must make sure it does not overlap another polygon and obscure itDepth-Sort Algorith

9、mFor each polygon Q that P might obscure, we make the following tests. As soon as one succeeds, there is no overlap, so we quit:Do the x extents of the polygons not overlap?Do the y extents of the polygons not overlap?Is P entirely on the opposite side of Qs plane from the viewpoint?Is Q entirely on

10、 the same side of Ps plane as the viewpoint?Do the projections of the polygons onto the (x, y) plane not overlap?（P、Q在xoy平面投影）中國地質大學計算機學院中國地質大學計算機學院Test 3 succeeds:Test 3 fails, test 4 succeeds:zQPzQPxx中國地質大學計算機學院Depth-Sort AlgorithmIf all 5 tests fail, assume that P obscures Q, reverse their roles,

11、 and repeat steps 3 and 4If these tests also fail, one of the polygons must be split into multiple polygons and the tests run again（多邊形分割）中國地質大學計算機學院Binary Space Partition (BSP) TreeRecursively subdivide space to determine depth order: （遞歸細分）Think of scene as clusters of objectsFind plane that separ

12、ates two clusters（兩組）Cluster on same side of plane as viewpoint can obscure, but cannot be obscured by, cluster on other side of planeRecursively subdivide clusters by finding appropriate planesStore subdivision (space-partioning) planes in a binary tree（二叉樹）Node: stores a polygon and a space partio

13、ning planeLeft child: subtree of objects on positive side of planeRight child: subtree of objects on negative side of planeVery efficient for static scenesNew viewpoints calculated quickly中國地質大學計算機學院BSP Trees: Basic Idea+In the plane (= 0)Behind the plane ( side)eyet2t1In front of the plane (+ side)

14、中國地質大學計算機學院BSP Trees: Basic Idea (cont.)Assume (for now) the polygons do not cross the planeLet f (p) be the implicit equation of a plane evaluated at p if (ft1(eye) 0) then draw t1 draw t2 else draw t2 draw t1+In the planeBehind theplaneeyet2t1Works for any eye point!中國地質大學計算機學院BSP AlgorithmBSP Tre

15、e: partitions space into positive and negative sidesNode: polygon and a space partioning planeLeft (right) child: subtree of objects on positive (negative) side of planeUse a modified in-order traversal to draw the scene:Start at rootCompute which side of nodes plane eye is onRecursively scan conver

16、t polygonson opposite side from eyeScan convert nodes polygonRecursively scan convert polygonson same side as eye123Root polygon+4+eye中國地質大學計算機學院BSP Tree AlgorithmSelect a polygon and make it the rootPartition space into two half-spaces determined by the normal of the root polygonIf a polygon is int

17、ersected by the plane, split the polygon into two polygons, one in each half spaceSelect one polygon in the roots front and one in the roots back and assign them as children of the rootRecursively subdivide space depending on each of the children generated from step 4.Stop when a sub-space contains

18、a single polygon中國地質大學計算機學院BSP Tree exampleInitial Scene:12345中國地質大學計算機學院BSP Tree exampleSelect polygon 3 as the root12345124a4b534a4bfrontback中國地質大學計算機學院BSP Tree exampleSelect polygons 2 and 4b as the next nodes123451b4a34a4b4b21a51b1afrontback中國地質大學計算機學院BSP Tree exampleSelect polygon 1b as the nex

19、t node1234534a4b4b21a51b1a1b4afrontback中國地質大學計算機學院BSP TreeOnce the tree is built, you can scan convertThe viewpoint will be in one of the subspacesTo scan convert properly:Recursively scan convert all polygons in the roots subspace that doesnt contain the viewpointThen scan convert the rootThen recu

20、rsively scan convert the subspace that contains the viewpoint中國地質大學計算機學院BSP Tree exampleSuppose the viewpoint is as shown:Since the eye is in front of 3, scan convert the polygons in back of 3 first34b21a51b4afrontback123454a4b1b1aeye中國地質大學計算機學院BSP Tree exampleThe eye is behind 4b, so scan convert t

21、he polygons in front of 4b first (there are none) Then scan convert 4b, then scan convert the polygons in back of 4b (5)123454a4b1b1a34b21a51b4afrontbackeye中國地質大學計算機學院BSP Tree exampleNext scan convert 3Then scan convert the polygons in front of 334b21a51b4afrontback123454a4b1b1aeye中國地質大學計算機學院BSP Tre

22、e exampleThe eyepoint is behind 2, so scan convert the polygons in front of 2 first34b21a51b4afrontback123454a4b1b1aeye中國地質大學計算機學院BSP Tree exampleThe eyepoint is behind 1b, so scan convert the polygons in front of 1b first (none)Then scan convert 1b, then the polygons behind 1b (4a)34b21a51b4afrontb

23、ack123454a4b1b1aeye中國地質大學計算機學院BSP Tree exampleThen scan convert 2Then scan convert the polygons behind 2 (1a)34b21a51b4afrontback123454a4b1b1aeye中國地質大學計算機學院BSP Tree exampleSo, the final ordering is:4b, 5, 3, 1b, 4a, 2, 1a34b21a51b4afrontback123454a4b1b1aeye中國地質大學計算機學院BSP Trees: SummaryHow do you pic

24、k the first triangle?Trial and errorPick a few permutations at random and try them out（挑選幾個隨機序列）Its a pre-process: dont worry much about build speedO(N) traversal on averageCan be worse since it creates more triangles!Eye can be placed anywhereNo problems with resizing中國地質大學計算機學院Z-Buffering（深度緩存算法）I

25、mage precision algorithm:Determine which object is visible at each pixelOrder of polygons not critical（多邊形順序隨機）Works for dynamic scenesBasic idea:Rasterize (scan-convert) each polygonKeep track of a z value at each pixelInterpolate z value of polygon vertices during rasterizationReplace pixel with n

26、ew color if z value is smaller (i.e., if object is closer to eye)Z-Buffering中國地質大學計算機學院Z-bufferFrame-buffer000000000000000000005080中國地質大學計算機學院Scan Line Algorithms(掃描線算法)Image precisionSimilar to the ideas behind polygon scan conversion, except now we are dealing with multiple polygonsNeed to determi

27、ne, for each pixel, which object is visible at that pixelThe approach we will present is the “Watkins Algorithm”中國地質大學計算機學院Watkins AlgorithmSimilar to the edge table idea used in polygon scan conversion（有效邊表算法）Create an Edge Table (ET)Entries in the edge table have the following format:X is the x co

28、ordinate of the endpoint with the smaller y coordinateYmax is the y coordinate of the endpoint with the greatest Y valuedx is the x increment used in going from one scan line to the nextID is the polygon to which this edge belongsXYmaxdxIDnext中國地質大學計算機學院Watkins Algorithm - contEdges are sorted by sm

29、allest Y value and placed in buckets accordinglyWe also need a Polygon Table (PT) that contains information about the polygonsEntries in the polygon table have the following format:ID is the id of this polygonPlane Coefs are the coefficients of the plane in which this polygon liesShading info is the

30、 color or shading info to be used in the scan conversion of the polygonIn/Out flag - a boolean flag to be used in scan conversionIDPlane CoefsShading InfoIn/Out Flag中國地質大學計算機學院Watkins Algorithm - contIn addition to the ET and PT, we keep an Active Edge Table (AET), similar to the one used in single

31、polygon scan conversionProcess scan line by scan line, left to rightInitially all polygon In/Out flags are FALSEWhen a scan line intersects and edge, that polygons In/Out flag is set to TRUE.中國地質大學計算機學院Watkins Algorithm - contIf two or more In/Out flags are TRUE, use the plane equations for the poly

32、gons to determine which intersected polygon is in frontY = the current scan lineX = the intersection point between the scan line and the edgesZ is computed using the plane equationsIf we have non-penetrating polygons, shade with one polygons color until the next edge intersection, then update accordingly.中國地質大學計算機學院Watkins Algorithm - contWhat about penetrating polygons?Break them into sub-polygons and scan convert the sub-polygonsY1Y2Y3中國地質大學計算機學院An area-subdivision techniqueIdea:Divide an area into four equal sub