13. Отсечение. Алгоритм Сазерленда Коэна отсечения отрезка. - p1xelse/CG GitHub Wiki

Описание алгоритма

Алгоритм Сазерленда-Коэна предусматривает нахождение точек пересечения отрезка со сторонами окна прямоугольной формы. Однако здесь не производится проверка корректности найденных точек пересечения, как в простом алгоритме.

Найденная точка пересечения разбивает отрезок на две части: полностью невидимую относительно очередной стороны отсекателя и видимую часть. Невидимой будет та часть отрезка, которая заключена от вершины отрезка, невидимой относительно текущей стороны окна, до точки пересечения. Этот факт используется в алгоритме для определения части отрезка, подлежащей отсечению.

В алгоритме предусматривается предварительный анализ сумм кодов концов отрезка и попарных логических произведений этих кодов с целью определения тривиально видимых и тривиально невидимых отрезков.

Если отрезок не является ни тривиально видимым, ни тривиально невидимым, то производится собственно его отсечение. При этом предполагается, что невидимой относительно каждого ребра должна быть первая вершина отрезка. Поэтому в случае необходимости вершины меняются местами. Можно заметить, что одновременно обе вершины не могут быть невидимыми относительно одного ребра отсекателя, так как этот факт позволил бы на предварительном этапе отбросить отрезок как тривиально невидимый.

псевдокод

Если суммы кодов концов отрезка отличны от нуля, какой вывод о расположении отрезка можно сделать?

Если одна из сумм кодов концов отрезка равна нулю, а вторая отлична от нуля, то отрезок частично видимый ((S1 == 0 и S2 <> 0) или (S1 <> 0 и S2 == 0)).

Если обе суммы ненулевые, то отрезок в действительности может оказаться частично видимым или полностью невидимым. Для распознавания части полностью невидимых отрезков можно использовать логическое произведение кодов концов отрезка: P = T1(1) * T2(1) + T1(2) * T2(2) + T1(3) * T2(3) + T1(4) * T2(4)

Если P <> 0, то отрезок невидимый.

Почему в случае if (T1[i] == T2[i]) continue; уходим на следующий шаг?

На очередном шаге выполнения алгоритма мы должны проверить i-ые разряды кодов для первой и второй вершины. Если они равны, то переход на следующий шаг выполнения цикла.

Логика здесь следующая: если одноименные биты коды концов отрезка равны, то мы считаем, что они могут равняться только нулю, т. е. обе вершины располагаются по видимую сторону по видимую сторону от текущей i-ой границы отсекателя, точки пересечения нет, нужно переходить на следующий шаг. Мы считаем, что они не могут одновременно равняться единице. Равенство одноименных разрядов кодов двух концов отрезка единице означает, что обе вершины лежат по невидимую сторону от текущей границы и означает тривиальную невидимость отрезка. До пункта if (T1[i] == T2[i]) continue; все подобные отрезки отбрасываются.

Почему в случае вертикального отрезка не проверяем if (flag != -1) номер шага, т.е. границу отсекателя, с которой ищем пересечение?

Вертикальный отрезок может быть полностью видимым, полностью невидимым, либо частично видимым.

Если он целиком видимый – это сразу обнаружится, уйдем сразу в визуализацию. Если полностью невидимый – уйдем в конец. Продолжится работа с вертикальным отрезком (частично видимым), но он в этом случае расположен по видимую сторону от левой и от правой границы. Значит, при выполнении пункта 3.3 (Если T1[i] =T2[i], то …) выяснится, что в первых двух разрядов обоих кодов для первой и второй вершин хранятся нули. По отношению к этим границам он является видимым и мы просто на первые два шага, где мы ищем пересечения с левой и правой границей не попадем. Мы будем переходить к следующей итерации. То есть, если мы дошли до пункта 3.5 (Если Fl <> -1, то …) и выяснили, что отрезок вертикальный, это будет означать, что мы ищем пересечения с верхней и нижней границей. Т. к. он вертикальный, x-координата изменяться не должна, измениться должна только y-координата.

Как решается вопрос о том, какую часть отрезка надо отбросить после нахождения пересечения?

Надо расставаться с той частью отрезка, которая расположена, начиная с невидимой вершины отрезка до найденной точки пересечения. Предлагается считать всегда невидимой по отношению к текущей границе отсекателя первую вершину. В алгоритме проводится проверка: если первая вершина невидима, значит находим точку пересечения и перемещаем первую вершину на найденную точку пересечения. Если же вторая вершина является невидимой, поменяем местами эти две вершины. Считаем (и не только считаем, а делаем так), что всегда первая вершина располагается по невидимую сторону от текущей границы отсекателя.

Чем данный алгоритм отличается от простого?

В простом алгоритме после нахождения точки пересечения отрезка с границей отсекателя проводится проверка на корректность найденного пересечения. Если пересечение корректно, то считается, что одна точка видимой части отрезка найдена и дальше надо находить вторую точку видимой части отрезка.

В алгоритме Сазерленда-Коэна, каждый раз находя точку пересечения отрезка со стороной отсекателя, мы никаких проверок на корректность не проводим, просто отбрасываем невидимую часть отрезка. Другими словам, мы невидимую вершину, P1, после нахождения точки пересечения, перемещаем в найденную точку пересечения (см. рисунок ниже).