Формализация функций отсечения.

Одна из самых первых операций – отсечение видимого объёма. Функцию отсечения также требуется формализовать, так как необходимо выполнить большое количество сравнений.

0 Точка. Если речь идёт о точке, то необходимо проверить три условия:

1) Xmin £ X £ Xmax

2) Ymin £ Y £ Ymax

3) Zmin £ Z £ Zmax

Это уже шесть сравнений. Если не выполнится хотя бы одно из условий, то точка отбрасывается. Но сложнее всё для отрезка.

0 Отрезок.

а) Лучший случай, когда отрезок внутри.

Аксиома: если оба конца отрезка лежат внутри видимого объёма, то отрезок сохраняется целиком.

б) Если А – внутри, В – вне, то необходимо искать точку пересечения с границей и усекать.

в) Обе вне.

Во втором случае ищем две точки пересечения и усекаем.

Для поиска точек пересечения следует решать систему трёх уравнений с тремя неизвестными (в параметрическом виде, где t меняется от 0 до 1). Но найти просто точки пересечения недостаточно. Надо решать проблему внутри – вне. С точки зрения геометрии для случая б) берётся по любой произвольной точке на двух концах, то есть для одного куска подставляем её параметры видимого объёма, определяем принадлежит или нет. Для второго куска отрезка выполнять подстановку в уравнение не обязательно, так как одна уже принадлежит.

В случае в) необходимо выполнить как минимум две проверки. С такой же подстановкой в уравнение прямой в пространстве. То есть мы получаем:

1) Огромное число вычислительных операций.

2) Кроме того может так оказаться, что отрезок параллелен плоскости, в итоге, ничего не получится.

Разработан ряд алгоритмов упрощения выполнения функций отсечения.

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

1ый бит равен 1, если точка выше окна

2ой бит равен 1, если точка ниже окна

3ий бит равен 1, если точка справа от окна

4ый бит равен 1, если точка слева от окна

Для трёхмерного изображения:

5ый бит равен 1, если точка сзади видимого объёма

6ой бит равен 1, если точка спереди видимого объёма

Отрезок точно расположен внутри (целиком), если оба кода нулевые. Его можно точно отбросить, если оба конца либо выше окна, либо ниже окна (2ой бит равен 1), либо слева от окна, либо справа от окна. Такая логическая функция минимизирована и получена: если сложение кодов отрезков не равно 0, то отрезок отбрасывается целиком, а если равна 1, то нельзя однозначно сказать, надо ли искать точки пересечения. Большинство языков позволяет работать с отдельными битами слов и надо сделать 4 сравнения и одно логическое сложение. Таким образом, мы получаем большую экономию вычислительных операций. Алгоритм Коэна-Сазерленда как и другие эффективен в двух случаях:

1) Большинство отрезков изображения лежат внутри видимого объёма.

2) Либо когда большинство отрезков изображения лежат вне видимого объёма.

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

Метод поиска – уравнение прямой в параметрической форме с учётом того, что видовые плоскости имеют 0, 1.

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

Первые четыре – это боковые грани, а последние два – две другие.

Всего известно примерно 20 алгоритмов для реализации функции отсечения. Этот алгоритм наиболее доступный.