Ray-Triangle intersection optimization advice from barque

barque on ##OpenGL on Freenode gave me some very good advice on ray-triangle hit testing. I thought I'd paste them here for everyone's sake:

<barque> Now
<barque> a few suggestions
<barque> is this vs. static mesh?
<jubei> barque: eer.. it's a static mesh yes
<barque> ok then transform once and leave it
<barque> cache your results
<barque> static as in pure static
<barque> no translation nothing
<jubei> ofc not it has a rotation and translation on it
<barque> because for example
<barque> ok
<jubei> to bring it to world coords
<barque> so here's some advice
<barque> because I've been doing this for a long time
<barque> and back when I was at your stage
<barque> I wish someone had told me this stuff
<barque> wasted hours learning the hard way :)
<barque> so if you have a 'rigid body' type thing
<barque> transform indexed non-duplicate vertices , transform their indexed non-duplicate normals using the inverse transpose of the normalize (and don't forget to re-normalize)
<barque> and then use indexing to catch your world space coords and normals
<barque> indexing saves you a ton of transformation computations
<barque> both on normals and on vertices
<barque> e.g.
<barque> you do only 8 transformations for a 6 face cube
<barque> 8 corners
<barque> and at most you transform 6 normals
<barque> this makes a lot more sense when you have large rigid bodies
<barque> make sure whatever math engine you're using is using SSE4 or something newer (VMX although it's not backwards compat)
<barque> :)
<jubei> barque: I'm currently trying this on a 6 face cube, and I have indexed the vertices. But I have no normals, I don't need normals for hit testing, the hit testing algorithm finds the normals from the vertices I think
<barque> (*e.g. VMX)
<barque> Jubei, aha, bad move
<barque> too many calculations
<barque> you can save a lot of pointless cross products just caching stuff
<jubei> barque, i get what you're saying but yea.. let me get this working first then I can optimize it :)
<jubei> good advice though, thanks
<barque> no probs :D
<barque> think about it
<barque> if you have 12 triangles on a cube (let's say your asuming everything as polygonal soups)
<barque> you're doing 12 pointless cross products and normalizations
<barque> besides you won't even know if those normals are pointing in the right direction
<barque> while you could do only 6 transformations and normalizations and be done with it
* Jubei nods
<barque> oh btw Jubei
<barque> if you're doing ray triangle intersections you could use side normals to speed up your point-in-borders test
<barque> and you could index those side normals along with your face normals :D
<jubei> never even heard of side normals^^
<barque> hah
<barque> it's someting I came up with
<barque> ray triangle intersections are a 2 stage process:
<barque> 1. you find your point on the triangle plane
<barque> 2. you see if the point lies in between the 3 lines
<jubei> so your "side normals" help with the 2nd part then
<barque> for the 2nd stage, you can think of those lines forming 3 perpendicular planes to the triangle plane, facing away from inside the triangle
<barque> yep
<barque> if the point is behind all 3 of those
<barque> it's inside the borders
<barque> and yep, you can cache and index those
<barque> and transform them once in your transformation phase
<barque> like normals etc.
<jubei> ah ic
<barque> otherwise you'll have to do some nasty arc cos nonsense
<barque> or cacluate them everytime
<barque> both of which waste time
* Jubei saves log for future reference^^
<barque> hah, I never thought I'd say this stuff on the Internet
<barque> but here I am
<barque> yeah make good use of it
<barque> if you come across hardware skinning and stuff in the future
<barque> hit me up if I'm around
<barque> I've got plenty to spew regarding those
<barque> and parametric animations
<barque> and CryEngine3 type goodies