장면 그래프

Scene graph
OpenSceneGraph의 아키텍처는 다양한 기능과 널리 채택된 장면 그래프 구현을 지원하는 오픈 소스 3D 그래픽 API입니다.

씬 그래프는 벡터 기반 그래픽 편집 애플리케이션 및 최신 컴퓨터 게임에서 일반적으로 사용되는 일반적인 데이터 구조이며 그래픽 씬의 논리적이고 종종 공간적인 표현을 배열합니다.그래프 또는 트리 구조의 노드 모음입니다.트리 노드에는 여러 개의 하위 노드가 있을 수 있지만 부모 노드 효과는 모든 하위 노드에 적용되며, 그룹에 대해 수행된 작업은 해당 효과를 모든 구성원에게 자동으로 전파합니다.많은 프로그램에서 각 그룹 수준에서 기하 변환 행렬(변환 및 행렬 참조)을 관련지어 이러한 행렬을 연결하는 것은 이러한 연산을 처리하는 효율적이고 자연스러운 방법입니다.예를 들어, 일반적인 기능은 관련된 모양과 개체를 복합 개체로 그룹화할 수 있으며, 이 개체는 단일 개체처럼 쉽게 조작할 수 있습니다.

그래픽 편집 도구의 장면 그래프

벡터 기반 그래픽 편집에서 씬 그래프의 각 리프 노드는 문서의 원자 단위(일반적으로 타원 또는 베지어 경로와 같은 모양)를 나타냅니다.형상 자체(특히 경로)는 스플라인 노드와 같은 노드로 더 분해될 수 있지만 씬 그래프는 낮은 수준의 표현으로 가는 것이 아니라 형상으로 구성된 것으로 생각하는 것이 실용적이다.

