МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Трехмерная компьютерная графика

    Zшаг – шаг между плоскостями z = const

    Dimension Верх (Гэкран), Низ (Гэкран)

    инициализация переменных

    Xлевое = (1; Yлевое = (1; Xправое = (1; Yправое = (1

    инициализация массивов горизонтов

    Верх = 0

    Низ = Вэкран

    Вычисление функции на каждой плоскости z = const, начиная с ближайшей к

    наблюдателю плоскости Zmax

    for z = Zmax to Zmin step ( Zшаг

    инициализация предыдущих значений по x и y: Xпред и Yпред

    Xпред = Xmin

    Yпред = f (Xmin, z)

    если используется видовое преобразование, то его нужно применить к

    Xпред, Yпред, z в данной точке

    обработка левого бокового ребра

    call Обрребра (Xпред, Yпред, Xлев, Yлев; Верх, Низ)

    call Видимость (Xпред, Yпред, Верх, Низ; Пфлаг)

    для каждой точки на кривой, лежащей в плоскости z = const

    for x = Xmin to Xmax step Xшаг

    y = f (x, z)

    если используется видовое преобразование, то его нужно применить к

    данной точке

    проверка видимости текущей точки и заполнение соответствующего

    массива горизонта

    call Видимость (x, y, Верх, Низ; Тфлаг)

    if Тфлаг = Пфлаг then

    if (Тфлаг = 1) or (Тфлаг = (1) then

    Draw (Xпред, Yпред, x, y)

    call Горизонт (Xпред, Yпред, x, y; Верх, Низ)

    end if

    если видимость изменилась, то вычисляется пересечение и заполняется

    массив горизонта

    else

    if Тфлаг = 0 then

    if Пфлаг = 1 then

    call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

    else

    call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

    end if

    Draw (Xпред, Yпред, Xi, Yi)

    сall Горизонт (Xпред, Yпред, Xi, Yi, Верх, Низ)

    else

    if Тфлаг = 1 then

    if Пфлаг = 0 then

    call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

    Draw (Xi, Yi, x, y)

    сall Горизонт (Xi, Yi, x, y; Верх, Низ)

    else

    call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

    Draw (Xпред, Yпред, Xi, Yi)

    call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

    call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

    Draw (Xi, Yi, x, y)

    call Горизонт (Xi, Yi, x, y; Верх, Низ)

    end if

    else

    if Пфлаг = 0 then

    call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

    Draw (Xi, Yi, x, y)

    call Горизонт (Xi, Yi, x, y; Верх, Низ)

    else

    call Пересечение (Xпред, Yпред, x, y, Верх; Xi, Yi)

    Draw (Xпред, Yпред, Xi, Yi)

    call Горизонт (Xпред, Yпред, Xi, Yi; Верх, Низ)

    call Пересечение (Xпред, Yпред, x, y, Низ; Xi, Yi)

    Draw (Xi, Yi, x, y)

    call Горизонт (Xi, Yi, x, y; Верх, Низ)

    end if

    end if

    end if

    end if

    вновь инициализировать Пфлаг, Xпред, Yпред

    Пфлаг = Тфлаг

    Xпред = x

    Yпред = y

    next x

    обработка правого концевого ребра

    call Обрребра (x, y, Xправ, Yправ; Верх, Низ)

    next z

    finish

    подпрограмма обработки бокового ребра

    Subroutine Обрребра (x, y, Xребра, Yребра; Верх, Низ)

    если Xребра = (1, то встречена первая кривая и ребро не создаётся

    if Xребра = (1 then 1

    call Горизонт (Xребра, Yребра, x, y; Верх, Низ)

    1 Xребра = x

    Yребра = y

    return

    подпрограмма определения видимости точки

    Subroutine Видимость (x, y, Верх, Низ; Тфлаг)

    видимость точки определяется по отношению к верхнему и нижнему

    плавающим горизонтам. Если точка лежит на самом горизонте, то она

    считается видимой.

    Тфлаг = 0, если точка невидима

    = 1, если она видима и выше верхнего горизонта

    = (1, если она видима и ниже нижнего горизонта

    x считается целой

    if (y < Верх (x)) and (y > Низ (x)) then Тфлаг = 0

    if y ( Верх (x) then Тфлаг = 1

    if y ( Низ (x) then Тфлаг = (1

    return

    подпрограмма заполнения массивов плавающих горизонтов

    Subroutine Горизонт (X1, Y1, X2, Y2; Верх, Низ)

    Эта программа использует линейную интерполяцию для заполнения массивов

    горизонтов между X1 и X2

    Max (a, b) – определяет большее из a и b

    Min (a, b) – определяет меньшее из a и b

    проверка вертикальности наклона

    if (X2 ( X1) = 0 then

    Верх (X2) = Max (Верх (X2), Y2)

    Низ (X2) = Min (Низ (X2), Y2)

    else

    Наклон = (Y2 ( Y1)/(X2 ( X1)

    for x = X1 to X2 step 1

    y = Наклон * (x ( X1) + Y1

    Верх (x) = Max (Верх (x), y)

    Низ (x) = Min (Низ (x), y)

    next x

    end if

    return

    подпрограмма вычисления пересечения текущей кривой с горизонтом

    Subroutine Пересечение (X1, Y1, X2, Y2, Массив; Xi, Yi)

    Эта процедура вычисляет пересечение двух отрезков прямых

    Массив содержит информацию о соответствующем горизонте

    Sign – функция принимающая значения (1, 0, 1, если знак её аргумента

    0 соответственно

    проверка бесконечности наклона

    if (X2 – X1) = 0 then

    Xi = X2

    Yi = Массив (X2)

    else

    вычисление пересечения

    обход начинается с самой левой используемой точки

    пересечение считается обнаруженным, когда изменяется знак разности

    значений y

    Наклон = (Y2 – Y1)/(X2 – X1)

    Ysign = Sign (Y1 + Наклон ( Массив (X1 + 1))

    Csign = Ysign

    Yi = Y1 + Наклон

    Xi = X1 + 1

    while Csign = Ysign

    Yi = Y1 + Наклон

    Xi = X1 + 1

    Csign = Sign (Yi - Массив (Xi))

    end while

    выбирается ближайшее целое число

    if |Yi ( Наклон ( Массив (X1 – 1)| ( |Yi ( Наклон ( Массив (X1)| then

    Yi = Y1 – Наклон

    Xi = X1 – 1

    end if

    end if

    return

    В приведенных выше алгоритме и примере функция у = f (x, z)

    рассматривалась только при z = const. Часто бывает удобно вычерчивать

    кривые, полагая постоянными как z, так и x. При этом возникает эффект

    перекрестной штриховки. На первый взгляд может показаться, что перекрестную

    штриховку можно получить путем наложения двух результатов, образованных

    плоскостями z = const и x = const. Однако это не так. Верный результат

    получается при обработке тех кривых из числа лежащих в плоскостях z = const

    и x = const, которые ближе всего к горизонтальным при обычном порядке их

    следования. Однако после обработки каждой кривой, самой близкой к

    горизонтальной, необходимо обрабатывать участки кривых, лежащих в

    ортогональных ей плоскостях, которые находятся между указанной кривой и

    кривой, следующей за ней. Разумеется, при обработке обеих

    последовательностей кривых нужно использовать одни и те же массивы верхнего

    и нижнего плавающих горизонтов. Если используется перекрестная штриховка,

    то не надо формировать левое и правое боковые ребра.

    2. Алгоритм Робертса

    Алгоритм Робертса представляет собой первое известное решение задачи об

    удалении невидимых линий . Это математически элегантный метод, работающий в

    объектном пространстве. Алгоритм, прежде всего, удаляет из каждого тела те

    ребра или грани, которые экранируются самим телом. Затем каждое из видимых

    ребер каждого тела сравнивается с каждым из оставшихся тел для определения

    того, какая его часть или части, если таковые есть, экранируются этими

    телами. Поэтому вычислительная трудоемкость алгоритма Робертса растет

    теоретически как квадрат числа объектов. Именно этот факт привёл к снижению

    интереса к алгоритму Робертса. Однако математические методы, используемые в

    этом алгоритме, просты, мощны и точны. Кроме того, этот алгоритм можно

    использовать для иллюстрации некоторых важных концепций. Наконец, более

    поздние реализации алгоритма, использующие предварительную приоритетную

    сортировку вдоль оси z и простые габаритные или минимаксные тесты,

    демонстрируют почти линейную зависимость от числа объектов.

    В алгоритме Робертса требуется, чтобы все изображаемые тела или объекты

    были выпуклыми. Невыпуклые тела должны быть разбиты на выпуклые части. В

    этом алгоритме выпуклое многогранное тело с плоскими гранями должно

    представляться набором пересекающихся плоскостей. Уравнение произвольной

    плоскости в трехмерном пространстве имеет вид

    ах + by + cz + d = 0 (3.1)

    В матричной форме это выглядит так:

    [pic]

    или

    [pic]

    где [pic] представляет собой плоскость. Поэтому любое выпуклое твердое тело

    можно выразить матрицей тела, состоящей из коэффициентов уравнений

    плоскостей, т. е.

    [pic]

    где каждый столбец содержит коэффициенты одной плоскости.

    Напомним, что любая точка пространства представима в однородных

    координатах вектором

    [pic]

    Более того, если точка [S] лежит на плоскости, то [S]*[P]T = 0.

    Если же [S] не лежит на плоскости, то знак этого скалярного произведения

    показывает, по какую сторону от плоскости расположена точка. В алгоритме

    Робертса предполагается, что точки, лежащие внутри тела, дают положительное

    скалярное произведение.

    Хотя уравнение плоскости (3.1) содержит четыре неизвестных

    коэффициента, его можно нормировать так, чтобы d = 1 следовательно, трех

    неколлинеарных точек достаточно для определения этих коэффициентов.

    Подстановка координат трех неколлинеарных точек (x1, y1, z1), (x2, y2, z2),

    (x2, y2, z2) в нормированное уравнение (3.1) дает:

    ax1 + by1 + cz1 = (1

    ax2 + by2 + cz2 = (1

    ax3 + by3 + cz3 = (1

    В матричной форме это выглядит так:

    [pic]

    или

    [pic] (3.2)

    Решение этого уравнения дает значения коэффициентов уравнения

    плоскости:

    [pic]

    Другой способ используется, если известен вектор нормали к плоскости,

    т. е.

    n = ai + bj + ck

    где i, j, k - единичные векторы осей x, y, z соответственно. Тогда

    уравнение плоскости примет вид

    ax + by + cz + d = 0 (3.3)

    Величина d вычисляется с помощью произвольной точки на плоскости. В

    частности, если компоненты этой точки на плоскости (х1, y1, z1) то:

    d = ( (aх1 + by1 + cz1) (3.4)

    Поскольку объем вычислений в алгоритмах удаления невидимых линий или

    поверхностей растет с увеличением числа многоугольников, для описания

    поверхностей выгодно использовать многоугольники с более чем тремя

    сторонами. Эти многоугольники могут быть как невыпуклыми, так и неплоскими.

    Метод, предложенный Мартином Ньюэлом, позволяет найти как точное решение

    для уравнений плоскостей, содержащих плоские многоугольники, так и

    «наилучшее» приближение для неплоских многоугольников. Этот метод

    эквивалентен определению нормали в каждой вершине многоугольника

    посредством векторного произведения прилежащих ребер и усреднения

    результатов. Если a, b, c, d – коэффициенты уравнения плоскости, то

    [pic] (3.5)

    где

    if i =n then j = 1 else j = i + 1

    а d вычисляется с помощью любой точки на плоскости.

    Перед началом работы алгоритма удаления невидимых линий или

    поверхностей для получения желаемого вида сцены часто применяется

    трехмерное видовое преобразование. Матрицы тел для объектов преобразованной

    сцены можно получить или преобразованием исходных матриц тел или

    вычислением новых матриц тел, используя преобразованные вершины или точки.

    Если [В] - матрица однородных координат, представляющая исходные

    вершины тела, а [Т] - матрица размером 4х4 видового преобразования, то

    преобразованные вершины таковы:

    [ВТ] = [В][T] (3.6)

    где [ВТ] - преобразованная матрица вершин. Использование уравнения (3.2)

    позволяет получить уравнения исходных плоскостей, ограничивающих тело:

    [В][V] = [D] (3.7)

    где [V] - матрица тела, а [D] в правой части - нулевая матрица. Аналогично

    уравнения преобразованных плоскостей задаются следующим образом:

    [ВТ][VТ] = [D] (3.8)

    где [VТ] - преобразованная матрица тела. Приравнивая левые части уравнения

    (3.7) и (3.8), получаем

    [ВТ][VT] = [В][V]

    Подставляя уравнение (3.6), сокращая на [В] и умножая слева на

    [T]-1 имеем

    [VT] = [T]-1[V]

    Итак, преобразованная матрица тела получается умножением исходной матрицы

    тела слева на обратную матрицу видового преобразования.

    Тот факт, что плоскости имеют бесконечную протяженность и что скалярное

    произведение точки на матрицу тела отрицательно, если точка лежит вне этого

    тела, позволяет предложить метод, в котором матрица тела используется для

    определения граней, которые экранируются самим этим телом. Отрицательное

    скалярное произведение даёт только такая плоскость (столбец) в матрице

    тела, относительно которой точка лежит снаружи.

    Если зритель находится в бесконечности на положительной полуоси z и

    смотрит на начало координат, то его взгляд направлен в сторону

    отрицательной полуоси z. В однородных координатах вектор такого направления

    равен:

    [pic]

    который служит, кроме того, образом точки, лежащей в бесконечности на

    отрицательной полуоси z. Фактически [Е] представляет любую точку, лежащую

    на плоскости z = ( (, т. е. любую точку типа (x, y, ( (). Поэтому, если

    скалярное произведение [Е] на столбец, соответствующий какой-нибудь

    плоскости в матрице тела, отрицательно, то [Е] лежит по отрицательную

    сторону этой плоскости. Следовательно, эти плоскости невидимы из любой

    точки наблюдения, лежащей в плоскости z = (, а пробная точка на z = ( (

    экранируется самим телом, как показано на рис. 3.8. Такие плоскости

    называются не лицевыми, а соответствующие им грани задними.

    Следовательно,

    [Е][V] < 0

    является условием того, что плоскости – не лицевые, а их грани - задние.

    Заметим, что для аксонометрических проекций (точка наблюдения в

    бесконечности) это эквивалентно поиску положительных значений в третьей

    строке матрицы тела.

    Этот метод является простейшим алгоритмом удаления невидимых

    поверхностей для тел, представляющих собой одиночные выпуклые

    многогранники. Этот способ часто называют отбрасыванием задних плоскостей.

    Для выпуклых многогранников число граней при этом сокращается примерно

    наполовину. Метод эквивалентен вычислению нормали к поверхности для каждого

    отдельного многоугольника. Отрицательность нормали к поверхности

    показывает, что нормаль направлена в сторону от наблюдателя и,

    Следовательно, данный многоугольник не виден.

    Этот метод можно использовать также и для простой закраски.

    Интенсивность или цветовой оттенок многоугольника делается пропорциональным

    проекции нормали к поверхности на направление взгляда.

    Данный метод определения не лицевых граней в результате формирует

    аксонометрическую проекцию на некую плоскость, расположенную бесконечно

    далеко от любой точки трехмерного пространства. Видовые преобразования,

    включая перспективное, производятся до определения не лицевых плоскостей.

    Когда видовое преобразование включает в себя перспективу, то нужно

    использовать полное перспективное преобразование одного трехмерного

    пространства в другое, а не перспективное проецирование на некоторую

    двумерную плоскость. Полное перспективное преобразование приводит к

    искажению трехмерного тела, которое затем проецируется на некую плоскость в

    бесконечности, когда не лицевые плоскости уже определены. Этот результат

    эквивалентен перспективному проецированию из некоторого центра на конечную

    плоскость проекции.

    Видовое преобразование можно применить к телу так, чтобы точка

    наблюдения оставалась фиксированной. При другом способе тело остается

    неподвижным. Соответствующие точка наблюдения и направление взгляда

    получаются умножением справа на матрицу, обратную матрице видового

    преобразования.

    После определения нелицевых плоскостей остается найти нелицевые

    отрезки. Нелицевой отрезок образуется в результате пересечения пары

    нелицевых плоскостей. После первого этапа удаления нелицевых отрезков

    необходимо выяснить, существуют ли такие отрезки, которые экранируются

    другими телами на картинке или в сцене. Для этого каждый оставшийся отрезок

    или ребро нужно сравнить с другими телами сцены или картинки. При этом

    использование приоритетной сортировки (z–сортировки) и простого

    минимаксного или габаритного с прямоугольной объемлющей оболочкой тестов

    позволяет удалить целые группы или кластеры отрезков и тел. Например, если

    все тела в сцене упорядочены в некотором приоритетном списке, использующем

    значения z ближайших вершин для представления расстояния до наблюдателя, то

    Страницы: 1, 2, 3, 4, 5, 6


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.