GENERATE ROUGH TOOL-PATHS FROM UNORGANIZED POINT-CLOUD DIRECTLY.doc

generate 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- sections be m, the point-cloud slicing algorithm is depicted below.(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.(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 algorithms only aim at one layer.in this section a data-structure named tool-path net (tp-net) is constructed. data storage and tool-path computation are based on this data structure. several key definitions used for building the data structure are given below firstly.intersecting point: the cutting plane cutting a point-sequence-curve will get several intersecting points (fig. 2a). give each intersecting-point a tendency, which stands for the slope.tool path; two adjacent intersecting points can form a tool path if their tendency variation belongs to one of the four types; 3-2; 3-1; 1-2; 1-1 (fig. 2b). one tool-path node (tp-node) is used to store one tool-path(fig. 2c), it includesbefore creating tool-path net, the size of cross-section data in one cutting plane should be expanded to avoid the machining errors shown in fig. 3a. if the cutter radius is r, the size of the original data in one cutting plane is a x b , then the size of the expanded data will be (a + 2r) x (b + 2r) (fig. 3b).fig. 3 expand cross-section data to avoid machining errors(1) build a head-node-array in which each element will link the tp-node list of the corresponding row.(2) for( i =0; i tpx and tfaxp* tp.x, rplll and t can be classified as the same sub-cut-area.we define a parameter k to mark number of sub-cut-area. our algorithm for partitioning sub-cut-areas is described as follows.1) start from the first row, find an unmarked node t (it isnt used to partitioned and 71 c = 0) in the tp-net. if not found, all the sub-cut-areas have been partitioned, stop the cycle procedure (break). if found, construct a new sub-cut-area, set tpa as the root node, let t c = k, and go to the next step.2) in the next row of ri, find the first unmarked node (tpnj c = 0) that can be classified as the same sub-cut-area with tpoi (using the same sub-cut-area criterion). if found, let t c = k and link rpn| and t, together. repeat this step line by line in the tp-net until no more nodes can be classified as the same sub-cut-area.fig. 4c shows three sub-cut-areas are acquired after the whole partition process is finished.1.4 compute tool-compensation contour for every sub-cut-areaduring machining the cutter cant travel along the contour of a sub-cut-area directly, otherwise interference will occur. the contour of each sub-cut-area should compensate a cutter-radius.in fact, we need compute the compensation cutter-locations for every row in a sub-cut-area. the corresponding algorithm is described as follows.as shown in fig. 4d, cutter radius is r, the interval distance between two rows is w, and the cutter circle occupies 2ri w + 1 rows. for the right point of a tp-node in the ;th row, the interference-free cutter location (*c,.vc) can be computed asfollows.similarly, the interference-free cutter location of left point can be computed as follows.undercutting and overcutting m*y occur in computation of cutter-location (fig. 5). to avcid the errors shown in fig. 5b and fig. 5c, adjacent sub-cut-artis should be considered. liropping back several rows can avoid the ovsreutting error in fig. 5d. let cutter radius be p, :ow interval be w, /?hrad point to the root node of sub-cut-area, and paa point to the tail node. for each sub-cut-area, apply the following processes can avoid undercutting and overcutting in fig. 5.1.5 delete uncuttable areas for every sub-cut-areaa sub-cut-area may have some uncuttable tp-nodes and the adjacent uncuttable tp-nodes form an uncttable area. fig. 6 shows three kinds of uncuttable areas. to testify a tp-node is uncuttable, we need inspect if its left cutter-location and right cutter-location satisfy the inequation cxc= crxc. if the inequation come into existence, the cutter cannot walk along the tp-node. major steps for dealing with the uncuttable areas are presented below.(1) if the uncuttable tp-nodes lie in the middle of a sub-cut-area, delete them and separate the sub-cut-area into two areas (fig. 6a and fig. 6b).(2) if the uncuttable tp-nodes lie in the tail (or head) of a sub-cut-area, delete them directly (fig. 6c).(3) reset the root pointer (/?head) and the tail pointer (/?ul|) of the sub-cut-area.1.6 optimal tool-path link based on zigzag millingall the tp-nodes in a sub-cut area are linked one by one by means of a zigzag pattern (fig. 4e), which forms a tool path of the sub-cut-area. when traveling from one sub-cut-area to another sub-cut-area, the cutter should be raised to a safe plane and start an empty-journey to avoid collision. for a few sub-cut-areas, they should be ordered to reduce empty-journey and enhance the machining efficiency. it can be transformed into a problem of traveling sales man6.2 tool path generation and cutting experimentin this research, the methodologies and algorithms are implemented by means of a personal computer equipped with a piv 2.0 ghz cpu and 256 mb ram. visual c+ running under the windows xp operating system is our programming tool.fig. 7a illustrates the unorganized data of a sculpture surface part, including a total of