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

Picaso.jpg

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

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

То есть, пусть имеется некий набор граней (т.е. сцена), который требуется нарисовать. Отсортируем грани по удаленности от камеры и отрисуем все грани, начиная с самых удаленных. Довольно распространенная характеристика удаленности для грани ABC - это среднее значение z, mid_z = (A.z+B.z+C.z)/3. Вот и весь алгоритм. Просто, и обычно достаточно быстро.

Реализация алгоритма художника приведена ниже. Реализация выполнена в Borland C++ 3.1

//Подключение необходимых библиотек
#include <math.h>
#include <iostream.h>
#include <conio.h>
#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
 
#define NUMBERVERTEX 15 //Количество вершин
#define NUMBERTRIANGLE 16 //Количество треугольников
 
 
//Структура вершины
struct Vertex {
 
    double x;
    double y;
    double z;
 
}
    masVertex[NUMBERVERTEX]; //Массив вершин
 
//Структура треугольника
struct Triangle {
 
    int A;
    int B;
    int C;
 
}
    masTriangle[NUMBERTRIANGLE]; //Массив треугольников
 
    double sortMasTriangle[NUMBERTRIANGLE]; //Массив для хранение значений отдаленности граней
 
//Инициализация вершин
void InitVertex () {
 
     masVertex[0].x = 0;           masVertex[8].x = 0;
     masVertex[0].y = 0;           masVertex[8].y = 6;
     masVertex[0].z = -11;         masVertex[8].z = -6;
 
     masVertex[1].x = 20;          masVertex[9].x = 6;
     masVertex[1].y = 0;           masVertex[9].y = 6;
     masVertex[1].z = -8;          masVertex[9].z = -6;
 
     masVertex[2].x = 0;           masVertex[10].x = 6;
     masVertex[2].y = 0;           masVertex[10].y = 6;
     masVertex[2].z = -9;          masVertex[10].z = 0;
 
     masVertex[3].x = 0;           masVertex[11].x = 0;
     masVertex[3].y = 5;           masVertex[11].y = 6;
     masVertex[3].z = -9;          masVertex[11].z = 0;
 
     masVertex[4].x = 0;           masVertex[12].x = 0;
     masVertex[4].y = 0;           masVertex[12].y = 0;
     masVertex[4].z = -6;          masVertex[12].z = -15;
 
     masVertex[5].x = 6;           masVertex[13].x = 15;
     masVertex[5].y = 0;           masVertex[13].y = 0;
     masVertex[5].z = -6;          masVertex[13].z = 0;
 
     masVertex[6].x = 6;           masVertex[14].x = 0;
     masVertex[6].y = 0;           masVertex[14].y = 15;
     masVertex[6].z = 0;           masVertex[14].z = 0;
 
     masVertex[7].x = 0;
     masVertex[7].y = 0;
     masVertex[7].z = 0;
 
}
 
//Инициализация треуголиников
void InitTriangle () {
 
   masTriangle[0].A = 1;           masTriangle[8].A = 8;
   masTriangle[0].B = 3;           masTriangle[8].B = 9;
   masTriangle[0].C = 0;           masTriangle[8].C = 10;
 
   masTriangle[1].A = 1;           masTriangle[9].A = 8;
   masTriangle[1].B = 2;           masTriangle[9].B = 10;
   masTriangle[1].C = 3;           masTriangle[9].C = 11;
 
   masTriangle[2].A = 2;           masTriangle[10].A = 6;
   masTriangle[2].B = 0;           masTriangle[10].B = 7;
   masTriangle[2].C = 3;           masTriangle[10].C = 10;
 
   masTriangle[3].A = 0;           masTriangle[11].A = 10;
   masTriangle[3].B = 2;           masTriangle[11].B = 7;
   masTriangle[3].C = 1;           masTriangle[11].C = 11;
 
   masTriangle[4].A = 4;           masTriangle[12].A = 7;
   masTriangle[4].B = 5;           masTriangle[12].B = 4;
   masTriangle[4].C = 8;           masTriangle[12].C = 8;
 
   masTriangle[5].A = 8;           masTriangle[13].A = 7;
   masTriangle[5].B = 5;           masTriangle[13].B = 8;
   masTriangle[5].C = 9;           masTriangle[13].C = 11;
 
   masTriangle[6].A = 5;           masTriangle[14].A = 6;
   masTriangle[6].B = 6;           masTriangle[14].B = 5;
   masTriangle[6].C = 9;           masTriangle[14].C = 4;
 
   masTriangle[7].A = 9;           masTriangle[15].A = 6;
   masTriangle[7].B = 6;           masTriangle[15].B = 4;
   masTriangle[7].C = 10;          masTriangle[15].C = 7;
 
}
 
