Carolina Alves
A quantum algorithm for ray casting using an orthographic camera
Alves, Carolina; Santos, Lu�s Paulo; Bashford-Rogers, Thomas
Authors
Lu�s Paulo Santos
Tom Bashford-Rogers Tom.Bashford-Rogers@uwe.ac.uk
Associate Lecturer - CATE - CCT - UCCT0001
Abstract
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).
Citation
Alves, C., Santos, L. P., & Bashford-Rogers, T. (2020). A quantum algorithm for ray casting using an orthographic camera. . https://doi.org/10.1109/ICGI47575.2019.8955061
Conference Name | 2019 International Conference on Graphics and Interaction (ICGI) |
---|---|
Conference Location | Faro, Portugal |
Start Date | Nov 21, 2019 |
End Date | Nov 22, 2019 |
Acceptance Date | Oct 10, 2019 |
Online Publication Date | Jan 13, 2020 |
Publication Date | Jan 13, 2020 |
Deposit Date | Jan 15, 2020 |
Publicly Available Date | Jan 16, 2020 |
Pages | 56-63 |
ISBN | 9781728163789 |
DOI | https://doi.org/10.1109/ICGI47575.2019.8955061 |
Keywords | Index Terms-quantum computing; ray casting; Grover's algorithm; complexity |
Public URL | https://uwe-repository.worktribe.com/output/4884154 |
Files
A Quantum Algorithm For Ray Casting Using An Orthographic Camera
(561 Kb)
PDF
Licence
http://www.rioxx.net/licenses/all-rights-reserved
Publisher Licence URL
http://www.rioxx.net/licenses/all-rights-reserved
Copyright Statement
© 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
You might also like
A wide spectral range sky radiance model
(2022)
Journal Article
Deep learning-based defect inspection in sheet metal stamping parts
(2022)
Conference Proceeding
Deep synthesis of cloud lighting
(2022)
Journal Article
Ensemble metropolis light transport
(2021)
Journal Article
Deception in network defences using unpredictability
(2021)
Journal Article
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search