# Collision with Ground (determining relevance in broad phase) [solved]

This topic is 4322 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, i read many of the collision articles and some of my questions were unanswered. Maybe someone could point where to look or give me some basic ideas on how to handle my problems, would be great. My question is how to check for collision with the ground. Test every triangle for intersection ? Split the ground into many single objects and then test ? How to exclude "irrelevant" triangles from testing ? With small objects i would save the middle of every object into a vector and set fixed distance when to add them into intersection test cycle. And start testing the bounding boxes or circles/ellipsoids for interscetion. thanks in advance flery can anyone suggest a book covering the basics aswell as new techniques of game programming (collision, enginestructures, leveleditorprogramming, texturing, raypicking, pathfinding, ai) that is up to date ? not too many math formulas and using pseudocode at best <= maybe too much for one book to ask for ? :/ [Edited by - flery on April 25, 2006 2:34:28 AM]

##### Share on other sites
Well, if you're using heightmapped terrain, then you can use linear interpolation to get your height (or an object's height, etc.) from the ground at the current position. I don't have the code right now, but I did this with a heightmap using Direct3D a year or two ago.

Try to find some more information about linear interpolation on heightmaps. I know this isn't ALL the information that you needed, but I hope it helps. =)

##### Share on other sites
thanks, but i thought more of a game like Mario64 or CounterStrike where the ground is more likly to be constructed "legostyle".

##### Share on other sites
Flery,

For books, you might want to look at the game programming gems series (1 through 6 ). It's a group of mostly well written article from different professional covering topics like general programming, AI, physics, Math and Audio. There's a few article on terrain creation. The articles aren't always in great details, but normally gives you plenty of references (often online) to go get the rest of the information.

When doing intersection with your ground, your normally have 2 triangle to test. In the case of a height map, you know which quads your falling within. You could do linear interpolation, or do a ray-triangle collision with a ray coming straight down from the sky to your ground at the specific x y coordinates that you are curently at. Try a search on this web site, the topic probably was already covered before also.

Cheers,

##### Share on other sites
i found one forum thread discussing my question but stopping at the interesting part (http://www.gamedev.net/community/forums/topic.asp?topic_id=261498&whichpage=1�). As for the hightmap iam thinking of a 3d jump'n run based ground collision. the basics of intersection are relativly clear. but i think with the ground which can be one very big object its sort of different ? You have more triangles to test against than with normal objects (which can be calculated easier with different tweaks like distance to object bounding boxes or radius). Now the question is, is my idea of one big ground wrong ? should it be splitted and then the distance to the single groundsplits be measured and taken for relevance.
i thought maybe you could calculate the volume of the bounding box of every object and the center of it than calculate some sort of factor depending on the volume and multiply it with distance between the player and the objects to determine the relevance.

thanks so far
flery

##### Share on other sites
First of all, is your terrain a regular heightmap, or just a plain mesh ? If its a heightmap, go to Graphics Programming forum, where I just described the technique in a thread named "Placing mesh over a terrain mesh".
Even if its just a plain mesh, same technique can be used provided you know the coordinates of the triangle over which you`re staying.

##### Share on other sites
Quote:
 1. Heightmap has a resolution of RxR vertices. Spacing between them is, say, 10.0f.

wouldnt that mean that we waste tons of triangles if there is a big plain area ?
(displayed in black)

[Edited by - flery on April 24, 2006 10:20:53 AM]

##### Share on other sites
Yes. There are other mesh techniques that don't have that problem, but are harder to do collision tests with. It's a tradeoff like so much of programming!

##### Share on other sites
For detail collision (objects spread over terrain) on a terrain
you may have to build a AABB tree (or a quad tree which I see it
inappropriate unless the height of the terrain is almost as big as
one of the terrain dimensions). Detail models then are linked
to the leafs. Then the whole collision detection is reduced
to a couple of AABB-tree-terrain-nodes bounding boxes up you reach the
current leaf. On the current leaf you collide as you wish with a reduced
set of objects (the ones belong to this leaf).
If you like some code I can paste it here for you.

##### Share on other sites
thanks marius..
but i still have problems getting this thing with the fixed grid size. for example if i wanted something very edgy and not as smooth as posted in the image before i couldnt do it. something like that:

but i got another idea maybe i could take grid over the whole map and check which objects is in which gridsegments to decide relevance but still this wont fix my ground problem. (like marius mentioned but not using the actual ground but a notional grid)

maybe i should really split the ground into segments and calculate the associated gridunit(s). which could make texture transition a bit problematic?

##### Share on other sites
SA BSP tree anybody?

##### Share on other sites
What I did for Bouncy Hunters was just to build an octree for the whole level. Then collision detection was a matter of testing all octants the moving object crossed through for each particular movement. Then within each octant, the collision detection was bounding sphere vs the triangles in the octant.

If you don't want to use the same tree structure for your visibility culling as for your collision detection it might make sense to keep two copies of the world: one subdivided for collision detection and one subdivided for visibility testing. It'll use up more memory but most players will make the tradeoff between loading times and in game speed.

##### Share on other sites
Quote:
 Original post by fleryMy question is how to check for collision with the ground. Test every triangle for intersection ? Split the ground into many single objects and then test ? How to exclude "irrelevant" triangles from testing ?
Collision detection can be divided into two phases: a broad phase and a narrow phase.

During the broad phase you determine which objects or part of are close enough to each other that they may be in collision with each other (and discards from collision those who are not). The narrow phase then takes the objects or parts which may be in collision and performs more detailed collision on these, such as triangle vs. triangle tests.

Your question is on the broad phase part. For that the basic idea is to use some sort of spatial partitioning scheme to group together objects that are "nearby" (for some definition of nearby) and to be able to exclude objects that are too far away to be able to collide with your query object.

For example, consider overlaying the world with a uniform grid and associate your ground geometry with the grid cells the ground geometry comes in contact with. Now, to test an object against the ground you check to see which grid cells your object overlaps, then you pass the contents of those cells to the narrow phase. No other ground geometry needs to be collision tested.

There are many different spatial partitioning schemes: grids (both hierarchical and nonhierarchical), trees (octrees, quadtrees, BSP, k-d, etc). You can also divide your ground geometry up into pieces and then form a bounding volume hierarchy around it and then recursively perform tests against this hierarchy (visiting only the parts of the tree that your query object overlaps). And more.

I would suggest starting with something simple, like a uniform grid. Then you can try other methods to see if they perform any better on your particular problem (which isn't necessarily the case).

If you want more detailed advice, you would have to provide much more detailed information about what your ground looks like, how it is represented, what type of collision queries you want to perform against it, how the colliding objects are represented, etc. Basically, there are tons of things that affect what is an appropriate method so, well, don't worry and just pick one.

##### Share on other sites
thanks to all
great help especially Christer Ericson for pointing out my problem, showing up the different ways and easing my decision.

[problem solved]
=)

as for the way the ground will look like, if you played mario 64 (great 3d jump'n run btw) thats the levellook/ground i am going for.

flery