Line of Sight over a 3D terrain map

How might I give a line of sight to an object that can move? I am working on a 3D map made up of quads between a total of 10000 points (100 by 100), and each point has its own x, y, and z coordinate.
Please help,


Do you want to calculate the angle to the object or test if its visible? Search the net for collision detecting. The code will be faster if your data has a hierarchial structure so that big parts can be culled.

You call it a 3d landscape, but then specify the # of polygons to be 10000 (100x100)
I’m guessing you’re using a heightmap.

The quick way to check if two points can see each other across a height map is to use some sort of line algorithm to step across the heightmap.
What I’d do is find the vector (p2(x,y,z) - p1(x,y,z)) between the two points. Find whether the change in x (we’ll call it dx) or y (dy) is greater abs(dx) or abs(dy)
(pseudo/vb code)

canSeeOtherPoint = true
if abs(dx)>abs(dy) then
x=int(p1.x)+Sgn(dx)'setup the first step
for x = int(p1.x)+Sgn(dx) to int(p2.x)
if z<LandscapeArray(int(x),int(y)) then
canSeeOtherPoint = false
z=z+dz 'add dz in respect to dx to z
y=y+dy/dx 'we’re adding dy in respect to dx
x=x+sgn(dx) 'step to the next x position
loop until (sgn(dx)<0 and x<p2.x) or (sgn(dx)>0 and x>p2.x) or canSeeOtherPoint == false

And you’d do a similar set of stuff if the primary axis was Y instead of X
btw, x,y, and z are all floating point values
if canSeeOtherPoint is true, then… the points can see each other…

Btw, this is just an approimation, you’d really want to do some linear calculations to check for intersection of the triangles in case the guy was just barely covered up.

A better approximation would probably to do a linear interpolation along the non-primary axis at each height check, based upon the fractional value of the non-primary axis (so, x, if it were the primary, would always be an integer (ie, no interpolation), but you’d pass y as a float and average the two points nearest to y (int(y) and int(y)+1) based upon their distance from y:

height = (Landscape(x,int(y))(1-(y-int(y))+Landscape(x,int(y)+1)(y-int(y))

something like that…

If this isn’t what you’re wanting… umm, I’ll delete my post or something,

[This message has been edited by Thr33d (edited 10-31-2003).]

By the way, I was using X and Y as the axis if you were looking down on the heightmap as an image. Z would be altitude in the example.

Here’s a picture of what it sounds like you’re trying to do, the red is an example of how you might write the above method to do the checking (except it would break early if they couldn’t see each other.

(Yeah, I drew the red in by hand… it should probably be following a slightly different path. You get the picture though.

[This message has been edited by Thr33d (edited 10-31-2003).]