A quantum algorithm for ray casting using an orthographic camera

Abstract

Quantum computing has the potential to provide better time complexities (than those achieved with classical computers) for challenging problems solved by classical comput ers or even provide a solution for problems out of reach of classical computers in terms of time complexity (where the time consumed for the resolution of the problem is not prac tical, e.g. thousands of years). Here we’re not solving an unsolvable problem but trying to improve its time complexity. There are several problems in rendering that are good can didates to being solved in a quantum fashion. Although previous research has proposed of theoretical ways of doing this, here we present a practical solution. This work takes a first step in applying quantum computing to one of the most fundamental operations in rendering: ray casting. This technique allows computing 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 complexity for this operation is O(N). The main goal of this work is to use the Grover’s Algorithm, a quantum search algorithm based on ampli tude amplification, to improve the complexity of this problem. This algorithm provides a quadratic speed up allowing for visibility evaluation for unstructured primitives in O( √ N) steps. Due to technological limitations associated with current quantum computers we had to simplify our problem’s structure and in this work the geometrical setup is limited to rectangles and parallel rays (orthographic projection).

A computação quântica tem o potencial de proporcionar melhores complexidades temporais, do que aquelas alcançadas por computadores clássicos, para problemas exigentes resolvidos por estes ou até proporcionar uma solução para problemas fora do alcance dos mesmos em termos de tempo consumido (onde o tempo necessário para a resolução do problema não é prático, como por exemplo milhares de anos). Não estamos a tentar resolver um problema sem solução, mas sim a tentar melhorar a sua complexidade. Existem vários problemas de renderização que são bons candidatos para serem resolvidos de forma quântica. Apesar de existirem algumas propostas teóricas para alcançar isso mesmo, aqui é apresentada uma solução prática. Este trabalho dá um primeiro passo em aplicar a computação quântica a uma das operações mais fundamentais da renderização: ray casting. Esta técnica permite computar visibilidade entre z pontos num modelo 3D do mundo que é descrito por um conjunto de primitivas. O algoritmo retoma, para um dado raio, qual a primitiva que este interseta mais próxima da sua origem. Sem uma estrutura espacial de aceleração, a complexidade desta operação é 0(N). O principal objetivo desta dissertação é usar o algoritmo de Grover, um algoritmo quântico de procura, para melhorar a complexidade deste problema. O algoritmo permite uma aceleração quadrática possibilitando uma avaliação de visibilidade para primitivas não estruturadas em O(v) passos. Devido a limitações tecnológicas associadas com os atuais computadores quânticos, tivemos a necessidade de simplificar a estrutura do nosso problema e, neste trabalho, a configuração geométrica é limitada a retângulos e raios paralelos (projeção ortográfica).