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

[Juan L. <re...@gm...>]

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...
>
>