Maxunderground news unavailable

Triangle on triangle action 
Mr_Stabby 
Kind of a math problem. Lets say i have 2 triangles on a collision course, i have their vertex positions and velocities but need to determine the exact time and position of their collision. I started with colliding points and was easy enough with the quadratic formula and figured i'd somehow ramp it up to triangles but then my head just exploded :( the method needs to be analytical and not simulative, if anybody knows which way to point i'd be most grateful.
read 716 times 7/10/2012 1:24:08 AM (last edit: 7/10/2012 1:24:08 AM)

Garp 
One triangle can be used to determine a plane. As soon as one of the verts of the other triangles is not on the same side of that plane than the two others, you can test if one of the edges of one triangle crosses the surface of the other and if so, you have your collision.
For the first part, you can define a transform matrix with one triangle and test if, in its coordinate system, all three verts of the other triangle have their z coordinate of the same sign. You can also do it with just cross and dot products. The second part should be easy.
What language?
read 709 times 7/10/2012 1:40:40 AM (last edit: 7/10/2012 1:43:10 AM)

Mr_Stabby 
Well the problem is  i cant test, it allow for the possibility of them completely missing each other between samples, needs to be one big giant equation that eats the positions, velocities and accelerations and spits out either a time or a position. Right now im working towards a solution where it would first determine the possible time period for the collision (when each vertex of one triangle passes by the plane of the other triangle), then it would split into 3 with 2 vectors on each vertex (on the first triangle) to build a bezier definition of the point on the second triangles plane and then i would see if any 2 combinations of the curves match to determine the exact time.. but it just occurred to me that the triangle could also be rotating in which case each of these would spit out an undetermined number of curves and trying to patch it all together is just melting my brain :/
as for the language  HLSL but doesn't really matter which, just need the math
read 699 times 7/10/2012 1:57:55 AM (last edit: 7/10/2012 1:57:55 AM)

Garp 
If I understand correctly, what you have to start with is 6 equations giving the verts positions as a function of time. Is that right? What I mean is that each vertex trajectory can be represented mathematically, they are not animated 'by hand'.
read 695 times 7/10/2012 2:04:53 AM (last edit: 7/10/2012 2:06:44 AM)

Mr_Stabby 
yes the xyz motion of each vertex can be described with a formula of (position + velocity * time + acceleration * time^{2}) * matrix which has position, rotation and scale defined by ax^{2} + bx + c (where a,b,c are acceleration, velocity and position and x is time)
the more i look at this though the more it seems that even if i figure it out it wont be suitable for a shader thats supposed to run in real time (budget is around 150 sequential instructions with maximum of 4 at the same time so theoretically 600)
read 680 times 7/10/2012 2:25:30 AM (last edit: 7/10/2012 2:29:02 AM)

Garp 
Ok. I'll let you deal with the details of the formulas ;)
Say you have a triangle ABC. The cross product of vectors AB and AC gives a 3rd verctor, AH, perpendicular to ABC. If P is a point of the other triangle, the dot product of vectors AH and AP is zero when P is coplanar with ABC (and ABC are not aligned). Since all the points coordinates are functions of time t, you can define the functions A(t), B(t), C(t) and P(t) for the positions of these points. Then you can define a function (ABxAC)(t), and finally ((ABxAC).AP)(t). The potential collision times are the values of t for which that last function is null. This of course needs to be done for each point P of the 2nd triangle. Then for each of these t values, since P and ABC are coplanar, there exist two real numbers (barycentric coordinates) X and Y such that AP = X.AB + Y.AC. You need to determine those coordinates and check that 0 < X < 1, 0 < Y < 1 and 0 < X+Y < 1. If so, P is inside the triangle ABC. Use <= instead of < if you consider it a collision when P just 'touches' one of the edges.
The main problem is writing the function ((ABxAC).AP)(t). Considering the formulas you're starting from, it should be several lines long. Ideal to make countless errors. Then again, since you're not doing it by hand but using a programming language, you can break it into manageable chunks.
read 672 times 7/10/2012 2:49:35 AM (last edit: 7/10/2012 2:49:35 AM)

Mr_Stabby 
Great! Ill try and chew through that, for clarification though what exactly is P? just a random point? or a vertex?
read 663 times 7/10/2012 3:56:37 AM (last edit: 7/10/2012 3:56:37 AM)

Garp 
P is one of the three points of the second triangle. So you should have all the above x3.
The good part is that even though the formula for the ((ABxAC).AP)(t) function is gonna be quite long, it should be made of only basic operations: additions, subtractions and multiplications. The alogorithm for actually solving the equation ((ABxAC).AP)(t) = 0 might have to perform a few square roots though. But not sure. The whole thing could be really fast.
read 659 times 7/10/2012 4:06:30 AM (last edit: 7/10/2012 4:07:39 AM)

LionDebt 
Well thanks guys:
Mind = blown.
read 653 times 7/10/2012 4:14:25 AM (last edit: 7/10/2012 4:19:10 AM)

Garp 
Come on, LD. That's prehigh school geometry. Nice pic though :)
read 648 times 7/10/2012 4:20:56 AM (last edit: 7/10/2012 4:21:25 AM)

advancesoftware 
check out some books/papers on rigid body dynamics. they should cover all this stuff.
http://tinyurl.com/hottriangleaction
read 629 times 7/10/2012 9:10:02 AM (last edit: 7/10/2012 9:22:43 AM)


