Oktalt tre

Et oktaltre (ofte referert til som octree ) er en tredatastruktur der hver intern node har nøyaktig åtte barn . Oktale trær brukes ofte til å dele et tredimensjonalt rom ved å dele det rekursivt inn i åtte oktanter . De er den tredimensjonale analogen til kvadramenttrær . Ordet oktre kommer fra okt (gresk rot som betyr "åtte") + tre (engelsk tre). Oktale trær brukes ofte i 3D -grafikk og spillmotorer3D.

Historie

Bruken av oktale trær for 3D-datagrafikk ble introdusert av Donald Meagher ved Rensselaer Polytechnic Institute , og beskrevet i en rapport fra 1980 med tittelen "Octree Encoding: A New Technique for the Representation, Manipulation and Display of Arbitrary 3-D Objects by Computer". Donald Meagher har et patent fra 1995 (med prioritetsdato 1984): "Høyhastighets bildegenerering av komplekse solide objekter ved bruk av oktre-koding ". [1]

Vanlige bruksområder

Merknader

  1. ^ google.com , http://www.google.com/patents/EP0152741B1?cl=no . Hentet 20. september 2012 .
  2. ^ David P. Luebke, Detaljnivå for 3D-grafikk , Morgan Kaufmann, 2003, ISBN  978-1-55860-838-2 .
  3. ^ Elseberg, Jan, et al. " Sammenligning av strategier og implementeringer for søk etter nærmeste nabo for effektiv formregistrering ." Journal of Software Engineering for Robotics 3.1 (2012): 2-12.
  4. ^ Tomas Akenine - Mo ̈ller, Eric Haines og Naty Hoffman, Real-Time Rendering, Fourth Edition , CRC Press, 6. august 2018, ISBN 978-1-351-81615-1 . 
  5. ^ Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation , Proceedings of the 13th International Conference on Information Fusion, Edinburgh, Storbritannia, juli 2010.
  6. ^ V. Drevelle, L. Jaulin og B. Zerr, Guaranteed Characterization of the Explored Space of a Mobile Robot by use Subpavings , NOLCOS 2013.

Relaterte elementer

Eksterne lenker