Слайд 2
Координатные представления
Для создания изображения с помощью программного пакета
необходимо задать геометрическое описание объекта, который следует изобразить. Это
описание определяет положение и форму объекта. Например, прямоугольник задается через положение его углов(граней), а сфера – через положение центра и радиус. В программных пакетах общего назначения необходимо, чтобы геометрическое описание задавались в стандартной правосторонней системе координат. Если значения координат рисунка задаются в какой-либо другой системе координат (сферической, гиперболической и т.д.), то, прежде чем вводить их значения в программный пакет, их необходимо преобразовать в декартовы координаты.
В общем случае в процесса создания и изображения сцены используется несколько различных декартовых координатных систем. Во-первых, можно задавать формы отдельных объектов в отдельной системе координат для каждого объекта.
Слайд 3
Координатные представления
Такие системы координат называют координатами моделирования, локальными
или главными координатами. Задав формы отдельных объектов, можно составить
сцену путем расстановки объектов по соответствующим местам в системе координат сцены, которая называется внешней системой координат. Этот этап подразумевает преобразование отдельных систем координат моделирования в координаты с заданным положением и ориентацией относительно внешней системы координат. Для описания не слишком сложных сцен часть объектов можно добавлять непосредственно в общую структуру сцены во внешних координатах. Геометрическое описание в системе координат моделирования и во внешней системе координат могут задаваться в любой удобной форме, как целые числа или как числа с плавающей точкой, без учета ограничений для отдельных устройств ввода.
Слайд 4
Координатные представления
После того, как заданы все элементы сцены,
чтобы создать изображение, общее описание во внешних координатах обрабатывают
различными программами в одной или нескольких системах координат устройств ввода. Этот процесс называется конвейером наблюдения (viewing pipeline). Вначале внешнею координаты преобразуются в координаты наблюдения, соответствующие тому изображению сцены, которое мы хотим увидеть. В основе этой системы координат лежит положение и ориентация гипотетической камеры. После этого координаты объекта преобразуются в двумерную проекцию сцены, которая соответствует тому, что мы увидим на устройстве вывода. Затем эта сцена записывается в нормированных координатах, где значение каждой координаты попадает в диапазон от – до 1 или от 0 до 1, в зависимости от системы. Нормированные координаты еще называют нормированными координатами прибора, т.к. такое описание делает графический пакет независимым от диапазона координат специального устройства вывода.
Слайд 5
Координатные представления
Еще необходимо определить видимые поверхности и обрезать
части рисунка, выходящие за пределы поля зрения. Наконец, стандарты
развертки рисунка преобразовываются и попадают в буфер регенерации растровой системы, чтобы превратится в изображение.. Систему координат устройства изображения обычно называют координатами устройства или экранными координатами. Часто и нормированные координаты и координаты экрана описываются в левосторонней системе координат, так что увеличение положительного расстояния от плоскости OXY (экрана или плоскости изображения) можно интерпретировать как удаление от точки наблюдения.
Слайд 6
Системы координат
Для того, чтобы, к примету, прорисовать прямолинейный
отрезок, необходимо задать положение его двух концов, а для
прорисовки многоугольника необходимо задать набор координат его вершин. Значения координат этих точек хранятся в описании сцены вместе с остальной информацией об этих объектов, таких как цвет и координатных границы, т.е. минимальные и максимальные значения координат x, y, z для каждого объекта. Набор координатных границ называют также ограничивающим прямоугольником данного объекта. Затем объекты изображаются – информация о сцене передаются стандартным процедурам визуализации, которые определяют видимые поверхности и, в конечном итоге, ставят в соответствие объектам значения координат на экране. Для записи информации о сцене, такой как коды цвета, в определенные места буфера кадров используется процесс преобразования в стандарт развертки, и на устройстве вывода изображаются сцены.
Слайд 7
Экранные координаты
Местоположение на экране выражается через целочисленные экранные
координаты, которые соответствуют положениям пикселей в буфере кадра. Значения
координат пикселей дают номер строки развертки (значение координаты у) и номер столбца (значение координаты х). При аппаратном выполнении таких процессов, как обновление экрана, как правило, положение пикселей отсчитывается от левого верхнего угла экрана. Тогда строкам развертки присваиваются значения от 0 (верхняя строка экрана) до какого-то целочисленного значения ymax (нижняя строка экрана), а положение пикселей в каждой строке развертки нумеруются от 0 до хmax в направлении слева направо. В то же время с помощью программных команд можно задать любую систему отсчета положений на экране. Например, можно задать диапазон точек с целочисленными координатами и началом координат в нижнем левом углу экрана или воспользоваться для описания рисунка нецелочисленными декартовыми координатами. Затем значения координат, используемых для описания геометрии сцены, с помощью стандартных процедур визуализации преобразуются в целые значения положений пикселей в буфере кадра.
Слайд 8
Экранные координаты
В алгоритмах для строк развертки графические примитивы
задаются через координаты представления, т.е. определяются положения пикселей, которые
следует изображать. Например, если заданы координаты конечных точек линейного отрезка, алгоритм построения изображения должен вычислить положения тех пикселей, которые лежат на прямой, соединяющей точки. Так как пиксель занимает конечную площадь экрана, это должно учитываться при выполнении алгоритмов. В настоящее время центр области, занимаемой пикселем, принято сопоставлять с каждым целочисленным значением координаты на экране.
Определив положение пикселей для данного объекта, в буфер кадра необходимо записать соответствующие коды цвета. Чтобы сделать это, предположим, дана низкоуровневая процедура вида
setPixel (x ,y, color); setPixel (x ,y);
Эта функция задает цвет пикселя в изображении с координатами (x , y) относительно произвольно выбранного на экране начала отсчета.
Слайд 9
Абсолютные и относительные координаты
Рассмотренные выше системы координат формулировались
через значения абсолютных координат. Т.е. задается действительное положение точек
в используемой системе координат.
Но в некоторых графических пакетах положения точек можно также задавать с помощью относительных координат. Такой способ удобен для построения чертежей с помощью перьевых графопостроителей, создания художественных изображений, а также для издательских целей и печатной работы. Воспользовавшись этим способом, можно задавать координаты точки относительно последнего положения, к которому обращалась система (к текущему положению). Например, если точка с координатами (3,8) - последнее положение, к которому обращалась программа, то относительные координаты (2,-1) соответствуют абсолютным координатам (5,7). В таком случае, перед тем, как задать какие-либо координат для функции примитива, используется дополнительная функция, устанавливающая текущее положение.
Слайд 10
Абсолютные и относительные координаты
Тогда, чтобы описать такой объект,
как набор соединенных между собой прямолинейных отрезков, нужно задать
только последовательность относительных координат (смещений) после того, как будет установлено исходное положение. Графические системы могут предлагать опции, для задания положения точки с помощью относительных/ абсолютных координат. Далее будем считать, что все координаты задаются в абсолютных системах отсчета.
В нашей первой программе мы использовали команду
void gluOrtho2D(GLdouble left, GLdouble right, GLdouble bottom, GLdouble top)
Которая представляет функцию, используемую для задания любой двумерной декартовой системы координат. Аргументы этой функции – значения, определяющие границы изменения координат х и у для того рисунка, который требуется изобразить. Т.к. gluOrtho2D описывает ортогональную проекция, необходимо убедится в том, что значения координат помещены в проекционную матрицу OpenGL. Кроме того, перед определением диапазона внешних координат в качестве проекционной матрицы можно использовать единичную матрицу. Это гарантирует, что значения координат не будет прибавляться к значениям,
Слайд 11
Абсолютные и относительные координаты
которые, возможно, были ранее внесены
в проекционную матрицу. Таким образом, систему координат для использованных
ранее примеров можно задать с помощью операторов:
glMatrixMode (GL_PROJECTION); // определяем вид матрицы
glLoadIdentity (); // устанавливаем текующую матрицу единичной
gluOrtho2D ( xmin , xmax , ymin , ymax ); // устанавливаем размеры плоскости
При этом левый нижний угол на экране будет описываться координатами ( xmin , уmin), а правый верхний угол – координатами (xmax , ymax ).
После этого можно задать один или несколько графических примитивов, при изображении которых используется система координат, описанная в gluOrtho2D . Если размеры этих примитивов будут вписываться в координатные пределы окна на экране, то будут изображены все примитивы. В противном случае будут видны только те части примитивов, которые попадают в диапазон координат окна. Кроме того, при задании геометрического описания рисунка все координаты примитивов OpenGL должны выражаться в абсолютной системе координат относительно системы отсчета.
Слайд 12
Функции точек в opengl
Чтобы описать геометрия точки, ее
положение задается во внешней системе координат. Затем эти значения
вместе с другими геометрическими параметрами, которые могут описывать данную сцену, обрабатываются стандартными процедурами визуализации. Пока не заданы другие значения атрибутов, примитивы OpenGL будут изображаться с размерами и цветом, определенными по умолчанию. Изначально цвет примитивов – белый, а размер точки равен размеру одного пикселя на экране.
Чтобы задать координаты единственной точки, используется следующая функция OpenGL:
glVertex*();
* означает, что для данной функции необходимо указать индексные коды, обозначающие размерность пространства, тип числовых данных, которые используются в качестве значения координат, и возможность представления координат в виде вектора. Функция glVertex должна находится в программе между функциями glBegin и glEnd. Аргумент glBegin определяет тип графического примитива, который следует изобразить, а функция glEnd не требует аргументов.
Слайд 13
Функции точек в opengl
При выводе на экран точки
аргументов функции glBegin является символьная константа GL_POINTS. Таким образом,
положение точки в OpenGL описывается так:
glBegin ( GL_POINTS );
glVertex* ();
glEnd ();
Хотя термином Vertex(вершина) в строгом смысле называют «угловую» точку многоугольник, точку пересечения сторон угла, точку пересечения эллипса с его главной осью или другие подобные точки геометрических фигур, функция glVertex описывает положение любой точки. Таким образом, для задания точек, прямых линий и многоугольников применяется одна функция, а для описания объектов, составляющих сцену, чаще всего используются прямоугольные участки.
Координаты точек в OpenGL могут задаваться в двух, трех или четырех измерениях. Для определения размерности используемого пространства необходимо указать индекс 2, 3 или 4 в функции glVertex. Четырехмерное описание указывает на представление с помощью однородных координат, где однородный параметр h (четвертая координата) – масштабный коэффициент для декартовый координат.
Слайд 14
Функции точек в opengl
Далее необходимо обозначить, какой тип
данных используется для описания числовых значений координат. Это осуществляется
с помощью второго индекса функции glVertex: i (integer), s (short), f (float), d( double).Значения координат в функции glVertex могут перечисляться в явном виде, или может использоваться единственный аргумент, который задает положения координат в виде массива. Если применяется описание координат в виде массива, то необходимо также добавить третий индекс v (vector).
Допустим, необходимо вывести на экран три точки на одинаковом расстоянии друг от друга на двумерном прямолинейном отрезке с тангенсом угла наклона 2:
glBegin ( GL_POINTS );
glVertex2i ( 50 , 100 );
glVertex2i ( 75 , 150 );
glVertex2i ( 100 , 200 );
glEnd ();
Или можно сделать все то же самое, но определить координаты в виде массивов и использовать их вместо параметра функции прорисовки:
Слайд 15
Функции точек в opengl
int point1[] = 50,100;
int point2[]
= 75,150;
int point3[] = 100,200;
…..
glBegin ( GL_POINTS );
glVetrex2iv (
point1 );
glVetrex2iv ( point2 );
glVetrex2iv ( point1 );
glEnd ();
А вот пример задания двух точек в трехмерном пространстве:
glBegin ( GL_POINTS );
glVetrex3f ( -78.05 , 909.72 , 14.60 );
glVetrex3f ( 261.91, -5200.67, 188.33);
glEnd ();
Кроме того, для описания координат точек можно определить класс или структуру:
Слайд 16
Функции точек в opengl
struct points
{
Glfloat x, y;
}
…
points pointPos;
pointPos.x
= 120.75;
pointPos.y = 45.30;
glBegin ( GL_POINTS );
glVetrex2f (pointPos.x ,
pointPos.y );
glEnd ();
Слайд 17
Функции прямых в opengl
В графических пакетах, как правило,
предлагаются функции для описания одного или нескольких прямолинейных участков,
причём каждый из этих участков определяется координатами двух его концов. В пакете OpenGL координаты одного конца выбирают с помощью glVertex, точно также, как это делалось для координат точки, а в среду glBegin\glEnd заключается список функций glVetrex. Однако теперь в качестве параметра glBegin используется символьная константа, которая указывает, что данный перечень координат нужно понимать, как координаты концов отрезков. Существует три символьные константы OpenGL, которые можно использовать для определения того, как следует соединять точки данного перечня, чтобы получился набор прямолинейных отрезков. По умолчанию каждая символьная переменная дает изображение сплошных линий белого цвета.
Набор прямолинейных отрезков, соединяющих каждую пару начало-конец из перечня, задается с помощью константы GL_LINES.
Слайд 18
Функции прямых в opengl
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0, 0, 1.0);
int p1[] =
{ 9,3 };
int p2[] = { 2,1 };
int p3[]
= { 4,6 };
int p4[] = { 7,1 };
int p5[] = { 0,3 };
glBegin(GL_LINES);
glVertex2iv(p1);
glVertex2iv(p2);
glVertex2iv(p3);
glVertex2iv(p4);
glVertex2iv(p5);
glEnd();
glFlush();
Слайд 19
Функции прямых в opengl
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0, 0, 1.0);
int p1[] =
{ 9,3 };
int p2[] = { 2,1 };
int p3[]
= { 4,6 };
int p4[] = { 7,1 };
int p5[] = { 0,3 };
glBegin(GL_LINE_STRIP);
glVertex2iv(p1);
glVertex2iv(p2);
glVertex2iv(p3);
glVertex2iv(p4);
glVertex2iv(p5);
glEnd();
glFlush();
Слайд 20
Функции прямых в opengl
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(0, 0, 1.0);
int p1[] =
{ 9,3 };
int p2[] = { 2,1 };
int p3[]
= { 4,6 };
int p4[] = { 7,1 };
int p5[] = { 0,3 };
glBegin(GL_LINE_LOOP);
glVertex2iv(p1);
glVertex2iv(p2);
glVertex2iv(p3);
glVertex2iv(p4);
glVertex2iv(p5);
glEnd();
glFlush();
Слайд 21
Алгоритмы построения прямых в opengl
Прямолинейный отрезок на сцене
определяется координатами его концов. Чтобы изобразить прямую на растровом
мониторе, графическая система сперва должна спроектировать положения концов отрезка, переводя их в целочисленные значения экранных координат, и определить ближайшие положения пикселей, лежащих вдоль линии, соединяющей эти концы. Затем в буфер кадра загружается цвет линии с соответствующими координатами пикселей. Считывая информацию из буфера кадра, видеоконтроллер изображает пиксели на экране. В ходе этого процесса происходит цифровая обработка прямой линии и преобразование ее а целочисленные значения координат, которые в общем случае только приблизительно передают настоящую форму линии. Рассчитанные координаты прямой (10.48 ; 20.51) дают координаты пикселя (10; 21). Такое округление значений координат до целых чисел приводит к тому, что все линии, кроме горизонтальных и вертикальных, изображаются в виде «зубцов».
Слайд 22
Алгоритмы построения прямых в opengl
Характерная «зубчатость» особенно заметна
в системах с невысоким разрешением. Их внешний вид можно
несколько улучшить с помощью систем с высокой разрешающей способностью. Более эффективные методы сглаживания растровых линий основываются на подборе интенсивности пикселей, находящихся на этой линии.
Слайд 23
Алгоритмы построения прямых в opengl. Уравнение прямой
Положение пикселей
вдоль прямой линии определяется исходя из геометрических свойств прямой
линии. Декартово уравнение прямой линии имеет вид
y = a * x + b (1)
где a – тангенс угла наклона прямой, b – точка ее пересечения с осью ординат. Если известно, что два конца отрезка заданы как точки с координатами (x0 , y0) и (xend , yend), то можно найти значения тангенса угла наклона a и точки b пересечения с осью y по следующим формулам:
(2)
(3)
Алгоритмы изображения прямых линий основаны на уравнении прямой и на последних двух формулах.
Слайд 24
Алгоритмы построения прямых в opengl. Уравнение прямой
Для любого
заданного интервала координат x(∂x) вдоль линии из уравнения (2)
можно найти соответствующий интервал координат y(∂y):
∂y = a * x(∂x) (4)
Аналогично можно найти интервал оси x(∂x), соответствующий заданному ∂у:
(5)
Эти уравнения составляют основу для определения отклоняющих напряжений в таких аналоговых дисплеях, как системы векторного сканирования, где возможны относительно небольшие изменения величины отклоняющего напряжения. Для прямых с тангенсом угла | a| < 1 ∂x может устанавливаться пропорциональным небольшому горизонтальному отклоняющему напряжению, и тогда соответствующее вертикальное отклонение задается пропорционально ∂у, что можно рассчитать по формуле (4). Для прямых, тангенс угла которых больше 1, ∂у можно выбирать пропорционально небольшому вертикальному отклоняющему напряжению, при этом соответствующее горизонтальное отклонение
Слайд 25
Алгоритмы построения прямых в opengl. Уравнение прямой
Задается пропорционально
∂х, которое рассчитывается по формуле (5). Для прямых с
тангенсом наклона угла, равным 1 и ∂у= ∂х, и напряжения горизонтального и вертикального отклонения равны между собой. В каждом из этих случаев между заданными точками изображается гладкая прямая с тангенсом угла наклона a.
В растровых системах прямые линии строятся по пикселям, и размер шага в горизонтальном и вертикальном направлении ограничивается разрешением пикселей. Это значит, что нужно «провести выборку» точек прямой линии с дискретными значениями и определить пиксели, самые близкие к данным прямой для каждого элемента выборки. Этот процесс отражен на рисунке, где элементы выборки с дискретными координатами расположены вдоль оси х.
Слайд 26
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
Цифровой дифференциальный
анализатор (ЦДА) - алгоритм преобразования стандартов развертки прямой линии,
основанный на вычислении либо ∂x, либо ∂у по уравнениям (4) или (5). Прямая разбивается на единичные отрезки по одной из координат, а для другой координаты определяются соответствующие целые значения, ближайшие к данной прямой.
Рассмотрим прямую линию с положительным тангенсом угла наклона.
Слайд 27
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
Если тангенс
угла наклона меньше или равен 1, прямая разбивается на
единичные отрезки по координате х (∂x = 1), и последовательно вычисляются значения у:
(6)
Индекс k пробегает целые числа от 0 (первая точка) и увеличивается на 1 доя тех пор, пока не будет достигнута последняя точка. Поскольку a может быть любым действительным числом от 0 до 1, каждое рассчитанное значение следует округлять до ближайшего целого числа, соответствующего положению пикселя на экране в обрабатываемом столбцу х.
Для прямых с положительным тангенсом угла наклона, превышающим 1, координаты х и у необходимо поменять местами. Прямая разбивается на единичные отрезки по у (∂у = 1) и последовательно вычисляются значения
(7)
Слайд 28
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
В основе
уравнений (6) и (7) лежит предположение, что линии обрабатываются
в направлении от левого до правого конца. Если обработку выполнять в обратном направлении, то есть слева направо, то либо ∂x = -1 и
(8)
Либо ∂у = -1 и
(9)
Аналогичные вычисления выполняются с помощью формул (6) – (9), что позволяет определить положения пикселей на прямой с отрицательным тангенсом угла наклона. Таким образом, если абсолютное значение тангенса угла наклона меньше 1, а начальная точка находится слева, то полагаем ∂x = 1 и вычисляем значения у с помощью (6), Если начальная точка находится справа, тангенс угла наклона положительный и меньше 1, то полагаем ∂х = -1 и находим положения у с помощь. (8). Для отрицательного тангенса угла наклона с абсолютным значением больше 1 мы используем ∂у = -1 и (9), или ∂у = 1 и (7).
Слайд 29
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
Этот алгоритм
сведен к следующей процедуре, входом которой служат 2 целочисленных
значения экранных координат концов отрезка. Параметрам dx и dy присваиваем значения горизонтальной и вертикальной разностей между точками-концами отрезков. Большую из разностей обозначаем step. Начиная с координат (х0, у0) определяем смещение, необходимое на каждом шаге для того, чтобы найти следующее положение этой прямой. Этот процесс выполняется step раз. Если dx больше, чем dy, а х0 меньше, чем xend, то значения приростов по направлениям х и у будут равны 1 и а соответственно. Если же разность по координате х больше, но при этом х0 больше, чем xend, то для создания следующей точки на прямой используются декременты -1 и –а. В любом случае, в направлении у используется единичный прирост, а в направлении х – прирост 1/а.
#include
#include
Слайд 30
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
void init(void)
{
glClearColor(0,
0, 0, 0.0);
glMatrixMode(GL_PROJECTION);
gluOrtho2D(0.0, 20.0, 0.0, 15.0);
}
void setPixel(int x, int
y)
{
glBegin(GL_POINTS);
glVertex2i(x, y);
glEnd();
glFlush();
}
Слайд 31
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
inline int
round_k(const float a)
{
return int(a + 0.5);
}
void lineCDA(int x0, int
y0, int xend, int yend)
{
int dx = xend - x0, dy = yend - y0, step, k;
float xInc, yInc, x = x0, y = y0;
step = (abs(dx) > abs(dy)) ? abs(dx) : abs(dy);
xInc = float(dx) / float(step);
yInc = float(dy) / float(step);
Слайд 32
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
setPixel(round_k(x), round_k(y));
for
(k = 0; k < step; k++)
{
x += xInc;
y
+= yInc;
setPixel(round_k(x), round_k(y));
}
}
void myDisplay(void)
{
glClear(GL_COLOR_BUFFER_BIT);
glColor3f(1, 1, 1);
lineCDA(0, 0, 20, 40);
}
Слайд 33
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
void main(int
argc, char** argv)
{
glutInit(&argc, argv);
glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
glutInitWindowPosition(0, 100);
glutInitWindowSize(400, 300);
glutCreateWindow("Пример ");
init();
glutDisplayFunc(myDisplay);
glutMainLoop();
}
Слайд 34
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
Слайд 35
Алгоритмы построения прямых в opengl. Алгоритм ЦДА
Алгоритм ЦДА
– более быстрый способ вычисления положений пикселей, чем тот,
при котором непосредственно используется уравнения прямой. В нем операция умножения, фигурирующая в уравнении прямой, исключена за счет использования растровых характеристик, так что при перемещении по прямой и переходе от одного пикселя к другому прибавляются нужные приросты по направления х и у. Тем не менее, если отрезки достаточно длинные, то из-за накопления ошибок округления при последовательном прибавлении прироста возможно смещение положения пикселя относительно фиксированного направления прямой. Более того, операции округления и арифметика м плавающей точкой требует больших временных затрат. Выполнение ЦДА алгоритма можно ускорить, разделив приросты а и 1/а на целую и дробную части, чтобы все вычисления сводились к операциям с целыми числами.
Слайд 36
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Алгоритм Брезенхема
– точный и эффективный растровый алгоритм создания прямых линий,
в котором вычисляются только целочисленные значения приростов. Кроме того, алгоритм можно адаптировать для изображения окружностей и других кривых.
Рассмотрим процесс преобразования стандартов развёртки для прямой с положительным тангенсом угла наклона, меньше 1. В этом случае положение пикселей на прямой определяется разбиением на единичные отрезки по координате х. Начиная с левого конца (х0, у0) данной прямой, при переходе к соседнему столбцу наносится пиксель, который по своему номеру строки развертки у является самым близким к направлению прямой.
Слайд 37
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Предположим, что
мы определили , что следует наносить пиксель с координатами
(xk,yk). Далее необходимо решить, какой пиксель изображать в столбце x(k+1) = xk + 1. Выбор необходимо сделать из пикселей с координатами (xk + 1, yk) (xk + 1, yk + 1).
В точке выборки с координатами xk + 1
обозначим расстояния по вертикали от пик-
селей до математической прямой как
d_lower и d_upper. Координата у математи-
ческой прямой в столбце пикселей xk + 1 на-
ходятся как
у = а * (xk + 1) + b (10)
Тогда
d_lower = y – yk = a * (xk + 1) + b – yk (11)
d_upper = (yk +1) – y = yk +1 - a * (xk + 1) - b
(12)
Чтобы определить, какой из этих пикселей ближе к заданной прямой, можно провести эффективную проверку, основанную на разности двух расстояний до пикселей:
Слайд 38
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
d_lower -
d_upper = 2 * а * (xk + 1)
– 2 * уk + 2 * b – 1 (13)
Параметр pk - параметр принятия решения для k-ого шага алгоритма построения прямой линии находится путем такого преобразования уравнения (13), чтобы в него входили только целочисленные расчеты. Это можно сделать, проведя подмену a=∂y/ ∂x, где ∂ -вертикальные и горизонтальные расстояния между концами отрезка, и вычислить параметр принятия решения как:
pk = ∂x * ( d_lower – d_upper) = 2 * ∂y * xk – 2 * ∂x * yk +c (14)
Знак параметра pk будет таким же, как и знак d_lower – d_upper. Параметр с – постоянная со значением 2 * ∂y + ∂х * (2 * b -1), которая не зависит от координаты пикселя и находится в ходе рекурсивных вычислений, необходимых для расчета pk . Если пиксель с координатой yk окажется ближе к реальному направлению прямой, чем пиксель с координатой yk+1( т.е. d_lower < d_upper), то параметр принятия решений окажется отрицательным и на график наносится нижний пиксель. Если pk оказывается положительным, то на график наносится верхний пиксель.
Слайд 39
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Изменение значения
координаты вдоль направления прямой происходит при единичном шаге как
в направлении х, так и у направлении у. Следовательно, с помощью схемы целочисленного прироста можно найти значения последующих параметров принятия решения. На шаге k+1 параметр находится из уравнения (14) как
pk+1 = 2 * ∂y * (xk+1) – 2 * ∂x * (yk + 1) + c
Вычитая (14) из предыдущего уравнения, получим
pk+1 – pk = 2 * ∂y * ( xk+1 – xk ) – 2 * ∂x * ( yk+1 – yk )
или
pk+1 = pk + 2 * ∂y – 2 * ∂x * ( yk+1 – yk ) (15)
где yk+1 – yk равен или 0 или 1, в зависимости от знака параметра pk.
Такой рекурсивный расчет параметров принятия решения выполняется в каждой точке с целым значением координаты х, начиная с координаты левого конца отрезка. Первый параметр p0 находится из уравнения (14) в начальной точке с координатами ( х0, у0 ), при этом а находится как ∂y/ ∂х:
p0 = 2 * ∂y - ∂х 16)
Итого, при выполнении преобразования стандартов развертки постоянные 2 * ∂y и 2 * ∂y - 2 * ∂х рассчитывается один раз для прямой.
Слайд 40
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Алгоритм Брезенхема
Вводим
два конца отрезка, помечая левый конец отрезка как (х0,
у0).
Задаем в буфере кадра цвет пикселя (х0, у0).
Вычисляем постоянные ∂х, ∂y, 2 * ∂y и 2 * ∂y – 2 * ∂х и находим начальное значение параметра принятия решения р0 = 2 * ∂y - ∂х.
Для каждого xk вдоль прямой, начиная с k = 1, проводим проверки: если pk < 0, то следующую точку следует изобразить на месте пикселя (xk+1, yk) и pk+1 = pk + 2 * ∂y. Если pk > 0, то следующую точку следует изобразить на месте пикселя (xk+1, yk+1) и pk+1 = pk + 2 * ∂y – 2 * ∂x .
Выполняем этап ∂x – 1 раз.
Слайд 41
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
void linesBrasenhem(int
x0, int y0, int xend, int yend)
{
int dx =
abs(xend - x0), dy = abs(yend - y0);
int p = 2 * dy - dx;
int x, y;
if (x0 > xend)
{
x = xend;
y = yend;
xend = x0;
}
else
{
x = x0;
y = y0;
}
Слайд 42
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
setPixel(x, y);
}
while
(x < xend)
{
x++;
if (p < 0)
p += 2 *
dy;
else
{
y++;
p += 2 * (dy-dx);
}
setPixel(x, y);
}
Слайд 43
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Слайд 44
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Слайд 45
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Алгоритм Брезенхема
можно обобщить для прямых линий с произвольным тангенсом угла
наклона, рассмотрев симметрию различных октантов и квадрантов плоскости ху. Для прямой с положительным тангенсом угла наклона, превышающим 1, роли х и у меняются местами. Это означает, что в направлении координаты у делаются единичные шаги, и при этом последовательно вычисляются координаты х, ближайшие к направлению прямой. Кроме того, программу можно изменить таким образом, чтобы построение прямой начиналось с другого конца. Если у качестве исходной точки прямой с положительным тангенсом угла наклона берется правый конец отрезка, то х и у уменьшаются при каждом шаге слева направо. Чтобы гарантировать, что независимо от начальной точки будут изображаться одни и те же пиксели, когда вертикальные расстояния от пикселей до прямой равны ( d_lower = d_upper), всегда выбирается верхний (или нижний) пиксель.
При отрицательном тангенсе угла наклона алгорит аналогичный, только на этот раз одна координата увеличивается, а вторая, наоборот, уменьшается.
Слайд 46
Алгоритмы построения прямых в opengl. Алгоритм Брезенхема
Наконец, можно
отдельно рассматривать некоторые частные случаи: горизонтальные ( ∂y =
0), вертикальные ( ∂ч = 0), и диагональные прямые (|∂y| = |∂x| ) можно непосредственно заносить в буфер кадров без обработки с помощью алгоритма построения простых линий.
Слайд 47
Изображение ломаных линий
Для построения ломаных линий следует n
– 1 раз вызвать процедуру построения прямой линии, в
результате чего изображаются прямые линии, соединенные в n точках. При каждом последующем вызове функции сообщается пара наборов координат, необходимых для построения следующего отрезка прямой, причем первой точкой в каждой паре является последняя точка предыдущего отрезка. После того, как в буфер кадра заносится код цвета пикселей, составляющих первый отрезок, обрабатывается следующий, начиная с пикселя, идущего после первого конца этого отрезка. Таким образом можно избежать дублирующего присвоения точкам – концам отрезка кода цвета.
Слайд 48
Параллельные алгоритмы построения прямых
В рассмотренным ранее методах построения
прямых положения пикселей определялись последовательно. Параллельная же обработка позволяет
одновременно рассчитывать положения нескольких пикселей на прямой, распределяя вычисления между различными доступными процессорами.
Одним из способов решения задачи распределения является модификация существующего последовательного алгоритма, позволяющая воспользоваться преимуществами, которые предлагают несколько процессоров. Кроме того, можно придумать другой алгоритм обработки, когда положения пикселей эффективно вычисляются по параллельной схеме. При создании параллельного алгоритма важным вопросом является равномерное распределение задач по обработке данных среди доступных процессоров.
Если доступно np процессоров, параллельный алгоритм построения прямой линии Брезенхема получается путем деления прямой на np частей с созданием отрезков на каждом подинтревале. Для прямой линии с тангенсом угла наклона 0 < a < 1, и координатами левого конца отрезка (х0, у0) прямую можно разделить в положительном направлении оси х. Расстояние между начальными точками соседних частей по координате х определяется следующим образом:
Слайд 49
Параллельные алгоритмы построения прямых
(17)
где ∂х –
длина линии, а длина отрезков ∂хр , на которые
разбивается эта линия, вычисляется с помощью целочисленного деления. Пронумеровав полученные части и процессоры от 0 до nр-1, начальную координату k-ого сегмента можно найти как
xk = x0 +k * ∂хp (18)
Допустим, nр = 4, а ∂х = 15. Тогда длина каждого интервала исходной линии будет 4, а координаты начала каждого из них можно определить как х0, х0+4, х0+8, х0+12. Очевидно, что возможна ситуация, когда крайний правый интервал будет короче всех остальных. Также, если координаты концов отрезка будут не целыми числами, то округление может привести к тому, что разные отрезки прямой будут иметь разную длину.
Чтобы применить к этим подинтервалам алгоритм Брезенхема, нужно знать начальное значение координаты у и начальное значение параметра принятия решения для каждого подинтервала. Изменение ∂уp в направлении координаты у для каждого отрезка рассчитывается по наклону прямой а и длине отрезков ∂хp, на которые разбивается прямая.
Слайд 50
Параллельные алгоритмы построения прямых
(19)
Таким образом, для
k-ого сегмента начальное значение координаты e будет равным
yk =
y0 + round ( k * ∂уp ) (20)
Исходное значение параметра принятия решения для алгоритма Брезенхема в начале k-ого подинтервала находится из уравнения (14):
pk =2 * ∂y * (k* ∂xp) – round (2 * ∂x * k* ∂yp ) + 2 * ∂у - ∂x (21)
Затем каждый процессор рассчитывает положения пикселей на выделенном ему участке, используя предыдущее значение начального параметра принятия решения и начальные координаты (xk, yk). При определении начальных значений yk и рk вычисления с величинами с плавающей точкой можно свести к арифметическим действиям с целыми числами, выполнив замену a = ∂y/∂x и перегруппировав члены уравнения.
Параллельный алгоритм Брезенхема можно применить и к пряой, тангенс угла наклона которой больше 1, разделив прямую на сегменты по координате у. При отрицательном тангенсе одна из координат увеличивается, а вторая параллельно уменьшается.
Слайд 51
Параллельные алгоритмы построения прямых
Еще один способ реализации параллельного
алгоритма в растровых системах – соотнести с каждым процессором
определенную группу пикселей на экране. При достаточном количестве процессоров с каждым из них можно соотнести один пиксель из какой-то области экрана. Этот подход применяется для изображения прямых, где каждому пикселю в пределах координатных областей заданной прямой ставится в соответствие один процессор и вычисляется расстояние от пикселей до самой прямой. Количество пикселей в ограничивающем прямоугольнике равно ∂х * ∂у . Перпендикулярное расстояние d от прямой до пикселя с координатами (х, у) находится следующим образом
d = A * x + B * y + C (22)
где
причем
Слайд 52
Параллельные алгоритмы построения прямых
Когда для данной прямой будут
найдены константы А, В, С, каждый процессор должен выполнить
две операции умножения и две операции сложения, чтобы рассчитать расстояние до пикселя d. Пиксель изображается, если расстояние меньше заданного параметра толщины линии.
Вместо того, чтобы разбивать экран на отдельные пиксели, можно с каждым процессором сопоставить строку развертки, либо столбец пикселей, в зависимости от угла наклона. После этого каждый процессор будет вычислять точку пересечения прямой с горизонтальной строкой или вертикальным столбцом пикселей, соответствующих этому процессору. Для прямой, тангенс угла наклона которой по абсолютной величине меньше 1, каждый процессор просто решает уравнение прямой относительно у при заданном значении столбца х. Если же тангенс по абсолютно величин больше 1, тогда процессор решает уравнение прямой относительно х, при заданном значении у. Хотя при таком прямом проходе на машинах с последовательной обработкой вычисления производятся медленно, их можно эффективно ускорить с помощью большого числа процессоров.
Слайд 53
Запись значений в буфер кадров
Последним этапом процедуры изображения
прямолинейных отрезков и других объектов является запись кодов цвета
в буфер кадра. Так как алгоритмы преобразования стандартов развертки выдают координаты пикселей в последовательных единичных интервалов, для эффективного обращения к буферу кадров на каждом шаге процесса преобразования стандартов развертки также можно использовать операции приращения.
Рассмотрим пример. Допустим, что обращение к массиву буфера кадра происходит в порядке возрастания номера строки, и что положениям пикселей присваиваются координаты от ( 0 , 0 ) в левом нижнем углу экрана до ( xmax , ymax ) в правом верхнем углу экрана. Для двухуровневой системы (один бин на пиксель) битовый адрес положения пикселя ( х , у ) находится как
address( x , y ) = address ( 0 , 0 ) + y ( xmax + 1) + x (23)
Следую по строке развертки, адрес в буфере кара пикселя с координатами ( х + 1 , у ) можно найти как следующий сдвиг от адреса пикселя с координатами ( х , у )
address( x + 1 , y + 1) = address ( х , у ) + 1 (24)
Слайд 54
Запись значений в буфер кадров
Перемещаясь по диагонали от
точки ( x , y ) на следующую строку
развертки, находим точку, адрес которой в буфере кадра будет ( x + 1 , y + 1)
address ( x + 1 , y + 1) = address (x , y ) + xmax + 2 (25)
где постоянная xmax + 2 рассчитывается заранее один раз для всех отрезков. Аналогичные вычисления приростов можно получить с помощью (23) для единичных шагов в отрицательном направлении координат х и у на экране. Каждый расчет адреса включает только одну операцию целочисленного сложения.
Реализация этих процедур зависит от возможностей конкретной системы и проектных требований программного пакета. Для систем, которые могут изображать каждый пиксель с несколькими значениями интенсивности, вычисление адреса из буфера кадра, кроме определения положения пикселя на экране, включают еще и вычисление ширины пикселя (количество битов).
Слайд 55
Функции кривых OPEngl
В корневую библиотеку OpenGL не включены
в качестве функций-примитивов функции создания таких кривых основных типов,
как окружности и эллипсы. Однако в этой библиотеке есть функции для изображения сплайнов Безье, представляющих собой полиномы, которые задаются набором дискретных точек. В библиотеку OpenGL Utility ( GLU ) есть процедуры для создания трехмерных поверхностей второго порядка, таких ка сферы и цилиндры, а также функции для построение рациональных би-сплайнов, т.е. сплайнов, которые включают более простые кривые Безье. С помощью рациональных би-сплайнов можно изображать окружности, эллипсы и другие двухмерные поверхности второго порядка. Кроме того, в пакете OpenGL Utulity Toolkit ( GLUT ) есть процедуры, с помощью которых можно изображать такие трехмерные поверхности второго порядка, как сферы и конусы, а также некоторые другие фигуры. Однако эти стандартные процедуры намного сложнее, чем те основные примитивы, с которыми мы уже знакомы.
Слайд 56
Функции кривых OPEngl
Еще один способ создания изображения простой
кривой – аппроксимировать ее с помощью ломаной линии. Нужно
всего лишь задать набор точек, расположенных на этой кривой, а затем соединить их. Причем, чем больше будет этих точек, тем более гладким будет изображение этой кривой.
Третий способ – написать собственную функцию для построения кривой, основанную на алгоритмах, которые будут нами рассмотрены в дальнейшем.
Слайд 57
алгоритмы построения окружностей
Поскольку окружность – элемент, который часто
используется в рисунках и графиках, во многие графические пакеты
включена процедура изображения или полных окружностей, или различных дуг Кроме того, иногда в графической библиотеке содержатся функции изображения различных типов кривых, включая окружности и эллипсы.
Окружность определяется как геометрическое место точек, удаленных на заданное расстояние r от центра с координатами (xc, yc). Для любой точки окружности взаимосвязь с этим расстоянием в декартовых координатах выражается через теорему Пифагора:
( х – хс )2 + ( у – ус )2 = r2 (26)
Слайд 58
алгоритмы построения окружностей
Можно регулировать величину этого промежутка, меняя
местами х и у (делая шаг по оси у
и вычисляя соответствующий х), когда абсолютное значение тангенса угла наклона окружности больше 1. Но это увеличит объем операций и время на обработку.
Слайд 59
алгоритмы построения окружностей
Еще один способ устранения неодинаковых промежутков
– найти точки на границе круга с помощью полярных
координат r и Θ, в которых уравнение окружности имеет вид:
х = хс + r cos Θ
y = yс + r sin Θ (28)
Если изображение создается с помощью этих уравнений при фиксированном шаге по углу, окружность строится из точек, расположенных по кругу через одинаковые интервалы. Чтобы уменьшить объем вычислений, можно сделать угловое расстояние между точками на окружности большим и соединять эти точки прямолинейными отрезками, аппроксимируя ими окружность. Для того, чтобы на растровом экране получить более гладкую линию, размер углового шага можно задать равным 1/r. При этом пиксели будут располагаться приблизительно на одинаковом расстоянии друг от друга. Из минусов такого подхода – необходимость использовать трудозатратные тригонометрические функции.
Слайд 60
алгоритмы построения окружностей
При любом из описанных способов прорисовки
окружностей можно уменьшить количество вычислений, учтя симметрию окружности. Если
определить положение кривой в первом квадранте, можно построить часть окружности во втором сегменте, отразив кривую симметрично относительно оси у. И так далее по аналогии. Этим путем можно пройти еще дальше и воспользоваться симметрией октантов.
На рисунке видно, что, зная координаты точки ( х, у ) на одной восьмой части окружности, можно изобразить еще 7 точек этой окружности.
Зная это, можно прорисовать лишь точки на секторе от х = 0 до х = у.
Слайд 61
алгоритмы построения окружностей
Но определение координат пикселей окружности с
использованием симметрии и уравнений (26)
( х – хс )2
+ ( у – ус )2 = r2
или (28)
х = хс + r cos Θ
y = yс + r sin Θ
требует существенного объема вычислений.
Более эффективные алгоритмы построения окружностей основаны на вычислении прироста параметра принятия решения, как это было в алгоритме Брезенхема, куда входят только простые операции с целыми числами.
Алгоритм Брезенхема для построения прямой линии можно адаптировать для построения окружностей, устранив на каждом шаге выборки параметры принятия решения для определения ближайшего к окружности пикселя.
Слайд 62
алгоритм построения окружности методом средней точки
Здесь мы будем
разбивать на единичные отрезки аппроксимируемую линию и на каждом
шаге будем определять координаты пикселей, которые находятся ближе всего к заданной окружности. При известном радиусе r и координатах центра окружности на экране ( хс, ус ) вначале можно организовать алгоритм таким образом, чтобы рассчитать координаты пикселей вокруг окружности с центром в ( 0, 0 ). После этого каждое рассчитанное положение ( х, у ) перемещается в соответствующую ему точку на экране, для чего хс прибавляется к х, ус – к у. На дуге окружности от х = 0 до х = у в первом квадранте тангенс угла наклона кривой меняется от 0 до -1. Таким образом, у этом октанте можно брать единичный шаг в положительном направлении координаты х и на основе параметра принятия решения определять, какой из пикселей в каждом столбце находится ближе по вертикали к заданной окружности. После этого, используя симметрию, находим координаты пикселей окружности в остальных семи октантах.
Слайд 63
алгоритм построения окружности методом средней точки
Чтобы воспользоваться методом
средней точки, зададим функцию окружности как
fcircl( x, y )
= x2 + y2 –r2 (29)
Любая точка ( х, у ), которая лежит на окружности радиуса r, удовлетворяет уравнению fcircl( x, y ) = 0. Если точка находится внутри круга, значение функции будет положительным.
(30)
Проверка (30) выполняется на каждом шаге выборки для средних положений между пикселями вблизи заданной окружности. Таким образом, функция окружности – это параметр принятия решения в алгоритме средней точки, и для этой функции можно установить операции приращения, как это было сделано для алгоритма построения прямой линии.
Слайд 64
алгоритм построения окружности методом средней точки
На рисунке показана
средняя точка между двумя возможными пикселями в точке выборки
xk+1. Допустим, только что поставлена точка в пикселе с координатами ( xk , yk ). Теперь определим, какой из двух пикселей ближе к заданной окружности – пиксель с координатами ( xk +1 , yk ) или пиксель с координатами ( xk + 1 , yk - 1 ). Параметром принятия решения будет функция окружности (29), которая рассчитывается для средней точки между этими двумя пикселями:
(31)
Слайд 65
алгоритм построения окружности методом средней точки
Если
< 0, данная точка лежит внутри окружности, и
к заданной окружности будет ближе пиксель, который находится в строке развертки yk. В противном случае средняя точка находится за пределами окружности или лежит на ней, и выбирается пиксель в строке развертки yk -1.
Последующие параметры принятия решения находятся с помощью операции приращения. Рекурсивное выражение для следующего параметра принятия решения получается вычислением функции окружности в точке выборки xk + 2:
или
(32)
где - это либо yk, или yk-1, в зависимости от знака pk.
Слайд 66
алгоритм построения окружности методом средней точки
Прирост, с помощью
которого находится pk+1, равен либо 2xk+1+1
( если pk отрицательное), либо 2xk+1+1-2уk+1. Члены 2xk+1 и 2уk+1 также можно оценить через прирост значения как
2xk+1 = 2xk + 2
2уk+1 = 2уk - 2
В начальном положении ( 0 , r ) эти два параметра имеют значения 0 и 2 r соответственно. Каждое последующее значение 2xk+1 находится прибавлением 2 к предыдущему значению, а каждое последующее значение 2уk+1 получается вычитанием 2 из предыдущего значения.
Чтобы найти начальный параметр принятия решения, вычисляется функция окружности в начальном положении ( х0, у0 ) = ( 0, r ):
(33)
Если радиус r – целое число, то все приросты - целые числа, p0 можно просто округлить до
р0 = 1 - r
Слайд 67
алгоритм построения окружности методом средней точки
Алгоритм:
1. Вводим радиус
r и координаты центра окружности ( xc , ус
), затем задать координаты первой точки на окружности, центр которой находится в начале координат ( х0, у0 ) = ( 0, r ).
2. Определяем исходное значение параметра принятия решения
р0 = 5/4 – r.
3. Для каждого значения xk, начиная с k = 0, выполнить следующую проверку:
если pk < 0, то следующая точка на окружности с центром в точке (0,0) будет ( xk +1 , yk ) и pk+1 = pk + 2 xk +1 +1
иначе следующей точкой на окружности будет точка ( xk +1 , yk-1 ) и
и pk+1 = pk + 2 xk +1 +1 - 2 уk +1 , где 2 xk +1 = 2 + 2 xk и 2 уk +1 = 2 уk - 2.
4. Находим симметричные точки в остальных семи октантах.
5. Перемещаем все рассчитанные пиксели с координатами ( х, у ) на окружность с центром в точке с координатами ( хс , ус ) и отмечаем точки с координатами х = х + хс , у = у + ус .
6. Повторяем этапы 3 – 5 до тех пор, пока не получится, что x ≥ у.
Слайд 68
алгоритм построения окружности методом средней точки
void circlePlotPoints(int
xc, int yc, int x, int y)
{
setPixel(xc + x,
yc + y);
setPixel(xc + x, yc - y);
setPixel(xc - x, yc + y);
setPixel(xc - x, yc - y);
setPixel(xc + y, yc + x);
setPixel(xc + y, yc - x);
setPixel(xc - y, yc + x);
setPixel(xc - y, yc - x);
}
Слайд 69
алгоритм построения окружности методом средней точки
void circleMiddlePoint(int xc,
int yc, int r)
{
int p = 1 - r;
int
x = 0, y = r;
while (x <= y)
{
circlePlotPoints(xc, yc, x, y);
x++;
if (p < 0)
p += 2 * x + 1;
else
{
y--;
p += 2 * (x - y) + 1;
}}}
Слайд 70
алгоритм построения окружности методом средней точки
Слайд 71
алгоритм построения Эллипса
Эллипс – эта вытянутая окружность. Так
что его можно описать, как модифицированную окружность, радиус которой
меняется от максимального значения в одном направлении до минимального значения в перпендикулярном направлении. Прямолинейные отрезки, проведенные внутри эллипса по этим двум перпендикулярным направлениям, называются большой и малой осями эллипса.
Точное определение эллипса можно дать, воспользовавшись расстояниями от любой точки эллипса до двух фиксированных точек, которые называются его фокусами. Сумма этих двух расстояний одинакова для всех точек эллипса. Если расстояние от двух фокусов до любой точки Р = ( х, у ) эллипса обозначить d1 и d2, тогда общее уравнение эллипса можно записать как
d1 + d2 = const (34)
Слайд 72
алгоритм построения Эллипса
Если выразить расстояния d1 и d2
через координаты фокусов
F1 = ( x1, y1 ) и F2 = ( x2, y2 ), то получится
(35)
Возведя это уравнение в квадрат и собрав члены с одинаковыми степенями и снова возведя в квадрат, можно переписать общее уравнение эллипса в виде
(36)
, где коэффициенты A, B, C, D, E и F выражаются через координаты фокусов и длины большой и малой осей эллипса. Большая ось – прямой отрезок, который соединяет одну сторону эллипса с другой и проходит через фокусы. Малой осью называется отрезок, покрывающий меньшее расстояние, под прямым углом пересекающий большую ось посредине между двумя фокусами (в центре эллипса).
Эллипс можно описать через его относительную ориентацию: ввести 2 фокуса и точку на границе эллипса. Зная координаты этих трех точек можно найти константу из (35).
Слайд 73
алгоритм построения Эллипса
После этого значения коэффициентов уравнения (36)
вычисляются и используются для изображения пикселей, расположенных на эллипсе.
Уравнения
эллипса значительно упрощаются, если направления большой и малой осей совпадают с координатами осей.
Слайд 74
алгоритм построения Эллипса
Если следовать рисунку, параметр rx обозначает
половину малой оси, а параметр rу – половину большой
оси. Уравнение эллипса с рисунка можно описать через координаты центра эллипса и параметры rx, ry:
(37)
В полярных координатах r и эллипс в стандартном положении можно также описать с помощью параметрического уравнения:
х = хс + rx cos
y = yс + ry sin (38)
Угол , называемый углом эксцентриситета эллипса, изменяется по периметру ограничивающей окружности. Если rx > ry, радиус ограничивающей окружности равен r = rx. В противном случае, радиус будет r = ry.
Как и в алгоритме окружности, количество вычислений можно уменьшить за счет симметрии. Эллипс в стандартном положении симметричен в квадрантах. Можно найти координаты пикселей на дуге эллипса в одном квадранте, а затем найти остальные 3 точки.
Слайд 75
алгоритм построения Эллипса методом средней точки
Алгоритм построения эллипса
методом средней точки аналогичен методу для окружности. Если известны
параметры rx, ry и ( хс, ус ) можно определить координаты точек ( х, у ) эллипса в стандартном положении с центром в начале координат, после этого сместить все точки так, чтобы получить эллипс с центром в точке ( хс, ус ). Если потребуется изобразить эллипс в нестандартном положении, можно развернуть его вокруг центральной точки, чтобы переориентировать большую и малую оси в нужном направлении.
Метод средней точки для эллипса применяется в обеих частях первого квадранта. Первый квадрант делится на части согласно тангенсу угла наклона эллипса, для которого rx < ry. При обработке этого квадранта в этой части, где тангенс угла наклона кривой меньше 1, выполняются единичные шаги в направлении х, а затем в той части, где величина тангенса угла наклона больше 1, выполняются единичные шаги в направлении у.
Области 1 и 2 можно обработать разными способами. Можно начать с точки ( 0 , ry ) и двигаться по часовой стрелке по эллиптической траектории в первом квадранте, а затем перейти от единичного шага по х к единичному шагу по у , тогда тангенс угла станет меньше -1.
Слайд 76
алгоритм построения Эллипса методом средней точки
Или можно начать
с точки ( rx , 0 ) и выбирать
точки в направлении против часов стрелки, перейдя от единичного шага от у к единичному шагу по х, когда тангенс угла наклона станет -1. При наличии параллельных процессоров можно рассчитывать координаты пикселей в двух областях одновременно.
Мы возьмём за начальное положение точку ( 0 , ry ) и будем перемещаться в первом квадранте по часовой стрелке.
Определим функцию эллипса из уравнения (37) при (хс, ус) = ( 0, 0).
felipse( x, y ) = ry2x2 + rx2y2 - rx2ry2 (39)
Эта функция обладает следующими свойствами :
(40)
Эта функция является параметром принятия решения в алгоритме средней точки.
Слайд 77
алгоритм построения Эллипса методом средней точки
Начиная с точки
( 0 , ry ) выполняются единичные шаги в
направлении х до тех пор, пока не будет достигнута граница между областями 1 и 2. Затем мы переключается на единичные шаги в направлении у на оставшейся части кривой в первом квадранте. На каждом шаге нужно проверять значение тангенса угла наклона кривой, который находится из уравнения (39)
(41)
На границе между областью 1 и 2 dy/dx = -1 и 2*ry2 *x = 2*rx2 *y. Следовательно, мы выходим за пределы области 1 когда
(42)
На рисунке изображена средняя точка между 2
возможными положениями пикселей, которая опреде-
ляется при точке выборки xk + 1 в первой области. До-
пустим на предыдущем шаге было выбрано положе-
ние ( xk , yk ) найдем следующее положение на эллип-
тической траектории, вычислив параметр принятия ре-
шение в этой средней точке
Слайд 78
алгоритм построения Эллипса методом средней точки
(43)
Если р1k
0, средняя точка находится внутри эллипса, тогда пиксель в
строке развертки yk будет ближе к границе эллипса. В противном случае средняя точка лежит за пределами эллипса или на его границе и выбирается пиксель в строке развертки yk-1/
В следующей точке выборки (xk+1 + 1 = xk + 2 ) параметр принятия решения для области 1 ищется как
или
(44)
где yk+1 равно yk или yk-1 в зависимости от знака p1k.
Параметры принятия решения увеличивается на следующие величины:
Слайд 79
алгоритм построения Эллипса методом средней точки
Приросты для параметров
принятия решения вычисляются с использованием только операции сложения и
вычисления, как в алгоритме для окружности, поскольку значения членов и 2*rу2 *х находятся путем сложения приростов. В начальном положении ( 0 , ry ) эти два члена равны
(45)
(46)
С увеличением х и у их новые значения находятся путем прибавления 2*rу2 к текущему значению увеличивающего члена, представленного в уравнении (45), и вычитая 2*rх2 из текущего значения члена, представленного в уравнении (46). На каждом шаге сравниваются новые значения приростов, и при выполнении условия (42) мы переходим из области 1 в область 2.
В области 1 начальное значение параметра принятия решения находится через функцию эллипса в начальной точке ( х0, у0 ) = (0 , ry):
2*rx2 *y
Слайд 80
алгоритм построения Эллипса
(47)
В области 2 выполняется выборка с
единичным интервалом в отрицательном направлении координаты у, а средняя
точка на каждом шаге теперь берется между горизонтальными пикселями. Для такой области параметр принятия решения находится как : (48)
Если р2k > 0, средняя точка находится за пределами эллипса, и выбирается пиксель с координатой xk. Иначе средняя точка расположена либо внутри, либо на границе эллипса и выбирается пиксель с координатой xk+1.
Чтобы найти взаимосвязь между последовательными параметрами принятия решения в области 2, найдем функцию эллипса для следующего шага yk+1 – 1 = yk – 2 (49)
Слайд 81
алгоритм построения Эллипса методом средней точки
или
(50)
при хk+1 равным
либо xk или xk+1 в зависимости от знака p2k.
При
входе в область 2 в качестве начальной точки ( х0 , у0) берется последнее положение в области 1, и тогда начальный параметр принятия решения для области 2 будет равен (51)
Чтобы упростить вычисление p20, положения пикселей можно выбирать в направлении против часовой стрелки, начиная с точки ( rx,0 ). Тогда единичные шаги выполняются в положительном направлении оси у до тех пор, пока не будет выбрано последнее положение в области 1.
Этот алгоритм можно применять и для эллипсов с нестандартным положением, воспользовавшись функцией эллипса
и вычисляя координаты пикселей на всей траектории.
Слайд 82
алгоритм построения Эллипса методом средней точки
Алгоритм:
1. Вводим rx,
ry и координаты центра эллипса (хс, ус), а затем
найти первую точку эллипса с центром в начале координат ( х0 , у0) = ( 0 , ry).
2. Вычислить начальное значение параметра принятия решения в области 1:
3. Для каждого значения xk в области 1, начиная с k=0, провести следующую проверку. Если p1k < 0, следующей точкой эллипса с центром ( 0, 0) будет ( xk+1, yk) и
В противном случае следующей точкой эллипса будет ( xk+1, yk-1) и
при
Этот процесс прекращается, когда
![Функции точек в openglint point1[] = 50,100;int point2[] = 75,150;int point3[] =](/img/tmb/13/1270381/b8ec13ba14830d239aeec89dda5ed135-720x.jpg "Выходные графические примитивы")
![Функции прямых в openglglClear(GL_COLOR_BUFFER_BIT);glColor3f(0, 0, 1.0);int p1[] = { 9,3 };int p2[]](/img/tmb/13/1270381/1ecf7c18e16864c197dba3645c52aa13-720x.jpg "Выходные графические примитивы")
![Функции прямых в openglglClear(GL_COLOR_BUFFER_BIT);glColor3f(0, 0, 1.0);int p1[] = { 9,3 };int p2[]](/img/tmb/13/1270381/72f2eecfb20c27cd03682a7215900604-720x.jpg "Выходные графические примитивы")
![Функции прямых в openglglClear(GL_COLOR_BUFFER_BIT); glColor3f(0, 0, 1.0); int p1[] = { 9,3 }; int p2[]](/img/tmb/13/1270381/bb53e96e3d74d9e655039e4dace875ae-720x.jpg "Выходные графические примитивы")
