Алгоритмы удаления невидимых линий

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

Алгоритм плавающего горизонта

Он используется для моделей, заданных явно – уравнением. Для удаления невидимых линий этим методом исходная поверхность рассекается набором секущих плоскостей с фиксированным шагом. Эти плоскости могут быть параллельны любой выбранной – это неважно. Для того, чтобы получить уравнение кривой, являющейся пересечением исходной фигуры и данной плоскости, достаточно подставить константу, определяющую данную плоскость, в исходное уравнение. Далее выбирается некоторое количество различимых по Х (для случая плоскостей, параллельных Z=0) точек и заводится массив соответствующего размера. Говорят, что в этом массиве будет храниться горизонт. Сечения рассматриваются в порядке удаления от наблюдателя. Изначально горизонт заполняется значениями первого сечения. Для каждого сечения рассматривается каждая различимая по Х точка, для нее по формуле соответствующего сечения рассчитывается координата У, это значение сравнивается со значением для такого же Х, хранящимся в горизонте. Если новое значение У меньше, чем хранимое в горизонте, то оно игнорируется (она не видна), иначе эта точка видна и новое значение У заносится в горизонт. Для корректного отображения нижней части поверхности необходимо завести второй горизонт, который будет не «всплывать», а «тонуть». По размерности он такой же всплывающий, изначально также инициализируется первым сечением.

Алгоритм Ньюэла-Ньюэла-Санча

Относится к алгоритмам, использующим приоритеты. Приоритеты по глубине сцены. Также называется алгоритмом художника.

Алгоритм подразумевает

1. предварительную сортировку по глубине, например, на основе Zmin;

2. разрешение всех противоречий и построение точечного списка;

3. преобразование многоугольников в растровую форму и вывод их в порядке уменьшения расстояния от наблюдателя.

Наибоее сложный - второй этап в силу некорректности сортировки и наличия циклических и взаимно-перекрывающих поверхностей. Наличие экранирования определяется с помощью серии тестов:

для тестов выбирается пара многоугольников, через P обозначается самый удаленный по результатам предварительной сортировки, через Q – самый приближенный. Если ближайшая вершина P будет дальше от точки наблюдения, чем самая удаленная вершина Q, то P перекрываться никак не может. Если это не так, то P потенциально экранирует не только Q, но и любой другой многоугольник из списка, для которого будут те же условия. Для того, чтобы такого не произошло, используют серию тестов, представленных в виде вопросов.

1. верно ли, что прямоугольные объемлющие оболочки P и Q не перекрываются по Х?

2. по Y?

3. Верно ли, что P целиком лежит по ту сторону плоскости, несущей Q, которая расположена дальше от точки наблюдения?

4. верно ли, что Q целиком лежит по ту сторону плоскости, несущей P, которая расположена ближе к точке наблюдения?

5. Верно ли, что проекции P и Q не перекрываются?

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

Z-буфер

Отличительные особенности: простота и эффективность. Очень сложно или невозможно реализовать некоторые спецэффекты вроде отражений и теней. Алгоритм работает в пространстве изображения, т.е. с пикселями. Для его работы помимо буфера цвета необходим такой же по размеру массив (буфер), хранящий информацию о глубине или, проще говоря, координату Z, каждой точки модели. Изначально один буфер заполняется цветом фона, второй – минимальной координатой Z. Многоугольник растеризуется и для каждой точки многоугольника определяется глубина. Эта глубина сравнивается со значением, хранимым в Z-буфере, для точки с такими же координатами (X,Y). Если расчетная глубина меньше, чем хранимая в буфере, то точка игнорируется, в противном случае расчетное значение заносится в соответствующую ячейку, а вместе с ним меняется и буфер цвета соответствующей ячейки.