Computing the Shape of Point Clouds

A point cloud is an unorganized collection of a very large number of points usually with just their coordinates and no other information. Such point clouds are increasingly encountered in the form of outputs from 3D scanning devices, 3D from images/sketches, from physically-based simulations, etc. Computing the shape of a point cloud (a curve in 2D and surface in 3D), is known to be a difficult problem. Imagine the game of connecting the dots but with no labels on the points and extend it to higher dimensions. This problem has been the subject of a lot of research over the last 3 decades with many different algorithmic solutions proposed. A robust solution has many applications such as reverse engineering, 3D printing, visualization, machine learning, etc. When posed as a search for the “desired” shape, this problem is most probably NP-hard. Apart from efficiency, the other main challenges include ability to handle non-dense and non-uniform sampling, accuracy to sharp features, robustness and provable reconstruction guarantees – that is, what is the class of point clouds for which the algorithm yields correct results?  In this talk, we will first introduce the problem and its challenges, then describe some of the better known previously proposed solutions and conclude with a brief presentation of work done with my student.
 

Brief Bio:

Dr. S. P. Mudur is presently visiting the School of Technology and Computer Science at TIFR. He got his B.Tech. from IIT Bombay in 1970 and his PhD from TIFR (through University of Mumbai) in 1976. He was with TIFR from 1970 – 1985 and with the National Centre for Software Technology (NCST) from 1985-2002. Since 2002 he is a professor  in the computer science and software engineering department of Concordia University in Montreal, Canada. Dr. Mudur started his research in computer graphics at TIFR in the early 70’s and has continued to do research in that field. His primary focus is on problems in 3D modeling and animation.