3.2 Ускорение алгоритма Брезенхэма

1. Частные случаи – горизонтальные, вертикальные и диагональные линии.

2. При разложении отрезка можно заметить, что при движении вдоль основной оси (X) по 1 , получаются группы , имеющие постоянную координату по неосновной оси (Y).

В стандартном алгоритме Брезенхэма проверка производится на каждом шаге, используя же группы , количество проверок можно .

Пусть есть отрезок длиной 35 по X и 10 по Y.

Рис. 3.3

. Тогда группы с неизменной Y – координатой будут иметь то 3 то 4 .

Поэтому достаточно 1 раз вычислить m, чтобы определить группы . Количество вычислений на 70%.

Минимальная длина группы:

Максимальная длина группы:

Как же располагать группы с максимальной и минимальной длиной? На каждый шаг по неосновной оси мы ставим вдоль основной. После этого решается ставить ли еще 1 или y на 1. Для этого анализируется накопленная ошибка отклонения.

Рис. 3.4

2-ой момент – балансирование групп . Это делается так: вначале оценивается ошибка накопления не за полный шаг на 1 , а за . Если 1-ая и последняя группы состоят из нечетного числа , получатся несимметричные начала и конец.

3.3. Растровая развертка литер

Ранее мы уже рассмотрели общий метод изображения литер, основанный на матрице точек. Тот же метод используется и при построении растровых изображений. Наименьшей сеткой, с помощью которой можно описывать литеры с приемлемым качеством, является сетка 5 7; для представления прописных и строчных литер нужна матрица 7 9 (клетка 8 10).

Дисплей разбивают на клетки размером 8 8 (8 10). Дополнительные используются для разделения литер и для строчных литер с выносными элементами. Маски литер хранятся в ПЗУ.

При изображении литер надо учитывать 2 особенности:

1. пропорциональное размещение литер (это изменение интервалов между центрами литер с учетом их ширины (Пример — и ).

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

2. нижние выносные элементы букв (части литер, опущенные ниже базовой линии (g,p,q,y) изображаются путем сдвига матриц вниз по отношению к другим литерам.)

Рис. 3.5

Каждая литера представляет собой код матрицы из 0 и 1.

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

Рис. 3.6

При изображении литер, так же как и при изображении отрезка возникает необходимость сглаживания. Используется принцип выравнивания – надо менять яркость пропорционально площади , покрытой изображением. Если взять 4 уровня яркости (от 0 до 3), то литера М будет выглядеть как показано на рис.

3.4. Растровая развертка окружностей Четырехсторонняя симметрия

Рис. 3.7

Существует несколько простых, но не эффективных способов развертки окружности. Рассмотрим окружность с центром в начале координат:

.

Чтобы изобразить окружности, можно x с 0 до R и на каждом шаге вычислить y. Остальные четверти получаются симметричным отображением. Этот метод неэффективен, т.к. в него входят операции “ ” и “ ”. Более того, при значениях x близких к R в окружности появляются незаполненные промежутки. Можно было бы воспользоваться расчетом координат окружности, заданной в полярных координатах – , путем пошагового изменения от 0⁰ до 90⁰. Но недостатки остаются все те же.