Arrangements and Duality Supersampling in Ray Tracing Khurram Hassan Shafique Duality The concept we can map between different ways of interpreting 2D values Points x y can be mapped in a one to one manner to lines slope intercept in a different space There are different ways to do this called duality transforms Duality Transforms A duality transform is a mapping which takes an element e in the primal plane to element e in the dual plane One possible duality transform point p px py line p y px x py line l y mx b point l m b Duality Transforms This duality transform takes points to lines lines to points line segments to double wedges This duality transform preserves order Point p lies above line l point l lies above line p p l l p Duality The dualized version of a problem is no easier or harder to compute than the original problem But the dualized version may be easier to think about New Concept Arrangements of Lines L is a set of n lines in the plane L induces a subdivision of the plane that consists of vertices edges and faces This is called the arrangement induced by L denoted A L The complexity of an arrangement is the total number of vertices edges and faces Arrangments Number of vertices of A L n 2 Vertices of A L are intersections of li lj L Number of edges of A L n2 Number of edges on a single line in A L is one more than number of vertices on that line n2 n 1 2 2 Number of faces of A L Inductive reasoning add lines one by one n Each edge of new line splits a face 1 i i 1 Total complexity of an arrangement is O n2 How Do We Store an Arrangement Data Type doubly connected edge list DCEL Vertex Coordinates Incident Edge Face an Edge Half Edges Origin Vertex Twin Edge Incident Face Next Edge Prev Edge Building the Arrangement Iterative algorithm put one line in at a time Start with the first edge e that li intersects Split that edge and move to Twin e ConstructArrangement Algorithm Input A set L of n lines in the plane Output DCEL for the subdivision induced by the part of A L inside a bounding box 1 Compute a bounding box B L that contains all vertices of A L in its interior 2 Construct the DCEL for the subdivision induced by B L 3 for i 1 to n do 4 Find the edge e on B L that contains the leftmost intersection point of li and Ai 5 6 7 f the bounded face incident to e while f is not the face outside B L do Split f and set f to be the next intersected face ConstructArrangement Algorithm Running Time We need to insert n lines Each line splits O n edges We may need to traverse O n Next e pointers to find the next edge to split Zones The zone of a line l in an arrangement A L is the set of faces of A L whose closure intersects l l Note how this relates to the complexity of inserting a line into a DCEL Zone Complexity The complexity of a zone is defined as the total complexity of all the faces it consists of i e the sum of the number of edges and vertices of those faces The time it takes to insert line li into a DCEL is linear in the complexity of the zone of li in A l1 li 1 Zone Theorem The complexity of the zone of a line in an arrangement of m lines on the plane is O m We can insert a line into an arrangement in linear time We can build an arrangement in O n2 time Proof of Zone Theorem Given an arrangement of m lines A L and a line l Change coordinate system so l is the x axis Assume for now no horizontal lines l Proof of Zone Theorem Each edge in the zone of l is a left bounding edge and a right bounding edge Claim number of left bounding edges 5m Same for number of right bounding edges Total complexity of zone l is linear Proof of Zone Theorem Base Case When m 1 this is trivially true 1 left bounding edge 5 Proof of Zone Theorem Inductive Case Assume true for all but the rightmost line lr i e Zone of l in A L lr has at most 5 m 1 left bounding edges Assuming no other line intersects l at the same point as lr add lr Proof of Zone Theorem Inductive Case Assume true for all but the rightmost line lr i e Zone of l in A L lr has at most 5 m 1 left bounding edges Assuming no other line intersects l at the same point as lr add lr Proof of Zone Theorem Inductive Case Assume true for all but the rightmost line lr i e Zone of l in A L lr has at most 5 m 1 left bounding edges Assuming no other line intersects l at the same point as lr add lr lr has one left bounding edge with l 1 1 Proof of Zone Theorem Inductive Case Assume true for all but the rightmost line lr i e Zone of l in A L lr has at most 5 m 1 left bounding edges Assuming no other line intersects l at the same point as lr add lr lr has one left bounding edge with l 1 lr splits at most two left bounding edges 2 1 1 1 Proof of Zone Theorem Relaxed Assumptions What if lr intersects l at the same point as another line li does lr has two left bounding edges 2 li is split into two left bounding edges 1 As in simpler case lr splits two other left bounding edges 2 1 1 2 1 Proof of Zone Theorem Relaxed Assumptions What if lr intersects l at the same point as another line li does 5 What if 2 lines li lj intersect l at the same point Like above but li lj are already split in two 4 1 2 1 Proof of Zone Theorem Relaxed Assumptions What if there are horizontal lines in L A horizontal line introduces less complexity into A L than a non horizontal line Done proving the Zone Theorem Ray Tracing Ray Tracing Render a scene by shooting a ray from the viewer through each pixel in the scene and determining what object it hits Straight lines will have visible jaggies We need to supersample Supersampling We shoot many rays through each pixel and average the results How should we distribute the rays over the pixel Regularly Distributing rays regularly isn t such a good idea Small per pixel error but regularity in error across rows and columns Human vision is sensitive to this Sample Point Set Rendered Half Plane 4x zoom Wow that really makes a difference Supersampling We need to choose our …