3D 게임 의 장면 관리 (팔자 수 트 리 와 BSP 트 리 소개)

21756 단어 데이터 구조 게임.tree null System Class

어떻게 수천 수만 의 물 체 를 포함 하 는 복잡 한 장면 을 잘 나 타 낼 수 있 는 지 는 디자인 시스템 이 반드시 고려 해 야 할 것 이다.이것 도 장면 관리 가 해 야 할 일이 고 장면 에 좋 은 차원 관 계 를 제공 하여 선별 (Culling) 과 숨겨 진 면 제거 (Hidden surface remove) 를 잘 할 수 있 도록 해 야 한다.장면 관 리 는 시각 적 처리 (Visibility processing) 와 충돌 검 측 (Collision detection) 과 관련 되 고 시스템 은 장면 의 어떤 부분 이 시각 적 제약 체 안에 있 는 지 판단 해 야 한다. 또한 두 물체 가 충돌 관계 가 있 으 면 충돌 점 의 값 을 계산 해 야 한다.
가시 성 제거
게임 의 실시 간 효 과 를 얻 기 위해 전통 적 인 기술 은 적용 할 수 없다. 왜냐하면 장면 이 매우 복잡 하기 때문에 Z 버퍼 링 방법 으로 만 가시 적 으로 처리 하면 비 현실 적 이다.현재 이미 장면 을 층 으로 나 누 는 방법 이 있어 보조 데이터 구 조 를 장면 에 응용 할 수 있다. 먼저 장면 을 구역 으로 나 눈 다음 에 물 체 를 나 누고 심지어 다각형 까지 나 눌 수 있다.예 를 들 어 실내 장면 관리 에 자주 사용 되 는 두 가지 차원 체계 가 있다. BSP (Binary Space Partitioning) 나 무 는 팔자 수 트 리 의 홍보 와 포위 체 트 리 (Boundingvolume tree) 이다.전 자 는 제 거 를 가속 화 하 는 데 쓰 이 고 후 자 는 주로 충돌 검 측 에 쓰 인 다.
이 절 은 차원 체 계 를 어떻게 사용 하여 더욱 효율 적 인 선별 을 하고 어떤 데이터 구 조 를 이용 하여 장면 을 조직 할 수 있 는 지 간단하게 토론 한다.
1.2 장면 의 조직 과 관리
장면 의 조직 구 조 는 렌 더 링 시스템 의 가장 기본 적 이 고 가장 중요 한 부분 이자 실현 의 난점 이다.그것 의 결정 은 충돌 검사, 은폐, 그림자 등 후속 작업 을 많이 결정 할 것 이다.
먼저 언급 해 야 할 개념 은 공간 세분 화 이 고 공간 세분 화 는 전체 물체 공간 을 고려 하 며 물체 의 공간 점유 (Object occupancy) 에 따라 공간 중의 모든 점 을 분류 하 는 것 이다.세계 공간 속 의 물 체 를 입방체 소 (voxel) 로 세분 화하 여 체 소 를 분류 할 수 있다.팔자 수 트 리 (octree) 는 3 차원 공간 을 묘사 한 트 리 데이터 구조 로 3 차원 장면 에서 물체 의 분포 상황 을 묘사 하고 체 소 를 차원 구조 에 간단하게 배치 할 수 있다.
따라서 장면 관 리 는 미리 처리 할 때 나 무 를 만 들 수 있다. 여기 서 물체 의 표현 방법 을 무시 하고 장면 의 구분 에 초점 을 맞 출 수 있다.나무 가 세 워 진 후에 이 나 무 를 실시 간 으로 옮 겨 다 니 며 두 물체 가 같은 공간 을 차지 하여 충돌 이 발생 했 는 지, 아니면 한 물체 의 공간 이 제약 체 안에 있 지 않 았 는 지 를 발견 한다.이렇게 하면 모든 선별 등 작업 을 트 리 에 대한 옮 겨 다 니 는 것 으로 간소화 할 수 있 습 니 다. 이것 은 선형 시간의 작업 입 니 다.
다른 하 나 는 장면 을 나타 내 는 데이터 구 조 는 BSP 나무 로 실내 장면 의 처리 에 광범 위 하 게 응용 된다. 이 는 하나의 분리 면 (splitting plane) 을 사용 하여 각 층 을 2 로 나 누 어 공간 에 대한 구분 을 실현 한다. 그 중에서 분할 에 사용 되 는 평면 은 그 어떠한 방향 에 도 나타 날 수 있다.BSP 의 아 이 디 어 는 최초 로 Fuchs (1980) 에서 제 기 됐 으 며, 처음에는 숨 은 면 을 실시 간 으로 없 애 는 것 이 목적 이 었 다.BSP 는 팔자 수 트 리 의 일반화 라 고 할 수 있다.이전 사람들 은 이 방면 에서 이미 많은 효과 적 인 작업 을 했다. Fuchs 는 처음으로 BSP 기술 에서 평면 을 나 누 는 정 측 성질 을 다각형 장면 의 분할 에 응용 하여 공간 이 진 트 리 구 조 를 구축 했다. 이 이 이 진 트 리 의 모든 결점 은 하나의 서브 공간 과 공간 에 포 함 된 다각형 을 나타 낸다.모든 결점 공간 에서 그 중의 한 평면 을 분할 평면 으로 선택 하고 이 공간 을 계속 양음 두 자 공간 으로 나 누 어 각각 이 결점 의 두 자 결점 으로 한다. 그 중에서 분할 평면 과 교차 하 는 다각형 은 두 개의 다각형 으로 나 누 어 각각 해당 하 는 자 공 간 에 들어간다.이 과정 은 모든 하위 공간 이 하나의 다각형 만 포함 할 때 까지 재 귀 과정 이다.
팔자 수 트 리 분할 에 비해 BSP 트 리 는 메모리 소모 가 적 고 분할 방식 이 유연 하 며 발생 하 는 무효 구역 이 비교적 작은 장점 을 가진다.또한 대부분의 장면 에서 BSP 트 리 는 팔자 수 트 리 보다 균형 이 잡 힌 다.
또 2 분 의 공간 인 만큼 방향 성 이 강해 팔자 수 트 리 보다 판단 이 쉬 워 Z - Buffer 대신 가 림 막 문 제 를 해결 할 수도 있 고, BSP 는 물체 의 그리 기 순 서 를 정할 수 있 기 때문에 이 순서에 따라 Z - Buffer 없 이도 정확 함 을 보 여줄 수 있 고 충돌 검 사 를 편리 하 게 수행 할 수 있다.
1
、BSP Tree
（
Binary space partitioning
）
의 원리
먼저 전체 장면 을 AABB (아웃 소 싱 박스) 에 둘러싸 고 재 귀 형식 으로 그 밖 에 가방 을 작은 상자 로 나 누 었 다.보통 상자 의 한 축 을 선택 하여 수직 평면 을 만 들 고 이 를 두 개의 작은 상자 로 나눈다.일반적으로 상 자 를 완전히 같은 두 부분 으로 나눈다.평면 과 교차 하 는 물 체 를 분할 하거나 이 차원 에 저장 하여 두 개의 집중 의 일원 이 된다.이 평면 에 의 해 두 개의 다른 물체 로 분할 된다.이 평면 분할 과정 을 반복 하면 모든 AABB 를 특정한 기준 을 만족 시 킬 때 까지 재 귀적 으로 세분 화 할 수 있다.일반적으로 이 기준 은 사용자 가 정의 하 는 나무의 최대 깊이 또는 상자 안에 포 함 된 집합 그림 의 수량 이 사용자 가 정의 하 는 특정한 값 보다 낮 거나 잎 노드 에 도달 하 는 것 입 니 다 (모든 노드 는 돌출 패키지 –
최소 볼록 다각형
）。
쉽게 말 하면 이런 사상 은 평면 으로 장면 을 나 누 는 것 이다.장면 속 에는 많은 물체 가 있 을 것 이다. 우 리 는 모든 물체 의 모든 것 으로
Polygon
하나의 평면 이 라 고 생각 하고 모든 평면 에 찬 반 두 개의 면 이 있 으 면 장면 을 두 부분 으로 나 눌 수 있다. 먼저 첫 번 째 평면 부터 나 눈 다음 에 이 분 리 된 두 부분 을 각각 같은 방식 으로 세분 화 할 수 있다. 이렇게 진행 하면 장면 을 두 갈래 나 무 를 구성 할 수 있다.
이 사상 을 2 차원 평면 으로 간소화 하면
아래 그림 에서 보 듯 이
3 차원 장면 에서 의 구축 방식 은 이와 유사 하 다.
(비고: 이 그림 은 en. wikipedia. org 에서 가 져 온 것 입 니 다)
1
, A 는 나무의 뿌리 노드 이자 전체 다각형 면
2
, A 는 B 와 C 로 나 뉜 다.
3
, B 는 D 와 E 로 나 뉜 다.
4
, D 는 F 와 G 로 나 뉘 는데 그 중에서 G 는 볼록 가방 (
최소 볼록 다각형
) 이 로 인해 이 나무의 잎 사 귀 노드 가 되 어 더 이상 나 눌 수 없다.
2. BSP Tree 의 저장 구조
본 례 중
BSP Tree
저장 구조
+2
) 필드 의 기록 은 나무의 모든 결점 을 나타 낸다.그 중 몇몇 필드 는 이 결점 의 특성 을 묘사 하 는 데 쓰 인 다
(
이 예 에서 의 특성 은 노드 의 값 과 노드 좌표 이다.
)
나머지
2
저장 소 가 가리 키 는 필드
2
자결 점 의 지침.
3
이루다
BSP Tree
몇 가지 핵심 기술 및 캡 처
A. 메 인 화면:
Main
함수 에서 사용
while(true)
Trinity 엔진 과 같은 렌 더 링 순환 효 과 를 내 고 사용자 의 입력 을 기다 리 고 있 습 니 다.IF 를 통 해 사용자 의 입력 을 판단 하고 해당 하 는 조작 을 합 니 다.
[Copy to clipboard] [-]
View CodeCPP

