Technical Report(pdf, abstract)

Uniform sampling on/near the surfaces of complex geometric objects has
application in mesh generation, remodeling, motion planning, and others.
In short, it provides an alternate and approximate way to represent the object
which for some applications can be used in place of the original object,
either to save computation time or to remove detail that is not
needed, and perhaps even distracting.
For example, in motion planning, high clearance paths can be safer
and in some cases computed more efficiently by ignoring
concavities on obstacle surfaces.
However, generating samples that uniformly cover a surface becomes
more difficult and costly as the model complexity increases.
In this work, we present a two phase approach to generate points
that ``nearly'' uniformly cover model surfaces by first decomposing
the model into approximately convex pieces and then uniformly sampling on
the convex hull surfaces of these pieces.
We implement the first phase using Fast Approximate Convex Decomposition (FACD),
a method that efficiently partitions the model into approximately convex pieces
such that their concavity does not exceed a specified value tau;
we call the convex hulls of the approximately convex pieces tau-surfaces.
Then, the Uniform Obstacle-Based Probabilistic Roadmap Method (UOBPRM) is
used to generate points distributed uniformly on the tau-surfaces
by finding intersections between uniformly sampled fixed length line segments
and the tau-surfaces.
Operating on the tau-surfaces instead of the the original surfaces is
expected to be more efficient since the convex hulls have reduced complexity
over the original input model.
We evaluate our method with respect to time and error in average distance to
the original input model and show that this scheme produces increased efficiency
in time with reduced distance error as compared to using a convex hull approximation
of the entire model and other decomposition approaches.
We also show that our sampling strategy can be used in a sampling-based
motion planning method to solve a challenging motion planning
problem more efficiently than previous methods.