Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!njin!paul.rutgers.edu!aramis.rutgers.edu!dimacs.rutgers.edu!mips!cs.uoregon.edu!ns.uoregon.edu!milton!hlab
From: mitchell@mitre.org (Richard B. Mitchell)
Newsgroups: sci.virtual-worlds
Subject: Spatial Data Structures
Message-ID: <1991Apr3.193547.15558@milton.u.washington.edu>
Date: 3 Apr 91 21:25:56 GMT
Sender: hlab@milton.u.washington.edu (Human Int. Technology Lab)
Organization: Mitre Corporation, Bedford, MA.
Lines: 25
Approved: cyberoid@milton.u.washington.edu



Hi,

        A group of us here at Mitre are in the beginning stages of a
virtual reality.  One the the topics that continues to arise is the
problem of having objects in space and with each hand movement
"asking" each of the objects if the hand is nearby.  One reason for
this is so that we can determine if the hand is in close enough range
to interact with any particular object.  This is ok if one only has a
few object in the world.  However, when the number of objects becomes
increasingly large, the system slows down accordingly.  I have though
about dividing the world into subworlds and only "polling" those objects
that are in the same subworld as the hand.  This seems ok until we
want ot move an object from one point in space to another.  I have
also considered using some sort of quad trees, but this does not seem
like the right approach either.  If any one has any ideas or pointers
to solutions, I would be grateful.

-------------------------------------------------------------------------------
Richard B. Mitchell                                    mitchell@linus.mitre.org
M/S A047                                               
The Mitre Corp.                                        (617) 271-8390
Burlington Rd
Bedford MA 01730