новая классификация алгоритмов компьютерной графики

Воинов С.Б.

Научный руководитель: проф. Авдошин С.М.

«МАТИ» – Российский Государственный Технологический Университет
им. К. Э. Циолковского,

121552, Москва, Оршанская 3, e-mail: svoinov@forte-it.ru

Анализ современной литературы и электронных источников по тематике, связанной с компьютерной графикой, показал отсутствие четкой классификации алгоритмов компьютерной графики с учетом последних достижений в этом направлении.

В данном тезисе сделана попытка составить краткую классификацию алгоритмов компьютерной графики с учетом не только последних теоретических достижений, но и с учетом прорыва в области аппаратной реализации алгоритмов.

Используемые признаки классификации:

1. по сложности:

1.1. низкоуровневые – предназначенные для реализации графических примитивов;

1.2. высокоуровневые – алгоритмы удаления невидимых линий и поверхностей, алгоритмы оптимизации.

2. по реализации:

2.1. реализуемые программно;

2.2. реализуемые аппаратно.

3. по функциональному назначению:

3.1. алгоритмы рисования геометрических примитивов;

3.2. алгоритмы заливки граней;

3.3. алгоритмы удаления невидимых линий и поверхностей;

3.4. алгоритмы оптимизации;

3.5. алгоритмы текстурирования;

3.6. алгоритмы обработки вершин и пикселей выводимых треугольников (так называемые шейдеры – shaders);

3.7. алгоритмы трассировки лучей;

3.8. алгоритмы физического моделирования.

4. по используемому математическому аппарату:

4.1. алгоритмы, использующие аппарат линейной алгебры;

4.2. алгоритмы, использующие нелинейные уравнения;

4.3. алгоритмы, использующие дифференциальное и интегральное исчисление;

4.4. алгоритмы, использующие преобразования и методы цифровой обработки сигналов.

4.5. эвристические алгоритмы.

5. по асимптотической временной оценке сложности:

5.1. линейные, с оценкой O(n);

5.2. логарифмические, с оценкой O(n log n);

5.3. с оценкой хуже логарифмической – O(n²) и т.д.

6. по поддержке современными графическими интерфейсами программирования:

6.1. поддерживаемые современными графическими API (GDI+, OpenGL, Direct3D, Cg);

6.2. неподдерживаемые современными графическими API.

7. по области применения:

7.1. обработка плоских изображений;

7.2. построение реалистичных изображений;

7.3. геоинформационные системы (GIS);

7.4. системы компьютерного видения (computer vision);

7.5. физическое моделирование.

Представленная краткая классификация представляет собой общие положения классификации, составленной в рамках диссертационной работы на тему «Разработка и исследование математических моделей алгоритмов цифровой обработки сигналов в задачах компьютерной графики». В дальнейшем предполагается использовать классификацию для исследования тех алгоритмов компьютерной графики, в которых можно применить алгоритмы и методы цифровой обработки сигналов.