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 brlcad-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/brlcad-users
