Content-type: multipart/related; boundary="Boundary_(ID_HHDPNEcmvKVMgyzOvdEKbg)"; type="text/html" --Boundary_(ID_HHDPNEcmvKVMgyzOvdEKbg) Content-type: text/html; CHARSET=US-ASCII Content-transfer-encoding: quoted-printable

On Jun 24, 2013, at 09:02 PM, Joshua Stults <joshua= .stults@gmail.com> wrote:

<= div class=3D"msg-quote">
On Tue, Apr 9, 2013 at 6:4= 2 PM, Christopher Sean Morrison
<brlcad@mac.com> wrote:
= > The fix needed is a change to be spatially aware so that it doesn't h= ave to perform so many comparisons (O(N*log(N)). The next piece being adde= d very likely only intersects a few polygons. It should only compare again= st those near it. Nothing at all hard, just not an optimization that's bee= n performed yet (we tend to abhor polygonal formats for their terrible ana= lysis and processing properites).
>
> Depending on how you c= ombined the truss elements together, you may be able to get a drastic redu= ction by changing your boolean recipe. For example, say you had OBJ =3D A = u B u C u D u E u F
>
> Changing that to spatially (and logi= cally) group them first can cut down on the number of comparisons:
>= ; OBJ =3D G1 u G2 u G3
> G1 =3D A u B
> G2 =3D C u D
>= ; G3 =3D E u F
>
I finally got around to trying this, and it do= es improve things quite
a bit! I just did one level of 'spatial awaren= ess' 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 number= s on the practical value of boolean restructuring.

If I'm reading your graph right, just by adding one level of spatial gro= uping, you reduced a 2 hour runtime to about 4 minutes.  Similarly, i= n the time it took you to do about 170 unions of your model, you can now d= o about 1000.  Not too shabby.

Now we just n= eed someone to get the code doing that automatically for you. ;)

Cheers!
Sean


=

= --Boundary_(ID_HHDPNEcmvKVMgyzOvdEKbg)--