Алгоритм Сазерленда-Ходжмана
Этот алгоритм (Sutherland-Hodgman algorithm) предназначен, на самом деле, для отсечения произвольного полигона (даже не обязательно выпуклого, хотя использовать невыпуклые полигоны довольно, на мой взгляд, нерационально) в полуплоскость, или, для 3D случая, в полупространство; другими словами, отсечения полигона прямой или плоскостью. Применяя алгоритм несколько раз, получаем методы отсечения в выпуклый полигон (например, прямоугольник, которым является экран) или выпуклый объем (например, ту часть пространства, которую видно из камеры). Итак, пусть у нас есть полигон с N вершинами, заданными в каком-то порядке, то есть, по часовой стрелке или против; в каком именно, алгоритму все равно. Занумеруем их от 0 до N-1. Теперь последовательно обходим все ребра полигона: ребро от вершины 0 до вершины 1, от 1 до 2,..., от N-2 до N-1, от N-1 до 0. Вершины, являющиеся началом и концом ребра, могут лежать в области отсечения, (область отсечения - либо полуплоскость для 2D случая, либо полупространство для 3D случая) могут и не лежать; возможны следующие случаи: - начало лежит в области отсечения, конец - тоже. Тогда просто добавляем начало к вершинам полигона-результата. - начало лежит в области отсечения, конец не лежит. В этом случае считаем точку пересечения ребра и границы области отсечения, добавляем в список вершин результата начало ребра и вслед за ним точку пересечения. - начало не лежит в области отсечения, конец лежит. Тоже считаем точку пересечения, и добавляем только ее. - начало не лежит в области отсечения, конец тоже. Переходим к следующему ребру, никак не изменяя результат.
Рассмотрим простенький пример работы алгоритма в 2D случае, а именно отсечем 2D треугольник прямой. Она делит плоскость на две полуплоскости, две области, нужную и ненужную. | отсекаемая | нужная область | 1 область | /..\ | /.....\ A........\ / |.........\ / |..........\ 0-----B-----------2 | | - шаг 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). // dst - массив для сохранения вершин результата // src - массив вершин исходного полигона // n - число вершин исходного полигона // функция возвращает число вершин результата int clipLeft(vertex *dst, vertex *src, int n) { int i, r; vertex p1, p2; float k; r = 0; for (i = 0; i < n; i++) { p1 = src[i]; p2 = src[(i + 1) % n]; if (p1.sx >= 0) { // если начало лежит в области if (p2.sx >= 0) { // если конец лежит в области dst[r++] = p1; // добавляем начало } else { // если конец не лежит в области dst[r++] = p1; // добавляем начало k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения dst[r].sx = 0; dst[r].sy = p1.sy + k * (p2.sy - p1.sy); dst[r].u = p1.u + k * (p2.u - p1.u); dst[r].v = p1.v + k * (p2.v - p1.v); r++; } } else { // если начало не лежит в области if (p2.sx >= 0) { // если конец лежит в области k = -p1.sx / (p2.sx - p1.sx); // добавляем точку пересечения dst[r].sx = 0; dst[r].sy = p1.sy + k * (p2.sy - p1.sy); dst[r].u = p1.u + k * (p2.u - p1.u); dst[r].v = p1.v + k * (p2.v - p1.v); r++; } } } return r; } Видно, что можно чуточку перемешать код обработки разных случаев, изменить порядок действий алгоритма и тем самым подсократить исходник, да и сделать алгоритм проще и понятнее: // dst - массив для сохранения вершин результата // src - массив вершин исходного полигона // n - число вершин исходного полигона // функция возвращает число вершин результата int clipLeft(vertex *dst, vertex *src, int n) { int i, r; vertex p1, p2; float k; r = 0; for (i = 0; i < n; i++) { p1 = src[i]; p2 = src[(i + 1) % n]; if (p1.sx >= 0) { // если начало лежит в области dst[r++] = p1; // добавляем начало } if (((p1.sx > 0) && (p2.sx < 0)) || // если ребро пересекает границу ((p2.sx >= 0) && (p1.sx < 0))) // добавляем точку пересечения { k = -p1.sx / (p2.sx - p1.sx); dst[r].sx = 0; dst[r].sy = p1.sy + k * (p2.sy - p1.sy); dst[r].u = p1.u + k * (p2.u - p1.u); dst[r].v = p1.v + k * (p2.v - p1.v); r++; } } return r; } Написав аналогичные куски кода для остальных трех сторон экрана, получим функцию отсечения в экран по алгоритму Сазерленда-Ходжмана.
|
