0
\$\begingroup\$

I am wondering how you would be able to extract mesh properties (i.e. faces, vertices, and vertex normals) and use them to create a collidable object, one that a camera can't go through ?

I am using @TheCodingUniverse's OBJLoader. The files are in the episode_24 and utility folders.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hey Sean, maybe provide some informations about what you have tried and where your problem resides. Questions with an actual problem have a higher chance to be answered correctly than questions in the style of 'Please hand me some code' \$\endgroup\$ – floAr Nov 22 '13 at 10:18
  • \$\begingroup\$ I don't think I have understand the question. Do You want to check if the camera have collided with an object? \$\endgroup\$ – dsilva.vinicius Nov 22 '13 at 16:59
  • \$\begingroup\$ @dsilva.vinicius: Yes, that is exactly what I want. I guess you could do it by getting the face, vertex normals, and vertices edges in the .obj file, and every time the camera moves, check for the position of the camera, and if it collides, move it's position back one. Would this be correct? \$\endgroup\$ – Sean Jordan Nov 23 '13 at 6:18
0
\$\begingroup\$

Just before going into how to do it in details, let me summarize what you need to do:

  1. Calculate Bounding Volume for your mesh (pre-process).
  2. Calculate distance between your camera and the bounding volume.
  3. Check if the camera position is less than a specific distance from the object.
  4. Trigger your collision response.

Calculate a bounding volume for your mesh

This is useful because a bounding volume is usually much simpler than your actual mesh, which makes your intersection test much simpler and much faster. As a simple example, in order to calculate an axis aligned bounding box:

A bounding box

  //Axis aligned bounding box, cannot be rotated in a direct way.
  struct AABB
  {
    Vec3 min;
    Vec3 max;
  };

  // Loop through vertices and get 
    AABB CalculateAxisAlignedBox()
    {
    Vec3 max( MIN_FLOAT, MIN_FLOAT, MIN_FLOAT);
    Vec3 min(MAX_FLOAT, MAX_FLOAT, MAX_FLOAT);

    for (int i=0; i< m_vertices.size(); ++i )
    {        
        if( m_vertices[i].x > max.x)
        {
            max.x= m_vertices[i].x;
        }
        //Do this for Y,Z

        if( m_vertices[i].x < min.x)
        {
            min.x= m_vertices[i].x;
        }
        //Do this for Y,Z
    }

    return AABB( min, max );
    }

What about the camera?

Unlike, the mesh, the camera can be considered as a single vertex. This gives us two simple options when dealing with the camera:

  • Consider the camera a single vertex.
  • Consider the camera a single vertex with a radius. In other words give your camera a sphere.

I will go with the first option because it's simpler.

Calculating Intersection

This is as simple as calculating the distance between the camera position and the bounding volume, if the distance is less than some distance stop the camera from entering the volume (do collision response).

// Calculates the square distance between point and an AABB
float SquaredDistPointAABB(Point p, AABB b)
{
float sqDist = 0.0f;

for (int i = 0; i < 3; i++) 
{
// For each axis, count any excess distance outside box extents
float v = p[i];
if (v < b.min[i]) sqDist += (b.min[i] - v) * (b.min[i] - v);
else 
if (v > b.max[i]) sqDist += (v - b.max[i]) * (v - b.max[i]);
}
return sqDist;
}

Here we calculate the distance squared, to avoid square root calculation, because it's faster, but you can simply take the square root.

What this solution doesn't do

This is a simple solution that can be enough for a simple game. But in the following scenarios it will clearly fell short.

What if I want trignle level collision detection?

In this solution we only checked for collision with the bounding volume, this good enough in case of the camera, but if you want more accurate collision detection, like for example Shooting a ray (bullet) in an FPS game, you need to check collision with the mesh triangles, there are other techniques can be used like using a proxy mesh which could be much simpler than the actual one, also check the next point.

What if I have N objects?

Well, for example if you have million objects it doesn't make sense to check for every intersection with those objects, what people do, is they do spatial partitioning to reduce checks to only those objects that are near (most likely will hit each other).

What about if my camera/object is moving at 1 bazillion km/h ?

Well, I doubt any collision engine can solve this (because of floating point accuracy). But (lame) jokes aside, moving objects (especially at high speeds) suffer from what is called Tunneling, in order to solve this you need to predict when the two objects will intersect, this will add the time variable to the static equation, so you need to calculate the possible time that two objects will collide. Which makes things a little bit more complicated.

\$\endgroup\$
  • \$\begingroup\$ How would I curve the box so I would be measuring the outline of the actual tree (made up object, not your example), not a space around it, so I could actually walk on the tree, etc.? \$\endgroup\$ – Sean Jordan Nov 24 '13 at 4:07
  • \$\begingroup\$ @SeanJordan that is somehow a different question, but in general you need to manually build sth like this thomasdiewald.com/blog/?p=1488, or use triangle level intersection (or both) but it's more complicated. \$\endgroup\$ – concept3d Nov 24 '13 at 6:51
-1
\$\begingroup\$

Games use Collision Detection and Response to ensure no interpenetration of objects. Collision Detection is divided in broad phase and narrow phase. In the broad phase coarse representations of the objects are tested for collision, for performance reasons. These representations are called Bounding Volumes (BVs) and are easy to test. Examples are spheres, boxes, k-dops.

The narrow phase is more accurate and checks for collisions of the primitives (faces in your case) of the objects that collided in the broad phase. How this is done depends which primitives you are using and other factors, such as if you are doing continuous or discrete collision detection.

Collision Response is about what the system does to resolve the interpenetrations detected. There are several ways of doing this, each one with different levels of accuracy and performance. For example, you can project one of the objects so there is no more collisions. This approach is fast and solves the problem, but lacks physical accuracy since velocities and accelerations are not taken into consideration. Others approaches such penalty-force and impulse-based methods

As you can see it is a very broad area and is an entire branch of Computer Graphics. I would suggest the book Real-time Collision Detection for deep explanation of algorithms and their tradeoffs. It's the Bible of the area. Another good books are Geometry Tools for Computer Graphics and Real-time Rendering, but they are more focused on the intersection algorithms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.