home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12103 < prev    next >
Encoding:
Text File  |  1992-11-19  |  2.3 KB  |  45 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!wupost!darwin.sura.net!udel!princeton!phoenix.Princeton.EDU!jdunning
  3. From: jdunning@phoenix.Princeton.EDU (John Alan Dunning)
  4. Subject: Re: What are Quad Trees?
  5. Message-ID: <1992Nov19.042358.8559@Princeton.EDU>
  6. Originator: news@nimaster
  7. Sender: news@Princeton.EDU (USENET News System)
  8. Nntp-Posting-Host: phoenix.princeton.edu
  9. Organization: Princeton University
  10. References: <1992Nov7.053905.18272@nuscc.nus.sg> <1992Nov09.230108.32263@watson.ibm.com> <martin.721555622@marsh>
  11. Date: Thu, 19 Nov 1992 04:23:58 GMT
  12. Lines: 31
  13.  
  14. In article <martin.721555622@marsh> martin@cs.curtin.edu.au (Martin Dougiamas) writes:
  15. >schultz@schultz.kgn.ibm.com (schultz) writes:
  16. >>There are a bunch of papers covering the properties of quadtrees.
  17. >>Also, octrees are the logical extension of quadtrees into 3D.
  18. >
  19. >I actually wrote a simple but effective solids-modeller last year using 
  20. >linear octrees, which are a VERY space efficient way to represent volumes.
  21. >You can also encode quadtrees linearly.  Essentially, the linear encoding
  22. >reduces the tree to a sorted array of leaves.  There is no need for pointers.
  23. >I found that operations like merging octrees and calculating cross-sections
  24. >could be performed quite speedily.
  25.  
  26. Yes, octrees are extremely useful data structures.  Last year I wrote
  27. a sort of 3D drawing program that let you sketch in 3D space using
  28. cubes, much like you can sketch in 2D space using little squares in a
  29. traditional bitmapped drawing program.  I used a linear octree to encode the
  30. positions of the "voxels" (volume elements) in space.  If the user
  31. drew eight voxels in one area so that their volume could be reprensented
  32. by a larger octant, the program would condense them into a single,
  33. larger octant, thus saving 7 elements in the array.  Conversely, if
  34. the user deleted a voxel from a single large octant, the program
  35. would decompose that octant into smaller ones until the octree
  36. represented the new shape.  Anyway, the program handled all this
  37. condensing and decomposing of the octree in real time.  The main speed
  38. limitation was depthcuing the voxels on a Personal IRIS, rather than
  39. maintaining the linear octree, even though I was using very naive algorithms
  40. for searching the array (i.e., starting at the beginning and checking
  41. each octant until I found the one I wanted).
  42.  
  43. John
  44.  
  45.