sponsors gamedev.net search:

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(k2), or rather to a maximum of k2 + 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. Introduction Collision detection is generalized as the means to detect whether any two objects in 3D space overlap. Over the years many models and ideas were suggested that attempt to either solve the problem entirely or approximate a solution. Of course, it has been shown that detecting collisions in a very accurate way is extremely computation intensive. Yet new ways and methods have been invented to optimize or accelerate the collision detection algorithms so those will be useable in real-time environments such as 3D simulations or 3D games. The method proposed here is called OFG and attempts to do the exact same thing - to optimize the collision detection algorithm by eliminating as many checks as possible. This article assumes the reader knows simple vector notation and operations, namely the dot product and vector sizes. The problem In real life, collision detection is a fact, it's simply how things work. Objects cannot occupy the same space, at least not usually. However, when dealing with computer programs it is clear that it's impossible to simulate the detail levels of the real world. In computer simulations the only way to actually define a 3D object is by defining the points from which its polygons are made. Each of these points is called a vertex, in plural - vertices. Defining a 3D object using only points connected by lines is the only way to represent a 3D object in a way that allows real-time simulations. This method is of course only an approximation, but when there are enough polygons making up an object, the approximation is very good. The representation of a 3D object is very simple. Vertices can be connected by lines to create closed shapes called 'polygons'1(usually triangles). A collection of faces constitutes a closed 3D object and therefore the only information at our disposal for collision detection testing is the vertices information. The problem begins by trying to create a model for collision detection. It seems highly unlikely that objects collide at exactly their vertices, and this is logically correct as well. Consider two normal cubes the same size. The two cubes can collide in an infinite number of ways and orientations, even without their vertices touching each other's or any connecting line between vertices (edges)2. What is more logical is that either edges themselves pierce the other object's faces, or some variation to that effect. The question then arises, how to detect faces intersecting each other? or better yet, how to detect edges piercing other faces? Well, the good news is that there are already good ways of testing for edges piercing faces. The bad news is that representing complex 3D objects requires a great deal of faces to look reasonably well, and since detecting intersection in an accurate way is slow in comparison to other optimized methods, this creates a big problem. In this article we will assume that detecting whether two faces intersect is a problem solved in a reasonable way and hence this article will not deal with methods for detecting actual intersection of a pair of faces, which is the most elementary test. For convenience a few methods are given in the appendix but it must be clear that OFG is a method for optimizing the entire process of object to object collision tests by dramatically reducing the number of faces needed for testing. Basic assumptions and the most general case In order to simplify the problem some basic assumptions need to be made. Of course these might present some problems but it must be clear that the assumptions help solve the most simple case. Later on the algorithm will be improved to circumvent some of the problems arising from the assumptions. The assumptions that we make are as follows: The objects that the algorithm is dealing with are convex3 3D objects only. It is true that the algorithm will work for some concave4 objects but care must be taken5. Detection of any pair of faces colliding is a well-defined and solved problem. Both objects have a pre-calculated center point. The accuracy constant k is set to be (min/max estimates) Object A has exactly n faces while object B has m faces. Under these assumptions, in order to detect a collision between objects, the most simple but inefficient method of checking every face in object A against every face in object B can be used. Actually, using the brute force method works for all types of objects, convex or concave. It makes no difference to the algorithm. For the brute force method therefore an order magnitude of O(nm) represents the algorithm's time complexity. The problem with this approach is obvious - detecting collision between complex objects becomes a very long operation. The more faces objects have, the more checks are needed. For two normal cubes, each with 6 sides (two faces per side, assuming each face is a triangle), the number of checks is: 12 * 12 = 144 tests between pairs of faces. For two objects with 100 faces each, the number increases very fast: 100 * 100 = 10,000 For two objects with 200 faces each, the number increases again to: 200 * 200 = 40,000 It is clear that this method is highly inefficient when dealing with more and more complex objects. Footnotes 1     In this article the term 'polygon' will be replaced by 'face' 2 Lines connecting two vertices are called 'edges' 3 Convex - A polygon (face) that has no "dents" in it. 4 Concave - A face that has "dents" in it. An edge connecting 2 vertices might fall outside the face. 5 Later on the problem of concave objects will be discussed The Opposing Face Geometry algorithm

Contents   Introduction   The Opposing Face Geometry algorithm   Problems with the basic OFG algorithm   Appendices   Printable version   Discuss this article