Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

## [Algorithms] Area of convex shape inside of a BSP tree

 [Algorithms] Area of convex shape inside of a BSP tree From: Juan Linietsky - 2009-11-08 16:42:12 ```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 ```

### Thread view

 [Algorithms] Area of convex shape inside of a BSP tree From: Juan Linietsky - 2009-11-08 16:42:12 ```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 ```
 Re: [Algorithms] Area of convex shape inside of a BSP tree From: Alen Ladavac - 2009-11-08 21:20:58 ```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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list -- Best regards, Alen mailto:alenl-ml@... ```
 Re: [Algorithms] Area of convex shape inside of a BSP tree From: Juan Linietsky - 2009-11-08 22:19:57 ```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 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 >> GDAlgorithms-list@... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > > -- > Best regards, >  Alen                            mailto:alenl-ml@... > > ```
 Re: [Algorithms] Area of convex shape inside of a BSP tree From: Jason Hughes - 2009-11-08 22:29:56 Attachments: Message as HTML ```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 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 >>> GDAlgorithms-list@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >> >> -- >> Best regards, >> Alen mailto:alenl-ml@... >> >> >> > > ------------------------------------------------------------------------------ > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > ```
 Re: [Algorithms] Area of convex shape inside of a BSP tree From: Jason Hughes - 2009-11-08 22:32:08 Attachments: Message as HTML ```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 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 >>> GDAlgorithms-list@... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >> -- >> Best regards, >> Alen mailto:alenl-ml@... >> >> >> > > ------------------------------------------------------------------------------ > 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 > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > ```