Scene Graph Rendering

원문 : http://www.nd.edu/~chuang1/summer03Images/scenegraph01.pdf Scene Graph Rendering Dirk Reiners OpenSG Forum dirk@opensg.org 이 수업에서 이 부분은 렌더링을 위한 씬그래프 시스템에 대해서 설명할 것이다. 씬그래프는 응용프로그램 개발을 단순화하고 이용 가능한 그래픽 하드웨어를 최적의 환경으로 사용할 수 있도록 도와줄 수 있다. 이 문서는 당신이 3D 컴퓨터 그래픽스에 대한 몇몇 기본 지식들을 가지고 있다고 가정한다. 만약 폴리곤, 방향성 광원(directional light source), 그리고 텍스처가 당신에게 아무런 의미도 없다면 당신은 이 수업을 따라가는데 문제를 느끼게 될 것이다. 이상적인 수준은 OpenGL을 사용하는 프로그램을 작성한 적이 있거나, "OpenGL Programming Guide"[1] 나 "Computer Graphics"[2]를 읽어본 수준이다.(역주 : D3D 라도 상관없을 듯) 첫 번째 섹션은 씬그래프의 기본 구조 및 표준 OpenGL 프로그램과의 차이에 대해서 설명한다. 주변에는 오픈 소스 및 상업용의 씬그래프가 많이 널려 있기 때문에 섹션 2는 가장 일반적으로 사용되는 것에 대한 짧은 개관을 제공한다. 나머지 장에서는 대부분의 씬그래프에 적용되는 일반 개념 및 특정 예제로서 OpenSG 의 사용에 대해 설명한다. 그 다음의 두 섹션은 일반적인 노드 구조체에 대해서 설명하고 그래프를 순회(traverse)하는 방법에 대해서 설명한다. 가장 중요한 단말 노드인 기하도형은 섹션 5에 설명되어 있다. 디스플레이된 기하도형, 변환 상태 및 재질 등을 지정하는 다른 것들은 섹션 6에서 다룬다. 몇 개의 다른 씬 그래프 지정 기능은 섹션 7에 설명되어 있듯이 다른 노드 유형 내부에 감춰져 있다. 씬 그래프의 메모리 공간을 최소화하기 위해 데이터는 여러 가지 방식으로 공유될 수 있는데, 섹션 8은 세부사항을 제공한다. 섹션 9 는 멀티스레딩에서의 중요한 부분 및 씬 그래프가 그것을 지원하기 위해서 어떤 것이 수행되는 지에 대해 다룬다. 섹션 10은 모든 부분에서 예제로서 사용되었던 OpenSG 에 대해서 약간 다룬다. 마지막 섹션은 씬 그래프의 장단점 및 씬그래프를 사용하기 좋은 상황에 대해서 다룬다(힌트 : 그런 상황이 그렇게 많지는 않다). 1. 씬그래프란 무엇인가? OpenGL 과 같은 저수준 그래픽 라이브러리들은 immediate 모드 기반이다. 모든 프레임에 대해서 응용프로그램이 그래픽 하드웨어로 모든 데이터를 전송하는 것이 필수적이다. 통신 모델은 "이 폴리곤과 이것, 그리고 이것을 취하고 렌더링 해주세요"라는 것과 같다. 씬그래프는 retained 모드 기반이다. 데이터는 한 번만 전달되고 필요할 때만 갱신된다. 통신 모델은 "이것은 내 데이터이며 이제 이미지와 저것 그리고 저것을 렌더링해 주세요"라는 것과 같다. 씬그래프가 관리하는 데이터는 그래프로서 구조화된다. 노드는 직접 링크에 의해 서로 연결되며, 루트 노드는 씬 데이터의 시작점을 정의하는데 사용된다. 렌더링을 위해서 이 그래프는 루트로부터 순회를 시작한다. 씬그래프는 보통 acyclic(역주 : 비환식) 그래프이다. 즉 한 노드에서 루트로 가는 과정에 있는 그래프 내의 다른 상위 노드들 사이의 연결이 존재하지 않는다(원문 :  i.e. there are no links from a node to any of its predecessors in the graph on the way to the root.). 이것은 루프를 생성하고 결국 순회를 무한 루프로 이끈다. 씬그래프와 수학적 그래프의 차이는 씬그래프들은 여러 가지 다양한 요소들을 포함하고 있다는 것이다. 즉 노드들은 서로 다른 유형이다. 인테리어와 단말 노드 사이에 눈에 띄는 차이가 있다. 단말 노드는 가시적인 기하도형을 담고 있으며, 인테리어 노드는 그래프를 논리적 그룹(fig. 1 참조)으로 구조화한다.   여러 종류의 인테리어 노드가 존재하지만 가장 기본적인 형태는 단일 그룹이다. 다른 인테리어 유형은 섹션 6과 7 에서 설명되며 많지는 않지만 다른 유형의 단말 노드로 존재하기도 한다. 그렇지만 가장 중요한 단말 노드는 기하도형이다(섹션 5를 참조).   2. 어떤 씬그래프가 있는가?   씬그래프는 오랫동안 존재해 왔다. 다음 리스트는 완벽하지 않지만 가장 잘 알려진 것들이다 :       - OpenSG (http://www.opensg.org)[3]     - Open Inventor (http://oss.sgi.com/projects/inventor)[5]     - PLIB (http://plib.sf.net)     - SGL (http://sgl.sf.net)     - OpenRM (http://openrm.sf.net)     - Open Scene Graph (http://www.openscenegraph.org)     - Performer (http://www.sgi.com/products/performer)[4]   이들 모두는 C++로 작성되어 있으며 Inventor 와 Performer는 C 인터페이스도 가지고 있다. SourceForge(www.sf.net)에서 "scene graph" 라고 검색하면 다른 많은 시스템들을 찾을 수 있다. 그러나 대부분은 더 이상 개발되지 않는 것들이다.   이들 중 세 가지(Performer, Open Scene Graph, OpenSG) 는 VR Juggler 바인딩을 가지고 있으며, 결국 VR 응용프로그램을 위한 좋은 후보이다. Performer 는 오픈 소스가 아니고 상업 제품임에 주의하라.   3. 노드 구조   씬그래프의 모든 노드는 몇 가지 공통적인 속성을 가지고 있다.   하나는 경계 볼륨이다. 노드의 경계 볼륨은 단순한 볼륨인데, 보통 축 정렬 경계상자(AABB) 나 구이다. 그것들은 현재의 노드의 하위에 있는 모든 노드들의 내용을 둘러 싼다. 그것은 씬그래프에 의해 노드의 가시성을 검사하기 위해서 사용된다. 만약 노드의 경계 볼륨이 가시 영역 바깥쪽에 있다면, 그 아래의 모든 노드들은 비가시화될 것이며 OpenGL 로 넘길 필요가 없을 것이다. 대규모의 씬에서 이것은 렌더링 속도에 있어 큰 영향을 끼친다.   여기에서 다른 씬그래프들은 조직화에 있어 약간의 다른 차이를 보인다. OpenSG 는 자식이 단말 노드로 사용되지 않더라도 모든 노드 내부에 자식의 리스트를 유지한다. 왜냐하면 그것은 구조를 단일화하고 순회를 단순화하기 때문이다. 또한 그것은 부모 노드의 포인터를 유지한다. 부모 및 그것들의 중요성에 대해서 세부적으로 알고자 한다면 섹션 8을 참조하라.   OpenSG의 특징은 노드가 Node 자체와 Core, 이 두 개로 분할된다는 것이다. Node 는 경계 볼륨, 부모에 대한 포인터, 자식 노드들에 대한 포인터 등과 같은 일반 정보를 모두 유지한다. Core 는 다른 유형의 노드들과 구분하기 위해서 사용된다(예제 그래프를 위해서는 fig.2 를 참조). 가장 단순한 Core 는 Group 인데, 이는 별다른 정보를 가지고 있지 않고 단지 그래프를 구조화하기 위해서만 사용된다. 4. 순회   씬그래프나 일반목적의 그래프 상에서의 기본 연산은 그래프의 순회이다. 루트 노드에서 시작해서 모든 노드가 방문될 때까지 노드들 사이의 링크를 따라간다. 대부분의 씬그래프 순회는 깊이 우선이다. 즉 같은 수준의 노드로 가기 이전에 자신의 모든 자식 노드를 순회한다(fig. 3 참조).   어떤 순회는 씬그래프 시스템에 의해 미리 정의되지만, 응용프로그램이 씬그래프를 순회하는 것도 가능하다. 어떤 유틸리티 함수는 그것을 매우 단순화할 수도 있다. 4-1 Actions 순회를 캡슐화하는 클래스들은 OpenSG 에서는 Actions 라고 불린다. 순회를 위해서 루트 노드와 함께 호출되는 것이 action 오브젝트이다. 다른 시스템들은 노드 메서드를 사용하지만, 기본 전제는 항상 루트 노드로부터 순회를 시작하는 것이다. 노드의 종류에 따라 다른 연산이 실행되고, 자식들은 순회로부터 선택되거나 배제된다. 다른 시스템에서는 다른 종류의 순회를 할 수 있다. 가장 중요한 것은 Rendering 순회이지만, 대부분의 시스템은 Intersect (역주 : 마우스 선택이나 충돌과 같은 검사를 위한) 순회도 포함하고 있다.   4-1-1. Render Action   (다른 시스템에서는 Draw 라 불리기도 하는)RenderAction 의 역할은 씬그래프의 데이터를 저수준 그래픽 라이브러리 명령어로 변경해, 결국 그래프를 이미지로 변경하는 것이다.   여기서 흥미로운 부분은 씬그래프가 수행할 수 있는 최적화이다. 왜냐하면 그것은 전체 씬에 대한 고차원의 지식을 가지고 있기 때문이다. 단순히 뷰어의 FOV(field of view, 시야각) 내에 존재하는지 여부를 통해 노드나 전체 하위 트리의 가시성 테스트할 수도 있지만, 더 복잡한 검사도 가능하다. 그러나 단순한 테스트라 하더라도 씬에 대해 고려해야할 많은 데이터를 이미 제거했기 때문에 비용이 적어진다.(원문 : It can test nodes or whole subtrees for visibility, in the simplest case just for inclusion in the field of view of the viewer, but more complex tests are possible. Even the simple test however will already remove a large part of the data from consideration for most scenes.)   씬그래프는 전체 씬을 렌더링하기 위해 저수준 라이브러리의 상태를 만드는데 필요한 변경을 최적화하고 최소화할 수도 있다. 이것은 파이프라인을 따라가는 시스템에 대해 렌더링 효율을 괄목할 만큼 증가시켜줄 수 있다.   렌더링은 씬그래프 시스템에서 대부분의 노력이 배치된 곳이며, 가장 효율적인 그래픽 하드웨어 용법을 만드는 방식에 대한 경험을 포함하고 있다. 그래서 결국 높은 렌더링 효율을 기대할 수 있는 것이다.   4-1-2. Intersect Action   다른 일반적인 action 은 IntersectAction 이다. 이것은 그래프의 기하도형이 레이(ray, 종종 레이 집합)에 충돌하는지 검사하며 결국 씬 내의 기하 오브젝트에 대한 충돌 테스트를 허용하게 된다. 이들은 오브젝트 픽킹 및 선택 혹은 땅바닥 기하도형으로부터 일정한 거리를 유지하기 위한 단순한 충돌 검사에 사용될 수 있다.   다시 말하지만 씬그래프에 내장된 고수준 데이터는 세부적인 기하도형과 함께 다뤄지기 이전에 씬의 많은 부분을 테스트함으로써 최적화될 수 있다.  결국 씬그래프는 수작업 검사보다 더 효율적일 수 있지만 그것을 프로그래밍하기 위해서는 응용프로그램 작성자가 괴로워진다고 말할 수 잇다. 씬그래프가 항상 광선추적(ray-tracing) 렌더러를 대체하는 데 있어 유용지는 않을 것이다. 그럼에도 이것은 더욱 특수화된 많은 요소들을 포함하고 있는 경향이 있기 때문에 광선 추적을 위한 더 효율적인 자료 구조가 될 수 있다.   4-2 단순 순회   응용프로그램은 종종 씬그래프가 제공하지 않는, 예를 들어 특정 상태를 만족하거나 만족하지 않는 오브젝트를 검색하는 것과 같은 특별한 기능을 구현하기 위해서 씬그래프를 순회할 필요성을 가지게 된다.   물론 응용프로그램은 자체적으로 전체 순회를 구현하거나 씬그래프에 의해 구현되어 있는 기본 action 중 하나로부터 상속받을 수도 있다. 그러나 대부분의 응용프로그램의 순회는 매우 간단하며 복잡한 순회를 위해 필요한 하위 구조 전체를 필요로 하지는 않는다.   이런 경우를 위해 OpenSG 를 포함하는 일부 시스템은 그래프를 순회하고, 만나게 되는 모든 노드를 사용자 제공 함수나 메서드로 넘겨 작업하고, 순회를 계속할지 말지를 결정하기 위한 단순한 방법을 제공한다. OpenSG 에서는 이 함수가 traverse() 라 불리며, 여러 상황에서 몇 가지 다양한 방식으로 이용할 수 있다.   세부적인 것은 이 문서의 뒷 부분으로 넘기도록 한다. 세부적인 것을 원한다면 OpenSG traverse tutorial 을 참조하라(섹션 10에 튜토리얼을 얻는 방법이 나와 있다). 5. 기하도형   씬그래프에서 가장 중요한 노드 유형은 기하도형인데, 이것은 최종적으로 렌더링되는 기하 데이터를 저장하고 있기 때문이다. OpenGL 에서 기하도형은 glBegin() 의 첫 번째 호출과 glEnd() 의 마지막 호출 사이에서 오브젝트에 대해 발생 가능한 모든 것들을 유지하고 있다. OpenGL 은 매우 유연하기 때문에, 그 데이터를 지정하기 위한 여러 가지 가능한 방식이 존재한다.   공통 인터페이스 스타일이 제공되며 그것은 모든 현재 씬그래프에 의해서 약간 다양하게 사용된다. 그것은 이 데이터를 분리된(개별) 배열에 나누어 저장하는데 기반하며, OpenGL VertexArray 인터페이스와 매우 유사하다.   5-1. 정점 속성   OpenGL 에서 한 프리미티브의 각 정점은 여러 개의 속성을 가질 수 있다. 물론 가장 중요한 것은 정점의 위치이다. 다른 공통적인 것은 법선인데, 이는 조명 계산, 색상, 텍스처 좌표를 위해서 사용된다. 씬그래프는 개별 배열을 이들 속성을 위해서 사용한다. 이 배열들이 관리되는 방식은 씬그래프마다 다르다. 가장 간단한 경우 씬그래프 자체는 단지 데이터에 대한 포인터만을 저장하고, 응용프로그램이 데이터를 다룰 책임이 있다. 다른 선택은 데이터를 기하도형 자체에 저장하는 것인데, 일반적으로 STL 벡터나 이와 유사항 동적 크기 배열 형식에 저장한다.   이러한 접근의 장점은 그 데이터의 유형이 고정된다는 것이다. OpenGL은 그것이 받아들일 수 있는 종류의 데이터에 대해서 매우 유연하며, 다른 응용프로그램들은 다른 필요성을 가진다. 개별 유형의 기하도형을 다른 매개변수 유형을 위해 생성하는 것이 가능하다. 그러나 다른 속성 유형을 위한 다른 차원(1 ~ 4)의 조합이나 다른 데이터형(unsigned/signed, byte/short/int/float/double)의 조합은 현실적이지 않은 완벽함을 위해 수 백개의 클래스를 생성하게 하는 상황을 만들게 될 것이다.   OpenSG 는 속성을 Properties 라는 자신만의 자료 구조에 넣음으로써 그 문제를 해결한다. Geometry Core 자체는 단지 이러한 Properties 에 대한 참조만을 유지한다. 모든 종류의 속성을 위해서 Properties 추상 기저 클래스가 존재하며, 여러 유형의 구체적인 버전이 존재한다. 이러한 방식으로 단일 Geometry Core 유형은 모든 다양한 자료형에 접근할 수 있다.   5-2. 프리미티브   정점들 자체는 기하도형을 정의하기에는 충분하지 않으며, 그것들은 올바른 방식으로 연결되어야 한다. OpenGL 은 정점들을 연결하기 위한 여러 개의 다양한 방식을 가지고 있다. 그것들을 단순한 점이나 삼각형, 쿼드 및 폴리곤을 통해 연결된 라인으로 그리는 것으로부터 삼각형 스트립이나 팬과 같은 연결된 프리미티브로 그리는 것까지 아주 다양하다. 이들 역시 씬그래프에 의해 매핑될 필요가 있다. 이것은 여러 가지 방식으로 수행될 수 있다. 하나는 여러 가지 프리미티브 유형을 위한 여러가지 기하도형을 가지고 있으며, 단지 하나의 기하도형 당 하나의 프리미티브만을 허용하는 것이다. 어떤 시스템들은 Geometry 를 각각이 자신만의 프리미티브 유형을 가질 수 있는 여러 개의 소규모 기하도형으로 분할함으로써 부하를 줄이려고 시도하기도 한다. 기하도형은 프리미티브 유형이 모두 같더라도 반드시 한 개 이상의 프리미티브 인스턴스를 유지해야만 한다. 일부 유형들(예를 들어 점, 라인, 삼각형)에 대해서는 단일 정점 카운트면 충분하다. 왜냐하면 그것들은 이미 고정된 개수의 정점에 의해 정의된 여러 개의 기하 프리미티브를 포함하기 때문이다. 다른 유형들(예를 들어 폴리곤, 스트립, 팬)은 프리미티브 인스턴스마다 개별 length 를 필요로 한다. 이들 length 는 보통 정점 속성과 같이 기하도형의 속성으로서 저장된다.   OpenSG 는 사용할 프리미티브 유형의 리스트를 유지하는 types 속성도 추가함으로써 혼합 프리미티브 유형을 허용한다. 이 types 속성 내의 모든 요소는 lengths 속성 내의 요소들과 관련이 있는데, length 를 모든 프리미티브 유형 인스턴스에 할당함으로써 그것을 정의하게 된다(fig. 4 를 참조). 이것은 여러 개의 프리미티브를 허용함으로써 최대의 유연성을 제공하며, 동질성과 함께 이질성 또한 제공한다.   5-3. 인덱싱   5-3-1. 단일 인덱싱   막혀있는 서피스, 정점들은 종종 여러 번 사용된다. 쿼드를 구성하는 단순한 그리드에서, 거의 모든 정점들은 네 개의 프리미티브에 의해서 사용될 것이다. 이 정점들을 네 번 저장하는 것은 스트림에 필요한 메모리를 많이 증가시키고, 결국 허용될 수 없게 된다.   그래서 인덱싱 레이어가 프리미티브와 정점들 사이에 삽입된다. 정점들을 property 에 주어진 순서대로 사용하는 대신데, 사용될 정점들이 중복되지 않도록 지정하기 위해서 인덱스가 사용된다. 2 혹은 4 바이트인 인덱스는 일반적으로 32 에서 120 바이트를 사용하는 정점보다 적은 양의 데이터를 사용하기 때문에, 이것은 메모리 소비를 꽤 줄여 준다(fig. 5 참조).   그러나 인덱싱은 부가적인 오버헤드를 야기한다. 즉 그것은 필요할 때만 사용되야 한다. 일부 씬그래프는 가하도형 노드 유형의 형태에서 차이를 보인다. OpenSG 는 단지 IndexProperty 의 유무 여부만을 검사한다. 5-3-2. 다중 인덱스 지금까지 속성은 모두 서로 연결되어 있었다. 즉 만약 colors, normals 가 존재한다면, 각 정점 위치에 대해 색상과 법선이 존재했다. 이것은 너무 많을 수도 있고 동시에 부족할 수도 있다. 만약 색상이 단지 제한된 하위집합만을 취한다면, 몇 십개의 색상만이 필요할 것이다. 즉 모든 정점들을 위해 개별 색상을 보유하는 것은 필요 이상의 메모리를 소비하게 되는 것이다. 한편으로 단일 정점 위치는 서로 다른 법선을 필요로 할 수 있다. 보통의 경우 면은 그것이 정점 기반으로만 수행된다고 해도 픽셀당 조명 계산의 느낌을 부여하기 위해서 smooth-shaded 처리가 된다. 만약 각진 모서리를 원한다면, 단일 정점은 서로 다른 법선을 사용해야만 한다. 다중 인덱싱은 가장 단순한 형태는 정점당 속성과 면당 속성 사이의 차이이다. 면당 속성은 정점과 연결되어 있지 않고 면과 연결되어 있다. 그것들은 보통 인덱싱되지 않는다. 그것들은 대부분의 경우 위에 주어진 법선 문제를 해결하지만, 색상 예제에서 주어진 반대 문제는 해결할 수 없다. 더욱 유연한 해결책은 모든 속성에 대해서 개별 인덱스를 소유하는 것이다. OpenSG 는 다른 접근을 사용한다 : 삽입 인덱스(interleaved indices).  정점 당 인덱스 속성으로부터 단일 값을 취하는 대신에, 다중 값이 사용될 수 있다. 어떠한 인덱스가 어떠한 속성을 위해 사용되어야 하는지를 정의하기 위해서 인덱스 매핑이 사용된다. 인덱스 맵의 모든 요소는 모든 속성 조합을 지정할 수 있는 비트필드(bitfield)이다(역주 : 비트 조합이라는 의미인듯). 이것은 다른 속성을 위해 인덱스를 공유하거나, 각각을 위해 개별 인덱스를 소유하는 것을 가능하게 한다(fig. 6 참조). 다중 인덱싱에 있어서 한 가지 문제는 그것이 발생시키는 퍼포먼스 오버헤드이다. 그것은 OpenGL 의 정점 배열에 직접 매핑되지 못하며, 명시적인 호출을 사용해서 현실화되어야만 하는데, 그것은 특히 PC 플랫폼에서 퍼포먼스를 낭비한다. 정적 모델을 위해 이 비용은 그것들을 디스플레이 리스트에 배치함으로써 초기화 단계 안으로 상쇄될 수 있다. 동적 모델을 위해 이 비용은 모델이 렌더링될 때마다 지불되어야 하며, 결국 다중 인덱싱을 사용하기 위한 시도를 할 때는 조심해야 한다.   5-4. 접근   여러 가지 다양한 기하도형 데이터를 사용하면 접근이 복잡해 질 수 있다. 특히 OpenSG는 다양한 프리미티브 및 데이터형을 지원하는 단일 노드 유형만을 가지고 있다. 기하도형 데이터에 대한 접근을 단순화하기 위한 두 가지 메커니즘이 있다.   이 속성은 다른 데이터형을 감추는 일반 인터페이스를 소유한다. 그를 위해 모든 유형의 속성들은 모든 유형의 데이터가 변환될 수 있고 접근 가능한 일반(generic) 데이터형을 소유한다. 예를 들어 법선을 위한 Vec3f 혹은 위치를 위한 Pnt3f. 이 변환은 일부 데이터를 소실할 수 있다. 예를 들어 4D 좌표를 변환하는 것은 4 번째 좌표를 잃어버리도록 만들 것이다. 또한 그것은 퍼포먼스 패널티를 일으킨다. 왜냐하면 가상 함수를 통해서 접근하기 때문이고, 데이터가 복사/변환되어야만 할 것이기 때문이다. 결국 데이터형이 알려져 있고 수 많은 요소들이 접근될 필요가 있다면, 대신 형지정(type-specific) 접근을 사용하는 것을 추천한다.   두 번째 메커니즘은 서로 다른 프리미티브 유형 및 인덱싱에 대한 걱정을 극복하는데 도움을 준다 : 반복자(iterators).   OpenSG 는 세 가지 유형의 기하도형 반복자를 가지고 있다 : 프리미티브, 면, 삼각형. Geometry 는 STL 컨테이너와 같이 자신을 통해 반복하는데 적당한 반복자를 생성하기 위한 begin 및 end 메서드를 가지고 있다. 그것들은 모두 인덱스 참조해제(dereferencing) 에 대해 주의를 기울였고, 프리미티브의 값에 대한 직접 접근을 허용한다. 그것들은 Geometry 에 대한 접근을 허용하는데, 마치 기하도형의 모든 데이터가 서로 다른 배열에 개별적으로 저장된 것이 아니라, 개별 프리미티브를 위한 특정 자료형의 조합인것처럼 취급한다.   서로 다른 반복자 유형 사이의 차이점은 반복자가 어떠한 요소를 반복하고자 고려하고 있는지에 달려 있다. PrimitiveIterator 는 단지 types 속성을 통해서 단계를 진행한다. 즉 삼각형이 삼각형 반복 요소를 스트립(strip)하는 예만을 고려한다. FaceIterator 는 더욱 선택적이며 모든 점과 라인을 무시한다. 그것은 반복시마다 모든 잔존 프리미티브를 3 개나 4 개의 정점 폴리곤으로 분할한다. TriangleIterator 도 이와 유사하지만, 단지 삼각형만을 반환한다.   반복자는 임의의 기하도형을 사용해 작업하는 것을 매우 쉽게 만들어 주며, 어떠한 유형 및 인덱스가 사용되어야 하는지에 대해 신경쓰지 않게 해 준다.   6. 상태 제어   기하도형을 정의하는 것은 그래픽적 씬을 생성하는데 있어서 절반이며, 서피스, 조명, 변환 속성을 정의하는 것이 나머지 절반이다. 6-1. 변환   이 문맥에서 변환은 씬 내의 오브젝트를 움직이는 데 사용되는 기하 변환에만 국한되며, 카메라 조작과 관련된 변환에 대해서는 이 수업 노트의 다른 장에서 다룬다. 변환은 완전한 오브젝트에 적용되며, 오브젝트의 일부에 대해서 적용될 수 없다. 또한 변환은 씬그래프의 전체 하위트리에 유용하게 적용되어 혼합 오브젝트나 다중 오브젝트들을 주위로 이동시킬 수 있다. 그래서 이것들은 씬 그래프의 상태 계층을 위한 주요한 예제가 될 것이다. 변환은 행렬을 저장하거나 변환을 정의하는데 필요한 요소들을 저장하는 개별 노드 유형으로서 구체화된다(예를 들어 스케일, 방향, 이동). 변환은 트리의 아래에 있는 모든 것들에 영향을 미치며, 그것은 다른 변환을 포함한다.   변환은 축적된다. 즉 새로운 변환은 그것의 상위에 있는 것의 변환을 대체하지 않고 그것을 추가한다. 이것은 로컬 좌표계에서 변환을 정의하는 것을 허용하면서, 전체 시스템을 변환할 수 있도록 해 준다. 그리고 그것들은 계층적 변환 체인을 정의하는 것을 허용한다. 계층적 변환의 사용에 대한 주요 예제는 행성과 달을 가지는 행성계이다.   행성계에서 달은 자신의 행성 주변을 회전한다. 동시에 행성은 태양 주변을 회전한다. 절대 좌표로 달의 이동을 지정하는 것은 복잡한 처리가 될 것이다. 그것들을 자신의 행성에 상대적으로 지정하고, 동시에 행성-달 덩어리를 태양 주변으로 움직이는 것이 간단하다.   6-2. 광원   광원은 씬그래프의 문맥에서 흥미로운 문제를 제시한다. 씬그래프에서 광원노드의 위치는 두 개로 정의될 수 있다. 하나는 광원의 위치와 방향이다. 이것은 자동차에 붙어 있는 헤드라이트와 같은 오브젝트에 광원을 붙이는데 유용하다. 변환 계층을 위해 광원은 자동적으로 자동차의 이동을 따라갈 것이다. 조명에 영향을 받는 것을 정의하기 위해 다른 목적이 존재할 수 있다. 이것은 상태 계층과 관련이 있다. 즉 씬그래프에서 광원 아래에 존재하는 모든 것은 그것에 의해 조명을 받는다.   그래프 내에서 광원 위치에 대한 이 두가지 의미는 모순되며, 트리 내의 단일 위치를 사용해서는 해결할 수가 없다. 만약 그래프 내에서 광원의 위치가 한 번에 두 가지 의미를 가진다면, 헤드라이트 시나리오는 불가능할 것이다. 왜냐하면 조명은 단지 그래프 내에서 아래에 있는 것들에만 비칠 것이며, 즉 일반적인 헤드라이트의 행동을 취하지 않고 차의 일부가 아니라 길의 일부가 될 것이다. 그럼에도 불구하고 Inventor 는 이 기법을 사용한다.   다른 시스템들은 이 문제를 해결하기 위해서 다른 해법을 사용한다. 하나의 해결책은 모든 광원을 전역으로 정의하는 것이다. 즉 모든 것은 모든 광원에 의해서 조명을 받는다. 이 경우 그래프 내의 위치는 그 조명만의 위치를 잡는데만 사용될 수 있다. 이 해결책은 간단하지만 시스템의 표현력에 제약을 가하게 된다. Performer 는 각 기하도형에 어떠한 광원이 영향을 미치는지를 명시적으로 정의하도록 허용하는 차선책을 사용한다. OpenSG 는 다른 해결책을 사용한다. 그래프에서 광원의 위치는 상태 계층 요소에 근거해 씬내에서 그것에 의해 영향을 받는 부분을 정의한다. 광원의 위치와 방향은 그래프 내의 다른 요소에  의해서 정의된다. 그 요소는 단지 광원에 의해서 참조되기만 하며 beacon(봉화, 등대?) 이라 불린다.   6-3. 재질   재질은 기하도형의 서피스 속성을 정의하는데 사용되며, OpenSG 에서는 실제로는 Geometry 노드의 속성이다. 재질의 속성은 대부분 OpenGL 재질 상태로부터 직접 매핑된다. 즉 emissive, ambient, diffuse, specular 색상 및 shininess이다.   OpenGL 에 직접적으로 매핑될 수 없지만 올바르게 구현되기 위해 많은 노력을 들인 순결해 보이는 재질은 투명도이다. 투명도와 OpenGL 은 서로 잘 맞지 않는다. 투명한 오브젝트는 다른 모든 오브젝트가 렌더링된 이후에 올바른 블렌딩 함수를 사용해 렌더링될 필요가 있으며, 그것들은 뒤에서 앞의 순서로 그릴 필요가 있다. 완전히 올바르게 그리려면 그것들은 면끼리 비교해 뒤에서 앞으로 그려지며, 겹치는 기하도형에 대해 겹치는 면을 분할하고 정렬해야 한다. 투명도를 위한 전체적이고 완벽한 지원은 매우 소비적이며, 특히 동적인 기하도형의 경우에 더 심하다. 결국 어떠한 씬그래프도 그것을 지원하지 않는다. 그것들에 대한 최선은 오브젝트 간 비교에 의해 투명한 오브젝트를 마지막에 렌더링하고, 뒤에서 앞으로 정렬하는 것을 지원하는 것이다. 즉 오브젝트는 뒤에서 앞으로 렌더링될 것이다(보통 참조 위치에 의해 정렬된다. 예를 들어 경계상자의 중심). 그러나 오브젝트 내부 정렬은 수행되지 않는다.   OpenSG 는 SimpleMaterial 과 SimpleTexturedMaterial 클래스를 이를 위해 사용한다. 또한 SimpleTexturedMaterial 은 텍스처 필터링을 정의하기 위한 매개변수와 함께 재질을 위한 텍스처로서의 이미지를 유지한다.   7. 다른 노드 유형   다른 씬그래프들은 다른 노드 유형의 형성을 위한 부가적인 기능을 제공한다. 이들 중 일부는 매우 ubiquitous 하며, 다른 것들은 적은 시스템에서만 작동한다. 다음은 약간의 일반적인 예들이다.   7-1. 스위치   Switch 노드는 단순하지만 Group 노드 상에서의 다양성을 위해 유용하다. t selects zero or one of its children for traversal instead of all of them. 이것은 하위 그래프를 끄거나 모델의 정적 집합을 통해 순환하기 쉬운 방법이다.   어떤 시스템은 비트마스크를 사용해 자식 집합을 선택하는 것을 허용한다.   7-2. LOD   Level of Detail(LOD) 는 다소 단순하지만 대규모 씬에 대한 렌더링을 최적화하는데 효율적인 방법이다. 기본 발상은 멀리 있는 오브젝트들은 가까이 있는 오브젝트보다 덜 세부적으로 렌더링한다는 것이다.   이렇게 함으로써 씬그래프는 렌더링되는 오브젝트의 복잡성을 줄일 필요가 있다. 가장 좋고 쉬운 방법은 다른 복잡도를 가지는 여러 가지 버전의 오브젝트를 제공하도록 응용프로그램에 요청하는 것이다. 이들 각각은 어디에서 자신이 사용되어야 하는지를 알기 위해서 보통 관찰자로부터의 거리인 범위를 할당받는다. 이 범위는 다른 버전을 가지고 노드의 자식으로서 LOD 노드에 저장된다.   LOD 노드의 작업은 예를 들어 주어진 관찰자의 거리를 위한 올바른 자식을 선택하는 것이다. 일반적으로 그것은 단지 하나의 자식만을 선택하며, 현재 상황에서 가장 적합한 것을 찾는다. 즉 그 중 더 복잡한 것을 디스플레이한다.   7-3. 파티클   종종 단순하지만 동적으로 이동하는 대규모의 오브젝트들이 필요하다. 그 예는 ball-and-stick 분자 모델에서의 ball인 순환적인 대칭 오브젝트를 위해 사용될 수 있는 관찰자에 정렬된 쿼드 또는 투명 텍스처를 사용하는 연기 시뮬레이션이다. 다른 예는 궤적을 보여주는 화살일 수 있다.   Geometry 노드를 매우 간단한 수 천개의 이러한 단순 개체 각각을 위해 생성하는 것은 많은 오버헤드를 발생시킨다. 그것들을 모두 관철자 정렬로 바꾸는 것은 다중의 뷰가 씬 내에서 활성화되어 있다면 응용프로그램으로서는 불가능하다. 즉 씬그래프에서 배제해야 한다. OpenSG 는 이러한 상황을 특정 Paticles 노드를 사용해 지원하는데, 이는 위치, 색상, 크기를 입력으로 취해 그것들을 매 프레임에 대해 여러 종류의 기하도형으로 변환한다.   8. 공유   8-1. 노드 기반   씬그래프는 씬을 렌더링하기 위한 모든 데이터를 소유할 필요가 있다. 그러나 많은 씬에는 다른 오브젝트의 복사본일 뿐인 오브젝트들이 존재한다. 단순한 예는 자동차의 휠이다. 같은 오브젝트에 대한 정확히 내 개의 복사본이 존재하며, 위치만 다를 뿐이다. 씬그래프를 위해 메모리를 효율적으로 사용하려면, 이들 오브젝트에 의해 사용되는 자료를 공유할 방법이 있어야만 한다.   이를 위한 한 방법은 다수의 부모에 대해 오브젝트 추가를 허용하는 것이다. 변환을 사용하여 서로 다른 복사본이 같은 데이터를 공유하면서 독립적으로 배치될 수 있도록 할 수 있다. 이것은 매우 간단한 기법이며, 이는 많은 씬그래프에서 사용된다.   그럼에도 불구하고 이것은 몇 가지 문제를 가지고 있다. 오브젝트가 포인터에 의해 더 이상 식별될 수가 없다. 모든 복사본이 같은 오브젝트이기 때문에, 포인터는 복사본의 의미를 알지 못한다. 결국 그래프를 따라 올라갈 때, 예를 들어 오브젝트의 전역 위치를 획득하기 위해 순회 과정 상의 변환을 누적하고자 할 때, 어떠한 방식으로 해야할지 알 수가 없다.   또 다른 문제는 이름과 같은 인스턴스 지정 데이터를 연결할 수가 없다는 것이다. 다시 말하는데 이 복사본은 모두 같은 오브젝트이며, 차이가 존재하지 않는다.   이것이 OpenSG 가 Node/Core 분할 정책을 사용하는 주요 이유이다. Node 는 단일하며, 그것들은 공유될 수 없다. 모든 Node 는 단지 단일 부모 포인터만을 가진다. Core 는 분할될 수 있으며, 그것들은 다수의 사용자를 가진다(fig. 7 참조).   Node 는 매우 작기 때문에 그것들을 복사하는데 있어서 발생하는 메모리 패널티는 문제가 안 된다. Cores 에 포함된 주요 데이터들은 공유될 수 있다. Graph 구조를 노드 내용으로부터 분할하는 것은 공유 제어를 허용하기도 한다. 예를 들어 Switch Core 를 공유하는 것은 단일 Core 상의 값을 설정하는 것을 허용해 씬 내의 여러 Node에 영향을 미칠 수 있다. 같은 원리가 LOD, Transformation, 다른 종류의 Core 에도 적용된다.   8-2. 기하도형   씬그래프 데이터의 대부분은 기하도형에 포함된다. 완전한 기하도형을 공유하는 것은 위에서 언급했던 노드 기반 공유와 함께 가능하다. 그러나 예를 들어 shaded 모델의 최상위에서 와이어프레임을 그린다거나 다른 색상으로 오브젝트의 일부를 그려서 강조한다거나 할 때 기하도형의 일부만을 공유하는 것이 좋은 상황이 존재한다.   어쨌든 기하도형의 데이터는 다른 속성으로 분할되었기 때문에, 개별 속성을 개별적으로 공유하기 위한 단계는 적다. 대부분의 씬그래프 시스템은 여러 가지 방식으로 그것을 허용한다. 왜냐하면 그 데이터는 응용프그램 혹은 OpenSG와 같은 것에 의해서 데이터를 자신만의 자료구조에 파생시키는 것에 의해 관리되기 때문이다.(원문 : As the data of the geometry is split into different properties anyway, it is a small step to sharing the separate properties separately. Most scene graph systems allow that in one way or another, either because the data is managed by the application anyway, or, like OpenSG, by splitting the data off into their own data structures.)   (역주 : 이 아래쪽은 중요하지도 않은 것 같고 뭔 소린지 이해가 안 되는 부분도 있고 해석하지 않습니다. 알아서들 보시길...)   9. Multi-Threading   Multi-threading is an aspect that is growing in importance, given the current trend in processor designs to go to simultaneous multi-threading (SMT). A number of scene graphs provide simple multi-threading support, which allows simultaneous reading or rendering of the scene graph. For many applications this is quite adequate, but for more demanding applications that use asynchronous simulation threads needing consistent data and/or manipulate the graph it is not enough. OpenSG supports these kinds of applications by allowing each structure to have multiple aspects, i.e. multiple copies of itself. This is done efficiently by only copying the bulk of the scene graph’s data, the geometry data, when it is needed. Different aspects can be efficiently synchronized under application control, making them contain the same data again. To support this in a general and easily extensible way, OpenSG adds reflectivity to the system. Reflectivity is the ability of the system’s structures to give out information about themselves, e.g. which fields they contain and how to access those fields. This ability is used to automatically add synchronization capabilities to each structure of the system. It can also be used to write a generic OpenSG loader/writer that can automatically handle new structures and extensions in the system without having to write any specific code for it. An extension of this system also allows synchronizing scene graphs across a cluster of machines. Again, no cluster-specific code needs to be written, the data is automatically distributed and synchronized. The difference between this kind of clustering and the kind of clustering the already introduced systems clusterJuggler and netJuggler lies in the point on the pipeline the distribution is done. Both netJuggler as well as clusterJuggler distribute the inputs to all nodes. This approach minimized the amount of data to be sent over the network, but the full application is running on all nodes and needs to process the input. If that input processing takes a lot of calculation or depends on large external data this can be a problem. OpenSG distribution on the other hand distributes after the inputs have been processed but before OpenGL commands are generated. This section can only give an idea of what’s done in OpenSG for multi-threading, see [3] for more information.   10 Getting to know OpenSG OpenSG is one example of the current breed of modern scene graphs. It is developed and distributed under the Open Source principle and is available including source code from www.opensg.org. It is designed with multi-threading (see sec. 9 for details) and application extensibility in mind, i.e. changes to internal data structures are possible without having to change the library’s source code (and thus without having to reapply changes whenever the library changes). The development is supported by a number of companies and research institutes (see www.opensg.org/forum for details), guaranteeing sustained development. Further development is also sponsored by the German Government by a research project called OpenSG PLUS (see www.opensg.org/OpenSGPLUS) which funds continuous development of the core as well as a lot of high-level functionality (NURBS rendering, subdivision surfaces, Clustering, Occlusion Culling, Volume Rendering, High-Level Shading to name but a few). It is developed on Linux, Irix andWindows, with a MacOS X port pretty much working and an HP port in the works. It is hosted on SourceForge (www.sf.net) and uses the SourceForge infrastructure to build a developer community, mainly based on mailing lists and IRC. The 1.0 version was released in October 2001, the 1.1 developer version will be released in April 2002. But an automatic dailybuild system makes sure that the current CVS always compiles on every platform and allows access to daily snapshots if needed. Some automated documentation is created from the source code using the doxygen tool, but more useful as an introduction is the Starter Guide (www.opensg.org/starter) and the tutorial examples (available in the tutorials/ directory in the source and distributions). 11. When does it make sense to use a scene graph?   This part of the course talked about scene graphs and what they can do for a graphics application. Of course they cannot solve all the problems, and they are not always the best solution to every problem. Their main strength and their main weakness is that they are a retained mode structure. Having access to all the data making up the scene allows them to optimize the rendering by only rendering visible objects and sorting them by state to make effective use of the graphics hardware. The weakness is that the data structure needs to be consistent with the application’s data. If that data is very dynamic, especially if the node structure changes for every frame, keeping the scene graph up-to-date can eat up the profit that it brings. If only the contents of the objects change it’s not as bad, especially if the maximum size of the dynamic areas is known beforehand, but there is still some overhead involved. Scene graphs really shine in complex scenes, complex in the sense that they consist of a large environment that uses many different materials. For situations where there is a small number of objects, all using the same rendering parameters, and all visible all the time, a simple application obeying some basic rules (only change state if it is really different, use vertex arrays with native data types) can reach a very good performance. Note however that even these applications can get a taste of complexity quickly, as soon as interaction gets involved and different kinds of markers, information displays and higher level rendering features are needed, in which case a scene graph becomes a more viable solution. Besides being highly efficient rendering engines, scene graphs also tend to accumulate useful utility functions for handling scene data. The most prominent examples are loaders for models and images. Writing loaders is a job that nobody likes to do, so being able to use somebody else’s work can already make using a scene graph worth it. Similar reasoning applies to the intersection test (see sec. 4.1.2). A special case is the clustering support given by OpenSG, as it simplifies bringing an application to a cluster significantly, something which is becoming more and more important and can turn into a lot of work quickly. When faced with an already fully developed application that displays a single object always centered on the screen, switching to a scene graph will only make sense in very few situations. However, when starting a new project it can never hurt to start using a scene graph. If the application turns out to be too simple for a scene graph going back won’t be a big problem. But the amount of useful functionality that a scene graph provides, especially in it’s domain of loading, processing and rendering scenes, can become addictive pretty quickly. Try it, you might enjoy it! References [1] Mason Woo et.al. OpenGL(R) Programming Guide: The Official Guide to Learning OpenGL, Version 1.2. Addison-Wesley Pub Co, 1999. [2] James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes. Computer Graphics, Principles and Practice, Second Edition. Addison-Wesley, Reading, Massachusetts, 1990. Overview of research to date. [3] Dirk Reiners, Gerrit Voss, and Johannes Behr. OpenSG Basic Concepts. In OpenSG 2002 Symposium, Darmstadt, 01 2002. [4] John Rohlf and James Helman. Iris performer: A high performance multiprocessing toolkit for real-time 3d graphics. Proceedings of SIGGRAPH 94, pages 381–395, July 1994. ISBN 0-89791-667-0. Held in Orlando, Florida. [5] Paul S. Strauss and Rikk Carey. An object-oriented 3D graphics toolkit. In Edwin E. Catmull, editor, Computer Graphics (SIGGRAPH ’92 Proceedings), volume 26, pages 341–349, July 1992.