Please use this identifier to cite or link to this item: https://hdl.handle.net/1822/71756

TitleA quantum algorithm for ray casting using an orthographic camera
Author(s)Alves, Carolina
Santos, Luís Paulo
Bashford-Rogers, Thomas
Keywordsray tracing
quantum computing
ray casting
Grover's algorithm
complexity
Issue date2019
PublisherIEEE
CitationC. Alves, L. P. Santos and T. Bashford-Rogers, "A Quantum Algorithm for Ray Casting using an Orthographic Camera," 2019 International Conference on Graphics and Interaction (ICGI), Faro, Portugal, 2019, pp. 56-63, doi: 10.1109/ICGI47575.2019.8955061.
Abstract(s)Quantum computing has the potential to provide solutions to many problems which are challenging or out of reach of classical computers. There are several problems in rendering which are amenable to being solved in quantum computers, but these have yet to be demonstrated in practice. This work takes a first step in applying quantum computing to one of the most fundamental operations in rendering: ray casting. This technique computes visibility between two points in a 3D model of the world which is described by a collection of geometric primitives. The algorithm returns, for a given ray, which primitive it intersects closest to its origin. Without a spatial acceleration structure, the classical complexity for this operation is O(N). In this paper, we propose an implementation of Grover's Algorithm (a quantum search algorithm) for ray casting. This provides a quadratic speed up allowing for visibility evaluation for unstructured primitives in O(√N). However, due to technological limitations associated with current quantum computers, in this work the geometrical setup is limited to rectangles and parallel rays (orthographic projection).
TypeConference paper
URIhttps://hdl.handle.net/1822/71756
ISBN978-1-7281-6379-6
e-ISBN978-1-7281-6378-9
DOI10.1109/ICGI47575.2019.8955061
Publisher versionhttps://ieeexplore.ieee.org/document/8955061
Peer-Reviewedyes
AccessOpen access
Appears in Collections:CCTC - Artigos em atas de conferências internacionais (texto completo)

Files in This Item:
File Description SizeFormat 
Quantum_Algorithm.pdf307,94 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu ORCID