Алгоритм Сазерленда-Ходжмана

Этот алгоритм (Sutherland-Hodgman algorithm) предназначен, на самом деле, для отсечения произвольного полигона (даже не обязательно выпуклого, хотя использовать невыпуклые полигоны довольно, на мой взгляд, нерационально) в полуплоскость, или, для 3D случая, в полупространство; другими словами, отсечения полигона прямой или плоскостью. Применяя алгоритм несколько раз, получаем методы отсечения в выпуклый полигон (например, прямоугольник, которым является экран) или выпуклый объем (например, ту часть пространства, которую видно из камеры).

Итак, пусть у нас есть полигон с N вершинами, заданными в каком-то порядке, то есть, по часовой стрелке или против; в каком именно, алгоритму все равно. Занумеруем их от 0 до N-1. Теперь последовательно обходим все ребра полигона: ребро от вершины 0 до вершины 1, от 1 до 2, ..., от N-2 до N-1, от N-1 до 0. Вершины, являющиеся началом и концом ребра, могут лежать в области отсечения, (область отсечения - либо полуплоскость для 2D случая, либо полупространство для 3D случая) могут и не лежать; возможны следующие случаи:

• начало лежит в области отсечения, конец - тоже. Тогда просто добавляем начало к вершинам полигона-результата.

• начало лежит в области отсечения, конец не лежит. В этом случае считаем точку пересечения ребра и границы области отсечения, добавляем в список вершин результата начало ребра и вслед за ним точку пересечения.

• начало не лежит в области отсечения, конец лежит. Тоже считаем точку пересечения, и добавляем только ее.

• н ачало не лежит в области отсечения, конец тоже. Переходим к следующему ребру, никак не изменяя результат.

Рассмотрим простенький пример работы алгоритма в 2D случае, а именно отсечем 2D треугольник прямой. Она делит плоскость на две полуплоскости, две области, нужную и ненужную.

• шаг 1, ребро 0-1: вершина 0 не лежит в нужной области, вершина 1 лежит. Ищем точку пересечения, находим точку A, добавляем ее в список вершин результата. Теперь этот список состоит из одной вершины A.

• шаг 2, ребро 1-2: обе вершины лежат в области, добавляем вершину 1. Результат теперь являет собой список A, 1.

• шаг 3, ребро 2-0: 2 лежит в области, 0 не лежит. Добавляем вершину 2 и точку пересечения B. После последнего шага, таким образом, получили корректный результат отсечения - полигон с вершинами A, 1, 2, B.

В случае, когда надо сделать отсечение в экран, последовательно применяем алгоритм, отсекая полигон прямыми sx=0, sx=XSIZE, sy=0, sy=YSIZE. Из-за такого простого вида уравнений прямых соответственно упрощается код для выяснения принадлежности вершины нужной области и поиска точки пересечния. Вот, например, кусок кода для отсечения полигона прямой sx=0 (оставляющий область sx > 0).

3D-отсечение

В пунктах предыдущих методах делался упор на 2D-отсечение, т.е. отсечение экраном уже спроецированного полигона. Еще один метод - это 3D-отсечение, когда все полигоны отсекаются областью зрения камеры. В этом случае после проецирования полигон заведомо попадает в экран и дальнейшее отсечение уже не требуется. Кстати, z-отсечение при 3D-отсечение делается почти автоматически, очень хорошо вписываясь в общую схему, при использовании же 2D-отсечения придется делать еще и его.

Рассмотрим стандартную камеру. Ее область зрения задается "пирамидой", ограниченной пятью плоскостями со следующими уравнениями:

z = -dist + smallvalue

y = (z + dist) * ySize / (2 * dist)

y = -(z + dist) * ySize / (2 * dist)

x = (z + dist) * xSize / (2 * dist)

x = -(z + dist) * xSize / (2 * dist)

Вот рисунок (вид сбоку), на котором видно первые три из этих плоскостей.

Отсекаем полигон каждой из этих плоскостей по тому же самому алгоритму Сазерленда-Ходжмана, получаем 3D-отсечение.

Теперь выясним, как это самое отсечение сделать относительно универсально (а не только для стандартной камеры), быстро и просто. Зададим наши пять плоскостей не в форме какого-то уравнения, а в форме

plane = [o, n],

где o - какая-то точка, принадлежащая плоскости; n - нормаль, смотрящая в то полупространство, которое мы хотим оставить. Например, для стандартной камеры в этом случае плоскости запишутся так:

n = (0, 0, 1),	o = (0, 0, -dist + smallvalue)
n = (0, -dist, ySize/2),	o = (0, 0, -dist)
n = (0, dist, ySize/2),	o = (0, 0, -dist)
n = (-dist, 0, xSize/2),	o = (0, 0, -dist)
n = ( dist, 0, xSize/2),	o = (0, 0, -dist)

При такой форме задания плоскости критерий принадлежности произвольной точки p нужному нам полупространству выглядит очень просто:

(p - o) * n >= 0.

Не менее просто выглядит и процедура поиска пересечения отрезка от точки p1 до точки p2 с плоскостью. Для любой точки p внутри отрезка имеем

p = p1 + k * (p2 - p1), 0 <= k <= 1,

но так как p лежит в плоскости, p * n = 0; отсюда имеем

(p1 * n) + (k * (p2 - p1) * n) = 0,

k = -((p2 - p1) * n) / (p1 * n) = (p1 * n - p2 * n) / (p1 * n) = 1 - (p2 * n) / (p1 * n).

и моментально находим точку пересечения. Все 3D-отсечение, таким образом, сводится к последовательному применению одной универсальной процедуры отсечения плоскостью. Кроме того, видно, что можно посчитать матрицу перевода стандартной камеры в произвольную, применить ее к выписанным точкам o и нормалям n для плоскостей, задающих "стандартную" область зрения (к нормалям, естественно, надо применить только "поворотную" часть матрицы) и получить, таким образом, уравнения плоскостей уже для *любой* камеры. Тогда 3D-отсечение можно сделать вообще до всяческих преобразований сцены, минимизировав, таким образом, количество поворотов и проецирований вершин - не попавшие в область зрения вершины поворачивать и проецировать, очевидно, не надо. Проецирования невидимых вершин, впрочем, можно избежать и другим образом: сделав поворот сцены, а потом 3D-отсечение "стандартной" областью зрения камеры.

Рассмотрим это более подробно. Пусть у нас есть какая-то камера; пусть есть матрица, которая переводит стандартную камеру в эту камеру. Она как бы состоит из двух частей: матрицы T и матрицы параллельного переноса, совмещающей Ss и s (обозначим ее буквой M). Причем сначала применяется матрица M, потом матрица T. Так вот, для перевода какой-то плоскости-ограничителя области зрения стандартной камеры, заданной в форме plane = [o,n], надо всего лишь сделать пару матричных умножений (поскольку M - матрица переноса, и ее применение на деле сводится к трем сложениям, матричных умножений будет ровно два):

new_o = T * M * std_o

new_n = T * std_n

Что лучше и быстрее, как обычно, не ясно. При отсечении до преобразований тест на попадание точки в область зрения стоит от 3 до 15 умножений (относительно дешевые операции типа сложений не считаем), плюс 11 умножений и 2 деления на поворот и проецирование после отсечения, зато поворачиваются и проецируются только видимые точки. При отсечении после преобразований тест стоит 8 умножений (так как в координатах нормалей шесть нулей и одна единица), зато для всех точек придется сделать 9 умножений для поворота; проецироваться же по-прежнему будут только видимые точки. Так что наиболее подходящий метод выбирайте сами.