Collision Detection of a Projectile on an Object

Hello,

I am doing a simulation in MatLab for my PhD thesis work and it involves shooting projectiles (modeled as point particles with random trajectories) at an object. At first I started with a rectangular plate in 3D space at a distance "z" from the emitter, as this was easy (just define x and y bounds) to see if the projectiles trajectory has hit it but now I want to move on to any irregular object in 3D space.

So what I have done is used an external modeling software to make a 3D object and export it as an .obj. This gives me

1.) Verticie information of the model. 2.) Normal vector information on the model.

What I did in the rectangular plate case was the following.

1.) Randomly assign a projectile a velocity vector [vx,vy,vz]. 2.) Using the standard kinematics equation (z=Vz*t),Plug in the value of "z" that the plate is located at to determine the time it took the projectile to get there 3.) Plug this time value into the x and y components (x=Vx*t and y=Vy*t) to see if x and y are within the bounds of the plate. 4.) If yes, then calculate the reflected trajectory using the following equation. Vr=2*(normal vector dot trajectory unit vector)*normal vector-trajectory unit vector.

The problem I am having with an arbitrary 3D object is, most of the time, the trajectory is going to go BETWEEN the vertices of the model.And I cannot think of a way to fix this issue. I cannot just define bounds as in the rectangular plate case, and I need to be able to determine the normal vector of the point it DOES hit to calculate the reflected trajectory.

Basically the question is, What would be a good way to determine if the trajectory has passed BETWEEN the verticies?

Answer 1

[Mohammad Abouali]

Nice project.

So you have basically bunch of points and the normal vectors at those vector.

I am sure if we go to graphic programming text books this is a resolved issue look under ray tracing. But what comes to my mind is this:

Get a voronoi mesh consisting of these points, and assume that that normal vector is valid for the extend of that voronoi polygon.

Now there is one problem. Your vornoi (facet) may not anymore have the same z all over. Your standard method of detecting t is good if your plate has the constant z all over. But it now that you are working general it might not have the same z. Here how you can overcome this

Your particle travels along a vector based on Vx,Vy,Vz velocity vectors ( I noticed that you don't have gravity). if the initial location of your point is L0=[x0;y0;z0] then L=(x,y,z), i.e. the location of your particle after passing t seconds, is defined with the following equation

L=[z;y;z]=L0+t*S*u

where S=norm( U ) and u=U/S and U=[Vx;Vy;Vz];

Now, for each voronoi you have a point P0 and a normal vector n. (make sure that norm(n)=1)

You can detect "t" as follow

t= (1/S) * dot( P0-L0, n) / dot(u,n);

Once solved for t get the point location as follow:

L=P0+t*S*u

Once you did that use inpolygon, to check if L is within the facet/boundary. If it was that ray is going to hit that facet and not the other one.

[Matthew Brandsema]

Thank you for your reply! So let me see if I understand totally what you're saying.

P0-L0 = Vector from the original position of the particle to the point P0 on the object

It looks like your formula for "t" was obtained by solving for "t" from the equation P0=L0+t*S*u after dotting by "n" on both sides. In my mind, this means you are projecting onto the direction of the normal vector.

So we are first projecting the velocity vector onto the normal of the point in question and then seeing how long it takes that vector to get to the distance P0. At this point, we can check to see if the coordinates of the vector are within the polygon by using inpolygon.

I believe I understand. The one thing confusing me is, I do not know much about voronoi polygons. In fact, this is the first time of me hearing about them. How do I define each polygon from my set of verticies?

Also I should mention that the list of normals given in the .obj file are vertex normals, meaning the normal of each vertex. Not the normals of each polygon.

Also I am ignoring gravity. These are supposed to be photons modeled as particles.

[Mohammad Abouali]

So, let's say L0 is a point on a line whose direction is defined by a unit vector u, i.e. norm(u)=1. In vector representation any point on that line can be written as:

L=L0+alpha*u; % This is line equation in vector form.

Now let's say P0 is a point on a surface defined by it's unit normal vector n, i.e. norm(n)=1. Any other point which is on the same plane should satisfy this equation

(P-P0).n=0;

This is the vector form of a plane equation.

Now we want to intersect our above line by this plane; or we want to see which L lies on the same plane as the one defined above

So we check if L satisfies our equation, i.e.

(L-P0).n=0;

or

(L0+alpha*u-P0).n;

solving for alpha you get

alpha= (P0-L0).n / u.n = dot( P0-L0, n) / dot(u,n);

We had alpha=t*S so t=alpha/S or

t= (1/S) * dot( P0-L0, n) / dot(u,n)

Two things you have to pay attention.

1) The above formula is for a plane or surface that goes to infinity. But your voronoi facets are not going to infinity and they are limited in span. So, check with inpolygon at the end.

