5.14. Невыпуклые отсекающие области – алгоритм

Вайлера – Азертона

Для использования рассмотренных алгоритмов отсечения требуются выпуклые отсекающие области. Однако во многих приложениях, например, при удалении невидимых поверхностей, необходимо уметь отсекать и по невыпуклым областям. Этой потребности отвечает более мощный, но и более сложный алгоритм, предложенный Вайлером и Азертоном. Будем называть многоугольник, который отсекается, обрабатываемым многоугольником, а многоугольник, по которому производится отсечение,  отсекающим многоугольником (отсекателем). Новые границы, образуемые в результате отсечения обрабатываемого многоугольника отсекающим, совпадают с участками границ отсекателя. Никаких иных новых границ не возникает. Следовательно, число многоугольников в результате минимально.

Как обрабатываемый, так и отсекающий многоугольники описываются в алгоритме циклическими списками их вершин. Внешняя граница каждого из этих многоугольников обходится по часовой стрелке, а внутренние границы или отверстия – против часовой стрелки. Границы обрабатываемого и отсекающего многоугольников могут пересекаться или не пересекаться между собой. Если они пересекаются, то точки пересечения образуют пары. Одно пересечение из пары возникает, когда ребро обрабатываемого многоугольника входит внутрь отсекающего многоугольника, а другое – когда оно выходит оттуда. Основная идея заключается в том, что алгоритм начинает с точки пересечения входного типа, затем он прослеживает внешнюю границу по часовой стрелке до тех пор, пока не обнаруживает ещё одно её пересечение с отсекающим многоугольником. Этот процесс продолжается до тех пор, пока не встретится начальная вершина.

5.15. Литеры

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

Программно сгенерированные литеры в форме точечной матрицы можно обрабатывать точно так же. Однако необходимо проверять, будет ли каждый пиксель из маски символа находиться внутри или вне отсеченной части оболочки. Если внутри, то пиксель активизируется, если снаружи то нет.

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

6. Удаление невидимых линий и поверхностей

Задача удаления невидимых линий и поверхностей является наиболее сложной задачей в машинной графике. Алгоритмы удаления невидимых линий и поверхностей служат для определения линий ребер, поверхностей или объемов, которые видны или невидны для наблюдателя, находящегося в заданной точке пространства.

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

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

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

Объем вычислений каждого алгоритма, работающего в объектном пространстве и сравнивающего каждый объект со всеми остальными объектами, растет теоретически как квадрат числа объектов. Аналогично, объем вычислений любого алгоритма, работающего в пространстве изображения и сравнивающего каждый объект с позициями всех пикселов в системе координат экрана, растет теоретически как n_*N, где n – количество объектов, а N – число пикселов.