Re: [Algorithms] Area of convex shape inside of a BSP tree

[Jason H. <jh...@st...>]

Since you're not looking for precision, there's a hacky solution that 
might send you off in a fruitful direction (or not).  You could do a 
little preprocessing to pack a bunch of spheres inside your level 
geometry that are equal-sized.  These would represent your volume.  When 
you split the geometry by a plane, you simply dot-product each sphere to 
see if it's on one side or the other.  You can trade off performance vs. 
precision by having more or less spheres. 

The volume of spheres won't be correct, but they're representative of an 
equal portion.  You could figure out the actual volume of the geometry 
offline, then assign each sphere one share of that amount...  The point 
of using spheres is there are (many) algorithms to pack them in a space, 
and the dot product to determine side of a splitting plane is cheap.

Maybe a bad idea, but it's relatively runtime friendly.  :-)

JH

Jason Hughes
President
Steel Penny Games, Inc.
Austin, TX



Juan Linietsky wrote:
> Well, i was wondering about doing it realtime and without having to
> create polygons..
> but it doesn't sound so simple after all. I guess the fastest way to
> do it "correctly" is to traverse the BSP "save" the planes
> intersecting the polygon along the way. In the end i guess i'd end up
> with a set of convex objects delimited by the planes, but computing
> area from that seems a little expensive to me.
>
> Since what i need to know does not need to be super precise, I was
> thinking doing  something similar to a montecarlo method should be
> best, as in.. throwing N random points inside the convex volume i want
> to test against the BSP tree, and use them to traverse the BSP. At the
> end, the number of points inside vs outside should give me an
> approximation of the area taken up by the intersection.. but i was
> wondering if there could be a better way to do something like this.
>
> Juan Linietsky
>
> On Sun, Nov 8, 2009 at 7:21 PM, Alen Ladavac <ale...@cr...> wrote:
>   
>> Juan,
>>
>> There are ways to make a boolean intersection of two objects
>> represented by BSP trees and get the resulting volume in form of a
>> polygon-soup. It is not trivial, but it not overly complex either. And
>> from the resulting polygon-soup you can determine volume or area of
>> the intersection. Is that what you need?
>>
>> Cheers,
>> Alen
>>
>>
>> Sunday, November 8, 2009, 5:41:57 PM, you wrote:
>>
>>     
>>> Hi! Here's another question about an algorithm i've been wondering
>>> since a few days, to implement an idea i had about interior
>>> rendering..
>>>       
>>> Basically, take a BSP tree of a closed, concave shape that encloses an
>>> area, and also a convex object (that provides a support function), how
>>> could the area of the convex object that is inside the concave object
>>> represented by a BSP tree be calculated?
>>> Finding if they intersect is easy, but it seems to me that calculating
>>> how much of the convex object is inside the BSP tree area is not so
>>> simple.. but maybe i'm missing something?
>>> Also maybe there is another structure that best fits this problem than
>>> a BSP tree?
>>>       
>>> Cheers
>>>       
>>> Juan Linietsky
>>>       
>>> ------------------------------------------------------------------------------
>>> 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
>>>       
>>
>> --
>> Best regards,
>>  Alen                            mailto:ale...@cr...
>>
>>
>>     
>
> ------------------------------------------------------------------------------
> 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
>
>