Sign in to follow this  
YoYoFreakCJ

reverse grid?

Recommended Posts

I talked to a colleague today about my QuadTree [for dynamic collision detection purposes]. He suggested for performance issues that I should rather use a grid. He showed me an example: instead of having a struct for each gridcell which holds a list of objects, he created another struct representing the objects, containing a reference to a node. When I move an object and have to calculate the reference node, it seems faster. Does anyone know if this technique has a name? He didn't know it himself, he just came up with it. But I can think of some advantages which may come with this method. There must be an optimized version of this somewhere. I can't believe that noone thought of this before. So, who can help me out?

Share this post


Link to post
Share on other sites
It's called a "grid."

It's a good method for simple cases, but riddle me this: what happens when an object is too big to fit inside a grid space? what happens if an object is not entirely enclosed by its grid space?

For some applications, this is not an issue.

But you shouldn't just rely on what seems faster. Profile and compare the two methods, then pick the winning one.

Also, I've come to learn that no matter how obscure a problem, or how innovative a solution, there was some guy from 1962 that already wrote a whitepaper about it. :)

Share this post


Link to post
Share on other sites
The 1st method: each grid cell has a list of objects that are inside it
The 2nd method: each object knows the index of the grid cell that it is in

Both are useful, depending on what you are doing, but the 2nd method will be much slower for all the cases that make grids useful (mainly adjacency of objects).

Location: What grid cell is object X in?
Method 1: O(1)
Method 2: O(1)

Adjacency: What objects are in grid cell X,Y?
Method 1: O(1) - look in the grid cell X,Y
Method 2: O(n) - linear search

Adjacency: What objects are within a Z grid cell radius of cell X,Y
Method 1: O(1) - look in the grid cell X,Y and the surrounding cells
Method 2: O(n) - linear search

Note: in nearly all grid implementations, objects will be in multiple cells, otherwise you will get really weird collision anomalies when objects are near grid lines.

Personally, I save "curentGridCell" with all objects and the corresponds to the the cell that the center of the object is in.

Share this post


Link to post
Share on other sites
Quote:
Original post by erissian
It's a good method for simple cases, but riddle me this: what happens when an object is too big to fit inside a grid space? what happens if an object is not entirely enclosed by its grid space?

For those cases there's the hgrid (hierarchical grid) which is similar to a quadtree/octree except that the top levels are missing (besides some storage methods, maybe).

Another possibility would be to use recursive grids, i.e. you start with a coarse grid and refine the cells that need to be refined. The level of refinement is up to you and could also depend on the objects within the cell. That's still similar to a quadtree/octree but each node/cell doesn't necessarily have 0, 4 or 8 but might hava abn arbitrary number of children.

Share this post


Link to post
Share on other sites
Thank you for your replies.
@EJH: I didn't quiet understand your example. What do you mean by O, and for which number of processes does 1 or n stand for?
Of course, if an object is overlapping into another cell it should be in both cells, so I can have a clean cd.

I guess I really just have to find the best way myself.
My situation is, that most of the objects are constant for the most time. I'm working on an animation editor, where I only need to check for collision between the mouse and the vertices. I might use an Octree which seems like the fastest way of doing things, since an Update of the tree won't happen too often.

Share this post


Link to post
Share on other sites
EJH is using Big O notation to describe how long the various methods take to complete. It's a standard and widely used notation in the computer programming field, particularly in computer science. Getting familiar with Big O - and, more specifically, with the performance characteristics of your algorithms and how to measure those characteristics - will be an essential addition to your programmer's toolbox.

Share this post


Link to post
Share on other sites
You just made your grid an intrusive container.
Nothing special.

Quote:
@EJH: I didn't quiet understand your example. What do you mean by O, and for which number of processes does 1 or n stand for?

How can you even use algorithms and data structures, let alone design new ones, when you don't even understand basic notions of complexity?

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
How can you even use algorithms and data structures, let alone design new ones, when you don't even understand basic notions of complexity?


Not everyone learns how to do things in the Ivory Tower. And every program "uses algorithms and data structures" - just perhaps not particularly well or in a particularly sophisticated way.

I really think you ought to adjust the attitude you convey in your posts. In my official moderator capacity, you know. You are crossing the line beyond "constructive criticism" with comments like this.

Share this post


Link to post
Share on other sites
I was being honest and pragmatic, not insulting.
I do not see how you can do any algorithmic work without understanding how the algorithm efficiency varies depending on input.

Quote:
Not everyone learns how to do things in the Ivory Tower

Basic complexity principles such as these are taught in Computer Science 101, if not earlier, such as in mathematics in high school.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Basic complexity principles such as these are taught in Computer Science 101, if not earlier, such as in mathematics in high school.


