Topic awaiting preservation: Collision Detection

After way too long away from...well, any kind of scripting in general, I decided the other day to actually implement a collision detection script. This is actually in preparation for something I was going to write for the Nintendo DS. However, being most conversant with javascript, I thought I might implement it in that first. In this case, I'm referring to full 3d objects all made of rigid triangles, with no points of rotation - simplistic I know, but mostly I was wondering about speed. I mean, the calculations aren't that hard - it all comes down to fairly simple vector calculations. Using bounding boxes, I wonder if it could be made to work at a reasonable speed with, say, a dozen polygons? Perhaps I could use a pre-rendered background in which a tetrahedron can move?

Well, anyway, I was just looking for any input anyone might have....whether it's possible/interesting etc...

Wrayal

(btw, I basically have triangle/triangle collision calculateed - now the hard bit - the reactions :\)

EDIT:One other little thing - I was wondering if anybody could point me to any info about that technique I used to see around on javascript-games.org that was used to rotate images?



(Edited by wrayal on 12-30-2005 15:14)

Gotta go- but check this out..

http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30
http://www.flipcode.com/articles/article_basiccollisions.shtml
http://www.flipcode.com/articles/tp_issue01.shtml
http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=64047

-- Petskull --

I have to say, a tad ambitiously I decided on my own method for checking these intersections, which doesn't seem to be the same as the commonly accepted ways using arbitrary intermediate planes. My system was this:

1) Find the direction of th line where the planes of the two polygons would intersect if they were infinite planes (cross product of the normals of the two planes)
2) Produce the complete equation for the line by finding an arbitrary point on that line
3) Check if at any point that line lay within both polygons, if so, there is a collision.

This may well be analagous to one of the common methods, and I'm just misunderstanding. Or is my way just incredibly slow or something? I don't think it woud be - it only requires a single cross product, a little bit of calculation then some max()/min()'s

Wrayal

Honestly, I don't have a clue. But bounding boxes or a naive approach, or any approach for that matter, would be "possible" to use on a small amount of vertices imho.
It boils down to a couple of matrix mults, which is not much. Am not aware of the current limits of js though, but it should handle it.

What I find to be a pain in the ass using c++ is memory management, so I'd go for a direct Nintendo DS implementation. My 2 cents.

yeah, it's possible using matrices certainly, though I was going to avoid those, at least at first (though in some ways they become one and the same thing). The performance isn't so important in javascript - more, I kinda wana check my methods and my maths, see if it's all going to work, even if it ends up being fairly slow, it'd be a fun tech demo. I know for many it would be best to go straight for C++, but I don't feel confident enough with C++ to take on the programming and the new maths at the same time - debugging would be hell!!

Wrayal

That's not exactly what I was saying.
So le'ts rephrase - naive algorithm = the straightforward algorithm that goes through all polygons in a scene and checks it against all others. Can be quite fast for small amounts of vertices methinks, and easy to implement given the code you already have.
Matrix maths - this wasn't to say that you "have" to use matrices, matrices are just a data structure. This was merely to represent the mathematical complexity of the algorithm,
equivalent to "n" mults, equivalent to some basic matrix mults.

And C++, yeah, I understand.

Anyway.
Given this is in js, I guess the "screen" resolution will be low, so I am afraid bounding boxes or spheres for that matter, will give an ugly result if used alone.
So, if the triangle per triangle approach turns out to be too heavy for the whole, what do we have left?

A combination, possibly.

You could use, as this is common, space partitionning (a simple grid) to quickly sort out objects that cannot colide at a given time.
You could use bounding box detection, or bounding spheres (easier), and when two objects collide at bounding box level, turn to some more detailed technique.

You will also like the Minkowsi difference, which could be handy to you and could offer another, possibly comprehensive solution.
"Sweep and prune" could be another one.

So? If I was you, I'd opt for:
1) Some bounding box or space-partitionning based "first pass" to leave out objects that should not be included in the deep collision test
2) Naive triangle/triangle collisions or a Minkowski, or Sweep and Prune, based algorithm to get into the details
3) If using the Minkowski difference, you'll already have an insight as to "how much of the volumes actually collides", which sets the base for collision reaction

That would be my roadmap if I had to implement collision detection in js.
Now let's have a look at the "other pros" advice, Petskull posted a couple of links I haven't checked..

Hmmm, I'll even give those links a quick review:
http://nehe.gamedev.net/data/lessons/lesson.asp?lesson=30 <-- only works for basic solids, planes and spheres. Covers the "bounding boxes" or "bounding spheres" part of the above.
In addition to being limited to spheres and planes, this just doesn't say how much of a sphere intersects another and which forces should be applied to have them bounce back realistically.

