mitchell@mitre.org (Richard B. Mitchell) (04/04/91)
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 01730chalmers@europarc.xerox.com (Matthew Chalmers) (04/05/91)
In article <1991Apr3.193547.15558@milton.u.washington.edu>, mitchell@mitre.org ( Richard B. Mitchell) writes: > I have thought > 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.or g You should find Hanan Samet's recent pair of books on spatial data structures quite useful. I think these grew out of the article "The Quadtree and Related Data Structures" in Computing Surveys, v16,2 June 84 p187. My favourites are k-d trees, especially netted k-d trees which were first described by J.L. Bentley: "Multidimensional Binary Search Trees used for Associative Searching", CACM 18(9), Sept 75, pp. 509-517. An application to a geographical information system was given in the paper Matsuyama, Hao and Nagao, "A File Organisation for Geographic Information Systems based on Spatial Proximity", Computer Vision, Graphics and Image Processing 26(3), June 84, pp 303-318. Other more regular structures like octrees have been used quite a lot for ray tracing: examples will be found in Andrew Glassner's book, called something like "An Introduction to Ray Tracing". Regards, Matthew
mg@godzilla.cgl.rmit.OZ.AU (Mike Gigante) (04/08/91)
You should check two excellent books by Hanan Samet
"The Design and Analysis of Spatial Data Structures"
Haman Samet
Addison Wesley
1990, ISBN: 0-201-50255-0
"Applications of Spatial data Structures"
1990, ISBN: 0-201-50300-X
This is the most comprehensive source that I am aware of.
Mike Gigante, mg@godzilla.cgl.rmit.oz.au