Войти
Каркасное изображение с использованием скрытой линии удаление Твердые объекты обычно моделируются по многогранникам в компьютерном представлении. Грань многогранника - это плоский многоугольник, ограниченный прямыми отрезками, называемыми ребрами. Изогнутые поверхности обычно аппроксимируются полигональной сеткой. Компьютерные программы для рисования линий непрозрачных объектов должны иметь возможность решать, какие кромки или какие части кромок скрыты самим объектом или другими объектами. Эта проблема известна как удаление скрытых линий .
Первое известное решение проблемы скрытых линий было разработано Робертсом в 1963 году. Однако оно сильно ограничивает модель: оно требует, чтобы все объекты были выпуклыми. Рут А. Вайс из Bell Labs задокументировала решение этой проблемы в 1964 году в статье 1965 года. В 1966 г. Иван Э. Сазерленд перечислил 10 нерешенных проблем компьютерной графики. Проблема номер семь - «удаление скрытой линии». Что касается вычислительной сложности, эта проблема была решена Devai в 1986 году.
Модели, например, в автоматизированном проектировании, могут иметь тысячи или миллионы ребер. Следовательно, решающее значение имеет подход вычислительной сложности, выражающий потребности в ресурсах, таких как время и память, в зависимости от размера проблемы. Требования ко времени особенно важны в интерактивных системах.
Размеры проблем для удаления скрытых линий - это общее количество n ребер модели и общее количество v видимых сегментов ребер. Видимость может измениться в точках пересечения изображений краев. Обозначим через k общее количество точек пересечения образов ребер. Оба k = Θ (n) и v = Θ (n) в худшем случае, но обычно v < k.
Алгоритмы скрытых линий, опубликованные до 1984 года, делят ребра на линейные сегменты по точкам пересечения их изображений, а затем проверяют каждый сегмент на видимость по отношению к каждой грани модели. Предполагая модель набора многогранников с границей каждого топологически эквивалентной сфере и с гранями, топологически эквивалентными кругам, согласно формуле Эйлера существует Θ (n) граней. Проверка Θ (n) линейных сегментов против Θ (n) граней в худшем случае занимает Θ (n) раз. Алгоритм Аппеля также нестабилен, поскольку ошибка видимости будет распространяться на конечные точки последующих сегментов.
Оттманн и Видмайер и Оттманн, Видмайер и Вуд предложили O ((n + k) log n) -время алгоритмов скрытой линии. Затем Нурми увеличил время работы до O ((n + k) log n). Эти алгоритмы занимают Θ (n log n), соответственно Θ (n log n) времени в худшем случае, но если k меньше квадратичного, на практике они могут быть быстрее.
Любой алгоритм скрытых линий должен определять объединение Θ (n) скрытых интервалов на n ребрах в худшем случае. Поскольку Ω (n log n) является нижней границей для определения объединения n интервалов, кажется, что лучшее, на что можно надеяться, - это время наихудшего случая Θ (n log n), и, следовательно, алгоритм Нурми является оптимальным.
Однако коэффициент log n был исключен Деваи, который поднял открытую проблему, существует ли такая же оптимальная верхняя граница O (n) для удаления скрытых поверхностей. Эту проблему решил Маккенна в 1987 году.
Чувствительные к пересечению алгоритмы в основном известны в литературе по вычислительной геометрии. Квадратичные верхние границы также ценятся в литературе по компьютерной графике: Гали отмечает, что алгоритмы Деваи и Маккенны «представляют собой вехи в алгоритмах видимости», преодолевая теоретический барьер от O (n log n) до O (n) для обработки сцена из n граней.
Другая открытая проблема, поднятая Деваи, относительно того, существует ли алгоритм скрытой линии за время O (n log n + v), где v, как отмечалось выше, является количеством видимых сегментов, является все еще не решен на момент написания.
В 1988 году Devai предложил параллельный алгоритм за O (log n), использующий n процессоров для решения проблемы скрытой строки в рамках одновременного чтения, исключительной записи (CREW) модель вычислений с параллельной машиной с произвольным доступом (PRAM). Поскольку произведение номера процессора и времени работы асимптотически больше, чем Θ (n), последовательная сложность задачи, алгоритм не является оптимальным для работы, но он демонстрирует, что проблема скрытой линии находится в класс сложности NC, т.е. ее можно решить за полилогарифмическое время, используя полиномиальное количество процессоров.
Для удаления скрытых линий можно использовать алгоритмы скрытых поверхностей, но не наоборот. Рейф и Сен предложили алгоритм за время O (log n) для проблемы скрытых поверхностей, используя O ((n + v) / log n) процессоров CREW PRAM для ограниченной модели многогранных ландшафтов, где v - выходной размер.
В 2011 году Devai опубликовал алгоритм скрытых линий с временным интервалом O (log n) и более простой алгоритм скрытых линий с временным интервалом O (log n). Алгоритм скрытой поверхности, использующий n / log n процессоров CREW PRAM, оптимален для работы.
Алгоритм скрытой строки использует n процессоров PRAM с исключительным чтением и исключительной записью (EREW). Модель EREW - наиболее близкий к реальным машинам вариант PRAM. Алгоритм скрытой линии работает O (n log n), что является верхней границей для лучших последовательных алгоритмов, используемых на практике.
Кук, Дворк и Рейщук дали нижнюю границу Ω (log n) для нахождения максимума из n целых чисел, позволяющего бесконечно много процессоров любой PRAM без одновременной записи. Нахождение максимума из n целых чисел в постоянном времени сводится к проблеме скрытой линии с помощью n процессоров. Следовательно, алгоритм скрытых линий является оптимальным по времени.
