Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
Brought to you by:
vexxed72
Menu
▾
▴
Re: [Algorithms] Depth-Sorting Axis-Aligned Boxes
|
From: John K. <jke...@pa...> - 2009-08-03 23:49:53
|
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 |
