Continuous collision detection improves the computation of the contact information for interacting objects in dynamic virtual environments. The computation cost is relatively high in the phase of the elementary test processing. In virtual environments, such as crowds in large urban models, there is a large portion of feature pairs that do not collide but the computation is relatively of high cost. In this paper, we propose a robust approach for solving the scalability of the collision detection problem by applying four distinct phases. First, k-DOPs are used for culling non-proximal triangles. Second, the feature assignment scheme is used for minimizing the number of potentially colliding feature pairs. Third, an intrinsic filter is employed for filtering non-coplanar feature pairs. Forth, we use a direct method for computing the contact time that is more efficient than the numerical Interval Newton method. We have implemented our system and have compared its performance with the most recently developed approaches. Six benchmarks were evaluated and the complexity of the models was up to 1.5M triangles. The experimental results show that our method improves the performance for the elementary tests.

Abstract Collision events between 3D objects in motion in computer animations or simulations are difficult to detect due to the difficulty of accurately sampling the motion paths of objects in space and time. One approach to this problem has been continuous collision detection but because the current approaches process potentially interacting primitive pairs (PIPPs) redundantly. This is time‐expensive, especially where there are a large number of PIPPs. In this paper we propose a novel collision detection process that more accurately and robustly detects collisions on simulated meshed deformable surfaces. We embed a new layer, primitive filtering layer (PFL), to extract PIPPs. This has two results. It reduces the number of PIPPs significantly and it means that each interacting primitive pair is processed just one time. Experimental results show that this approach achieves interactive rates for complex deformable surfaces with large contact regions. This is especially practical for cloth dynamics. Our method is efficient, accurate, reliable, and robust even in the presence of objects with sharp features. We also present techniques to implement the method on programmable graphics processing units (GPUs). Copyright © 2007 John Wiley & Sons, Ltd.

Abstract An intrinsic collision detection unit (ICDU) forms the bottom‐most layer of a collision detection pipeline. The ICDU performs collision detection and computes collision information for primitive feature pairs of objects in a 3D dynamic environment. A significant amount of time can be spent by the ICDU during the collision detection process. In this paper, we extend the ICDU framework to take advantages of the computational power of programmable graphics processors (GPUs). Some components of the ICDU framework consist of time demanding and fine‐grained tasks that can be implemented on GPUs. By employing the framework, collision information can be computed accurately, robustly, and efficiently. Experimental results show that the proposed method greatly improves the performance of the ICDU. A collection buffer is proposed for the future enhancement of GPU‐based collision detectors. Copyright © 2005 John Wiley & Sons, Ltd.

In this paper, we introduce new techniques that enhance the computational performance for the interactions between sharp objects and deformable surfaces. The new formulation is based on a time-domain predictor-corrector model. For this purpose, we define a new kind of (pi, beta, I)-surface. The partitioning of a deformable surface into a finite set of (pi, beta, I)-surfaces allows us to prune a large number of noncolliding feature pairs. This leads to a significant performance improvement in the collision detection process. The intrinsic collision detection is performed in the time domain. Although it is more expensive compared to the static interference test, it avoids portions of the surfaces passing through each other in a single time step. In order to resolve all the possible collision events at a given time, a penetration-free motion space is constructed for each colliding particle. By keeping the velocity of each particle inside the motion space, we guarantee that the current colliding feature pairs will not penetrate each other in the subsequent motion. A static analysis approach is adopted to handle friction by considering the forces acting on the particles and their velocities. In our formulation, we further reduce the computational complexity by eliminating the need to compute repulsive forces.

We propose a positional constraint method to solve the multi-layered deformable surface problem based on a master-slave scheme. This allows two or more deformable surfaces to be attached together in any orientation relative to each other for the purpose of modeling cloth attachments and multi-layered clothing. The method does not require the mesh resolution of the deformable surfaces to be the same or the matching of anchor points between layers. After the attachment process, the surfaces are treated as a multi-layered surface. However, this surface contains non-manifold features. We introduce a technique for preventing self-intersection of the non-manifold features. We demonstrate the stability of this method by performing several experiments with high surface complexity and a large number of colliding feature pairs. Interactive rates can easily be achieved for multilayered surfaces with an appropriate discretization level of triangles.

