23. Определение факта выпуклости трехмерных тел. Разбиение тела на выпуклые многогранники. - p1xelse/CG GitHub Wiki

Определение факта выпуклости

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

Разбиение тела на выпуклые многогранники

1. Перенести тело так, чтобы одна из вершин совпала с центром координат
2. Повернуть вокруг точки начала координат, чтобы одно из рёбер, выходящее из рассматриваемой вершины совпало с одной из координатных осей
3. Поворот вокруг выбранной оси координат такой, чтобы рассматриваемая грань совпала с координатной плоскостью
4. Для всех вершин, не лежащих в рассматриваемой плоскости, определить знаки координаты, которая перпендикулярна рассматриваемой плоскости. Если знаки для всех вершин одинаковы(или равны 0), то тело выпуклое относительно рассматриваемой грани. Если тело выпукло относительно одной из своих граней, то оно и в целом выпуклое. Если знаки в целом не совпадают, то тело не выпукло. Если все знаки равны 0, то тело вырожденное. Если тело невыпуклое, то плоскостью, проходящей через рассматриваемую грань, мы разрезаем тело на составляющие части. Рассматриваемую процедуру применяем к каждой из полученных частей.
5. Вектор внутренней нормали к рассматриваемой грани(для выпуклого тела) будет иметь 2 нулевые компоненты(те, которые лежат в плоскости этой грани), а третья будет совпадать с осью, перпендикулярной рассматриваемой грани(и != 0). Знак этой компоненты совпадает со знаком любой вершины, не лежащей в данной плоскости. Получим вектор внутренней нормали в повернутой системе координат. Для вычисления его в исх. системе координат надо выполнить обратные преобразования. Реальное положение полученных разбиением многогранников восстанавливаются применением обратных преобразований.