Octree

Des nœuds d'octree dépeints en tant que division d'un espace de couleur.

Un octree est une structure de données de type arbre dans laquelle chaque nœud peut compter jusqu'à huit enfants. Les octrees sont le plus souvent utilisés pour partitionner un espace tridimensionnel en le subdivisant récursivement en huit octants.

Quelques utilisations courantes des octrees :

  • l'indexation spatiale
  • la détection efficace de collision dans le cadre de la 3D
  • l'élimination des objets hors du cône de vue dans le cadre d'un rendu 3D
  • l'observateur d'état[1].

Les octrees sont l'analogie tridimensionnelle des quadtrees. Le nom est formé à partir d'octo (οκτώ « huit », en grec) et de tree (« arbre », en anglais) et s'écrit octree (avec un seul « t »). Chaque nœud d'un octree subdivise l'espace qu'il représente en huit sous-espaces (les octants).

Dans le cas d'un octree de type « point region » (PR), le nœud mémorise explicitement un point tridimensionnel qui est le « centre » de la subdivision pour ce nœud ; le point définit alors l'un des coins de chacun des huit enfants. Le nœud racine d'un octree de type PR peut représenter un espace infini.

Dans un octree de type « MX », le point de subdivision est implicitement le centre de l'espace que le nœud représente. Le nœud racine d'un octree de type MX doit représenter un espace fini de manière que les centres implicites des nœud soient bien définis.

Application pour la quantification de couleurs

L'algorithme d'octree de quantification de couleur (en), inventé par Gervautz et Pergathofer en 1988, encode les données de couleur d'une image en tant qu'octree pouvant aller jusqu'à neuf niveaux de profondeur. Les octrees sont utilisés parce que et qu'il y a trois composantes de couleurs dans le système RVB.

L'indice de nœud pour qu'il s'étende à partir du niveau plafond est déterminé par une formule qui utilise les bits les plus significatifs des composantes rouge, verte et bleue, 4r + 2g + b, par exemple. Le niveau inférieur suivant utilise les bits les plus significatifs suivants, et ainsi de suite. Les bits les moins significatifs sont parfois ignorés afin de réduire la taille de l'arbre.

L'algorithme est grandement efficace du point de vue de la consommation de mémoire puisqu'il limite la taille de l'arbre. Le niveau plancher de l'octree est constitué de nœuds terminaux qui accumulent les données de couleur qui ne sont pas représentées dans l'arbre. Ces nœuds contiennent initialement des bits uniques. Si bien plus de couleurs de palette que la quantité désirée sont entrées dans l'octree, sa taille peut être continuellement réduite en cherchant après un nœud plancher et en moyennant ses bits dans un nœud terminal, éliminant ainsi diverses parties de l'arbre.

Une fois que la phase d'échantillonnage est terminée on obtiendra approximativement le nombre requis de couleurs en parcourant toutes les routes possible de l'arbre en partant de son nœud racine jusqu'à ses nœuds terminaux tout en tenant compte, au passage, des différents bits.

Notes et références

  1. ↑ (en) Henning Eberhardt, Vesa Klumpp et Uwe D. Hanebeck, Density Trees for Efficient Nonlinear State Estimation, dans Proceedings of the 13th International Conference on Information Fusion, Édimbourg, juillet 2010

Voir aussi

Articles connexes

Liens externes

v · m
Arbre binaire
Arbre équilibré
Arbre B
Trie
Partition binaire de l'espace trees
Arbres non binaires
Arbre de base de données spatiales
Autres arbres

Read other articles:

Ivan Hašek

