gdalgorithms-list

[Algorithms] Depth-Sorting Axis-Aligned Boxes

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

This is a variation of the famous "isometric depth-sorting" problem: I have a 3D scene composed of axis-aligned boxes, viewed with an oblique/cabinet perspective ( http://en.wikipedia.org/wiki/Oblique_projection ). 

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

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?

Would it help to consider individual faces rather than boxes? (It seems to me that this wouldn't help, since each face can be considered a box with size=0 along one axis).

Any suggestions or references would be most appreciated; all of the "isometric" stuff I've found via Google seems to be a big mess -- the algorithms which do work only work for objects which are all tile-sized and move in tile-sized increments.. which is just a special case of BSP (i.e the scene is essentially cut up by the grid).

thanks,
raigan


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

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

[Pablo de H. C. <pa...@vi...>]

I'm also interested in this. I had a look at the Inigo Quilez grid-aligned
approach but as I can see I can'tget it to work for "arbitrary" grids. In
that apporach he uses 48 pre-sorted directions which seems huge
but maybe there is a smart way of compressing that?

Here is the link to the article by Inigo:

http://iquilezles.org/www/articles/volumesort/volumesort.htm

All the best,

Pablo

On Sat, Aug 1, 2009 at 4:05 PM, metanet software <met...@ya...>wrote:

>
> This is a variation of the famous "isometric depth-sorting" problem: I have
> a 3D scene composed of axis-aligned boxes, viewed with an oblique/cabinet
> perspective ( http://en.wikipedia.org/wiki/Oblique_projection ).
>
> 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).
>
> 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?
>
> Would it help to consider individual faces rather than boxes? (It seems to
> me that this wouldn't help, since each face can be considered a box with
> size=0 along one axis).
>
> Any suggestions or references would be most appreciated; all of the
> "isometric" stuff I've found via Google seems to be a big mess -- the
> algorithms which do work only work for objects which are all tile-sized and
> move in tile-sized increments.. which is just a special case of BSP (i.e the
> scene is essentially cut up by the grid).
>
> thanks,
> raigan
>
>
>      __________________________________________________________________
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

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

[Richard M. <mi...@tr...>]

I may be missing something, but can't you just do a sort based on their 
furthest point along the camera axis?

i.e. transform into view space, then sort by furthest Z coordinate.

-- 
()()      Richard Mitton
( '.')
(")_(")       Beard Without Portfolio :: Treyarch


----- Original Message ----- 
From: "metanet software" <met...@ya...>
To: <gda...@li...>
Sent: Saturday, August 01, 2009 7:05 AM
Subject: [Algorithms] Depth-Sorting Axis-Aligned Boxes



This is a variation of the famous "isometric depth-sorting" problem: I have 
a 3D scene composed of axis-aligned boxes, viewed with an oblique/cabinet 
perspective ( http://en.wikipedia.org/wiki/Oblique_projection ).

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

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?

Would it help to consider individual faces rather than boxes? (It seems to 
me that this wouldn't help, since each face can be considered a box with 
size=0 along one axis).

Any suggestions or references would be most appreciated; all of the 
"isometric" stuff I've found via Google seems to be a big mess -- the 
algorithms which do work only work for objects which are all tile-sized and 
move in tile-sized increments.. which is just a special case of BSP (i.e the 
scene is essentially cut up by the grid).

thanks,
raigan


      __________________________________________________________________
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
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

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

[Pablo de H. C. <pa...@vi...>]

What I was referring to was not to have to redo this sorting each frame when
the camera moves orchanges direction. I am guessing the sorting problem is
already solved. It's the problem of not
having to re-sort, given the data is static of course. I might have misread
it though.
Pablo

On Sun, Aug 2, 2009 at 9:30 PM, Richard Mitton <mi...@tr...> wrote:

> I may be missing something, but can't you just do a sort based on their
> furthest point along the camera axis?
>
> i.e. transform into view space, then sort by furthest Z coordinate.
>

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

[Sebastian S. <seb...@gm...>]

On Sun, Aug 2, 2009 at 8:30 PM, Richard Mitton <mi...@tr...> wrote:

> I may be missing something, but can't you just do a sort based on their
> furthest point along the camera axis?
>
> i.e. transform into view space, then sort by furthest Z coordinate.


Also, the closest corner of the AABB will be the same for every AABB, so you
can just look at the camera direction once per frame, and compute which
"corner index" you need to check for each AABB.

-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862

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

[<chr...@pl...>]

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

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/

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.

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

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

[John K. <jke...@pa...>]

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