Modeling the natural interaction of cloth and garments with objects in a 3D environment is currently one of the most computationally demanding tasks. These highly deformable materials are subject to a very large number of contact points in the proximity of other moving objects. Furthermore, cloth objects often fold, roll, and drape within themselves, generating a large number of self-collision areas. The interactive requirements of 3D games and physically driven virtual environments make the cloth collisions and self-collision computations more challenging. By exploiting mathematically well-defined smoothness conditions over smaller patches of deformable surfaces and resorting to image-based collision detection tests, we developed an efficient collision detection method that achieves interactive rates while tracking self-interactions in highly deformable surfaces consisting of a large number of elements. The method makes use of a novel technique for dynamically generating a hierarchy of cloth bounding boxes in order to perform object-level culling and image-based intersection tests using conventional graphics hardware support. An efficient backward voxel-based AABB hierarchy method is proposed to handle deformable surfaces which are highly compressed.

Most collision detection methods developed so far are based on geometrical object-space interference tests. While this remains the basic mode of investigation for geometric algorithms, the requirements for interactive rates and complex geometry predominate in commercial applications. In this article, we propose a new mode of collision detection based on an image-space approach. This approach breaks the object-space collision detection bottleneck by distributing the computational load onto the hardware graphics pipeline. The image-space approach, in conjunction with efficient bounding-box strategies in the object-space, has the potential to handle complex object interactions at interactive rates.

The natural behavior of garments and textile materials in the presence of changing object states is potentially the most computationally demanding task in a dynamic 3D virtual environment. Cloth materials are highly deformable inducing a very large number of contact points or regions with other objects. In a natural environment, cloth objects often interact with themselves generating a large number of self-collisions areas. The interactive requirements of 3D games and physically driven virtual environments make the cloth collisions and self-collisions computations more challenging. By exploiting mathematically well-defined smoothness conditions over smaller patches of deformable surfaces and resorting to image-based collision detection tests, we developed an efficient collision detection method that achieves interactive rates while tracking self-interactions in highly deformable surfaces consisting of more that 50,000 elements. The method makes use of a novel technique for dynamically generating a hierarchy of cloth bounding boxes in order to perform object-level culling and image-based intersection tests using conventional graphics hardware support.

In interactive virtual environments and dynamic simulations, collisions between complex objects and articulated bodies may occur simultaneously at multiple points or regions of interference. Many solutions to the collision response problem are formulated based on the local pair‐wise contact dynamics. In this article, we present a new solution to the global interactions and dynamic response between multiple structures in a three‐dimensional environment. This is based on a new dynamic impulse graph that tracks the reaction forces through the entire system and gives a global view of all the interactions in a multibody system.

Object interactions are ubiquitous in interactive computer graphics, 3D object motion simulations, virtual reality and robotics applications. Most collision detection algorithms are based on geometrical object-space interference tests. Some algorithms have employed an image-space approach to the collision detection problem. In this paper we demonstrate an image-space collision detection process that allows substantial computational savings during the image-space interference test. This approach makes efficient use of the graphics rendering hardware for real-time complex object interactions. Copyright © 1999 John Wiley & Sons, Ltd.

Object interactions are ubiquitous in interactive computer graphics, 3D object motion simulations, virtual reality and robotics applications. Most collision detection algorithms are based on geometrical object space interference tests. Some algorithms have employed an image space approach to the collision detection problem. We demonstrate an image space collision detection process that allows substantial computational savings during the image space interference test. This approach makes efficient use of the graphics rendering hardware for real time complex object interactions.

Article Free Access Share on Hardware-assisted virtual collisions Authors: George Baciu Computer Science Department, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong Computer Science Department, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong KongView Profile , Wingo Sai-Keung Wong View Profile , Hanqiu Sun View Profile Authors Info & Claims VRST '98: Proceedings of the ACM symposium on Virtual reality software and technologyNovember 1998 Pages 145–151https://doi.org/10.1145/293701.293720Published:02 November 1998Publication History 3citation300DownloadsMetricsTotal Citations3Total Downloads300Last 12 Months25Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Collision detection between complex objects using rasterizing graphics hardware provides a rich ground of exploration for speeding up the interference detection algorithms and computing points of collision. We show that despite the limitations imposed by the current graphics rendering hardware, it is still possible to perform collision detection at rendering rates using only conventional graphics hardware without any enhancements.