Компьютерная графика

4. РАСТРОВЫЕ АЛГОРИТМЫ 103 вом представлении, например, отрезка, то следует ясно понимать, о каком именно представлении идет речь. При этом нужно иметь в виду, что растровое пред-ставление объекта не является единственным и возможны различные способы по-строения. Растровое представление отрезка. Алгоритм Брезенхейма Рассмотрим задачу построения растрового изображения отрезка, соединяющего точки ()xy11,и ()xy22,. Для простоты будем считать, что 02121≤−≤−yyxx. Тогда отрезок описывается следующим уравнением: ()[]yyyyxxxxxxx=+−−−∈12121112,, или ykxb=+ . Простейший алгоритм растрового представления отрезка имеет вид: // File Line1.cpp void Line ( int x1, int y1, int x2, int y2, int color ) { double k = ((double)(y2-y1))/(x2-x1); double b = y1 – k*x1; for ( int x = x1; x <= x2; x++ ) putpixel ( x, round ( k*x + b ), color ); } Используя рекуррентное соотношение для вычисления y, можно упростить функ-цию, однако это не устраняет основного недостатка алгоритма – использования веще-ственных вычислений для работы на целочисленной решетке. В 1965 году Брезенхеймом был предложен простой целочисленный алгоритм для растрового построения отрезка, первоначально предназначенный для использования в графопостроителях. При построении растрового изображения отрезка всегда выбирается ближайший по вертикали пиксел. При этом из двух точек А и В (рис. 2) выбирается та, которая ближе к исходной прямой (в данном случае выбирается точка А, так как a < b). Для этого вводится чис-ло d, равное ()()xxba21−−. Рис. 2