CHINESE JOURNAL OF MECHANICAL ENGINEERINGVol. 20, No. 5, 2007WU ShixiongWANG ChengyongFAN JingmingSchool of Mechanical and ElectricalEngineering,Guangdong University of Technology,Guangzhou 510006, ChinaGENERATE ROUGH TOOL-PATHS FROM UNORGANIZED POINT-CLOUD DIRECTLYAbstract: An approach is presented to generate rough interference-free tool-paths directly from massive unorganized data in rough machining that is performed by machining volumes of material in a slice-by-slice manner. Unorganized point-cloud is firstly converted to cross-section data. Then a robust data-structure named tool-path net is constructed to save tool-path data. Optimal algorithms for partitioning sub-cut-areas and computing interference-free cutter-locations are put forward. Finally the tool-paths are linked in a zigzag milling mode, which can be transformed into a traveling sales man problem. The experiment indicates optimal tool paths can be acquired, and high computation efficiency can be obtained and interference can be avoided successfully. Key words: Rough machining Tool path Unorganized point-cloud0 INTRODUCTIONReverse engineering plays an important role in design and manufacturing. It consists of three major phases: Digitizing the physical object with measuring devices; Constructing a CAD model; (3) Realizing the geometric model with rapid prototyping (RP) or NC machining. Among the three phases, the second phase is time consuming. A fast mode that omits the second phase is put forward in this paper, in which tool-paths can be generated directly from point-cloud d?ta.Most recent commercial CAD/CAM software systems are capable of generating tool-paths from surf&co and solid models. However, conversion of point data to tool path cannot be found in these software systems. Literature about tool-path generation from relatively measured data can be found in LIU, et al11 and PARK, et al21. The algorithm of LIN, et al11 generates tool-paths by constructing a Z-map model. It is robust but requires a large amount of memory as well as excessive computation time. PARK, et alPI, employed 2D curve offsetting and polygonal chain intersection algorithms to generate tool-path from regular measured data, which may be interference in curve offsetting.Because complicated free-form products frequently need multiple scans to obtain sufficient information, which will generate unorganized point cloud easily after data registration. For the finishing tool-path generation from unorganized point-cloud, the classic algorithm presented by HWANG, et alpl, can be adopted. First construct triangulated surfaces from unorganized data, then generate finishing tool-paths from the triangulated surfaces. While literature about rough tool-path generation from unorganized cloud data cannot be found. This paper focuses on an efficient procedure through which rough interference-free tool-paths can be directly generated from unorganized point-cloud.1 GENERATE ROUGH TOOL-PATHS FROM UNORGANIZED POINT-CLOUD1.1 Convert the unorganized point-cloud into cross-section dataIt is very difficult to generate rough tool-paths from unorganized point-cloud, so we first convert the unorganized point cloud into cross-section data by using a slicing algorithm similar to Ref. 4. We use a series of parallel cross-sections to slice the unorganized point-cloud (Fig. la). The points in one section can be regarded as a dispersed curve that is defined as a point-sequence-curve in this paper. Let the number of parallel cross-Received December 6, 2006; received in revised form May 18, 2007; accepted May 24, 2007sections be m, the point-cloud slicing algorithm is depicted below.For(j=0;/m;i+)(1) For a cross-section F move a micro distance d in two sides and get two parallel planes, Fn and Fa (Fig. lb). All the unorganized points between Ft and F, form into a point set At, and points between /, and Fa form m*.o Ii.Cross-section plailes1r,)f /&*FI2nJ&k&i,yJy/Sw&%tilW/r,iAo(a)Cross-sections(b)Generate point-sequence-curveFig. 1 Point-cloud slicing(2)For each point pk in A, find in fl, the nearest point pm.Compute the intersect point between the segment pk - pm and thecross-section Fh and put the intersect point into a point set Q.(3)All the points in C, are ordered to get the finalpoint-sequence-curve in the cross-section Ft. First find the xcoordinate range of C xmin, ij, divide it into n small sections,and insert point in C, into the corresponding section according toits x coordinate value. And then the points in every section areordered according to x coordinate value.1.2 Build data structure tool-path netThe rough machining in this paper is performed in a slice-by-slice manner. Because all layers (each is parallel to the xy plane) use a similar method to generate tool-paths, the following al