Description: |
The BOXEL framework for 2.5D data with applications to virtual drivethroughs and ray tracing
The framework of boxels is developed to represent 2.5D datasets, such as urban environments. Boxels are axis-aligned non-intersecting boxes which can be used to directly represent objects in the scene or as bounding volumes. L. J. Guibas and F. F. Yao [in: Miller, Raymond E. (ed.), Conference proceedings of the twelfth annual ACM symposium on theory of computing, held at Los Angeles, California, April 28-30, 1980. Sponsored by the Association for Computing Machinery, Special Interest Group on Automata and Computability Theory, with the Cooperation of the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing and Computer Science Department, University of Southern California, Los Angeles, California. New York: The Association for Computing Machinery, 154–160 (1980; Zbl 0476.68003), also in: Advances in computing research 1, 61–77 (1983)] have shown that axis-aligned disjoint rectangles in the plane can be ordered into four total orders so that any ray meets them in one of the four orders. This is also applicable to boxels, and it is shown that there exist four different partitionings of the boxels into ordered sequences of disjoint sets, called antichains, so that boxels in one antichain can act as occluders of the boxels in subsequent antichains. The expected runtime for the antichain partitioning is \(O(nlog n)\), where \(n\) is the number of boxels. This partitioning can be used for the efficient implementation of virtual drivethroughs and ray tracing. Boxels can also be easily organized into hierarchies to speed up the rendering. For drivethroughs, the antichains are processed in front-to-back order together with a run-length encoding of the boxel horizon, yielding real-time rendering of scenes with up to 300,000 buildings. For ray tracing, a ray intersects at most one boxel in an antichain, and the time to determine that boxel is O(1) for most “natural” scenes, and at worst, logarithmic in the size of the antichain. Objects which are not axis-aligned can also be handled by a simple modification. Boxel rendering can also be parallelized for multi-core machines. |