<!-- MHonArc v2.4.4 -->
<!--X-Subject: Linear Quadtrees -->
<!--X-From-R13: "Qnegre F Eubpx" <pgfbNhzvnpf.hzq.rqh> -->
<!--X-Date: from fabius.globecomm.net [207.51.48.6] by mx01.ny.us.ibm.net id 857306106.79688-3 Sun Mar 2 12:35:06 1997 -->
<!--X-Message-Id: 199703021150.LAA18390#lupa,umiacs.umd.edu -->
<!--X-Content-Type: multipart/mixed -->
<!--X-Derived: bin00000.bin -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Linear Quadtrees</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:ctso#umiacs,umd.edu">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00032.html">Previous</a>
| <a href="msg00034.html">Next</a>
]
Thread:
[ <a href="msg00070.html">Previous</a>
| <a href="msg00018.html">Next</a>
]
Index:
[ <A HREF="author.html#00033">Author</A>
| <A HREF="#00033">Date</A>
| <A HREF="thread.html#00033">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Linear Quadtrees</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <<A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A>></LI>
<LI><em>Subject</em>: Linear Quadtrees</LI>
<LI><em>From</em>: "Carter T Shock" <<A HREF="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</A>></LI>
<LI><em>Date</em>: Sun, 2 Mar 1997 06:49:53 -0500</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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</PRE>
<P><A HREF="bin00000.bin" >qt (GIF Image)</A></P>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00032.html">Re: Just a bit of musing</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00034.html">Re: Quadtrees?</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00070.html">Re: q-tree stuff</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00018.html">Quadtrees?</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00033"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00033"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: Issues from the digests and Wout's list</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00149" HREF="msg00149.html">Re: Issues from the digests and Wout's list</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Thu 20 Mar 1997, 13:21 GMT
</LI>
</ul>
</LI>
<LI><strong><A NAME="00041" HREF="msg00041.html">q-tree stuff</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Mon 03 Mar 1997, 04:19 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00043" HREF="msg00043.html">Re: q-tree stuff</A></strong>,
Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Mon 03 Mar 1997, 14:05 GMT
</LI>
<LI><strong><A NAME="00070" HREF="msg00070.html">Re: q-tree stuff</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Sat 08 Mar 1997, 11:54 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00033" HREF="msg00033.html">Linear Quadtrees</A></strong>,
Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sun 02 Mar 1997, 20:35 GMT
<LI><strong><A NAME="00018" HREF="msg00018.html">Quadtrees?</A></strong>,
Wout Mertens <a href="mailto:Wout.Mertens#rug,ac.be">Wout.Mertens#rug,ac.be</a>, Fri 28 Feb 1997, 10:54 GMT
<UL>
<LI><strong><A NAME="00019" HREF="msg00019.html">Re: Quadtrees?</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Fri 28 Feb 1997, 17:33 GMT
</LI>
</UL>
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00021" HREF="msg00021.html">Re: Quadtrees?</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 28 Feb 1997, 23:49 GMT
</LI>
<LI><strong><A NAME="00022" HREF="msg00022.html">Re: Quadtrees?</A></strong>,
Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sat 01 Mar 1997, 00:26 GMT
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>