Hidden Surface AlgorithmsRon GoldmanDepartment of Computer ScienceRice UniversityPolygonal ModelsStandard Assumptions (Always)1. Surfaces are planar polygons2. Surfaces are opaqueAdditional Assumptions (Sometimes)3. Surfaces completely enclose a solid4. Surfaces form a manifold -- No dangling polygons or edgesObjectiveDisplay only those polygons visible to the eyeCull Backfacing PolygonsTestN •(E − Q) ≤ 0N = normal to polygon pointing out of the solid E = eye positionQ = any point on the polygon (e.g. a vertex)Remove backfacing polygons before Perspective (Pseudoperspective) -- need the eye pointProceeding with other algorithms -- fasterHidden Surface AlgorithmsTypes• Object Space = Model Space -- Before Perspective Projection• Image Space = Pixel Space (Frame Buffer) -- After Perspective ProjectionTo Increase Speed• Store additional information• Use pixel coherenceMain Technique• SortingObject SpaceAlgorithmFor each polygonFind unobstructed partRender itWhenBefore perspective (pseudoperspective)SpeedO(n2) -- n = number of polygonal facesImage SpaceAlgorithmFor each pixelFind the closest objectRender itWhenAfter perspective (pseudoperspective)SpeedO(nN)N = number of pixelsn = number of polygonal facesRemarkMost raster display algorithms work in image space.Image Space Algorithms1. Heedless Painter2. Z-Buffer (Depth Buffer)3. Scan Line AlgorithmHeedless PainterAlgorithm• Paint polygons in order in which they occur in some list• Overpaint preceding polygonsProblems• Slow -- painting same pixel many times• May be incorrect -- give an exampleZ-Buffer (Depth Buffer)Data Structure Z-Buffer = Large ArrayAlgorithm• For each pixel, store the following informationi. Current depth (Depth buffer)ii. Current color and intensity• Use painter’s algorithm -- visit each face in turn• Overwrite pixel only if depth<current depth• Compute depth of each pixel in polygon incrementallyAdvantages DisadvantagesSimple to understand Slow -- paints same pixel many timesEasy to implement Memory intensiveLinear InterpolationDerivation€ L(t) = (1− t)P1+ tP2L(t) = P1+ t(P2− P1)L(t + Δt) = P1+ (t + Δt)(P2− P1)__________________________ΔL = Δt(P2− P1)•Δx = Δt(x2− x1)•Δy = Δt(y2− y1)•Δz = Δt(z2− z1)znew= zold+ ΔzIncremental Depth ComputationAlong a Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)••••Δx = 1 }Δx = 1 ⇒ Δt = 1/( x2− x1)Δy = 0Δz = (z2− z1)Δt = (z2− z1)/(x2− x1)Next Scan LineP1= (x1, y1,z1)P2= ( x2, y2, z2)(x, y, z)(x + Δx, y + Δy, z + Δz)•••• {Δy = 1Δy = 1 ⇒ Δt = 1 /(y2− y1)Δz = (z2− z1)Δt = (z2− z1)/(y2− y1)Scan Line AlgorithmData Structure• For each scan line, maintain an Active Edge List• For each edge, store a pointer to its polygon• For each face, storei. whether or not it covers the current pixelii. depth at the current pixel -- computed incrementallyActive Edge List (AEL)•€ EdgeData = (Ymax, current Xint, current Zint, Δx, Δz)• Introduce new edges as they become active -- see Edge Table• Remove old edges as they become inactive -- see YmaxEdge Table• For each scan line, a list of those edges whose lower vertex lies on the line.• Data -- Same as AELPolygonScan Line€ •€ •VertexVertexEdge€ •€ •€ •€ •VertexVertexVertexVertexEdgeEdgeEdgeEdgeEdgeScan LineScan LineScan LineScan Line Algorithm (continued)AlgorithmFor each scan line:• Update the AEL.• Select the polygon corresponding to the first edge in the AEL.• Fill with the current polygon color/intensity until a closer polygon is encountered along the scan line.i. If the next polygon in the AEL has both end points behindthe current polygon’s end points, then there is no need toswitch polygons (look ahead in the AEL). Fill the run withthe current polygon.ii. If the next polygon to enter the AEL has an end point infront of one of the current polygon’s end points, then compute where the cross over occurs (see below) and switch polygons at the crossover.Active Edge List (AEL)Edge Data€ (Ymax, current Xint, current Zint, Δx, Δz)Update AlgorithmFor each edge in the active edge list,If Yscan line> Ymax, delete the edge from the active edge list.Else update the values of current Xint and current Zint using € Δx and € Δz.For each edge in the edge table for the current scan line (Yscan line),Insert the edge to the active edge list.Sort the active edge list by increasing values of current Xint.CrossoverScan LineScan LineCrossoverProblemGiven the depths z,z * of 2 polygons at the same point along a scan line,find the pixel at which the polygons intersect.Solutionz + NΔz = z * + NΔz *N =z * −zΔz − Δz *•z,z * are known -- current depths•Δz,Δz * are known -- see z-buffer algorithmScan Line Algorithm (continued)Observations• Only one crossover can occur per polygon pair,but a polygon may become inactive by ending.• Whenever a covering polygon exits the active list, choose the polygon that is next closest.• Look ahead in polygon list for intersections.• Compute depth of each pixel in polygon incrementally.• Fast because of scan line coherence.• Integrates well with Gouraud and Phong shading algorithms.Object Space Algorithms1. Ray Casting2. Depth Sort 3. BSP-TreeRay CastingAlgorithmThrough each pixel, fire a ray to the eye:• Intersect ray with each polygonal plane.• Reject intersections that lie outside the polygon.• Accept the closest remaining intersection -- smallest t.Advantages• Can use with non-polygonal surfaces -- e.g. spheres.• Requires only Line/Surface intersection algorithm.Disadvantages• Through each pixel, instead of for each polygon.• No coherence -- dense sampling -- slow.Ray Casting (continued)Intersection of Line and PlaneLine Equation (Parametric): L(t) = E + tvPlane Equation (Implicit): N •(P − Q) = 0Solve Linear Equation:N •(L(t) − Q) = N • (E + tv − Q) = 0t =N •(Q − E)N • vInside/Outside Test• Convex Polygon -- Half plane test N •(P − Q) > 0• Concave Polygon -- Fire ray in plane of polygon• # intersection even ⇒ outside• # intersection odd ⇒ insidePoint Inside Polygon€ P1€ P2€ P3€ P4€ P5€ •€ •€ •€ •€ •€ •€ Q€ N12€ N23€ N34€ N45€ N51€ LTest 1: (Convex Polygons)€ (Q − Pi)• Ni,i+1≥ 0for all inward normals € Ni,i+1Test 2: (Arbitrary Polygons)€ #(L ∩ Polygon) is odd for any ray L through