1. B-rep 스트림
B-rep(경계 표현)을 기하 파이프라인의 입력 스트림으로 가져오는 생산자(producer) 프로세스를 구성하는 것이 명확히 요구됩니다. 여기서 B-rep은 Wavefront 또는 Java3D OBJ 파일과 같은 표준 폴리곤 형식으로 외부에 정의됩니다. 폴리곤과 법선(normal)으로 제공되는 경계 표현은 반드시 일관성 있게 방향이 지정되어야 합니다.
컴퓨터 그래픽스 분야에서 주로 활용되는 아카이브된 기하 모델의 경우, 비평면 다각형(nonplanar polygon)이나 기하학적 부정확성을 처리하기 위해 입력 파일에 대한 필터링 과정이 필요할 수 있습니다. 이렇게 일관된 방향으로 정렬된 삼각형 출력 스트림은 아래에서 설명하는 알고리즘 단계를 거쳐 쌍대 진행형 BSP(Binary Search Partitioning) 트리로 변환됩니다.
2. B-rep에서 BSP로의 알고리즘 개요
이 방법의 핵심 절차는 각 삼각형에 대해 사전 계산된 관성(inertia)을 축약(contract)하여 삼각형 부분집합의 관성을 계산하고, 그 관성의 고유값 분해(eigen decomposition)를 통해 해당 부분집합의 형태를 최적으로, 그리고 재귀적으로 한정하는 것입니다.
d차원의 경우, 오일러 행렬(Euler matrix)의 d개 고유벡터 각각에 대해 2개의 극단 접촉 초평면(extremal tangent hyperplanes)을 구현함으로써 형상 한정이 이루어집니다. 해당 2d개의 초공간(hyperspace)들의 교집합은 현재 셀에 포함된 경계 부분집합에 가장 잘 맞는 (초)평행육면체를 생성합니다. 3차원에서는 6=2×3개의 평면이 존재합니다.
초기화
- 입력된 각 삼각형의 아핀 확장 오일러 텐서(affinely extended Euler tensors)를 먼저 계산합니다(선형 시간 소요).
- 입력 삼각형 전체 집합을 BSP 루트와 결합합니다.
- 볼록(convex)한 E3 공간 전체를 루트에 결합합니다.
- 루트 레이블을 FUZZY로 설정합니다.
재귀적 경우
- 현재 FUZZY 셀은 최대 6개의 직교 초평면으로 분할되며, 이 초평면들은 현재 삼각형 부분집합의 오일러 텐서 행렬 표현의 고유벡터들에 수직입니다.
- 이러한 평면은 현재 삼각형 부분집합의 정점 v에서 선형 함수 w = a · v를 평가하여 얻은 최솟값과 최댓값을 통해 계산됩니다. 여기서 a는 현재 고유벡터를 나타냅니다.
- 각 고유벡터에 대해 두 개의 최대-최소 병렬 초평면(max-min parallel hyperplanes)에 의해 최대 3개의 볼록 셀이 생성되며, 이는 {OUT, FUZZY, IN} 또는 {OUT, FUZZY, OUT}의 형태를 가집니다.
- 각 FUZZY 셀은 최대 고유벡터에 연관된 주 초평면(principal hyper-plane)에 의해 추가로 분할됩니다.
- 정점 포함 검사(containment test)를 통해 더 작은 삼각형 부분집합이 각 분할된 셀에 결합됩니다.
- 분할 평면과 교차하는 삼각형은 분할되며, 그 결과로 얻어진 (하위)삼각형들은 노드 하위 트리에 결합됩니다.
기본 경우
현재 셀이 소수의 경계 삼각형만으로 구성되면 재귀적 관성 기반 분할이 중단됩니다. 마지막으로 경계 삼각형들이 이루는 평면들을 사용하여 최종 셀 분할이 수행됩니다.