План лекции. Зачем нужны текстуры? Пример линейной закраски треугольников. Недостатки (слишком много треугольников на геометрически простых поверхностях). Понятие текстуры

Вид материала

Лекции

Содержание §1 Зачем нужны текстуры? Рис. 1 ( процесс закраски треугольника ) §2 Отображение текстуры на поверхность. §2.1 Модель, используемая во всех методах. §2.2 Быстрый метод отображения текстур. Алгоритм быстрого наложения текстуры на треугольник. Перебираем горизонтальные строки треугольника сверху вниз с шагом 1. Для каждой строки выполняем следующие шаги (см. Рис. 3) §2.3 Искажения при отображении. Пример §2.4 Mipmapping Построение mip уровней (оценка по памяти) Методы расчета LOD Методы формирования значения текстуры Nearest (см Рис. 5). Trilinear (см. Рис. 5). §2.5 Учет перспективы при отображении. Пример Эффективная реализация алгоритма с учетом перспективы

Подобный материал:

• Лекция 14. Формирование текстуры типичных оксидных носителей и адсорбентов, получаемых, 301.46kb.
• Разработка урока по теме «Признаки равенства треугольников», 53.91kb.
• Урок по геометрии в 7 классе по теме: «Признаки равенства треугольников», 60.74kb.
• Урок по теме: «Признаки равенства треугольников», 57.32kb.
• А. С. Пушкина р п. Колышлей Пензенской области Геометрия и сказки А. С. Пушкина Повторительно, 36.32kb.
• Конспект урока математики в 3 классе по теме «Виды треугольников. День космонавтики», 79.5kb.
• Темы вашего учебного проекта Первый признак равенства треугольников, 65.14kb.
• Рабочая программа: Примерная тематика рефератов, творческих и научно-исследовательских, 51.5kb.
• Урок геометрии в 7 классе по теме: Применение признаков равенства треугольников к решению, 75.1kb.
• Календарно-тематический план по геометрии 7 класс, 63.91kb.

Алгоритмы отображение текстур в 3D конвейерах.

Данная лекция может содержать ошибки (как логические, так и грамматические). Авторы будут признательны за любые сообщения об ошибках, неточностях, а также за любые комментарии и дополнения, присланные по адресу Denis@fit.com.ru (Денису Иванову).

План лекции.

• Зачем нужны текстуры?
  
  • Пример линейной закраски треугольников. Недостатки (слишком много треугольников на геометрически простых поверхностях).
    
  • Понятие текстуры.
    
• Отображение текстуры на поверхность.
  
  • Модель, используемая во всех методах.
    
    • Битовая карта текселей. Координаты (s, t) (пиксели как точки).
      
    • 3х мерная система координат. Проекция на плоскость.
      
    • Экран. Координаты (p, q) (пиксели как квадраты).
      
  • Быстрый метод отображения текстур.
    
    • Проход по пикселям треугольника алгоритмом ScanLine.
      
    • Расчет вещественных координат пикселя на текстуре (как образа центра пикселя, рассматривая его как квадрат).
      
    • Методы выбора значения пикселя по вещественным координатам (s, t).
      
      • NEAREST
        
      • BILINEAR.
        
  • Искажения при отображении.
    
    • Пример.
      
    • Идеальная модель. (не применяют из-за сложности).
      
  • Mipmapping.
    
    • Построение mip уровней (оценка по памяти).
      
    • Методы расчета LOD.
      
    • Методы формирования значения текстуры.
      
      • NEAREST
        
      • LINEAR
        
      • TRILINEAR
        
  • Учет перспективы при отображении.
    
    • Пример.
      
    • Эффективная реализация алгоритма с учетом перспективы.
      

^

§1 Зачем нужны текстуры?

