Re: Depth-Sorting Axis-Aligned Boxes

metanet software <[email protected]> Tue, 4 Aug 2009 07:03:24 -0700 (PDT)
Newsgroups	gmane.games.devel.algorithms
Message-ID	<[email protected]>
> Since you are using flash you could
> use masking capabilities.

Great, this definitely looks like a good solution; I've never actually used mask layers in any form (in the tool or via code) so I completely failed to consider them. Thanks!!


> 1. roughly sort all boxes using their centroid

I'm unclear about what exactly the view direction *is* for this sort of perspective; it can't be axis-aligned along z since three faces of an axis-aligned cube are visible, but worldspace x and y are parallel to screenspace x and y, which implies an axis-aligned view along z..?!

thanks,
raigan




--- On Tue, 8/4/09, Mathi Nagarajan (2K Australia) <[email protected]> wrote:

> From: Mathi Nagarajan (2K Australia) <[email protected]>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: [email protected], "Game Development Algorithms" <[email protected]>
> Received: Tuesday, August 4, 2009, 12:19 AM
> Since you are using flash you could
> use masking capabilities.
> 
> So in the example picture you provided, you could:
> 
> 1. render the dark grey object first with a mask that
> excludes the medium grey object (cos it is considered
> in-front of the current object)
> 2. render the medium grey object next with a mask that
> excludes the light grey object (cos it is considered
> in-front of the current object)
> 3. render the light grey object next with a mask that
> excludes the dark grey object (cos it is considered in-front
> of the current object)
> 
> In this case, only step 3 needs to use a mask, cos steps 1
> and 2 have their "front" objects rendered after them in
> sequence.
> 
> So this shows a simple approach:
> 1. roughly sort all boxes using their centroid (this is
> actually an optimization to minimize masking, you could use
> something more sophisticated to optimize further)
> 2. loop over each object from back to front 
>     2a. collect objects that are considered
> in front of the current object that have already been
> rendered
>     2b. build a mask excluding the collected
> "in-front" objects
>     2c. render the current object using the
> mask
> 
> I'm not that fluent with flash masking, but I think it can
> do that...
> 
> I'm relying on the property that you can render 2 convex
> non-intersecting objects sorted correctly without splitting
> either.
> 
> -----Original Message-----
> From: metanet software [mailto:[email protected]]
> 
> Sent: Tuesday, August 04, 2009 12:41 PM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> 
> > 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 <[email protected]>
> wrote:
> 
> > From: John Ketchpaw <[email protected]>
> > Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned
> Boxes
> > To: [email protected],
> "Game Development Algorithms" 
> > <[email protected]>
> > 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:[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
> >
> 
> 
>      
> __________________________________________________________________
> The new Internet Explorer® 8 - Faster, safer,
> easier.  Optimized for Yahoo!  Get it Now for
> Free! at http://downloads.yahoo.com/ca/internetexplorer/
> 
> ------------------------------------------------------------------------------
> 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