 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
Southwest Gaming ExpoWorkshop on Network and Systems Support for Games (NetGames 2009)ICIDS 2009 Interactive StorytellingGlobal Game Jam
Appendix A - Detecting collision between two facesUp until now the problem of testing for collision between a pair of faces was a well solved problem. That meant that the algorithm assumed detecting if two faces intersect is a black box operation, the details weren't important for the algorithm itself. Still, in order to create a solid implementation of any collision detection scheme, the problem of intersecting faces must be solved. In this section two methods are presented that attempt this. The first method is called the intersection-based collision detection and is basically an accurate way of detecting whether any two faces intersect each other. Other methods exist as well, however, the second method presented here is a hybrid method that incorporates bounding spheres and some basic geometry testing. Intersection-based collision detectionThe problem of collision detection between faces can be broken down to two stages. A well known fact is that any two planes that are parallel don't intersect each other. A plane of course is a flat, infinitely thin, infinitely long surface in 3D space. Unless the planes that contain the faces are parallel, those two planes are going to intersect each other. The first stage would be to detect if any edges of the first face intersect the plane of the second face. That ensures that the first face at least intersects the plane that contains the second face, but it is not sufficient in order to determine if the first face intersects the actual second face. This will be dealt with in the second stage. In order to determine if any edges in the first face pierce the second face's plane, the vertices making up the edges must be examined. For simplicity, if two points that define an edge fall on one side of the plane (containing the second face), the edge does not pierce that plane. Then, generalizing for the entire face, if all edges don't pierce the plane, the face does not pierce the plane. If any edge pierces the plane it is assured that at least one edge pierces the plane. For convex polygons there are exactly two edges piercing the plane. The only thing left to solve is how to find whether an edge pierces the plane. It so happens that all points in space that satisfy the following equation fall on the plane:
This might be familiar to you. It is called the plane equation. Any point that lies on the plane itself will evaluate the equation to be true. It so happens that any points on one "side" of the plane produce a positive sign (instead of 0) and all the points on the other "side" produce a negative sign. Therefore, if an edge is defined by two points (vertices) and solving for both vertices gives the same sign, the edge is definitely not piercing the plane. The logical extension to this is to check all edges against the plane. The check becomes very simple:
If there was any piercing by any edge, the second stage should be used to actually detect whether the edges actually pierce the second face itself, unlike the plane tested against in the first step. Actually, this step is all that is needed in order to determine if two faces intersect. However, the second stage is much slower in comparison with stage one. Stage one can be used as an optimization to rule out any faces that definitely don't collide. Because this algorithm deals with convex polygons (faces actually), this stage will assume the same. Since step one stopped when an edge that pierces the second plane was found, and there are actually two such edges (again, for convex polygons such as triangles), there must be exactly two intersection points between the face and the plane of the other face. Using the plane equation and solving for the x,y and z coordinates of the point that represent the intersection between the plane and the edge it is possible to find those two intersection points. Those points are naturally on the plane itself. Once two intersection points are found, in order to determine whether the edge pierced the second face itself, at least one of the points must be within the second face! What is left then is to determine whether a point is within a convex polygon or not. If one of them is within it, there is a definite collision. If both are not within it, there is definitely no collision. There is one very simple solution to this problem, called the half-space method. The halfspace method is a method to determine if a point lies within a convex polygon. For 2D polygons this is simple. Using the line equations of the edges and solving for the point gives either 0, a negative sign or a positive sign, just like in the previous step. However, our edges are vectors in 3D space so this doesn't apply here. What can be done instead is create a plane that is perpendicular both to the normal of the face and the edge vector. That plane divides space into two parts and therefore the point must lie either on it, or on one of its sides. The same logic from the previous stage applies here as well:
Hybrid collision detection between two facesThis method is a proposed method that approximates intersection between a pair of faces. The idea is to find a bounding sphere for both faces. If the bounding spheres intersect (an easy and fast check), there is a need for a better check. If the bounding spheres do not intersect, there is definitely no intersection. For intersecting bounding spheres, there is the possibility of collision. Consider using the logic in the previous method's stage one to determine whether edges on the first face pierce the second. Although this alone does not guarantee collision of course, coupled with the bounding spheres check it gives a reasonable chance for collision. That is, if the spheres collided AND an edge was found to be piercing the other face, most chances there is a collision. Of course, this method is only an approximation and will not give accurate results such as those provided by the intersection method. However, this method is by far much faster than the intersection based method. Generally, the smaller the faces, the better this method works. This is because when the faces are smaller, there is less and less "free space" within the sphere. Less free space that can generate a collision between spheres but might not actually generate a collision between the faces themselves. Appendix B - Determining k, the accuracy constantThe reasoning behind assigning a proper k value are totally up to the engine in question. In most cases in a normal 3D surface, each vertex will share a maximum of four polygons (each made of two triangles). Of course, there are cases, such as the tip of a pyramid with n sides that do not satisfy this condition. For the first case, a normal 3D surface, each vertex can be shared by 8 triangles at most and 4 at the very minimum. Therefore those values are chosen as the default accuracy range for most purposes. Assigning a different value might serve different types of geometry better though, it has to be considered carefully. For the cases where a vertex does not share only 8 triangles (such as the tip of an n-sided pyramid), it is a definite fact that if the vertex falls within another 3D object, all of the n-sides of the pyramid will intersect the other object. Therefore, any value for k that is one or more will suffice for this type of degenerate case. It happens that any 3D geometry can be represented either by the former representation or the latter. The latter has no bearing on the assignment of k. The former has and it has been shown that a value of 6 is the best average while 8 should give good accuracy. About this document...Opposing Face GeometryA Collision Detection Optimization Scheme This document was generated using the LaTeX2HTML translator Version 2002 (1.62) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The translation was initiated by Lord Soth on 2004-01-05 Lord Soth 2004-01-05 |
|
