Xref: utzoo comp.sys.amiga.graphics:94 alt.flame:27685 Path: utzoo!utgpu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!vsi1!zorch!xanthian From: xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan) Newsgroups: comp.sys.amiga.graphics,alt.flame Subject: Re: Layers bug Message-ID: <1991Jan28.013434.22001@zorch.SF-Bay.ORG> Date: 28 Jan 91 01:34:34 GMT References: <1991Jan22.204914.7652@msuinfo.cl.msu.edu> Followup-To: comp.sys.amiga.graphics Organization: SF-Bay Public-Access Unix Lines: 26 limonce@pilot.njin.net (Tom Limoncelli +1 201 408 5389) writes: [Recollection mode ON] Layers is based on a paper presented at SIGGRAPH a couple years ago. I'm sure I could get the exact bibliographic reference if someone asked for it. Basically, the pseudo-code presented in the paper was almost directly translated into C (or BCPL?) to create layers.library. This included the sequential searches used all over the code. So, it seems that the layers could be stored in sorted order and faster searches could be implemented. [Recollection mode OFF] Well, not "sorted"; overlapping 2D objects don't sort well. However, there are some very clever tree structures for storing quick access to recursive 2D subdivisions of a rectangle parallel to the axes; take a look at Hannan Samet's textbook Applications of Spacial Data Structures, an exhaustive study of fast storage and retrieval and indexing methods for objects with dimensions and metrics, like a windowed raster screen. Kent, the man from xanth.