March 8, 2005The Visibility ProblemandBinary Space Partition(slides by Nati Srebro)March 8, 2005The Visibility ProblemabcdeMarch 8, 2005Algorithms• Z-buffer:– Draw objects in arbitrary order– For each pixel, maintain distance to the eye (“z”)– Only draw pixel if new “z” is closer• Painter’s algorithm: – draw objects in order, from back to frontMarch 8, 2005Painter’s algorithm• Can one always order objects from front to back ? That is, is “A occludes B” a partial order ?Assuming:– Simple objects, e.g., segments or triangles– Objects disjoint • In 2D: Yes• In 3D: No• We will have to split sometimesMarch 8, 2005Binary Planar Partitionsabcde01230123a b cd eabcdedeMarch 8, 2005Painter’s Algorithmabcde01230123a b cd eMarch 8, 2005Binary Planar Partitionsabcb1b2March 8, 2005Auto-partitionsabcb1b2ab1cb2b2,cMarch 8, 2005Auto-partitionsacb1b2ab1b2c1c1c2c2b2,cMarch 8, 2005What is the complexity of BSP using auto-partitions ?1+2+3+···+n = n(n+1)/2 = O(n2)March 8, 2005Binary Planar PartitionsGoal:Find binary planer partition,with small number of fragmentationsMarch 8, 2005Random Auto-PartitionsChoose random permutation of segments(s1, s2, s3,…, sn)While there is a region containing more than one segment,separate it using first siin the regionMarch 8, 2005Analysisu can cut v4only if u appears before v1,v2,v3,v4in random permutationP(u cuts v4) ≤1/5uv1v2v3v4March 8, 2005Cv1=1 if u cuts v1,0 otherwiseRandom Auto-Partitionsuv1v2v3v4t1t3t2E[number of cuts u makes]= E[num cuts on right] + E[num cuts on left]= E[Cv1+Cv2+···] + E[Ct1+Ct2+···]= E[Cv1]+ E[Cv2]+··· + E[Ct1]+ E[Ct2]+···≤ 1/2+1/3+1/4+···+1/n + 1/2+1/3+1/4+···+1/n= O(log n)E[total number of fragments] = n + E[total number of cuts]= n + ΣuE[num cuts u makes] = n+nO(log n) = O(n log n)March 8, 2005Random Auto-PartitionsChoose random permutation of segments(s1, s2, s3,…, sn)While there is a region containing more than one segment,separate it using first siin the regionO(n log n) fragments in expectationMarch 8, 2005What about 3D ?• Assume arbitrary order of triangles• What is the complexity of the BSP ?– Each triangle can be split using n-1 planes– From the perspective of the triangle, it is split using n-1 lines– Complexity of arrangement: O(n2)– Total complexity: O(n3)• Also, at least Ω(n2)March 8, 2005•The zone of a line l in an arrangement A(L) is the set of faces of A(L) whose closure intersects l.• Note how this relates to the complexity of inserting a line into a DCEL…ZoneslMarch 8, 2005Zone 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 liinto a DCEL is linear in the complexity of the zone of liin A({l1,…,li-1}).March 8, 2005Zone Theorem• The complexity of the zone of a line in an arrangement of m lines on the plane is O(m)• Therefore:– We can insert a line into an arrangement in linear time– We can compute the arrangement in O(n2)timeMarch 8, 2005Proof 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 lineslMarch 8, 2005Proof 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 linearMarch 8, 2005Proof of Zone Theorem-Base Case-• When m=1, this is trivially true.(1 left bounding edge ≤ 5)March 8, 2005Proof 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 lrMarch 8, 2005Proof 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 lrMarch 8, 2005Proof 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– lrhas one left boundingedge with l (+1)+1March 8, 2005Proof 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– lrhas one left boundingedge with l (+1)– lrsplits at most two leftbounding edges (+2)+1+1+1March 8, 2005Proof of Zone TheoremLoosening Assumptions•What if lrintersects l at the same point as another line, lidoes? – lrhas two left bounding edges (+2)– liis split into two left bounding edges (+1)– As in simpler case,lrsplits two other leftbounding edges (+2)+2+1+1+1March 8, 2005Proof of Zone TheoremLoosening Assumptions• What if lrintersects l at the same point as another line, lidoes? (+5)• What if >2 lines (li, lj, …) intersect l at the same point?– Like above, but li, lj, …are already split in two(+4)+2+1+1March 8, 2005Proof of Zone Theorem-Loosening Assumptions-• What if there are horizontal lines in L?• A horizontal line introduces not more complexity into A(L) than a non-horizontal line.March 8, 2005Free cutsUse internal fragments immediately as “free”