Implementation II Ed Angel Professor of Computer Science, Electrical and Computer Engineering, and Media Arts University of New Mexico

  • Published on
    05-Jan-2016

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

  • Implementation IIEd AngelProfessor of Computer Science, Electrical and Computer Engineering, and Media ArtsUniversity of New Mexico

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009ObjectivesIntroduce clipping algorithms for polygonsSurvey hidden-surface algorithms

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Polygon ClippingNot as simple as line segment clippingClipping a line segment yields at most one line segmentClipping a polygon can yield multiple polygons

    However, clipping a convex polygon can yield at most one other polygon

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Tessellation and ConvexityOne strategy is to replace nonconvex (concave) polygons with a set of triangular polygons (a tessellation)Also makes fill easierTessellation code in GLU library

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Clipping as a Black BoxCan consider line segment clipping as a process that takes in two vertices and produces either no vertices or the vertices of a clipped line segment

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Pipeline Clipping of Line SegmentsClipping against each side of window is independent of other sidesCan use four independent clippers in a pipeline

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Pipeline Clipping of Polygons

    Three dimensions: add front and back clippersStrategy used in SGI Geometry EngineSmall increase in latency

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Bounding BoxesRather than doing clipping on a complex polygon, we can use an axis-aligned bounding box or extentSmallest rectangle aligned with axes that encloses the polygonSimple to compute: max and min of x and y

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Bounding boxesCan usually determine accept/reject based only on bounding boxrejectacceptrequires detailed clipping

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Clipping and VisibilityClipping has much in common with hidden-surface removalIn both cases, we are trying to remove objects that are not visible to the cameraOften we can use visibility or occlusion testing early in the process to eliminate as many polygons as possible before going through the entire pipeline

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Hidden Surface RemovalObject-space approach: use pairwise testing between polygons (objects)

    Worst case complexity O(n2) for n polygonspartially obscuringcan draw independently

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Painters AlgorithmRender polygons a back to front order so that polygons behind others are simply painted over

    B behind A as seen by viewerFill B then A

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Depth SortRequires ordering of polygons first O(n log n) calculation for orderingNot every polygon is either in front or behind all other polygons

    Order polygons and deal with easy cases first, harder later

    Polygons sorted by distance from COP

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Easy CasesA lies behind all other polygonsCan render

    Polygons overlap in z but not in either x or yCan render independently

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Hard CasesOverlap in all directionsbut can one is fully on one side of the othercyclic overlappenetration

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Back-Face Removal (Culling)face is visible iff 90 -90equivalently cos 0or v n 0plane of face has form ax + by +cz +d =0but after normalization n = ( 0 0 1 0)T need only test the sign of c

    In OpenGL we can simply enable cullingbut may not work correctly if we have nonconvex objects

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Image Space ApproachLook at each projector (nm for an n x m frame buffer) and find closest of k polygonsComplexity O(nmk)Ray tracing z-buffer

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009z-Buffer AlgorithmUse a buffer called the z or depth buffer to store the depth of the closest object at each pixel found so farAs we render each polygon, compare the depth of each pixel to depth in z bufferIf less, place shade of pixel in color buffer and update z buffer

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009EfficiencyIf we work scan line by scan line as we move across a scan line, the depth changes satisfy ax+by+cz=0Along scan line y = 0z = - x

    In screen space x = 1

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Scan-Line AlgorithmCan combine shading and hsr through scan line algorithmscan line i: no need for depth information, can only be in noor one polygon scan line j: need depth information only when inmore than one polygon

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009ImplementationNeed a data structure to storeFlag for each polygon (inside/outside)Incremental structure for scan lines that stores which edges are encountered Parameters for planes

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Visibility TestingIn many realtime applications, such as games, we want to eliminate as many objects as possible within the applicationReduce burden on pipelineReduce traffic on busPartition space with Binary Spatial Partition (BSP) Tree

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009Simple Exampleconsider 6 parallel polygonstop viewThe plane of A separates B and C from D, E and F

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

  • *Angel: Interactive Computer Graphics 5E Addison-Wesley 2009BSP TreeCan continue recursively Plane of C separates B from APlane of D separates E and FCan put this information in a BSP treeUse for visibility and occlusion testing

    Angel: Interactive Computer Graphics 5E Addison-Wesley 2009

Recommended

View more >