## Re: [Algorithms] Aproximating a sphere with boxes

 Re: [Algorithms] Aproximating a sphere with boxes From: Jon Watte - 2009-03-11 20:56:14 ```Jon Valdés wrote: > Yesterday I tried something similar using fixed-width slices, but I > couldn't get my head around filling the space left by them... But this > looks good. Filling a central cube, and then recursively adding smaller > slices on each side seems like a good way to go about it. Not sure if > that'd have the smallest possible box count, but it looks promising. > If the boxes can overlap, you can use symmetry to cut the number of extra boxes in half by running them through the center and out the other end. Sincerely, jw ```

### Thread view

 Re: [Algorithms] Aproximating a sphere with boxes From: Julian Alden-Salter - 2009-03-11 13:21:35 ```Surely you could use the algorithm to form flat box slices through the sphere? Which is what you'd actually want for collision purposes? You could probably use the 45 degree point to create a larger box and add flat slices to define the 'detail' slices on each face to approximate the sphere. -----Original Message----- From: Jon Valdés [mailto:juanval@...] Sent: 11 March 2009 12:31 To: Game Development Algorithms Subject: Re: [Algorithms] Aproximating a sphere with boxes Yes, the shape of the final set of boxes could be calculated like that without much fuzz, but this would leave me with lots of small boxes. My main problem is finding a way to shape the sphere with as few boxes as possible... and if it can be done in a fast way, even better. Thanks, Jon Valdés James Robertson wrote: > Could you not use a variation of the midpoint circle algorithm > (http://tinyurl.com/cppase) to calculate the box edges over a low resoultion > grid? It should be fairly trivial to expand the calculated points into > three dimensions. > > James > > > ----- Original Message ----- > From: "Jon Valdés" > To: "Game Development Algorithms" > Sent: Wednesday, March 11, 2009 12:50 PM > Subject: [Algorithms] Aproximating a sphere with boxes > > >> Hi there, >> >> I'm working with axis-aligned boxes, and I'm trying to aproximate a >> solid sphere with them, using as few boxes as possible. Think of it as >> trying to build a sphere with LEGO blocks of different sizes, trying to >> use only as few pieces as you can. >> >> Of course, the boxes, just like LEGO blocks, have a certain minimum >> size, or else you could always keep adding smaller and smaller boxes >> trying to fill the sphere. >> >> So, do you know of any tips or algorithms to do this? >> >> (I'm hoping it's not NP-hard or something...) >> >> Thanks in advance >> >> Regards, >> Jon Valdés >> >> ------------------------------------------------------------------------------ >> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are >> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and >> easily build your RIAs with Flex Builder, the Eclipse(TM)based development >> software that enables intelligent coding and step-through debugging. >> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDAlgorithms-list@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are > powering Web 2.0 with engaging, cross-platform capabilities. Quickly and > easily build your RIAs with Flex Builder, the Eclipse(TM)based development > software that enables intelligent coding and step-through debugging. > Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are powering Web 2.0 with engaging, cross-platform capabilities. Quickly and easily build your RIAs with Flex Builder, the Eclipse(TM)based development software that enables intelligent coding and step-through debugging. Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list *********** IMPORTANT INFORMATION Information and any attached documentation from Blitz Games Studios Limited (including its divisions: Blitz Games, Volatile Games, Blitz Arcade, TruSim & BlitzTech) is intended for the use of the addressee only and may contain confidential information. If you are not the intended recipient please delete this email and notify us immediately. Please note that without the prior written consent of Blitz Games Studios Limited any form of distribution, copying or use of this email or the information in it is strictly prohibited and may be unlawful. Attachments to this email may accidentally contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any attachments before they are opened. Any formal offer contained in this email is subject to the standard terms & conditions of Blitz Games Studios Limited and must be signed by both parties. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Blitz Games Studios Limited. Blitz Games Studios Limited is registered in England (company no: 2482913). Its registered address is Regent Square House, The Parade, Leamington Spa, Warwickshire, CV32 4NL, UK *********** ```
 Re: [Algorithms] Aproximating a sphere with boxes From: Jon Valdés - 2009-03-11 14:45:42 ```Yesterday I tried something similar using fixed-width slices, but I couldn't get my head around filling the space left by them... But this looks good. Filling a central cube, and then recursively adding smaller slices on each side seems like a good way to go about it. Not sure if that'd have the smallest possible box count, but it looks promising. Thanks for the idea :) Regards, Jon Valdés Julian Alden-Salter wrote: > Surely you could use the algorithm to form flat box slices through the sphere? Which is what you'd actually want for collision purposes? You could probably use the 45 degree point to create a larger box and add flat slices to define the 'detail' slices on each face to approximate the sphere. > > -----Original Message----- > From: Jon Valdés [mailto:juanval@...] > Sent: 11 March 2009 12:31 > To: Game Development Algorithms > Subject: Re: [Algorithms] Aproximating a sphere with boxes > > Yes, the shape of the final set of boxes could be calculated like that > without much fuzz, but this would leave me with lots of small boxes. > > My main problem is finding a way to shape the sphere with as few boxes > as possible... and if it can be done in a fast way, even better. > > Thanks, > Jon Valdés > > James Robertson wrote: >> Could you not use a variation of the midpoint circle algorithm >> (http://tinyurl.com/cppase) to calculate the box edges over a low resoultion >> grid? It should be fairly trivial to expand the calculated points into >> three dimensions. >> >> James >> >> >> ----- Original Message ----- >> From: "Jon Valdés" >> To: "Game Development Algorithms" >> Sent: Wednesday, March 11, 2009 12:50 PM >> Subject: [Algorithms] Aproximating a sphere with boxes >> >> >>> Hi there, >>> >>> I'm working with axis-aligned boxes, and I'm trying to aproximate a >>> solid sphere with them, using as few boxes as possible. Think of it as >>> trying to build a sphere with LEGO blocks of different sizes, trying to >>> use only as few pieces as you can. >>> >>> Of course, the boxes, just like LEGO blocks, have a certain minimum >>> size, or else you could always keep adding smaller and smaller boxes >>> trying to fill the sphere. >>> >>> So, do you know of any tips or algorithms to do this? >>> >>> (I'm hoping it's not NP-hard or something...) >>> >>> Thanks in advance >>> >>> Regards, >>> Jon Valdés >>> >>> ------------------------------------------------------------------------------ >>> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are >>> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and >>> easily build your RIAs with Flex Builder, the Eclipse(TM)based development >>> software that enables intelligent coding and step-through debugging. >>> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> GDAlgorithms-list@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> >> ------------------------------------------------------------------------------ >> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are >> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and >> easily build your RIAs with Flex Builder, the Eclipse(TM)based development >> software that enables intelligent coding and step-through debugging. >> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDAlgorithms-list@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are > powering Web 2.0 with engaging, cross-platform capabilities. Quickly and > easily build your RIAs with Flex Builder, the Eclipse(TM)based development > software that enables intelligent coding and step-through debugging. > Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > *********** > > IMPORTANT INFORMATION > > Information and any attached documentation from Blitz Games Studios Limited (including its divisions: Blitz Games, Volatile Games, Blitz Arcade, TruSim & BlitzTech) is intended for the use of the addressee only and may contain confidential information. > > If you are not the intended recipient please delete this email and notify us immediately. > > Please note that without the prior written consent of Blitz Games Studios Limited any form of distribution, copying or use of this email or the information in it is strictly prohibited and may be unlawful. > > Attachments to this email may accidentally contain software viruses. You are advised to take all reasonable precautions to minimise this risk and to carry out a virus check on any attachments before they are opened. > > Any formal offer contained in this email is subject to the standard terms & conditions of Blitz Games Studios Limited and must be signed by both parties. Any views or opinions expressed are solely those of the author and do not necessarily represent those of Blitz Games Studios Limited. > > Blitz Games Studios Limited is registered in England (company no: 2482913). Its registered address is Regent Square House, The Parade, Leamington Spa, Warwickshire, CV32 4NL, UK > > *********** > > > ------------------------------------------------------------------------------ > Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are > powering Web 2.0 with engaging, cross-platform capabilities. Quickly and > easily build your RIAs with Flex Builder, the Eclipse(TM)based development > software that enables intelligent coding and step-through debugging. > Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Aproximating a sphere with boxes From: Jon Watte - 2009-03-11 20:56:14 ```Jon Valdés wrote: > Yesterday I tried something similar using fixed-width slices, but I > couldn't get my head around filling the space left by them... But this > looks good. Filling a central cube, and then recursively adding smaller > slices on each side seems like a good way to go about it. Not sure if > that'd have the smallest possible box count, but it looks promising. > If the boxes can overlap, you can use symmetry to cut the number of extra boxes in half by running them through the center and out the other end. Sincerely, jw ```