Ivan Hašek Informasi pribadiNama lengkap Ivan HašekTanggal lahir 6 September 1963 (umur 60)Tempat lahir Městec Králové, Republik CekoPosisi bermain PenyerangKarier senior*Tahun Tim Tampil (Gol)1981-1990 Sparta Prague 1990-1994 Strasbourg 1994-1995 Sanfrecce Hiroshima 1996 JEF United Ichihara 1997-1998 Sparta Prague Tim nasional1984-1993 Cekoslowakia 54 (5)1994 Republik Ceko 1 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik Ivan Hašek (lahir 6 September 19...

 

The Catalyst

Untuk zat dalam kimia, lihat Katalis. The CatalystSingel oleh Linkin Parkdari album A Thousand Suns dan Medal of HonorSisi-BNew Divide (Live)Dirilis02 Agustus 2010 (2010-08-02)FormatCD, unduhan digitalDirekam2008–2010GenreElectronic rock,[1] techno[2]Durasi5:42LabelWarner Bros.PenciptaLinkin ParkProduserRick Rubin, Mike ShinodaKronologi singel New Divide (2009) The Catalyst (2010) Waiting for the End ((2010)) Video musikThe Catalyst di YouTube The Catalyst adalah lagu k...

 

أفتون (قرية)

  لمعانٍ أخرى، طالع أفتون (توضيح). أفتون الإحداثيات 42°13′45″N 75°31′29″W / 42.2292°N 75.5247°W / 42.2292; -75.5247  [1] تقسيم إداري  البلد الولايات المتحدة[2]  التقسيم الأعلى مقاطعة تشينانغو  خصائص جغرافية  المساحة 4.143112 كيلومتر مربع4.142908 كيلومتر مربع (1 أبريل...

العلاقات البنمية الزيمبابوية

العلاقات البنمية الزيمبابوية بنما زيمبابوي   بنما   زيمبابوي تعديل مصدري - تعديل   العلاقات البنمية الزيمبابوية هي العلاقات الثنائية التي تجمع بين بنما وزيمبابوي.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة...

 

Buff-bellied monarch

Species of bird Buff-bellied monarch Conservation status Least Concern  (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Passeriformes Family: Monarchidae Genus: NeolalageMathews, 1928 Species: N. banksiana Binomial name Neolalage banksiana(G.R. Gray, 1870) Synonyms Lalage banksiana The buff-bellied monarch (Neolalage banksiana) is a species of bird in the family Monarchidae. It is monotypic within the genus Neol...

 

Bell 412

Utility transport helicopter family by Bell Bell 412 Bell 412EP of the NSW Police Sydney Role Multipurpose utility helicopterType of aircraft National origin United States/Canada Manufacturer Bell Helicopter First flight August 1979; 44 years ago (1979-08) Introduction 1981; 43 years ago (1981) Primary users Japan Ground Self Defence ForceSee Operators for others Produced 1979–present Number built 1,300+[1] Developed from Bell 212 Varian...

Portland Firefighters Park

Public park in Portland, Oregon, U.S. Portland Firefighters ParkThe park in 2010TypePublic park[1]LocationSW 19th Avenue & West Burnside StreetPortland, OregonCoordinates45°31′22″N 122°41′24″W / 45.522735°N 122.690011°W / 45.522735; -122.690011Operated byDavid Campbell Memorial AssociationStatusOpen all year David Campbell MemorialU.S. National Register of Historic Places Built1928NRHP reference No.10000802Added to NRHPSeptember 2...

 

Theodore William Richards

Pour les articles homonymes, voir Richards. Theodore William RichardsTheodore William RichardsBiographieNaissance 31 janvier 1868GermantownDécès 2 avril 1928 (à 60 ans)CambridgeSépulture Cimetière de Mount AuburnNationalité américaineFormation Université HarvardHaverford CollegeActivité ChimistePère William Trost RichardsMère Anna Matlack Richards (en)Fratrie Anna Richards Brewster (en)Autres informationsA travaillé pour Université HarvardUniversité de PrincetonMembre de A...

 

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。 美國眾議院 United States House of Representatives第118届美国国会众议院徽章 众议院旗...

Nazareno Strampelli

Nazareno Strampelli[1] Senatore del Regno d'ItaliaDurata mandato26 febbraio 1929 –23 gennaio 1942 LegislaturaXXVIII legislatura del Regno d'Italia Incarichi parlamentari Membro della Commissione delle Finanze (1º maggio 1934 - 2 marzo 1939) Membro della Commissione dell'economia corporativa e dell'autarchia (17 aprile 1939 - 28 gennaio 1940) Vicepresidente della Commissione dell'agricoltura (17 aprile 1939 - 23 gennaio 1942) Sito istituzionale Dati generaliFirma ...

 

Istirahat sekolah

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

 

Hyundai Matrix

Untuk mobil kompak yang diproduksi Toyota, lihat Toyota Matrix. Hyundai MatrixInformasiProdusenHyundai Motor CompanyJuga disebutHyundai LavitaHyundai Elantra Lavita (Australia)Inokom MatrixMasa produksi2001—2010PerakitanUlsan, Korea Selatanİzmit, Turki (Hyundai Assan)[1]Kulim, MalaysiaPerancangPininfarinaKesamaanFiat MultiplaMitsubishi Space StarOpel MerivaRenault ModusBodi & rangkaBentuk kerangkaMobil MPV 5 pintuMobil terkaitHyundai ElantraHyundai TucsonHyundai Tibur...

Emgrand

Not to be confused with the Nissan Elgrand van. EmgrandEmgrand's dealership in Shanghai, ChinaNative name帝豪Company typePrivateIndustryAutomobile manufacturingFoundedAugust 2009; 14 years ago (2009-08) in Shanghai, ChinaDefunct2014 (2014)FateMerged with GeelyParentGeelyWebsiteOfficial website Emgrand was an automobile marque owned by the Chinese automotive manufacturer Geely.[1] It was launched in August 2009 and discontinued in 2014 after its products w...

 

Ram Mandir, Ayodhya

Kuil Ram Ram Mandir அயோத்தி இராமர் கோயில் राम मंदिरKuil semasa upacara Prana PratishtaAgamaAfiliasiHinduDistrikRam JanmabhoomiProvinsiAyodhyaDewaRamaLokasiNegaraIndiaArsitekturTipeSenibina NagaraDibuat olehShri Ram Janmbhoomi Teerth KshetraRampung2024Situs web[1] Ram Mandir (Hindi: राम मंदिर, har. 'Kuil Rama') adalah sebuah kuil Hindu yang berlokasi di situs ziarah suci Ram Janmabhoomi di Ayodhya, Uttar Pra...

 

Cannabis in New York

Use of cannabis in New York State A medical marijuana dispensary in Newburgh Part of a series onCannabis ArtsCulture 420 (chan) Books Magu (deity) Names Religion Judaism Latter-day Saints Sikhism Smoke-in Spiritual use Sports Stoner film Stoner rock Terms Chemistry Phytocannabinoids Quasi-psychedelic delta-8-THC delta-10-THC THC THCH THCP Other CBD CBDH CBDP Semi-synthetic cannabinoids THC-O-acetate Synthetic cannabinoids AM AM-2201 CP CP-55940 Dimethylheptylpyran HU HU-210 HU-331 JWH JWH-018...

Beach volleyball at the 2016 Summer Olympics – Men's tournament

Men's beach volleyballat the Games of the XXXI OlympiadVenueCopacabana StadiumDates6–18 August 2016Competitors48 from 17 nationsTeams24Medalists Alison CeruttiBruno Oscar Schmidt  Brazil Daniele LupoPaolo Nicolai  Italy Alexander BrouwerRobert Meeuwsen  Netherlands← 20122020 → Volleyball at the2016 Summer OlympicsIndoorQualificationmenwomenTournamentmenwomenRostersmenwomenBeachQualificationmenwomenTournamentmenwomenvte The men's beach volleyba...

 

Giovanni Pitruzzella

Italian jurist You can help expand this article with text translated from the corresponding article in Italian. (November 2023) Click [show] for important translation instructions. View a machine-translated version of the Italian article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into ...

 

Party Pier station

Haizhu Tram station in Guangzhou Party Pier琶醍General informationLocationHaizhu, Guangzhou, GuangdongChinaOperated byGuangzhou Metro Co. Ltd.Line(s)     Haizhu TramHistoryOpened21 October 2015[1]Services Preceding station Guangzhou Metro Following station Liede Bridge Southtowards Canton Tower Haizhu Tram Nanfengtowards Wanshengwei Party Pier station (Chinese: 琶醍站), is a station of Haizhu Tram of the Guangzhou Metro. It started operations on 21 Oc...

Édouard Chatton

French biologist Édouard ChattonBorn11 October 1883Romont, SwitzerlandDied23 April 1947(1947-04-23) (aged 63)Banyuls-sur-Mer, FranceNationalityFrenchKnown forDistinction between prokaryotes and eukaryotesScientific careerFieldsBiologyAuthor abbrev. (botany)Chatton Édouard Chatton (French: [edwaʁ ʃatɔ̃]; 11 October 1883 – 23 April 1947)[1] was a French biologist who first characterized the distinction between the prokaryotic and eukaryotic cellular ty...

 

Big Wolf on Campus

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Big Wolf on Campus – news · newspapers · books · scholar · JSTOR (December 2016) (Learn how and when to remove this message) Canadian TV series or program Big Wolf on CampusOpening titleGenreSupernatural fiction Comedy SuperheroCreated byChris BriggsPeter A. Kn...