🔒 Locked

intersection line & surface, drawing terrain

Started by AndyMan Aug 8, 2001 at 8:29 PM 5 replies 2.1k views

Original Post

Aug 8, 2001 at 8:29 PM

Suppose we have an area of land, with height of each grid point stored in an array. You can write a function which calculates height at any x,y by interpolating. When you choose a camera angle you can create a matrix which will convert x,y,h(x,y) into screen coordinates. But is there a simple way to convert back the other way? Suppose you want to iterate through the whole screen and calculate the x,y,z using the matrix and the height function, so you can choose a colour for the pixel (based on a tilemap of x,y or height or slope or whatever). You can assume a continuous surface, although there may be steep slopes. This is essentially a mathematical problem - find the (first) intersection between a line and a surface. Point me to another thread or article if necessary, I imagine a lot of people have had to work this out before me.

danz

Aug 13, 2001 at 3:13 PM

it''s very simple

to find and intersection point of a ray (line) and a plane you have to do this :

lets consider a ray : X=A+t*V
where X is any point on the ray , t is a scalar and V is the direction vector of the ray.

now , lets consider a plane : X dot N + D=0
where X is any point on the plane, N is the normal to the plane and D is a scalar unique to the plane

all we have to do is find a point Xi that fits both eqations :
Xi dot N+D=0 , but Xi=A+t*V , so :
(A+t*V) dot N +D=0
A dot N + t*V dot N +D =0
t=-(D+A dot N)/(V dot N )

back to the first equation , replace t and there you go , the intersection point !!!

AndyMan

Aug 14, 2001 at 12:58 AM

You gave a solution for a ray and a flat plane. I was talking about a surface described by a 2D array of height values.

I looked around for stuff about raytracing and most of it is about intersections of lines with geometric shapes, which gives you a mathematical solution. But looking at a height map is one which probably requires some iterative method to zoom in on the right point. Any ideas?

Shannon Barber

Aug 14, 2001 at 1:25 AM

You want to perform collision dection with a ray and the world, it''s called "picking".

You need a tree structure which you use to perform culling, so that you don''t have to test the ray against every polygon in the world - I think you can use a quadtree or bsp tree for terrain.

I wouldn''t know how to explain the math, it''s a little involved, not too hard but lots of vectors and a few matrices, which are hard to show in ascii...

Magmai Kai Holmlor
- Not For Rent

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.