Трёхмерная версия алгоритма Кируса – Бека работает с выпуклыми отсекателями. Вместе с тем существует потребность отсечения относительно невыпуклых тел. Её можно удовлетворить путём реализации внутренних и внешних отсечений выпуклыми объёмами, из которых состоит невыпуклое тело. Задачу разрезания простого невыпуклого тела на составляющие его выпуклые тела можно решить путём обобщения метода переносов и поворотов, который был рассмотрен ранее. В алгоритме предполагается, что тело представляет собой многогранник с плоскими гранями. Процедура разрезания такова.
Для каждой грани тела:
1) перенести тело так, чтобы одна из вершин выбранной грани совпала с началом координат;
2) повернуть тело вокруг начала координат так, чтобы одно из смежных ему ребёр совпало с одной из осей координат, например, с осью х;
3) повернуть тело вокруг выбранной оси координат так, чтобы выбранная грань совпала с одной из координатных плоскостей, например, с плоскостью z=0;
4) проверить знаки координаты, которая перпендикулярна выбранной грани (т.е. координаты z), для всех вершин тела, не лежащих на этой грани;
5) если все эти знаки совпадают или равны нулю, то тело является выпуклым относительно этой грани. В противном случае оно не выпукло; разрезать тело плоскостью, несущей выбранную грань;
6) повторить всю процедуру с каждым из вновь образовавшихся тел. Продолжать работу до тех пор, пока все тела не станут выпуклыми.
Предыдущие алгоритмы были связаны с отсечением отрезков. Разумеется, многоугольник можно рассматривать как набор отрезков (рис.16).
Если замкнутый многоугольник отсекается, как набор отрезков, то исходная фигура может превратиться в один или более открытых многоугольников или просто стать совокупностью разрозненных отрезков. Однако если многоугольники рассматривается как сплошные области, то необходимо, чтобы замкнутость сохранялась и у результата. Для нашего случая это означает, что отрезки bc, ef, fg, и ha должны быть добавлены к описанию результирующего многоугольника. Добавление отрезков ef и fg представляет особые трудности.
Основная идея алгоритма Сазерленда – Ходжмена состоит в том, что отсечь многоугольник относительно одной прямой или плоскости очень легко. В этом алгоритме исходный и каждый из промежуточных многоугольников отсекается последовательно относительно одной прямой. Порядок отсечения многоугольника разными сторонами окна непринципиален.
Результатом работы алгоритма является список вершин многоугольника, у которого все вершины лежат по видимую сторону от очередной отсекающей плоскости. Поскольку каждая сторона многоугольника отсекается независимо от других, то достаточно рассмотреть только возможные ситуации расположения одного отрезка относительно одной отсекающей плоскости. Будем рассматривать каждую точку P из списка вершин многоугольника, за исключением первой, как конечную точку ребра, начальной точкой S которого является вершина, предшествующая P в этом списке. Тогда возможны только четыре ситуации взаимного расположения ребра и отсекающей плоскости (ОП) (рис.17).
Результатом каждого сопоставления ребра многоугольника с отсекающей плоскостью будет занесение в список вершин результирующего усеченного многоугольника нуля, одной или двух вершин. Если рассматриваемое ребро полностью видимо, то результатом будет вершина P. Заносить в результат начальную вершину S в этом случае не надо, так как если вершины рассматриваются поочередно, то S уже была конечной точкой предыдущего ребра и поэтому уже попала в результат (рис.17,а). Если же ребро полностью невидимо, то результат не изменяется (рис.17,б).
Если ребро многоугольника видимо неполностью, то оно может или входить или выходить из области видимости отсекающей плоскости. Если ребро выходит из области видимости, то надо определить и занести в результат точку пересечения ребра и отсекающей плоскости (рис.17,в). Если же ребро входит в область видимости (рис.17,г), то следует поступить точно так же. Поскольку в последнем случае конечная вершина P ребра видима, то она также должна попасть в результат.
Для первой вершины многоугольника необходимо определить только факт её видимости. Если вершина видима, то она попадает в результат и становится начальной точкой S. Если же вершина невидима, она тоже становится начальной точкой, но в результат не попадает.
Определение видимости точки эквивалентно определению той стороны границы отсекающей плоскости, по которую лежит эта точка. Можно воспользоваться ранее рассмотренным алгоритмом, который сводится к определению знака скалярного произведения вектора нормали на вектор, начинающийся в произвольной точке на прямой или плоскости и заканчивающийся в пробной точке. Ребро многоугольника будет полностью видимым, если оба его конца видимы, и полностью невидимым, если оба они не видны. Если же один конец ребра видим, а другой невидим, то ребро пересекается с отсекающей плоскостью и нужно вычислять точку пересечения. Для этого можно использовать любые изложенные выше алгоритмы отсечения отрезка, например, Кируса – Бека или разбиение средней точкой.
Сазерленд и Ходжмен показали, как можно избежать порождения и запоминания вершин промежуточных многоугольников. Для этого вместо отсечения каждого ребра (вершины) многоугольника одной плоскостью, ограничивающей окно, надо отсекать каждое такое ребро (вершину) последовательно всеми границами окна. После отсечения очередного ребра (вершины) многоугольника по одной из границ окна, алгоритм рекурсивно обращается к самому себе, чтобы отсечь результат предыдущего обращения по следующей границе окна. Это свойство делает данный алгоритм более удобным для аппаратной реализации. Этот алгоритм можно использовать и для отсечения по выпуклому объёму путём вычисления его пересечений с трёхмерными отсекающими плоскостями при помощи алгоритма Кируса – Бека.
5.14. Невыпуклые отсекающие области – алгоритм
Вайлера – Азертона
Для использования рассмотренных алгоритмов отсечения требуются выпуклые отсекающие области. Однако во многих приложениях, например, при удалении невидимых поверхностей, необходимо уметь отсекать и по невыпуклым областям. Этой потребности отвечает более мощный, но и более сложный алгоритм, предложенный Вайлером и Азертоном. Будем называть многоугольник, который отсекается, обрабатываемым многоугольником, а многоугольник, по которому производится отсечение, - отсекающим многоугольником (отсекателем). Новые границы, образуемые в результате отсечения обрабатываемого многоугольника отсекающим, совпадают с участками границ отсекателя. Никаких иных новых границ не возникает. Следовательно, число многоугольников в результате минимально.
Как обрабатываемый, так и отсекающий многоугольники описываются в алгоритме циклическими списками их вершин. Внешняя граница каждого из этих многоугольников обходится по часовой стрелке, а внутренние границы или отверстия – против часовой стрелки. Границы обрабатываемого и отсекающего многоугольников могут пересекаться или не пересекаться между собой. Если они пересекаются, то точки пересечения образуют пары. Одно пересечение из пары возникает, когда ребро обрабатываемого многоугольника входит внутрь отсекающего многоугольника, а другое – когда оно выходит оттуда. Основная идея заключается в том, что алгоритм начинает с точки пересечения входного типа, затем он прослеживает внешнюю границу по часовой стрелке до тех пор, пока не обнаруживает ещё одно её пересечение с отсекающим многоугольником. Этот процесс продолжается до тех пор, пока не встретится начальная вершина.