cin>>choiced;
while(true)
{
        if(choiced == 0)
   return 0;
        else if(choiced == 1)
        {
             …………
        }
 …………
}

B
만들다
BSP Tree
인터페이스, 사용자 가 재 귀 횟수 와 아웃 소 싱 박스 가 3 차원 장면 에서 의 좌 표를 입력 해 야 합 니 다.
이 예 는 3 층 깊이 를 사용 하고 아웃 소 싱 박스 좌 표 는 (1, 100, 1, 100, 1, 100) 이다.
[Copy to clipboard] [-]
View CodeCPP

//  BSP    
struct BSPTreeNode
{
    T data; //    
 T xmin,xmax; //    ，          
 T ymin,ymax;
 T zmin,zmax;
    BSPTreeNode <T> *left,*right; //        ,           
}
//  BSP 
int scale = -1;  
//         ，                  X      ，  Y   Z  
template <class T>
void createBSPTree(BSPTreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
 maxdepth=maxdepth-1; //             -1
 scale++; //             +1，             
 if(3==scale) scale=0; //          ，    
 if(maxdepth>=0)
 {
  root=new BSPTreeNode<T>();
  root->xmin=xmin; //       
…………
  double xm=(xmax-xmin)/2;
  double ym=(ymax-ymin)/2;
  double zm=(zmax-zmin)/2; //    3        
  //      。
  if(0==scale) //     0，  X        
  {
//                    
   createBSPTree(root->left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);
   createBSPTree(root->right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);
  }
  else if(1==scale) //     1，  Y        
…………
  else if(2==scale) //     2，  Z        
…………
 }
}

