Sponsor: NIST
Systems that simulate virtual environments (such as our Project Newton or the new project Isaac [4]) or deal with physical objects depend on geometric support capable of at least representing the static environment and the moving objects, and operations providing the n-body collision detection and a two-body contact analysis of objects in close proximity[3].
Addressing these requirements, we have developed the multi-dimensional space partitioning tree and the Brep-Index data structures, and the back-face culling algorithm[2]. Their combined use was shown to greatly improve the computational efficiency of classifying geometric entities with respect to polyhedral objects, and to support high-level operations such as collision detection of objects in close proximity and contact analysis of moving objects. The multidimensional space partition (MSP) tree data structure is an extension of the classical binary space partition tree. By itself, the MSP tree is a sufficient representation for polyhedral objects. However, when the MSP tree is combined with the boundary representation of the particular object, it becomes a convenient spatial index into the boundary representation. We call such a unified representation the Brep-index[1]. Its use has been demonstrated to reduce the typically linear-time classification problems to sublinear time, and to do so in a robust way. Consequently, we built an efficient and robust collision detection and analysis support package for the Newton simulation system.
The Brep-index and the back-face culling, along with the supported operations, are packaged into a system called Proxima[1]. It is written in C++ and it is provided as a library for other applications to use. In Proxima, objects are invariant and are given externally; so any existing solid modeling systems, such as ACIS can be used to create the needed objects.
Currently the project is proceeding in the development of additional geometric operations based on a multi-resolution Brep-index and back-face culling. Such a system could support a broad range of applications such as physical based simulations, ray tracing, robot navigation systems, and other systems that require detailed geometric information about positions of the objects.