Удаление скрытых линий - Hidden-line removal

Каркасное изображение с удалением скрытых линий

Твердые объекты обычно моделируются многогранники в компьютерном представлении. Грань многогранника - это плоский многоугольник, ограниченный прямыми отрезками, называемыми ребрами. Изогнутые поверхности обычно аппроксимируются многоугольной сеткой. Компьютерные программы для рисования линий непрозрачных объектов должны иметь возможность решать, какие кромки или какие части кромок скрыты самим объектом или другими объектами. Эта проблема известна как удаление скрытой линии.

Первое известное решение проблемы скрытых линий было разработано Робертсом.[1] в 1963 г. Однако он сильно ограничивает модель: он требует, чтобы все объекты были выпуклыми. Рут А. Вайс из Bell Labs задокументировала решение этой проблемы в 1964 году в статье 1965 года.[2]В 1966 г. Иван Э. Сазерленд перечислил 10 нерешенных проблем компьютерной графики.[3] Проблема номер семь была "удаление скрытой линии". С точки зрения вычислительной сложности эта проблема была решена Devai в 1986 году.[4]

Модели, например, в системе автоматизированного проектирования, могут иметь тысячи или миллионы граней. Следовательно, решающее значение имеет подход вычислительной сложности, выражающий потребности в ресурсах, таких как время и память, в зависимости от размера проблемы. Требования ко времени особенно важны в интерактивных системах.

Размеры проблем для удаления скрытых линий - это общее количество п кромок модели и общее количество v видимых сегментов краев. Видимость может измениться в точках пересечения изображений краев. Позволять k обозначим общее количество точек пересечения образов ребер. Обе k = Θ (п2) и v = Θ (п2) в худшем случае[4] но обычно v < k.

Алгоритмы

Алгоритмы скрытых линий, опубликованные до 1984 г.[5][6][7][8] разделите края на линейные сегменты по точкам пересечения их изображений, а затем проверьте каждый сегмент на видимость на каждой грани модели. Если предположить модель набора многогранников с границей каждого топологически эквивалентной сфере и гранями, топологически эквивалентными кругам, согласно формуле Эйлера существует Θ (п) лица. Тестирование Θ (п2) отрезки прямой напротив Θ (п) граней принимает Θ (п3) время в худшем случае.[4] Алгоритм Аппеля[5] также нестабилен, потому что ошибка видимости будет распространяться на последующие конечные точки сегмента.[9]

Оттманн и Видмайер[10] и Оттманн, Видмайер и Дерево[11]предложил О((п + k) бревно2 п) -временные алгоритмы скрытых линий. Потом Нурми поправился[12] время работы до О((п + k) бревноп). Эти алгоритмы принимают Θ (п2 бревно2 п) соответственно Θ (п2 бревноп) время в худшем случае, но если k меньше квадратичного, на практике может быть быстрее.

Любой алгоритм скрытых линий должен определять объединение Θ (п) скрытые интервалы на п края в худшем случае. Поскольку Ω (п бревноп) - оценка снизу для определения объединения п интервалы,[13]похоже, что лучшее, на что можно надеяться, - это Θ (п2 бревноп) время наихудшего случая, и, следовательно, алгоритм Нурми является оптимальным.

Однако журналп фактор был устранен Деваи,[4] кто поднял открытую проблему, такой же оптимальный О(п2) существовала верхняя граница для удаления скрытых поверхностей. Эту проблему решил МакКенна в 1987 году.[14]

Чувствительные к пересечению алгоритмы[10][11][12] в основном известны в литературе по вычислительной геометрии. Квадратичные верхние границы также высоко ценятся в литературе по компьютерной графике: Гали отмечает[15] что алгоритмы Деваи и МакКенны "представляют вехи в алгоритмах видимости", преодолевая теоретический барьер от О(п2 бревноп) к О(п2) для обработки сцены п края.

Другая открытая проблема, поднятая Деваи,[4] о том, существует ли О(п бревноп + v) -время алгоритма скрытой линии, где v, как отмечалось выше, это количество видимых сегментов, все еще не решенное на момент написания.

Параллельные алгоритмы

В 1988 году Деваи предложил[16] ан О(бревноп) -временной параллельный алгоритм с использованием п2 процессоров для проблемы скрытой линии под одновременное чтение, эксклюзивная запись (CREW) модель вычислений с параллельной машиной произвольного доступа (PRAM). Поскольку произведение номера процессора и времени работы асимптотически больше, чем (п2), последовательная сложность задачи, алгоритм не является оптимальным для работы, но он демонстрирует, что проблема скрытой линии находится в класс сложности NC, т.е. ее можно решить за полилогарифмическое время, используя полиномиальное количество процессоров.

Алгоритмы скрытых поверхностей можно использовать для удаления скрытых линий, но не наоборот. Рейф и Сен [17] предложил О(бревно4 п) -временной алгоритм для задачи о скрытых поверхностях с использованием О((п + v)/бревноп) CREW PRAM для ограниченной модели многогранных ландшафтов, где v размер вывода.

