Are you looking to actually calculate the outline of the shadow on the terrain? There are better ways to do shadows for rendering that don''t explicitly require the the line intersection you''re talking about. The two most prominent methods for rendering shadows are stencil shadow volumes and shadow maps. See nVidia''s developer site for details:

http://developer.nvidia.com/view.asp?IO=docs_shadows

They even have code samples. And there are techniques to do shadow volumes using vertex shaders.

If you''re wanting to do line-of-site (LOS) checks for visibility, e.g., to see if an object is in the shadow of a hill (for example) and so cannot be seen by an observer on the opposite side of the hill, then you will have to do some line intersections in some manner. Brute force method says check the line against every terrain triangle that overlaps the line in the x, y directions. You could also use a technique called the "depth estimation buffer," which is often used for image-based occlusion culling. This would provide an approximation of whether the object behind a hill is in shadow. A google search should bring up some very academic papers on that subject.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

It depends on what you call brute force, but there it no reason to use brute force as in check all squares. You can fairly easily calculate which squares the line runs through as well as the height that you enter and exit each square. With each grid there is actually only one line you have to go under on a vertical plane to collide with the terrain. It might be faster just to check for collision with the two triangles in that square though.