Удаление скрытых линий
В компьютерной 3D-графике твердые объекты обычно моделируются многогранниками . Грань многогранника — это плоский многоугольник, ограниченный отрезками прямых, называемыми рёбрами . Искривленные поверхности обычно аппроксимируются сеткой полигональной . Компьютерные программы для рисования линий непрозрачных объектов должны иметь возможность решать, какие края или какие части краев скрыты самим объектом или другими объектами, чтобы эти края можно было обрезать во время рендеринга . Эта проблема известна как удаление скрытых строк .
Первое известное решение проблемы скрытых линий было предложено Л.Г. Робертсом. [1] в 1963 году. Однако это сильно ограничивает модель: она требует, чтобы все объекты были выпуклыми . Рут А. Вайс из Bell Labs задокументировала свое решение этой проблемы в 1964 году в статье 1965 года. [2] В 1966 году Иван Э. Сазерленд перечислил 10 нерешённых задач компьютерной графики. [3] Проблема номер семь заключалась в «удалении скрытых строк» . С точки зрения вычислительной сложности эту задачу решил Фрэнк Деваи в 1986 году. [4]
Модели, например, в компьютерном проектировании , могут иметь тысячи или миллионы ребер. Поэтому решающее значение имеет подход к вычислительной сложности, выражающий требования к ресурсам (таким как время и память) как функцию размера задачи. Требования ко времени особенно важны в интерактивных системах.
Размеры задачи по удалению скрытых линий — это общее количество n ребер модели и общее количество v видимых сегментов ребер. Видимость может меняться в точках пересечения изображений ребер. Обозначим через k общее количество точек пересечения изображений ребер. Оба k = Θ( n 2 ) и v = Θ( n 2 ) в худшем случае, [4] но обычно v < k .
Алгоритмы
[ редактировать ]Алгоритмы скрытых линий, опубликованные до 1984 г. [5] [6] [7] [8] разделите края на сегменты линий по точкам пересечения их изображений, а затем проверьте каждый сегмент на видимость относительно каждой грани модели. Предполагая модель набора многогранников с границей каждого топологически эквивалентной сфере и с гранями, топологически эквивалентными дискам, согласно формуле Эйлера, существует Θ( n ) граней. Тестирование Θ( n 2 ) отрезки прямой против Θ( n ) граней занимают Θ( n 3 ) время в худшем случае. [4] Алгоритм Аппеля [5] также нестабильно, поскольку ошибка видимости будет распространяться на последующие конечные точки сегмента. [9]
Оттманн и Видмайер [10] и Оттманн, Видмайер и Вуд [11] предложено O (( n + k ) log 2 n )-временные алгоритмы скрытых линий. Потом Нурми улучшился [12] время работы до O (( n + k ) log n ). Эти алгоритмы принимают Θ( n 2 бревно 2 n ), соответственно Θ( n 2 log n ) время в худшем случае, но если k меньше квадратичного, на практике может быть быстрее.
определять объединение Θ( n ) скрытых интервалов на n Любой алгоритм скрытых линий должен в худшем случае ребрах. Поскольку Ω( n log n ) является нижней границей для определения объединения n интервалов, [13] оказывается, что лучшее, на что можно надеяться, — это Θ( n 2 log n ) время наихудшего случая, и, следовательно, алгоритм Нурми является оптимальным.
Однако фактор log n был исключен Деваем, [4] который поставил открытый вопрос, является ли тот же оптимальный O ( n 2 ) существовала верхняя граница для удаления скрытых поверхностей. Эту проблему решил Маккенна в 1987 году. [14]
Алгоритмы, чувствительные к пересечению [10] [11] [12] известны в основном в литературе по вычислительной геометрии. Квадратичные верхние границы также ценятся в литературе по компьютерной графике: отмечает Гали. [15] что алгоритмы Деваи и Маккенны «представляют собой вехи в алгоритмах видимости» , преодолевая теоретический барьер от O ( n 2 log n ) до O ( n 2 ) для обработки сцены из n ребер.
Другая открытая проблема, поднятая Деваи, [4] Вопрос о том, существует ли O ( n log n + v алгоритм скрытых линий за время ), где v , как отмечалось выше, — это количество видимых сегментов, на момент написания все еще не решен.
Параллельные алгоритмы
[ редактировать ]В 1988 году Деваи предложил [16] параллельный алгоритм с временем O ) , (log n использующий n 2 процессоры для решения проблемы скрытых линий в рамках модели вычислений с параллельным чтением и эксклюзивной записью (CREW) с параллельной машиной произвольного доступа (PRAM). Поскольку произведение номера процессора и времени работы асимптотически больше Θ( n 2 ), последовательная сложность проблемы, алгоритм не является оптимальным по работе, но он демонстрирует, что проблема скрытых линий относится к классу сложности NC , т. е. ее можно решить за полилогарифмическое время с использованием полиномиального числа процессоров.
Алгоритмы скрытой поверхности можно использовать для удаления скрытых линий, но не наоборот. Рейф и Сен [17] предложил O (log 4 n )-временной алгоритм для задачи скрытой поверхности с использованием процессоров CREW PRAM O (( n + v )/log n ) для ограниченной модели многогранных ландшафтов, где v — выходной размер.
В 2011 году Деваи опубликовал [18] ( алгоритм скрытой поверхности за время O log n ) и более простой O (log n алгоритм скрытых линий, также за время ). Алгоритм скрытой поверхности, использующий n 2 /log n процессоры CREW PRAM оптимальны для работы.
Алгоритм скрытых линий использует n 2 Процессоры PRAM с эксклюзивным чтением и эксклюзивной записью (EREW). Модель EREW — это вариант PRAM, наиболее близкий к реальным машинам. Алгоритм скрытых линий выполняет O ( n 2 log n ) работы, что является верхней границей для лучших последовательных алгоритмов, используемых на практике.
Кук, Дворк и Райщук дали нижнюю границу Ω(log n ) для нахождения максимума из n целых чисел, позволяющего использовать бесконечное количество процессоров с любой PRAM без одновременной записи. [19] Нахождение максимального из n целых чисел за постоянное время сводится к проблеме скрытых линий с использованием n процессоров. Следовательно, алгоритм скрытых линий является оптимальным по времени. [18]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ LG Робертс. Машинное восприятие трехмерных тел . Докторская диссертация, Массачусетский технологический институт, 1963 год.
- ^ Рут А. Вайс BE VISION, Пакет программ IBM 7090 FORTRAN для рисования ортогональных представлений комбинаций плоских и квадратичных поверхностей
- ^ IE Сазерленд. Десять нерешённых задач компьютерной графики. Датамация , 12(5):22–27, 1966.
- ^ Jump up to: Перейти обратно: а б с д и Ф. Деваи. Квадратичные границы для исключения скрытых линий. В Proc. 2-й ежегодный симпозиум. по вычислительной геометрии , SCG '86, стр. 269–275, Нью-Йорк, США, 1986.
- ^ Jump up to: Перейти обратно: а б А. Аппель. Понятие количественной невидимости и машинная визуализация твердых тел . В Proc. 22-я национальная конференция , ACM '67, стр. 387–393, Нью-Йорк, штат Нью-Йорк, США, 1967.
- ^ Р. Галимберти и У. Монтанари. Алгоритм устранения скрытых линий . Коммун. ACM , 12(4):206–211, апрель 1969 г.
- ^ Ч. Хорнунг. Подход к алгоритму скрытых линий, минимизирующему вычисления . Компьютеры и графика , 6 (3): 121–126, 1982.
- ^ ПП Лутрел. Решение проблемы скрытых линий для многогранников, нарисованных на компьютере . IEEE Транс. Comput ., 19(3):205–213, март 1970 г.
- ^ Дж. Ф. Блинн. Частичная невидимость. IEEE-компьютер. График. Appl ., 8(6):77–84, ноябрь 1988 г.
- ^ Jump up to: Перейти обратно: а б Т.е. Оттманн и П. Видмайер. Решение проблем видимости с помощью каркасных структур . В Proc. Математические основы информатики, 1984 , стр. 459–470, Лондон, Великобритания, 1984. Springer-Verlag.
- ^ Jump up to: Перейти обратно: а б Т.е. Оттманн, П. Видмайер и Д. Вуд . Эффективный алгоритм устранения скрытых линий в худшем случае . Интерн. Дж. Компьютерная математика , 18 (2): 93–119, 1985.
- ^ Jump up to: Перейти обратно: а б О. Нурми. Алгоритм быстрой очистки линий для устранения скрытых линий . БИТ , 25:466–472, сентябрь 1985 г.
- ^ М.Л. Фредман и Б. Вейде. О сложности вычисления меры U[ai , b i ]. Коммун. ACM , 21:540–544, июль 1978 г.
- ^ М. Маккенна. Оптимальное удаление скрытых поверхностей в худшем случае. АКМ Транс. График. , 6:19–28, январь 1987 г.
- ^ Ш. Гали. Обзор практических алгоритмов видимости пространства объектов . Учебные заметки по SIGGRAPH, 1(2), 2001.
- ^ Ф. Деваи. ( O log N Алгоритм скрытых линий с параллельным временем и точностью ). Достижения в области компьютерного графического оборудования II , стр. 65–73, 1988.
- ^ Дж. Х. Рейф и С. Сен. Эффективный чувствительный к выходным данным алгоритм удаления скрытых поверхностей и его распараллеливание . В Proc. 4-й ежегодный симпозиум. по вычислительной геометрии , SCG '88, стр. 193–200, Нью-Йорк, США, 1988.
- ^ Jump up to: Перейти обратно: а б Ф. Деваи. Оптимальный алгоритм скрытой поверхности и его распараллеливание . В «Вычислительной науке и ее приложениях» , ICCSA 2011, том 6784 конспектов лекций по информатике , стр. 17–29. Шпрингер Берлин/Гейдельберг, 2011.
- ^ С. Кук, К. Дворк и Р. Рейщук. Верхняя и нижняя границы времени для параллельных машин с произвольным доступом без одновременной записи . SIAM J. Comput ., 15:87–97, февраль 1986 г.
Внешние ссылки
[ редактировать ]- Диссертация Патрика-Жиля Майо , расширение алгоритма рисования линий Брезенхема для удаления скрытых линий в 3D; также опубликовано в сборнике статей MICAD '87 по CAD/CAM и компьютерной графике, стр. 591, ISBN 2-86601-084-1 .
- Удаление векторной скрытой линии , статья Уолтера Хегера с дальнейшим описанием (патологических случаев) и дополнительными цитатами.