February 1998
- OT: Following in the footsteps of JCL Alex Oren
- OT: Following in the footsteps of JCL Nathan Yospe
- OT: Following in the footsteps of JCL Richard Woolcock
- OT: Following in the footsteps of JCL Chris Gray
- OT: Following in the footsteps of JCL coder@ibm.net
- OT: Following in the footsteps of JCL Marc Eyrignoux
- Ada? Andrew C.M. McClintock
- Monthly FAQ posting Koster, Raph
- Monthly FAQ posting Adam Wiggins
- Monthly FAQ posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Chris Gray
- Monthly FAQ Posting Ling
- Monthly FAQ Posting J C Lawrence
- Monthly FAQ Posting J C Lawrence
- Monthly FAQ Posting Alex Oren
- Monthly FAQ Posting Greg Miller
- Monthly FAQ Posting s001gmu@nova.wright.edu
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling
- Monthly FAQ Posting Ling Lo
- Monthly FAQ Posting Koster, Raph
- Monthly FAQ Posting Ling Lo
- Monthly FAQ Posting Greg Miller
- Monthly FAQ Posting Marian Griffith
- Monthly FAQ Posting Greg Miller
- Monthly FAQ Posting Ling Lo
- Databases Shawn Halpenny
- OT: This is a test coder@ibm.net
- OT: This is a test Alex Oren
- Clients and things [Was: OT: This is a test] Matt Chatterley
- Clients and things [Was: OT: This is a test] coder@ibm.net
- Clients and things [Was: OT: This is a test] Matt Chatterley
- MUD Development Digest Dr. Cat
- DBs and Events Greg Munt
- DBs and Events Nathan Yospe
- DBs and Events Greg Munt
- DBs and Events Nathan Yospe
- DBs and Events Felix A. Croes
- DBs and Events Jon A. Lambert
- DBs and Events coder@ibm.net
- DBs and Events s001gmu@nova.wright.edu
- DBs and Events Jon A. Lambert
- DBs and Events coder@ibm.net
- (subject missing) Ben Greear
- META: Unsubscribed users dur to bounces coder@ibm.net
- META: Unsubscribed users dur to bounces Adam Wiggins
- Source Code Release Greg Munt
- Source Code Release Ben Greear
- Source Code Release Greg Munt
- Source Code Release Ben Greear
- Source Code Release Greg Munt
- Source Code Release Richard Woolcock
- Source Code Release Ben Greear
- Source Code Release Chris Gray
- Source Code Release Greg Munt
- Source Code Release coder@ibm.net
- Source Code Release Richard Woolcock
- Source Code Release Stephen Zepp
- Source Code Release Jon A. Lambert
- Source Code Release Greg Munt
- Source Code Release Jon A. Lambert
- Source Code Release Greg Munt
- Source Code Release Travis Casey
- Source Code Release Jon A. Lambert
- Source Code Release Jon A. Lambert
- [RESEARCH]MUD articles archive (fwd) Greg Munt
- Socket programming (Was: The impact of the web on muds) Jon Leonard
- Socket programming (was: The impact of the web on muds) Vadim Tkachenko
- Socket programming (was: The impact of the web on muds) Richard Woolcock
- byte-code anyone? Chris Gray
- byte-code anyone? Jon Leonard
- byte-code anyone? Chris Gray
- byte-code anyone? Jon Leonard
- byte-code anyone? Chris Gray
- user-centered design (was Clients) Mike Sellers
- OT: Linux g++ Greg Munt
- OT: Linux g++ Ben Greear
- OT: Linux g++ coder@ibm.net
- OT: Linux g++ Shawn Halpenny
- OT: Linux g++ Chris Gray
- OT: Clients Vadim Tkachenko
- OT: Clients Adam Wiggins
- OT: Clients coder@ibm.net
- META: OS wars coder@ibm.net
- META: OS wars Mike Sellers
- Clients Stephen Zepp
- Moore's Law sucks (was: 3D graphics) Brandon J. Rickman
- Moore's Law sucks (was: 3D graphics) Adam Wiggins
- Moore's Law sucks (was: 3D graphics) Chris Gray
- Moore's Law sucks (was: 3D graphics) coder@ibm.net
- Moore's Law sucks (was: 3D graphics) Brandon J. Rickman
- Moore's Law sucks (was: 3D graphics) Mike Sellers
- Moore's Law sucks (was: 3D graphics) Chris Gray
- Moore's Law sucks (was: 3D graphics) Ben Greear
- Moore's Law sucks (was: 3D graphics) Ling
- Moore's Law sucks (was: 3D graphics) Brandon J. Rickman
- Moore's Law sucks (was: 3D graphics) coder@ibm.net
- Moore's Law sucks (was: 3D graphics) Alex Oren
- Version Control (was: DBs and Events) Vadim Tkachenko
- Version Control (was: DBs and Events) coder@ibm.net
- Version Control (was: DBs and Events) Vadim Tkachenko
- Version Control (was: DBs and Events) coder@ibm.net
- Version Control (was: DBs and Events) coder@ibm.net
- Version Control (was: DBs and Events) Jon A. Lambert
- Version Control (was: DBs and Events) s001gmu@nova.wright.edu
- Version Control (was: DBs and Events) Raph & Kristen Koster
- Version Control (was: DBs and Events) coder@ibm.net
- Version Control (was: DBs and Events) Felix A. Croes
- Net protocols for MUDing (was: Moore's Law sucks) Jon Leonard
- Net protocols for MUDing (was: Moore's Law sucks) coder@ibm.net
- Net protocols for MUDing (was: Moore's Law sucks) s001gmu@nova.wright.edu
- Net protocols for MUDing (was: Moore's Law sucks) Vadim Tkachenko
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) Caliban Tiresias Darklock
- Net protocols for MUDing (was: Moore's Law sucks) J C Lawrence
- Net protocols for MUDing (was: Moore's Law sucks) J C Lawrence
- Net protocols for MUDing (was: Moore's Law sucks) Adam Wiggins
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) Vadim Tkachenko
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) Vadim Tkachenko
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) Adam Wiggins
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) J C Lawrence
- Net protocols for MUDing (was: Moore's Law sucks) Chris Gray
- Net protocols for MUDing (was: Moore's Law sucks) Adam Wiggins
- Net protocols for MUDing (was: Moore's Law sucks) Ben Greear
- Net protocols for MUDing (was: Moore's Law sucks) Adam Wiggins
- Net protocols for MUDing (was: Moore's Law sucks) s001gmu@nova.wright.edu
- Net protocols for MUDing (was: Moore's Law sucks) Jon A. Lambert
- Net protocols for MUDing (was: Moore's Law sucks) J C Lawrence
- VEIL (was: Clients) Brandon Gillespie
- LDMs (large dynamic maps) was Unique items Mike Sellers
- Describing the environment Stephen Zepp
- Describing the environment Richard Woolcock
- Back on the list Niklas Elmqvist
- Back on the list Chris Gray
- Back on the list coder@ibm.net
- Unique items The Eternal City
- Unique items coder@ibm.net
- Position sorting Adam Wiggins
- Position sorting coder@ibm.net
On 22/02/98 at 10:07 AM, Adam Wiggins <nightfall@user1.inficad.com> said:
>A while back (I can't remember how long, maybe a year or so) someone
>posted the basics for an algorithm which involved interpolating the bits
>of an object's coordinates in game space in order to generate a sorting
>key.
"Morton Codes" as described by Carter T Shock -- alas, no longer on the
list.
>Recently something came up that made me think of that, and I wanted
>to reread the message, but it seems that I either never saved it or lost
>it during the system moves I've made since then.
>So...could someone dredge it up out of their archives and
>post it, or just explain it once again for me? I'd
>be much obliged...
--<cut>--
Date: Mon, 21 Apr 1997 08:18:29 PST8PDT
Reply-To: mud-dev@null.net
From: "Carter T Shock" <ctso@umiacs.umd.edu>
To: <mud-dev@null.net>
Subject: [MUD-Dev] Re: Quadtrees?
> do you know of any good books that I can read up on some of those
algorithms
> specifically the Peano, Hilbert or Morton curves you mentioned?
>
"The Design and Analysis of Spatial Data Structures" by Samet (Addison
Wesley) is a great primer on this stuff and spatial data structures in
general. However, save 30 bux...
Peano and Morton are two names for the same thing. A space filling curve
is one that can cover all the points in a grid without ever crossing over
itself. Hilbert is kinda odd and computationally a bit nasty to work with,
but Morton is easy.
In a nutshell: interleave the bits.
Given a coordinate [3,5] represented with 4 bits each you have: X = 0011
Y = 0101
Morton is: 00011011 or 00100111
0 0 1 1
0 1 0 1
00011011
Your choice as to whether to start with the X or Y bit as most
significant. Here's the sweet part... because the most significant bits of
the code represent the most significant bits of the two coordinates you
can use it as a sorting key. Codes that are numerically close are also
spatially close. There's also a direct correspondence between the code and
quadrants/depth in quadtrees but I'm not swift enough with ASCII graphics
to draw it here. I can do a picture and send it via MIME if ya want. Also
as mentioned, you can do algebra on them. Need to offset the coordinates
by an X,Y? make a code for the offset and add/subtract it in.
You can also do range searching by masking off low-order bits. Finally,
this is why using B-Tree type stuff works.. the keys in the tree are just
the interleaved codes. It's one of those things that once discovered you
bonk yourself on the head and say "why didn't I think of that?"
-Todd
--<cut>--
--
J C Lawrence Internet: claw@null.net
----------(*) Internet: coder@ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...
- Position sorting coder@ibm.net
- Unique items coder@ibm.net
- Unique items Nathan F Yospe
- BOOK: Myer's Silverlock coder@ibm.net
- BOOK: Myer's Silverlock Chris Gray
- BOOK: Myer's Silverlock Adam Wiggins
- Dynamic Loading of Modules (was: Back on the list) Niklas Elmqvist
- Dynamic Loading of Modules (was: Back on the list) Vadim Tkachenko
- Dynamic Loading of Modules (was: Back on the list) J C Lawrence
- Dynamic Loading of Modules (was: Back on the list Jon A. Lambert
- Net protocols for MUDing s001gmu@nova.wright.edu
- Net protocols for MUDing Stephen Zepp
- Net protocols for MUDing Chris Gray
- Net protocols for MUDing Adam Wiggins
- Net protocols for MUDing J C Lawrence
- Net protocols for MUDing Shawn Halpenny
- Net protocols for MUDing J C Lawrence
- Net protocols for MUDing Chris Gray
- Dynamic Loading of Modules Niklas Elmqvist
- Senses (was: The MLI Project) s001gmu@nova.wright.edu
- bar-time (was The MLI Project) Mike Sellers
- 3D engines for MUDs (was: The MLI Project) Niklas Elmqvist
- 3D engines for MUDs (was: The MLI Project) J C Lawrence
- 3D engines for MUDs (was: The MLI Project) Michael Hohensee
- 3D engines for MUDs (was: The MLI Project) Miroslav Silovic
- 3D engines for MUDs (was: The MLI Project) Michael Hohensee
- Why not compile java into object code? Ben Greear
- Why not compile java into object code? Cynbe ru Taren
- Why not compile java into object code? Caliban Tiresias Darklock
- Why not compile java into object code? Nathan F Yospe
- Why not compile java into object code? Niklas Elmqvist
- Why not compile java into object code? Ben Greear
- Why not compile java into object code? Jon A. Lambert
- Why not compile java into object code? Travis Casey
- Why not compile java into object code? Chris Gray
- Tutorial: Comments on Hand-crafting a compiler Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part I: Introduction Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part II: Expression Parsing Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part I: Introductio Chris Gray
- Tutorial: Let's build a Compiler! - Part I: Introductio s001gmu@nova.wright.edu
- Tutorial: Let's build a Compiler! - Part I: Introductio coder@ibm.net
- MUD Development Digest Dr. Cat
- MUD Development Digest Koster, Raph
- MUD Development Digest Mike Sellers
- Tutorial: Let's build a Compiler! - Part III: More Expressions Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part IV: Interpreters Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part V: Control Constructs Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part VI: Boolean Expressions Jon A. Lambert
- Tutorial: Let's build a Compiler! - Comments Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part VII: Lexical Scanning Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part VIII: A Little Philosophy Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part IX: A Top View Jon A. Lambert
- Tutorial: Let's build a Compiler! - Part X: Introducing TINY Jon A. Lambert
- Compilers: Toy available for ftp Chris Gray