Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes

[<chr...@pl...>]

Raigan wrote:
> Sadly I don't have a z-buffer, so I need to determine a way to sort
> the boxes back-to-front. The boxes will all be non-overlapping,
> although they may be touching, and will move smoothly (i.e not by
> grid-sized steps as is common in some games).

The picture you included in a subsequent post HAD the boxes
overlapping.


> Is there a simple solution to this problem? I.e a formula which
> considers the extents and/or a reference point on each box to
> produce a back-to-front order? Or am I stuck with the general
> solution: build a BSP tree?

Building a BSP tree makes sense for static geometry but perhaps
less for dynamic geometry (though you could merge dynamic objects
into a prebuilt static tree).

There's also Newell-Newell-Sancha:

http://en.wikipedia.org/wiki/Newell%27s_algorithm

which, from the limited description you gave, sounds like a
better option for you.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica