Malířův algoritmus

Jste zde:
Odhadovaná doba čtení: 2 min

Malířův algoritmus (také algoritmus hloubkového třídění a prioritní výplň ) je algoritmus pro určování viditelného povrchu ve 3D počítačové grafice, který pracuje na bázi mnohoúhelníku po mnohoúhelníku spíše než pixel po pixelu, řádek po řádku nebo oblast po ploše jiných algoritmů pro odstranění skrytého povrchu. Malířův algoritmus vytváří obrazy tak, že seřadí polygony v obraze podle jejich hloubky a každý polygon umístí v pořadí od nejvzdálenějšího k nejbližšímu objektu.

Algoritmus byl původně navržen jako základní metoda pro řešení problému určování skrytého povrchu Martinem NewellemRichardem Newellem a Tomem Sanchou v roce 1972, zatímco všichni tři pracovali v CADCentreNázev „Painter algoritmus“ odkazuje na techniku ​​používanou mnoha malíři, kde začínají malováním vzdálených částí scény před částmi, které jsou blíže, čímž pokrývají některé oblasti vzdálených částí. Podobně algoritmus seřadí všechny polygony ve scéně podle jejich hloubky a pak je vybarví v tomto pořadí, od nejvzdálenějšího k nejbližšímu. Přebarví části, které normálně nejsou vidět – čímž vyřeší problém s viditelností – za cenu toho, že namaluje neviditelné oblasti vzdálených objektů. Uspořádání, které algoritmus používá, se nazývá „ pořadí hloubky“ a nemusí respektovat číselné vzdálenosti k částem scény: podstatnou vlastností tohoto uspořádání je spíše to, že pokud jeden objekt zakryje část druhého, pak je první objekt namalován za objektem, který zakrývá. Platné uspořádání lze tedy popsat jako topologické uspořádání orientovaného acyklického grafu reprezentujícího okluze mezi objekty.

Časová složitost algoritmu je silně závislá na třídicím algoritmu použitém k uspořádání polygonů. Za předpokladu použití nejoptimálnějšího třídícího algoritmu má algoritmus složitost nejhoršího případu O ( n log n + m*n ), kde n je počet polygonů a m je počet pixelů, které mají být vyplněny.

Nejhorší případ prostorové složitosti algoritmu je O ( n+m ), kde n je počet polygonů a m je počet pixelů, které mají být vyplněny.

Algoritmus není tak složitý ve struktuře jako jeho jiné protějšky s algoritmem hloubkového třídění. Komponenty, jako je pořadí vykreslování založené na hloubce, které používá algoritmus, jsou jedním z nejjednodušších způsobů, jak určit pořadí grafické produkce. Tato jednoduchost jej činí užitečným v základních scénářích výstupu počítačové grafiky, kde bude třeba provést jednoduché vykreslení s malým úsilím.

Na počátku 70. let, kdy byl vyvinut algoritmus, byla fyzická paměť relativně malá. To vyžadovalo, aby programy spravovaly paměť co nejúčinněji, aby mohly provádět velké úkoly bez zhroucení. Algoritmus upřednostňuje efektivní využití paměti, ale na úkor vyššího výpočetního výkonu, protože všechny části všech obrázků musí být vykresleny. Algoritmus může v některých případech selhat, včetně cyklického překrývání nebo proražení polygonů. Případ proražení polygonů nastává, když jeden polygon protíná druhý. Podobně jako u cyklického překrývání lze tento problém vyřešit oříznutím problematických polygonů. V základních implementacích může být malířův algoritmus neefektivní. Přinutí systém vykreslit každý bod na každém polygonu ve viditelné sadě, i když je tento polygon v hotové scéně uzavřen. To znamená, že u detailních scén může malířův algoritmus příliš zatěžovat počítačový hardware.

Byl tento článek užitečný?
Nelíbí 0
Zobrazeno: 3
Back to top button