I decided to teach myself about this data structure and see if it could be
used to help ScrollPanes with very large numbers of objects scroll more
smoothly.

The results were pretty good; you can scroll through very large numbers of
morphs very fast,  if you are willing to tolerate the time needed to build
the QuadTree - I believe its O(n log n) ish, though I haven't read a real
reference on it. Traversing the tree and determining visibility is fast
enough that the effective bottleneck becomes drawing the morphs that touch
your viewing area.

This implementation is a intended as a demo and has lots of caveats and
limitations, but the bottom line is that if your project requires smooth
scrolling of arbitrary morphs that scales very well, it is possible with a
bit of work.

Eddie

Benchmarks:

20,000 RectangleMorphs in a 15k x 15k field, with a 400x400 visible window

Stock:                3 fps
Basic Tweaks:    5 fps
QuadTree:          45 fps    (tree build time - 2 seconds)

100,000 RectangleMorphs in a 35k x 35k field, with a 400x400 visible window

Stock:                 0.8 fps
Basic Tweaks:     1.4 fps
QuadTree:           44 fps    (tree build time -  15 seconds)

Run on a P3-600, Win2k, Squeak 3.6a #5325
*Basic Tweaks is basically caching localSubmorphBounds as noted by Andreas
and others.
The benchmark code is from QuadTreeAbstractNode(Class)>>Demo, appropriate
numbers changed


-------------- next part --------------
A non-text attachment was scrubbed...
Name: TransformQuadTree-efc.1.cs.gz
Type: application/octet-stream
Size: 3217 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20030721/f7ceaeb7/TransformQuadTree-efc.1.cs.obj