또 다른 유용하고 사용자 주도적인 노드 개념은 계층입니다.레이어는 임의의 수의 도형 및 도형 그룹을 배치할 수 있는 투명 시트처럼 작동합니다.그러면 문서가 일련의 레이어가 되고, 이러한 레이어는 쉽게 보이지 않게 하거나, 흐리게 하거나, 잠글 수 있습니다(읽기 전용으로 할 수 있습니다.일부 애플리케이션은 모든 레이어를 선형 리스트에 배치하는 반면 다른 애플리케이션은 원하는 깊이까지 레이어 내의 레이어를 지원합니다.

내부적으로는 레이어와 그룹이 모두 씬 그래프의 노드에 불과하기 때문에 실제 구조적인 차이가 전혀 없을 수 있습니다.차이가 필요한 경우, C++의 일반적인 유형 선언은 일반 노드 클래스를 만든 후 하위 클래스로 계층과 그룹을 도출하는 것입니다.예를 들어 가시성 부재는 레이어의 특징이지만 반드시 그룹의 특징일 필요는 없습니다.

게임 및 3D 응용 프로그램의 장면 그래프

장면 그래프는 3D 그래픽과 점점 더 큰 세계 또는 레벨을 사용하는 현대 게임에 유용합니다.이러한 애플리케이션에서 씬 그래프(일반적으로)의 노드는 씬(scene)의 엔티티 또는 객체를 나타냅니다.

예를 들어, 게임은 기사와 말의 논리적 관계를 정의하여 기사가 말의 확장으로 간주될 수 있습니다.장면 그래프에는 '말' 노드가 있고 여기에 '나이트' 노드가 연결되어 있습니다.

장면 그래프는 또한 다양한 실체의 공간적 관계뿐만 아니라 논리적 관계도 설명할 수 있습니다. 즉, 기사는 말이 움직이는 대로 3D 공간을 이동합니다.

이러한 대규모 애플리케이션에서는 장면 그래프를 설계할 때 메모리 요건이 주요 고려 사항입니다.이러한 이유로 많은 대형 장면 그래프 시스템에서는 메모리 비용을 절감하고 속도를 높이기 위해 지오메트리 인스턴스링을 사용합니다.위의 예에서 각 기사는 개별 장면 노드이지만 기사(3D 메쉬, 텍스처, 재료 및 셰이더로 구성됨)의 그래픽 표현이 인스턴스화됩니다.즉, 데이터의 단일 복사본만 유지되고 씬(scene) 그래프의 '나이트' 노드에 의해 참조됩니다.이를 통해 새로운 나이트노드가 생성될 때 외관 데이터를 복제할 필요가 없으므로 메모리 버젯을 줄이고 속도를 높일 수 있습니다.

장면 그래프 구현

씬 그래프의 가장 단순한 형태는 배열 또는 링크 리스트 데이터 구조를 사용하며, 그 모양을 표시하는 것은 단순히 노드를 하나씩 선형적으로 반복하는 것입니다.어떤 모양이 마우스 포인터와 교차하는지 확인하는 것과 같은 다른 일반적인 작업도 선형 검색을 통해 수행됩니다.작은 장면 그래프의 경우 이 정도면 충분한 경향이 있습니다.

장면 그래프 조작 및 디스패치

장면 그래프에 작업을 적용하려면 노드 유형에 따라 작업을 디스패치하는 방법이 필요합니다.예를 들어, 렌더링 연산에서 변환 그룹 노드는 행렬 곱셈, 벡터 변위, 사분수 또는 오일러 각도에 의해 변환을 축적합니다.그 후 리프 노드는 렌더러로 오브젝트를 전송합니다.일부 구현에서는 DirectX 또는 OpenGL과 같은 기본 렌더링 API를 호출하는 개체를 직접 렌더링할 수 있습니다.그러나 렌더링 API의 기본 구현에는 일반적으로 이식성이 없기 때문에 장면 그래프와 렌더링 시스템을 분리할 수 있습니다.이러한 유형의 디스패치를 실현하기 위해서는 몇 가지 다른 방법을 사용할 수 있습니다.

C++와 같은 객체 지향 언어에서는 가상 함수에 의해 쉽게 달성할 수 있으며, 각 함수는 노드에서 수행할 수 있는 작업을 나타냅니다.가상 함수는 쓰기가 간단하지만 일반적으로 소스 코드에 액세스하지 않고 노드에 새 작업을 추가하는 것은 불가능합니다.또, 방문자 패턴을 사용할 수도 있다.이 경우에도 마찬가지로 새로운 노드유형을 추가하기 어렵다는 단점이 있습니다.

다른 기법으로는 RTI(Run-Time Type Information)를 사용하는 방법이 있습니다.이 조작은 현재 노드에 전달되는 클래스로 실현할 수 있습니다.이 클래스는 RTI를 사용하여 노드의 유형을 쿼리하고 콜백 또는 펑터의 배열에서 올바른 조작을 검색합니다.이를 위해서는 콜백 또는 펑터에 대한 유형 맵을 런타임에 초기화해야 하지만 유연성, 속도 및 확장성이 향상됩니다.

이러한 기법의 다양성은 존재하며, 새로운 방법을 사용하면 추가적인 이점을 얻을 수 있습니다.한 가지 방법은 장면 그래프 재구축입니다. 장면 그래프는 수행된 각 작업에 대해 재구축됩니다.그러나 이것은 매우 느릴 수 있지만 매우 최적화된 장면 그래프를 생성합니다.이는 양호한 장면 그래프 구현이 사용되는 애플리케이션에 크게 의존한다는 것을 보여줍니다.

트래버설

횡단은 장면 그래프에 연산을 적용하는 기능의 핵심입니다.트래버설은 일반적으로 임의의 노드(흔히 씬 그래프의 루트)에서 시작하여 작업을 적용하고(대개 업데이트 및 렌더링 작업이 차례로 적용됨), 리프 노드에 도달할 때까지 씬 그래프(트리)를 반복적으로 하위 노드로 이동하는 것으로 구성됩니다.이 시점에서 많은 장면 그래프 엔진이 트리 위로 이동하여 유사한 작업을 적용합니다.예를 들어 변환을 고려한 렌더링 작업을 고려합니다. 씬 그래프 계층을 반복적으로 통과하는 동안 렌더 전 작업이 호출됩니다.노드가 변환 노드인 경우 자체 변환을 현재 변환 매트릭스에 추가합니다.조작이 노드의 모든 하위 노드 통과를 마치면 변환 노드가 변환을 취소할 수 있도록 노드의 렌더 후 작업을 호출합니다.이 방법은 행렬 [citation needed]곱셈의 필요량을 대폭 줄입니다.

노드가 다른 순서로 이동할 때 씬 그래프 작업이 실제로 더 효율적입니다. 즉, 일부 시스템에서는 씬 그래프를 구문 분석하기 쉬운 형식 또는 트리로 정렬하기 위해 씬 그래프 재구성을 구현합니다.

예를 들어, 2D의 경우 씬 그래프는 일반적으로 트리의 루트 노드에서 시작한 다음 하위 노드를 재귀적으로 그려 자체 렌더링합니다.이 나무의 잎은 가장 전경적인 개체를 나타냅니다.그림 그리기는 더 가까운 물체와 함께 더 먼 물체를 덮어쓰기만 하면 뒤에서 앞으로 진행되기 때문에, 이 과정은 화가 알고리즘을 사용하는 것으로 알려져 있습니다.종종 깊이 버퍼를 사용하는 3D 시스템에서는 가장 가까운 객체를 먼저 그리는 것이 더 효율적입니다. 왜냐하면 더 먼 객체는 더 가까운 객체에 의해 가려지기 때문에 실제로 렌더링되지 않고 깊이 테스트만 하면 되기 때문입니다.

장면 그래프 및 경계 볼륨 계층(BVH)

BVH(Bounding Volume Hierarchy)는 객체 간의 효율적인 도태 및 충돌 검출 속도 향상 등 다양한 작업에 유용합니다.BVH는 공간 구조이지만 지오메트리를 분할할 필요는 없습니다(아래 공간 분할 참조).

BVH는 경계 볼륨(종종 구체, 축 정렬 경계 상자 또는 방향 경계 상자)의 트리입니다.계층의 하단에서 볼륨의 크기는 단일 개체를 꽉 포함할 수 있을 정도로 큽니다(또는 고해상도 BVH에서는 개체의 일부만 더 작을 수도 있습니다).계층이 올라가면 각 노드는 그 아래의 모든 볼륨을 긴밀하게 포함하는 자체 볼륨을 갖게 됩니다.트리의 루트에는 트리의 모든 볼륨(장면 전체)을 포함하는 볼륨이 있습니다.

BVH는 객체 간의 충돌 검출 속도를 높이는 데 유용합니다.개체의 경계 볼륨이 트리의 상위 볼륨과 교차하지 않으면 해당 노드 아래의 개체와 교차할 수 없습니다(따라서 모두 매우 빠르게 거부됩니다).

BVH와 장면 그래프 사이에는 몇 가지 유사점이 있다.씬 그래프는 각 노드에 볼륨이 관련되어 있거나 계층 내 편리한 위치에 특별히 제작된 "바운드 노드"가 추가되어 있는 경우 BVH를 포함하거나 BVH가 되도록 쉽게 조정할 수 있습니다.이것은 씬 그래프의 일반적인 뷰는 아니지만 씬 그래프에 BVH를 포함하면 이점이 있습니다.

장면 그래프 및 공간 분할

공간 분할과 장면 그래프를 결합하는 효과적인 방법은 공간 분할 [clarification needed]데이터를 포함하는 장면 리프 노드를 만드는 것입니다.이를 통해 렌더링의 계산 효율성이 향상될 수 있습니다.

공간 데이터는 일반적으로 정적이며 일반적으로 분할된 [clarification needed]형태로 움직이지 않는 장면 데이터를 포함합니다.일부 시스템에는 시스템과 렌더링이 따로 있을 수 있습니다.이것은 괜찮고, 어느 방법에도 실질적인 이점은 없습니다.특히 씬 그래프는 공간 [neutrality is disputed]분할에 대한 보다 큰 시스템이라고 생각하기 때문에 씬 그래프가 공간 분할 시스템 내에 포함되는 것은 좋지 않다.

매우 큰 도면 또는 (레이 트레이스 렌더링 프로그램에서와 같이) 런타임에만 생성되는 장면 그래프에서는 보다 자동화된 방식으로 그룹 노드를 정의해야 합니다.예를 들어, 레이트레이서는 3D 모델의 장면 설명을 가져와 개별 부품을 경계 상자(경계 슬래브라고도 함)로 분할하는 내부 표현을 작성합니다.이러한 상자는 (가시성 결정의 일부로) 광선 교차 테스트를 효율적으로 계산할 수 있도록 계층적으로 그룹화됩니다.예를 들어, 아이레이와 교차하지 않는 그룹 상자는 구성원 테스트를 완전히 건너뛸 수 있습니다.

2D 애플리케이션에서도 비슷한 효율이 유지됩니다.사용자가 문서를 확대하여 컴퓨터 화면에서 일부만 볼 수 있도록 한 후 스크롤한 경우, 경계 상자(또는 이 경우 경계 직사각형 구성)를 사용하여 어떤 장면 그래프 요소가 보이는지 빠르게 판단하여 실제로 그려야 합니다.

응용 프로그램의 도면 성능에 대한 세부 사항에 따라 씬 그래프 설계의 상당 부분이 렌더링 효율 고려 사항에 의해 영향을 받을 수 있습니다.Quake와 같은 3D 비디오 게임에서는 가시성 테스트를 최소화하기 위해 바이너리 스페이스 파티션(BSP) 트리가 매우 선호됩니다.그러나 BSP 트리는 설계 장면 그래프에서 계산하는 데 매우 오랜 시간이 걸리고 설계 장면 그래프가 변경되면 다시 계산해야 하므로 수준은 정적인 경향이 있으며 동적 문자는 일반적으로 공간 분할 방식에서 고려되지 않습니다.

높이 필드 및 폴리곤 메쉬와 같은 조밀한 정규 객체에 대한 장면 그래프는 3D 경계 상자 계층의 특수 변형인 4중 트리 및 8중 트리를 사용하는 경향이 있습니다.높이 필드는 상자 볼륨 자체를 차지하기 때문에 개별 높이 필드 요소에 도달할 때까지 이 상자를 8개의 하위 상자(즉, 8진수에서 '옥트')로 반복적으로 세분화하는 것이 효율적이고 자연스럽다.쿼드 트리는 단순히 2D 옥트리입니다.

표준

피그

PHIGS는 최초의 상용 장면 그래프 규격으로 1988년에 ANSI 표준이 되었다.UNIX 하드웨어 벤더는 다양한 구현을 제공했습니다.HOOPS 3D Graphics System은 단일 소프트웨어 벤더가 제공한 최초의 상업 장면 그래프 라이브러리인 것으로 보입니다.이 제품은 서로 다른 하위 레벨의 2D 및 3D 인터페이스에서 실행되도록 설계되었으며, 1991년에 첫 번째 주요 프로덕션 버전(v3.0)이 완성되었습니다.

SGI

실리콘 그래픽스(SGI)는 1991년에 OpenGL Performer 또는 더 일반적으로 Performer라고 불리는 제품을 출시했는데, 이는 미래의 대부분의 SGI 제품에 대한 주요 장면 그래픽 시스템이었다.IRIS Inventor 1.0(1992)은 퍼포먼스 위에 구축된 고급 장면 그래프인 SGI에 의해 출시되었습니다.1994년 Open Inventor에 이어 새로운 Performer 릴리즈를 기반으로 구축된 고급 장면 그래프의 또 다른 반복입니다.Category:3D Scenegraph API에서 더 많은 3D Scene Graph 라이브러리를 찾을 수 있습니다.

X3D

X3D는 로열티가 필요 없는 오픈 스탠다드 파일 형식 및 런타임 아키텍처로 XML을 사용하여 3D 장면과 오브젝트를 표현하고 통신합니다.이것은, 애플리케이션에 짜넣어진 리얼 타임 그래픽 컨텐츠의 보존, 검색, 재생을 위한 시스템을 오픈 아키텍처내에 제공하는 ISO 인증의 표준입니다.이 모든 것은, 폭넓은 도미노를 서포트합니다.ins 및 사용자 시나리오.

「 」를 참조해 주세요.

레퍼런스

책들

  • Leler, Wm and Merry, Jim(1996) HOOPS, Addison-Wesley 3D
  • 요시에 베르네케(1994년)Inventor 멘토: Open Inventor, Adison-Wesley와 함께 객체 지향 3D 그래픽을 프로그래밍합니다. ISBN0-201-62495-8(릴리스 2)

기사들

외부 링크