Rokne, JonLiu, Xin2014-01-072016-02-112014-01-072013http://hdl.handle.net/11023/1245Lens effects play an important role in the realism and aesthetics of graphical rendering. Although a wide range of lens effect simulation algorithms have been proposed in computer graphics, we found that realistic lens effect simulation is still very costly in terms of computing time. In this thesis, we have developed efficient algorithms for rendering images with realistic lens effects. We first strived to improve the efficiency of the physically correct distributed ray tracing algorithm by speeding up the fundamental ray-object intersection operations on a GPU. This work brought forth a new acceleration structure built on the top of a uniform grid, called the micro 64-tree, and a new grid traversal algorithm based on the micro 64-tree. The micro 64-tree speeds up the distributed ray tracing by an order of magnitude compared to algorithms based on the uniform grid. However, it does not improve the computational complexity of the distributed ray tracing algorithm, which is proportional to the number of sampling rays per pixel. A main benefit of distributed ray tracing is that it uses correct visibility and thus can render partial occlusions properly. Observing that the visibility of a lens can be mostly covered by a few representative views, we then proposed a new algorithm that synthesizes lens effects from sparse views. The sparse-view based algorithm can produce high quality lens effects close to the result of distributed ray tracing, but at a much higher speed. Realizing the fact that synthesizing realistic lens effects in 2D space is also computationally expensive, we finally proposed a novel lens effect simulation method based on a physical lens, which “calculates” the complicated optics with the instant physical process of lens imaging. Although the algorithm is still not mature partially because of hardware limitations, it is the first attempt in computer graphics that inserts a physical lens into the graphical rendering pipeline. The physical lens based algorithm can synthesize images incorporating various lens effects with a very low computational complexity.engUniversity of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.Computer ScienceComputer GraphicsRenderingLens Effect SimulationRay TracingAcceleration StructureMicro 64-TreeSparse ViewBokehPseudo 3D DisplayGPU Algorithmsdoctoral thesis10.11575/PRISM/25840