No Cover Image

E-Thesis 223 views 131 downloads

Investigating ray tracing algorithms and data structures in the context of visibility. / RAVI KAMMAJE

Swansea University Author: RAVI KAMMAJE

Abstract

Ray tracing is a popular rendering method with built in visibility determination. However, the computational costs are significant. To reduce them, there has been extensive research leading to innovative data structures and algorithms that optimally utilize both object and image coherence. Investiga...

Full description

Published: 2009
Institution: Swansea University
Degree level: Doctoral
Degree name: Ph.D
URI: https://cronfa.swan.ac.uk/Record/cronfa42220
Tags: Add Tag
No Tags, Be the first to tag this record!
first_indexed 2018-08-02T18:54:10Z
last_indexed 2020-09-04T03:03:02Z
id cronfa42220
recordtype RisThesis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2020-09-03T09:07:01.1979162</datestamp><bib-version>v2</bib-version><id>42220</id><entry>2018-08-02</entry><title>Investigating ray tracing algorithms and data structures in the context of visibility.</title><swanseaauthors><author><sid>3d5d632d71d8608f62a9f27b033aafd4</sid><firstname>RAVI</firstname><surname>KAMMAJE</surname><name>RAVI KAMMAJE</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2018-08-02</date><abstract>Ray tracing is a popular rendering method with built in visibility determination. However, the computational costs are significant. To reduce them, there has been extensive research leading to innovative data structures and algorithms that optimally utilize both object and image coherence. Investigating these from a visibility determination context without considering further optical effects is the main motivation of the research. Three methods - one structure and two coherent tree traversal algorithms - are discussed. While the structure aims to increase coherence, the algorithms aim to optimise utilization of coherence provided by ray tracing structures (kd-trees, octrees). RBSF trees - Restricted Binary Space Partitioning Trees - build upon the research in ray tracing with kd-trees. A higher degree of freedom for split plane selection increases object coherence implying a reduction in the number of node traversals and triangle intersections for most scenes. Consequently, reduced ray casting times for scenes with predominantly non-axis-aligned triangles is observed. Coherent Rendering is a rendering method that shows improved complexity, but at an absolute performance that is much slower than packet ray tracing. However, since it led to the creation of the Row Tracing' algorithm, it is described briefly. Row Tracing can be considered as an adaptation of Coherent Rendering, scanline rendering or packet ray tracing. One row of the image is considered and its pixels are determined. Similar to Coherent Rendering, an adapted version of Hierarchical Occlusion Maps is used to identify and skip occluded nodes. To maximize utilisation of coherence, the method is extended so that several adjacent rows are traversed through the tree. The two versions of Row Tracing demonstrate excellent performance, exceeding that of packet ray tracing. Further, it is shown that for larger models (2 million+ triangles). Row Tracing and Packet Row Tracing significantly outperform Z-buffer based methods (OpenGL). Row tracing show's scalability over scene sizes leading to a rendering method that has fast rendering times for both large and small models. In addition it has excellent parallelisation properties allowing utilisation of multiple cores with ease. Thus, the Row Tracing and Packet Row Tracing algorithms can be considered as the significant contributions of the Ph.D. These data structures and algorithms demonstrate that ray tracing data structures and adaptations of ray tracing algorithms exhibit excellent potential in a visibility context.</abstract><type>E-Thesis</type><journal/><publisher/><keywords>Computer science.</keywords><publishedDay>31</publishedDay><publishedMonth>12</publishedMonth><publishedYear>2009</publishedYear><publishedDate>2009-12-31</publishedDate><doi/><url/><notes/><college>COLLEGE NANME</college><CollegeCode>COLLEGE CODE</CollegeCode><institution>Swansea University</institution><degreelevel>Doctoral</degreelevel><degreename>Ph.D</degreename><apcterm/><lastEdited>2020-09-03T09:07:01.1979162</lastEdited><Created>2018-08-02T16:24:28.4797839</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>RAVI</firstname><surname>KAMMAJE</surname><order>1</order></author></authors><documents><document><filename>0042220-02082018162437.pdf</filename><originalFilename>10797922.pdf</originalFilename><uploaded>2018-08-02T16:24:37.5130000</uploaded><type>Output</type><contentLength>28643523</contentLength><contentType>application/pdf</contentType><version>E-Thesis</version><cronfaStatus>true</cronfaStatus><embargoDate>2018-08-02T00:00:00.0000000</embargoDate><copyrightCorrect>false</copyrightCorrect></document></documents><OutputDurs/></rfc1807>
spelling 2020-09-03T09:07:01.1979162 v2 42220 2018-08-02 Investigating ray tracing algorithms and data structures in the context of visibility. 3d5d632d71d8608f62a9f27b033aafd4 RAVI KAMMAJE RAVI KAMMAJE true false 2018-08-02 Ray tracing is a popular rendering method with built in visibility determination. However, the computational costs are significant. To reduce them, there has been extensive research leading to innovative data structures and algorithms that optimally utilize both object and image coherence. Investigating these from a visibility determination context without considering further optical effects is the main motivation of the research. Three methods - one structure and two coherent tree traversal algorithms - are discussed. While the structure aims to increase coherence, the algorithms aim to optimise utilization of coherence provided by ray tracing structures (kd-trees, octrees). RBSF trees - Restricted Binary Space Partitioning Trees - build upon the research in ray tracing with kd-trees. A higher degree of freedom for split plane selection increases object coherence implying a reduction in the number of node traversals and triangle intersections for most scenes. Consequently, reduced ray casting times for scenes with predominantly non-axis-aligned triangles is observed. Coherent Rendering is a rendering method that shows improved complexity, but at an absolute performance that is much slower than packet ray tracing. However, since it led to the creation of the Row Tracing' algorithm, it is described briefly. Row Tracing can be considered as an adaptation of Coherent Rendering, scanline rendering or packet ray tracing. One row of the image is considered and its pixels are determined. Similar to Coherent Rendering, an adapted version of Hierarchical Occlusion Maps is used to identify and skip occluded nodes. To maximize utilisation of coherence, the method is extended so that several adjacent rows are traversed through the tree. The two versions of Row Tracing demonstrate excellent performance, exceeding that of packet ray tracing. Further, it is shown that for larger models (2 million+ triangles). Row Tracing and Packet Row Tracing significantly outperform Z-buffer based methods (OpenGL). Row tracing show's scalability over scene sizes leading to a rendering method that has fast rendering times for both large and small models. In addition it has excellent parallelisation properties allowing utilisation of multiple cores with ease. Thus, the Row Tracing and Packet Row Tracing algorithms can be considered as the significant contributions of the Ph.D. These data structures and algorithms demonstrate that ray tracing data structures and adaptations of ray tracing algorithms exhibit excellent potential in a visibility context. E-Thesis Computer science. 31 12 2009 2009-12-31 COLLEGE NANME COLLEGE CODE Swansea University Doctoral Ph.D 2020-09-03T09:07:01.1979162 2018-08-02T16:24:28.4797839 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science RAVI KAMMAJE 1 0042220-02082018162437.pdf 10797922.pdf 2018-08-02T16:24:37.5130000 Output 28643523 application/pdf E-Thesis true 2018-08-02T00:00:00.0000000 false
title Investigating ray tracing algorithms and data structures in the context of visibility.
spellingShingle Investigating ray tracing algorithms and data structures in the context of visibility.
RAVI KAMMAJE
title_short Investigating ray tracing algorithms and data structures in the context of visibility.
title_full Investigating ray tracing algorithms and data structures in the context of visibility.
title_fullStr Investigating ray tracing algorithms and data structures in the context of visibility.
title_full_unstemmed Investigating ray tracing algorithms and data structures in the context of visibility.
title_sort Investigating ray tracing algorithms and data structures in the context of visibility.
author_id_str_mv 3d5d632d71d8608f62a9f27b033aafd4
author_id_fullname_str_mv 3d5d632d71d8608f62a9f27b033aafd4_***_RAVI KAMMAJE
author RAVI KAMMAJE
author2 RAVI KAMMAJE
format E-Thesis
publishDate 2009
institution Swansea University
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
document_store_str 1
active_str 0
description Ray tracing is a popular rendering method with built in visibility determination. However, the computational costs are significant. To reduce them, there has been extensive research leading to innovative data structures and algorithms that optimally utilize both object and image coherence. Investigating these from a visibility determination context without considering further optical effects is the main motivation of the research. Three methods - one structure and two coherent tree traversal algorithms - are discussed. While the structure aims to increase coherence, the algorithms aim to optimise utilization of coherence provided by ray tracing structures (kd-trees, octrees). RBSF trees - Restricted Binary Space Partitioning Trees - build upon the research in ray tracing with kd-trees. A higher degree of freedom for split plane selection increases object coherence implying a reduction in the number of node traversals and triangle intersections for most scenes. Consequently, reduced ray casting times for scenes with predominantly non-axis-aligned triangles is observed. Coherent Rendering is a rendering method that shows improved complexity, but at an absolute performance that is much slower than packet ray tracing. However, since it led to the creation of the Row Tracing' algorithm, it is described briefly. Row Tracing can be considered as an adaptation of Coherent Rendering, scanline rendering or packet ray tracing. One row of the image is considered and its pixels are determined. Similar to Coherent Rendering, an adapted version of Hierarchical Occlusion Maps is used to identify and skip occluded nodes. To maximize utilisation of coherence, the method is extended so that several adjacent rows are traversed through the tree. The two versions of Row Tracing demonstrate excellent performance, exceeding that of packet ray tracing. Further, it is shown that for larger models (2 million+ triangles). Row Tracing and Packet Row Tracing significantly outperform Z-buffer based methods (OpenGL). Row tracing show's scalability over scene sizes leading to a rendering method that has fast rendering times for both large and small models. In addition it has excellent parallelisation properties allowing utilisation of multiple cores with ease. Thus, the Row Tracing and Packet Row Tracing algorithms can be considered as the significant contributions of the Ph.D. These data structures and algorithms demonstrate that ray tracing data structures and adaptations of ray tracing algorithms exhibit excellent potential in a visibility context.
published_date 2009-12-31T03:52:32Z
_version_ 1763752597446983680
score 11.028798

Similar Items