MIT EECS 6.837, Cutler and Durand 1 Clipping and other geometric algorithmsMIT EECS 6.837Frédo Durand and Barb CutlerMIT EECS 6.837, Cutler and Durand 2 Final projects•Rest of semester–Weekly meetings with TAs–Office hours on appointment•This week, with TAs–Refine timeline–Define high-level architecture•Project should be a whole, but subparts should be identified with regular merging of codeMIT EECS 6.837, Cutler and Durand 3 Review of last time?MIT EECS 6.837, Cutler and Durand 4 Last time•Polygon scan conversion–Smart•Take advantage of coherence•Good for big triangles–back to brute force•Incremental edge equation•Good for small triangles•Simpler clipping•Visibility–Painer: complex ordering–Z buffer: simple, memory cost•Hyperbolic z interpolationMIT EECS 6.837, Cutler and Durand 5 Z interpolation•X’=x/z•Hyperbolic variation•Z cannot be linearly interpolatedz0z1ximagex’MIT EECS 6.837, Cutler and Durand 6 Integer z-buffer•Use 1/z to have more precision in the foreground•Set a near and far plane–1/z values linearly encoded between 1/near and 1/far•Careful, test direction is reversedxfarnearMIT EECS 6.837, Cutler and Durand 7 Plan•Review of rendering pipeline•2D polygon clipping•Segment intersection•Scanlinerendering overviewMIT EECS 6.837, Cutler and Durand 8 The Graphics PipelineModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 9 Modeling TransformationsModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)Object spaceWorld spaceClippingx'y'z'1=xyz1aei0bfj0cgk0dhl1Projection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 10 Illumination (Shading) (Lighting)•Vertices lit (shaded) according to material properties, surface properties (normal) and light•Local lighting model (Diffuse, Ambient, Phong, etc.)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display2 4 )()()()(dkkkLsqsdarπωΦ⋅+⋅+=rvlnMIT EECS 6.837, Cutler and Durand 11 Viewing Transformation•Viewing position is transformed to origin & direction is oriented along some axis (usually z)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayYet another 4x4 matrixx'y'z'1=xyz1aei0bfj0cgk0dhl1 P near v u -n o far z y x o eye Seth Teller Image adapted from: World space Eye spaceMIT EECS 6.837, Cutler and Durand 12 Clipping•Portions of the object outside the view volume (view frustum) are removedModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 13 Clipping –modern hardware•Only to the near planeModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display(eyex, eyey, eyez)image planez axis"clip" geometry to near planeMIT EECS 6.837, Cutler and Durand 14 Projection•Projective transformModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /Display near eye far y z z x y x o Seth Teller Image adapted from: y y x x z o zMIT EECS 6.837, Cutler and Durand 15 Perspective Projection•2 conceptual steps:–4x4 matrix–Homogenize•In fact not always needed•Morderngraphics hardware performs most operations in 2D homogeneous coordinatesxy1z /d=xyz1100001000001/d0010x * d /zy * d /zd/z1=homogenizeMIT EECS 6.837, Cutler and Durand 16 When to clip?•Before perspective transform in 3D space–Use the equation of 6 planes–Natural, not too degenerate•In homogeneous coordinates after perspective transform (Clip space)–Before perspective divide (4D space, weird wvalues)–Canonical,independent of camera–The simplest to implement in fact•In the transformed 3D screen space after perspective division–Problem: objects in the plane of the camera M NEAR CLIP PLANE v u -n o FAR CLIP PLANE z y x o EYEMIT EECS 6.837, Cutler and Durand 17 Scan Conversion (Rasterization)•Incremental edge equations•Interpolate values as we go (color, depth, etc.)•Screen-space bboxclippingModeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayMIT EECS 6.837, Cutler and Durand 18 Visibility /Display•Each pixel remembers the closest object (depth buffer)Modeling TransformationsIllumination(Shading)Viewing Transformation(Perspective /Orthographic)ClippingProjection (to Screen Space)Scan Conversion(Rasterization)Visibility /DisplayxfarnearMIT EECS 6.837, Cutler and Durand 19 Rendering Pipeline vs. ray castingRay CastingFor each pixelFor each objectSend pixels to the sceneDiscretizefirstRendering PipelineFor each triangleFor each pixelProject scene to the pixelsDiscretizelastMIT EECS 6.837, Cutler and Durand 20 Rendering Pipeline vs. ray castingRay CastingFor each pixelFor each object•Depth complexity: no calculation for hidden part•Whole scene must be in memory•Very atomic computation•More general, more flexible–Primitive, lighting effects, adaptive antialiasingRendering PipelineFor each triangleFor each pixel•Coherence: geometric transforms for vertices only•Arithmetic intensity: the amount of computation increases in the depth of the pipeline–Good bandwidth/computation ratio•Harder to get global illumination(shadows, interreflection, etc.)MIT EECS 6.837, Cutler and Durand 21 What they use•Games:pipeline•Flight simulation:pipeline•Movies: Both pipeline and ray tracing•CAD-CAM & design: pipeline during design, anything for final image•Architecture: ray-tracing, pipeline, but do complex lighting simulation (cf. later lectures)•Virtual reality: pipeline•Visualization: mostly pipeline, ray-tracing for high-quality eye candy, interactive ray-tracing is startingMIT EECS 6.837, Cutler and Durand 22 The infamous half pixel•I refuse to teach it, but it’s an annoying issue you should know about•Do a line drawing of a rectangle from [top, right] to [bottom,left]•Do we actually draw the columns/rows of pixels?MIT EECS 6.837, Cutler and Durand 23 The infamous half pixel•Displace by half a pixel so that top, right, bottom, left are in the middle of pixels•Just change the viewporttransformMIT EECS 6.837, Cutler and Durand 24 Plan•Review of rendering pipeline•2D polygon clipping•Segment intersection•Scanlinerendering overviewMIT EECS 6.837, Cutler and Durand 25 Polygon clippingMIT EECS 6.837, Cutler and Durand 26 Polygon clippingMIT EECS 6.837, Cutler and Durand 27 Polygon clipping•Clipping is symmetricMIT EECS 6.837, Cutler and Durand 28 Polygon clipping is complex•Even when the polygons are convexMIT EECS 6.837, Cutler and Durand 29 Polygon clipping is nasty•When the polygons are concaveMIT EECS 6.837, Cutler and Durand 30 Naïve polygon clipping?•N*m intersections•Then must link all segment•Not efficient and not even easyMIT EECS 6.837, Cutler and Durand 31 Weiler-Atherton Clipping•Strategy: “Walk” polygon/window boundary•Polygons are oriented (CCW)MIT EECS 6.837, Cutler and Durand 32 Weiler-Atherton Clipping•Compute intersection pointsMIT EECS 6.837, Cutler and Durand 33 Weiler-Atherton Clipping•Compute intersection points•Mark points where polygons enters clipping window (green here)MIT EECS 6.837, Cutler and Durand 34 ClippingWhile there is still an unprocessed enteringintersectionWalk” polygon/window boundaryMIT EECS 6.837, Cutler and Durand 35 Walking rules•Out-to-in pair:–Record clipped point–Follow polygon boundary (ccw)•In-to-out pair:–Record clipped point–Follow window boundary (ccw)MIT EECS 6.837, Cutler and Durand 36 Walking rules•Out-to-in pair:–Record clipped point–Follow polygon boundary (ccw)•In-to-out pair:–Record clipped point–Follow window boundary (ccw)MIT EECS 6.837, Cutler and Durand 37 Walking rules•Out-to-in pair:–Record clipped point–Follow polygon boundary (ccw)•In-to-out pair:–Record clipped point–Follow window boundary (ccw)MIT EECS 6.837, Cutler and Durand 38 Walking rules•Out-to-in pair:–Record clipped point–Follow polygon boundary (ccw)•In-to-out pair:–Record clipped point–Follow window boundary (ccw)MIT EECS 6.837, Cutler and Durand 39 Walking rulesWhile there is still an unprocessed entering intersectionWalk” polygon/window boundaryMIT EECS 6.837, Cutler and Durand 40 Walking rulesWhile there is still an unprocessed enteringintersectionWalk” polygon/window boundaryMIT EECS 6.837, Cutler and Durand 41 Walking rulesWhile there is still an unprocessed enteringintersectionWalk” polygon/window boundaryMIT EECS 6.837, Cutler and Durand 42 Walking rulesWhile there is still an unprocessed entering intersectionWalk” polygon/window boundaryMIT EECS 6.837, Cutler and Durand 43 Weiler-Atherton Clipping•Importance of good adjacency data structure(here simply list of oriented edges)MIT EECS 6.837, Cutler and Durand 44 Robustness, precision, degeneracies•What if a vertex is on the boundary?•What happens if it is “almost” on the boundary?–Problem with floating point precision•Welcome to the real world of geometry!MIT EECS 6.837, Cutler and Durand 45 Clipping•Many other clipping algorithms:•Parametric, general windows, region-region, One-Plane-at-a-Time Clipping, etc.MIT EECS 6.837, Cutler and Durand 46 Constructive Solid Geometry (CSG)IntersectionUnionDifference•Sort of generalized clipping•Boolean operations•Very popular in CAD/CAM•CSG treeAriRappoport, Steven Spitz 97 MIT EECS 6.837, Cutler and Durand 47 Plan•Review of rendering pipeline•2D polygon clipping•Segment intersection•Scanlinerendering overviewMIT EECS 6.837, Cutler and Durand 48 Line segment intersection•N segments in the plane•Find all intersectionsMIT EECS 6.837, Cutler and Durand 49 Maximum complexity?•N2•(always N2if we take full lines)MIT EECS 6.837, Cutler and Durand 50 Intersection between 2 segments•Compute line equation for the 4 vertices•If different signs•Line intersectionA1B2A2B1MIT EECS 6.837, Cutler and Durand 51 Naïve algorithm•N2intersection:For (I=0; IremoveSegmentsBefore(L.xmin)For all segments Li in Active segmentsCompute Intersection between L and LiActiveSegments->insert(L)MIT EECS 6.837, Cutler and Durand 54 Taking advantage of coherence 1Sort segments by xmininto queue QList ActiveSegments=emptyWhile Q not emptyL= Q.next() //pick next segmentActiveSegment->removeSegmentsBefore(L.xmin) //easier if sortedFor all segments Li in Active segmentsCompute Intersection between L and LiActiveSegments->insert(L) //keep sorted by xmaxMIT EECS 6.837, Cutler and Durand 55 What have we achieved?•Take advantage of locality and coherence•Maintain working set•Still O(n2)•But much better on average•Can we do better?MIT EECS 6.837, Cutler and Durand 56 Can we do better?•We have taken advantage of the coherence in x•We have maintained a local view of the world at discrete events in x•Do the same in y as wellMIT EECS 6.837, Cutler and Durand 57 Maintain segments sorted in y•Events–New segment–End of segment –Change of y sortingMIT EECS 6.837, Cutler and Durand 58 New segment•Just insert at y1•Use balanced binary treesMIT EECS 6.837, Cutler and Durand 59 End of segment•Just remove•Potentially re-balance the treeMIT EECS 6.837, Cutler and Durand 60 Intersection•Where can intersection occur?•Intersection must be between segments adjacentsin y•Fort each pair of adjacent segments, always maintain next intersectionMIT EECS 6.837, Cutler and Durand 61 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionsMIT EECS 6.837, Cutler and Durand 62 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionsMIT EECS 6.837, Cutler and Durand 63 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionsMIT EECS 6.837, Cutler and Durand 64 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionssliceMIT EECS 6.837, Cutler and Durand 65 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionssliceMIT EECS 6.837, Cutler and Durand 66 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionssliceMIT EECS 6.837, Cutler and Durand 67 Sweep algorithm•Maintain event queue–New segment for each x1 •Insert in binary tree •Compute potential new intersection•Add ending event–End of segment •simply remove•compute new intersections–Change of y sorting •report intersection•swap two segments •compute new intersectionssliceMIT EECS 6.837, Cutler and Durand 68 Output sensitive•The running time depends on the output•Hopefully linear in the output + smaller complexity in the input•In our case time O(n log n + k log n )–Where k is the number of intersections•Space: O(n)•The optimal bound is time O(n log n +k)MIT EECS 6.837, Cutler and Durand 69 Other strategy?•Grid!MIT EECS 6.837, Cutler and Durand 70 Ref•De Berg, M. M. van Kreveld, M. Overmars. O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Ed. 2. Springer•O’Rourke, Joseph. Computational Geometry in C. Ed. 2.MIT EECS 6.837, Cutler and Durand 71 Questions?•Rendering this line drawing involved the intersection of all stroke segmentsMIT EECS 6.837, Cutler and Durand 72 Plan•Review of rendering pipeline•2D polygon clipping•Segment intersection•Scanlinerendering overviewMIT EECS 6.837, Cutler and Durand 73 Scan Line rasterization•Draw one scanlineat a time•Maintain ordered slices of triangles•Advantage, does not require whole model and whole image in memoryyMIT EECS 6.837, Cutler and Durand 74 Scan Line : Principle•Proceed row by row•Maintain Active Edge List (AEL) (EdgeRecList)•Edge Table (ET) for new edges at y(EdgeRecTable)yPrecompute: Edge Table MIT EECS 6.837, Cutler and Durand 75 –One entry per scan line (where edge begins)–Each entry is a linked list of Edges, sortedbyxyend: y of top edge endpoint xcurr, x: current x intersection, delta wrty Next or null pointerEdge tableInitialization: events MIT EECS 6.837, Cutler and Durand 76 •Edge Table–List of Edges,sorted by x yendxcurr, delta wrty•Active edge list(AEL)–Will be maintained–Store all active edges intersecting scanline–Ordered by xEdge tableMIT EECS 6.837, Cutler and Durand 77 When Does AEL Change State?•When a vertex is encountered–When an edge begins •All such events pre-stored in Edge Table–When and edge ends•Can be deduced from current Active Edge ListMIT EECS 6.837, Cutler and Durand 78 When Does AEL Change State?•When a vertex is encountered•When two edges change order along a scanline–I.e., when edges cross each other!–How to detect this efficiently?Scanlinealgorithm summary MIT EECS 6.837, Cutler and Durand 79 •Initialize Raster, Polygons, Edge Table, AEL•For each scanliney–Update Active Edge List (insert edges from EdgeTable[y])–Assign raster of pixels from AEL–Update AEL (delete, increment, resort)yMIT EECS 6.837, Cutler and Durand 80 Other sweep algorithms•Sweep is a very general principle:–Maintain a slice–Update at events–Works well if events are predictable locally in the slice (regular)•Applied to many problems–E.g. construction of weird visibility data structures in 4.5D