HOW EFFICIENT IS A BSP TREE?
Space complexity For the problem of hidden surface removal, consider a set of n parallel polygons, and the set of m partitioning planes, all of which are perpendicular to the polgyons. This has the effect of splitting every polygon with every partition. The number of polygons resulting from this partitioning scheme is n + (n * m). If the partitioning planes are selected from the candidate polygon set (an autopartition), then m = n, and the expression reduces to n^2 + n. Thus the worst case spatial complexity of a BSP tree constructed using an autopartition is O(n^2). It will be extremely difficult to construct a case which satisfies this formula. The “expected” case, repeatedly expressed by Naylor, is O(n). Time complexity The time complexity of rendering from a BSP built using an autopartition is the same as the spatial complexity, that is a worst case of O(n^2), and an “expected” case of O(n). — Last Update: 09/06/101 14:50:28 • HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT? Bounding v
