With the progress of computers and peripheral devices. the application of computer graphics in teal world is ever-widening. Especially, animation is used widely in the entertainment industry, education, and scientific research. In these areas, scan-line methods have been used widely for fast image generation. A fast scan-line algorithm for a raster-scan graphics display is proposed based on an observation that a sequence of successive image frames in animation mostly consists of still objects with relatively few moving objects. In the proposed algorithm, successive images are generated using the background image composed of still objects only, and moving image composed only of moving objects. The color of each pixel in the successive images is then determined by one, which is nearer from eye, from the two candidate pixels, where one is from the background image and the other is from the moving image. The background image is generated once in the whole process, while the moving image is generated using an interpolation of two images generated at the start and end time of the given time interval whenever the successive images are generated. For the purpose of fast shadow generation, the shadows are classified into three groups, i.e., basic shadows generated by still objects on the still objects, still shadows generated by still objects on the moving objects, and moving shadows generated by moving objects on both still objects and moving objects. These shadow can be generated very quickly by utilizing the frame coherence. According to the experimental results, a speed up factor of 3.2 to 12.8, depending on the percentage of the moving objects among all objects, was obtained using our algorithm, compared to the conventional scheme not utilizing the frame-to-frame image coherence.
Ray tracing has been used for generating quality images in various applications. A problem with ray tracing is its computing time, which becomes more severe when one wants to create a sequence of image frames for animation purposes. Most efforts so far have been targeted to reducing the processing time of still images. In this thesis, a two-pass ray tracing algorithm which reduces the ray tracing time for a sequence of still images containing moving objects, based on a ray classification scheme according to which rays are classified into basic set and active set is proposed. Basic set(B-set) consists of rays which do not intersect any swept volume of the moving objects, while active set(A-set) consists of rays that intersect at least one swept volume of the moving objects. Ignoring the set-up cost for generating data structures and preparation of the initial image, speed-up factors which denote the speed up of the proposed scheme compared to the conventional one were distributed from 5 to 13 for several examples consisting of a sequence of 10 to $10^5$ still images.
A parallel hardware accelerator consisting of N processors, object memory, VME bus to interface to the host computer, and local bus to transfer data between processors and object memory is also proposed for fast ray tracing. In the proposed system, each processor which consists of adder, multiplier, register file, local memory, and control logic is responsible for generating the corresponding portion of the whole image using the cell traversal scheme and operates asynchronously to maximally utilize the hardware resources. The proposed architecture having only one processor generates several test images 48.71 - 57.76 times faster than 40MIPS Solbourne workstation.
컴퓨터와 주변장치의 발전과 더불어 컴퓨터 그래픽스의 응용분야는 매우 넓어지고 있다. 특히, 애니메이션은 오락분야, 교육분야, 과학분야등에 널리 쓰인다. 이들 분야에서, 고속의 이미지 생성을 위해 스캔라인 기법이 널리 쓰인다. 본 논문에서는 애니메이션을 위해서 제작되는 연속적인 이미지는 소수의 이동물체와 다수의 고정물체로 구성된다는 사실을 토대로 고속으로 연속적인 이미지를 생성하기 위한 스캔라인 기법을 제안하였다. 제안된 알고리즘에서는 고정물체만으로 구성된 배경 이미지와 이동물체만으로 구성된 이동 이미지를 이용하여 여러장의 연속 이미지를 생성한다. 연속 이미지의 한 화소의 색은 고정 이미지와 연속 이미지의 해당화소 중에서 눈에서 가까운 이미지의 화소의 색이된다. 배경 이미지는 여러장의 이미지를 만드는 전 과정을 통해서 한번만 제작하면 되지만, 이동 이미지는 주어진 시간 간격의 처음과 마지막에 존재하는 두 이미지를 interpolation하여 연속 이미지를 제작할 때마다 제작한다. 이미지의 질을 강화하기 위한 그림자를 고속으로 생성하기 위하여, 모든 그림자를 고정물체에 의하여 고정물체상에 그려지는 기본 그림자와 고정물체에 의해서 이동물체 상에 그려지는 이동 그림자, 이동물체에 의해 이동물체와 고정물체 상에 그려지는 이동 그림자로 분류하였다. 제안된 알고리즘에서는 이러한 그림자들을 이미지의 유사성을 이용하여 고속으로 발생 시킨다. 실험 결과에 의하면 제안된 알고리즘을 이용할 경우 기존의 알고리즘을 이용한 경우보다 3.2에서 12.8배 까지 고속으로 이미지를 제작하였으며, 가속되는 정도는 이미지를 구성하는 전체 물체중에서 이동물체가 차지하는 비율에 따라 변한다.
광선추적기법은 고화질의 이미지를 필요로하는 여러 그래픽 응용프로그램에서 이용 된다. 광선추적기법의 최대의 문제점은 이미지 제작시간이며, 이 제작시간은 애니메이션을 위해 연속적인 여러장의 이미지를 만들때는 큰 문제점으로 부각된다. 지금까지 진행되온 대다수의 연구는 한장의 고정 이미지를 고속으로 제작하는 방법에 집중 되었다. 본 논문에서는 광선들을 기본 광선과 활성 광선으로 분류하는 광선 분류법을 기초로하여 연속적인 여러장의 이미지를 고속으로 생성하는 두단계 광선 추적 알고리즘을 제안하였다. 기본 광선은 이동물체가 형성하는 이동 체적과 교차를 이루지 않고 이미지의 변화에 기여할 수 없는 광선이며, 활성 광선은 한개의 이동체적이라도 만나게되어 이동물체의 위치에 따라 이미지의 변화를 가져올 수 있는 광선이다. 데이타 구조의 작성, 초기 이미지의 작성, 광선의 분류와 같은 초기화 비용을 무시하면, 기존의 기법을 이용한 이미지 제작 속도에 비해 제안된 알고리즘을 이용한 경우 이미지의 종류에 따라 5배에서 13배정도 빠르게 이미지를 제작하였다.
또한, 본 논문에서는 N개의 프로세서와 object memory, host 컴퓨터와 통신을 위한 main bus, 프로세서와 메모리간의 정보 전송을 위한 local bus로 구성된 병렬형 하드웨어 가속기를 고속의 광선추적을 위하여 제안 하였다. 제안된 시스템의 각 프로세서는 덧셈기, 곱셈기, 레지스터 파일, local 메모리와 제어부로 구성되어 있으며, 전체 이미지의 일부를 cell traversal 기법을 이용하여 제작하며 하드웨어 자원을 최대한으로 이용하기 위하여 비동기적으로 동작된다. 제안된 가속기를 이용하여 이미지를 제작한 결과, 40MIPS의 Solbourne 워크스테이션보다 48.7에서 57.8배의 속도로 이미지를 제작하였다.
