{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T05:03:19Z","timestamp":1775624599715,"version":"3.50.1"},"reference-count":47,"publisher":"ASME International","issue":"2","content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,6,1]]},"abstract":"<jats:p>We describe a graphics processing unit (GPU)-based computational platform for six-dimensional configuration mapping, which is the description of the configuration space of rigid motions in terms of collision and contact constraints. The platform supports a wide range of computations in design and manufacturing, including three- and six-dimensional configuration space obstacle computations, Minkowski sums and differences, packaging problems, and sweep computations. We demonstrate dramatic performance improvements in the special case of configuration space operations that determine interference-free or containment-preserving configurations between moving solids. Our approach treats such operations as convolutions in the six-dimensional configuration space that are efficiently computed using the fast Fourier transform (FFT). The inherent parallelism of FFT algorithms facilitates a straightforward implementation of convolution on GPUs with existing and freely available libraries, making all such configuration space computations practical, and often interactive.<\/jats:p>","DOI":"10.1115\/1.4005776","type":"journal-article","created":{"date-parts":[[2012,5,14]],"date-time":"2012-05-14T22:17:14Z","timestamp":1337033834000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":7,"title":["Rapid Mapping and Exploration of Configuration Space"],"prefix":"10.1115","volume":"12","author":[{"given":"Saigopal","family":"Nelaturi","sequence":"first","affiliation":[{"name":"Spatial Automation Laboratory, University of Wisconsin-Madison, 1513 University Avenue, Madison, WI 53706"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikola","family":"Lysenko","sequence":"additional","affiliation":[{"name":"Spatial Automation Laboratory, University of Wisconsin-Madison, 1513 University Avenue, Madison, WI 53706"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vadim","family":"Shapiro","sequence":"additional","affiliation":[{"name":"Spatial Automation Laboratory, University of Wisconsin-Madison, 1513 University Avenue, Madison, WI 53706"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"33","published-online":{"date-parts":[[2012,5,14]]},"reference":[{"key":"2019100514134357200_c1","doi-asserted-by":"crossref","volume-title":"Robot Motion Planning","author":"Latombe","DOI":"10.1007\/978-1-4615-4022-9"},{"issue":"32","key":"2019100514134357200_c2","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1109\/TC.1983.1676196","article-title":"Spatial Planning: A Configuration Space Approach","volume":"100","author":"Lozano-Perez","journal-title":"IEEE Trans. Comput."},{"issue":"8","key":"2019100514134357200_c3","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1177\/02783640022067157","article-title":"A Survey of Global Configuration-Space Mapping Techniques for a Single Robot in a Static Environment","volume":"19","author":"Wise","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"2019100514134357200_c4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1109\/70.481749","article-title":"A Complete Algorithm for Designing Planar Fixtures Using Modular Components","volume":"12","author":"Brost","journal-title":"IEEE Trans. Rob. Autom."},{"key":"2019100514134357200_c5","first-page":"321","article-title":"Kinematic Synthesis","volume-title":"Formal Engineering Design Synthesis","author":"McCarthy"},{"issue":"3","key":"2019100514134357200_c6","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0010-4485(99)00015-9","article-title":"Dual of Sweep","volume":"31","author":"Ilies","journal-title":"Comput.-Aided Des."},{"issue":"4","key":"2019100514134357200_c7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0010-4485(88)90275-8","article-title":"Application of Vector Sum Operator","volume":"20","author":"Middleditch","journal-title":"Comput.-Aided Des."},{"key":"2019100514134357200_c8","first-page":"67","article-title":"Minkowski Operations for Satellite Antenna Layout","volume-title":"Proceedings of the Thirteenth Annual Symposium on Computational Geometry","author":"Boissonnat"},{"issue":"3","key":"2019100514134357200_c9","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/S0010-4485(99)00014-7","article-title":"A Computing Strategy for Applications Involving Offsets, Sweeps, and Minkowski Operations","volume":"31","author":"Hartquist","journal-title":"Comput.-Aided Des."},{"key":"2019100514134357200_c10","first-page":"31","article-title":"A GPU-Based Voxelization Approach to 3D Minkowski Sum Computation","volume-title":"Proceedings of the 14th ACM Symposium on Solid and Physical Modeling","author":"Li"},{"key":"2019100514134357200_c11","volume-title":"Image Analysis and Mathematical Morphology","author":"Serra"},{"issue":"4","key":"2019100514134357200_c12","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1145\/356827.356833","article-title":"Representations for Rigid Solids: Theory, Methods, and Systems","volume":"12","author":"Requicha","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"2019100514134357200_c13","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0010-4485(90)90051-D","article-title":"Sweeping of Three-Dimensional Objects","volume":"22","author":"Martin","journal-title":"Comput.-Aided Des."},{"issue":"9","key":"2019100514134357200_c14","doi-asserted-by":"publisher","first-page":"902","DOI":"10.1177\/02783649922066646","article-title":"Determination of 6D Workspaces of Gough-Type Parallel Manipulator and Comparison Between Different Geometries","volume":"18","author":"Merlet","journal-title":"Int. J. Robot. Res."},{"key":"2019100514134357200_c15","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1115\/1.3267347","article-title":"An Algorithm for the Workspace of a General n-R Robot","volume":"105","author":"Tsai","journal-title":"ASME J. Mech. Des."},{"key":"2019100514134357200_c16","article-title":"Group Morphology With Convolution Algebras","author":"Lysenko","journal-title":"ACM Symposium on Solid and Physical Modeling 2010"},{"key":"2019100514134357200_c17","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1016\/j.cad.2010.09.007","article-title":"Configuration Products and Quotients in Geometric Modeling","volume":"43","author":"Nelaturi","journal-title":"Comput.-Aided Des."},{"issue":"7","key":"2019100514134357200_c18","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1177\/0278364909352700","article-title":"Generating Uniform Incremental Grids on SO(3) Using the Hopf Fibration","volume":"29","author":"Yershova","journal-title":"Int. J. Robot. Res."},{"key":"2019100514134357200_c19","first-page":"366","article-title":"The Design of Shape Interactions Using Motion Constraints","volume-title":"Proceedings of the 1994 IEEE International Conference on Robotics and Automation","author":"Caine"},{"key":"2019100514134357200_c20","volume-title":"The Complexity of Robot Motion Planning ACM Doctoral Dissertation Awards","author":"Canny"},{"issue":"3","key":"2019100514134357200_c21","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/0004-3702(87)90069-5","article-title":"A Search Algorithm for Motion Planning With Six Degrees of Freedom","volume":"31","author":"Donald","journal-title":"Artif. Intell."},{"issue":"6","key":"2019100514134357200_c22","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1177\/027836499801700604","article-title":"Sliced Configuration Spaces for Curved Planar Bodies","volume":"17","author":"Sacks","journal-title":"Int. J. Robot. Res."},{"issue":"8","key":"2019100514134357200_c23","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1016\/j.cagd.2008.06.006","article-title":"Covering Minkowski Sum Boundary Using Points With Applications","volume":"25","author":"Lien","journal-title":"Comput. Aided Geom. Des."},{"issue":"4","key":"2019100514134357200_c24","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.gmod.2005.11.003","article-title":"Accurate Minkowski Sum Approximation of Polyhedral Models","volume":"68","author":"Varadhan","journal-title":"Graphical Models"},{"issue":"1","key":"2019100514134357200_c25","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0022-4049(91)90131-K","article-title":"Operations on Constructible Functions","volume":"72","author":"Schapira","journal-title":"J. Pure Appl. Algebra"},{"issue":"3","key":"2019100514134357200_c26","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1109\/70.388783","article-title":"Computation of Configuration-Space Obstacles Using the Fast Fourier Transform","volume":"11","author":"Kavraki","journal-title":"IEEE Trans. Rob. Autom."},{"issue":"6","key":"2019100514134357200_c27","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/j.gmod.2003.07.003","article-title":"Computing the Minkowski Sum of Ruled Surfaces","volume":"65","author":"Muhlthaler","journal-title":"Graphical Models"},{"issue":"3","key":"2019100514134357200_c28","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/BF01032731","article-title":"On Discrete Subgroups of the Three-Dimensional Rotation Group","volume":"46","author":"Muradyan","journal-title":"Theor. Math. Phys."},{"key":"2019100514134357200_c29","doi-asserted-by":"publisher","DOI":"10.1115\/1.1421108","article-title":"Engineering Applications of Noncommutative Harmonic Analysis: With Emphasis on Rotation and Motion Groups","volume":"54","author":"Chirikjian","journal-title":"ASME Appl. Mech. Rev."},{"issue":"6","key":"2019100514134357200_c30","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1016\/S0031-3203(99)00152-1","article-title":"Group Morphology","volume":"33","author":"Roerdink","journal-title":"Pattern Recogn."},{"key":"2019100514134357200_c31","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/030601879","article-title":"Sampling Rotation Groups by Successive Orthogonal Images","volume":"30","author":"Mitchell","journal-title":"SIAM J. Sci. Comput. (USA)"},{"key":"2019100514134357200_c32","doi-asserted-by":"crossref","volume-title":"Basic Topology","author":"Armstrong","DOI":"10.1007\/978-1-4757-1793-8"},{"key":"2019100514134357200_c33","doi-asserted-by":"crossref","volume-title":"Differential Geometry and Topology: With a View to Dynamical Systems","author":"Burns","DOI":"10.1201\/9781420057539"},{"key":"2019100514134357200_c34","volume-title":"Algebraic Topology","author":"Hatcher"},{"key":"2019100514134357200_c35","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1109\/JPROC.2004.840301","article-title":"The Design and Implementation of FFTW3","volume-title":"Proc. IEEE","author":"Frigo"},{"key":"2019100514134357200_c36","volume-title":"The Digital Signal Processing Handbook","author":"Madisetti"},{"key":"2019100514134357200_c37","unstructured":"NVIDIA Corporation, 2012, CUFFT Library, Technical Report. Report number PG-05327-040_v01"},{"key":"2019100514134357200_c38","unstructured":"Kl\u00f6ckner, A., Pinto, N., Lee, Y., Catanzaro, B., Ivanov, P., and Fasih, A., 2009, \u201cPyCUDA: GPU Run-Time Code Generation for High-Performance Computing,\u201d Arxiv preprint arXiv, p. 911."},{"key":"2019100514134357200_c39","unstructured":"Min, P.\n          , 2005, BINVOX, \u201cA 3D Mesh Voxelizer.\u201d"},{"key":"2019100514134357200_c40","first-page":"43","article-title":"Real-Time Voxelization for Complex Polygonal Models","volume-title":"Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG 2004)","author":"Dong"},{"key":"2019100514134357200_c41","first-page":"73","article-title":"Single-Pass GPU Solid Voxelization for Real-Time Applications","volume-title":"Proceedings of Graphics Interface 2008","author":"Eisemann"},{"key":"2019100514134357200_c42","first-page":"1","article-title":"Bandwidth Intensive 3-D FFT Kernel for GPUs Using CUDA","volume-title":"International Conference for High Performance Computing, Networking, Storage and Analysis (SC 2008), IEEE","author":"Nukada"},{"issue":"4","key":"2019100514134357200_c43","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1006\/gmod.2000.0525","article-title":"3D Volume Rotation Using Shear Transformations","volume":"62","author":"Chen","journal-title":"Graphical Models"},{"issue":"9","key":"2019100514134357200_c44","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1109\/83.784442","article-title":"Two- and Three-Dimensional Image Rotation Using the FFT","volume":"8","author":"Cox","journal-title":"IEEE Trans. Image Process."},{"issue":"2","key":"2019100514134357200_c45","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1006\/gmip.1997.0420","article-title":"Three-Dimensional Rotations by Three Shears","volume":"59","author":"Toffoli","journal-title":"Graph. Models Image Process."},{"issue":"4","key":"2019100514134357200_c46","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1016\/j.gmod.2005.11.004","article-title":"Rotation of 3D Volumes by Fourier-Interpolated Shears","volume":"68","author":"Welling","journal-title":"Graphical Models"},{"key":"2019100514134357200_c47","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1093\/comjnl\/bxq086","article-title":"GPU Prefilter for Accurate Cubic B-Spline Interpolation","volume":"55","author":"Ruijters","journal-title":"Comput. J."}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4005776\/5498099\/021007_1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/doi\/10.1115\/1.4005776\/5498099\/021007_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T18:13:55Z","timestamp":1570299235000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/doi\/10.1115\/1.4005776\/465791\/Rapid-Mapping-and-Exploration-of-Configuration"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,14]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4005776","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,14]]},"article-number":"021007"}}