Well, this is not about the basics of tri-tri intersection (as I''ve found docs on that) but comes a tad nearer to the implementation of collision detection based on this. That''s why I have no idea where to put this damn thread. It''s prolly a lot of maths involved, but is quite near to game programming too. Anyway, what I''m wondering about is a fast way to translate a whole set of polygons in such a way that they are represented to the worlds axis system. I mean, when I go calculate the intersection of two polygons their coordinates have to be represented in the same axis system. My data representation is relative to each objects own axis-system. So basically, I have a big object, consisting out of a set of polygons. When I draw it I can rotate the entire axis system an Xr degrees and draw it in it''s local coordinates. I can also move the entire axis system an Xt units. So, that''s where I''m stuck... I have to translate my relative coordinates to world-coordinates so I can do tri-tri intersection of them. Ofcourse I know on before hand how much I rotated/translated my object in the first place What basically worries me the most is the expense of these calculations. It''s rather speed critical. Another problem is that I''m momentarilly brushing up my maths. I have been a trigonometry-phobic for a long time, but now I found a new hobby in 3D development I''m seriously working on my maths. So please, can you keep it easy so I can understand each step? Thank you! ______________________________ If idiots could fly, I would be a space-shuttle.

I use the term BCS for body coordinate system (the relative one)
I use the term WCS for world coordinate system

You're right. You have two objects which you want to test for intersection, and assuming the first contains N triangles and the latter M triangles. The "easiest" way of doing the test might be, for example (in C code):


for( i=0; i{
Triangle t1 = object1.triangle;<br> t1 = object1.FromBCSToWCS( t1 );<br> for( j=0; j<M; j++ )<br> {<br> Triangle t2 = object2.triangle[j];<br> t2 = object2.FromBCSToWCS( t2 );<br> CheckForIntersection( t1,t2 );<br> }<br>}<br> </i> <br><br>This gives N*M transformation operations. &#79;ne simple idea would be to make temporary objects out of each object &#111;n each frame, which contain the transformed coordinates. This gives &#111;nly N+M transformations. If you don't want to add the complexity involved with creating temporary objects, you can use a more clever method, too: transform the first object to WCS, and from WCS, transform it to the BCS of the second object. Now both of the objects are in the BCS of the second object. See the pseudocode:<br><br>for( i=0; i<N; i++ )<br>{<br> Triangle t1 = object1.triangle<i>;<br> t1 = object1.FromBCSToWCS( t1 );<br> t1 = object2.FromWCSToBCS( t1 );<br> for( j=0; j<M; j++ )<br> {<br> Triangle t2 = object2.triangle[j];<br> // see? no transformation done in the inner loop<br> CheckForIntersection( t1,t2 );<br> }<br>}<br><br>This is "pretty" much just N+M. A tad bit slower than creating temporary objects. The problem of constructing the functions FromBCSToWCS, FromWCSToBCS and CheckForIntersection is left as an exercise for the reader <img src="smile.gif" width=15 height=15 align=middle> Or you can as well ask more questions &#111;n the forum…<br><br> - Mikko Kauppila </i> <br><br><SPAN CLASS=editedby>[edited by - uutee &#111;n December 13, 2002 10:32:35 AM]</SPAN>

Thank you...

I think I''ll stick to the "ask more questions" option tho.

I''m quite new to the concept of the maths involved in 3D programming, so I''ll just post how I think I''d do the BCS to WCS translation. I hope any of you can correct it or tell if I''m getting near. This way I''ll learn this better and will keep me from comming to these forums for every fart
("oefening baart kunst" we say in Holland)

OK, since every point of the object is rotated with the same angle I think I can do the sine/cosine calculations once. That will give me a good speedup.
OK, so if I had a rotation, in the X/Y plane of 45 degrees. I have this nice book with matrix transformations, so I''ll use this.
The Z position of every point would be unchanged (let''s keep this easy, mmkay ). I can find that in my matrix by a ''1''.

Right, next step is to calculate the COS and SIN of -45 degrees. Do this once to speed things up. We take -45 because we want to cancel out the old rotation.
COS(-45) = ~0.707
SIN(-45) = ~-0.707

Next we translate points... we loop through our vectors and calc the new positions.
NewX = x*COS(-45) - y*SIN(-45)
NewY = x*SIN(-45) - y*COS(-45)
NewZ = z


Next we take translation into account, which basically is WCS_OBJECT_CENTRE + BCS_VERTEX_POSITION

One thing that bugs me why I use both the sine and cosine when, for example, I recalculate the x. I mean, when I draw it out on paper (2D) I ONLY need the sine to get the matrix multiplication for the newX.
If I have a point on 0,2 (to keep things simple) and wish to rotate it 30 degrees, the newX would be (the way I would do it) y*SIN(30)... where does the COS(30) fit in?
Also, if I placed 0,2 in the matrix formula I''d get a negative value, while the position is positive. No?




Well, it took me an hour to make this post, but the more I think about it the more things start bugging me. I hope someone can clear a few things up. I''m trying to understand every little bit (I hate copy-paste work).

______________________________
If idiots could fly, I would be a space-shuttle.