© 2013 IEEE. Nowadays, industrial robot applications are required to customize the manufacturing of diverse products to reduce both downtime and standoff variability. The two methods for robot programming are regularly implemented to carry out that goal. The first one, online programming, requires a specialized operator to guide the robot through desired poses, and the quality of the result is directly limited by his skill level. On the other side, off-line programming uses software packaging to simulate robot applications before their implementation. It reduces downtime with respect to online programming but requires additional calibration steps. In this paper, a novel procedure is presented to obtain accurate surface approximations by combining linear interpolations generated during online programming with a triangulated surface reconstruction of a workpiece surface representation. The method uses a point cloud instead of a predefined mesh to reduce the standoff variability between the robotic tool center point and the surface. Additionally, a technique based on a penalized least squares method was implemented to smooth the trajectory, including position and orientation. The proposed methodology was validated with three well-known case studies involving real trajectories, with simulations in MATLAB and RobotStudio, as well as by experimentation with an industrial ABB robot. The quality of the results demonstrates a great efficiency of this method for path generation based on surface reconstruction.