An Efficient Space Partitioning Method Using Binary Maps

摘要

Space partitioning techniques are well known especially because of their use in computer graphics, especially within ray-tracing acceleration techniques. The primary aim of those techniques is to enable fast test whether a geometric object resides at least partially within the given area. There are many modifications that proved the applicability despite of high memory requirements of complexity O(M~2) for the two dimensional space, resp. O(M~3) for the three dimensional space. The space division technique is used in standard software packages like PovRay etc. A new technique with O(M) memory complexity and its comparison with original space subdivision and residency mask techniques is presented.