reverse grid?
Author
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?
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. :)
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. :)
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.
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.
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.
Author
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.
@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.
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.
You just made your grid an intrusive container.
Nothing special.
How can you even use algorithms and data structures, let alone design new ones, when you don't even understand basic notions of complexity?
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?
Author
wow, you really know a lot loufoque. I hope I can be like you someday.
This thread is sort of done, my question is answered.
This thread is sort of done, my question is answered.
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.
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.
Basic complexity principles such as these are taught in Computer Science 101, if not earlier, such as in mathematics in high school.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement