Lecture 12: BSP October 14, 2003The Visibility ProblemandBinary Space Partition(slides by Nati Srebro)Lecture 12: BSP October 14, 2003The Visibility ProblemabcdeLecture 12: BSP October 14, 2003Z-buffering• Draw objects in arbitrary order• For each pixel, maintain depth (“z”)• Only draw pixel if new “z” is closerInstead:draw objects in order, from back to front(“painter’s algorithm”)Lecture 12: BSP October 14, 2003Binary Planar Partitionsabcde01230123a b cd eabcdedeLecture 12: BSP October 14, 2003Painter’s Algorithmabcde01230123a b cd eLecture 12: BSP October 14, 2003Binary Planar Partitionsabcb1b2Lecture 12: BSP October 14, 2003Auto-partitionsabcb1b2ab1cb2b2,cLecture 12: BSP October 14, 2003Auto-partitionsacb1b2ab1b2c1c1c2c2b2,cLecture 12: BSP October 14, 2003Auto-partitions1+2+3++n = n(n+1)/2 = O(n2)Lecture 12: BSP October 14, 2003Binary Planar PartitionsGoal:Find binary planer partition,with small number of fragmentationsLecture 12: BSP October 14, 2003Random 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 regionLecture 12: BSP October 14, 2003Random Auto-Partitionsu can cut v4only if u appears before v1,v2,v3,v4in random permutationP(u cuts v4) uv1v2v3v4Lecture 12: BSP October 14, 2003Random Auto-Partitionsuv1v2v3v4t1t3t2E[number of cuts u makes]= E[num cuts on right] + E[num cuts on left]= E[Cv1+Cv2+] + E[Ct1+Ct2+]Cv1]+ Cv2]+ + Ct1]+ Ct2]++1/n + +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)Cv1=1 if u cuts v1,0 otherwiseLecture 12: BSP October 14, 2003Random 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 expectationLecture 12: BSP October 14, 2003Free cutsUse internal fragments immediately as “free” cutsLecture 12: BSP October 14, 2003Binary Space Partitions• Without free cuts: O(n3)• With free cuts:
View Full Document
Unlocking...