Thread: Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: metanet s. <met...@ya...> - 2009-08-03 04:06:03
Attachments:
depth.jpg
|
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. |
|
From: metanet s. <met...@ya...> - 2009-08-04 02:41:14
Attachments:
overlap.jpg
|
> 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/ |
|
From: Mathi N. (2K Australia) <Mat...@2k...> - 2009-08-04 04:46:09
|
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/ |
|
From: metanet s. <met...@ya...> - 2009-08-04 14:03:35
|
> 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 |
|
From: Alen L. <ale...@cr...> - 2009-08-04 15:01:51
|
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 |
Thanks for helping keep SourceForge clean.
X