УДАЛЕНИЕ НЕВИДИМЫХ ЛИНИЙ И ПОВЕРХНОСТЕЙ

Литеры

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

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

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

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

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

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

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

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