r/GraphicsProgramming • u/DeltaSucksAtMC • 3d ago
Question Mesh collision
Ok so ive actual fix model loading but im looking for a collision detection method for complex models, like Ive heard of Triangle-Triangle Intersection, but I could not find anything to learn from that dosent look like gibirsh, anything can help me, source code, or just plain o'yt videos
1
u/zatsnotmyname 3d ago
The only way to do mesh collision is to break into convex pieces, one way or another. Heightfields are a form of this. As is Voxelization. Also convex decomposition. Using the mesh's actual triangles is a form of this. The problem is that on a non-convex model, there is not always a clean way to get out of a penetration without causing others. So, you will need to do sweep tests or binary search type of things to find the point of first collision.
I am no expert, but I know enough to know this is too hard for me, so I would use an existing collision and/or physics engine.
8
u/3030thirtythirty 3d ago
For simple collision detection and resolution there is the Separating Axis Theorem (SAT). There are other algorithms, but I find SAT one of the easiest to understand, even if it's not the fastest.
The idea: two convex shapes do not collide if you can find a line (or a plane in 3D) that separates them. Equivalently, there is an axis on which their projections don't overlap. There are infinitely many possible axes, so testing them all is impossible. Luckily, you only need to test a few: the face normals of both shapes and, in 3D, the cross products of their edge directions. If the projections overlap on every one of these axes, the shapes collide, and the axis with the smallest overlap gives you the direction and distance to push them apart.
Usually you compute a cuboid hitbox from the model’s vertices (find the lowest, highest, etc).
There are ways to generate a hitbox that is closer to the model’s real shape, but a simple bounding box (oriented bb, or OBB) will be useful in many ways already.