On Jun 24, 2013, at 09:02 PM, Joshua Stults <joshua.stu...@gmail.com> wrote:
On Tue, Apr 9, 2013 at 6:42 PM, Christopher Sean Morrison
<brl...@mac.com> wrote:
> 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).
>
> 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
>
I finally got around to trying this, and it does improve things quite
a bit! I just did one level of 'spatial awareness' so the scaling is
ultimately still quadratic; plot attached. Here's the python script I
used: https://gist.github.com/jstults/5855032<brlcad_union_time.png>
Joshua,
Thanks for sharing your timings! Cool to see some real numbers on the practical value of boolean restructuring.
If I'm reading your graph right, just by adding one level of spatial grouping, you reduced a 2 hour runtime to about 4 minutes. Similarly, in the time it took you to do about 170 unions of your model, you can now do about 1000. Not too shabby.
Now we just need someone to get the code doing that automatically for you. ;)
Cheers!
Sean
------------------------------------------------------------------------------ This SF.net email is sponsored by Windows:
Build for Windows Store. http://p.sf.net/sfu/windows-dev2dev
_______________________________________________ BRL-CAD Users mailing list brlcad-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/brlcad-users