В 2011 году Деваи опубликовал[18] ан О(бревноп) -time hidden-surface, а также более простой О(бревноп) -время, алгоритм скрытой линии. Алгоритм скрытой поверхности, использующий п2/бревноп Процессоры CREW PRAM работают оптимально.

Алгоритм скрытой линии использует п2 эксклюзивное чтение, эксклюзивная запись (EREW) процессоры PRAM. Модель EREW - наиболее близкий к реальным машинам вариант PRAM. Алгоритм скрытой линии делает О(п2 бревноп), что является верхней границей лучших последовательных алгоритмов, используемых на практике.

Кук, Дворк и Рейщук дали оценку Ω (логп) нижняя оценка нахождения максимума п целые числа, позволяющие бесконечно много процессоров любой PRAM без одновременной записи.[19] Нахождение максимума п целые числа постоянно сводится к проблеме скрытой линии с помощью п процессоры. Следовательно, алгоритм скрытых линий является оптимальным по времени.[18]

Рекомендации

  1. ^ Л. Г. Робертс. Машинное восприятие трехмерных тел. Кандидатская диссертация, Массачусетский технологический институт, 1963 г.
  2. ^ Рут А. Вайс [https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-weiss.pdf BE VISION, пакет программ IBM 7090 FORTRAN для рисования ортогональных представлений Комбинации плоских и квадрических поверхностей]
  3. ^ И. Э. Сазерленд. Десять нерешенных проблем компьютерной графики. Датамация, 12(5):22–27, 1966.
  4. ^ а б c d е Ф. Деваи. Квадратичные оценки для исключения скрытых линий. В Proc. 2-й ежегодный симпозиум. по вычислительной геометрии, SCG ’86, pp. 269–275, New York, NY, USA, 1986.
  5. ^ а б А. Аппель. Понятие количественной невидимости и машинная визуализация твердых тел. В Proc. 22-я национальная конференция, ACM ’67, pp. 387–393, New York, NY, USA, 1967.
  6. ^ Р. Галимберти и У. Монтанари. Алгоритм устранения скрытых линий. Commun. ACM, 12 (4): 206–211, апрель 1969.
  7. ^ Гл. Hornung. Подход к алгоритму скрытых линий с минимальным расчетом. Компьютеры и графика, 6(3):121–126, 1982.
  8. ^ П. П. Лутрель. Решение проблемы скрытых линий для нарисованных компьютером многогранников. IEEE Trans. Вычислить., 19 (3): 205–213, март 1970.
  9. ^ Дж. Ф. Блинн. Дробная невидимость. IEEE Comput. График. Приложение., 8 (6): 77–84, ноябрь 1988 г.
  10. ^ а б Чт. Оттманн и П. Видмайер. Решение проблем видимости с помощью каркасных структур. В Proc. Математические основы компьютерных наук 1984, pp. 459–470, London, UK, 1984. Springer-Verlag.
  11. ^ а б Чт. Оттманн, П. Видмайер и Д. Вуд. Наихудший эффективный алгоритм устранения скрытых линий. Междунар. J. Компьютерная математика, 18(2):93–119, 1985.
  12. ^ а б О. Нурми. Быстрый алгоритм линейной развертки для устранения скрытых линий. КУСОЧЕК, 25: 466–472, сентябрь 1985 г.
  13. ^ М. Л. Фредман и Б. Вейде. О сложности вычисления меры U [aя, бя]. Commun. ACM, 21: 540–544, июль 1978 г.
  14. ^ М. Маккенна. Оптимальное удаление скрытых поверхностей в наихудшем случае. ACM Trans. График., 6: 19–28, январь 1987 г.
  15. ^ Ш. Гали. Обзор практических алгоритмов видимости объектного пространства. SIGGRAPH Tutorial Notes, 1 (2), 2001.
  16. ^ Ф. Деваи. An О(бревноN) параллельный алгоритм точных скрытых линий. Достижения в области аппаратного обеспечения компьютерной графики II, 1988, с. 65–73.
  17. ^ Дж. Х. Рейф и С. Сен. Эффективный чувствительный к выходу алгоритм удаления скрытой поверхности и его распараллеливание. В Proc. 4-й ежегодный симпозиум. по вычислительной геометрии, SCG ’88, pp. 193–200, New York, NY, USA, 1988.
  18. ^ а б Ф. Деваи. Оптимальный алгоритм скрытой поверхности и его распараллеливание. В Вычислительная наука и ее приложения, ICCSA 2011, том 6784 из Конспект лекций по информатикеС. 17–29. Springer Berlin / Heidelberg, 2011 г.
  19. ^ С. Кук, К. Дворк, Р. Рейщук. Верхняя и нижняя границы времени для параллельных машин с произвольным доступом без одновременной записи. SIAM J. Comput., 15: 87–97, февраль 1986 г.

внешняя ссылка

  • Диссертация Патрика-Жиля Майо, расширение Алгоритм рисования линий Брезенхема выполнять удаление 3D скрытых линий; также опубликовано в трудах MICAD '87 по CAD / CAM и компьютерной графике, стр. 591, ISBN  2-86601-084-1.
  • Удаление векторной скрытой линии, статья Вальтера Хегера с дальнейшим описанием (патологических случаев) и другими цитатами.