Проблема выбора решается с помощью характеристической переменной с/ = Ь-а, где а и Ь - суть расстояния между прямой в точке х = /' + 3/2 и верхним и нижним пикселями-кандидатами (рис. 7.44). Если с/ отрицательно, прямая проходит ближе к центру нижнего пикселя и в качестве следующего пикселя образа отрезка выбирается (/ + 3/2,7 + 1/2); в противном случае выбирается пиксель с центром в (/ + 3/2,7 + 3/2). Можно было бы определить значение а", вычислив у = тх + Ъ, но тогда теряется одно из заявленных достоинств алгоритма - использование только целочисленных операций, поскольку т является действительной дробью.
Рис. 7.43. Алгоритм Брезвнхэма Рис 7.44. Характеристическая переменная алгоритма Брезенхэма Поэтому, во-первых, операции над числами с плавающей точкой заменяются операциями над числами с фиксированной точкой, а во-вторых, все вычисления выполняются в приращениях.
Изменим определение характеристической переменной. Будем использовать
а\ = (х2 -Х\)(Ь-а) = Ах(Ь-а).
Это изменение не влияет на выбор пикселей-кандидатов, поскольку для принятия решения используется только знак характеристической переменной, а он в новой формулировке будет таким же, как и в прежней. Подставляя в выражение с/ значения а и Ь, полученные из уравнения прямой, и принимая во внимание, что х2-х1 Ах И = у2 - тх2, При описании алгоритма предполагается, что центры пикселей имеют координаты, сдвинутые на 1/2 шага относительно целочисленной сетки.
Алгоритмы формирования изображения
приходим к выводу, что а\ принимает только целочисленные значения. Итак, нам удалось избавиться от операций над действительными числами, но непосредственное вычисление а" все же требует большого количества вычислений, хотя и целочисленных.
Поэтому несколько изменим подход. Пусть с1к- значение а\ при х = к+ 1/2. Попробуем вычислить с1к+\ в приращениях относительно с1к. Значение приращения будет зависеть от того, выполнялось ли на предыдущем шаге приращение координаты у пикселя. Возможные варианты представлены на рис. 7.45. Для параметров а и Ь - расстояний между прямой и пикселями-кандидатами - справедливы следующие соотношения"opengl5_343.html">⇐ Предыдущая| |Следующая ⇒