Визуализация отрезков прямых

Начнем построение отрезка, взяв за начальное значение текущей точки P точку P1. Будем двигаться от нее по дискретной плоскости к конечной точке P2, стремясь отклоняться от прямой P1P2 в наимень- шей степени. Направление движения и значения элементарных шагов sx и sy по осям зависят от знаков приращений ∆x и ∆y. Если ∆x > 0, то sx = 1. Если же ∆x < 0, то sx = -1. Следовательно, sx = sign(∆x). Анало- гично элементарным шагом по координате y будет sy = sign(∆y). Любая точка на дискретной плоскости имеет 8 соседних. Если учитывать направление движения от P1 к P2, то для выбора очередной точки вместо 8 достаточно рассматривать только 3 соседние точки. Чтобы еще сократить выбор, рассмотрим частный случай, когда |∆x| ³ |∆y|. Ему соответствуют отрезки с углом наклона к оси OX, меньшим или равным 450 . Тогда новым значением текущей точки P с коорди- натами (x, y) может быть либо точка (x + sx , y), либо (x + sx , y + sy). Для выбора лучшей из них используем оценочную функцию. Так как за начальное значение P принята точка P1, лежащая на прямой P1P2, то начальное значение F(x , y) = 0. Для соседней точки (x + sx , y) имеем F(x + sx, y) = ∆y(x + sx – x1) – ∆x(y – y1) = F(x, y) + sx ∆y. (2.7)

1. Установить цвет рисования Color.

2. Вычислить:

∆x = x2 – x1; ∆y = y2 – y1; sx = sign(∆x); sy = sign(∆y);

Еслиsx> 0, тогда ∆Fx = ∆y, иначе ∆Fx = – ∆y.

Если sy> 0, тогда ∆Fy = ∆x, иначе ∆Fy = – ∆x. x = x1; y = y1; // начальные координаты текущей точки

F = 0. // начальное значение оценочной функции

3. Вывести пиксель с координатами (x, y) цветом Color.

4. Если x = x2 , то – конец алгоритма.

5. Вычислить: Fx = F + ∆Fx; F = Fx – ∆Fy; x = x + sx.

6. Если êFxê<êF ê, то вычислить F = Fx, иначе – вычислить y = y + sy.

7. Перейти к п. 3.

Двумерные примитивы

К двумерным примитивам относят точки, линии, отрезки прямых (векторы) и кривых линий, много- угольники, ограниченные области плоскости. Границей области могут служить многоугольник или кривая линия, например окружность. Конкретный состав используемых примитивов в зависимости от прикладного назначения программы может быть различным. Примитивы характеризуются описанием их геометрии и видом закрашивания. Закрашивание может быть однотонным, т.е. задаваться кодом цвета. Кроме этого используется текстурное закрашивание ограниченных областей с помощью образцов текстур. Рассмотрим описание геометрии наиболее общих видов примитивов. Точки на плоскости обычно задаются своими координатами (x, y). Для аналитического задания линий используют алгебраические уравнения или системы функций. Алгебраические линии описываются алгебраическими уравнениями вида F(x, y) = 0. Из них на практике чаще используют прямые линии и линии второго порядка (эллипсы, параболы, гиперболы). Прямые линии в алгебраической форме задаются уравнением первого порядка: a1 x + a2 y + a3 = 0. (2.1) Общее уравнение линии второго порядка имеет следующий вид: a11 x 2 + a22 y 2 + 2 a12 x y + 2 a13 x + 2 a23 y + a33 = 0. (2.2) Произвольные гладкие кривые принято задавать параметрическими функциями видаP(t) =[x(t) y(t)]. (2.3) Матрица-строка P(t) содержит функции x(t), y(t) от общего пара- метра t, которые определяют значения координат x, y всех точек пара- метрической кривой. Если дополнительно ограничить область измене- ния параметра t1 £ t £ t2, то на линии будет выделен отрезок. Например, отрезок параболы между точками (x0, y0) и (x0 + kx , y0 + ky) задается функциями x(t) = x0+ kx t, y(t) = y0 + ky t 2 и ограничением 0 £ t £ 1. В качестве базисных функций для x(t) и y(t) используют полино- миальные функции, такие, как полиномы Лежандра, Ньютона, Эрми- та, Бернштейна. Выбор базиса зависит от постановки задачи и требо- ваний к качеству кривой. Полиномиальные параметрические кривые называются сплайнами. Кроме выбора базиса для описания конкретной кривой нужно за- дать начальные условия. Начальные условия определяют расположе- ние, размеры и общий характер линии, поэтому при конструировании сплайнов в качестве начальных условий стремятся использовать такие, которые имеют понятный геометрический смысл: узловые точки кри- вой, касательные векторы к кривой. В то же время начальные условия должны однозначно определять все коэффициенты функций x(t) и y(t). Многоугольник общего вида описывается списком его вершин, т.е. списком точек P1, P2,…, Pn на плоскости, которые последова- тельно соединяются отрезками прямых, причем имеется в виду, что последняя точка соединяется с первой: Pg = (P1, P2,…, Pn). (2.4) В этом смысле многоугольник является частным случаем лома- ной линии и не представляет особого интереса для синтеза более сложных объектов, поэтому в компьютерной графике, говоря о мно- гоугольнике, в качестве примитива обычно рассматривают ограни- ченную многоугольную область, т.е. область плоскости с границей в виде многоугольника (рис. 2.1). Частными случаями многоугольников являются правильные мно- гоугольники, т.е. многоугольники, у которых равны все стороны и углы между смежными сторонами. Правильный многоугольник мо- жет быть вписан в окружность (рис. 2.2), поэтому правильные много- угольники удобно задавать через параметры описанной окружности (xc ,yc), R и число сторон n. Рис. 2.1 Рис. 2.2 Следует только отметить, что в этом способе задания однозначно не определяется расположение вершин многоугольника на окружности. Однако если в программной процедуре расчета вершин многоугольни- ка определенный порядок их расположения на окружности выбирается по умолчанию, то в большинстве случаев это бывает приемлемым. Области на плоскости могут ограничиваться не только много- угольниками, но и кривыми линиями, например окружностями, но для сокращения объема вычислений при визуализации их обычно аппроксимируют многоугольниками, т.е. все ограниченные области приводятся к единому полигональному формату.

Кубические сплайны

Кубическими сплайнами называются параметрические кривые, для которых в качестве базисных функций используются полиномы 3-й степени вида a t 3 + b t 2 + c t + d. (2.11) На плоскости кубический сплайн задается следующим образом: ( ) [] . 3 2 3 2 x xxx y yydy P t = a t + b t + c t + d a t + b t + c t + (2.12) Параметр t изменяется в пределах 0 £ t £ 1. При этом начальной точкой сплайна будет P(0), а конечной – точка P(1). Для однозначного задания кубического сплайна в форме Эрмита [1] используют следующие начальные условия (рис. 2.7): - кривая должна проходить через заданные начальную T1 и конечную T2 точки; - в начальной и конечной точках должны быть заданы касательные векторы T¢ 1 и T¢ 2 к кривой

Кривые Безье