Archived

This topic is now archived and is closed to further replies.

Witchcraven

Vertex-triangle collision help

Recommended Posts

Witchcraven    564
I am doing an rts in 3d. Outdoor landscape will be made of many triangles. I am thinking to move a unit on the landscape I will have an invisible vertex at his feet that is used to make sure he can traverse the terrain correctly. So I need to know to check if that vertex is colliding with a triangle.

Share this post


Link to post
Share on other sites
Witchcraven    564
I just had perhaps a better idea. A ray going vertically through the character. I could move the ray through space as if it were 2d by adjusting the xy coordinates, what I need to know is where on the ray does the trianle intersect. THat way I just need to draw the character at that point.

Share this post


Link to post
Share on other sites
atcdevil    145
If a point is inside of a triangle the sum of the angles it makes with the triangle will equal 360 degrees.

Here''s how to do find this out:
First you will want to get the three vectors, to do so subtract the point from each vertice. Then you want to take the anticosine of the dot product between each vector so that you have the 3 angles. Then you can add them together, And if the sum equals 360 degrees or if it is at least close enough the vertex is inside.


[Edited by - atcdevil on October 12, 2006 10:04:37 AM]

Share this post


Link to post
Share on other sites
benjamin bunny    838
A word of advice: don't try to find where vertices intersect a triangle at a given time frame. Most probably, the vertex won't intersect the triangle at all - it'll just pass right through between frames. Treat the vertex's positions from one frame to the next as 2 points on a line segment and see whether that intersects the triangle.

Here's how you do it:

Get the triangle's plane equation in the form Ax+By+Cz+D=0

A, B and C are the triangle's normal. To get the D part, just plug any point on the plane (such as one of the triangle's vertices) into the equation, so if you have a vertex at 1,2,3, and a normal of (0,1,0), the equation looks like this

1*0 + 2*1 + 3*0 + D=0
so D+2=0
so D=-2

Next, you need to know if (and where) the ray intersects with the plane of the triangle. A line segment (a non-infinite line) in 3D space is defined as

x = x1 + i*t
y = y1 + j*t
z = z1 + k*t

t is how far along the line the point is (0 for at the start, 1 for at the end)
i,j and k are the difference in x y and z: x2-x1, y2-y1 and z2-z1, respectively
x1,y1,z1 is the line start, x2,y2,z2 is the line end,

You need to find t, which will tell you how far along the line segment the plane is. If it's between 0 and 1, the plane intersects the line segment.

Substitute the line equations into the plane equation and you get
t = - (a*x1 + b*y1 + c*z1 + d)/(a*i + b*j + c*k)

if (a*i + b*j + c*k) is equal to 0, the plane and the line are parallel and you'll get a divby0 error when you try to do the calculation; so calculate this value first and return PARALLEL
or something if it's equal to 0.

if t is equal between 0 and 1 then the plane and your line segment intersect. You can get the position of the point of intersection like this

x=x1+i+t
y=y1+j+t
z=z1+k+t


If your line segment doesn't intersect the plane, your triangle and the plane do not intersect, obviously. You can return false or whatever.

Otherwise, you need to find if the point of intersection you calculated is on the triangle. You can do that by the method described above; it works fine, but there is a much faster way, which does not use expensive arccosine calls:

You have a triangle, and a point, p, and you want to find if p is in the triangle. Here's a picture:



If you take the cross product of ab with ac, you'll find the resultant vector points out of the triangle into the screen. If you take the crossproduct of ab with ap, you'll find the vector points the opposite way. This is because ap is on the other side of ab. P is therefore not in the triangle.

If you check all the sides of a triangle like this, you can find whether p is in the triangle.

I think that just about covers it. Any questions?

[edit]clarification of some bits[/edit]
[edit]fixing ascii masterpiece[/edit]
[edit]ascii masterpiece still dead. screw the ascii masterpiece - uploaded a picture[/edit]

www.elf-stone.com

Edited by - benjamin bunny on January 14, 2002 9:01:41 AM

Edited by - benjamin bunny on January 14, 2002 9:03:42 AM

Edited by - benjamin bunny on January 14, 2002 9:26:31 AM

Share this post


Link to post
Share on other sites
MENTAL    383
http://www.acm.org/jgt/papers/MollerTrumbore97/code.html


that will calculate a collision between an ray and a triangle and return the barycentric co-ordinates of the intersection. although you will probably have no use for the U and V values, by performing Ray.Origin + (Ray.Direction * T) you will get the intersection point in 3d world co-ordinates.

example:

  
float T, U, V;
float loc[3];

// define rayorigin, raydir, vert0, vert1 and vert2 somewhere else


int result = intersect_triangle (rayorigin, raydir, vert0, vert1, vert2, &T, &U, &V);

if (result == 1)
{
loc[0] = rayorigin[0] + (raydir[0] * T);
loc[1] = rayorigin[1] + (raydir[1] * T);
loc[2] = rayorigin[2] + (raydir[2] * T);
}

else
{
// do whatever

}



if you dont know what to do with the U and V values, then ignore them for now (just don''t remove the code to calculate them from intersect_triangle!), but they might become useful later.

Share this post


Link to post
Share on other sites
Witchcraven    564
THanks for the replies. BTW, I cant check the forums every 10 minutes to thank the posters. I am fairly busy

Edited by - witchcraven on January 15, 2002 12:45:13 PM

Share this post


Link to post
Share on other sites
benjamin bunny    838
I thought it was a pretty safe assumption that you wouldn''t say thanks, seeing as A) you didn''t reply within 24 hours and B) I checked your profile and found you didn''t say thanks once after the last 4 times you asked for help and got it.

I guess I''m being a bit petty about this, but I just get pissed off sometimes when I go to the effort of helping someone out and they don''t even acknowledge it.

www.elf-stone.com

Share this post


Link to post
Share on other sites