But then I don't sense infernal science and knowledge in you, too: A, B, C; actually, one only has to look at what you write and what people reply to you... plus, well, your rating isn't growing much (in the past, actually I often rated you up for some posts, but that won't happen again for some time).

Or is it that you sticked to the 101 stuff?

Share this post


Link to post
Share on other sites
The previous message from phresnel was obviously off-topic, and so is mine I suppose, since it is in its continuity.

Quote:
But then I don't sense infernal science and knowledge in you, too: A, B, C;

I never claimed to be an expert in the fields of geometry or 3D games. Those are fairly more advanced things than algorithmics 101 or whatever anyway.
Well to be honest I'm not familiar with the education in the united states of america, so it's true I wouldn't know.

Quote:
plus, well, your rating isn't growing much (in the past, actually I often rated you up for some posts, but that won't happen again for some time).

I'm on that forum to experience what game programmers are like, since I found quite horrible all the game-related code I ever saw and was thus curious, and I try to improve things a bit maybe, while learning things at the same time.
I don't care about my rating.

Interesting thread, that thread C. Only thread I ever made on that forum (in my memory, at least), because I thought I could gather more information this way on the subject than by doing it the hard way by myself. At the time, I only knew of spatial indexing of points as a way to get logarithmic neighbor search, since I saw it in computational geometry classes, not game-related studies.

I mostly got answers that missed the point though. Those forums are really filled with more "technical" people, and I'm astonished at how people can code software when they only have about half an understanding of what they're doing, design algorithms without even thinking of their complexity, etc.
It's not necessarily a bad thing, I just don't understand it.

The solution here was really simple: sample rays in all directions (using tricks to resample near borders of intersected geometry to avoid sampling too much), cast them (using spatial indexing for logarithmic complexity on the number of polygons of the world), and find who you hit. No one gave me that solution, but rather they lingered on technical details, or told me to let the graphics card render and see rather than try to find the algorithmic solution to the problem.
(Of course there are other solutions with different complexities, some of which might be considered better in some scenarios, but that was what I'm looking for)

Share this post


Link to post
Share on other sites
Quote:
The solution here was really simple: sample rays in all directions (using tricks to resample near borders of intersected geometry to avoid sampling too much), cast them (using spatial indexing for logarithmic complexity on the number of polygons of the world), and find who you hit.

This is another way I'll try out for the sake of performance. Thanks for that.

But really, can you guys please stop spoiling this thread? Discussions about the qualities of a member are not to be written in here. I don't want to hear any explanations, nor any pros or contras, nor any comments about me not wanting this discussion. Just do not post about it again. Focus on solely the topic "grid" or leave it be. This is to everyone. Seriously..

Share this post


Link to post
Share on other sites
It seemed pretty evident to me that the OP was not working from formal studies of the topic, and had simply been working from tutorials and/or trying to make sense out of random bits of advice.

But in case you didn't notice, I'm the moderator of this forum now, and I'm not interested in public discussion of the matter.

In the future, think about whether what you're saying can reasonably be construed as a non-constructive insult, and rephrase yourself if so. It's fine to talk about the failings of an educational system or of someone's code; do not just pause to point out a person's ignorance. If the OP were not aware of his/her own ignorance, the thread wouldn't exist in the first place. (An exception is made for OPs who are reluctant to take advice because it's not what they wanted to hear or because it requires them to accept that they were mis-taught earlier; but that isn't the case here.)

Further posts arguing about this will be deleted.

@OP: I agree with you, but ordering people around is my job. ;)

Share this post


Link to post
Share on other sites
Quote:
Quote:
The solution here was really simple: sample rays in all directions (using tricks to resample near borders of intersected geometry to avoid sampling too much), cast them (using spatial indexing for logarithmic complexity on the number of polygons of the world), and find who you hit.
This is another way I'll try out for the sake of performance. Thanks for that.

Just to make sure there is no misunderstanding, that solution I gave is that of the thread "C" phresnel linked, and is unrelated to your thread.

Share this post


Link to post
Share on other sites
Quote:
Original post by YoYoFreakCJ
Does anyone know if this technique has a name?


For overview of algorithms involved in collision detection, this is a good reference.

Quote:
it seems faster.


For various reasons, memory layout can bring drastic performance improvements (ppt). This applies even to quadtrees. Naive quad tree which allocates nodes and elements as needed can behave poorly.


But as far as original problem of collision detection goes, reducing number of comparisons, and any other approach to tackling the n-squared problem will be where the money really is, regardless of which structure is implemented underneath.

Share this post


Link to post
Share on other sites
Quote:
Just to make sure there is no misunderstanding, that solution I gave is that of the thread "C" phresnel linked, and is unrelated to your thread.

But it's a good exercise trying it out and figuring the details out. Who knows, maybe I'll find a groundbraking method while doing so? ;)
Is it really so unfitting for CD? I can see some possibilities to improve performance by checking overlaying points in the axes one after another, rather than calling Intersects() [or another predefined CD method]. Using this in a grid sounds good to me. What do you think?

@Antheus: thanks for the suggestion, I'll try to get a hold of that book.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this