Collision Detection

Collision Detection

• WingingIT

  I would love to see your PolygonSoup code, that would be very helpful.
  If you would, please email it to me. I will give you credit for it when my game is finished (well, technically, I'm working on an engine, so it'll be in any game that uses the engine)
  
  

• m.a.fuchs

  Each Model mesh has a bounding sphere, check against it first.

  If you wish to do triangle collision tests after that then yes, you will have to use the vertices and indices (untransformed in your case it sounds like).

  If you have a way to seperate a levels sections in seperate ModelMeshs then that will help with determining more quickly which section(s) of the level the player is in.

  In my Quadtree project, I started writing a model importer/processor that did just that, with a heightmap. I eventually decided not to use that method, before I released it.

  
  
  

• xVxObliVioNxVx

  Heey, I also experienced exactly the same problem as you have. I also wanted to implement sphere (actualla an ellipsoid) vs triangle intersection. And in order to be able to do that I had to have access to vertex information, but my geometry was stored in a Model object with vertexbuffers. To solve this issue I took the following approach:
  
  I made a new class called PolygonSoup, which holds simply a list of triangle structs. I then made a custom Processor using the content pipeline, which generates PolygonSoups out of its input nodes. These PolygonSoup objects contain btw vertices in worldspace. I also made a Writer class to get those soups written to disk. And so I also made my own loader class which I use in my own project. So this way I can simply add a FBX or X model file to my content, set its processing type to "PolygonSoup" and then load it up using content.Load<PolygonSoup>("....."); It works really great, and I believe this is what the content pipeline is made for.
  
  Another reason why I did it this way is that I couldnt access the vertices from the vertexbuffer in the Model object I was using, since the buffer was writeonly. (According to the exception I got when trying it out) And there wasnt actually a reason for me for using a Model for my collision hull, since I wasnt going to draw it either.
  
  Anyway, I can give you my code for my PolygonSoup processor/writer if you like.
  
  grtz, Gloei
  
  

• Alexander Marinov

  That still doesn't answer my question of how to access each of the vertices in the mesh.
  I understand the concepts of checking each vertex's distance from the center point of my object and how I can determine if it has collided, but I still don't know how to do this.
  
  

• MotteKarotte

  First, you probably don't want to check against every triangle.  That's what spacial scene manager (ie, quadtree, octtree, binarytree, bsp, etc...) is for.  You can know that your object (bounding sphere) is located in some area by using one of the spacial trees.  Then use that information to reduce it down to a few triangles to check against.

  You could then, check each vertice in the triangles (some of which share vertices) using Ray.Intersects against the bounding sphere (whilch way does the ray point toward the center of the sphere) .  It returns the distance from the intersection, if it is greater than the radius of your bounding sphere, they don't intersect.  If all 3 points of a triangle are a greater distance from the center than the radius, the sphere does not intersect any part of the triangle.

  This is probably not the most effecient way, but is a way.  The spacial tree dividing up the world is a really effecient way to find the triangles that might intersect, though.

  The way I check for objects on a landscape is to find the height of the terrain at the location the object is at in x,z.  If it is at or below that height, it hit it or is touching it. 

  Depends on what your trying to do.......

  
  
  

• JinMengcheng

  The triangles in the meshparts are put together using vertex buffers (containing all the vectices) and indices (index into the vertex buffer) contained in the ModelMesh. The format of the vertex buffer is not just x,y,z (usually) but also tu,tv,color,etc......vertex format. That depends on your model and how it was created.

  If you must do it this way. I would pre-process the vertex buffers for each model right after loading them, making a copy of the x,y,z components by creating my own class Triangle and List<Triangle> (that would allow a foreach type thing). This would be your Physics.Meshes or what ever........(less data)

  
  
  

• Nipam N. Patel

  ClydeCoulter wrote:

  ... You could then, check each vertice in the triangles (some of which share vertices) using Ray.Intersects against the bounding sphere (whilch way does the ray point toward the center of the sphere) . It returns the distance from the intersection, if it is greater than the radius of your bounding sphere, they don't intersect. If all 3 points of a triangle are a greater distance from the center than the radius, the sphere does not intersect any part of the triangle. ...

  
  
  This is not a correct way of determining sphere/triangle intersection. It is possible to have a single triangle of about the size of the earth. Using your method, we can only intersect it at the three corners, and never near the center of the triangle.
  
  I myself do the following:
  - check if our sphere hits the plane of the triangle, if not we fail
  - check if our sphere is on the "inner side" of all the edge-planes of my triangle (an edge plane is the plane going through an edge, perpendicular to the triangle)
  - if we are on the innerside for all edges, we intersect the triangle!
  - if we arent on the innerside for all edges, we find the point closest to our sphere for each edge, and if any of these three points has a distance to the sphere smaller than the radius of the sphere we have an intersection
  
  I think this is correct in all situations. But it's still a bit of tricky math you have to use.
  
  

