# Collision detection between transformed meshes (not primitives)

I know questions related to collision detection have been asked multiple times, but I find all of them like this and this depend on the assumption that I have some sort of measurement of the object like the dimensions of the cube, or the radius of the sphere which is not true. I am working with vertex based geometry.

In my game, the vertex data is discarded after it is loaded into the Vertex Buffers.

So the question is that how can collide 2 objects of which i don't know details like the radius of the sphere? I am willing to implement the collision mesh, which again isn't necessarily going to be a cube but is regularly translated, rotated and scaled.

• Based on your latest edits, it sounds like your problem is that you have been looking at collision detection functions for primitives like cubes and spheres, not mesh collision detection solutions. The mesh case is still a well-studied problem, so you should try searching for terms like "convex hull collision" "GJK algorithm" "Separating Axis Theorem" "triangle-triangle intersection" etc. These will usually involve keeping a (possibly simplified/pre-processed) version of the mesh data and its transformation CPU-side, not discarding all mesh information after uploading it to the GPU. Commented Dec 1, 2021 at 11:34
• Ive used blender for some time and in it , "convex hull" is like a simpler ,lower poly version of the rendered mesh. Is this the same thing? @DMGregory Commented Dec 1, 2021 at 12:08
• @DMGregory thanks for the algorithm recommendations, will look into it. Commented Dec 1, 2021 at 12:09
• @DMGregory although i don't mean to say that i wanna implement collision only for primitives. i mean to say that i don't have measurements like radius and vertex data (at the moment) to compare their distances(which most online articles exhibit) Commented Dec 1, 2021 at 12:12
• Your convex hull question sounds like one you can answer with a search. It's not just simpler/lower-poly, it's convex — it has no concave hollows/notches/etc. Convex hulls are much easier to use for fast collision detection, because they save you from checking potentially every triangle of one mesh versus every triangle of the other. For that reason we'll often take a concave mesh and try to break it into convex pieces ("convex decomposition") so that we can still get reasonably fast collision checks with it. With regard to "I don't have vertex data", too bad. You need it, so you will get it Commented Dec 1, 2021 at 12:13

Ok I can write an answer.

You can either save the vertex data when you load the mesh and run the collision on those structures.

Or you can implement collision detection entirely on the GPU. Since there is no known solution by the community you will be looking at writing the collision engine in GPU code. Also, as you have found it is difficult to get vertex data back from the GPU so your collision results would mostly only exist in the OpenGL rendering.

The second option is dangerous territory, and if you are having problems with the first option I would say that it's probably easier to make some changes to allow copying the data than it is to write collision code for the GPU.

• The problem lies in " run the collision on those structures." what is this. how Commented Dec 1, 2021 at 11:02
• i have done some changes to the question because i think i have done a terrible job at explaining my problem. Commented Dec 1, 2021 at 11:09
• I think you could possibly refine your problem a little more. For example generating a sphere form your vertex data and colliding with a sphere could be two different problems.
– Jay
Commented Dec 1, 2021 at 22:44

Several meshes are usually used for an object:

• The rendering meshes, for rendering on screen. There can be several rendering meshes, for example to manage Level of Detail (LOD) or to display several states of the same object.
• The collision mesh, used by the physics engine for collision detection and resolution. This mesh is usually very simple compared to the rendering meshes to avoid very costly operations while being good enough for its purpose.

A mesh is a mesh, whether you intend to use it in OpenGL to render that magnificent ball or in your favorite physics engine to make that bouncy ball bounce.
Moreover, the physics engine will probably expect data not in the same format as OpenGL.

It is usual to have both the rendering mesh and collision mesh to be manually created, with the collision mesh being a crude approximation of the rendering mesh. I'm not aware of tools to automate this process, but they certainly exist, although it might be simpler to create the collision mesh manually.

If you still insist on using a single mesh to generate collision data, you still have a few options:

### 1. Use a single mesh to generate both OpenGL vertex data and to use in your collision system (NOT ADVISED)

This will be a performance nightmare. Really.

### 2. Simplify the rendering mesh to use in your collision system

You can do the transformation from a complex rendering mesh to a simplified collision mesh at runtime if you find an algorithm/tool that suits your need for it, although I would advise that you do it during the development process and that you embed the result along with the initial mesh in your game.

• I am willing to use collision meshes, but the problem is , how can i collide collision meshes in the first place, i am not using spheres of which i know the radius or cubes of which i know the vertices, that data is long discarded after it was loaded into the memory and now, the only thing which is alive at loop-time is the VAO id and the vertex count. Commented Dec 1, 2021 at 11:05
• i have done some changes to the question because i think i have done a terrible job at explaining my problem Commented Dec 1, 2021 at 11:10
• @ExtorcProductions If you have full control on what you're implementing, you should not discard that data if you need it later. Commented Dec 1, 2021 at 13:44

Expanding on my comment to try to give this old question some closure: common non-primitive polygon mesh collision detection functions include...

Both of these techniques work only for convex hulls: meshes that have no holes, caves, or divots, but they're way faster than the alternatives.

For that reason, many game engines will make (or allow the designer to author separately) a CPU-side physics-only version of the mesh that's reduced to its convex hull for collision purposes. Meshes that have important concavities can often be broken down into parts that are each convex, so you can run these fast algorithms on each part - see approximate convex decomposition for details on those techniques.

If your mesh is concave but well represented by a heightfield (eg. a terrain without caves or overhangs), then you can reduce collision detection to a 2D sweep over the heightfield checking if the highers height in the colliding object's footprint is above the lowest part of the object there.

If you need to find collisions with more general concave meshes that aren't heightfields and don't break down neatly into convex parts (meaning they have so many concavities that you'd end up with something close to one convex hull per triangle anyway), or worse, non-manifold geometry (meshes that don't have a clearly identified interior vs exterior), then unfortunately the only solution is to test for intersection against each polygon in the mesh. If you have to collide two such meshes, then you need to test for an intersection of each pair of triangles (yuck!). About the best you can do here is break up the triangles into some kind of acceleration structure like a spatial hash, BSP, or octree that lets you quickly find relevant triangles without visiting every single one.

If you can afford to approximate to some fixed resolution, and your mesh doesn't cover "too huge" an area, you can also create a signed distance function (SDF) from the mesh, and store it in a 3D array where the value at each lattice point is the distance from there to the closest point on the mesh (with negative values for points "inside". These are expensive to create, but fast to query, especially for small colliders. When you transform the mesh, you transform your query by the inverse of that transform, so you don't have to recalculate the SDF every time you move the mesh.

All of these approaches get much more expensive the more polygons are in your mesh, so it's common for the CPU-side physics mesh to be significantly lower-poly than the display mesh, whether it's crafted by hand or automatically decimated by some mesh simplification algorithm on import.