#141164 - DiscoStew - Sat Sep 22, 2007 8:32 pm
Could anyone direct me to some resources for 3D collision, and perhaps some examples of the different methods?
So far, I've only done sphere/sphere collision, but that doesn't include time-based if the two spheres go through each other without actually hitting from one frame to the next. What I am wanting to do is a collision sphere and/or cube based attribute against an environment. Basically, model vs level collision, like a model in a room, on terrain, etc.
_________________
DS - It's all about DiscoStew
#141165 - Mighty Max - Sat Sep 22, 2007 8:50 pm
Model vs Level collisions are usually done using BSP trees.
They partition the whole space into parts that can be attributed with "solid" or passable. Also methods to find the nearest polygon intersected with a given vector+origin are well documented on the net.
They are average at log(n) costs against the number of polygons in the level.
_________________
GBAMP Multiboot
#141173 - sajiimori - Sat Sep 22, 2007 10:56 pm
BSP is so flippin fast compared to all other methods I've seen that I have to recommend it for DS development.
These were the resources I used:
"Collision Detection In Interactive 3D Environments" by Gino Van Den Bergen. Great intuitive introduction, but most of the book is geared toward collisions between arbitrary convex shapes using GJK. The BSP section is less than 20 pages.
"Real-Time Collision Detection" by Christer Ericson. More details about how to build the tree.
http://www.faqs.org/faqs/graphics/bsptree-faq/. I grabbed the Split_Polygon function from here.
Quake 1 source. Doesn't use dynamic plane shifting, but it's not hard to add. Uses native C recursion in the engine, whereas recursion using a hand-made stack offers much better optimization opportunities.
#141186 - M3d10n - Sun Sep 23, 2007 2:17 am
There is a difference between testing collision and intersection. You might find tons of intersection tutorials on the net, but they usually don't solve collision problems.
Search for "sweep colision test" and "axis separation theorem" on google. There are some excellent gamasutra and gamedev.net articles on it.
Sweep collision tests take in account the object's travel path, so you can avoid the classic "pass through objects when fast enough" problems which arise when you use plain intersection tests. The axis separation theorem is used to find how much a convex is intersecting another, allowing you to properly correct their positions (thrown in mass and you can easily have objects pushing each other).
#141189 - sajiimori - Sun Sep 23, 2007 2:40 am
That reminds me: cheap swept collisions are another reason BSP kicks ass. The cost is not much greater than an intersection test. It's still nice to have both algorithms on hand so you can use the cheapest one applicable to each situation.
#141196 - DiscoStew - Sun Sep 23, 2007 3:41 am
To be quite honest everyone, all this talk of BSP trees and intersecting convexes is really turning my brain into mush. I can't get my head around it, as I feel even that stuff is a bit advanced for me, as it involves more than the actual subject of those topics, of which I know nothing about.
What I need is to start from page 1, and progress from there. That is basically my knowledge on 3D collision....that I have no knowledge on the subject, other than finding if two spheres are intersecting. I just have no idea on where to start.
_________________
DS - It's all about DiscoStew
#141218 - HyperHacker - Sun Sep 23, 2007 8:01 am
Warning: Heavy math ahead. >_>
_________________
I'm a PSP hacker now, but I still <3 DS.
#141225 - zeruda - Sun Sep 23, 2007 8:59 am
You know sphere/sphere collision which can be useful.
You should also learn Axis aligned box/box collision which is simple. Basically if the minimum x value of box1 is more than the maximum value of box 2 then there is no chance of a collision and do the same for all the other min and max axes.
You'll also probably need to look at sphere/polygon or sphere/triangle intersection routines which'll check against the exact polygons for collisions for more accuracy.
Now, checking against a level there's a second issue in addition to checking if there is a collision; speed. If you're level has 10,000 polygons you certainly don't want to check against every single one of them every frame. Too slow. So what you have to do is group bunches of polygons together somehow be that an octree or quadtree of bsp or some other method. Then you do a single check against the group, then with 1 check you can eliminate 100 polygons. With Octrees conceptually you're basically putting boxes around each group of polygons, and then do a box box test with the character against the group.
By doing this with a 100 box box checks or less you'd narrow down the number of polygons to less than a 1000, maybe only a couple hundred or less even. Then you can put a box around each of those individual couple hundred polygons and do a box box test(which is lightning fast) and narrow it down even more. Finally you do a sphere/polygon test(which is very slow but accurate) for final results.
Hope that all makes sense
#141226 - nce - Sun Sep 23, 2007 9:06 am
You have to thing about what you want exactly....
If your character is just walking or running, thing if it's not possible to just do your collison in 2D....
What I usualy do for a character in a scene, is to modelise a collision mesh on the ground, the caracter can walk only on that mesh and will snap on it.
It's realy fast ( only some dot product ) and easy to implement.
If it's that kind of thing you are looking for... tell me and I can post a more precise explanation of this...
_________________
-jerome-
#141227 - simonjhall - Sun Sep 23, 2007 9:58 am
| HyperHacker wrote: |
| Warning: Heavy math ahead. >_> |
...pretty much sums up what I was thinking! The little BSP monsters out there have a voodoo doll with my name on it, and are sticking pins in it every day.
_________________
Big thanks to everyone who donated for Quake2
#141341 - a128 - Mon Sep 24, 2007 9:00 am
| zeruda wrote: |
You'll also probably need to look at sphere/polygon or sphere/triangle intersection routines which'll check against the exact polygons for collisions for more accuracy.
|
While using 20:12 Fixpoint in those methods..you will get overflows in multiplications quite soon
#141368 - sajiimori - Mon Sep 24, 2007 7:14 pm
Anything that involves heavy math is probably not appropriate for the DS. ;) For instance, I'd recommend not doing any tests versus polygons. Poly tests are slow as hell.
The math for BSP is not hard. All you need to know is the dot product. Find a graphical representation of what the dot product means, and you're set. BSP still takes some time to grasp because of the conceptual difficulty, but you need nothing beyond high school math.
The books I mentioned are excellent for starting from scratch, especially the orange one by Ericson.
#141467 - HyperHacker - Tue Sep 25, 2007 10:46 pm
| nce wrote: |
You have to thing about what you want exactly....
If your character is just walking or running, thing if it's not possible to just do your collison in 2D....
What I usualy do for a character in a scene, is to modelise a collision mesh on the ground, the caracter can walk only on that mesh and will snap on it.
It's realy fast ( only some dot product ) and easy to implement.
If it's that kind of thing you are looking for... tell me and I can post a more precise explanation of this... |
Once you have it down to 2D collision detection, you can speed it up by using a grid or bitmap test. Make a 2D grid the same size as your level, in units the character can move in. (That is, if you can move a pixel at a time, your grid is the size of the level in pixels. If you can move 16 pixels at a time, it's the size of the level divided by 16.) Determining what your character is touching is a simple matter of filling in the grid with information about the surfaces under it, and then determining what cell your character is in. It can help to think of the grid as a bitmap, where one colour means solid, one means passable, maybe one means touching it hurts you, etc. For example, you can tell if your character is on a collision course with something the same way you would draw a line on a bitmap, starting at the character and moving outward in his direction of travel. Except you don't modify the pixels, you just see if any are solid. You can even count them to see how long until the collision will occur.
In debug mode, you can also render the grid as an actual bitmap (overlayed on or in place of the level), to see what's what.
If your game is using 16-bit bitmaps and the camera can't be rotated, you don't even need a grid. You could simply use the lowest bit of the red, green or blue value as a solidity flag. I doubt anyone would notice the difference. You could do this with a palleted image too, but you'd need to cut the number of colours in the palette in half, as every pair of colours would need to be the same. (Of course, you could make them different for debugging.)
Of course you can do a 3D grid too, but usually in 3D games you move in very fine increments, so it'd take up a busload of memory. >_>
Pok?mon G/S use this method BTW. The levels are made up of 32x32 tiles, and the characters can move in 16x16 units. Each tileset has a tile attribute table, which has 4 entries per tile (top left, top right etc) that tell how to react when a character tries to move onto it. On every movement the tile number you're standing on is used as an index into the table. When you do it this way, you don't even really need to generate a grid, you can use the tilemap your level is already made of.
[edit] Rewritten to be less confusing.
_________________
I'm a PSP hacker now, but I still <3 DS.