2) if u.n=0 it means that your line and the plane are parallel. Now check if dot(P0-L0,n) is zero. If it is zero your line is in the plane, so you have infinite answer. If it is not zero, then your line never touches that plane.

If you want to know more about voronoi I suggest looking at

http://www.mathworks.com/help/matlab/ref/voronoin.html

It gives more visual information on what they are. pretty much if you have bunch of points, after calculating the voronoi it tells which part of your area is closest to which point. All those point that are closest to the same point would form your facet.

Hope this was helpful to clear some of the equations.

Answer 2

[Matthew Brandsema]

Hello again, sorry about the very delayed response. I had other work to do this week and this project got pushed to the back burner.

Anyway your explanation was incredibly helpful and I believe I fully understand everything. I am having one issue and I was wondering if you could help clear things up.

The command "[V,C]=voronoin(X)" outputs all of the vertices of the voronoi polygons in variable V and the information on which of these verticies make up each polygon in variable "C". However, I need to be able to match up each ACTUAL vertex with its respective voronoi polygon. "voronoin(X)" only gives me information on the voronoi polygons but not which polygon is assigned to which vertex.

[Mohammad Abouali]

In "[V,C]=voronoin(X)" X is your points. V stores the vertices of Voronoi coordinate and C pretty much is the connectivity matrix.

If you want to get the voronoi polygon surrounding point defined by X(i,:) you can construct the polygon as follow:

polygonSurroundingXi= V(C{i},:)

It's good to check that it did not returned any coordinate as inf. if you want to make sure that the last point in the polygon is the same as first point then do this:

polygonSurroundingXi= V([C{i} C{i}(1)],:)

Let's give an example: {This is from MALTAB Help with some modification}

x = [ 0.5    0
      0      0.5
     -0.5   -0.5
     -0.2   -0.1
     -0.1    0.1
      0.1   -0.1
      0.1    0.1 ]
[V,C] = voronoin(x)

so now to find the voronoi polygon surrounding point x(7,:) we can do:

i=7;
plot(x(i,1),x(i,2),'r.','MarkerSize',35)
hold on
plot(V([C{i} C{i}(1)],1),V([C{i} C{i}(1)],2),'b-')

[Mohammad Abouali]

By the way, there is the issue of transparency.

Here is the thing.

1) you calculate where your ray hits the facet. 2) you check with inpolygon that the location is actually within the facet.

Now it is possible that you find multiple facet with valid collision points. If your surface is transparent then that doesn't matter, but if your surface is opaque you must check which facet was hit first, i.e. check the one with smallest t.

Note that it is important to check smaller t after you have made sure that the collision point is within the facet extend. So do that after checking with inpolygon.

[Matthew Brandsema]

Thank you so much AGAIN! Your explanations are VERY clear and I am very grateful for all the help you have given me so far. I have one final issue. How do I deal with defining the edge polygons?

For example, I am starting things simple with a rectangular plate that is 0.1 meters long (thus, from -0.05 to 0.05 on both the x and y axis). All of the voronoi polygons associated with the edge verticies go to infinity.

I have attached an image showing what I mean.

Inside the green box is OK. But when trying to define the outer polygons, they have points along the green line, but then have a point that goes to infinity.

Take the point at (-0.05,0.03) for example. Should it not have the polygon defined as..

    -0.05 0.04
    -0.05 0.02
    -0.04 0.04
    -0.04 0.02

But when getting its actual polygon it gives me the following.

   -0.0400    0.0200
       Inf       Inf
   -0.0400    0.0400

Meaning it does not include the end points.

[Mohammad Abouali]

One quick solution that comes to my mind is to introduce some fake points around all your points. So this way your real points are not on the edge; hence, they won't have inf as coords in their voronoi facets. And just keep track of those fake points and make sure that you do not include them in your further calculation.

But let me check if Matlab has another option to do this.