In 3D graphics, the PN triangle method improves visual quality and has a great significance in processing tessellation at the hardware level without software assistance. Processing tessellation at the hardware level, this method turns out to be a solution to a memory bandwidth bottleneck which is a persistent problem in 3D graphics. Despite its significance, however, the conventional PN triangle method has certain defects such as inefficient GE operation and degradation of visual quality. Because the method tessellates a curved surface according to the user-defined fixed LOD (Level Of Detail).
In this thesis, we propose adaptive tessellation of PN triangles using minimum-artifact edge linking. The adaptive tessellation of PN triangles is based on adaptive LOD. Adaptive LOD is used to depict triangles in different detail according to the size of the triangles. This adaptivity results in higher efficiency of tessellation. Adaptive LOD should be decided only by the characteristic of an edge to avoid edge cracking on the sharing edge between neighbor triangles. In this thesis, the adaptive LOD uses the edge LOD, which is decided according to the length of an edge. After deciding the edge LOD, the triangle is divided into inner triangle and outer triangle. The inner triangle is tessellated based on the maximum edge LOD among three edge LOD values of a triangle. The next step is to link the edges between the inner triangle and the outer triangle. The conventional edge linking method gives rise to the problem of artifacts by long edges. However, the proposed minimum-artifact edge linking removes the artifacts by long edges, resulting in better quality of scene. Consequently, through adaptive tessellation of PN triangles using minimum-artifact edge linking, higher efficiency of tessellation and better quality of scene are obtained by adaptivity and minimum-artifact edge linking, respectively.
This thesis also presents a hardware architecture of a PN triangle method using adaptive LOD, which is not a burden for overall 3D graphics hardware. Adaptive PN triangle operation is divided into three parts: LOD evaluation, control point generation, and tessellation, and we distribute them to dedicated hardware part and the other parts which are using conventional GE. This distribution is based on the operation analysis. The dedicated hardware, named as tessellation unit, handles tessellation while the other parts using conventional GE handles LOD evaluation and control point generation.
For hardware cost minimization, we decide the architecture of tessellation unit based on the load balance. Finally, the proposed tessellation hardware that has 3 floating point MAC, 3 register files and a ROM table, is practically demonstrated through VLSI implementation. The hardware, which is described by Verilog HDL and synthesized with a 0.18㎛ 1.8V standard cell library, is operated at 100MHz and it generates 4.2M vertex per second.
PN triangle [1] 기법은 좋은 화질을 얻음과 동시에 하드웨어 상에서 테셀레이션(tessellation)을 수행함으로써 메모리 대역폭을 줄일 수 있다는 점에서 큰 의의가 있다. 그러나 기존의 PN triangle 기법은 사용자가 정해주는 정해진 LOD(Level Of Detail)에 의해 테셀레이션을 수행하기 때문에 비효율적인 GE(Geometry Engine)연산이나 화질 저하가 야기될 수 있다.
본 논문에서는 최소 결함 에지 연결을 이용한 적응 모자이크 기법을 제안한다. 적응 모자이크 기법은 적응 LOD에 근간을 두며 이 적응성 LOD를 이용하여 삼각형의 표현되는 크기에 따라 세밀 정도를 다르게 표현할 수 있다. 이러한 적응성은 고효율의 테셀레이션을 가능하게 한다. 이웃한 삼각형의 공유된 에지에서 발생하는 에지 크랙(edge crack) 문제를 피하기 위해서 적응성 LOD는 에지 자체의 성질에만 기인하여 결정되어야 하고 본 논문에서는 에지의 길이를 이용하는 에지 LOD를 사용하게 된다. 에지 LOD가 결정되면 삼각형을 내부 삼각형과 외부 삼각형으로 나누어서 내부 삼각형은 최대 에지 LOD에 기반을 두어 테셀레이션을 수행하고 그 다음으로 외부 삼각형과 내부 삼각형을 연결하게 된다. 기존의 에지 연결 방법은 긴 에지에 의해서 발생되는 결함을 발생시키지만 최소 결함 에지 연결은 이러한 결함을 제거하여 화질 개선의 결과를 갖게 된다. 결과적으로 제안된 방법을 사용함으로써, 적응성으로 고효율의 테셀레이션을 이룰 수 있고, 최소 결함 에지 연결에 의해서 더 나은 화질을 얻을 수 있다.
또한, 본 논문은 적응 모자이크 기법을 위한 하드웨어 구조를 제안한다. 제안된 하드웨어 구조는 전체적인 3D 그래픽스 하드웨어에 부담이 적게 되는 것을 목표로 한다. 우선, 적응 모자이크 기법에 필요한 연산인 LOD evaluation, control point generation, 테셀레이션을 전용 하드웨어 부분과 GE를 사용하는 부분으로 나눈다. 이 분배는 연산량 분석에 의해서 이루어진 것이다. 테셀레이션 부분은 전용 하드웨어로 처리 되고, 나머지 부분은 GE를 사용하여 처리 된다.
전용 하드웨어의 비용(cost)을 낮추기 위해서, 로드 밸런스(load balance)에 근간을 두고 테셀레이션 유닛의 구조가 결정된다. 이 결과, 3개의 부동 소수점 MAC과 3개의 레지스터 파일(register file)과 롬 테이블(ROM table)로 이루어진 테셀레이션 전용 하드웨어 구조가 얻어진다. 제안된 테셀레이션 전용 하드웨어 구조는 VLSI 구현을 통하여 실제 구현 가능함을 보이고 있으며, 0.18㎛ 1.8V cell library로 100MHz에서 동작하고 초당 4.2M 버텍스(vertex)를 처리하는 성능을 보인다.
