Linear Quadtrees

Carter T Shock ctso at umiacs.umd.edu
Sun Mar 2 06:49:53 CET 1997


This is a multi-part message in MIME format.

------=_NextPart_000_01BC26D5.EEF8BEE0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Please forgive the awful image attached... I is a code monkey, not a
artist.

Top figure is the space divided up by the quadtree in the bottom figure.
Bottom figure shows the classic pointer-based quadtree implementation.
Lotsa overhead here. Every node in the tree has four (possibly null)
pointers. It doesn't adapt well to disk based operations etc. The question
is how to get rid of all of those pointers. This is just an overview, not a
hard-core implementation.

The top figure is 256 pixels square, so the entire space indexes nicely
with a pair of 8 bit values. Take a peek at the 1's and 0's next to the
upper figure. We already know that we can come up with a morton code for
any point in 2-d space.  Consider the morton codes for the upper-left
corners of any block in the tree.

The green block's (at least I hope it's green) upper left coordinate is
[0,0], so the
morton code is trivially 0000000000000000. The blue block has upper left
coordinate [0,128] yielding 0100000000000000. The yellow block is [0,192],
0101000000000000. Why do we care?

'Scuse the pseudo-code here, but...
Find all points in the green block:

for each point's morton code, P
   if( (P & 1100000000000000) == 0)
       return true.

Where '&' is bitwise AND.

The blue block presents a bit of a problem because its upper left corner is
the same point as the square that contains it (i.e. the square that is the
same size as the green one... blue's parent). The difference is the block's
level in the tree. Just use more bits.

for each P (as above)
   if((P & 1111000000000000) == 0100000000000000) return true.

Same trick with the yellow block...

for each P
   if((P & 1111110000000000) == 0101000000000000) return true.

Look Ma! No pointers.

The trick is called (go figure..) Morton Blocks.
There are fancier tricks you can do, but for those you'll have to buy the
book :)
	-Todd
------=_NextPart_000_01BC26D5.EEF8BEE0
Content-Type: application/octet-stream; name="qt.gif"
Content-Transfer-Encoding: base64
Content-Description: qt (GIF Image)
Content-Disposition: attachment; filename="qt.gif"

