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

[metanet s. <met...@ya...>]

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

Sorry, I meant that in 3D the boxes wouldn't be interpenetrating, they would be separated or resting on each other; when projected onto the viewing plane they will almost definitely overlap -- hence the need to sort them somehow.


> 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).

I figured that a combination of using sweep-and-prune for broadphase collision detection, and the fact that all of the polygons are parallel to world planes (xy,xz, or yz), building a BSP would be simplified: we'd already have all the faces sorted in order along each axis, as well as knowing which pairs overlapped along which axes. 

Possibly "kd-tree" is a better description, since all the planes would be axis-aligned.

So far my fall-back plan is to use a head-on perspective as in SNES Zelda; this avoids the cyclical three-mutually-overlapping-faces problem. Sadly it doesn't really look or work as well when you're trying to depict depth :(

thanks again,
raigan





--- On Mon, 8/3/09, chr...@pl... <chr...@pl...> wrote:

> From: chr...@pl... <chr...@pl...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: ra...@ha..., "Game Development Algorithms" <gda...@li...>
> Received: Monday, August 3, 2009, 2:14 PM
> 
> 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
> 
> 
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal
> Reports 2008 30-Day 
> trial. Simplify your report design, integration and
> deployment - and focus on 
> what you do best, core application coding. Discover what's
> new with 
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
> 


      __________________________________________________________________
Looking for the perfect gift? Give the gift of Flickr! 

http://www.flickr.com/gift/