转载：Model Based Collision Detection-白红宇

转载：Model Based Collision Detection

阅读量：5323 次

发布时间：2019-06-14

本文共 12159 字，大约阅读时间需要 40 分钟。

转自：http://www.ziggyware.com/readarticle.php?article_id=156

Objective

This tutorial shows you how to write model based collision detection.

Introduction

I mean we’ll have a separate collision model which is not a particular 3D shape (like a sphere or a box), but any 3D shape, that we have described with vertices and indices. I’ve chosen this topic, because I haven’t found ANY articles about this on the internet (maybe distant hints, or some ideas but nothing concrete).

Step 1: Math

Mostly we’ll use Vector3.Dot and Vector3.Cross as base methods. If you know what these are exactly doing (which is not impossible) you can step this part, but it can be useful for younger ones (who haven’t learnt yet) (it took me as well a few weeks to match the expression dot product with the Hungarian term, and to realize that I’ve already learnt it).

So, dot product: also scalar product, with vectors a and b: |a|*|b|*cosβ (|a| and |b| are the length of the two vectors and β is the angle between them). It is also equal to ax*bx + ay*by + az*bz . Now that is how Vector.Dot doing is it, exactly:

So how can we use this? If you look at the former formula (I love alliterations) |a| and |b| is positive, so if cosβ is positive the dot product is positive as well etc. So if β is less than 90°, the dot product is positive, if β more than 90° the dot product is negative, if β equals to 90° the dot product is 0.

Cross product (also called vector product) of two vectors is a vector, that perpendicular to both vectors, with a direction given by the right-handed rule:

aXb=-bXa, which is important! We’ll use this, but don’t be afraid you won’t have to imagine this hall thing every time, it is enough to know that the order counts, so if it’s not working with aXb, try bXa and tadam(If it’s not working either, sorry but you have to imagine it:( )!

If you interested:

Step 2: CollisionMesh class (and Math)

We’ll create a CollisionMesh class to store the model data and to handle the necessary calculations. First we’ll create a static method to determine that our point moved through a side’s plane or not. If the old position is on one side of the plane and the new position is on the other side of the plane they have intersected. If we give the collision model’s indices in a specific order (we’ll give it in clockwise), we can tell that the point wants to get out or get into the mesh. If it wants to come out we’ll give it a chance (even havoc makes mistakes, it’s Ok to have a B plan). We’ll use a cross product to get the plane’s normal and a dot product to get the angle between the vector that points to the new position and the plane’s normal (I mean not exactly the angle only it’s relationship with the 90°) with an addition that we know that the angle have to be less than 90° to be outside of the shape (if we give the indices in a counterclockwise order the cross product will point to the other side of the plane so the angle will have to be greater than 90°).

(an example to intersection, every point is substracted by B in the picture already)

The former method is not enough for us, we need to know that the ray defined by the new and the old coordinates of the point is crossing the triangle or not? We’ll use the clockwise winding order again. Consider the triangle’s edges as 3 vectors: AB, BC and CA. If the ray intersects the triangle, it’s orientation with both edges must be the same. In our case it must be clockwise, because we used a clockwise order at the edges and when we assigned the indices (of course when both orientations are counterclockwise the ray intersects the triangle as well, but in that case the point wants to come out from the shape and we’ve already talked it over that it should feel free to do such thing). How can we check the orientations? We’ll play with cross and dot products again. In the picture the UV vector is on of the triangle’s oriented edges and the ON vector is the point’s movement. First we subtract U from all points thus we’ve transformed all vectors and U became the origin. Next we’ll compute V x O (you can mark the right-hand rule on the picture). If the angle (I always mean the smaller angle) between N’s position vector (UN vector at the moment, cause U is at the origin now) and V x O is greater than 90° ON’s orientation with UV is counterclockwise, if this angle is less than 90° the orientation is clockwise, if it’s equal to 90° it’s either intersecting or parallel. We can easily tell this with a simple dot product.

(the red arrow’s orientation here is clockwise) (and here is counterclockwise)

(the point crosses the triangle and as you can see its orientation with both oriented edges are the same, clockwise)

(In this picture the angle is greater than 90° so the orientation is counterclockwise)

Step 3: (Just) CollisionMesh class

We’ve done with the math part (at least for the moment), so let’s write the code that handles this model and add a few things to the CollisionMesh class.

(We won’t recreate the WorldMatrix every frame just if it changed)

Step 4: The program

Now we have a CollisionMesh class that does something (not many). Let’s use it! Here’s a basic program I’ve written for demonstration. You can move the camera with clicking the left button, rotate the yellow collision with buttons wasdqe, rotate the black collision with buttons 789456, move the black collision with the arrows and +- and you can roll to zoom!

If you try it know the black box's vertices won't go into the yellow box, but its edges and polygons will still go inside. We will fix this in a minute I've just wanted to show you something concrete.

Step 5: The fix

First we’ll do the easier, to not allow the yellow box’s vertices to go into the black boxes polygons. The theory is the same as we used just we’ll pretend that the yellow box moved. Add these lines before “Position += movement;”:

Now only the edges are going across each other cruelly. We use a similar technique as before. The movement of an edge can be described as a convex square (like we described the movement of a vertex as a line) and we can look at the other edge as a moving vertex.

(we’ve got a very similar picture aren’t we?)

The problem is that we have to store a description of the edges somehow. We’ll use indices again.

Add this to the top of the CollisionMesh class:

And this code into the BoxPrimitive function:

Now we have another problem. We’ve designed our CheckPlaneIntersection and CheckRayTriangleIntersection functions to allow vertices to come out, but now the situation is different and we don’t know anything about the orientations, thus we have to write new functions to handle this. First:

The other one is a bit trickier:

And finally we have to complete the Move method, add these lines before the “Position += movement;” again:

Try it! A strange thing happens, sometimes our box just stuck in the air, because CheckPlaneIntersection is not perfect. Why? Cause sometimes there aren’t any plane just a line! Consider the case when the moving edge’s coordinates are (0,3,0) and (0,4,0)

and it’s moving up 0.01f on the Y axis! In this case we won’t get any planes only a simple line, so it’s normal will be 0 (cause the angle between these points are 0) thus the dot products will be 0. So let’s change the code a bit:

It should work now, but if you give a bigger movement vector for example 2 or 3 it stops pretty far from the other box. It can be a problem when you’re working with fast moving objects or lower fps. We’ll fix this now.

Step 5: Finding the Intersection

We need the line’s equation in 3D and the plane’s equation: p = org + u * dir. P is a point on the line, org and dir are 3D vectors. If you have two points on a line you can get org by simply choosing one of them and dir by subtracting them from each other. With changing u you can get any points of the line.

The equation of a plane is p.normal = D. P is a point on the plane, normal is the normal vector of the plane, the dot between them means dot product it must be 0 if the point is on the plane (but if it’s not D it’s not on the plane). We’ll transform it again so it’ll intersect with the origin. When a plane lies on the origin D = 0 (if a point is on the plane in this case the angle between it and the normal must be 90° and cos90° = 0, so D = 0). Because dot product is commutative and distributive:

And from the line’s equation we can get the point. Let’s code!

We now dir, because it’s the same for every vertices, it’s the movement vector. We subtract B from A, C and LinePoint thus the plane goes through the origin. You can look at every vertices movement as a line’s equation, where org is the original point, dir is the movement vector, and when u = 1, you’ll get the new position of the vertex. Let’s integrate this to our code! Overwrite the first lines of the Move method to this:

Try it! Rotate the yellow box then hit it with the other one. If you try it a few times it’ll go inside. What’s the problem with our formulas? Nothing at the current stage of mathematics, the problem is in our code, it’s caused by the f****n floats (aren’t alliterations just beautiful?). Our program calculates the intersecting point, but it rounds and sometimes to the wrong direction so the black one goes into the yellow one. How can we prevent this? We need variable. Put this at the top of the CollisionMesh class:

And change these lines:

We scale the movement vector a bit (you can experiment with the TOWORK’s value).

If you try it you can see it’s still not working. The problem is similar. If the movement vector length is too short, the TOWORK variable becomes too great to handle the situation and it still goes in. We can solve this with an if statement. Change the last lines of the method:

You can experiment with this number as well.

Let’s implement this to the other two types of collision checks.

The last one is more difficult. Finding the point where they are intersecting (let’s call at E from now) it’s the easier part, we can do it just like before, but now an edge is moving not a point. We have to figure out how to get the new (shorter, to prevent collision) movement vector. We have to get the intersecting point between the line which is going across E and parallel to the movement vector and the line of the old position of the moving edge (check the former image). The vector that points from this point to E is our new movement vector (more clearly we look for the old position of the point on the edge that went to position E and get this movement vector). Let’s write down the equation of these two lines! The equation of the former line:

(the direction vector is the movement vector cause we’re working with the line where this point moved)

The equation of the letter line:

(dir = B – A, B and A are the endpoints of the edge)

These equations are a summary of:

And

Cause we need the intersecting point:

These are 3 equations and only s and t are unknown so the third equation is unnecessary. Let’s get s from the first one:

And put it into the second one:

Isn’t it beautiful? Now we can write a new method:

Now our completed move method:

We are done!

Step 6: Optimalization

My tutorial’s main goal was to show the techniques of such a model based collision detection and try to explain it thus I’ve tried to keep the code as basic and clear as possible, so it’s highly unoptimalized! We’ve computed a lot’s of things more than once, used unnecessary variables (but it’s the smaller problem). If you’ve fixed these there are many other techniques to speed up things a bit. It’s important to keep in mind that collision is extremely rare in comparison with when nothing collides. For example it’s advisable to use a bounding compound (box or sphere) or to sort the objects to grids and check collision on a moving object only in its own and the neighboring 8 grid. In this topic you can get nice ideas from the internet.