Accelerating Geometric Queries for Computer Graphics: Algorithms, Techniques, and Applications
No Thumbnail Available
Date
0000-08-16
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In the ever-evolving context of Computer Graphics, the demand for realistic and real-time virtual
environments and interaction with digitised or born-digital content has exponentially grown.
Whether in gaming, production rendering, computer-aided design, reverse engineering, geometry
processing, and understanding or simulation tasks, the ability to rapidly and accurately perform
geometric queries of any type is crucial. The actual form of a geometric query varies depending
on the task at hand, application domain, input representation, and adopted methodology. These
queries may involve intersection tests as in the case of ray tracing, spatial queries, such as
needed for recovering nearest sample neighbours, geometry registration in order to classify
polygonal primitive inputs, or even virtual scene understanding in order to suggest and embed
configurations as in the case of light optimisation and placement. As the applications of these
algorithms and, consequently, their complexity continuously grow, traditional geometric queries
fall short, when naïvely adopted and integrated in practical scenarios. Therefore, these methods
face limitations in terms of computational efficiency and query bandwidth. This is particularly
pronounced in scenarios, where vast amounts of geometric data must be processed in interactive
or even real-time rates. More often than not, one has to inspect and understand the internal
mechanics and theory of the algorithms invoking these geometric queries. This is particularly
useful in order to devise appropriately tailored procedures to the underline task, hence maximise
their efficiency, both in terms of performance and output quality. As a result, there is an enormous
area of research that explores innovative approaches to geometric query acceleration, addressing
the challenges posed.
The primary focus of this research was to develop innovative methods for accelerating
geometric queries within the domain of Computer Graphics. This entails a comprehensive
exploration of algorithmic optimisations that include the development of advanced data structures
and neural network architectures, tailored to efficiently handle geometric collections. This
research addressed not only the computational complexity of individual queries, but also the
adaptability of the proposed solutions to diverse applications and scenarios primary within the
realm of Computer Graphics but also intersecting domains. The outcome of this research holds
the potential to influence the fields that adopt these geometric query methodologies by addressing
the associated computational challenges and unlocking novel directions for real-time rendering,
interactive simulation, and immersive virtual experiences.
More specifically, the contributions of this thesis are divided into two broad directions for
accelerating geometric queries: a) global illumination-related, hardware-accelerated nearestneighbour
queries and b) application of deep learning to the definition of novel data structures
and geometric query methods.
In the first part, we consider the task of real-time global illumination using photon density
estimators. In particular we investigate scenarios where complex illumination effects, such
as caustics, that can mainly be handled from the illumination theory regarding progressive
photon mapping algorithms, require vast amount of rays to be traced from both the eye sensor
and the light sources. Photons emanating from lights are cached into the surface geometry
or volumetric media and must be gathered at query locations on the paths traced from the
camera sensor. To achieve real-time frame rates, gathering, an expensive operation, needs to
be efficiently handled. This is accomplished by adapting screen space ray tracing and splatting
to the hardware-accelerated rasterisation pipeline. Since the gathering phase is an inherent
subcategory of nearest neighbours search, we also propose how to efficiently generalise this
concept to any form of task by exploiting existing low-level hardware accelerated ray tracing
frameworks. Effectively boosting the inference phase by orders of magnitude compared to the
traditional strategies involved.
In the second part, we shift our focus to a more generic class of geometric queries. The
first work involves accurate and fast shape classification using neural networks architectures.
We demonstrate that a hybrid architecture, which processes orientation and a voxel-based
representation of the input, is capable of processing hard-to-distinguish solid geometry from
the context of building information models. Second, we consider the form of geometric queries
in the context of scene understanding. More precisely, optimising the placement and light
intensities of luminaries in urban places can be a computationally intricate task especially for
large inputs and conflicting constraints. Methodologies employed in the literature usually make
assumptions about the input representation to mitigate the intractable nature of this task. In this
thesis, we approach this problem with a holistic solution that can produce feasible and diverse
proposals in real time by adopting a neural-based generative modelling methodology. Finally,
we propose a novel and general approach to solve recursive cost evaluators for the construction
of geometric query acceleration data structures. This work establishes a new research direction
for the construction of data structures guided by recursive cost functions using neural-based
architectures. Our goal is to overcome the exhaustive but intractable evaluation of the cost
function, in order to generate a high-quality data structure for spatial queries.
Description