"Now get all terrain triangles between those two points. " This is really where the complexity comes in, right? There needs to be some kind of spatial hierarchy to get the triangles.
Well, you can pre-sort the triangles in a 2d array like structure on the xz-plane (in dx, that is, xy in opengl if I'm not confused; its as if you where looking from above). Then you simply take the min-point as the index of the first triangle, and iteratively add +1 on both the x and z axis until you are at the max point, adding each triangle at the next point to the potential collision list. Whereas 1 is the density of your terrain, if its more dense you need more steps, though I quess you'd want to use a less dense approximation, seeing how the graphical representation of a terrain can get quite complicated in the nearest LOD. Does it appear more clear now?