Anyone care to give this optimization a try? The solution is to use some
spatial partitioning (e.g., a kd-tree) during the processing. Data coherence
would be another. Both would be pure gravy.
For tools like g-stl where we know we're going to triangles, it might make
sense to triangulate right away (instead of processing as polygons and then to
triangles) so we could use TIE's kd-tree during triangle comparisons. Another
approach would be to try using something like http://code.google.com/p/kdtree/
or generalizing TIE's kd-tree. Or using a different BVH altogether. Either
way, we just shouldn't end up with two implementations of the same algorithm in
our tree (even for "just a little while"). Any takers?
Cheers!
Sean
Begin forwarded message:
> From: Christopher Sean Morrison <[email protected]>
> Date: April 9, 2013 6:42:20 PM EDT
> To: BRL-CAD Users Mailing List <[email protected]>
> Subject: Re: [brlcad-users] Parallel g-stl conversion?
> Reply-To: BRL-CAD Users Mailing List <[email protected]>
>
>
> On Apr 9, 2013, at 5:24 PM, Joshua Stults wrote:
>
>> I think you are right; this scripting approach is probably what I'll end up
>> doing. Right now I'm unioning a bunch of right circular cylinder primatives
>> into a region, and then converting to stl with g-stl (I've found the time
>> scaling for that to be quadratic in the number of cylinders [1]).
>
> Ouch! 8 hours for 500 cells... that's just awful. A recent change I've been
> working on and was planning for public unveiling in a couple months will
> probably cut a couple hours off that time but the conversion is still way too
> slow.
>
> The reason it slows down so fast is due to the simple algorithm (which is
> O(N^2) complexity at best with large overhead constants). As it unions in
> each new object, it has to compare all the triangles being added against the
> set so it knows how and where to stitch them together.
>
> The fix needed is a change to be spatially aware so that it doesn't have to
> perform so many comparisons (O(N*log(N)). The next piece being added very
> likely only intersects a few polygons. It should only compare against those
> near it. Nothing at all hard, just not an optimization that's been performed
> yet (we tend to abhor polygonal formats for their terrible analysis and
> processing properites).
>
> Done right, it'd probably only take a few seconds.
>
>> An alternative approach would be to facetize the cylinders (maybe at really
>> low resolution) and perform Boolean ops on those BoTs (perhaps incrementally
>> rather than all n cylinders at once?). Would you expect unioning BoTs to be
>> faster than unioning rcc primitives?
>
> It should be identical. Under the hood, it first turns all of the primitives
> into polygons (which takes no time whatsoever) and then starts splicing them
> together.
>
>> I'm happy to report back with timing results for any other approaches folks
>> on the list recommend.
>
> Depending on how you combined the truss elements together, you may be able to
> get a drastic reduction by changing your boolean recipe. For example, say
> you had OBJ = A u B u C u D u E u F
>
> Changing that to spatially (and logically) group them first can cut down on
> the number of comparisons:
> OBJ = G1 u G2 u G3
> G1 = A u B
> G2 = C u D
> G3 = E u F
>
> Worth a try if you basically built up a massive union. Most of the devs are
> knee deep in the middle of projects at the moment to try the optimization,
> but I'll add it to our TODO.
>
> Cheers!
> Sean
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
> _______________________________________________
> BRL-CAD Users mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/brlcad-users
------------------------------------------------------------------------------
Precog is a next-generation analytics platform capable of advanced
analytics on semi-structured data. The platform includes APIs for building
apps and a phenomenal toolset for data science. Developers can use
our toolset for easy data analysis & visualization. Get a free account!
http://www2.precog.com/precogplatform/slashdotnewsletter
_______________________________________________
BRL-CAD Developer mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
