Jump to content

  • Log In with Google      Sign In   
  • Create Account

[Tutorial] Instant-Insertion Quadtrees


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
14 replies to this topic

#1 L. Spiro   Crossbones+   -  Reputation: 13595

Like
18Likes
Like

Posted 05 February 2013 - 11:30 PM

I have just posted a tutorial on super-fast instant-insert quadtrees here. Efficient Instant-Insertion Quadtrees

 

The downsides of typical implementations of quadtrees is related to caching and searching (which compounds the caching problem) when objects are inserted into it.

Here, I explain 2 ways to improve the cache:

  1. Insert objects into the tree instantly, without a search.
  2. Store all the tree nodes together in one large pool of nodes.

I use bit hacks to instantly determine how deep into the tree an object is, and then I store the nodes at each level in a grid-like order so that I can instantly convert the object’s X and Y coordinates to the X and Y indices of the node to which it will be inserted.

 

 

The results are quite drastic.  I can update, move, and re-insert 30,000 objects into this quadtree at 60 FPS on an iPad 3.

 

So read it for yourselves!

 

 

L. Spiro


Edited by L. Spiro, 06 February 2013 - 09:13 PM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

Sponsor:

#2 Mussi   Crossbones+   -  Reputation: 1969

Like
1Likes
Like

Posted 06 February 2013 - 06:04 AM

Bookmarked. Thanks for sharing!

#3 swiftcoder   Senior Moderators   -  Reputation: 9994

Like
1Likes
Like

Posted 06 February 2013 - 10:22 AM

That's pretty damn slick - gotta love the bit-hacks.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#4 CC Ricers   Members   -  Reputation: 623

Like
1Likes
Like

Posted 06 February 2013 - 01:54 PM

Interesting stuff! I just made a simple quadtree program last week to refresh myself on the C++ language.

I may try making this quadtree as a challenge.


My development blog: Electronic Meteor

#5 web383   Members   -  Reputation: 774

Like
1Likes
Like

Posted 07 February 2013 - 11:28 AM

Great tutorial!

Wit this technique, are my world coordinates forced to be from 0 - 256? And objects will only be spatially sorted at a resolution of (1/256)?

Edited by web383, 07 February 2013 - 11:29 AM.


#6 CC Ricers   Members   -  Reputation: 623

Like
0Likes
Like

Posted 07 February 2013 - 01:10 PM

Great tutorial!

Wit this technique, are my world coordinates forced to be from 0 - 256? And objects will only be spatially sorted at a resolution of (1/256)?

 

That would make it very limited, wouldn't it? It's 256 in his example since it's easier to show how it works in 8 bits. You can use 16 or 32 bit types if you want, for a much larger area.


My development blog: Electronic Meteor

#7 swiftcoder   Senior Moderators   -  Reputation: 9994

Like
3Likes
Like

Posted 07 February 2013 - 01:25 PM

Wit this technique, are my world coordinates forced to be from 0 - 256?

No, you just need to apply a suitable conversion factor.

And objects will only be spatially sorted at a resolution of (1/256)?

Yes. That should be plenty to significantly speed up collision detection, or any other naive O(N^2) process.

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.


Tristam MacDonald - Software Engineer @Amazon - [swiftcoding]


#8 CC Ricers   Members   -  Reputation: 623

Like
0Likes
Like

Posted 07 February 2013 - 01:38 PM

You can use 16 or 32 bit types if you want, for a much larger area.

You will run out of memory - it's not feasible to preallocate enough storage. If you really need a quad-tree with depth greater than 8, then you need a sparse representation thereof.


Oh right, I mixed up the world coordinates for depth representations. I forgot for a moment that the 8-bit value represents the tree levels, not coordinates.

Converting the coordinates as you said makes more sense.


My development blog: Electronic Meteor

#9 Waterlimon   Crossbones+   -  Reputation: 2564

Like
0Likes
Like

Posted 07 February 2013 - 02:07 PM

But couldnt you just use a part of lets say a 16 bit into to get lets say a 10 level tree?

o3o


#10 L. Spiro   Crossbones+   -  Reputation: 13595

Like
3Likes
Like

Posted 07 February 2013 - 04:17 PM

The world size can be any value.  In the code, m_fInvRadius is used to make the conversion from world units to internal units here:
		// Now to the range from [0..255].
		a2Shifted.m_vMin.x *= m_fInvRadius;
		a2Shifted.m_vMin.y *= m_fInvRadius;
		a2Shifted.m_vMax.x *= m_fInvRadius;
		a2Shifted.m_vMax.y *= m_fInvRadius;
You can use 16-bit values and some adjustments to the internal range to get 10 levels, but that would be 349,525 nodes and 18,175,300 megabytes of memory on 32-bit machines.

8 levels is usually enough. If your world is 10,000 meters square (10 kilometers), the smallest squares are 78.125 meters in size, which is very reasonable resolution. Remember that the smaller your nodes are the more frequently moving objects have to be re-inserted, so there is a trade-off with deeper trees.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#11 JackShannon   Members   -  Reputation: 488

Like
1Likes
Like

Posted 07 February 2013 - 10:07 PM

Thanks again L. Spiro!



#12 Polarist   Members   -  Reputation: 160

Like
0Likes
Like

Posted 08 February 2013 - 08:11 AM

Cool approach.  To manage the memory requirements in a large-yet-dense 3d world, it might make sense to store traditional oct-trees within this type of structure to have cache friendly step prior to a traditional broad phase collision detection.


Edited by Polarist, 08 February 2013 - 08:12 AM.


#13 L. Spiro   Crossbones+   -  Reputation: 13595

Like
1Likes
Like

Posted 08 February 2013 - 09:33 AM

I mention a few ideas on how to extend it into 3D at the bottom of the article and the way I am likely to do it when I get around to it is to use this method exactly as-is for the X and Z and use stacks for the Y (vertical).

To be honest, you don’t even necessarily need a vertical partition in most outdoor games, and indoor games use PVS’s, which you could couple with this type of quadtree (after testing to see if it makes sense for you), but even then you wouldn’t need a vertical partition most of the time.

 

Imagine a world that is 10 kilometers by 10 kilometers.  As a cube that means your octree would also be 10 kilometers tall, yet 90% of your level is likely to be in the root node or just the second node down, betrayed by its vertical proximity to the center of the octree.

 

So my feeling is that 3D should be handled by a mix of this method (completely as-is) for the X and Z and something entirely differently (if at all) for the Y.

And also, whatever method used for the Y (for me that will be stacks—just divide the world vertically by a fixed number of slices) can still benefit from better caching by being part of that same pool as the one used in the quadtree here.  Just extend the size of the pool by whatever is needed for the vertical slices and you should still keep decent caching.

 

 

L. Spiro


It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#14 Polarist   Members   -  Reputation: 160

Like
0Likes
Like

Posted 08 February 2013 - 09:50 AM

Yup, I did read that part of the article, and it's a good observation for a 3d game which largely only expands in 2-dimensions.

 

But sometimes you need richness in that 3rd dimension, as well.  E.g. a space simulation.



#15 Froyo   Members   -  Reputation: 201

Like
0Likes
Like

Posted 08 February 2013 - 10:30 AM

I really need to find a good tutorial like this for Java. The ones I've looked at haven't been much help.. maybe it's just me though.






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS