Fast checking if a line segment is going through a triangle?

I've been working on a physics engine (I posted alot about it at the "Mod to Miracles Verlet Physics" in the Advanced 3d forums). Anyway, I just redid the whole system with a much better foundation, and decided that Blitz collisions can't do what I want as far as collisions go.

Basically, all I need is a line segment to triangle collision checker that returns some extra info. It needs to be extremly fast, as it would be run 100s of times every frame. I have no idea how to check if a line segment is going through a triangle, other than linepick, but sadly, linepick is a little slow for my purposes.

Anyway, I know this is a fairly demanding list of features, but it's what the system needs.

1)Whether or not the line goes through the triangle
2)The closest place on the triangle to the 2nd point of the line segment
3)The point at which the line intersects the triangle
4)Fast, Fast, Fast! If you can sacrafice a little bit of accuracy for a ton of speed, do it!

Please tell me if anyone has a way to achieve one of these or, hopefully all of them. I'll be posting this same post on blitzcoder, so hopefully I'll get a good solution.

Thanks for any useful Reply!

I'd say use linepick but before you do reset the pick mode of entities outside of some arbitrary range to 0. This way you're only picking from a few polys.

hmm, I actually hadn't thought of re-setting pickmode, but It's still quite a bit slower than a mathamatical method. I think that linepick goes through the line incrementally, as the picktime is higher proportional to the distance to the entity.

It is a strategy I'll have to use if no other method is thought of.

Thanks for the quick response!

I haven't noticed linepicks being slower relative to distance, only to number of triagles being picked from.

; CameraPick Example
; ------------------

Graphics3D 640,480,0,2
SetBuffer BackBuffer()

camera=CreateCamera()
PositionEntity camera,0,2,-10

light=CreateLight()
RotateEntity light,90,0,0

plane=CreatePlane()
EntityPickMode plane,2 ; Make the plane entity 'pickable'. Use pick_geometry  mode no.2 for polygon collision.
ground_tex=LoadTexture("media/Chorme-2.bmp")
EntityTexture plane,ground_tex

cube=CreateCube()
EntityPickMode cube,2 ; Make the cube entity 'pickable'. Use pick_geometry mode  no.2 for polygon collision.
cube_tex=LoadTexture("media/b3dlogo.jpg")
EntityTexture cube,cube_tex
PositionEntity cube,0,1,0

lprep1=CreateSphere()
EntityColor lprep1,0,255,0
ScaleEntity lprep1,.2,.2,.2

lprep2=CreateSphere()
EntityColor lprep2,255,0,0
ScaleEntity lprep2,.1,.1,.1

cur#=1
a#=1
While Not KeyDown( 1 )

If KeyDown( 205 )=True Then TurnEntity camera,0,-1,0
If KeyDown( 203 )=True Then TurnEntity camera,0,1,0
If KeyDown( 208 )=True Then MoveEntity camera,0,0,-0.05
If KeyDown( 200 )=True Then MoveEntity camera,0,0,0.05

; If left mouse button hit then use CameraPick with mouse coordinates
; In this example, only three things can be picked: the plane, the cube, or  nothing
;If MouseHit(1)=True Then CameraPick(camera,MouseX(),MouseY())


a#=a+.01
LinePick 0,.5,-a,0,.5,a
PositionEntity lprep1,0,.5,-a
PositionEntity lprep2,PickedX(),PickedY(),PickedZ()

RenderWorld

Text 0,0,"Use cursor keys to move about"
Text 0,20,"Press left mouse button to use CameraPick with mouse coordinates"
Text 0,40,"PickedX: "+PickedX#()
Text 0,60,"PickedY: "+PickedY#()
Text 0,80,"PickedZ: "+PickedZ#()
Text 0,100,"PickedNX: "+PickedNX#()
Text 0,120,"PickedNY: "+PickedNY#()
Text 0,140,"PickedNZ: "+PickedNZ#()
Text 0,160,"PickedTime: "+PickedTime#()
Text 0,180,"PickedEntity: "+PickedEntity()
Text 0,200,"PickedSurface: "+PickedSurface()
Text 0,220,"PickedTriangle: "+PickedTriangle()
Text 0,240,"Distance: "+a

Flip

I did actually confuse linepick and camerapick as far as the speed thing goes. camerapick has a large slowdown at high distance, yet linepick still has distance-related speed problems. In the code, the green sphere is the first point of the linepick, and the red one is the point picked. Anyway, I'm trying to make speed-demon code for physics, that I've decided to have a minimum of 32 fps. This means 31.25 milliseconds between each frame. A basic cube runs at 2.5 m., although the complexity-speed ratio doesn't work. What I mean is that somthing twice as complicated as the cube would run less than 5. Maybe 3 or 4. Anyway, my point is that since each linepick takes ~1 millisecond, I would have a limit of 27 linepicks, disregarding rendering! In addition to that, I would have to write algorithms to get other values, so it would be even slower. Another thing is that it's actually quite hard to only pick certain triangles. If I could pick single triangles, I could write a bounding box culling method that would speed it all up signifigantly.

I hope you realise that the docs are a tad misleading regarding Pickedtime().