теория, алгоритмы, примеры на С++ и OpenGL  
    2D теория 3D теория OpenGL        Обратная связь / Авторам

Мы vkontakte.ru


Rambler's Top100 Rambler's Top100
Каталог@Mail.ru - каталог ресурсов интернет

Друзья

Словарь синонимов русского языка

Растеризация треугольника. Алгоритм заливки (заполнения)

Одним из важнейших алгоритмов растеризации является алгоритм растеризации треугольника (заполнения треугольника), т.к. в большинстве моделей построения трехмерных объектов последние состоят именно из треугольников.

Прим. В некоторых статьях этот алгоритм называется алгоритм рисования треугольника.

Схематично алгоритм можно описать следующим образом:

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

Заполнение треугольника

  1. Каждый из двух полученных треугольников растеризуется по отдельности.
  2. В процессе растеризации обе стороны растеризуются параллельно, таким образом, чтобы координаты по оси y текущих точек на обоих отрезках совпадали. При этом связность растеризуемых линий (сторон треугольника) не обеспечивается:

Растеризация треугольника

  1. При получении координат текущих точек горизонтальный отрезок между ними заполняется.

При растеризации отрезков сторон используется один из алгоритмов рассмотренных ранее. Т.к. связность отрезков не обеспечивается в силу того, что единичное приращение всегда идет по оси y, будем использовать алгоритм DDA-линии с фиксированной точкой.

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

#include <windows.h>
#include "math.h"
#include "fixed.h"
 
#define roundf(x) floor(x + 0.5f)
 
inline void swap(int &a, int &b)
{
      int t;
      t = a;
      a = b;
      b = t;
}
 

 

 Вспомогательные функции.

 
void triangle(HDC hdc, int x1, int y1, int x2, int y2, int x3, int y3)
{
 

В функцию растеризации передаются три вершины треугольника и дескриптор контекста устройства*.

 
      // Упорядочиваем точки p1(x1, y1),
      // p2(x2, y2), p3(x3, y3)
      if (y2 < y1) {
            swap(y1, y2);
            swap(x1, x2);
      } // точки p1, p2 упорядочены
      if (y3 < y1) {
            swap(y1, y3);
            swap(x1, x3);
      } // точки p1, p3 упорядочены
      // теперь p1 самая верхняя
      // осталось упорядочить p2 и p3
      if (y2 > y3) {
            swap(y2, y3);
            swap(x2, x3);
      }
 

 

 Точки, переданные в качестве параметров в функцию, упорядочиваются по не убыванию ординаты.

 
      // приращения по оси x для трёх сторон
      // треугольника
      fixed dx13 = 0, dx12 = 0, dx23 = 0;
 
      // вычисляем приращения
      // в случае, если ординаты двух точек
      // совпадают, приращения
      // полагаются равными нулю
      if (y3 != y1) {
            dx13 = int_to_fixed(x3 - x1);
            dx13 /= y3 - y1;
      }
      else
      {
            dx13 = 0;
      }
 
      if (y2 != y1) {
            dx12 = int_to_fixed(x2 - x1);
            dx12 /= (y2 - y1);
      }
      else
      {
            dx12 = 0;
      }
 
      if (y3 != y2) {
            dx23 = int_to_fixed(x3 - x2);
            dx23 /= (y3 - y2);
      }
      else
      {
            dx23 = 0;
      }
     

 

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

 
      // "рабочие точки"
      // изначально они находятся в верхней точке
      fixed wx1 = int_to_fixed(x1);
      fixed wx2 = wx1;
 

 

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

 
      // сохраняем приращение dx13 в другой переменной
      int _dx13 = dx13;
 
      // упорядочиваем приращения таким образом, чтобы
      // в процессе работы алгоритмы
      // точка wx1 была всегда левее wx2
      if (dx13 > dx12)
      {
            swap(dx13, dx12);
      }
 

 

 Упорядочиваем приращения таким образом, чтобы в процессе работы алгоритмы точка wx1 была всегда левее wx2. При этом приращение dx13 может быть потеряно, оно заранее сохраняется в переменной _dx13.

 
 

 
      // растеризуем верхний полутреугольник
      for (int i = y1; i < y2; i++){
            // рисуем горизонтальную линию между рабочими
             // точками
            for (int j = fixed_to_int(wx1); j <= fixed_to_int(wx2); j++){
                  SetPixel(hdc, j, i, 0);
            }
            wx1 += dx13;
            wx2 += dx12;
      }
 
     

 

 Растеризуется верхний полутреугольник. Цикл идет по координате y. При этом переменные wx1 и wx2 изменяются параллельно, на каждом шаге цикла.

Важно! Обратите внимание на граничные условия цикла. Средняя точка с ординатой y2 здесь не рисуется. При у1 = y2 (отсутствует верхний полутреугольник) на этом шаге ничего выведено не будет.

 
      // вырожденный случай, когда верхнего полутреугольника нет
      // надо разнести рабочие точки по оси x, т.к. изначально они совпадают
      if (y1 == y2){
            wx1 = int_to_fixed(x1);
            wx2 = int_to_fixed(x2);
      }
 

 

 В случае, когда y1 = y2, приходится вручную переносить рабочие точки для растеризации нижнего полутреугольника.

 
      // упорядочиваем приращения
      // (используем сохраненное приращение)
      if (_dx13 < dx23)
      {
            swap(_dx13, dx23);
      }
     
Упорядочиваем приращения таким образом, чтобы в процессе работы алгоритмы точка wx1 была всегда левее wx2. При этом используется сохраненное приращение _dx13.

 
 

 
      // растеризуем нижний полутреугольник
      for (int i = y2; i <= y3; i++){
            // рисуем горизонтальную линию между рабочими
            // точками
            for (int j = fixed_to_int(wx1); j <= fixed_to_int(wx2); j++){
                  SetPixel(hdc, j, i, 0);
            }
            wx1 += _dx13;
            wx2 += dx23;
      }
}

 

 Растеризуется нижний полутреугольник. При этом, в случае когда треугольник вырожденный (y1 = y2 = y3), он будет выведен на этом шаге.

 
 
Прим. * В следующей статье будет рассказано, как выводить изображение в память.
            ** Если внимательно проанализировать алгоритм, становится видно, что в вырожденных случаях, при y1 = y2, y2 = y3 или y1 = y3 на соответствующих шагах алгоритма приращения dx12, dx23 или dx13 использованы не будут. Поэтому их можно не приравнивать нулю в этих случаях:

if (y3 != y1) {
            dx13 = int_to_fixed(x3 - x1);
            dx13 /= y3 - y1;
      }
      else

{

dx13 = 0;

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

Слабым местом в приведенной реализации является вывод пикселей на экран. Использование функции SetPixel в данном случае крайне неразумно. Вывод в память на порядок увеличит скорость работы приложения и избавит от необходимости реализовывать двойную буферизацию через теневой контекст устройства.

Скачать исходные тексты демонстрационных программ (в программе, при нажатии на любую клавишу, можно посмотреть, как отрисует тот же треугольник стандартная WinAPI функция)