What is a good practice for 2D scene graph partitioning for culling?

Question

I need to know an efficient way to cull the scene graph objects, to render exclusively the ones in the view, and as fast as possible.

I am thinking of doing it the following way, having in each object a local boundingbox which holds the object bounds, and a global boundingbox which holds the bounds of the object and all children.

When a camera is moved, the render list is updated by traversing the global boundingboxes. When only the object is being moved, it tries to enlarge or shrink the ancestors global boundingboxes, and in the end updating or not the renderlist.

What do you think of this approach? Do you think it will provide a fast and efficient culling?

Also, because the render list is a contiguous list, it could accelerate the rendering, right?

Any further tips for a 2D scene graphs are highly appreciated!

Answer 1

Can't comment either, heh.

I'm not sure a quad tree is the best solution. I believe quad trees (and oct trees in 3D) are typically used to sub-divide space for rendering and bounds checking of static geometry, and are pre-generated and accessed only at load-time. If I understand the question, Devil is looking for a way to do scene culling of dynamic geometry every frame at run-time. Having to re-calculate a quad tree every frame could get expensive.

If you are really looking for a way to just do view culling (as opposed to intelligent collision detection), have you tried simply checking for bounding rect intersection with the screen rect? This can be done relatively cheaply in screen coordinate space, even faster if you maintain a separate bounding rect in screen space for your dynamic objects and update only as necessary. This should work fine unless you have a great many objects on screen at once.

As for techniques of doing collision detection between dynamic objects, I have personally used the binning technique quite successfully in a 2D side-scrolling shooter. We tried using a dynamically-updated quad tree but took a pretty significant performance hit.

Answer 2

Cannot comment so will answer

I think what you are referring to is a QuadTree : http://en.wikipedia.org/wiki/Quadtree and from the article, it seems that this is a quick method. Looks also useful with regards to collision detection (a quick pass before going into the nitty gritty) as well as identifying appropriate culling.

Additionally useful for painter's algorithm because the leaves of the quadtree could be drawn last working from the root to the leaves - allowing back to front render and completing all the spatial information you need to draw correctly. So overall quite a lot of information and usefulness to store in one scene graph!

Answer 3

Scene graphs is a way to go. I recommend this gamedev thread.

Answer 4

The 3D variation of this question was asked recently: Scene Graph for Deferred Rendering Engine

I recommend a quadtree. Objects would typically best be represented by bounding boxes, rather than points (it always puzzles me that all the 'tutorials' seem to think games are made from point clouds). A node would contain four children - quadtree sub-nodes - and a list of those objects that straddle more than one child (which is way simpler than allowing objects to be in multiple nodes at once).

As items move they check to see if they are not fully-within their quadtree node's bounds and if not they remove themselves from their current node and then re-add themselves to the quadtree.

It is not uncommon to put projectiles and other very-fast-moving objects into a separate always-visit list or such, as adding and removing them constantly from the quadtree can hurt performance. An approach I favour though is adding the bounds of their flight in some number of game time steps to the quadtree. In this way they get moved around in the tree much more rarely, and they get found by all the nearest neighbour searches and such - this allows projectiles to actually hit things accidentally etc. It can dramatically simplify collision detection by not having several code paths and the interaction of several lists.

When rendering 3D you tend to want to draw front-to-back and opaque-then-transparent and in general this is true of 2D too, although you may know something about your artwork that lets you be less careful perhaps. So you take a frustum - or however you decide what is visible - and you cast this through your octree. This will be very fast.

You might want to hoist the list of currently visible items into the quadtree manager so that the frustum is painted onto the quadtree only when the camera moves, and bit-flags in the octree that track those sub-nodes that are fully-in-view or partially-in-view allow you to efficiently add and remove your visible items from the list.

At this point its all likely so blazingly fast - compared to your rendering cost - that you don't need to optimise it further with all the various special cases when moving things around and such, or deferred re-sorting of changing visibility lists and such.