Xna objects, space partitioning etc

Graham

Hello :-)
Veteran
Supporter
I've been mucking about with XNA a bit recently. Anyway.
I thought I'd share some of the things I've learnt, and a bit about an algorithm I'm implementing.

One thing I found is that the performance of the base GameComponent isn't all that hot. My guess is that each frame, they sort the components by the DrawOrder, or UpdateOrder (depending on the op). Yet the default for both of these is zero, so by default, they are sorting a list of zeros. Assuming they are using Array.Sort(), this probably means quicksort, so probably means O(N^2).
But ignoring that...

I've also been mucking about with my own xna-like base classes. I'm wondering if there is any interest out there, if any of you want them? etc

The best one I have so far is a space partitioning class.

In the past I've done various implementations. Usually octree (for no particular reason).
What this one does is pretty much the same. It's a binary tree, dividing an axis at a time. So first divide is X axis, next is Y axis, next Z axis. Always at midpoints.

I know it sounds simple, but it has a catch. It can call Update() on all the items stored within, and shift them around in the tree afterwards. It expands/contracts and culls itself, so provided your dataset is fairly good, it keeps itself fairly well balanced. Of course stick 1000 objects within 1mm and another 1000 10km away and it won't be so balanced. But it works, and is fast. It does no runtime allocation.
Currently it's (as far as I can tell) cache limited. All nodes/leaves are currently classes (for simplicity) but I'm moving it to structs and 16bit or 32bit indexing. This will really help the CF GC on the 360 too (in theory).
I'm monitoring how much time I keep a thread busy when updating at 60hz. At 15,000 items it's ~%2 but fluctuates a lot, at 18,000 it's 100%, and 20k can't keep up - so I'm pretty sure it's a cache issue. Moving to structs should help this a lot (maybe down as low as 10byte node,~50byte leaf).

The actual implementation is a damn sight more complex than it seems on the surface (duh! :)). I've done it all before, but it's amazing how I keep forgetting the little catches :p. Keeping track of what items have had Update() called for the current sweep - for when they get rearranged - has been frustrating :p Especially without using lists/allocation.

Anyway the plan is to eventually put it out there for anyone. XNA, MDX, maybe even a C++ port. Ideally I'll be looking at the entire thing having a constant allocation overhead (less than 10 allocations).
Currently jazzing it up with per-item bounding box support.

Anyway here is a pic.

5000 boxes, around 1800 nodes / 1800 leaves (leaves store a max of 5 items). The cpu hit for the Update sweep is less than 1% as far as I can tell :p...

sp.png


Ideally I want to be able to comfortably put 30k+ items in it at 60hz updating.
I'm thinking a good test case would be a space battle with 5,000 ships. :devilish:

I'm interested in opinion. Space partitioning ain't exactly easy, but I'm not deluded in thinking it's rocket science - yet at the same time it's not exactly a glamour feature, so I don't have much to compare/learn from. I'm thinking something robust, small and efficient would be really, really useful for the xna community. And I think I'm getting there on most counts
 
Last edited by a moderator:
- Why don't you subdivide your tree based on the # of objects contained in each cell?
- Loose Octree ftw. (e.g. look at the thread titled "Fast picking against triangle soup" on GDAlg.
 
As soon as there are more than 5 items in a leaf, that leaf's items gets split into two groups by centre point on an axis.. The axis being +1 each level down the tree. If there are 3 or less items in a node, that node is collapsed down to a single leaf. Means the leaf has 5 pointers to potential children. Not 100% efficient, but way better than an allocated array or a linked list.

I looked up the loose octree.. Frankly I can't see the advantage? Perhaps the post didn't explain it well enough, but I couldn't see it. I don't see how having nodes be massivly bigger than they need to be is possibly a good thing...
Moving items around the tree isn't really a performance issue, it's just tricky to get exactly right. I suppose it is easier if the nodes already exist, but my main issues were with update ordering, etc.

Each node also stores the axis bounds of the items contained within it's children. So in that sense they can (and do) overlap. But it also means if the items within are small, the node is small too.
 
Last edited by a moderator:
The loose octree is a bit easier to work with dynamic geometry and just allows for some nifty optimisations, check the last email on http://tulrich.com/geekstuff/partitioning.html. It's not radically new or anything, but works fairly well in a number of cases.

For the particular visibility culling stuff I've done, a simple pre-calculated quadtree for static objects worked fine and was simple to implement, especially as the world-space was rather sparse object-wise along the Y-axis.
 
Ok that makes more sense.
I could see a number of corner cases where it would struggle, but then again there are corner cases for my one too. :)

If you stored the bounds for the items in the tree it would be a heck of a lot more efficient.

Pains me to say but it would be easier to maintain, however I'm inclined to believe intersection tests would be less efficient, but that would depend on the test. You'd absolutely need to store the bounds of the children to get decent performance. Especially with the extra gigantic nodes.

Node count gets pretty staggering pretty quick. 5 levels and your looking at 37449 :oops:



Sigh
 
Last edited by a moderator:
Back
Top