gdalgorithms-list

[Algorithms] Course notes for Siggraph '09

[Jon G. <jon...@rc...>]

Hopefully this isn't considered off topic, but would anyone know if the
course notes for Advances in Real-Time Rendering in 3D Graphics and Games
have been posted anywhere?  I noticed that the notes for the Beyond
Programmable Shading were all posted here: http://s09.idav.ucdavis.edu/, for
example.

 

Thanks,

 

Jon

Re: [Algorithms] Image compression

[Richard F. <ra...@gm...>]

nice links, thanks. Makes me think that approaching the compression of
images by blocks is a coders dream but not good for quality. I'm rethinking
the approach for non power of two images and trying to do it without using
blocks at all.

2009/8/7 metanet software <met...@ya...>

>
> Some of CBloom's blog notes might be of interest to you, here are some
> recent ones that are relevant:
>
> http://cbloomrants.blogspot.com/2009/02/02-19-09-png-sucks.html
>
> http://cbloomrants.blogspot.com/2009/05/05-13-09-image-compression-rambling.html
>
> http://cbloomrants.blogspot.com/2009/05/05-14-09-image-compression-rambling.html
>
> http://cbloomrants.blogspot.com/2009/07/07-06-09-small-image-compression-notes.html
>
> http://cbloomrants.blogspot.com/2009/07/07-07-09-small-image-compression-notes.html
>
>
>
>
> --- On Fri, 8/7/09, Richard Fabian <ra...@gm...> wrote:
>
> > From: Richard Fabian <ra...@gm...>
> > Subject: [Algorithms] Image compression
> > To: "Game Development Algorithms" <
> gda...@li...>
> > Received: Friday, August 7, 2009, 6:41 AM
> > Not sure if i'm reinventing the wheel
> > here, but I've been working on
> > an in house image compressor for our DS games, and had an
> > idea that i
> > thought was a novel approach to solving the lossy
> > compression problem.
> >
> > I started with DCTs (which were terribly slow on the DS, so
> > were soon
> > discouraging), then tried wavelets, which did provide a
> > great speed
> > increase, and good image quality, but after working with
> > them for a
> > while i had the idea that maybe what we need to encode is
> > the terrain
> > of the image. not the two distinct 1D signals.
> >
> > So, with the idea of "doing it in 2D" in mind, i tried to
> > develop an
> > algorithm that instead of taking the differences between
> > pixels, it
> > assumes that the pixels are part of a larger image and
> > starts from an
> > assumption that anything other than the predicted value of
> > a pixel is
> > notable. I took the vertical gradient, horizontal gradient,
> > and the
> > _saddle_ (diagonal difference / Determinant), and these
> > were then the
> > values recorded for later use in the compression. This 2D
> > approach
> > made a small but significant difference in the
> > compressability of the
> > image over wavelets, but I'm not brilliant at compression,
> > just not
> > incompetent, so I requested the right to start a
> > source-forge project
> > based on the library so that all the other games developers
> > could both
> > benefit and help me make this fast and quite good
> > compressor into
> > something really cool for us all to use.
> >
> > https://sourceforge.net/projects/mergelet/
> >
> > Sorry that my code is a bit wandery in places, and I don't
> > use
> > comments much, I tend to comment with variable names and
> > structure of
> > code instead.
> >
> > Also, I'm new to source-forge, so don't know how everything
> > works yet.
> >
> > --
> > fabs();
> > Just because the world is full of people that think just
> > like you,
> > doesn't mean the other ones can't be right.
> >
> >
> ------------------------------------------------------------------------------
> > 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
> >
>
>
>      __________________________________________________________________
> Make your browsing faster, safer, and easier with the new Internet
> Explorer® 8. 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
>



-- 
fabs();
Just because the world is full of people that think just like you, doesn't
mean the other ones can't be right.

Re: [Algorithms] Image compression

[Richard F. <ra...@gm...>]