이상 의 방식 으로 현재 노드 를 순환 절단 하여 BSP 트 리 를 만 듭 니 다. 절단 면 의 순 서 는 다음 과 같 습 니 다.
(a)
X 축 과 수직 으로 평면 절단
(b)
Y 축 과 수직 으로 평면 절단
(c)
Z 축 과 수직 으로 평면 절단
순차 순환
C
, 생 성 성공 후 이 순 서 를 옮 겨 다 니 기
BSP Tree
。
[Copy to clipboard] [-]
View CodeCPP

int i=1;
template <class T>
void preOrder( BSPTreeNode<T> * & p)
{
    if(p)
    {
  cout<<i<<".       ："<<p->data<<"/n   ：";
  cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
…………
  i+=1;
        preOrder(p->left);
        preOrder(p->right);
    }
}

총 7 개의 노드.
D
이 나무의 깊이 보기
왼쪽 노드 의 개 수 를 찾 는 것 입 니 다.
[Copy to clipboard] [-]
View CodeCPP

template<class T>
int depth(BSPTreeNode<T> *& p)
{
    if(p == NULL)  return -1;
    int h = depth(p->left);
    return h+1;
}

4. BSP Tree 와 Octree 의 비교
a) BSP 트 리 는 1 개의 면 분할 장면 을 사용 하고, Octree 는 3 개의 면 분할 을 사용한다.
b) BSP Tree 는 노드 당 2 개의 점 이 있 고, Octree 는 8 개의 점 이 있다.
따라서 BSP Tree 는 몇 차원 이 든 장면 에 사용 할 수 있 고 문제 가 없 으 며 Octree 는 3 차원 장면 (N 차원 으로 확대 하면 매우 복잡 하 다) 에 자주 사용 된다.