//Отрисовка сцены
void ShowObject (int COLOR, int Pattern) {
 
  int Sxmin = 0, 
      Sxmax = 639,
      Symin = 0,
      Symax = 479;
  double xmin = -9,
	 xmax = 9,
	 ymin = -9,
	 ymax = 9;
 
	 double mx = (Sxmax - Sxmin)/(xmax - xmin);
	 double my = (Symax - Symin)/(ymax - ymin);
	 double min;
	 double X,Y,X1,Y1,X2,Y2;
 
	 if (mx > my) min = my;
	 else min = mx;
 
           //Задаем стиль отрисовки сцены
	   setfillstyle(Pattern,COLOR);
	   setcolor(MAGENTA);
	   int Tria[6];
 
       //Отрисовка сцены
       for (int i=0; i<NUMBERTRIANGLE; i++) {
 
	X = masVertex[masTriangle[i].A].x + masVertex[masTriangle[i].A].z/sqrt(2);
	Y = masVertex[masTriangle[i].A].y + masVertex[masTriangle[i].A].z/sqrt(2);
	Tria[0] = Sxmin + min*(X - xmin);
	Tria[1] = Symax - min*(Y - ymin);
 
	X1 = masVertex[masTriangle[i].B].x + masVertex[masTriangle[i].B].z/sqrt(2);
	Y1 = masVertex[masTriangle[i].B].y + masVertex[masTriangle[i].B].z/sqrt(2);
	Tria[2] = Sxmin + min*(X1 - xmin);
	Tria[3] = Symax - min*(Y1 - ymin);
 
	X2 = masVertex[masTriangle[i].C].x + masVertex[masTriangle[i].C].z/sqrt(2);
	Y2 = masVertex[masTriangle[i].C].y + masVertex[masTriangle[i].C].z/sqrt(2);
	Tria[4] = Sxmin + min*(X2 - xmin);
	Tria[5] = Symax - min*(Y2 - ymin);
 
	fillpoly(3,Tria);
 
       }
 
}
 
//Сортировка граней по удаленности от камеры
void SortTriangle () {
 
       //Нахождение средней величины Z - удаленности грани
       for (int i=0; i<NUMBERTRIANGLE; i++) {
 
	 sortMasTriangle[i] = (masVertex[masTriangle[i].A].z +
			       masVertex[masTriangle[i].B].z +
			       masVertex[masTriangle[i].C].z)/3;
       }
 
    Triangle temp;
    int j;
    double TEMP;
 
  //Непосредственная сортировка граней по удаленности
  for (i=0; i<NUMBERTRIANGLE-1; i++)
 
    for (j=0; j<NUMBERTRIANGLE-1; j++)
 
    if (sortMasTriangle[j] <= sortMasTriangle[j+1]) {
 
     TEMP = sortMasTriangle[j];
     sortMasTriangle[j] = sortMasTriangle[j+1];
     sortMasTriangle[j+1] = TEMP;
 
     temp = masTriangle[j];
     masTriangle[j] = masTriangle[j+1];
     masTriangle[j+1] = temp;
 
    }
 
}
 
//Инициализация графики
void InitGraph () {
  int gdriver = DETECT, gmode, errorcode;
  initgraph(&gdriver, &gmode, "");
}
 
 
int main () {
 
    InitGraph (); //Инициализация графики
    InitVertex ();//Инициализация вершин
    InitTriangle (); //Инициализация треугольников
    ShowObject (WHITE,9); //Отрисовка сцены
    SortTriangle (); //Сортировка граней по удаленности от камеры
    getch();
    ShowObject (WHITE,9); //Отрисовка сцены
 
      getch();
      return 0;
 
}

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