home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / graphics / 11781 < prev    next >
Encoding:
Text File  |  1992-11-11  |  1.8 KB  |  42 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!munnari.oz.au!uniwa!cujo!martin
  3. From: martin@cs.curtin.edu.au (Martin Dougiamas)
  4. Subject: Re: What are Quad Trees?
  5. Message-ID: <martin.721555622@marsh>
  6. Sender: news@cujo.curtin.edu.au (News Manager)
  7. Organization: Curtin University of Technology
  8. References: <1992Nov7.053905.18272@nuscc.nus.sg> <1992Nov09.230108.32263@watson.ibm.com>
  9. Date: Thu, 12 Nov 1992 08:07:02 GMT
  10. Lines: 30
  11.  
  12. schultz@schultz.kgn.ibm.com (schultz) writes:
  13. >There are a bunch of papers covering the properties of quadtrees.
  14. >Also, octrees are the logical extension of quadtrees into 3D.
  15.  
  16. I actually wrote a simple but effective solids-modeller last year using 
  17. linear octrees, which are a VERY space efficient way to represent volumes.
  18. You can also encode quadtrees linearly.  Essentially, the linear encoding
  19. reduces the tree to a sorted array of leaves.  There is no need for pointers.
  20. I found that operations like merging octrees and calculating cross-sections
  21. could be performed quite speedily.
  22.  
  23. Hidden line removal for graphical display was also eased by the fact that 
  24. the tree is pre-sorted spatially, so you always know what's behind what.
  25.  
  26. Irene Gargantini wrote a lot of papers on this topic, starting in the early
  27. eighties... 
  28.  
  29. >There is a lot of material on octrees.
  30.  
  31. Yes, there is.  Octrees are a nifty data structure for a lot of other
  32. things besides graphics.
  33.  
  34. Martin
  35. --
  36. ,--------------------------------------------------------------.      _ .
  37. | All the deserts I could irrigate      Martin Dougiamas.      |   _r| Ll\
  38. | All the poor I could emancipate    martin@cs.curtin.edu.au   |  |  |    \
  39. | But that's not what interests me      Curtin University      |  \  |_   /
  40. | I'm interested in apathy          Perth, Western Australia  -+-> x~  `-'
  41. `=== This Is Serious, Mum ====================================='        V
  42.