/*
Author   :   
Date  : 2008/05/01
Filename : bsptree.cpp
Platform : VC++ 2005
BSP    
  ：
1、  BSP 。
    BSP    ，     /      。
           BSP                。
    a：           ，                ，     。
    b：     (1)         -(2)         -(1)-(2)……
2、    BSP 。
   BSP                  BSP ，          ，         。
3、  BSP    。
*/
#include <iostream>
using namespace std;
//  BSP    
template<class T>
struct BSPTreeNode
{
 T data; //    
 T xmin,xmax; //    ，          
 T ymin,ymax;
 T zmin,zmax;
 BSPTreeNode <T> *left,*right;  //        ,           
 BSPTreeNode //   
 (T nodeValue = T(),
 T xminValue = T(),T xmaxValue = T(),
 T yminValue = T(),T ymaxValue = T(),
 T zminValue = T(),T zmaxValue = T(),
 BSPTreeNode<T>* left_Node = NULL,
 BSPTreeNode<T>* right_Node = NULL )
 :data(nodeValue),
 xmin(xminValue),xmax(xmaxValue),
 ymin(yminValue),ymax(ymaxValue),
 zmin(zminValue),zmax(zmaxValue),
 left(left_Node),
 right(right_Node){}
};
//  BSP 
int scale = -1;  //         ，                  X      ，  Y   Z  
template <class T>
void createBSPTree(BSPTreeNode<T> * &root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
 cout<<"   ，   ……"<<endl;
 maxdepth=maxdepth-1; //             -1
 scale++; //             +1，             
 if(3==scale) scale=0; //          ，    
 if(maxdepth>=0)
 {
  root=new BSPTreeNode<T>();
  root->data = 9; //     ，        ，      。       BSP   ，     。
  root->xmin=xmin; //       
  root->xmax=xmax;
  root->ymin=ymin;
  root->ymax=ymax;
  root->zmin=zmin;
  root->zmax=zmax;
  double xm=(xmax-xmin)/2;//            
  double ym=(ymax-ymin)/2;
  double zm=(zmax-zmin)/2;
  //      
  if(0==scale) //     ，  X        
  {
   createBSPTree(root->left,maxdepth,xmin,xmax-xm,ymin,ymax,zmin,zmax);//                    
   createBSPTree(root->right,maxdepth,xmax-xm,xmax,ymin,ymax,zmin,zmax);
  }
  else if(1==scale) //     ，  Y        
  {
   createBSPTree(root->left,maxdepth,xmin,xmax,ymin,ymax-ym,zmin,zmax);//                    
   createBSPTree(root->right,maxdepth,xmin,xmax,ymax-ym,ymax,zmin,zmax);
  }
  else if(2==scale) //     ，  Z        
  {
   createBSPTree(root->left,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax-zm);//                    
   createBSPTree(root->right,maxdepth,xmin,xmax,ymin,ymax,zmax-zm,zmax);
  }
 }
}
int i=1;
//    BSP 
template <class T>
void preOrder( BSPTreeNode<T> * & p)
{
 if(p)
 {
  cout<<i<<".       ："<<p->data<<"/n   ：";
  cout<<" xmin: "<<p->xmin<<" xmax: "<<p->xmax;
  cout<<" ymin: "<<p->ymin<<" ymax: "<<p->ymax;
  cout<<" zmin: "<<p->zmin<<" zmax: "<<p->zmax;
  i+=1;
  cout<<endl;
  preOrder(p->left);
  preOrder(p->right);
  cout<<endl;
 }
}
// BSP    
template<class T>
int depth(BSPTreeNode<T> *& p)
{
 if(p == NULL)
  return -1;
 int h = depth(p->left);
 return h+1;
}
//      ，       
int cal(int num)
{
 int result=1;
 if(1==num)
  result=1;
 else
 {
 for(int i=1;i<num;i++)
  result=2*result;
 }
 return result;
}
//main  
int main ()
{
 BSPTreeNode<double> * rootNode = NULL;
 int choiced = 0;
 int maxdepth=0;
 while(true)
 {
  double xmin,xmax,ymin,ymax,zmin,zmax;
  system("cls");
  cout<<"     ：/n";
  cout<<"1.  BSP  2.    BSP /n";
  cout<<"3.     0.     /n/n";
  cin>>choiced;
  if(choiced == 0)
   return 0;
  else if(choiced == 1)
  {
   system("cls");
   cout<<"         ："<<endl;
   cin>>maxdepth;
   cout<<"        ，    ：xmin,xmax,ymin,ymax,zmin,zmax"<<endl;
   cin>>xmin>>xmax>>ymin>>ymax>>zmin>>zmax;
   if(maxdepth>=0 || xmax>xmin || ymax>ymin || zmax>zmin || xmin>0 || ymin>0 ||zmin>0)
   {
    scale = -1;  //         
    createBSPTree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
   }
   else
   {
    cout<<"    ！";
    return 0;
   }
  }
  else if(choiced == 2)
  {
   system("cls");
   cout<<"    BSP   ：/n";
   i=1;
   preOrder(rootNode);
   cout<<endl;
   system("pause");
  }
  else if(choiced == 3)
  {
   system("cls");
   int dep = depth(rootNode);
   cout<<" BSP     "<<dep+1<<endl;
   system("pause");
  }
  else
  {
   system("cls");
   cout<<"/n/n    ！/n";
   system("pause");
  }
 }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

정수 반전

Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

golang 두 갈래 검색 트 리 구현 (대상 지향, 비 귀속)

jdbc에서 mssql의 설정되지 않은 반환 매개 변수 저장 프로세스를 호출하는 반환 데이터 집합 예시

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다