Przegląd głównych algorytmów grafiki komputerowej: klasyfikacja i zastosowania
Grupy algorytmów grafiki komputerowej
Istnieją dwa poziomy algorytmów grafiki komputerowej: dolny i górny. Przeznaczeniem grupy dolnej jest realizacja takich prymitywów graficznych jak linia, okrąg, wypełnienia i inne. Swoje zastosowanie algorytmy te znalazły w bibliotekach graficznych języków programowania wysokiego poziomu, a także na poziomie sprzętowym w procesorach graficznych stacji roboczych. Do grupy górnego poziomu należą algorytmy usuwania niewidocznych linii i powierzchni. Warto zaznaczyć, że wyświetlanie obiektów w tych algorytmach jest zapewniane przez prymitywy implementujące algorytmy poziomu dolnego. W związku z tym należy odpowiedzialnie podchodzić do wyboru i opracowywania efektywnych algorytmów dolnego poziomu.
Charakterystyce cech algorytmów poziomu dolnego pomoże ich pogrupowanie w ramach tego poziomu, przeprowadzone przez uczestników jednego z forów programistycznych [www.cyberforum.ru/]. Do pierwszej grupy można zaliczyć najprostsze algorytmy, wyróżniające się prostotą implementacji i matematycznymi metodami ich uzyskiwania. Niestety takie implementacje nie mogą pochwalić się niskimi wymaganiami pamięciowymi ani małymi nakładami obliczeniowymi. Druga grupa wykorzystuje bardziej złożone podejścia matematyczne, często heurystyczne, ale takie algorytmy są już bardziej efektywne niż te z pierwszej grupy. Trzecia grupa obejmuje algorytmy, które mogą być realizowane na poziomie sprzętowym bez większych przeszkód; przedstawicielami tej grupy są te, które dopuszczają paralelizację, algorytmy rekurencyjne oraz takie, które można zrealizować przy użyciu najprostszych instrukcji. Do czwartej grupy należą algorytmy o specjalnym przeznaczeniu, takie jak eliminacja efektu schodkowania (aliasing) i inne.
Na zadania algorytmów poziomu górnego przypada m.in. usuwanie niewidocznych linii i powierzchni; rozwiązywanie tego problemu pozostaje nadal aktualne w grafice komputerowej. Jakość i szybkość budowy obrazu trójwymiarowego zależą od efektywności algorytmów rozwiązujących to zadanie. Niestety obecnie istniejące algorytmy cechują się znacznymi nakładami obliczeniowymi. Poziom górny obejmuje także zadanie renderowania, czyli wypełniania obrazów półtonowych. Obejmuje to uwzględnianie właściwości powierzchni obiektu, takich jak odbicie światła, przezroczystość, załamanie oraz zjawiska związane z charakterem i liczbą źródeł światła.
Różne cechy algorytmów mogą być istotne w zależności od obszaru zastosowań grafiki komputerowej. Na przykład grafika naukowa preferuje uniwersalność algorytmu ponad jego szybkością. Natomiast w systemach symulacyjnych, charakteryzujących się poruszającymi się obiektami, szybkość działania jest jednym z najważniejszych kryteriów wyboru algorytmu, ponieważ konieczne jest uzyskiwanie obrazu w czasie rzeczywistym.
Warto poświęcić uwagę grafice rastrowej; jej wyświetlacz przedstawia się jako macierz dyskretnych elementów o określonych parametrach fizycznych. Ponieważ ich liczba jest znacznie ograniczona, aby narysować na przykład linię, należy dokonać aproksymacji tej linii przy jej odwzorowaniu na płaszczyźnie dyskretnej. Odwzorowanie obiektu na tę płaszczyznę nazywa się rastrową reprezentacją obiektu.