22. Отсечение отрезков в трехмерном пространстве. Трехмерный алгоритм Кируса Бека.

Отсечение отрезков в трехмерном пространстве.

См. тут.

Трехмерный алгоритм Кируса-Бека

Так же как и в двухмерном случае, отсекатель может быть произвольным выпуклым объемом.

Основные отличия от двумерного случая:

• Вектор состоит из 3х компонент: x, y, z
• Видимость определяем относительно граней

Видимость точки

• Так же проводят нормаль (но уже от грани), и берут произвольную точку любой грани отсекателя, от которой будем проводить вектор к точке.
• Подсчёт скалярного произведения двух этих векторов.
• Анализ знака этого произведения: > 0 - точка видима, = 0 - на грани, < 0 - невидима.
• Для отчесения отрезка, так же как и в двухмерном случае, анализируют вектор направления (директрису): P2 - P1.
• Определение точки пересечения через t = -Wск / Dск
• Wск - произведение двух векторов из п. 1, Dск - произведение дирректрисы на вектор нормали

Про произведения и вектора

• Dск = 0 - отрезок паралелен рассматриваемой грани, это из свойств скалярного произведения
• D = 0 - отрезок точка (очевидно)
• Wск >= 0, отрезок видимый относительно грани
• Wск < 0, отрезок невидимый относительно грани и поэтому невидимый относительно всего отсекателя

Выбор t для нахождения точек пересечения

t для видимого отрезка (то есть выбор нужных параметров для отрисовки), выбирается так же как в двумерном случае, с помощью анализа знака Dск и разбиения на группы >= и < 0, и выбором в них.

• Dск > 0 - точка расположена ближе к началу
• Dск < 0 - ближе к концу

При Dск >= 0 берем максимум, и это будет началом отрезка (tн). При Dcк < 0 берем минимум, и это будет концом отрезка (tк).

Стоит отметить, что не хранятся все t для каждой грани. t выбираются в момент вычисления, по типу tн = max(tн, tтек) и тд

И не забыть проверку tн <= tв.

Псевдокод тут

Про пирамиды и эффективность (лучше это не читать)

Просто для ознакомления

В случае усеченной пирамиды (пирамиды видимости), внутренние нормали к граням отсекатля определяют формально (ЧТО?), так как их значения неочевидны.

Оценка числа операций растет линейно с ростом числа сторон или граней у отсекателя.

Следующий вопрос: 23. Определение факта выпуклости трехмерных тел. Разбиение тела на выпуклые многогранники.

Предыдущий вопрос: 21. Трехмерное отсечение. Виды отсекателей. Вычисление кодов концов отрезка для каждого типа отсекателей. Алгоритм отсечения отрезков средней точкой.