oddly, I'm seeing better than DCT ratios. However there is something wrong
with my code as I'm not getting the same ratios as Photoshop with a JPEG
export of the same image. Can't be sure where I'm going wrong. I though it
was the huffman encoding and tried to implement jpeg standard encoder, but
found that once I had it in, it made no difference, funnily enough, my
(supposedly) naive approach to huffman encoding the DCT quantised
coefficients was bit-wise identical to the JPEG standard approach.

I recently found that some improvements in image quality can be obtained by
bleeding the colour data across any black (or very dark) colours before
compressing, thus improving the colour values of chromal sections. I wonder
if this would work even better if i included white out too?

2009/8/7 Jon Watte <jw...@gm...>

> Richard Fabian wrote:
> > notable. I took the vertical gradient, horizontal gradient, and the
> > _saddle_ (diagonal difference / Determinant), and these were then the
> > values recorded for later use in the compression. This 2D approach
> > made a small but significant difference in the compressability of the
> >
>
> Isn't that basically a lifting process, based on a 2D predicted value?
> For previous approaches, I believe that the good-old lossless JPEG
> method used almost exactly that pre-process to determine deltas, and
> then used an entropy coder to code the deltas (instead of treating the
> deltas as something to separately compress using wavelets or whatever).
> What kind of compression ratios are you seeing now, btw? And have you
> tried the smaller/embedded profiles of JPEG 2000 for comparison?
>
> Sincerely,
>
> jw
>
>
>
> --
>
>  Revenge is the most pointless and damaging of human desires.
>
>
>
> ------------------------------------------------------------------------------
> 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
>



-- 
fabs();
Just because the world is full of people that think just like you, doesn't
mean the other ones can't be right.

Re: [Algorithms] Image compression

[Jon W. <jw...@gm...>]

Richard Fabian wrote:
> notable. I took the vertical gradient, horizontal gradient, and the
> _saddle_ (diagonal difference / Determinant), and these were then the
> values recorded for later use in the compression. This 2D approach
> made a small but significant difference in the compressability of the
>   

Isn't that basically a lifting process, based on a 2D predicted value? 
For previous approaches, I believe that the good-old lossless JPEG 
method used almost exactly that pre-process to determine deltas, and 
then used an entropy coder to code the deltas (instead of treating the 
deltas as something to separately compress using wavelets or whatever).
What kind of compression ratios are you seeing now, btw? And have you 
tried the smaller/embedded profiles of JPEG 2000 for comparison?

Sincerely,

jw



-- 

  Revenge is the most pointless and damaging of human desires.

Re: [Algorithms] Image compression

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

Some of CBloom's blog notes might be of interest to you, here are some recent ones that are relevant:

http://cbloomrants.blogspot.com/2009/02/02-19-09-png-sucks.html
http://cbloomrants.blogspot.com/2009/05/05-13-09-image-compression-rambling.html
http://cbloomrants.blogspot.com/2009/05/05-14-09-image-compression-rambling.html
http://cbloomrants.blogspot.com/2009/07/07-06-09-small-image-compression-notes.html
http://cbloomrants.blogspot.com/2009/07/07-07-09-small-image-compression-notes.html




--- On Fri, 8/7/09, Richard Fabian <ra...@gm...> wrote:

> From: Richard Fabian <ra...@gm...>
> Subject: [Algorithms] Image compression
> To: "Game Development Algorithms" <gda...@li...>
> Received: Friday, August 7, 2009, 6:41 AM
> Not sure if i'm reinventing the wheel
> here, but I've been working on
> an in house image compressor for our DS games, and had an
> idea that i
> thought was a novel approach to solving the lossy
> compression problem.
> 
> I started with DCTs (which were terribly slow on the DS, so
> were soon
> discouraging), then tried wavelets, which did provide a
> great speed
> increase, and good image quality, but after working with
> them for a
> while i had the idea that maybe what we need to encode is
> the terrain
> of the image. not the two distinct 1D signals.
> 
> So, with the idea of "doing it in 2D" in mind, i tried to
> develop an
> algorithm that instead of taking the differences between
> pixels, it
> assumes that the pixels are part of a larger image and
> starts from an
> assumption that anything other than the predicted value of
> a pixel is
> notable. I took the vertical gradient, horizontal gradient,
> and the
> _saddle_ (diagonal difference / Determinant), and these
> were then the
> values recorded for later use in the compression. This 2D
> approach
> made a small but significant difference in the
> compressability of the
> image over wavelets, but I'm not brilliant at compression,
> just not
> incompetent, so I requested the right to start a
> source-forge project
> based on the library so that all the other games developers
> could both
> benefit and help me make this fast and quite good
> compressor into
> something really cool for us all to use.
> 
> https://sourceforge.net/projects/mergelet/
> 
> Sorry that my code is a bit wandery in places, and I don't
> use
> comments much, I tend to comment with variable names and
> structure of
> code instead.
> 
> Also, I'm new to source-forge, so don't know how everything
> works yet.
> 
> -- 
> fabs();
> Just because the world is full of people that think just
> like you,
> doesn't mean the other ones can't be right.
> 
> ------------------------------------------------------------------------------
> 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
> 


      __________________________________________________________________
Make your browsing faster, safer, and easier with the new Internet Explorer® 8. Optimized for Yahoo! Get it Now for Free! at http://downloads.yahoo.com/ca/internetexplorer/

[Algorithms] Image compression

[Richard F. <ra...@gm...>]

Not sure if i'm reinventing the wheel here, but I've been working on
an in house image compressor for our DS games, and had an idea that i
thought was a novel approach to solving the lossy compression problem.

I started with DCTs (which were terribly slow on the DS, so were soon
discouraging), then tried wavelets, which did provide a great speed
increase, and good image quality, but after working with them for a
while i had the idea that maybe what we need to encode is the terrain
of the image. not the two distinct 1D signals.

So, with the idea of "doing it in 2D" in mind, i tried to develop an
algorithm that instead of taking the differences between pixels, it
assumes that the pixels are part of a larger image and starts from an
assumption that anything other than the predicted value of a pixel is
notable. I took the vertical gradient, horizontal gradient, and the
_saddle_ (diagonal difference / Determinant), and these were then the
values recorded for later use in the compression. This 2D approach
made a small but significant difference in the compressability of the
image over wavelets, but I'm not brilliant at compression, just not
incompetent, so I requested the right to start a source-forge project
based on the library so that all the other games developers could both
benefit and help me make this fast and quite good compressor into
something really cool for us all to use.

https://sourceforge.net/projects/mergelet/

Sorry that my code is a bit wandery in places, and I don't use
comments much, I tend to comment with variable names and structure of
code instead.

Also, I'm new to source-forge, so don't know how everything works yet.

-- 
fabs();
Just because the world is full of people that think just like you,
doesn't mean the other ones can't be right.

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

[Alen L. <ale...@cr...>]

metanet wrote at 8/4/2009:
> I'm unclear about what exactly the view direction *is* for this
> sort of perspective;

Perhaps you should do an inverse projection of Z axis by the
projection matrix to find that out?

Alen

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

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

> 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) <Mat...@2k...> wrote:

> From: Mathi Nagarajan (2K Australia) <Mat...@2k...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: ra...@ha..., "Game Development Algorithms" <gda...@li...>
> 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: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/
> 
> ------------------------------------------------------------------------------
> 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

[Mathi N. (2K Australia) <Mat...@2k...>]

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/

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

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

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

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

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