Same goes here: http://www.flipcode.com/articles/article_basiccollisions.shtml
It focuses on ray-plane intersection. This is suitable for a first/third person shooter, because it's easy to sum it up to one player-to-target ray, or a bunch of rays, and even then, the author
suggests some space partitionning. Actually, at the end of the article, the author suggests bounding boxes instead of his "my player is a spot" approximation, AND space partitionning.

That one is a lot more interesting, and a bit above my head actually, I have to re-read it a couple of times:
http://www.flipcode.com/articles/tp_issue01.shtml

That one is correct, too: http://www.flipcode.com/cgi-bin/fcarticles.cgi?show=64047
But focuses on sphere/triangle intersection.

All in all, my approach didn't seem bad, let's refine my roadmap:
- keeping a data structure for a "3d grid" in my 3d world. Limited amount of cubes... maybe 16*16*16.
- keeping bounding spheres, eg. a center and a radius, for each 3d object I have

Say we have n 3d objects, and let's consider memory management and complexity in details:
- 3d grid == 16*16*16 * Vertices, = 4096 * (sizeof(Vertex) + sizeof(int) * n) bytes
- n * (Vertex center + float radius). We have n * (sizeof(Vertex) + sizeof(radius))

Both very compact ways to store our cubes, the volumes they may contain, and the bounding spheres of those volumes.
With only these, a quick and simple routine would let us know which grid cubes contain a volume or not. When a cube contains two volumes or more, detailed collision detection occurs.
The grid should be updated when an object moves, it would then be easy as checking the newly occupied cubes, and only those (a bunch per volume movement) to see if they already contain something.

If those cubes already contain something, detailed collision detection would occur against that something.

It can be done using Minkowski difference, which only requires iterating through very basic operations (+- and alike), AND would return the "amount of penetration".
At this point, I'd have a vector representing the penetration of object B by object A.

A simple way to use this vector would be split it in two, opposites, and add these opposites to the respective movements of solids A and B.
All in all, the complexity and size of data structures would be low.


The biggest data structure would be the cube itself, and it would be small, occupying a small share of memory.
The complexity would get close to O(n) for most functions, O(1) for some, javascript can deal with that. It would be fast.
AND it would be accurate.
Plus there would be a lot of room for "practicle hacks" and lowering the practicle complexity.

I think that pretty much sums it up. Good luck and keep us posted.

Ah, yes, your first roadmap was pretty much what I had decided upon. At first I was confused a little by perskulls's articles, before I realised they weren't at all what I was looking for - they discussed simple bounding boxes, and checking ray/polygon and ray/sphere intersections essentially.

What I want to do is to first check by sphere/box bounding, then do triangle by triangle.
I have to say, I hadn't really thought of doing the 3d grid approach - I worry that that could easily end up being either way too complex or way too slow/useless.

However, I got some great/bad news this morning - I got an offer from my top choice university (cambridge) which is kinda good, but means I actually have to do lots of work now...I will certainly keep this program up but will have to be on the back burner for a little while.

InI: thanks for all your help and suggestions, I'm off to look up a couple of the algorithms you mentioned in more detail now!

Wrayal

He got an offer from Cambridge and he is complaining Poor, poor boy. You know some people WISH they would have those kinds of problems?
Congratulations and my best wishes on this own, this is the kind of thing that happens once in a lifetime, and not to everybody.

The grid concept was inspired by marching cubes (and isosurfaces).
Space partitionning is used a lot in collision detections, and in reality, a well structured data structure could work wonders methinks,
but bsp trees would be useless and too heavy, so I came up with the most simple kind of space partitionning I could think of.

You're right, though, it could be useless in js.
Reviewing my proposals, I may opt for bounding spheres at first.

One potential benefit of the cube space partitionning could be isolating the exact triangles that need collision detection, and applying it only to those.
Which in turn would make the whole code more complex than I planned it.

The problem is interesting though... bounding spheres collision detection would be as easy as detecting the distance between the centers of two objects,
and comparing it to the radius of each sphere. This comparison would have to be made for each moving volume against all other volumes each time a volume moves, though.
With cube based partitionning, you would only have to compute the "entering cube/leaving cube" part for a given moving volume.

After that, you would be left with many cases where the volumes don't collide eventhough theyre spheres meet each other's,
and that's the tricky bit to me. Eliminating those cases.

That's where my cube grid would come in handy again: say you know two volumes may collide in cube "n", it's easy to know exacly which vertices are in cube n
at any given time.

And then, to compute intersections only for triangles attached to those vertices.
Or to refine the process a little further, and determine wether volumes are intersecting at all with <some algorithm>.

