|
Collision Detection
Fast Collision Detection for 3D Bones-Based Articulated Characters
Abstract: This article aims to give a practical, efficient implementation for collision detection with a bones-based character. Our implementation offers several advantages over techniques common in today's engines and leverages current infrastructure that is already needed for character animation.
Opposing Face Geometry: A Collision Detection Optimization Scheme
Abstract: OFG presents a new method for collision detection optimizations by performing a simple pre-calculation on both input objects. It is possible to reduce the number of faces necessary to check for intersection dramatically, from an order of O(mn) intersection tests to an order of O(k^2), or rather to a maximum of k^2 + 3k test operations, where k is a predetermined constant. The pre-calculation phase is of the order of O(m + n). Therefore, for increasingly complex convex objects, the OFG method saves more and more processing time. The method's downside is that increasingly complex objects might need a very high constant and small faces are less suited for this type of optimization. The method is much better for relatively low detail 3D objects.
Collision Detection of Deformable Volumetric Meshes
Abstract:
An Effective Implementation of the k-D Trees |  |
Abstract:
Pool Hall Lessons: Fast, Accurate Collision Detection between Circles or Spheres
Abstract: This article explains how to detect collisions between two spheres and determine what they'll do after they collide. This is useful not only for games like pool where accurate collision of spheres is key, but also in games where characters and other mobile objects are bounded by spheres, these can be used to quickly determine if they have bumped into each other.
Sphere Trees for Fast Visibility Culling, Ray Tracing, and Range Searching | |
Abstract: The article presents an algorithm and demonstration application that manages thousands of objects in motion that are continuously maintained as a collection of hierarchical bounding spheres in a SphereTree. The design goal for this algorithm has been to make the 99-percentile case spend almost no CPU time updating an object in motion within the tree structure. Queries against the SphereTree perform more tests than other data structures, but this is mitigated by the fact that the tree can be maintained using very little CPU time. This data structure is ideally suited for gross culling of massive numbers of moving objects in a large world space. It doesn't matter if the objects are moving at widely disparate speeds, or even if many of them are not in motion at all. It also has a very low cost when objects are inserted and removed from the tree with great frequency.
Compressed Axis-Aligned Bounding Box Trees
Abstract: The axis-aligned bounding box (AABB) tree structure has proven to be very useful for accelerating intersection queries on sets of geometry. The data structure is easy to implement, the built structure is numerically well conditioned, and like all binary trees, they have O(log n) search time. This article explains several techniques that can be used to lower the overall memory footprint of an AABB tree to 11 bytes per triangle.
Direct Access Quadtree Lookup
Abstract: This article presents a general-purpose optimization for quadtree access that improves performance in three ways over the traditional implementations: 1) by eliminating node traversal and the unnecessary cache-misses it causes, 2) by requiring fewer instructions and CPU cycles overall vs. a best case traditional approach, and 3) by doing so in a compact amount of time and with minimal memory accesses regardless of what depth in the tree the target node resides in.
3D Collision Detection | |
Abstract: This article will help lay the groundwork for building an accurate physics simulation by starting with one of the most crucial parts of a real-time physics engine: 3D collision detection. The two basic algorithms this article covers are: Bounding Sphere Collision Detection and Triangle-to-Triangle Collision Detection.
Multi-Resolution Maps for Interaction Detection (Collision Detection) | |
Abstract: This article describes a method for reducing the number of proximity tests that must be performed for games with large numbers of game objects of varying sizes.
Octree Construction | |
Abstract:
Loose Octrees | |
Abstract:
Advanced Collision Detection Techniques
Abstract: This article will take a top-down approach to collision detection by first looking at the whole picture and then quickly inspecting the core routines. I’ll discuss collision detection for two types of graphics engines: portal-based and BSP-based engines. Because the geometry in each engine is organized very differently from the other, the techniques for world-object collision detection are very different. The object-object collision detection, for the most part, will be the same for both types of engines, depending upon your current implementation. After we cover polygonal collision detection, we’ll examine how to extend what we’ve learned to curved objects.
Crashing into the New Year: Collision Detection
Abstract: Collision detection is a huge issue and an active area of research in graphics simulation. Using techniques such as the dot product and cross product, Jeff Lander investigates some common problems that can be important to a variety of game applications.
When Two Hearts Collide: Axis-Aligned Bounding Boxes
Abstract: Most discussions of collision detection for real-time game applications begin with bounding spheres and bounding boxes. While fast, bounding spheres don't generally give the best approximation of an object's extent. Jeff Lander demonstrates the use of axis-aligned bounding boxes for 3D collision detection.
2D Collision Detection
Abstract: Collision detection in 2D graphics is fairly straight-forward. You are normally trying to see whether two rectangular areas are in any way touching or overlapping each other. The rectangles to test for overlapping are the vertical and horizontal extents of the two bitmap images you want to perform collision detection on.
Octree Partitioning Techniques
Abstract: Using Octree Space Partioning correctly can make all the difference between just another game and a beatiful work of art. Mike Kelleghan shows how it's done.
|