Любая система трехмерной графики стремится к идеалу – абсолютно реалистичному изображению. Одно из препятствий на пути к этому окраска окружающих нас предметов. Поверхности из таких материалов, как дерево, камень, ткань обладают богатой палитрой цветов и разнообразием узоров. Хорошая система трехмерной графики должна не только воспроизводить материал, из которого сделан предмет, но и быть быстрой, ведь поверхностей в трехмерной сцене, как правило, очень много. Алгоритмам решающим эту задачу и посвящена эта лекция.

Зам. Для простоты изложения будем считать, что все поверхности задаются наборами треугольников (а не более сложными фигурами).

В первых алгоритмах раскраски трехмерных фигур предлагалось закрашивать каждый треугольник поверхности исходя из заранее заданных значений цвета в его вершинах. Обычно цвет задается как линейная функция на плоскости, содержащей треугольник, с известными значениями в трех точках вершинах. Процесс вычисления линейной функции удобнее всего организовать так. Сперва мы задаем значение цвета на всех точках каждой стороны треугольника, как линейную функцию на отрезке с известными значениями на концах. Затем можно вычислить значение цвета для любой точки внутри треугольника, проведя через нее горизонтальный отрезок с концами на сторонах треугольника (значение цвета на сторонах нам уже известно) и повторив вычисление линейной функции внутри отрезка (см. описание алгоритма в §2.3 и Рис. 1).



^ Рис. 1 ( процесс закраски треугольника )


Этот способ обладает одним серьезным изъяном, цвет внутри треугольника плавно изменяется между его вершинами, а материалов с такой плавной окраской немного. Более реалистичную окраску поверхности можно показать, лишь добавляя к поверхности треугольники на каждый перепад цвета материала. Для плоских поверхностей, составляющих основу любой сцены, число треугольников может возрасти на несколько порядков. Большое количество треугольников, составляющих поверхности объектов, сильно замедляет скорость отображения сцены. В связи с этим был предложен метод раскраски, не требующий изменения геометрической структуры модели.

В нем предлагается хранить окраску предмета отдельно от модели в специальной битовой карте называемой текстурой. При отображении сцены карта «натягивается» на поверхность предмета, определяя цвет каждой ее точки. Такой подход позволяет разделить задание формы объекта и цветов его материала.
^

§2 Отображение текстуры на поверхность.

§2.1 Модель, используемая во всех методах.

Формализуем предшествующее не очень строгое описание текстуры. Текстура представляет собой цветную битовую карту изображения с собственной системой координат (s, t,) (см. Рис. 2а). Будем считать, что пиксели текстуры, обычно называемые текселями, являются точками-узлами с целочисленными координатами s и t.

Вся трехмерная сцена задана в системе координат OXYZ (см Рис. 2б). Мы рассматриваем сцену через плоский прямоугольный экран параллельный плоскости OXY. Стороны экрана параллельны осям OX и OY соответственно. Ось OZ пересекает центр экрана в точке z=1.

Поверхности в сцене задаются наборами треугольников. Для любой поверхности известны ее текстура и соответствие координат (s, t) на текстуре координатам (x, y, z) на поверхности. Внутри каждого отдельного треугольника эта зависимость линейна. (т.е. достаточно знать соответствие только для трех вершин каждого треугольника).

Сцена переносится на экран проективным преобразованием. Границы экрана задают область видимости (frustum) – прямоугольную призму с вершиной в точке O, проходящую через периметр экрана. Для того чтобы избежать опасности переполнения при делении на 0, верхушку этой призмы обычно «обрезают» на некотором расстоянии от точки O.



Рис. 2а Рис.2б

На экране задана ортогональная система координат (p, q) с осями параллельными сторонам экрана (см. Рис. 2в). Пикселями экрана будем считать квадраты между соседними четверками с целочисленными координатами p и q. Наша задача научится раскрашивать проекцию треугольника на экране, используя соответствие между поверхностью треугольника и текстурой.



Рис. 2в
^

§2.2 Быстрый метод отображения текстур.

Для упрощения изложения рассмотрим треугольник поверхности целиком лежащий внутри области видимости. Треугольник останется треугольником, и после проекции на экран, ведь отсечение за границами видимости отсутствует (частный случай преобразования треугольника в отрезок сложностей не вызывает). Обозначим пространственные координаты вершин треугольника как (x₁, y₁, z₁), (x₂, y₂, z₂), (x₃, y₃, z₃) соответственно, а координаты вершин проекции (p₁,q₁), (p₂, q₂), (p₃, q₃). Пусть тексели соответствующие вершинам на текстуре имеют координаты (s₁, p₁), (s₂, p₂),
(s₃, p₃). (см Рис. 3) Линейная зависимость координат (s, t) от координат (x, y, z) позволяет вычислять координаты текстуры на всей поверхности треугольника. В общем случае зависимость между координатами (p, q) и (x, y, z) нелинейна. Однако для небольших треугольников искажениями, вносимыми проективным преобразованием можно пренебречь и считать эту зависимость линейной. Это предположение позволяет построить простой и быстрый алгоритм наложения текстуры.



Рис. 3 ( процесс перебора строк сверху вниз, процесс вычисления координат (p,q,s,t) на границе строки по известным значениям на предыдущей строке)

^

Алгоритм быстрого наложения текстуры на треугольник.

Наши допущения делают зависимость между координатами (s, t) и (p, q) линейной. Поскольку мы задали координаты текстуры для трех точек – вершин треугольника, то линейное отображение из (p, q) в (s, t) задано полностью. Для того чтобы максимально эффективно организовать процесс вычисления рассмотрим следующий прием.

Пусть задан отрезок и на нем задана последовательность точек с постоянным шагом между соседними точками. Тогда разность значений линейной функции между соседними точками и одинакова для любого i. Если мы вычислением функцию f(x) на всех точках , то разумно организовать процесс ее вычисления следующим образом:

1. Вычислить .
   
2. На каждом последующем шаге (*).
   

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


Подготовительный этап (выполняется один раз для всего треугольника):

1. Вычисляем координаты (p_i , q_i) i = 1,2,3 проекции вершин треугольника на экран. Получим треугольник на экране.
   
2. Горизонтальная строка треугольника с координатой q задается своей левой и правой границей – p_l (q) и p_r (q) соответственно. Границы можно вычислить, подставив значение q в линейные уравнения сторон треугольника, следовательно, их зависимость от координаты q линейна. Согласно (*) вычисляем начальные значения границ, а также значение сдвига левой и сдвига правой границы при переходе на одну строку вниз.¹
   
3. По нашему предположению зависимость координат (s, t) от координат (p, q) линейна. Согласно (*) вычисляем начальные значения координат (s, t) на левой и правой границе треугольника, а также их приращения при переходе на одну строку вниз.
   

^ Перебираем горизонтальные строки треугольника сверху вниз с шагом 1. Для каждой строки выполняем следующие шаги (см. Рис. 3):

1. Используя значения границ предыдущей строки p_l (q-1), p_r (q-1) и вычисленные на подготовительном этапе сдвиги, вычисляем левую и правую границы строки p_l (q) и p_r (q).
   
2. Аналогично вычисляем вещественные координаты текстуры для левой и правой границы строки.
   
3. Перебираем внутренние точки строки, вычисляя соответствующие им вещественные координаты текстуры (s, t). Зависимость координат (s, t) от координат (p, q) линейна, начальное значение и величину приращения можно найти исходя из имеющейся информации на границах отрезка. Процесс вычисления полностью аналогичен процессу описанному в (*).
   
4. Зная вещественные координаты (s, t) на текстуре, выбираем значение пикселя
   (p, q) c помощью дополнительной процедуры.
   

Последний пункт алгоритма нуждается в пояснении. Тексели на карте текстуры имеют только целые координаты. Координаты (s, t) вещественны и прямо никакому текселю не соответствуют. Поэтому нужно преобразовать вещественные координаты (s, t) в значение цвета экранного пикселя. Простейший подход заключается в том, чтобы взять значение из ближайшего текселя на текстуре, округлив координаты (s, t) (такой метод называется NEAREST). Недостатком такого подхода являются четко выраженные границы между цветами хорошо заметные на близком расстоянии, когда нескольким экранным пикселям соответствует один тексель на текстуре. Более реалистичный метод BILINEAR вычисляет значение экранного пикселя как билинейную функцию от четырех текселей текстуры окружающих точку (s, t). Такой подход позволяет достичь плавного изменения цвета даже на близком расстоянии.
^

§2.3 Искажения при отображении. Пример

Как ни странно проще получить хорошее изображение текстуры вблизи поверхности, чем вдали от нее. При большом расстоянии до объекта в один пиксель экрана попадает сразу несколько текселей текстуры. Алгоритм учитывает только один из них (или 4 в случае использования BILINEAR), игнорируя значения остальных. Такая произвольная выборка значений из текстуры приводит к непредсказуемому искажению внешнего вида.

Конечно, можно попытаться учесть все тексели текстуры, попадающие в квадрат пикселя на экране. Для того чтобы найти эти тексели, необходимо вычислить образ квадрата экранного пикселя в координатах (s, t) и найти в получившемся произвольном четырехугольнике точки с целочисленными координатами (см. Рис. 4). Эту дорогостоящую процедуру надо повторить для каждого пикселя на экране. Временные затраты делают такой подход неприемлемым для большинства трехмерных приложений.



Рис. 4 ( квадрат пикселя в координатах (p, q) и его образ в координатах (s, t). В образе выделены целочисленные точки.)

^

§2.4 Mipmapping

Алгоритм mipmapping’а предназначен для быстрого решения этой проблемы, за счет потери доли реалистичности. При mipmapping’е в памяти хранится целый набор текстур отвечающих различным уровням детализации изображения. Уровень детализации обозначается аббревиатурой LOD (Level Of Details).
^

Построение mip уровней (оценка по памяти)

Исходная текстура соответствует уровню детализации 0. Разобьем карту уровня 0 на блоки текселей размера 2x2. Сожмем каждый блок в один единственный тексель и запишем получившуюся сжатую карту в уровень LOD 1. Теперь разобьем на блоки карту уровня 1. Повторяя процедуру сжатия, получим по очереди уровни LOD = 2,3,4,.. (см. Рис. 5).



Рис. 5 ( процедура получения следующего уровня LOD.)

Каждый последующий уровень в четыре раз меньше предыдущего. Легко посчитать занимаемую всеми уровнями память. Если размер памяти исходной текстуры взять за 1, то уровень LOD n потребует памяти размера . Все вместе уровни занимают , т.е. дополнительные расходы памяти не превосходят 34%.
^

Методы расчета LOD

При наложении текстуры методом mipmapping’а первая задача – определить подходящий уровень детализации. Уровень LOD должен быть таким, чтобы размер образа экранного пикселя на текстуре и размер текселя текстуры были максимально близки. Размер текселя заданного уровня LOD вычислить просто. Но как найти размер образа экранного пикселя на текстуре?

Рассмотрим пиксель как квадрат. Его образ в координатах (s, t) произвольный четырехугольник. Понятно, что изменение координаты s вдоль образа горизонтальной стороны пикселя приблизительно равно

поскольку горизонтальный размер пикселя равен 1.

Аналогично изменение координаты t вдоль образа горизонтальной стороны пикселя приблизительно равно . Заменив в формулах p на q легко получить соотношения и для вертикальной стороны пикселя. Производные обычно приближаются конечными разностями значений на сторонах пикселей (или соседних пикселей).

Пользуясь этой аппроксимацией, можно построить следующие приблизительные оценки размера пикселя.

• – дает слегка размытое изображение.
  
• – изображение резкое, контрастное.
  
• .
  

Разумно сочетая все три оценки можно добиться хорошего качества изображения. Подсчет этих производных и координат (s, t) в каждом пикселе производится также как и в алгоритме быстрого отображения.

^

Методы формирования значения текстуры

