Из Википедии, бесплатной энциклопедии
  (Перенаправлен из удаления скрытой линии )
Перейти к навигации Перейти к поиску
Каркасное изображение с удалением скрытых линий

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

Первое известное решение проблемы скрытых линий было разработано LG Roberts [1] в 1963 году. Однако оно сильно ограничивает модель: оно требует, чтобы все объекты были выпуклыми. Рут А. Вайс из Bell Labs задокументировала решение этой проблемы в 1964 году в статье 1965 года. [2] В 1966 году Иван Сазерленд перечислил 10 нерешенных проблем компьютерной графики. [3] Проблема номер семь была «удаление скрытой строки» . С точки зрения вычислительной сложности эта проблема была решена Devai в 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  log 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 году Devai предложил [16] O (журнал  N ) -время параллельный алгоритм с использованием п 2 процессоров для задачи скрытой линии под одновременным чтения, эксклюзивные записи (CREW) параллельно машина с произвольным доступом (PRAM) модели вычислений. Поскольку произведение номера процессора и времени выполнения асимптотически больше, чем ( n 2 ), последовательная сложность задачи, алгоритм не является оптимальным для работы, но он демонстрирует, что проблема скрытой линии находится в классе сложности NC , т.е. ее можно решить за полилогарифмическое время, используя полиномиальное количество процессоров.

Для удаления скрытых линий можно использовать алгоритмы скрытых поверхностей, но не наоборот. Рейф и Сен [17] предложили алгоритм за время O (log 4  n ) для проблемы скрытых поверхностей, используя O (( n + v ) / log  n ) процессоров CREW PRAM для ограниченной модели многогранных поверхностей, где 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]

Ссылки [ править ]

  1. ^ LG Робертс. Машинное восприятие трехмерных тел . Кандидатская диссертация, Массачусетский технологический институт, 1963 г.
  2. ^ Рут А. Вайс [ https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-weiss.pdf BE VISION, Пакет программ IBM 7090 FORTRAN для рисования ортогональных представлений комбинаций Плоские и квадратные поверхности]
  3. ^ IE Сазерленд. Десять нерешенных проблем компьютерной графики. Датамейшн , 12 (5): 22–27, 1966.
  4. ^ а б в г д Ф. Деваи. Квадратичные оценки исключения скрытых линий. В Proc. 2-й ежегодный симпозиум. по вычислительной геометрии , SCG '86, стр. 269–275, Нью-Йорк, Нью-Йорк, США, 1986.
  5. ^ а б А. Аппель. Понятие количественной невидимости и машинная визуализация твердых тел . В Proc. 22-я Национальная конференция , ACM '67, стр. 387–393, Нью-Йорк, Нью-Йорк, США, 1967.
  6. ^ Р. Галимберти и У. Монтанари. Алгоритм устранения скрытых линий . Commun. ACM , 12 (4): 206–211, апрель 1969 г.
  7. ^ Гл. Hornung. Подход к алгоритму скрытых линий с минимальным расчетом . Компьютеры и графика , 6 (3): 121–126, 1982.
  8. ^ PP Loutrel. Решение проблемы скрытых линий для нарисованных компьютером многогранников . IEEE Trans. Comput ., 19 (3): 205–213, март 1970.
  9. ^ JF Блинн. Дробная невидимость. IEEE Comput. График. Appl ., 8 (6): 77–84, ноябрь 1988 г.
  10. ^ а б Чт. Оттманн и П. Видмайер. Решение проблем с видимостью с помощью каркасных структур . В Proc. Математические основы компьютерных наук, 1984 , стр. 459–470, Лондон, Великобритания, 1984. Springer-Verlag.
  11. ^ а б Чт. Оттманн, П. Видмайер и Д. Вуд . Наихудший эффективный алгоритм устранения скрытых линий . Междунар. J. Компьютерная математика , 18 (2): 93–119, 1985.
  12. ^ а б О. Нурми. Быстрый алгоритм линейной развертки для устранения скрытых линий . BIT , 25: 466–472, сентябрь 1985 г.
  13. ^ ML Фредман и Б. Вайде. О сложности вычисления меры U [a i , b i ]. Commun. ACM , 21: 540–544, июль 1978 г.
  14. ^ М. Маккенна. Оптимальное удаление скрытых поверхностей в наихудшем случае. ACM Trans. График. , 6: 19–28, январь 1987 г.
  15. ^ Ш. Гали. Обзор практических алгоритмов видимости объектного пространства . SIGGRAPH Tutorial Notes, 1 (2), 2001.
  16. ^ F. Devai. O (журнал  N ) параллельно время алгоритма точного скрытые строк. Достижения в области аппаратного обеспечения компьютерной графики II , стр. 65–73, 1988.
  17. ^ JH Reif и S. Sen. Эффективный чувствительный к выходу алгоритм удаления скрытых поверхностей и его распараллеливание . В Proc. 4-й ежегодный симпозиум. по вычислительной геометрии , SCG '88, стр. 193–200, Нью-Йорк, Нью-Йорк, США, 1988.
  18. ^ а б Ф. Деваи. Оптимальный алгоритм скрытой поверхности и его распараллеливание . In Computational Science and its Applications , ICCSA 2011, volume 6784 of Lecture Notes in Computer Science , pp 17–29. Springer Berlin / Heidelberg, 2011 г.
  19. ^ С. Кук, К. Дворк и Р. Рейщук. Верхняя и нижняя границы времени для параллельных машин с произвольным доступом без одновременной записи . SIAM J. Comput ., 15: 87–97, февраль 1986 г.

Внешние ссылки [ править ]

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