Home research People General Info Seminars Resources Intranet

Mukulika Ghosh, Cindy (Hsin-Yi) Yeh, Shawna Thomas, Nancy M. Amato, "Nearly Uniform Sampling on Surfaces with Applications to Motion Planning," Technical Report, TR13-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Apr 2013.
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.