A piece of me wants to take this on, as it would be a good opportunity to
learn some parallel processing skills, which has been on my todo list for a
while now. Might go well, might not...
Any pointers as to where a good starting point might be?
On 10/04/2013 9:04 AM, "Christopher Sean Morrison" <[email protected]> wrote:
> 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
>
>
------------------------------------------------------------------------------
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
