.MAP 파일로 만드는 BSP (7) - 평면에 대해 폴리곤 판별하기

<평면에 대해 폴리곤 판별하기 >

평면에 대해 폴리곤을 판별하기 라는 것은 매우 일반적인 방법이다. 이를 하기 위해 우리가 알아야 할 것은 폴리곤이 앞에 있는가, 뒤에 있는가, 평면상에 있는가, 평면에 걸쳐져 있는가 이다. (그림 참조)

평면에 대해 폴리곤을 판별하는 것은 꽤 간단하다. 평면의 방정식인 n · x + d = 0 을 사용하면 평면에 대해 어떤 점이라도 판별할 수 있다. 만일 그 결과가 양의 값이라면 그 점은 평며늬 앞에 있다. 음의 값이라면 뒤에 있는 것이고, 0이라면 평면상에 존재하게 된다. 아래 는 평면에 대해 폴리곤을 판별하는 것에 대한 의사코드이다.

int iFront, iBack, iOnPlane;

 

for n = 0 to NumberOfVertices – 1

{

           double result = n.Dot ( vertices[ n ] ) + d;

           if ( result > 0 )

           {

                     iFront++;

           }

           else if ( result < 0 )

           {

                     iBack++;

           }

           else

           {

                     iOnPlane++;

           }

}

 

if ( iFront == NumberOfVertices )

{

           return FRONT;

}

if ( iBack == NumberOfVertices )

{

           return BACK;

}

if ( iOnPlane == NumberOfVertices )

{

           return ONPLANE;

}

return SPANNING;

<평면에 대해 폴리곤 쪼개기>

만일 폴리곤이 평면에 걸쳐져 있다면 이를 쪼개야 한다. 평면에 대해 쪼개진 폴리곤은 두 개의 부분, 앞부분과 뒷 부분, 두 부분으로 나뉜다. “앞 부분”은 평면의 앞에 위치하는 폴리곤의 한 부분이다. “뒷 부분”은 평면의 뒤에 위치하며 이 역시 폴리곤의 한 부분이다.

정점들은 올바른 “앞부분”에 할당해야 할 뿐만 아니라, 새로운 정점들은 폴리곤이 평면을 가로지르는 그 지점에 대해 생성되어야만 한다. 아래 그림에서는 커다란 파란색 점으로 표시해놨다. 폴리곤이 평면을 가로지르는 지점에서 새 정점을 생성하려면, 폴리곤이 평면에 걸쳐지는 그 선(edge)을 알아야 한다. 평면에 의해 쪼개지는 선 세그먼트로서 이 선(edge)을 고려할 수 있다.

새로운 정점을 계산하기 위하여, 먼저 교차가 일어나는 지점에서 선 세그먼트의 길이에 대한 퍼센티지를 알아야 한다.

 

이 퍼센티지를 계산하는 공식은

이다. 여기서 n과 D는 평면을 나타내고, s는 첫번째 정점, d는 선 세그먼트의 방향벡터이다. d는  s에서  e를 빼고 이를 노멀라이징 해서 계산한다. 여기서 만일 분모가 0이라면 이는 교차가 일어나지 않다는 점을 주의한다. 그리고 나서 그 결과인 p는 새로운 정점을 계산하는데 쓰인다.
그 공식은

이다.  만일 p가 새로운 텍스처 좌표계를 계산하는 것과 같은 다른 계산에 사용된다면, 노멀라이즈 해야 한다. 이 때 p는

이며, |  | 는 벡터의 크기를 나타낸 것이다.
이제, 우리는 평면으로 선 세그먼트의 교차를 발견하는 법을 알았다. 폴리곤이 평면에 의해  쪼개지는 함수에 대한 코드는 다음과 같다.

void SplitPolygon ( Polygon* pPoly_, Plane* pPlane_, Polygon* pFront_, Polygon* pBack_ )

{

           // Classify all vertices

           Classify Positions[ NumberOfVertices ];

 

           for n = 0 to NumberOfVertices – 1

           {

                     Positions[ n ] = pPlane_->ClassifyPoint ( pPoly_->vertices[ n ] );

           }

           // Build front and back fragments

           for n = 0 to NumberOfVertices – 1

           {

                     int m = n + 1;

                     bool bIgnore = false ;

                     if ( n == NumberOfVertices – 1 )

                     {

                                m = 0;

                     }

                     switch ( Positions[ n ] )

                     {

                     case FRONT:

                                pFront->AddVertex ( pPoly_->vertices[ n ] );

                     case BACK:

                                pBack->AddVertex ( pPoly_->vertices[ n ] );

                     case ONPLANE:

                                pFront->AddVertex ( pPoly_->vertices[ n ] );

                                pBack->AddVertex ( pPoly_->vertices[ n ] );

                     }

                    

                     if ( ( Positions[ n ] == ONPLANE ) && ( Positions[ m ] != ONPLANE ) )

                     {

                                bIgnore = true;

                     }

                     else if ( ( Positions[ m ] == ONPLANE ) && ( Positions[ n ] != ONPLANE ) )

                     {

                                bIgnore = true;

                     }

                     if ( ( !bIgnore ) && ( Positions[ n ] != Positions[ m ] ) )

                     {

                                // Calculate new vertex

                                Vector3 d = ( pPoly_->vertices[ n ] – pPoly->vertices[ m ] ).Normalize ( );

                                double denom = pPlane_->n.Dot ( d );

                                if ( denom == 0 )

                                {

                                          continue;

                                }

                                double p = -( pPlane_->n.Dot ( pPoly_->vertices[ n ] ) + pPlane_->d ) ) / denom;

                                Vertex v = pPoly_->vertices[ n ] + ( p * d ) ;

                                p = p / ( End – Start ).Magnitude ( ) ;

               

                      // Calculate new vertex’s texture coordinates

                                double du = pPoly_->vertices[ m ].tu - pPoly_->vertices[ n ].tu ;

                                double dv = pPoly_->vertices[ m ].tv - pPoly_->vertices[ n ].tv ;

                                du = du / sqrt ( du * du + dv * dv );

                                dv = dv / sqrt( du * du + dv * dv ) ;

                                v.tu = pPoly_->vertices[ n ].tu + ( p * du );

                                v.tv = pPoly_->vertices[ n ].tv + ( p * dv );

                                // Add the vertex to the fragments

                                pFront_->AddVertex ( v );

                                pBack_->AddVertex ( v );

                     }

           }

}