Re: Depth-Sorting Axis-Aligned Boxes

You may be over thinking it.

Non overlapping convex polyhedra are usually correctly sorted using their
centroids, assuming they are of similar volume.  Along the way, if you
generate a axis aligned bounding box in camera space for each one, you can
detect the groups of objects that violate the simple sort + use a more
expensive algorithm like a kd tree without feeling dirty since the sets
will be small.

The neat thing is that you only need to use the spatial data structure to
"discover" the sort order, since certain classes of geometry sets (AABB's
in particular) can be rendered correctly without splits.

Also, if you always keep track of the "last sort", you can get the next
sort order very quickly since it will usually only diverge a little bit.

-john

-----Original Message-----
From: metanet software [mailto:[email protected]]
Sent: Monday, August 03, 2009 1:32 PM
To: Game Development Algorithms
Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes


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

I just realized you must have been referring to how the blue box was
within the extents of the red shape; in this case the red shape would be
modeled as three boxes (top and sides are all separate AABBs of minimum
thickness).





--- On Mon, 8/3/09, metanet software <[email protected]> wrote:

> From: metanet software <[email protected]>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: "Game Development Algorithms"
<[email protected]>
> Received: Monday, August 3, 2009, 3:15 PM
>
> > 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, [email protected]
> <[email protected]>
> wrote:
>
> > From: [email protected]
> <[email protected]>
> > Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned
> Boxes
> > To: [email protected],
> "Game Development Algorithms" <[email protected]>
> > 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
> > [email protected]
> > 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/
>
>
--------------------------------------------------------------------------
----
> 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
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
>
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>


      __________________________________________________________________
Be smarter than spam. See how smart SpamGuard is at giving junk email the
boot with the All-new Yahoo! Mail.  Click on Options in Mail and switch to
New Mail today or register for free at http://mail.yahoo.ca

--------------------------------------------------------------------------
----
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

------------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list