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

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

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

Is this right? I *definitely* might be overthinking, but it seems like you could easily construct the classic "three mutually overlapping/overlapped sticks" out of AABBs.. which would imply that you _do_ need to split them in some cases. I'll attach an example of what I mean.

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

Yes, I'm hoping that I can somehow combine/piggyback the depth-sorting with the incremental sweep-and-prune for collision.

thanks,
raigan

--- On Mon, 8/3/09, John Ketchpaw <jke...@pa...> wrote:

> From: John Ketchpaw <jke...@pa...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: ra...@ha..., "Game Development Algorithms" <gda...@li...>
> Received: Monday, August 3, 2009, 7:22 PM
> 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:met...@ya...]
> 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 <met...@ya...>
> wrote:
> 
> > From: metanet software <met...@ya...>
> > Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned
> Boxes
> > To: "Game Development Algorithms"
> <gda...@li...>
> > 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, 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/
> >
> >
> --------------------------------------------------------------------------
> ----
> > 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
> >
> 
> 
>      
> __________________________________________________________________
> 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
> GDA...@li...
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

      __________________________________________________________________
The new Internet Explorer® 8 - Faster, safer, easier.  Optimized for Yahoo!  Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/