Anyway, congrats again on Cambridge. I remember having said that before, but you'll do fine.
*And a happy new year to you.

Oddly enough, grid-based spatial subdivision for collision detection seems to be one of the first options according to many books
Talking about roadmpas, the following lecture seems to give an overview of the possible options.

And also mentions Minkowski difference..

http://www.bookpool.com/sm/1558607323

Haven't read the details of this thread nor made that kind of math since a while, but I think you should have a look at the OPCODE collision detection library by Pierre 'Zappy/Holocaust^Bomb' TERDIMAN. FWIW, in the golden age of the Atari I considered Zappy as a living god of code, and he's still a beast of a coder.

Looks good. Platform specific, but good The final target machine here is a Nintendo DS dear castor. I see a Windows version and a Linux port, but I am afraid this closed-source gem
can't be used in Wrayal's case.

In my case, though... Well, in my case, we know the rules: I post material I create or do credit the author. For demo sports it's a no go.
For school this will be fine.
Thank you

I saw Pierre release the source code of Flexporter and thought he did so for Opcode. My bad. Anyway, wandering on his website should provide some interresting pointers.

/me will read this thread in detail

"He got an offer from Cambridge and he is complaining" - hehe, I didn't realise how much cambridge would mean to people here or I'd have been more tactful - sorry! But, thanks

I guess it all comes down to a matter of speed of computation. I'm not bothered about writing the extra code - the maths is fun - but I'm wondering whether the extra layer of a grid will makemit slower, because there are extra checks, or faster because there are fewer polygon collision tests. I guess the ideal check is to write both and compare!

poi: tanks for the pointers, shame it's closed :\

Wrayal

(btw: when you used 'castor', it confused me for a sec - my nickname is beaver I take it that is poi's nickname?)

"All the castors in the thread, please stand up".

Funny.

Castor is his uncalled for nickname, yeah, I am the one who keeps calling him castor, although he has handles a plenty already.

* I guess it all comes down to a matter of speed of computation.

My point exactly. A roadmap as the above can be used to forecast the complexity and speed of the final app.
Hence the little stupid data structure calculations: two key elements matter for fast applications, algorithmic complexity ( O(n), O(log n), O(N^2), etc... notations)
and memory usage, because memory allocation/deallocation is time consuming and proportional to the amount of memory in use.

Once have these, you can forecast the speed.
Functions which only contain one linear for loop have a complexity of O(n), n being the number of items in the loop.

So, write down a couple of "descriptions" as the above, translate them into "general descriptions of the involved programmatic functions",
and then you can evaluate the complexity.

For example, write down the "all triangles against all triangles" scenario, turn it into a step-by-step-linear execution scheme, and you'll have an overview of the complexity of this approach.
Do the same with the other options you consider, and you'll already know which ones sound good and which ones will fail, and how they compare.

Then you can take two relevant approaches, and implement both for comparison of the real result.

For general guidelines about complexity, it's O form represents the "maximum amount of unitary operations required to perform the function".
So, a for loop = O(N). Two nested for loops = O(N^2). O(log N) or O(N log N) are generally appreciated, as log N is close to 1.

O log N occurs most often with functions where the amount of objects to parse is divided by 2 at each iteration.
For example, dichotomic search does exactly this: split a sorted array in two, if "needle" is superior to the central value in the array, take the right part of it and start over again.

As N is generally assumed to be big, O(1000 *N) is considered equivalent to O(N).

And these guidelines define the complexity of an algorithm regardless of the language or architecture in use, so they make for a fantastic set of rules to evaluate complexity.

- Spare yourself the headaches, plan a lot first, consider all options, write them down to paper, sketch the roadmap, evaluate the complexity, THEN code.
And once the code is stable and corresponds to the specs, OPTIMIZE.

Quite cool paper about collision detection

Sweep and prune explained.
The "3d grid" concepts is already classyfied and used, as the "Sector Method".
And it gives an insight into the algorithmic notion of complexity.

Ah, finally got some time to work on this again. It's pretty close, but as ever there are one or two programmatic issues that get in the way of the nice maths

I have to re-arrange a couple of simultaneous equations for a couple of my functions. However, of course some of the denominators are 0...are there any obvious ways round this? It just throws NaN errors, which is irritating. I can check for these cases and have extra re-arrangements to get round it, but this requires a heck of a lot of code that would be redundant 99% of the time - or perhaps the matrix system for solving simultaneous equations might provide more joy?

Anyway, just wanted to let you guys know that I hadn't abandoned this, even in the light of numerous exams, and to see if you had any input!

wrayal