Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!dimacs.rutgers.edu!seismo!uunet!orca!mesa!rthomson
From: rthomson@mesa.dsd.es.com (Rich Thomson)
Newsgroups: comp.graphics
Subject: Re: Looking for info on fast picking.
Message-ID: <1991Mar14.064404.24329@dsd.es.com>
Date: 14 Mar 91 06:44:04 GMT
References: <3007@fai.UUCP>
Sender: usenet@dsd.es.com
Reply-To: rthomson@dsd.es.com (Rich Thomson)
Distribution: usa
Organization: Design Systems Division, Evans & Sutherland, SLC, UT
Lines: 21
Nntp-Posting-Host: 130.187.85.21

In article <3007@fai.UUCP>
	stevec@fai.fai.com (Steve Churchill) writes:
>  For fast picking given many entities, we're thinking about dividing our 2-D
>  display list into "cells" (ie., into a grid of linked lists, one for each
>  cell).
>  
>  Does anyone know of any references about this type of architecture? Note
>  that I do not have the luxury of simply using a mega-MIPS machine.

You may want to look at quadtree data structures.  There are oodles of
references in the books by Hannan Samet (_The Design and Analysis of
Spatial Data Structures_ and _Applications of Spatial Data
Structures_).  Quadtrees (and their kin octtrees) can be space pigs,
but you always trade space for time with any good datastructure.

							-- Rich
-- 
  ``Read my MIPS -- no new VAXes!!'' -- George Bush after sniffing freon
	    Disclaimer: I speak for myself, except as noted.
UUCP: ...!uunet!dsd.es.com!rthomson		Rich Thomson
ARPA: rthomson@dsd.es.com			PEXt Programmer