R0lGODlhgARgA6L/AP//////AAD//wD/AAAAAAAAAAAAAAAAACH5BAEAABcALAAAAACABGADQAP/
CLrc/jDKSau9OOvNu/9gKI5kaZ5oqq5s675wLM90bd94rhB87//AoHBILBqPyKRyyWw6n1Cebkqt
Wq/YrHbL7Xq/YBlhQC6bz+i0es1uu9/w+JkQ9tLr+Lx+z+/7/4CBgi5jcoaHiImKb3eDN42OkZKT
lJWWl5iZW4WLnZ6foGWQmiqjpKeoqaqrrK2uNpyhsrO0aqavHre4u7y9vr/AwXa1xMWzusITyMnM
zc7P0NG+scbV1nLL0gDZ2t3e3+Dh4rDX5eZt3NHp4+zt7u/wfI3rK9Tn9+b0zvrx/f7/AAOakMKA
YA17+BIa48eMocCHECNKnIgDocKLx9w5pMix/6PHjyCVYRxJbGMwkyFTqlzJsp1FkjATofw1s6XN
mzhzvnoZs2ecmr2A6hxKtKjRPjx9KmUjdFfTo1CjSp16cKlVbBqpat3KtesjAWDDih1LtqzZs2jJ
Pq2X1avbt3DjdiCQtq7du2nXlmort6/fv3Hp4h1MuK7eFIdZJQbMuLHjfoILS54MdvFAvo8za96s
ruCHyJRD47VcgjQq05xTq169CrTo12hRi5CtiTbr27hzB3INu/dY258x6x5OvHi9Hlh4+14OPJdw
49CjS+dgsAqBANiza9/OvXuAw83nPp9Ovrx5KvMKel/PHjv4L+ErxT9Pv779B9fb69/+3s74+/8A
BihgU/ntZ2B/Xcw3iYICNuggVciFsBaCXDAYiYUPZqihXLdMeAKGFoAoiIgblmiiWx5e5p9LJ7bo
YoAplgbffy/WaOONOOao44480uADBT/2KOSQREqVGIlFJqnkkkEVweSTUEYJUITKVKBLkFJmqeWW
jlAJwlNCecnlmGSWeYGYLIQXH5pmtulmfdWhlwWSELD55p144hRnGHRu0Odne+Yp6KBO/UmCoR+2
FiihjDZ60KK1wemko5QKmpQiiNapojwoZPplp5WGSiYPMnlqZU2QyrNRqpZguY0prooq66y0SmBn
A/SMcmutvPZK5K5+bpoLsL4Wa2xfrLI1g4L/xB7r7LPdNFvRJnXECu212IIh7YxIZbJttuA2ysNk
yVaIqqlATnqKtQ6wG+67OCoHG7oL6OXpkYDgC+++/MbjbkHfjqhuvwQXbKOYyFxp8MIMG1fuDhro
Q2/DFFfc5LkSfmrxxhxDZtnDwYLa8cgkK7pmDM1NXPLKIxdo4H7Z2BuisBiAyfLNOBPi8sv8rWPz
mYdSR3PORBdt9NFIJ6300kw37fTTUEct9dRUV2311VhnrfXWXHft9ddghy322GSXbfbZaKet9tps
t+3223DHLffcdNdt991456333nz37fffgAcu+OCEF2744YgnrvjijDfu+OOQRy755JRXbvnl/5hn
rvnmnHfu+eeghy766KSXbvrpqKeu+uqst+7667DHLvvstNdu++2456777rz37vvvwAcv/PDEF2/8
8cgnr/zyzDfv/PPQRy99BpdeZb3KK06Pe/XWW4V9gtrnzn33Sn1fYfjbk68+GuZTi77t468PU/ta
0P8+3PHLP5L9yd1fe/76uwj/rjBA/60NgAFMSAGtY8C9xQlknUqg+hYopwbyLWCIkSD5KDgFDlqQ
bAjUYD5o9MHThVCE1/BgDlRYQrCdEIXVYOEjWui6F8KwGDKEBQ1bZ8Mb1iKHB9kh63row4ywSIiq
k9dy5sUtdgARiVdT4hJFQ68nLguKqZPiFP8pU0USYjFwkJiJFrcomS4e8YuKg2AExkhGwpjRiWg0
HRvbOJomjsOKcYTaHOlolzfeMY9qU+MLokDIQhrykIJMBh4BSSggWGFnPPMOhdwHR0ZiLj31iqR+
Jlk/L1rScpDUJH8Slb0/fnJwBJLR0ObkyVNOLkZBK6U4FunKlXVIlbg83xlrqTlYjsCPs+Ql53w5
GzsGU5jITKYyIbTKZToTHD97pjQ1siddYXCa2DxNIrchnpptM5vgHOQ3rZSmUowznMK8Zi5n2MFz
olN47hwkn/agzndWLp4VHMQi62nPsvEzD7TED03w2c9wkaoTBIXFqljozoTqspgFxRYR51D/LZFx
ap0XamZEN5oKhAGMmxwNaau+iZJc/VOkKF2jQzVVzuMENKXDXGlwdPCnf8H0dicN4jx3I9Obti2n
D9VnK2zqU6LtsY7asmgnfylUjBaVX+OiIv+22VPEaFQP0XyqVikhBV15ZqtgxWqqfFalsJoVBlR1
TsjOytY6OfStTm0rOKsq0JYqS6475IEov2MSor4Kn371K6CIgFfohXKvo2TpVSFGSqA1trDONII5
CTtZbggWspjNrGY3y9nOevazoA2taEdL2tKa9rSoTa1qV8va1rr2tbCNrWxnS9va2va2uM2tbnfL
29769rfADa5wh0vc4hr3uMhNrnKXy9zm/zr3udCNrnSnS93qWve62M2udrfL3e5697vgDa94x0ve
8pr3vOhNr3rXy972uve98I2vfOdL3/ra9774vWMRffLSFvQ3v2+Z6H4/8d+7AvhOAh4wQlt54Cwl
WMGYYnCDo/RgCCOiwHuZ8JsqbGFDYNiqGnYThzv8EwmHeEkjJjEjTHziJKVYxehgcYt/BWMFynjG
QnpxjW1xYxzzSMc7Zl+PfawjIAfZDB9WKpGlZOQjkyHJj10yhZ1cDigvVso0prI1rBxXLGvGq4/Q
8paH7GWvPJBBTXYyl2NZZtUYhK4hEnMMydzmE6X5yGtmap2ZdOcg5xmie1ZSn3f854wFWv/Qcl4I
nQ+doUHXuNAaY3SWE/3DRUu6QY6GMaRneukcU7oklu40gDKt4k2rVdQ//nSld4nqHJGaxKbuZquL
rGpaxFposy4yInfN6177+tfADjacc02co/IxNsYMx62J7ZJjM1GWymZ2vJz9GmBGW9oHozYVkw1N
bGdb21zk9jeW7W1ogjvc0O52uYsTT2OfOyzWVve6cxPGz7y7jOL2Brnn7a2vzuXehYn3uPltZ4C7
Md/RIriJ3H1vgetb4SVi+LsdnnCIa0ji56a4NvZt8WZgHNwalwbHO97O5Bh8MCHvDMmLMmzqIFaS
UV5qJVc+lJb76eXd4SQrWU3z6GByBzj/547O+8fznjusXuoJunaGTsBQGx0wCFP60mO+85k/HU5S
zw7TH+n0q9f8l1l3D9WJbnWv/4VAwjYkwjdu9sakks1wp6Qp224eYhoafEWnO2sCZfdIB/WYeh/O
LeMO6L9fO/D0rmaXT214eSPe54uXdeMH/njp9J3Tk3945SFP+LtnvuKbd1jaR0/60pv+9EsIvepX
z3qUNnTkrW+ZkmNfOpnRnocLvf327oAc2OseZ2NdI8B8//t3qZEf6QBq8Q94TlQNi/jLd/FK9XUo
m0e/X8q3lTx1Zv3rUyr7NWOnQqHvfa2An/EdTE73y3/x9UcM7/BxP/txc367VtQP9Z8//9Tlf+Wk
Loj/+ucR+TctXLUuABiA43aAKLMuhUJ+CPh8qsBlyzaAD8hTB8UUFLhCA3MJgZWB5kIdDnh1FWY+
WXVRnddUJ1iB+Adq/td/cpeCf0B9KqhPskCCLgh/nicfGDODBkhZktCBCrgsG+gKvedvPOg5txIz
HniEgXR8a9UuS8iETpNTYQKCQSiF2TKAiwEeV4iFeBKFSIdWKNOFXrgjYKh9OtROIViGEXGG1NN0
5kKGbHh2ckhOOAhQdTiHLeGGs9eCXZKHeuhEgFh4+NdRgxiIf+iDO3CI1EMsl4UHf/aIiKgYzAGJ
N0hTMeNWXLWDk+gtZDQxMkh2ehaDff/YiRcyRd9TgqIIg/fHiqb4f1EVG3yIVkMIiZx4Ibn3ipeU
Hmuoi7USIXyHK754OHaSicI3jHhTLrkyM8jYhO/3jOHXjFzTfJj3hNKoNMqnirh2jbYUiqP4jdyI
fahhGqTRi+EIFe5nG7RhjufYEZK1gFckBu3IJYe1Vz5ziyGCjyC4j/NohmE3dYoVeSB1iYzliv3Y
aP/4HWVlkAMJjnZIkAf5ID6wSfVEVSWVi4DyJewYkRzZkR75kSAZkiI5kiRZkiZ5kiiZkiq5kizZ
ki75kjAZkzI5kzRZkzZ5kziZkzq5kzzZkz75k0AZlEI5lERZlEZ5lEiZlEq5lEzZlE7/+ZRQGZVS
OZVUWZVWeZVYmZVauZVc2ZVe+ZVgGZZiOZZkWZZmeZZomZZquZZs2ZZu+ZZwGZdyOZd0WZd2eZd4
mZd6uZd82Zd++ZeAGZiCOZiEWZiGeZiImZiKuZiM2ZiO+ZiQGZmSOZmUWZmWeZmYmZmauZmc2Zme
+ZmgGZqiOZqkWZqm2S61ZkRld5r1kpo12HWT+WodtpEFyZoF4ZqhQJsNaZs7gJugoJu6CZOyaWHA
yZu44psEBpuSOZwQVpzG2ZrIuWB5d5rMqWDO+ZzbEJ3SuZq2WZ0Ddp3P6Z37BZ7GKZ5FRJ68aZ4+
hJ7dqZ2LwJ6sqZ43BJ/U6Z4RNp2m/ymfMESf+WmfMqGckamfKMSfpSmgIkSgpGmgGoSgo6mgEsSg
oumgCQShoSmhAUShoGmh+oOhn6mh8sOhnumh6wOinSmiEwSgkGmiG4SiWjmL+OGfF8aiV/lmFqKi
3UOiZHlmYQajHiajVamj5MCjWIGfbQmkVSGkJUakRSqMO4qkK6akS1qbR+qkboCjm2mj1+OjjIml
V2Glmsml3qOliwmmS+GlmUmm5SOmiomm/KWmicmmPWGmmAmnMSGnl0mn8+OmiImnJGGnlsmn+6On
hwmoGOGnlUmoAiSohomoCmGolMmoNgalEUqlT8qd8UmpVaqohQmp+OCosYmpMSapFf8KqkyhqYTJ
qffgqctJqmugqgHKqjwmqhkKq2ngqilKq0Imqx16ckh1h4cXnrx6FykHDcH5kh+nbcP6DMXqksdK
bcm6D9i5A8HaR2snctG6DdNqGNWqctjZrM72rB53rd56bODaEOKarXmxrcR6ruh6FuWqSOzarmXx
rsKwrC05rnxErycRr/L6G+qqrPzar/D2r9C6nFLqJwKrFgQbrgFqhAibsGKhr8Bgr8NYb7kAsRG7
sObasGH4bxhbGRoLrwa7mw/7sRJLEwGbsCc7DSkrsCsbFC3bry/LCxS7kvhKRzPrFDErrzmLCzWr
kjfbRj27EzvbrkNLhEWLrkc7VEn/m61Lqxh1OYhB+4khW69RW1MfC7LpRnlzKbVZKwBP2xpXmxz/
uHUMpKs5WlNlO3ZwaKlFqrZhZ7b5NHdyKbVrC5E65bYh+kB3K5Dph7aP2rHb0LcMuUKmqpc/N7hx
y7ZcB7ixKbj1aI+Me7Z6y5mJG7miJLd/W7kJSrgOWXV0W56eS4gyF7rpObo5WLqAF56o63cv+KuN
mY2tW42qC7uOSSCzi36163iP+Xaf67q7y7Up+ruSR7yNy7mDarzWSLqgu7rl6bfQ+HlsF62Xp7vN
a7sVWlfKu43Sa635qb3MC7zXy7sRCr6pe76riL0Zar7i275ta7rZ2y7Q+4Zbq3nd/zq/0eir5Nud
+OtY+iu8z1u4+du93Bqe/cuM/2u/BizA/kvA60q9B/yQDgywEMzACDzBBXu/FizBr7u/1/rBIBzC
IjzClleLJBxxGHnCmLbBKkxveNvCe1eKMAwd3jjDlvfCNrwar5fDmIYm1sSIPLwVwBjEL+IlvAfE
RMxyizJ4LprE6Mgqxjh8Tnwb27KMtoLEU6xsguQQJvWzWZwmJWW9p+LFXwyB7ku/ZlzGHAFXEaxS
ZDzF+fcxnYLFavyBBpZhk1XH9Wp9wJEydKzHiKEmeSuEb7ycB4ghINLEgDwbiUy5arjI9ZOHNRXJ
hfyWiryQ6Tsnf0y9WBy2lQXJaf+cwMGrLZt8qKUsuJaYL6e8p6vssFj1g62MuLEsvyMyUpWMkpc8
uSbIgbMclrmMxwWoTbeMjL9sfxw4VMXslb0cvZFCs8vMk8kMj2I7sc8snEk2zEhRzR35jhGoGCZs
iMkiiUZ5gR7GQUD4RBZpgBr5lAlGPzu8GyzcitsLlCOYyvHsyOELz7rskyOmMjW8Uzhcv7RLlP0M
0G08t/cs0NyLlPUsz/ls0A+tzxFN0D00y9pIT/o4UvxIlT5QpdEsISmMi+H80RXxzTPMzTT8ZrQM
yj4XjFCozSytxVGMhuIc00YCMsiHHzBt0xGYSKsyxjytJ9Q40Mqw00HNJwR10Wf/YtRHjYmau7yh
3NQNAWflGMhMLdVzwcfbB8ZXjdUv7SPyKAYk7dV+ooDzgchjTdZSTFOGax1dTcJjjSSZktZOTNcH
u7kJ8tZf+sf3gtHYHJV2fYwKHX96/ZeBDSQAlYh/bZOH3cCJvYmFnbYqtEAvVdNnqteTbTIdqs1H
EMxEGNk22wOGYdnqt9ES3YBD4JaxyEXto9Sb4MO40tiMbNpiObXYY3t5vc5dktBLObVaO9gL/b4T
DdHom5W+DbZ+yNt3PM/ADdUtiooOXdx4rdxsvc8/Wol4qNuiHNy7PNzGLXEwfc6P7d3VktFnidLm
F9KwaFmyrda/ZNLa9CrundJg/7bY840evLfSJHvfjFEdCaPf/B0YgxeQTBrgXAEp4YyGBv7EiM3B
BL7ge6iMEuPYEC6AEMQQOV3hFIFBacXMGu4vJEXUDv7hWnzGF+zcJK6sVUjeCp7iU33Q7CvGLo7M
1o3GLD7jsAhiAd3iOM7LVQ3MO97jry0b47jcQi5W6kjkhHDk2R3WW+1fTG7HQujkTx7lYq1X7UHa
Oq2IAwHfMmzlXR50x6fe3kTbGjnSoB3CmJu5Dc7irp0u2g3m1JOQYifYzI3bA3zjcr7mkvvgE/3P
dk7dM87nkbQMgI7KzI3oer7ni4vJ3o3nFG7icl7U9oh85n3Fce7hMj7pZc3lz//H3oDliOCXzpye
3p5e6qie6qq+6qze6q7+6rAe67I+67Re67Z+67ie67q+67ze677+68Ae7MI+7MRe7MZ+7Mie7Mq+
7Mze7M7+7NAe7dI+7dRe7dZ+7die7dq+7dze7d7+7eAe7uI+7uRe7uZ+7uie7uq+7uze7u7+7vAe
7/I+7/Re7/Z+7/ie7/q+7/ze7/7+7wAf8AI/8ARf8AZ/8Aif8Aq/8Azf8A7/8BAf8RI/8RRf8RZ/
8Rif8Rq/8Rzf8R7/8SAf8iI/8iRf8iZ/8iif8iq/8izf8i7/8jAf8zI/8zRf8zZ/8zif8zq/8zzf
8z7/80Af9EI/9ERf9EZ/9EhDn/RKv/RM3/RO//RQH/VSP/VUX/VWf/VYn/Vav/Vc3/Ve//VgH/Zi
P/ZkX/Zmf/Zon/Zqv/Zs3/Zu//ZwH/dyf5IJAAA7

------=_NextPart_000_01BC26D5.EEF8BEE0--




More information about the mud-dev-archive mailing list