An efficient space partitioning method using binary maps
Václav Skala · Digital Library (University of West Bohemia) · 2012
Abstract:- 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. Key-Words:- Computer graphics, algorithm acceleration, algorithm complexity, space partitioning, space subdivision, residency mask. Notifications: p – number of objects, M- number of subdivision in one axis (Mx = Mx = Mx for simplicity) 1