stevec@fai.UUCP (Steve Churchill) (03/13/91)
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. Thanx in advance. -- Steven Churchill stevec@fai
rthomson@mesa.dsd.es.com (Rich Thomson) (03/14/91)
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