Получившиеся значения LOD и координат (s, t) вещественны. Возникает проблема выбора значения цвета аналогичная пункту 6 алгоритма предыдущего параграфа. Существует три метода выбора цвета пикселя:

1. ^ Nearest (см Рис. 5).
   

Округляем LOD до ближайшего уровня.

Округляем координаты (s, t) до ближайшего текселя.

2. Linear (см. Рис. 5).
   

Рассматриваем уровни детализации [LOD] и [LOD+1].

На каждом из них рассчитываем цвет точки (s, t) округляя до ближайшего текселя.

Результирующий цвет рассчитываем, как линейную функцию между уровнями исходя из вещественного уровня LOD.

3. ^ Trilinear (см. Рис. 5).
   

Похож на Linear, но значения цвета на обоих уровнях, рассчитываем по методу Bilinear предыдущего параграфа.


Метод Trilinear позволяет достичь плавного изменения вида объекта, как при изменениях масштаба, так и при перемещении вдоль поверхности предмета. К сожалению, современной аппаратуре недостает мощности, чтобы реализовать его в реальном времени.
^

§2.5 Учет перспективы при отображении. Пример

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

Рассмотрим в качестве примера кусочек шахматной доски (см. Рис. 6а). Разделим ее по диагонали на два больших треугольника и зададим рисунок шахматных клеток текстурой размером со всю доску. Линейное отображение сохраняет соотношение длин отрезков находящихся на одной прямой, поэтому высота всех клеток в одном столбце проекции шахматной доски на Рис. 6б одинакова. В изображении на Рис. 6б не учтен эффект перспективы – объект находящийся дальше должен выглядеть меньше. Правильное изображение показано на Рис. 6в. Таким образом, возникает необходимость в процедуре наложения текстуры, учитывающей эффект перспективы.



Рис. 6а Рис. 6б Рис. 6в
^

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

Конечно, для каждого пикселя экранной проекции можно вычислить трехмерные координаты прообраза пикселя на поверхности треугольника, а по ним рассчитать координаты на текстуре. Обращение перспективного преобразования требует умножения на матрицу размера 4х4 для каждого пикселя проекции. Аппаратная реализация мультипликативных операций требует большого числа транзисторов, их скорость часто является «бутылочным горлышком» в общей производительности системы. Попытаемся уменьшить число мультипликативных операций при вычислении обратного перспективного преобразования.

Вспомним прием (*), который мы использовали в реализации алгоритма быстрого наложения текстуры. Для последовательности точек из отрезка значение линейной функции в любой из них вычислялось индуктивно, на базе значения функции в предыдущей точке. Попробуем реализовать похожий подход для обратного перспективного преобразования.

Выбросим на время из модели ось OY трехмерной системы координат и ось q экрана, для рассмотрения эффекта перспективы это не существенно (см. Рис. 7). Пусть мы движемся вдоль заданного на экране отрезка [p₁,p₂]. Прообраз отрезка [p₁,p₂] – отрезок [P₁,P₂] в пространстве координаты концов которого (x₁, z₁), (x₂, z₂) нам известны.

Восстановим по точке ее прообраз P с координатами .



Рис. 7 ( систему координат OXZ, отрезок [P1,P2], проекцию на экран - отрезок [p1,p2], точку P и ее проекцию p )


Напишем уравнение прямой содержащей отрезок [P1,P2]: Ax+Bz+C=0.

При проективном преобразовании экранная координата p вычисляется как , откуда .

Подставляя выражение для x в уравнение отрезка [P1,P2] получим , или .

Выразим из этого соотношения , .

Введем вспомогательную величину .

Для нее , а , что позволяет выразить просто, как .

Воспользовавшись последним соотношением, найдем координаты точки : (**).

Зам Если бы мы не исключили из модели оси OY и q, то к системе (**) добавилось бы уравнение (***).


Пользуясь соотношениями (**) и (***) можно реализовать эффект перспективы в алгоритме быстрого наложения текстуры. Храня величину вместо z мы сэкономим по одному делению на каждом шаге алгоритма.