Quadtree for dynamic collision detection

Quote:

Original post by Mercenarey Has it been done with dynamic collision detection, where you have to take velocities into consideration, when finding nearby objects?

Yes, it has been done many times.

Usually it is easier and faster to keep dynamic objects in a list. It takes a lot of work to keep a moving spatial tree current, but sometimes it makes sense.

My biggest problem is how to make certain, that I get all objects, that may influence, just from the tree alone (not looking at each neighbouring object's radius/velocity).

I thought of making a temporary sphere around the object-in-question, with a radius corresponding to the object radius+velocity+object-max-radius+object-max-velocity, and then do a standard static query, since such a sphere would cover the entire possible area of colliding objects.
But the problem is, that if I have to every time test with max-velocity, that the temporary sphere will be alot bigger than what is necessary.

So how is the problem of finding the relevant neighbours in the tree, while taking their possible velocities into consideration, without querying an excessive area?

I don't suppose there are some sources on it? I have looked around alot on the internet the last days.

Quote:

Original post by Mercenarey I don't suppose there are some sources on it? I have looked around alot on the internet the last days.

Foo
--> Bar, with further pointers

Phresnel:
Thanks for the google lesson.

Now, can you point to me anywhere in your two links, where my problem is considered?

Your wiki-link says the following about spatial partitioning:
"Alternative algorithms are grouped under the spatial partitioning umbrella, which includes octrees, binary space partitioning (or BSP trees) and other, similar approaches. If one splits space into a number of simple cells, and if two objects can be shown not to be in the same cell, then they need not be checked for intersection. Since BSP trees can be precomputed, that approach is well suited to handling walls and fixed obstacles in games. These algorithms are generally older than the algorithms described above."

But how can you know, by just looking at cells in a dynamic system, that they will not potentially intersect, when velocities are involved? Exactly. What they treat is static collision detection, I don't have problems with that.


Can you point me to ONE SINGLE resource in your google search link, that treats the problem at hand?
No, I dont think so. The problem is "spatial partitioning" and "moving collision detection" (I use dynamic instead of moving when I search), not "moving collision detection" alone.

[Edited by - Mercenarey on August 11, 2010 6:38:45 AM]

Quote:

Original post by Mercenarey Phresnel: Thanks for the google lesson. Now, can you point to me anywhere in your two links, where my problem is considered? [...] Can you point me to ONE SINGLE resource in your google search link, that treats the problem at hand? No, I dont think so. The problem is "spatial partitioning" and "moving collision detection" (I use dynamic instead of moving when I search), not "moving collision detection" alone.

Quote:

from the wikipedia link Better methods have since been developed. Very fast algorithms are available for finding the closest points on the surface of two convex polyhedral objects. Early work by Ming C. Lin [1] used a variation on the simplex algorithm from linear programming. The Gilbert-Johnson-Keerthi distance algorithm has superseded that approach. These algorithms approach constant time when applied repeatedly to pairs of stationary or slow-moving objects, when used with starting points from the previous collision check. The end result of all this algorithmic work is that collision detection can be done efficiently for thousands of moving objects in real time on typical personal computers and game consoles.

So, as the site claims, as long as you don't have tens of thousands of moving stuffs, everything is alright using referenced article. Worth a look I guess.

Then, about static/dynamic intersection: Consider that you have a velocitiy, so you prolly have linear movement, i.e. you have a moving bounding box or bounding sphere. You could hence use the bounding sphere enriched with time, forming a ... cylinder. I don't think that a cylinder is wasteful.

Also, the wiki-page contains many pointers to open source physics engines. Have you thought about studying what they do?

Quote:

What they treat is static collision detection, I don't have problems with that.

As you probably don't want to collide walls with houses, do I extrapolate it correctly from that phrase that you have a dynamic timestep, instead of a fixed one?

Or what is your larger target?

Quote:

Original post by phresnel Then, about static/dynamic intersection: Consider that you have a velocitiy, so you prolly have linear movement, i.e. you have a moving bounding box or bounding sphere. You could hence use the bounding sphere enriched with time, forming a ... cylinder. I don't think that a cylinder is wasteful.

No it is not. But what do you propose then? That I take each object every timestep, create a cylinder (I would call a capsule since a cylinder does not have rounded ends) from it and put it back into the tree?
What happens with response, if one object bounces or slides off another and therefore changes direction in the middle of the timestep? That is gonna be some funky looking capsules, and you cannot up-front anticipate what collision is going to happen.

So you see, it is not only not wasteful, it is also impossible.

Quote:

Original post by phresnel Also, the wiki-page contains many pointers to open source physics engines. Have you thought about studying what they do?

I looked at Box2D and they use the static method. So yes, I did exactly that.

Quote:

Original post by phresnel As you probably don't want to collide walls with houses...

The techniques used with quadtrees, that I have seen, use timesteps and then do an overlap test. They move the scene forward, test for intersection (statically), and if there is collision, they resolve it.

I want to do a dynamic test, where I move the entire scene forward with velocities, find the first collision, resolve the collision (often resulting in a changing velocity-vector), then move forward to next collision etc.

Those are dramatically different approaches. I was then asking if it was possible to combine the spatial partitioning technique of quadding - which I have only seen done with timestep+static - with a dynamic test.

And then I got the reply from you, which I found severely lacking in respect.

My solution will be to drop the quadtree. It gets too complicated, when neighbouring quads of differing resolutions need to interact.

Instead I will go with a cell system, with cells big enough to make sure, that only objects in neighbouring cells need to be considered, that means cells big enough to contain the maximum object and it's maximum velocity times two, to make sure that an object two cells away cannot intervene.

I hate quoting myself, but it looks like it must be done:

Quote:

Usually it is easier and faster to keep dynamic objects in a list. It takes a lot of work to keep a moving spatial tree current, but sometimes it makes sense.

For moving objects, it is almost always the best option to go with a simple list.

Unless you have hundreds of moving objects (which I doubt) then the overhead of managing a dynamic spatial tree will be far greater than the cost of queries.

That is why most of the current literature and research covers either static spatial trees or massive offline solutions. The other case (small real-time solutions) simply aren't necessary in the general case.

Quote:

Original post by frob I hate quoting myself, but it looks like it must be done: Quote: Usually it is easier and faster to keep dynamic objects in a list. It takes a lot of work to keep a moving spatial tree current, but sometimes it makes sense. For moving objects, it is almost always the best option to go with a simple list. Unless you have hundreds of moving objects (which I doubt) then the overhead of managing a dynamic spatial tree will be far greater than the cost of queries. That is why most of the current literature and research covers either static spatial trees or massive offline solutions. The other case (small real-time solutions) simply aren't necessary in the general case.

I have potentially alot of moving objects. I am working on an RTS.
I agree, that the Quadtree is overkill, and wayyy too hard to keep up-to-date with dynamic objects, and that is why I will go with the cell system instead.

Note that "a lot" is very relative. "A lot" might also be 2 billion instances of tree-leafs in a terrain renderer. But it might also mean just 32 players in a networked RTS match.

Quote:

Original post by Mercenarey I have potentially alot of moving objects. I am working on an RTS.

Potentially how many? Potentially 500? Potentially 3000? Potentially 50000?

Also, are you talking about collision handling and response within the game?

I assume this is just one component of a game.

Any processing over a few milliseconds per frame will be just too complex for real time. You've only got a few million cycles per frame, maybe around 40 million. Most of that time will be spent on cache waits and memory reads. Most of what remains will be spent on graphics processing, and secondly on game physics. You only get a few hundred thousand cycles each frame for manipulating world objects.

If your item count is small enough that it can be processed in the necessary time frame then you probably don't have enough to justify that kind of spatial tree. If it is large enough to require a tree then you are either doing infrequent processing or non-game processing, which is a different story.

Quote:

Original post by Mercenarey I have potentially alot of moving objects. I am working on an RTS. I agree, that the Quadtree is overkill, and wayyy too hard to keep up-to-date with dynamic objects, and that is why I will go with the cell system instead.

A quadtree is just a hierarchical grid - not significantly harder to keep up-to-date if you hide the implementation details properly. If units are more or less evenly divided across the field, a quadtree offers no significant benefits. But when units are clustering in certain areas, a quadtree allows you to change cell granularity for those specific areas, potentially culling more objects.

I think the best approach here is to test which one works best for your particular situation. If you separate responsibilities correctly, you could even swap the underlying data-structure at run-time. They could have the exact same interface (insertObject, moveObject, getObjectsInArea, ...).

I was done with this thread, as I believe that we more or less covered it.

But I can't notice - which I also notice around on other threads - this mad fight for being right. If it isn't achieved on one front, a new one is simply opened. Or some detail is taken and blown completely out of proportions. Why is that?

What the hell is the relevance of discussing the number of collisions, to solving the problem I pose (Even after I say 'alot', lol)? Even if in some scenarios, it would be overkill with so and so many objects, there will exist some, where it is relevant with spatial partitioning.


I advise that you argue to solve the problem posed, instead of arguing for the sake of arguing.

Quote:

Original post by Mercenarey I was done with this thread, as I believe that we more or less covered it. But I can't notice - which I also notice around on other threads - this mad fight for being right. If it isn't achieved on one front, a new one is simply opened. Or some detail is taken and blown completely out of proportions. Why is that? What the hell is the relevance of discussing the number of collisions, to solving the problem I pose (Even after I say 'alot', lol)? Even if in some scenarios, it would be overkill with so and so many objects, there will exist some, where it is relevant with spatial partitioning. I advise that you argue to solve the problem posed, instead of arguing for the sake of arguing.

Firstly: your thread was done right after the first reply. Your original question was

Quote:

Has it been done with dynamic collision detection, where you have to take velocities into consideration, when finding nearby objects?

and right the first reply correctly answered "Yes". That was the moment the "posed problem" was solved. So any further content is by benevolence.


Secondly: What mature help do you expect for such a vague problem descriptions that says "alot" if there are infinite definitions of "alot" (ranging from 3 to INF). For some definitions of "alot", a list is superiour. For other definitions of "alot", a bounding volume hierarchy is better.


Thirdly: You are not the one who decides when a thread is closed.


Lastly: You are an ingrate person without manners for which investing time is not worth the effort. Go help yourself and seek enlightenment in the vastness of your own infinity.

Quote:

Original post by phresnel Firstly: your thread was done right after the first reply. Your original question was Quote: Has it been done with dynamic collision detection, where you have to take velocities into consideration, when finding nearby objects?

I expected some kind of pointer as to how. Most people come here because they need a problem solved.

Quote:

Original post by phresnel Secondly: What mature help do you expect for such a vague problem descriptions that says "alot" if there are infinite definitions of "alot" (ranging from 3 to INF). For some definitions of "alot", a list is superiour. For other definitions of "alot", a bounding volume hierarchy is better.

When did you ever play an RTS with 3 units?

Quote:

Original post by phresnel Thirdly: You are not the one who decides when a thread is closed.

That is why I said: "I was done with this thread". Did you notice the "I"? You can stay here and argue the "alot" as long as you want, I just choose to stop now.

Quote:

Original post by phresnel Lastly: You are an ingrate person without manners for which investing time is not worth the effort. Go help yourself and seek enlightenment in the vastness of your own infinity.

You are the one dishing out google lessons, and you call me without manners??
That is not the kind of "effort" I want anyway, so maybe you should think about that next time you give "advice" in the form of google lessons, that don't even lead anywhere.

Finally:

Quote:

Original post by Mercenarey I expected some kind of pointer as to how. Most people come here because they need a problem solved.

But then complain about further pointers just because they only touch your problem by 90% instead of 100%?

Right.

Quote:

When did you ever play an RTS with 3 units?

You don't get it. This is not relevant. Relevant is only your definition of "alot".

Anyways: In Command+Conquer, "alot" is when there are 50 mammoth tanks on the screen. In Shogun: Total War, "alot" is when there are 1000 units on the field. In Napolean: Total War, "alot" is when there are 10000 units on the field. I just gave you examples in three orders of decimal magnitude. For each, there are different optimal solutions.

Quote:

That is why I said: "I was done with this thread". Did you notice the "I"? You can stay here and argue the "alot" as long as you want, I just choose to stop now.

So why post at all "that you are done" and not leave the others alone discussing? If your intention was not to say "guys, stop it now", you'll need a lecture in empathy. And my conjecture is emphasized by the rant that follows your posting.

Quote:

You are the one dishing out google lessons, and you call me without manners??

Because on gd.net, it is good manner when one shows how he would find out. And results on the google page seemed promising. And it is indeed often the case that ppl just don't have the right combo of search terms.

But you only see the worst expected behaviour in us. Again, you need a lesson in empathy.


o/

Quote:

Original post by Mercenarey Quote: Original post by phresnel Lastly: You are an ingrate person without manners for which investing time is not worth the effort. Go help yourself and seek enlightenment in the vastness of your own infinity. You are the one dishing out google lessons, and you call me without manners?? That is not the kind of "effort" I want anyway, so maybe you should think about that next time you give "advice" in the form of google lessons, that don't even lead anywhere.

Just so you know, I edited my last post to include a reply to your flame.


As for the case of 'alot', why isn't that good enough for you? Don't you trust me to evaluate what I need?

Quote:

Original post by phresnel But you only see the worst expected behaviour in us. Again, you need a lesson in empathy. o/

I don't see the worst expected behaviour in people, not even here. But when I see bad behaviour, I recognize it.

Quote:

Original post by Mercenarey As for the case of 'alot', why isn't that good enough for you? Don't you trust me to evaluate what I need?

You are asking for the right algorithm (or if quadtrees are of use) for collision detection, yet you don't see that it highly depends on the number of objects in the scene...