I would go with an octree like subdivision of space. Start out with the root node of the octree which contains the whole sphere. Then subdivide this node (the box in your case) into eight nodes which in sum are containing the same space as the root node. Repeat this until your target approximation is reached. You can very easily check if one node is inside the sphere or outside of it by calculating the distance to the center of the sphere. At the target subdivision level only take the nodes which are inside of the sphere which you want to approximate.

stefan

On Wed, Mar 11, 2009 at 5:02 PM, Jon Valdés <juanval@gmail.com> wrote:
The only restriction for the shape is that it should _look_ as close to
a sphere as possible. Volume and such is not really important in this
case. So I guess minimizing distance to the sphere surface is what I'm
looking for.

Regards,
   Jon Valdés

Osman, Brian wrote:
> Is there a restriction that the approximation must be conservative (eg, fully contained within the sphere)? The actual solution might depend on what error you're trying to minimize. It might not be obvious, but if the goal is to match the sphere's volume, then having some of the AABBs extend beyond the bounds of the sphere will let you match the volume (or maximum distance to the surface) with fewer boxes.
>
> -Brian
>
> -----Original Message-----
> From: Jon Valdés [mailto:juanval@gmail.com]
> Sent: Wednesday, March 11, 2009 11:02 AM
> To: Game Development Algorithms
> Subject: Re: [Algorithms] Aproximating a sphere with boxes
>
> The use of AABs is a restriction I cannot avoid, because of the way the
> world works. It's not just for collision detection, but the hole world
> is formed with AABs.
> For a video of this thing in action: http://www.vimeo.com/3565879
>
> So, oriented boxes are not a viable option in this case, I'm afraid.
>
> What I'm trying to do here is creating holes with a more or less
> spherical shape, although it will certainly still be formed of small
> boxes. And if I can create the spherical holes with fewer boxes, so much
> better.
>
> Regards,
>     Jon Valdés
>
>
> Chris Jenner wrote:
>> If you want to describe a sphere with a number of axis aligned boxes then you will need a lot of small boxes.  The number will depend on how accurately you want to describe the sphere, compared with how large the sphere is.  You cannot escape this, it comes from trying to use a description of the world that does not fit the world itself.
>>
>> Use oriented boxed and you would need far fewer.
>>
>> Use a sphere and you would need one.
>>
>> Chris.
>>
>>> -----Original Message-----
>>> From: Jon Valdés [mailto:juanval@gmail.com]
>>> Sent: Wednesday, March 11, 2009 12:31 PM
>>> 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" <juanval@gmail.com>
>>>> To: "Game Development Algorithms" <gdalgorithms-
>>> list@lists.sourceforge.net>
>>>> 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@lists.sourceforge.net
>>>>> 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@lists.sourceforge.net
>>>> 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@lists.sourceforge.net
>>> 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@lists.sourceforge.net
>> 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@lists.sourceforge.net
> 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@lists.sourceforge.net
> 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@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



--
--
Stefan Daenzer
Wilhelmstr. 16
48149 Muenster

Tel.: +49-176-61157550

"Work like you don't need the money, love like you've never been hurt and dance like no one is watching." - Randall G Leighton