In order to make rendering, updating, and collision detection much more efficient, I'm looking in to quadtrees.
Does anyone have any good, detailed references on spatial indexing such as quadtrees, octrees, binary space partitions, etc. that also have well documented code and examples? I have found plenty, but none of them are really explained in detail or come with documented code. Mostly it's just "this is what <insert spatial index type here> is" and some sloppy uncommented and undocumented code. A nice book would also be helpful.
I am programming in java, any language would be fine, but preferably a C variant language or java.
Hm, that's for culling various kinds of stuff, right? I had a look at some of that sloppy, poorly commented code and now I'd like to know more about it myself.
yes it is used in view culling as well as various other things, like efficient collision detection in games.
QuadTrees are a type of spatial indexing, that makes queries into a 2d space very quick. so instead of having to test for collisions of an object against a "list" of all other objects, you would just make a query into the tree, and it would return a list of only the objects that might "possibly" come close to colliding with the area you specified in the query. this greatly reduces the amount of expensive collision detections needed.
Ive spent the past 3 days porting a quadtree implementation from C# to Java. Hopefully it works properly once its done and i build a test program. If not, I've gotten a handle on how a quadtree should work and how it should be implemented, and can build my own from scratch.
If you happen to find a good resource though, post it up.
If anyone is interested in the source code, i can package it up individually, as it is currently part of a bigger library that i am not ready to release yet.
After finishing i did some more research on spatial indexing and broadphase collision detection and learned that quadtrees may not even be the best solution, but is only one solution. It is still a very efficient solution but apparently under certain circumstances not the most efficient.
I am looking into a bunch of other spatial partitioning methods, and will try to see which ones are relevant and implement them myself.
Compared to normal list culling, where you simply cull objects based on being outside of the box before iterating over their collision mask, or like Clickteam uses, a total window culling that only has objects within a virtual frame be checked at all, or even against a binary tree culling, where you can sort the list of indexes into binary trees based on their coordinates and cull away as you search for a position, well, the only benefit of quadtrees I could see is if you're going to be using an application that has a very high amount of colliding objects (nodes) all within the same logical frame, where none are culled based on being 'offscreen', yet the dimensions are very large. I mean, tens of thousands of colliding objects at least- more than standard RTS games. If you're just blindly culling a list of objects from a box, thats only O(N^2) iterations in the worst case, which isn't exactly gamebreaking with only ~300 objects. Now if there were 5000, yes, it is.
I assume you are refering to Sweep and Prune algorithms?
Regardless of the size of the area that needs to be checked, Sweep and Prune is still less efficient. Im not quite sure how clickteam implements their checking, because it DOES do checks even offscreen.
A simple test of 1000 objects for colliding with every other object in a 640x480 area in mmf yields a frame rate of 6fps on my PC which drops to 0fps at 2000 objects. Now it may be a result of the overhead in mmf, but thats MASSIVELY low regardless. 1000 objects colliding in my java game framework using the quadtree implementation in the same size area runs at a framerate of about 61fps when capped at 60. at 2000 objects it drops to around 10-11 fps which is still a tenfold perfomance advantage on mmf, and still faster than mmf back at 1000 objects. There are still better Structures that handle clustering of large quantities of objects in small spaces better beyond quadtrees.
Another thing to note, its even worse in HWA mmf2. At 1000 objects its already running at 0fps and at 2000 objects it becomes unresponsive for short periods of time, in between which it runs at 0fps. I'm not sure of the implications but that sounds bad.
Even WITH the mmf2 overhead, the use of ANY sort of complex spatial indexing would greatly benefit the runtime. Perhaps even using smart code that decides what usage should be chosen at runtime based on play area size, and amount of colliding objects.
So i think you're wrong in saying that the only benefit is in large numbers of colliding objects. In My Opinion the methods used currently for checks are just a result of using old legacy code.
I'll post more when i implement my own Sweep and Prune, Uniform Grid, and Spatial Hashing(a grid based 1 dimensional spatial indexing structure), implementations. I want to look into Hilbert curves but they seem super complicated. Not something my brain was able to soak in when i was looking at it at 4am.
I am currently writing an octree implementation for my opengl engine (a view frustum culling algorithm). I have found that documentation of such algorithms is poor but they are one of those things where there is no defacto implementation, so people tend to mix ideas depending on the application. My research was basically a quick read over the wikipedia page. If you understand the basic principle it should be quite easy to come up with your own spatial indexing algorithm relying on elementary computer science theory. Stack overflow is full of questions on the topic and is probably a more appropriate place for a question that sits in mainstream programming and indeed computer science theory. If you are looking for books and none have been recommended already on stack overflow you may receive a reasonable response from someone there as well.
Spatial indexing in MMF would of course bring significant advantages, particularly with respect to texture management on mobile devices, but I doubt it's likely to enter the MMF2 runtime given the complications of dealing with legacy code. Hopefully the next version of MMF will provide the developers with enough scope to develop an efficient rendering engine which is primarily based on hardware acceleration and modern efficient rendering techniques, possibly with a fallback to software rendering where appropriate.
Advertisement
Post Reply
I consider myself decent at programming but I have no idea what you're talking about.
Edited by Cecilectomy
