Все рассмотренные выше алгоритмы проводили отсечение по прямоугольному окну, стороны которого параллельны осям координат. Это, конечно, наиболее частый случай отсечения. Однако, во многих случаях требуется отсечение по произвольному многоугольнику, например, в алгоритмах удаления невидимых частей сцены. В этом случае наиболее удобно использование параметрического представления линий, не зависящего от выбора системы координат. Из предыдущего пункта ясно, что для выполнения отсечения в параметрическом представлении необходимо иметь способ определения ориентации удлиненной линии, содержащей отсекаемый отрезок, относительно линии границы - с внешней стороны на внутреннюю или с внутренней на внешнюю, а также иметь способ определения расположения точки, принадлежащей отрезку, относительно окна - вне, на границе, внутри. Для этих целей в алгоритме Кируса-Бека [29], реализующем отсечение произвольным выпуклым многоугольником, используется вектор внутренней нормали к ребру окна. Внутренней нормалью Nв в точке А к стороне окна называется нормаль, направленная в сторону области, задаваемой окном отсечения. Рассмотрим основные идеи алгоритма Кируса-Бека. Так как многоугольник предполагается выпуклым, то может быть только две точки пересечения отрезка с окном. Поэтому надо найти два значения параметра t, соответствующие начальной и конечной точкам видимой части отрезка. Пусть Ni - внутренняя нормаль к i-й граничной линии окна, а P = V1 - V0 - вектор, определяющий ориентацию отсекаемого отрезка, тогда ориентация отрезка относительно i-й стороны окна определяется знаком скалярного произведения Pi    =   Ni ·V, равного произведению длин векторов на косинус наименьшего угла, требуемого для поворота вектора Ni до совпадения по направлению с вектором V: Pi = Ni ·P    =   Ni ·(V1   -  V0). (0.2.16) При Pi < 0 отсекаемый отрезок направлен с внутренней на внешнюю стороны i-й граничной линии окна (см. рис. 0.2.14a). При Pi = 0 точки V0 и V1 либо совпадают, либо отсекаемый отрезок параллелен i-й граничной линии окна (см. рис. 0.2.14б). При Pi > 0 отсекаемый отрезок направлен с внешней на внутреннюю сторону i-й граничной линии окна (см. рис. 0.2.14в). (0.2.17) a)Изнутри наружу б)Параллельно границе в)Снаружи внутрь Рис. 0.2.12: Ориентация отсекаемого отрезка относительно окна Для определения расположения точки относительно окна вспомним параметрическое представление отсекаемого отрезка: V(t)    =   V0   +  (V1   -  V0)·t;       0 ? t ? 1. (0.2.18) Рассмотрим теперь скалярное произведение внутренней нормали Ni к i-й границе на вектор Q(t) = V(t) - Fi, начинающийся в начальной точке ребра окна и заканчивающийся в некоторой точке V(t) удлиненной линии. Qi    =   Ni ·Q    =   Ni ·[V(t)   -  Fi]       для       i    =   1,2,3  ? (0.2.19) Аналогично предыдущему имеем (рис. 0.2.15): При  Qi < 0 точка  V(t)  лежит  с   внешней  стороны  границы При  Qi = 0 точка  яV(t)  лежит  на  самой   границе При  Qi > 0 точка  V(t)  лежит  с   внутренней  стороны  границы (0.2.20) a)Точка V вне б)Точка V на границе в)Точка V внутри Рис. 0.2.13: Расположение точки относительно окна Подставляя в (0.2.19) параметрическое представление (0.2.18), получим условие пересечения отрезка с границей окна: Ni ·[  V0   +  (V1   -  V0)·t   -  Fi   ]    =   0 (0.2.21) Раскрывая скобки, получим: Ni·[  V0   -  Fi  ]   +  Ni·[  V1   -  V0  ] ·t    =   0. (0.2.22) Используя (0.2.16) и (0.2.19) перепишем (0.2.21): (  Ni   ·  P  )  ·  t   +  Ni   ·  Q    =   Pi   ·  t   +  Qi. (0.2.23) Разрешая (0.2.22) относительно t, получим: t    =   - Qi Pi    =   - Ni ·Q Ni ·P   при    яPi ? 0,     i   =   1,2,3,? (0.2.24) Это уравнение и используется для вычисления значений параметров, соответствующих начальной и конечной точкам видимой части отрезка. Как следует из (0.2.17), Pi равно нулю если отрезок либо вырожден в точку, либо параллелен границе. В этом случае следует проанализировать знак Qi и принять или не принять решение об отбрасывании отрезка целиком в соответствии с условиями (0.2.17). Если же Pi не равно 0, то уравнение (0.2.24) используется для вычисления значений параметров t, соответствующих точкам пересечений удлиненной линии с линиями границ. Алгоритм построен следующим образом: Искомые значения параметров t0 и t1 точек пересечения инициализируются значениями 0 и 1, соответствующими началу и концу отсекаемого отрезка. Затем в цикле для каждой i-й стороны окна отсечения вычисляются значения скалярных произведений, входящих в (0.2.23). Если очередное Pi равно 0, то отсекаемый отрезок либо вырожден в точку, либо параллелен i-й стороне окна. При этом достаточно проанализировать знак Qi. Если Qi < 0, то отрезок вне окна и отсечение закончено иначе рассматривается следующая сторона окна. Если же Pi не равно 0, то по (0.2.24) можно вычислить значение параметра t для точки пересечения отсекаемого отрезка с i-й границей. Так как отрезок V0V1 соответствует диапазону 0 ? t ? 1, то все решения, выходящие за данный диапазон следует отбросить. Выбор оставшихся решений определяется знаком Pi. Если Pi < 0, т.е. удлиненная линия направлена с внутренней на внешнюю стороны граничной линии, то ищутся значения параметра для конечной точки видимой части отрезка. В этом случае определяется минимальное значение из всех получаемых решений. Оно даст значение параметра t1 для конечной точки отсеченного отрезка. Если текущее полученное значение t1 окажется меньше, чем t0, то отрезок отбрасывается, так как нарушено условие t0    ?   t1. Если же Pi    >   0, т.е. удлиненная линия направлена с внешней на внутреннюю стороны граничной линии, то ищутся значения параметра для начальной точки видимой части отрезка. В этом случае определяется максимальное значение из всех получаемых решений. Оно даст значение параметра t0 для начальной точки отсеченного отрезка. Если текущее полученное значение t0 окажется больше, чем t1, то отрезок отбрасывается, так как нарушено условие t0    ?   t1. На заключительном этапе алгоритма значения t0 и t1 используются для вычисления координат точек пересечения отрезка с окном. При этом, если t0 = 0, то начальная точка осталась V0 и вычисления не нужны. Аналогично, если t1 = 1, то конечная точка осталась V1 и вычисления также не нужны. Все эти случаи пояснены на блок-схеме, представленной на рис. 0.2.16. Рис. 0.2.14: Блок-схема алгоритма Кируса-Бека Вычисления значений параметров t0 и t1 выполняются в соответствии с выражениями (0.2.25). t0 ? max ({-Qi/Pi | Pi > 0, i = 1,2,?} И{0}}, t1 ? min ({-Qi/Pi | Pi < 0, i = 1,2,?} И1}}. (0.2.25) В Приложении 7 приведена C-подпрограмма V_CBclip, реализующая описанный выше алгоритм. Проверка выпуклости и определение нормалей Как видно из описания, алгоритм Кируса-Бека отсекает только по выпуклому окну. Кроме этого требуются значения внутренних нормалей к сторонам окна. Естественно выполнить эти вычисления в момент задания окна, так как следует ожидать, что одним окном будет отсекаться достаточно много отрезков. Алгоритм с использованием векторных произведений Проверка на выпуклость может производиться анализом знаков векторных произведений смежных ребер (рис. 0.2.17). |[A\vec] ×[B\vec]| = A·B · sin (AB Щ ) Рис. 0.2.15: Проверка выпуклости и определение нормалей Если знак векторного произведения равен 0, то вершина вырождена, т.е. смежные ребра лежат на одной прямой (см. рис. 0.2.17 б), вершина Q). Если все знаки равны 0, то многоугольник отсечения вырождается в отрезок. Если же векторные произведения имеют разные знаки, то многоугольник отсечения невыпуклый (см. рис. 0.2.17 б)). Если все знаки неотрицательные, то многоугольник выпуклый, причем обход вершин выполняется против часовой стрелки (см. рис. 0.2.17 а)), т.е. внутренние нормали ориентированы влево от контура. Следовательно вектор внутреннего перпендикуляра к стороне может быть получен поворотом ребра на +90? (в реализации алгоритма вычисления нормалей на самом деле вычисляется не нормаль к стороне, а перпендикуляр, так как при вычислении значения t по соотношению (0.2.22) длина не важна). Если все знаки неположительные, то многоугольник выпуклый, причем обход вершин выполняется по часовой стрелке, т.е. внутренние нормали ориентированы вправо от контура. Следовательно вектор внутреннего перпендикуляра к стороне может быть получен поворотом ребра на -90?. Описанный алгоритм реализован в процедуре V_SetPclip, приведенной в Приложении 7 и предназначенной для установки многоугольного окна отсечения. Разбиение невыпуклых многоугольников Одновременное проведение операций проверки на выпуклость и разбиение простого невыпуклого многоугольника на выпуклые обеспечивается методом переноса и поворотов окна. Алгоритм метода при обходе вершин многоугольника против часовой стрелки состоит в следующем: Для каждой i-й вершины многоугольник сдвигается для переноса упомянутой вершины в начало координат. Многоугольник поворачивается против часовой стрелки для совмещения (i+1)-й вершины с положительной полуосью X. Вектор внутреннего перпендикуляра к ребру, образованному вершинами i-й и (i+1)-й, вычисляется поворотом ребра на -90? против часовой стрелки. Анализируется знак Y-координаты (i+2)-й вершины. Если Yi+2 ? 0, то в (i+1)-й вершине выпуклость. Если Yi+2 ? 0, то в (i+1)-й вершине невыпуклость. Если имеется невыпуклость, то многоугольник разрезается на два вдоль положительной полуоси X. Для этого вычисляется пересечение положительной полуоси X с первой из сторон. Формируются два новых многоугольника: первый многоугольник - вершины с (i+1)-й до точки пересечения - вершины 2, 3, 4, 6, 7, [7\tilde] на рис. 0.2.18 б); второй многоугольник - все остальные вершины - вершины [7\tilde], 8, 0, 1 на рис. 0.2.18 б) Так как вновь полученные многоугольники могут в свою очередь оказаться невыпуклыми, алгоритм применяется к ним, пока все многоугольники не станут выпуклыми. a) Исходное окно б) Невыпуклость после вершины 2 в) Невыпуклость после вершины 5 Рис. 0.2.16: Проверка выпуклости и разбиение многоугольника Повторное применение алгоритма в многоугольнику, образованному вершинами 2, 3, 4, 6, 7, [7\tilde], показано на рис. 0.2.18 в). Данный алгоритм не обеспечивает минимальность числа вновь полученных выпуклых многоульников и некорректно работает если имеется самопересечение сторон, как это показано на рис. 0.2.19. Рис. 0.2.17: Многоугольник с самопересечением сторон  8  Комментарии к статье  8 8  Обсудить в чате