Collision
Detection
The collision detection method described is between a sphere and a polygon mesh. The coodernate system used is the universe. The mesh has only convex polygons. The viewer is the sphere. The center is viewer position, and, is recomendable, as minimum radius, the half viewport diagonal measure, in universe reference system coordenate units. The collision detection is made in two steps. First, verify if the distance between the sphere and the polygon plan is equal or less than the radius. Second step, case the first is true, verify if the intersection point between sphere and the plan is inside the polygon area. For each polygon in the mesh is needed make collision detection tests. This can be optimized, as suggested bellow. To implement the first step is needed define the distance, between a point (viewer position) and a plan, using the expression: distance = ax + by + cz - d where, (a, b, c) are the polygon normal vector normalized, (x, y, z) are viewer position, d = - ax' - by' - cz', (x', y', z') are any point inside plan (can be a vertex). Both, "d" and (a, b, c), can be pre-calculated. If the distance is equal or less than sphere radius is needed run the second step. In my implementations, the second step, doesn't work for all cases. I don't know exactly why. For the second step is needed one new information: the intersection point. The intersection point between the sphere and the plan can be computed by projecting the sphere center to the plan, using the expression: px = x - a * distance py = y - b * distance pz = z - c * distance where, (px, py, pz) is the projected point, (x, y, z) is sphere center position is space, (a, b, c) are the polygon normal vector normalized, "distance" is the value computed on first step. To verify if a point is inside a convex polygon is used dot-product between two vectors. The algorithm is: - select one polygon vertex; - make a vector from selected vertex to its next vertex; - make other vector from the selected vertex and the point to be tested; - compute dot-product; - select the next vertex and make all again. If the dot-product sign change during the interaction, this mean the point is outside the polygon. If there is no sign change, the point is inside the polygon. Example of how to get the vectors: 1--------2 / \ / \ / \ / \ / polygon 3 / / / / / / 5------------------4 * point Interaction 0: 1--------2 / \ / \ / \ / \ / polygon _ 3 / /| / / / / 5------------------4------->* point Interaction 1: 1--------2_ / |\ / \ / \ / \ / polygon 3 / / \ / / \ / / _\/ 5------------------4 * point .... The first step can be optimized if the mesh has explicit information about its plans. Share a plan with many polygons have other advantajes like: memory save, more efficient back-face culling, ... Other optimization can be made, if collision detection is to avoid polygon crossing. For example, between the viewer and a wall, in some cases, is only need the first step. If the polygon is not in same plan as a portal (portals must be crossable polygons) maybe this is possible. If the collision detection is made only between the sector where viewer is, there is a problem. No adjacent sectors can be smaller than the viewer radius. Or while the viewer is going to the adjacent sector it can cross some destin sector polygons. In second step, 3DFC v0.0.1 use other way to make sign test. Is used, cross-product between two vectors to define a normal vector. The sign test is made over each normal vector component. This solution is more slow and don't work for all cases.