I'm wondering what people would suggest regarding some issues I'm encountering using a quadtree to represent geometry. Below I'll just outline what I'm doing. I hope to see if anyone else has played with this and has any useful suggestions, ideas, or a discussion in general. Also, I'd like to mention that I was inspired by the Cube 2 engine (Sauerbraten) when hashing up this approach. The idea is fairly simple (the details are killer though! :-P ). I use a quadtree wherein each node contains four (transformable) points, a texture/animation, "material", etc. Each node/cell can be transformed (points can be pushed into different shapes as long as they're convex), extruded (a node is extended into a neighboring node from one of its edges), textured, etc. This allows map editing to occur in-game. (In case it isn't obvious, this is all 2D.) This is tied into the graphics and physics systems. I'm not very far along with implementing this yet at all, but I've already hit a few problems. I don't want to optimize early, but speed and (especially) memory consumption is already a tough issue (or so it seems). Memory: The tree is sized (I'm talking about dimensions, not memory) by powers of two. For testing, I've tried various sizes of the root. Each set of four subdivisions has a width half of its parent's. To test extremes, I tried a root with a log width of 15 (2^15 = 32768 pixels). To give you an idea, the player controls a flying ship about 64x64 pixels in size, so this isn't a small space but also isn't huge. Since the geometry is a quadtree, the finer the granularity, the more memory it eats. I exploded this tree into the maximum possible number of subdivisions (the minimum log width is 5, or 2^5 = 32). This took nearly 300MB of memory! (lol, programming this on a laptop with only 512MB of physical RAM was fun to watch.) It's unrealistic to have a map that uses absolutely every possible subdivision in the tree, but it's not impossible nor is it unlikely that a map could use between 25% and 50% of the possible subdivisions. That still caps at more than 100MB. I don't want a typical large map to take up that much memory. Curiously, the memory footprint drops drastically fast. A similar exploded tree with a log width of 10 (1024 pixels) takes only 2 or 3MB. Of course, I'm working in powers of two, so a difference of five in the log width is very significant. Speed: Before running the above tests, my quadtree used a more "inline" approach and did a lot of on-the-fly calculation, including calculating the square regions of each node. In fact, nodes were never told their log width at all. It was passed into functions that required any knowledge of physical dimensions (such as the function that fills vertex buffers to render the tree; any size could be passed in and the tree would be rendered at that size). I didn't do much memory testing with this, so I can't be sure, but I'm fairly certain this had a significant impact. However, I did notice that for larger trees this added a noticeable load time (we're only talking seconds though). Because I didn't calculate/store a lot of information, going from a tree to a vertex buffer required traversing the tree once to fill the buffer and once for every single node just to find out it's coordinates! I only did this with small trees before I made changes, but I suspect this would have taken a very, very long time with the 2^15 tree. In theory, I only have to go from tree to vertex buffer once, but in-game editing ruins all of that because as soon as a single point in any node is moved the whole buffer must be reloaded. My latest approach stores a lot of information within each node (hence the huge memory footprint), but this makes it much more straightforward to look up certain information (such as, "what region of the screen does this node occupy?" or "given this point, what's the smallest intersected node?"). Data includes a region class template (four size_t's), a pointer to a central game component, smart pointers to the parent node and four children nodes, a local path index, and a smart pointer to geometry data. The geometry data is a struct containing four points (eight floats, though these will be changed to an integral type), a material index, and a smart pointer to an sprite object. Note that only leaf nodes point to valid geometry data. Subdivided nodes (non-leaf) do not need this data, so it is deleted. I haven't used sizeof() to determine how large each node actually is yet; I plan to do that shortly. Anyway, has anyone else played with this idea before? I'm not sure which approach is generally better or how to find a balance between calculating/storing/memory and on-the-fly/on-demand/speed. Oh, and the power of two thing was somewhat arbitrary, but I figured it would help with optimizing down the road, especially when it came time to apply texturing. Also, because subdivisions are always halved, this is convenient, and pigeonholes the possible widths to prevent mistakes, rendering artifacts, or misaligned nodes. Hopefully this logic makes a little sense. :-P Any thoughts?

Oh, one quick note about the memory stats I posted above! I made a stupid mistake. I was examining the total memory used by the program! That means the 300MB included not only the quadtree, but the vertex buffer (probably similar in size to the tree) and every other facet of the application, including any shared library code! This means the quadtree probably didn't end up as large as I thought it was. I'll have to keep testing.

Hi,

Given your measurements of memory-issues, you might want to look into a KD-tree implementation. Preferably the one with 4-byte nodesize with cache-line as described by Christer Ericson. That solution is quite nice since you also have pre-laid out cachelines so you can easily prefetch them to avoid all types of cache-misses. Also if the lookup is the most time-critical section of your applications, there can be done alot of work to get it going really fast. If you're doing area-or-volymetric lookups in the tree (naturally dependant on the amount of axis you span), the kd-tree has a better worst-case-scenario than the quadtree since you only traverse 2 nodes as worst case instead of 4.

Cheers.

Quote:I guess I'm kinda stumped when you say "Each node/cell can be transformed (points can be pushed into different shapes as long as they're convex), extruded (a node is extended into a neighboring node from one of its edges)". What's the point of having the quadtree if the surrounding boundary points are just going to move anyway?

This means that each node, while confined within it's square bounds, can be reshaped. Each of the four points that make up the initial square can be pushed inward to form angles and curves. This is the actual geometry used to generate rigid body data for physics and vertex data for rendering.

The quadtree allows for dynamic subdivision. Its possible to work at different resolution or levels of granularity. Shaping a larger 128x128 node can be done, followed by increasing the resolution and shaping subdivision to form smooth curves. The same applies to texturing, material, etc. However, all nodes are naturally bound to the region they occupy; they're data (including points) reside in only those bounds.

Also, there is a limit to subdividing. The smallest allowable node is 32x32 pixels. Once this limit is detected, subdivisions fail. (Now that the tree actually stores and knows it's dimensions, it's much easier to detect this condition. My original implementation couldn't really pull this off because it didn't know what it's final dimensions would be.)

Again, check out Sauerbraten to see how this works (but in 3D with octrees). I'm essentially doing the same thing, but in 2D.

Quote:Given your measurements of memory-issues, you might want to look into a KD-tree implementation.

I haven't heard of a KD-tree before. I'll look into this.

So far, my implementation of the tree is very sloppy, so I'm sure that has contributed to some of the poor performance I've witnessed.

Thanks for the replies!

Hey man,

Check this link out for a more detailed description, by ericson himself:
http://realtimecollisiondetection.net/pubs/GDC03_Ericson_Memory_Optimization.ppt

That should hopefully give you all the resources you need :)

Cheers!