Collision Detection
Collisions with Force Feedback in Maintainability Studies over Complex and Compact Mock-ups
ABSTRACT
Virtual reality provides an environment free of the high costs normally associated with physical mock-ups. As such, accurate and efficient collision detection is required in order to simulate maintainability tasks. Even more significant is the complexity and enormous size of the CAD input models (millions of triangles); so the visualization modules and the collision solver have to implement sophisticated techniques to obtain a real-time frame-rate.
CONTENT
To sum up, our collision problem has two specific characteristics. The first one concerns the number of scene objects. There is a reduced number of mobile objects (the tool or some engine part), while the rest of the scene is a large set of static objects. Therefore, the mobile objects represent only about 0.5% of the total number of facets in the scene. The second concerns the relative position between the static and mobile geometry: the facets of the mobile object are usually close to a subset of static facets. The compact nature of the virtual model and its high number of polygons, forces us to use spatial sorting techniques. We have chosen techniques based on voxels, but we have also tested hierarchical methods like octrees. Although these required less memory storage, the computation time was higher than that needed for direct access voxel techniques. However, algorithms based on voxel techniques have several disadvantages, such as those related to memory storage requirements and the choice of voxel size. Hashing techniques can solve the first problem reducing even a 60% the memory storage without perfomance penalty. The choice of an optimal voxel size can be solved by means of a new analytical method based on the algorithm cost function. This function describes the behaviour and complexity of the collision algorithm. In our case, the final cost function z that describes the algorithm behaviour might reasonably be expected to be:
z = pnc vo + (1-pnc) vo fs rt
where pnc is the probability (estimated average) of no collision between one mobile triangle and one not empty static voxel, vo is the mean number of voxels covered by the AABB of a triangle, fs is the number of static object facets per voxel and rt is the ratio between voxel and facets intersection times. These parameters are function of the voxel size l and scene geometric parameters so, the optimal size will be the minimum of the z function, i.e., dz / dl = 0.
These solutions should therefore make the use of spatial partition techniques more attractive. Next experiments were done in worst case conditions. Actually, the collision detection performance in normal conditions is between 1-5 ms.
PAPERS
Books:
Borro, D., Colisiones en Estudios de Mantenibilidad con Restitución de Esfuerzos sobre Maquetas Digitales Masivas y Compactas (ISBN 84-8081-143-9), PhD Thesis Dissertation in July 2003. Ed. Universidad de Navarra (February 2011). (http://dspace.unav.es/dspace/handle/10171/16712).
Journals:
Borro, D., García-Alonso, A., and Matey, L., "Approximation of Optimal Voxel Size for Collision Detection in Maintainability Simulations within Massive Virtual Environments", Computer Graphics Forum, Vol. 23, No. 1, pp. 13-23. January/March 2004. (pdf).
Conferences:
Borro, D., Hernantes, J., Mansa, I., Amundarain, A., García-Alonso, A., and Matey, L., "Virtual Maintenance System for Dense Environments", Proceedings of the Laval Virtual, 7th International Conference on Virtual Reality 2005 (VRIC 2005), pp. 141-148. Laval, France. April 20-24, 2005. (pdf).
Borro, D., Hernantes, J., García-Alonso, A., Matey, L., “Collision problem: Characteristics for a Taxonomy”, Proceedings of the 9th International Conference Information Visualisation (IV’05), pp. 410-415. London, England. July 6-8, 2005. (pdf).
Hernantes, J., Borro, D., Matey, L., and García-Alonso, A., “Analysis of Collision Detection in Dense Geometry Sets”, Proceedings of the 10th International Fall Workshop Vision, Modeling, and Visualization (VMV 2005), pp. 99-106. Erlangen, Germany. November 16-18, 2005. (pdf).
VIDEOS
Video 01: Static model of ~150K triangles and mobile of ~2K (Youtube link)
Video 02: Static model of ~1.5M triangles and mobile of ~2K (Youtube link)
RELATED PROJECTS
Haptics research
Collisions between deformable objects
ABSTRACT
Spatial Partitioning Algorithms have been broadly used in Computer Graphics and simulations. In particular, voxels based methods are simple and quick, but finding the optimum voxel size is not trivial. We propose a methodology to easily determine the optimal voxel size for Collision Detection Algorithms. Using an algorithm which represents volumetric objects with tetrahedra as an example, a performance cost function is defined in order to analytically bound the voxel size that gives the best computation times. This is made by inferring and estimating all the parameters involved in the cost function by only using geometry data. By doing so, it is possible to determine the optimal voxelization for any algorithm and scenario.
CONTENT
We propose a methodology (a sequence of steps) to calculate the optimal voxel size for algorithms based on Uniform Spatial Partitioning. The main contribution of this work is a sequence of steps to infer an analytical method that automatically determines the optimal voxel size based only on the geometry of the scene. This will conclude in an easy and rapid method for improving algorithm time-rates. Our previous work (described above) validated the method with objects represented by triangle meshes. This proposal extends that work to other types of object representations (tetrahedral meshes) and defines a general methodology for any kind of collision detection algorithm based on voxels. Furthermore, the work extends the experimental results obtained for 3D models varying geometry and complexity. They have been used to validate the methodology and compare our results with others proposed in the bibliography (all the experiments of the Virtual Reality Journal are described here).
PAPERS
Journals:
Echegaray, G., and Borro, D., “A Methodology for Optimal Voxel Size Computation in Collision Detection Algorithms”, Virtual Reality, Vol. 16, No. 3, pp. 205-213. September 2012. (pdf).
VIDEOS
RELATED PROJECTS