View Full Version : Collision Detection

01-21-2003, 07:19 AM
I've made a bit of a hill but i can walk through it. The area around d hill is flat and i was able to avoid going through the ground by just keeping an eye on the height i was at:
if (height < 3)
height = 3;
But now i have a hill which complicates tings. I was lookin at a heap of collision detection tutorials on a bunch of sites but i find myself losing my sanity looking at them. The tutorials tell me to divide up the "world" into sections and test for collisions with these sections. So my question to you people is how do i divide up my world? the world is flat as a pancake besides this hill. the hill is the only ting i need to check for collisions. so i presume there's no point dividing the whole world up????? I also don't need to no much about the collision except that it has happened cos i want to just crash.
One reply i got was about a bounding box which includes the whole mountain. It doesn't seem like a great idea to me cos if i go within 100 feet of the hill, i'll crash in mid air! I want to avoid this method (unless i'm wrong about mid-air collisions??) so i need to find out how to split up the area around my hill and then check it for collisions.

Some code would be great if it's not too much to ask

01-21-2003, 07:36 AM
OOOHHH, I love collision detection, but there are somethigns i need to know before i can help. First, how many triangles are in that mountain. 3? 12? 10,000? Also, is the ENTIRE world flat besides this mountain? If so its realy easy, BUT it will generaly only work for this one case. If there are very few polys in the mountain, you can simply check every poly each time. Not too hard, i will walk you thought it. First you have to do what is called a point to plane distance. Basicaly the shortest distance from you to the plane the triangle is on. If that distance is negative, or less than a desired amount (like 5 feet, or whatever you think your width of the object your testing is) you test that point against the triangle itself. with a triangle face collision test. That is is. (Basicaly) but its alot of math. if you want to do this, let me know, i will work out all the math theory in a forum here. And you can pick what you need.

01-22-2003, 01:04 AM
What?? U love collision detection?? U are willing to go through torturous maths in order to help me??? What? Holy moley man! Are you nuts, lol. If you are serious, i'll take you up on your kind offer. The land is completly flat bar this hill/mountain in the middle of it. Not entirely sure at the moment how many polygons there is. I'll go find out.

You love collision detection! Hah, wonders will never cease!!!!

01-22-2003, 04:07 AM
landscape collision detection is really easy. look at my post in the advanced forum.

01-22-2003, 06:36 AM
Had a moment of inspiration(or stupidity depending on how good an idea it is). If i put a bounding box around my hill, and check if my position is inside this box, it will tell me if i'm in, over or around my mountain, yes???? If i then check my current height for every height property of the hill, and if i'm lower than the height of the hill, then i have collided yes???

01-22-2003, 09:33 AM
it sounds like you are doing an outdoor scene. is your terrain generated from a heightmap? or do you have some sort of underlying grid? break up your terrain into blocks or sections. have a function that can determine which section you are currently in, and you only have to do collision detection on the polys in that section. the smaller the sections are, the quicker the collision detection is, but it may take longer to find where you are. with really flat terrain, this can be done using brute force. with more detailed terrain you may want to think about using oct/quadtrees or ROAM.


01-22-2003, 10:17 AM

i have an outdoor terrain and i onyl have do to EIGHT operations for clipping.

you only have to clip one polygon. ONE !

01-22-2003, 10:24 AM
Yes i LOVE, collision detection, it is by far the trickiest thing to do and do QUICKLY ( I think any how ). Physics rocks. But in your case, I dont think i need to go into the whole math bit. You simply need a hight list. All you need to do, is figure out different hight at differnt points of you mountain, then depending where you are in your xyz planes, you can tell if you are too low for that point, if so, you push it up to that point, etc. I think that will work well in your case, since you dont need anything too fancy for A mountain. If you want something more let me know.

01-22-2003, 09:14 PM
There's a thing that I would like to know.
I have read Hamsters post on the advanced forum, and he's talking about interpolating the points between which the collision point is.
My question is about how precise this is. Is this an acceptable way of terrain detection for racing cars for example? Objects that are (almost) always in contact with the terrain.
Another thing, what is the formula for interpolating those points? What is exactly the method one uses? I have a vague idea of what interpolation is, but I'm not 100% sure.


01-22-2003, 09:59 PM
my method is 100% exact.
the idea is to have a heightmap, which the landscape is built from.
lets say you store it in array[x][y]
now, you draw the landscape :
for all x do
for all y do
drawquad(x,y -> x+1,y -> x+1,y+1 -> x,y+1)

now, opengl draws quads between 4 height points.
an because of the fact that this polygon is a part of a flat plane in 3d-space, you can calculate every point on it !exactly!.

a little math is necessary here...

i'll post an optimized formula later, (i got only a ****ed up totally mhz-and-ram-wasting code...)

ok, here is it :

you are at xf,yf.
your heightmap is array[x][y]

first, you need to know whats the nearest heightmap-point.
divide xf,yf by the x/y-size of your quads, ignore the numbers after the .
in my case, the quad's x and y-size is equal, and the length is one.

xhere = trunc(xf/xsize);
yhere = trunc(yf/ysize);

now you got two numbers, xhere and yhere.
this is the upper left heightpoint of the plane your are in.

now, you need the height-differences of 2 vectors :
v1 = array[xhere+1][yhere]-array[xhere][yhere];
v2 = array[xhere][yhere+1]-array[xhere][yhere];

if your quadsize is not 1, divide v1 and v2 by it.

then we need ne distance from xf,yf to xhere/yhere, which is easy to get.
xdist = xf-x;
ydist = yf-y;

now, the height of the landscape at xf,yf is exactly :

thats it.

[This message has been edited by HamsterofDeath (edited 01-23-2003).]

if you optimize the code you get , you'll get something like this :

public float getHeight(float x,float y)
int xhere=(int)(x/scaleFactor),
polyOrigin = xhere+yhere*mapSize;
float xdist = x-xhere,
ydist = y-yhere;
return interpolatedMap[polyOrigin]
+(x-xhere*scaleFactor)*((interpolatedMap[1+polyOrigin] -interpolatedMap[polyOrigin])/scaleFactor)
} catch (ArrayIndexOutOfBoundsException e) {return 0;}

[This message has been edited by HamsterofDeath (edited 01-23-2003).]

[This message has been edited by HamsterofDeath (edited 01-23-2003).]