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 equalsized. These would represent your volume. When
you split the geometry by a plane, you simply dotproduct 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 <alenlml@...> 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
>> polygonsoup. It is not trivial, but it not overly complex either. And
>> from the resulting polygonsoup 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 30Day
>>> 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/bobjjuly
>>> _______________________________________________
>>> GDAlgorithmslist mailing list
>>> GDAlgorithmslist@...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist
>>>
>>
>> 
>> Best regards,
>> Alen mailto:alenlml@...
>>
>>
>>
>
> 
> Let Crystal Reports handle the reporting  Free Crystal Reports 2008 30Day
> 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/bobjjuly
> _______________________________________________
> GDAlgorithmslist mailing list
> GDAlgorithmslist@...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithmslist
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithmslist
>
>