[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

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

> If what's stopping you from using a ZBuffer is memory or
> performance,you can try a span-list based system

Unfortunately the problem is the platform: Flash. This means I don't have access to the pixels directly if I want to use the flashplayer's rendering system.

In theory I could write a z-buffer or span-list system in Actionscript, however this would require circumventing Flash's built-in renderer and writing my own (on top of the basic get/set pixel commands). I suspect this would be hellishly slow, but if that's the only solution I guess it's worth trying.


> How many different camera angles will you be viewing from?  Also, by
> sprites, do you mean quads in 3-space, or something more like point
> sprites

The camera angle will be fixed (pointing along z) but will translate in x and y. By "sprites" I mean something close to GBA: 2D images you can translate/rotate/scale, but not anything as general as a textured quad; if I had access to textured polygons, I could conceivably build a BSP each frame and split each quad into pieces.


This is looking more and more grim! :(

thanks again,
raigan



--- On Mon, 8/3/09, Bert Peers <be...@bp...> wrote:

> From: Bert Peers <be...@bp...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: ra...@ha..., "Game Development Algorithms" <gda...@li...>
> Received: Monday, August 3, 2009, 9:56 AM
> metanet software schreef:
> >> Unfortunately, this is the classic polygon sorting
> problem.
> > 
> > This is what I was afraid of; aside from the cost of
> building a BSP every frame, the more fundamental problem is
> that the graphics are sprites and not really amenable to
> arbitrary splitting. I was hoping in the worst case that I
> could split them up to have one sprite per face (top, front,
> side, etc), but it would appear that even that is too
> coarse.
> > 
> > So, I'm screwed?
> 
> If what's stopping you from using a ZBuffer is memory or
> performance,
> you can try a span-list based system; at every scanline,
> you keep track
> of which poly's overlap it, then you analytically compute
> the spans of
> pixels that are visible due to every polygon edge or
> intersection.
> See quake1.  If the sprites in turn have an alpha
> mask, you can still
> make it work by converting the sprites into several spans
> (ie. RLE
> compression; see, uh, 'Divinity').
> 
> 
> bert
> 
> ------------------------------------------------------------------------------
> 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
> 


      __________________________________________________________________
Yahoo! Canada Toolbar: Search from anywhere on the web, and bookmark your favourite sites. Download it now
http://ca.toolbar.yahoo.com.

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

[Bert P. <be...@bp...>]

metanet software schreef:
>> Unfortunately, this is the classic polygon sorting problem.
> 
> This is what I was afraid of; aside from the cost of building a BSP every frame, the more fundamental problem is that the graphics are sprites and not really amenable to arbitrary splitting. I was hoping in the worst case that I could split them up to have one sprite per face (top, front, side, etc), but it would appear that even that is too coarse.
> 
> So, I'm screwed?

If what's stopping you from using a ZBuffer is memory or performance,
you can try a span-list based system; at every scanline, you keep track
of which poly's overlap it, then you analytically compute the spans of
pixels that are visible due to every polygon edge or intersection.
See quake1.  If the sprites in turn have an alpha mask, you can still
make it work by converting the sprites into several spans (ie. RLE
compression; see, uh, 'Divinity').


bert

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

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

> Unfortunately, this is the classic polygon sorting problem.

This is what I was afraid of; aside from the cost of building a BSP every frame, the more fundamental problem is that the graphics are sprites and not really amenable to arbitrary splitting. I was hoping in the worst case that I could split them up to have one sprite per face (top, front, side, etc), but it would appear that even that is too coarse.

So, I'm screwed?

raigan




--- On Mon, 8/3/09, Mike Welsh <mw...@gm...> wrote:

> From: Mike Welsh <mw...@gm...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: "Game Development Algorithms" <gda...@li...>
> Received: Monday, August 3, 2009, 1:00 AM
> 
> 
> On Mon, Aug 3, 2009 at 12:05 AM,
> metanet software <met...@ya...>
> wrote:
> 
> 
> I've attached an example demonstrating what I'd
> like to achieve: the scene is made of 9 faces (3 objects of
> 3 faces each), a green box resting on a red
> "desk", underneath which there's a blue box.
> 
> 
> Unfortunately, this is the classic polygon sorting problem.
> Even with the constraint of axis-aligned faces, I don't
> think you can find a solution that works for every case
> without splitting polygons using BSP or other trickery.
> I've attached a terrible diagram of a case where no sort
> order can produce the correct result.
> 
> 
> Take care,-- 
> Michael Welsh
> mw...@gm...
> 
> 
> 
> -----Inline Attachment Follows-----
> 
> ------------------------------------------------------------------------------
> 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
> -----Inline Attachment Follows-----
> 
> _______________________________________________
> 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

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

I've attached an example demonstrating what I'd like to achieve: the scene is made of 9 faces (3 objects of 3 faces each), a green box resting on a red "desk", underneath which there's a blue box.

As far as I can tell there's no sorting function based on camera-space position which works. Then again I'm a bit unclear about what camera-space is exactly for this type of parallel projection, since AFAICT the "camera" is a plane rather than a point (or, camera space is a cube rather than a frustum).

It's tempting to say "just sort along z, then y, then x" or something like that, but for such functions there are cases where it does the wrong thing. 

For instance it seems like sorting the faces based on the distance from their front-upper-right corner to the front-upper-right corner of the cameraspace cube might work, but it doesn't: all three green faces should appear in front of the top red face, but the top red face's corner is closer.

Is it even correct to choose a single point to represent the depth of a polygon? It seems like that alone is going to cause problems when there are polygons which extend across a wide range of depths..

Sorry if this is totally stupid and I'm missing something obvious! 

thanks again,
raigan






--- On Sun, 8/2/09, Sebastian Sylvan <seb...@gm...> wrote:

> From: Sebastian Sylvan <seb...@gm...>
> Subject: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
> To: "Game Development Algorithms" <gda...@li...>
> Cc: ra...@ha...
> Received: Sunday, August 2, 2009, 6:18 PM
> 
> 
> 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
> 
> 
> -----Inline Attachment Follows-----
> 
> ------------------------------------------------------------------------------
> 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
> -----Inline Attachment Follows-----
> 
> _______________________________________________
> 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


      __________________________________________________________________
Yahoo! Canada Toolbar: Search from anywhere on the web, and bookmark your favourite sites. Download it now
http://ca.toolbar.yahoo.com.

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

[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

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

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

[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] Lighting (HDR)

[Nathaniel H. <na...@io...>]

> To
> be honest, all three approaches (m+2)/(2pi), (m+8)/(8pi), and (m+2)/(8pi)
> have produced nice results for me, so it is basically down to what works
> visually for us I guess since they all seem to have some legitimate
> grounding in theory.

Well... if you are using Blinn-Phong (N.H), then dividing by (2pi) is
unambiguously wrong (it is correct for Phong - (R.V) - though). I agree
that the two with division by (8pi) both have theoretical legitimacy. Note
however that most game engines use units that cause the (pi) factor to be
removed, so you would just be dividing by 8.

Naty

Re: [Algorithms] Lighting (HDR)

[Joe M. <jo...@ga...>]

First, let me thank you guys for the interesting discussion surrounding the 
normalization factor and its derivations. In the end I've decided to go with 
Naty's suggestion and (continue) using the m+2 approach as indeed I am 
including an approximate geometry/visibility term of 1 / (4 * L.H^2) (i.e., 
Kelemen, Szirmay-Kalos) and treating the cosine power function as an NDF. To 
be honest, all three approaches (m+2)/(2pi), (m+8)/(8pi), and (m+2)/(8pi) 
have produced nice results for me, so it is basically down to what works 
visually for us I guess since they all seem to have some legitimate 
grounding in theory.

So with that bit of business pretty much wrapped up, that leaves me with 
just the outstanding issues on dynamic white point computation (vs. ditching 
it altogether) and practical advice on empirical vs. physically meaningful 
inputs for my direct light sources. Any insights on either of these two 
issues would of course be accepted gratefully.

Thanks again!

Joe