Л. р. 2:
1. Содержательная и формальная постановка задачи.
Разработать программу, позволяющую изображать прямую, ее проекции и линии связи на пространственном и комплексном чертежах, с помощью алгоритма Брезенхема.
Формальную постановку задачи можно определить как экранное отображение:
пространственного чертежа прямой, содержащего изображения прямой АВ, трех ее проекций А1В1, А2В2 и А3В3 и линий связи;
комплексного чертежа прямой с изображением трех ее проекций А1В1, А2В2 и А3В3 и линий связи;
ползунковых элементов управления для редактирования координат точек А и В прямой.
Причем при изменении положения ползунков, задающих координаты точки прямой, должно происходить соответствующее изменение пространственного и комплексного чертежей .
2. Структура решения.
- Отображение прямой АВ на комплексном и пространственном чертежах.
- Отображение точек А и В
- Пересчет мировых координат точек А и В, в координаты устройства и вычисление по ним координат проекций А1В1, А2В2, А3В3 на пространственном и комплексном чертежах.
- Перерисовка изображения пространственного и комплексного чертежей прямой.
- Прорисовка точек на пространственном и комплексном чертежах.
- Прорисовка линии с помощью алгоритма Брезенхэма на пространственном и комплексном чертежах.
*Исходные графические объекты могут находиться только в первом октанте.
3. Обзор и анализ методов решения.
Прорисовка точек и пересчёт координат осуществляется с помощью методов используемых в первой лабораторной работе.
Все линии прочерчиваются с помощью алгоритма Брезенхема.
4. Описание реализации применяемых методов.
- Отображение прямой АВ на комплексном и пространственном чертежах.
- Отображение точек А и В
Эту подзадачу будем решать, используя следующий метод перевода мировых координат в координаты устройства пространственного чертежа. Пусть прямая АВ задана двумя точками с координатами А(Aх,Aу,Az) и В (Bx,By,Bz) в трехмерном пространстве.
- Перерисовка изображения пространственного и комплексного чертежей прямой АВ.
При реализации этой подзадачи будем использовать набор методов вывода графических примитивов на экран. Данными методами будут: прорисовка линии, эллипс и части эллипса.
- Прорисовка линии с помощью алгоритма Брезенхэма на пространственном и комплексном чертежах.
Поскольку в большинстве случаев, для визуализации различных объектов и поверхностей используются линейные апроксимации, т. к. кривые в чистом виде почти не чертятся, то скорость и надежность прочерчивания прямых является достаточно весомым фактором.
Будем считать, что у нас есть функция point (х,у), используемая для высвечивания пиксела на растровом устройстве. Основная задача, в связи с этим, заключается в определении тех точек сетки (x,y), лежащих на экране, которые должны быть высвечены. Поскольку таких точек может быть достаточно большое количество, то предпочтительнее использовать только целочисленную арифметику, которая выполняется быстрее и надежнее, чем операции с плавающей точкой.
Рассмотрим отрезок, заданный тт. Т1(Х1, Y1) и Т2 (Х2, Y2). Причём при условии, что Х2>Y2, Y2≥Y1, Y2-Y1≤X2-X1.
Для рассмотрения перехода от действий с плавающей точкой к целочисленной арифметике рассмотрим несколько алгоритмов:
1)real – алгоритм (без целочисленной арифметики).
2)real – integer алгоритм (промежуточный алгоритм). Если рассмотреть изменение у, то ожно увидеть, что он или остается тем же, или увеличивается на 1. А поскольку выбор должен осуществляться таким образом, чтобы новая точка сетки (х, у) располагалась по возможности ближе к линии, проходящей через начальные и конечные точки, то это означает, что расстояние по вертикали между точкой и прямой (t1, t2) не должно превышать d=0,5.
Если расстояние по вертикали между точками А, В больше чем по горизонтали, то независимой координатой становится Y, теперь при увеличении Y координата X остаётся постоянной или изменяется на 1.
Известно, что для прямой линии
Yi+1=Yi+(y2-y1)/(x2-x1)∆X, где k=(y2-y1)/(x2-x1).
3) integer – алгоритм (алгоритм Брезенхема, 1965 г.). Поскольку d вычисляется как конечная сумма элементов, каждый из которых равен либо k, либо -1, то d является рациональной дробью и подобно k, может быть записью в виде частного со знаменателем (x2-x1). То есть можно перейти к целочисленным переменным, умножив k и d на (x2-x1) и 2.
Для избавления от не целого 0,5, умножим знаменатель на 2. Получим
k = 2k(x2-x1), D= 2d(x2-x1). Пусть V= 2(x2-x1), d>0,5;
2d(x2-x1)>0,5*2(x2-x1), т.е. D>dx, где dx= (X2-X1).
Т.к. с нулём сравнение производится быстрее, то
D-dx>0, D-dx=E, а т.к. d=0, то и D=0 . Получаем, что E = -dx.
dx= (X2-X1)
dy= (Y2-Y1); x=dx*2, k=dy*2 вместо увеличения величина D на K, будем использовать увеличение E на К, а вместо уменьшения D на V – уменьшение E на V.
Таким образом реализовать этот метод можно следующим образом:
V=(X2-X1)*2;
K=(Y2-Y1)*2;
E=X1-X2;
Y=Y1;
For (x=X1; X<=X2; x++)
{ point(x,y); //point(x,y) – высвечивает точку (x,y)
E+=K;
If (E>0) {y++, E-=V}
}
Обобщенный алгоритм Брезенхэма
Пусть произвольный отрезок MN задан координатами своих концов M(X1,Y1) и N(X2,Y2). Рассмотрим величину |X2-X1| - |Y2-Y1|. Ели эта величина больше 0 то это означает, что угол наклона отрезка к оси Ox меньше 45°. В этом случае ведущей будем выбирать координату x. В противном случае угол наклона MN к оси Ox больше 45° и за ведущую координату мы возьмем y. При таком выборе координаты x и y меняются местами во всех выражениях, где они участвуют.
Так как ведущую координату удобнее наращивать, а не уменьшать в процессе прорисовки отрезка, то поменяем точки M и N местами (если это необходимо) чтобы ведущая координата в направлении от M к N возрастала. Затем проверим, в каком направлении меняется не ведущая координата (убывает или возрастает от точки M к N). Если не ведущая координата убывает в направлении от M к N, то её значение в ходе алгоритма будем не увеличивать, а уменьшать на 1, а также умножим в этом случае величину K на –1.
В данной лабораторной работе алгоритм Брезенхема используется в следующей функции:
void CLine::LineBr(TImage* pDC,int X1,int Y1,int X2,int Y2)
{ // алгоритм Брезенхема рисования линии
int vertical;
int x,y,dx,dy,xinc,yinc,hlp,v,k,e;
pDC->Canvas->MoveTo(X1,Y1);
vertical=0;
dx=abs(X2-X1);
dy=abs(Y2-Y1);
xinc=1;
yinc=1;
if (X2<X1)
{
xinc=-1;
}
if (Y2<Y1)
{
yinc=-1;
}
if (dy>dx)
{
vertical=1;
hlp=dx;
dx=dy;
dy=hlp;
}
v=2*dx;
k=2*dy;
e=-dx;
x=X1;
y=Y1;
while(dx>0)
{
dx-=1;
pDC->Canvas->LineTo(x,y);
e+=k;
if (e>0)
{
if (vertical==1)
{
x+=xinc;
}
else
{
y+=yinc;
}
e-=v;
}
if (vertical==1)
{
y+=yinc;
}
else
{
x+=xinc;
}
}
}
Л. р. 3: