Project Progress Update
Things That I Have Done
Since the
project proposal time, I have mainly focused on reading code, and
reading related literature. The two sets of code that I need to
get familiar with are the PQP implementation available from its project
website, and the GPU collision detection code written by Christian
Lauterbach. I have finished the PQP code, and I am currently in the
middle of exploring Christian's GPU code.
The literature I have covered was mainly recent publications on
collision detection and proximity queries. Because of my (lack of)
background I do need to cover basics by reading textbooks like Real
Time Collision Detection, and by now I have got an essencial grasp of
this topic.
The Next Step
I plan to get my hands dirty and start implementing PQP on the GPU
platform. In order to achieve much better performance than a naive
migration of code, considerations need to be taken in the design of
algorithms. The base-line goal is to get an implementation running at
the end of the semester, and profiling and optimization could follow
from that, given more time. At the same time, more reading of
literature is necessary in search of existing methods and/or
inspirations that fit the GPU platform better than the original
implementation.
Answers to Questions 2, 3, 4
The goal of this project has not been changed. I feel confident that I could deliver on time, surprise-free.
Project Proposal Slides
Robotics Project Proposal
Motivation and Overview
This project will focus on fast proximity queries with Swept
Sphere Volumes (SSVs) on the GPUs. The idea is to utilize the
tight-fitting property of SSVs, and to accelerate the bottleneck
part of intersection tests and distance computation between SSVs
with parallelism of GPU computing, so that the computation cost of
proximity queries using SSVs could be optimized. The GPU acceleration
algorithm will be built on Christian Lauterbach et al.'s framework of
GPU collision detection with BVHs.
Proximity queries, including collision detection , and
both exact and approximate distance
computation, are fundamental problems that arise
in applications such as dynamics simulation, virtual prototyping,
computer animation, surgical simulation, robot motion planning, haptic
rendering, molecular modeling, and computer games.
A number of proximity query algorithms have been studied in
the literature, and the most general and versatile among them are based
on bounding volume hierarchies (BVHs). BVHs of different bounding
volumes (BVs) display different degrees of efficiency, and for each
type of bounding volume there is always the trade-off between the
tightness of fit and the speed of operations between two
such volumes. This project chose to use SSVs, which fit the
underlying objects tightly but require relatively complex operations
for proximity queries, and the goal is to accelerate these operations
with GPUs, so that SSVs would have both tightness of fit and low
proximity query cost..
The fast development of GPU computing has the potential of
accelerating many types of
computations, as long as they lend themselves to a parallel
reformulation. Within the GAMMA group a lot of work is underway that
leverages GPU parallelism to accelerate BVH construction and
traversal in the context of both ray tracing and collision detection.
This project will be built upon these previous efforts. It will
incorporate the SSVs into the existing framework, as well
as extend the system to handle separation distance
computation in addition to collision detection.
Prior Works
Due to space limit, only the directly related literature is
presented here. In [1] a new family of BVs was presented for fast
proximity queries. These BVs are the Minkowski sum or convolution of
three core primitive shapes (point, line, and rectangle), and a sphere.
They are named Point Swept Sphere (PSS), Line Swept Sphere (LSS),
and Rectangle Swept Sphere (RSS), respectively. By building a hybrid
BVHs using a combination of the three BVs at each node, it provides
varying tightness of fit that is flexible with the enclosed objects. It
is also relatively simple to perform different proximity queries since
it involves computing the distance between the primitive core shapes
and subtracting the offset radius of each BV.
Bounding
volume hierarchy has also been studied extensively in the context of
ray tracing acceleration. In [2] and [3] respectively, Christian
Lauterbach et al. propsed efficient algorithms implemented on GPU for
BVH construction and traversal, that enable interactive ray tracing for
dynamic scenes. Another project by Christian Lauterbach et al. is
currently underway that utilizes the same framework to solve collision
detection problem.
Semester Goal
The
minimal goal for this semester
is to develop fast algorithms of collision detection and distance
computation for SSVs on GPU, and to implement them in CUDA. Then if
time permits, a comparison among
different BVs could be made to gain insights into choosing among
existing BVs and designing new BVs for proximity queries. Another
direction of extension to the minimal goal
would be to apply the fast proximity queries on problems like
motion planning.
Novelty
The novelty of this project is the GPU parallel
algorithms of proximity queries with SSVs. Only CPU algorithms
have been proposed before, and completely different
algorithms need to be designed to fully utilize the parallelism of
GPUs. With such algorithms, a meaningful comparison can be done
among different BVs, and such insights could potentially open up new
research problems.