Вычисление нормалей и определение выпуклости многоугольников

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

Si = | Ai+2 Ai Ai+1 |, позволяющих определить взаимное положение вершины Ai+2 относительно ребра Ai Ai+1. Если Si < 0, то вершина лежит справа от ребра при обходе многоугольника по часовой стрелке. Знак этого определителя относится к вершине Ai+1.

Вычислив определители для всех ребер многоугольника по их знакам, определяют выпуклость данного многоугольника: если знаки имеют значение “минус”, то многоугольник является выпуклым. При невыполнении этого условия многоугольник является невыпуклым, а число положительных знаков определяет число вершин, нарушающих выпуклость многоугольника. При обходе многоугольника против часовой стрелки знаки определителей и условия выпуклости принимают противоположный смысл. Если ставится задача разбиения невыпуклого многоугольника на выпуклые части, то это можно сделать продлением одного из смежных ребер вершины, нарушающей выпуклость многоугольника, до пересечения с его ребром. Каждая такая операция уменьшает число вершин, нарушающих выпуклость многоугольника, по крайней мере, на одну. Для полного разбиения многоугольника требуется число операций не превосходящее числа вершин, нарушающих его выпуклость.

Трехмерные однородные координаты и преобразования точки в пространстве

Преобразования точки в пространстве выполняются, также как и на плоскости, в однородных координатах. В этом случае точка P представляется четырехмерным вектором (X Y Z W), где W – произвольный множитель, не равный нулю. Связь декартовых и однородных координат выражается следующими соотношениями:

Из этого определения следует, что две точки (X1,Y1,Z1) и P2 (X2,Y2,Z2) представляют собой одну и ту же точку, если P1 = c P2 для любого c  0. Использование однородных координат позволяют вычислять преобразования композиции элементарных преобразований путем умножения на результирующую матрицу, полученную перемножением матриц соответствующей последовательности преобразований. Матрицы трехмерных однородных координат имеют порядок 4х 4.

Перенос. Координаты точки после переноса можно вычислить в векторной форме P * = P * T.

Масштабирование. Аналогично вычисляется координаты преобразованной точки при масштабировании P * = P * S.

Поворот. В отличие от плоскости поворот в пространстве возможен вокруг каждой из трех осей – X, Y, Z. Можно рассмотреть, кроме этого, повороты в левосторонней и правосторонней системах координат.

Стрелками показано направление положительного вращения вокруг соответствующих осей. Для определения направления положительного вращения удобно использовать простую табличку следующего вида.

 

Для правосторонней системы координат положительное направление – это вращение против часовой стрелки при взгляде с конца положительной полуоси вращения, а для левосторонней – по часовой стрелке. В компьютерной графике обычно используют обе системы координат. Расположение их осей выбирают таким образом, чтобы направление оси Z совпадало с направлением взгляда наблюдателя.