iDevGames Forums
On visibility culling and 2d physics engines - Printable Version

+- iDevGames Forums (
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: On visibility culling and 2d physics engines (/thread-8728.html)

On visibility culling and 2d physics engines - TomorrowPlusX - Mar 15, 2011 06:08 PM

So, I've written my share of quadtrees, octrees, and spatial hashes. But as I'm considering visibility culling for my game, it seems like I might as well take advantage of chipmunk's existing spatial hash, as well as chipmunk's knowledge of the "things" in my game, moving and static.

Is it a good idea to simply make a box collider in world space which corresponds to my viewport and run collision queries against it to determine my visible set?

If it's not a good idea, why not?

I mean, I'm ready and able to write a quadtree or spatial hash and keep it up to date with my game objects, but it seems like the physics engine already has that knowledge, and, frankly, the odds are chipmunk's code is faster and better tested than mine.

RE: On visibility culling and 2d physics engines - Skorche - Mar 16, 2011 07:47 AM

I've thought about this a bunch actually. You can use cpSpaceQuery() to find shapes overlapping a certain rectangle. (apparently I've forgotten to document rectangle and shape queries, whoops) Check the cpSpace.h header. It's just a simple callback driven iterator.

For one, querying the collision shapes requires that the graphics for them match exactly. If they don't then you would need to keep a second, separate spatial index to do visibility culling. While this would allow you to accelerate static queries, reindexing all the dynamic objects a second time would be more expensive than just checking individual bounding boxes against the viewing volume. Unless there is some sort of extra fancy pants temporal coherence structure that I've never heard of that would let you get better than linear performance. I sort of doubt it though.

The API for the spatial indexing in Chipmunk is generic and works with more than just Chipmunk shapes. The API is fairly simple, but has never been documented, and it's changing for version 6 to add more spatial indexes than just spatial hashing.

Anyway, that was a lot of babbling. I think what I would do in a similar situation would be to just build a simple fixed sized grid with the static geometry in it and compare simple bounding volumes of the dynamic geometry with the view volume. It's simple to implement, and I don't really think it's possible to make the performance substantially better anyway.