Wat is een Octree?

Een octree is een digitale boomstructuur die wordt gebruikt om driedimensionale (3D) en veelhoekige creaties te maken, meestal voor de game-industrie. In de octree-structuur heeft elke interne node geen kinderen of acht kinderen - niets ertussenin - en kan elke node kleurinformatie bevatten voor het rood-blauw-groene (RGB) kleurprofiel. De hele structuur begint als één kubus en lege interne kubussen worden gebruikt voor botsingsinformatie. Deze structuur is zeer geheugenefficiënt, omdat er een relatief kleine hoeveelheid gegevens in elk kind wordt bewaard en de structuur beperkt kan zijn.

Wanneer een model is gemaakt voor een videogame, moet het over textuur- en kleurinformatie beschikken en moet het in botsing kunnen komen met andere modellen. Een van de structuren die in deze industrie worden gebruikt, is het octree. Soms een oct-boom genoemd, betekent deze naam het belang van het nummer acht in deze boomstructuur. Net als boomstructuren maken, heeft de octree ouder- en kindknooppunten. In tegenstelling tot andere bomen, is er heel weinig variatie in hoeveel kinderknooppunten van de ouder kunnen worden gemaakt.

Elke ouder kan acht of geen knooppunten bevatten. Beide kubustypes zijn belangrijk bij het maken van een volledig gerenderd model. De meest intensieve kubussen zijn die met acht knooppunten. Elke interne knoop bevat kleur- en textuurinformatie, zodat het model een ingewikkeld uiterlijk kan hebben. Als het model bijvoorbeeld een boom is, moet elk van de interne knooppunten een bruine kleur voor de stam en schaduwinformatie bevatten om een ​​realistische textuur te creëren.

Terwijl de kubussen met acht knopen belangrijk zijn voor een octree, zijn de lege kubussen net zo belangrijk. De hele structuur begint als een grote lege kubus, die andere kleinere kubussen kunnen bewonen. Deze kubus wordt samen met andere lege kubussen hoofdzakelijk gebruikt voor informatie over botsingen. Als een model bijvoorbeeld tegen dit model botst, vertellen de lege kubussen het model dat het niet verder kan, omdat het een botsing veroorzaakt.

Het maken van een goed model met een octree is intensief en er gaat veel informatie in, maar de structuur zelf gebruikt het geheugen zeer efficiënt. Een reden hiervoor is dat, hoewel er veel codering is, de informatie alleen kleur- en textuurinformatie is en dus vrij klein. Een andere reden is dat de boom verschillende niveaus heeft die onnodige gegevens bevatten en, indien gesnoeid, het geheugen nog meer kan worden verkleind.