Hardware acceleration technology for 3D graphics becomes ubiquitous from the traditional high-end systems to the portable embedded platforms, as hardware fabrication technology improves. Today's fastest commodity graphics accelerators are still required to produce real-world complex scenes at real-time rates. Furthermore, future graphics hardware must increase not only its geometry and fill rates but also its flexibility. The demand for more detailed lighting and shading is one of the driving forces behind the desire for more flexibility in 3D graphics. The current graphics hardware is going on ceaselessly rendering more polygons and adopting advanced graphics algorithms for photo-realistic rendering.
Removing of the redundant factors in each functional stage of the rendering pipeline directly enhances the processing ability of a graphics accelerator. In the rendering of polygonal models, we have traditionally attempted to quickly remove portions of the model that are invisible with respect to a particular viewpoint in order to reduce the required workloads of the following pipeline stages. One of such approaches is backface culling, which discards the invisible parts of the model at the triangle-level. Generally half of an object is backfacing. In a traditional pipeline, however, backface culling is an efficient technique for reducing the burden of the fragment engines, not for the vertex engines, because it is performed before rasterizing, after vertex transformation.
In this thesis, we enumerate and analyze the reasons why modern graphics accelerators do not use this transparent benefit, and propose the hardware-friendly solution. We have performed backface culling earlier than transform and lighting (TnL) to solve the pipeline redundancy, and named that as early backface culling. This approach requires determining which vertices are visible in the input polygonal meshes. To do this, we proposed SVD (survived vertex decision) algorithm and proved the performance excellence and the hardware feasibility of the proposed architecture.
The SVD algorithm consists of conceptually three parts. First, we have to determine facing of a triangle by calculating the dot product between the facet normal and the eye vector. Second, we have to determine the survival of a vertex by checking the facings of the adjacent triangles sharing that vertex. An arbitrary vertex is shared by on average six triangles in geometrical topology, but the number of shared triangles is fixed to three in the format of a triangle strip. This format is the best optimized representation for triangle meshes and frequently used to save the bandwidth for the geometry data transfers in the performance-oriented applications such as 3D games. We can discard the vertex only when all triangles are invisible. Third, it is required to reassembly the triangle meshes because the input long strip is divided into many substrips as a result of SVD. We assigned a tag for each vertex to reorganize the triangles from the chipped meshes.
This thesis also introduces a high-performance geometry engine architecture using the proposed SVD algorithm, Since early backface culling brings out the new rendering pipelines, we supported an extended API for easy control of a geometry engine; the programmers can heuristically choose the proper pipeline mode in the application. The SVD algorithm was implemented as two forms in hardware; one is hardwired style and another is programmable style. The latter is named as VP-Engine because it is based on the traditional vertex engine. The VP-Engine can be operated as a vertex engine for the conventional tasks or a polygon engine for early backface culling. As the corresponding concept of multi-threading technology of vertex engine, we introduced a hardware looping that iteratively executes a fetched instruction so as to support such dual operation modes. We also suggested the ideas such as the efficient datapath and the scheme of direct vertex cache access in order to optimize the architecture of a geometry engine.
Early backface culling removed half of the triangles and the vertices of the. rendered objects. Sometimes the vertex engine generates the stalls, when a vertex is transformed with a short vertex program. It degrades the overall performance of a geometry engine because of the insufficient determination rate of the survived vertices. However, the backface culling hardware is generally not the bottleneck, since the length of the vertex program is large in most cases. The maximum gain is up to about twice as much as we expected.
The proposed architecture was modeled with C++ language for cycle-accurate simulation, and we analyzed the architecture efficiency with respect to the various parameters that affect the performance. Then it is described with Verilog-HDL at register transfer level. The chip is targeted for operating at 100MHz with Samsung's 0.18um standard cell library. The hardwired BFC unit consists of 72K gates equivalents and the VP-Engine is 188K gate equivalents and 12.5KB memory cells.
오늘날의 3차원 컴퓨터 그래픽스 기술은 이를 가속해주는 하드웨어의 비약적인 발전으로 말미암아, 주로 영화나 게임 콘솔에서만 국한되던 시장이 여러 응용 분야들과 융합ㆍ확대되는 과도기를 거치고 있다. 이러한 시대적 흐름은 필연적으로 새로운 분야에 적합한 그래픽스 하드웨어 설계를 요구한다. 3차원 그래픽스는 3차원 공간에서 모델링된 물체를 2차원의 화면으로 옮기는 작업이다. 이를 수행하는 여러 단계별 프로세스를 렌더링 파이프라인이라 부른다. 그래픽스 하드웨어의 발전은 CPU에서 모든 파이프라인을 처리하던 방식에서 점차적으로 그래픽스 연산에 최적화된 GPU에서 이러한 기능들을 실현하는 방향으로 흘러왔다. 최신의 그래픽스 가속기는 고급 알고리즘을 수용할 수 있는 프로그래머블한 구조를 채택함으로써 과거에 비해 매우 복잡한 장면도 실시간으로 렌더링할 수 있다. 하지만, 실제 세계와 같은 이미지 합성은 아직도 역부족이다.
GPU의 성능을 높이기는 각 파이프라인 단계에서의 불필요한 요소를 제거해줌으로써 가능하다. 전통적인 폴리곤 모델 렌더링에서는 눈에 보이지 않는 부분을 미리 제거해 줌으로써 그래픽스 하드웨어의 연산량을 줄여왔다. 이러한 시도 중의 하나가 폴리곤 컬링 (뒷면 제거 기법)이며, 다면체로 이루어진 물체의 절반이 뒷면이므로 보이지 않는다. 이 기법은 복잡한 폴리곤 메쉬(mesh)를 하드웨어에서 처리하기가 까다롭기 때문에 기하 연산 파이프라인의 후반부에서 처리되고 있다. 따라서, 본 논문에서는 현재의 하드웨어가 이를 활용하지 못하는 이유를 나열ㆍ분석하고, 하드웨어로의 구현 가능한 해결 방법을 제시한다.
폴리곤 컬링을 기하 연산 파이프라인의 최앞단에서 처리하는 방식을 이른 뒷면 제거 방법 (Early Backface Culling)이라 부르기로 한다. 이를 위해선 폴리곤 메쉬로부터 어떤 정점(vertex)이 눈에 보이는지 결정해야 한다. 폴리곤의 뒷면 판별은 평면의 법선 벡터와 눈에서 폴리곤으로 향하는 벡터의 내적을 취하는 전통적인 방법을 그대로 사용한다. 성능을 중시 여기는 응용 프로그램에서는 모델 데이터의 전송 부하를 줄이기 위해, 동일한 정점 프로그램(vertex program)을 사용하는 여러 물체들의 폴리곤 메쉬를 하나의 긴 스트립(strip) 형태로 만들어서 그래픽스 하드웨어로 전달한다. 따라서, 이 포맷에 최적화된 알고리즘이 필요하다. 삼각형 스트립 포맷에서의 임의의 정점은 3개의 이웃한 폴리곤에 의해 공유되고, 이들의 면방항성을 확인하여 정점의 생존 여부를 판별할 수 있다. 이웃한 세 개의 폴리곤이 모두 뒷면일 경우에만 해당 정점은 버려질 수 있다. 이러한 알고리즘을 SVD(survived vertex decision)라 부르기로 한다. 이 방법은 매우 적은 수의 논리 소자로 구현이 가능하며 결과는 강력하다.
또한, 본 학위 논문에서는 위의 방법을 적용한 고성능 기하 연산 엔진의 구조를 제안한다. 사용자는 제공하는 단 하나의 API만으로 기존의 파이프라인을 사용할지 제안하는 이른 뒷면 제거 방법을 이용한 파이프라인을 사용할지 선택할 수 있다. 하드웨어로의 구현은 크게 다음의 두 부분으로 구분된다. 각 폴리곤의 뒷면 판별을 수행하는 하드웨어와 SVD 알고리즘을 처리하는 로직이 그것이다. 전자는 수식을 그대로 하드웨어로 매핑한 hardwired 구조이거나 기존의 정점 엔진을 개조한 프로그래머블한 VP-Engine의 형태로 제공된다. VP-Engine은 정점 엔진(vertex engine)으로도 폴리곤 엔진(polygon engine)으로도 동작이 가능하다. 이를 위해서 정점 엔진의 multi-threading 기법에 상응하는 hardware looping을 도입하여 읽어 들인 하나의 명령어가 여러 번 반복 수행될 수 있도록 지원하였다.
제안하는 구조는 C++ 언어로 명령어 수준에서 모델링한 뒤, 여러 변수에 따른 구조의 효율성에 대해서 분석하였다. 이 결과를 바탕으로 verilog-HDL를 이용하여 RT-수준에서 하드웨어를 기술하고, 칩은 삼성의 0.18um 공정을 사용하여 100MHz에서 동작하도록 제작하였다. Hardwired 폴리곤 컬링 유닛은 72k 게이트, VP-Engine은 188k 게이트와 12.5KB의 메모리로 구성되었다.
제안하는 구조의 성능은 BFC의 연산량이 일정하기 때문에 각 정점마다 적용되는 정점 프로그램의 길이에 의존적이었다. 두 엔진의 작업이 순차적이며 병렬적으로 동작할 경우엔, 선행 작업을 처리하는 엔진에 의해 시스템의 성능이 좌우된다. 하나의 정점 변환에 필요한 연산량이 적을 경우, BFC 유닛이 충분한 속도로 정점의 살생 여부를 결정해 주지 못하여 정점 엔진이 일시적으로 멈추게 되고, 이는 바로 성능 감쇠를 야기시킨다. 하지만, 대부분의 경우 정점 프로그램의 길이가 충분이 길어 BFC 유닛의 살아남는 정점 결정 속도에 영향을 받지 않을 정도로 빨랐다. 따라서, 성능 향상 정도는 예상됐던 대로 최대 2배 가까이 높아졌다.
이른 뒷면 제거 기법을 위해 하드웨어가 추가되었다. 최대 결과를 보장하기 위한 hardwired BFC unit을 병렬로 수행되는 정점 엔진의 속도에 맞춘다면 더 적은 양의 면적을 소모하게 될 것이다. 정점 엔진을 개조한 VP-Engine은 하드웨어의 양이 정점 캐쉬를 무시할 경우 정점 엔진의 약 50% 정도면 충분하다. 또한, 현재의 그래픽스 하드웨어는 여러 개의 정점 엔진을 탑재하고 있으므로, 하나의 VP-Engine의 오버헤드는 성능 향상 정도를 고려할 때 무시할 만 하다고 할 수 있다.