• George2

  How would I go about doing that
  
  

• cheesenhomer

  I recommend the book "real-time collision detection" by Christer Ericsson. It does a great job of explaining many of the intricacies of real-time collision detection, how to accelerate it through pre-processing, etc. It does use C++, but assuming you can read that, the examples are all easily portable to the language of your choice.
  
  Another source of collision information is most books on the Magic engine by David Eberly.
  
  
  

• Radith

  Perhaps we need more information.

  What is a "level" that you refer to   Landscape other objects   If landscape, are you using a Model for it

  A model has ModelMeshes that contain the vertex buffer for all its MeshParts.  You would need to transform them (from model space to world space) then each meshpart describes the indices for their triangles that index into the vertices you transformed.

   

  
  
  

• psc161

  I still don't understand how to get the vertex data for each triangle in the ModelMesh.
  How would I go about compiling each triangle into a set of Vector3's (or any other list) for each vertex.
  What I would like to do (or at least try for now) is to basically:
  foreach (ModelMesh mesh in level.Meshes)
  {
  foreach (ModelMesh part in myModel.Meshes)
  {
  float Ax = mesh.BoundingSphere.Center.X;
  float Az = mesh.BoundingSphere.Center.Z;
  float Ay = mesh.BoundingSphere.Center.Y;
  float Bx = part.BoundingSphere.Center.X;
  float Bz = part.BoundingSphere.Center.Z;
  float By = part.BoundingSphere.Center.Y;
  if (GetDistance(Ax,Az,Ay,Bx,Bz,By) < (part.BoundingSphere.Radius + mesh.BoundingSphere.Radius))
  {
  foreach ([set of vertices] tri in mesh.[list of triangles])
  {
  if (collided == false)
  {
  if ([GetTriDist](tri,Bx,Bz,By) < part.BoundingSphere.Radius)
  {
  (reverse direction);
  collided = true;
  }
  }
  if ([GetTriDist](tri,Bx,Bz,By) > part.BoundingSphere.Radius)
  { collided = false; }
  }
  }
  }
  }
  ---
  I need to know how I would go about doing everything I've dubbed in brackets
  My GetDistance() is defined as:
  public double GetDistance(float Ax, float Az, float Ay, float Bx, float Bz, float By)
  {
  double dx = Ax - Bx;
  double dy = Ay - By;
  double dz = Az - Bz;
  double dist = Math.Sqrt(dx * dx + dy * dy + dz * dz);
  return dist;
  }
  EDIT:
  Or, better yet, I could create a separate model containing a set of spheres that define the collision of my mesh, it would work the same way only it would be more accurate... Instead of myModel.Meshes, it would be physics.Meshes or something along those lines..
  
  

• Asbj&amp;#248;rn

  No problem. I cleaned up my library code a bit and made an example set-up, which includes all sources and shows how to use it in an example game.
  You're free to use it and adapt it in any way you like. (At your own risk :)) (Ohw and I like getting credits for it, but its not necessary I think,
  its quite basic code. Most of it was copied from the XNA manual. From the topic "Extending the content pipeline".)
  
  You can download it from here: PolygonSoupLibrary example.
  
  I also included an info file with a bit more info in it. Hope you like it. If needed, I can give some more info here. PS. This only includes
  code for importing/processing raw triangle lists ("polygonsoups") out of models. No actual collision detection code is included. (I did write
  my own collision detection code, but I rather not (yet) share it. It's not so stable, and really badly coded.)
  
  Hopefully this is of any use for you guys.
  
  

• Greg Van Mullem

  Same here, I'm working on an engine also, and I've been stuck on triangle collision... Is there any chance I could get it also
  

• Bill YU

  The 'level' is a model, yes, more than a landscape, which is why I want to determine collision with each polygon of the model.
  So, I'll need to convert the local coordinates to world coordinates (except the world doesn't move, so shouldn't they all be the same anyway The level model stays at the origin, so the coordinates wouldn't need to be transformed like that) From there I need the vertices from the triangles from the vertex buffer from the model mesh. Correct
  
  
• Collision Detection