On visibility culling and 2d physics engines

Sage
Posts: 1,199
Joined: 2004.10
Post: #1
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.
Quote this message in a reply
Sage
Posts: 1,482
Joined: 2002.09
Post: #2
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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Bullet Physics Library / COLLADA physics viewer erwincoumans 14 12,765 Aug 12, 2006 12:59 AM
Last Post: Fenris
  Inheritage visibility in C++ ermitgilsukaru 13 6,347 Dec 9, 2005 09:44 PM
Last Post: zKing
  Collision Detection/Physics engines optomized for 2D? Joseph Duchesne 0 3,049 Jun 12, 2005 12:10 PM
Last Post: Joseph Duchesne