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

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

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:met...@ya...] 
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 <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/