傳統直線插補器在進行複雜曲面加工的時候會因為大量的加減速導致進給率誤差，利用參數式曲線或曲面插補器進行加工已成為製造業的重要趨勢。目前文獻上所提出的插補器多半以控制系統的角度來討論曲面加工問題並且強調以改善數值控制器的運動規劃功能來達到更好的加工品質。然而這樣的論點通常會增加數值控制系統實作的複雜度以及與CAD/CAM系統整合上的困難。

　　有鑑於此，本研究同時以控制系統與CAD/CAM系統的角度來思考如何建構新一代的曲面加工系統，並且提出一個分散式運動規劃系統的概念來解決現有數值控制參數式插補器無法與CAD/CAM系統整合的問題。本研究所提出的分散式運動規畫系統分成非即時與即時兩部份。在非即時運算的部份，提出應變能最小化模式將刀具位置轉換成二次微分連續的複合曲線。在即時運算的部份，為了能夠在複合曲線上實現連續的速度規劃，本研究提出ㄧ個具備預讀(look-ahead) 功能的曲線插補器，以便在插補運算接近曲線連接點的時候仍然能夠產生正確且連續的運動指令。

　　透過雛型系統的建構以及模擬與實驗結果的分析顯示利用應變能最小化模式以及預讀插補器進行加工可以有效減少由於運動曲線的不連續性所造成的進給誤差。本論文所提出的分散式運動規劃系統可以有效的分配曲面加工系統的運算量並且使得新一代的參數式插補器順利與CAD/CAM系統整合。

　Using parametric interpolators in free-form surface machining is an important trend in modern manufacturing industry because it is believed that toolpaths in terms of parametric curves or surfaces may result in less accelerations/decelerations and feedrate errors compared with conventional methods in which linear interpolators are used for surface machining. However, existing solutions are proposed with only the viewpoint from control system design, that is, to focus on improving the capability of the CNC system and put all motion planning tasks in the CNC system. This makes the CNC system difficult to implement and integrate with modern CAD/CAM systems.

　Seeing the difficulties to integrate modern CAD/CAM systems with techniques developed in many researches on advanced interpolators, in this research, the concept of Distributed Motion Planning System (DMPS) is proposed and implemented according to viewpoints of both control system and CAD/CAM system design. The proposed DMPS is composed of non-real-time and real-time subsystems. In the non-real-time subsystem, a strain energy minimization model (SEMM) is proposed to transform cutter locations into C2 continuous composite curves. In the real-time subsystem, in order to realize smooth velocity profile along composite curves, a look ahead interpolator (LAI) is proposed to generate continuous motion commands near connection points between adjacent curve segments.

　Simulations and experiments based on the prototype system show that feedrate errors induced by the discontinuities of the motion curves can be eliminated by the proposed SEMM and LAI. The proposed DMPS can effectively distribute computational loads of spline-based surface machining and integrate modern CAD/CAM systems with leading edge interpolators.

References
[1] Alintas, Y., K. Erkormaz, “Feedrate optimization for spline interpolation in high speed machine tools,” Annals of the CIRP, Vol. 52, No. 1, pp 297-302, 2003.
[2] Alintas, Y., N. Newell, and M. Ito, “Modular CNC design for intelligent machining: part1: Design of a hierarchical motion control module for CNC machine tools,” Transactions of the ASME Journal of Manufacturing Science and Engineering, Vol. 118, pp. 506-513, 1996.
[3] Alintas, Y., W. K.Munasinghe, “Modular CNC design for intelligent machining: part2: Modular integration of sensor based milling process monitoring and control tasks,” Transactions of the ASME Journal of Manufacturing Science and Engineering, Vol. 118, pp. 514-521, 1996.
[4] Aoki, K., N. Iwazawa, T. Tsujisawa, U. Sakaguchi, and E. Nakawatase, “High-accuracy path-tracking by multi-axis coordination in CNC machines,” 20th International Conference on Industrial Electronics, Control and Instrumentation, IECON 94, Vol. 3, pp.1842-1847, 1994.
[5] Bahr, B., X. Xiao, and K. Krishnan, “A real-time scheme of cubic parametric curve interpoalators for CNC systems,” Computers in Industry, Vol. 45, pp 309-317, 2001.
[6] Borges, C. F., T. Pastva, “Total least squares fitting of Bezier and B-spline curves to ordered data,” Computer-Aided Geometric Design, Vol. 19, pp. 275-289, 2002.
[7] Brechner, E. L., “General tool offset curves and surfaces,” In R. E. Barnhill (eds), Geometry processing for design and manufacturing, SIAM, 1992, pp. 101-121.
[8] Brunnett, G., J. Kiefer, “Interpolation with minimal energy splines,” Computer-Aided Design, Vol. 26, No. 2, pp. 137-144, 1994.
[9] Chen, Y. D., J. Ni, and S. M. Wu, “Real-time CNC tool path generation for machining IGES surfaces,” Transactions of the ASME Journal of Engineering for Industry, Vol. 155, pp. 480- 486, 1993.
[10] Cheng, M. Y., M. C. Tsai, and J. C. Kuo, ”Real-time NURBS command generators for CNC servo controllers,” International Journal of Machine Tools and Manufacture, Vol. 42, No.7, pp. 801-813,2002.
[11] Chivate, P. N., A. G. Jablokow, “Review of surface representations and fitting for reverse engineering,” Computer Integrated Manufacturing Systems Vol. 8, No. 3, pp. 193-204, 1995.
[12] Chou, J. J., D. C. H. Yang, “Command Generation for three-axis CNC machining,” Transactions of the ASME Journal of Engineering for Industry, Vol. 113, pp.305-310, 1991.
[13] Chou, J. J., D. C. H. Yang, “On the generation of coordinated motion of five-axis CNC/CMM machines,” Transactions of the ASME Journal of Engineering for Industry, Vol. 114, pp.15-22, 1992.
[14] Coquillart, S., “Computing offsets of B-spline curves,” Computer-Aided Design, Vol. 19, No. 6, pp. 305-309,1987.
[15] Datta, B. N., “Numerical Linear Algebra and Applications”, Brooks/Cole Publishing Company, 1995,pp.262-264.
[16] DIN, “DIN 66215: CLDATA,” NC-Machinen, Beuth Verlage, Berlin, pp-49-100, 1987.
[17] Du, W. H., J. M. S. Francis, “On the G1 continuity of piecewise Bezier surfaces: a review with new results,” Computer-Aided Design, Vol. 22, No. 9, pp. 556-573,1990.
[18] Duc, E., C. Lartigue, C. Tournier, and, P. Bourdet, “A new concept for the design and the manufacturing of free-form surfaces: The machining surface,” Annals of the CIRP, Vol. 48, No. 1, 1999.
[19] Elber, G., I. K. Lee, and M. S. Kim, “Comparing offset curve approximation methods,” IEEE Computer Graphics and Applications, Vol. 17, No. 3, pp. 63-71, 1997.
[20] Farouki, R. T., “The elastic bending energy of Pythagorean-hodograph curves,” Computer-Aided Geometric Design, Vol. 13, pp 227-241, 1996.
[21] Farouki, R. T., S. Shah, “Real-time CNC interpolators for Pythagorean-godograph curves,” Computer-Aided Geometric Design, Vol. 13, pp 583-600, 1996.
[22] Farouki, R. T., J. Manjunathaiah, D. Nicholas, G. F. Yuan, and S. Jee, “Variable-feedrate CNC interpolators for constant material removal rates along Pythagorean-hodograph curves,” Computer-Aided Design, Vol.30, No. 8, pp. 631-640, 1998.
[23] Farouki, R. T., J. Manjunathaiah, and G. F. Yuan, “G codes for the specification of Pythagorean-hodograph tool paths and associated feedrate functions on open-architechture CNC machines,” International Journal of Machine Tools and Manufacture, Vol. 39, No.1, pp. 123-142, 1999.
[24] Farouki, R. T., Y. F. Tsai, and G. F. Yuan, “Contour machining of free-form surfaces with real-time PH curve CNC interpolators,” Computer-Aided Geometric Design, Vol. 16, pp. 61-76, 1999.
[25] Farouki, R. T., Y. F., Tsai, “Exact Taylor series coefficients for variable-feedrate CNC curve interpolators,” Computer-Aided Design, Vol. 33, pp. 155-165, 2001.
[26] Farin, G., G. Rein, N. Sapidis, and A. J. Worsey, “Fairing cubic B-spline curves,” Computer-Aided Geometric Design, Vol. 4, pp. 91-103, 1987.
[27] Golub, H. G., C. F. Van Loan, “An analysis of the total least squares problem,” SIAM Journal on Numerical Analysis, Vol. 17, No. 6, pp. 883-893, 1980.
[28] Guarino, L., C. Bianco, and A. Piazzi, “Optimal trajectory planning with quintic G2-splines,” Proceedings of the IEEE Intelligent Vehicles Symposium 2000, pp. 620-625.
[29] Han, G. C, D. I. Kim, H. G. Kim, K. Nam, B. K. Choi, and S. K. Kim, “A high speed machining algorithm for CNC machine tools,” Industrial Electronics Society IECON '99 Proceedings. The 25th Annual Conference of the IEEE, Vol. 3, No.29, pp 1493 – 1497,1999.
[30] Kallay, M., “Constrained Optimization in Surface Design,” In Falcidieno B., T. K. Kunii (eds). Modeling in Computer Graphics -- Methods and Applications, Springer-Verlag, Berlin, pp 85-93, 1993.
[31] Kjellander, J. A. P., “Smoothing of cubic parametric splines,” Computer-Aided Design Vol. 15, No.3, pp. 175-179, 1983.
[32] Koninckx, B., H. Van Brussel, “Real-time NURBS interpolator for distributed motion control,” Annals of the CIRP, Vol. 51, No.1, pp. 315-318, 2002.
[33] Koninckx, B., B. Demeulenaere, H. Van Brussel and J. Swevers, “Closed-loop Fieldbus-based Clock Synchronization for Decemtralized Control Systems”, Proc. of the CIRP 1th International Conference on Agile, Reconfigurable Manufacturing, Ann Arbor, Michigan, 2001. (Keynote Lecture, Accessed via http://people.mech.kuleuven.ac.be/~bdemeule/pubs/bdm_cirp2001.pdf, 2005/5/27 )
[34] Koren, Y., O. Masory, “Reference-pulse circular interpolators for CNC systems,” Transactions of the ASME Journal of Engineering for Industry, Vol. 103, pp. 131-136, 1981.
[35] Koren, Y., C. C. Lo, and M. Shpitalni, “CNC interpolators: algorithms and analysis,” Manufacturing Science and Engineering, ASME, PED Vol. 64, pp. 83-92, 1993.
[36] Koren, Y., R. S. Lin, “Five-Axis Surface Interpolators”, Annals of the CIRP, Vol. 44, No. 1, pp. 379-382, 1995.
[37] Kruth, J. P., A. Kerstens, “Reverse engineering modelling of free-form surface from point clouds subject to boundary conditions,” Journal of Materials Processing Technology, Vol. 76, pp. 120-127, 1998.
[38] Lai, J. Y., C. Y. Lu, “Reverse Engineering of Composite Sculptured Surfaces,” International Journal of Advanced Manufacturing and Technology, Vol. 12, pp. 180-189,1996.
[39] Lai, J. Y., W. D. Ueng, “G2 Continuity of Multiple Surface Fitting,” International Journal of Advanced Manufacturing and Technology, Vol. 17, pp. 575-585, 2001.
[40] Lartigue, C., F. Thiebaut, and T. Maekawa, “CNC tool path in terms of B-spline curves,” Computer-Aided Design, Vol. 33, pp.307-319, 2001.
[41] Lee, I. K., M. S. Kim, and G Elber, “Planar curve offset based on circle approximation,” Computer-Aided Design, Vol. 28, No. 8, pp. 617-630, 1996.
[42] Liang, S. P., “Algorithm and Software System Design of Multi-axis Surface Machining with Helical Interpolation,” Master Thesis, National Cheng Kung University, 1999.
[43] Lin, Q., J. G. Rokne, “Variable-radius offset curves and surfaces,” Mathematical and Computer Modeling, Vol. 26, No. 7, pp. 97-108, 1997.
[44] Lin, R. S., “Real-time surface interpolator for 3-D parametric surface machining on 3-axis machine tools,” International Journal of Machine Tools and Manufacture, Vol. 40, No. 10, pp.1513-1526, 2000.
[45] Lin, R. S., Y. Koren, “Real-Time Interpolators for Multi-Axis CNC Machine Tools,” CIRP Journal of Manufacturing System, Vol. 25, No.2, pp. 145-149, 1996.
[46] Lin, R. S., Y. Koren, “Efficient tool-path planning for machining free-form surfaces,” Transactions of the ASME Journal of Engineering Industry, Vol. 118, pp. 21-28, 1996.
[47] Lin, R. S., Y. Koren, “Ruled Surface Machining on Five-Axis CNC Machine Tools”, Journal of Manufacturing Processes, Vol. 1, No. 2, pp. 1-11, 2000.
[48] Lin, S. C. J., “Computer Numerical Control from Programming to Networking,” Delmar Publishers, pp. 2-3, 1994.
[49] Liu, D., J. Hoschek, “GC1 continuity conditions between adjacent rectangular and triangular Bezier surfaces patches,” Computer-Aided Design, Vol. 21, No.4, pp. 194-200, 1989.
[50] Lo, C. C., C. Y. Hsiao, “CNC machine tool interpolator with path compensation for repeated contour machining,” Computer-Aided Design, Vol. 30, No. 1, pp. 55-62, 1998.
[51] Lo, C. C., “Real-time generation and control of cutter path for 5-axis CNC machining,” International Journal of Machine Tools and Manufacture, Vol. 39, No.3, pp. 471-488, 1999.
[52] Lo, C. C., “CNC machine tool surface interpolator for ball-end milling of free-form surfaces”, International Journal of Machine Tools & Manufacturing, Vol. 40, pp. 307-326, 2000.
[53] Maekawa, T., “An overview of offset curves and surfaces,” Computer-Aided Design, Vol. 31, pp. 165-173, 1999.
[54] Masory, O., Y. Koren, “Reference-word circular interpolators for CNC systems,” Transactions of the ASME Journal of Engineering for Industry, Vol. 104, pp. 400-405, 1982.
[55] McConalogue, D. J., “A quasi-instrinsic scheme for passing a smooth curve trhough discrete set of points,” Computer Journal, Vol. 13, No. 4, pp. 392-396, 1970.
[56] Meier, H., H. Nowacki, “Interpolating curves with gradual changes in curvature,” Computer-Aided Geometric Design, Vol. 4, pp. 297-305, 1987.
[57] Millan, K. Y., D. J. Walton, “Curve fitting with arc splines for NC tool path generation,” Computer-Aided Design, Vol. 26, No. 1, pp. 845-849, 1994.
[58] Milroy, M. J., C. Bradley, G. W. Vikers, and D. J. Weir, “G1 continuity of B-spline surface patches in reverse engineering,” Computer-Aided Design, Vol. 27, No. 6, pp 471-478, 1995.
[59] Nam, S. H., M. Y. Yang, “A study on a generalized parametric interpolator with real-time jerk-limited acceleration,” Computer-Aided Design, Vol. 36, pp 27-36, 2004.
[60] Pham, B., “Offset approximation of uniform B-splines,” Computer-Aided Design, Vol.20, No. 8, pp. 471-474, 1988.
[61] Pham, B., “Offset curves and surfaces: a brief survey,” Computer-Aided Design, Vol. 24, No. 4, pp. 223-229, 1992.
[62] Piazzi, A., A. Visioli, “Global Minimum-jerk trajectory planning of robot manipulators,” IEEE Transactions on Industrial Electronics, Vol. 47, No.1, pp. 140-149, 2000.
[63] Piegel, L., W. Tiller, ”The NURBS Book, Second Edition,” Springer-Verlag, New York, 1997.
[64] Piegel, L., W. Tiller, “Computing offsets of NURBS curves and surfaces,” Computer-Aided Design, Vol. 31, pp. 147-156, 1999.
[65] Piegel, L., W. Tiller, “Least-Square B-Spline Curve Approximation with Arbitrary End Derivatives,” Engineering with Computers, Vol. 16, pp.109-116, 2000.
[66] Pottmann, H., “Rational curves and surfaces with rational offsets,” Computer-Aided Geometric Design, Vol. 12, pp. 175-192, 1995.
[67] Pottmann, H., “General offset surfaces,” Neural, Parallel and Scientific Computations, Vol. 5, pp.55-80, 1997.
[68] Pottmann, H, J. Wallner, G. Glaeser, and B. Ravani, “Geometric criteria for gouge-free three-axis milling of sculptured surfaces,” In Proceedings of ASME Design Engineering Technical Conference, Atlanta, Georgia, 1998.
[69] Qu, R., J. Ye, “Approximation of minimum energy curves,” Applied Mathematics and Computation, Vol. 108, pp.153-166, 2000.
[70] Qiu, H., K. Cheng, and Y. Li, “Optimal circular arc interpolation for NC tool pathe generation in curve contour manufacturing,” Computer-Aided Design, Vol. 29, No. 11, pp. 751-760, 1997.
[71] Schofield, S., P. Wright, “Open architecture controllers for machine tools, part 1: design principles,” Transactions of the ASME Journal of Manufacturing Science and Engineering, Vol. 120, pp. 417-424, 1998.
[72] Schonherr, J., “Smooth biarc curves,” Computer-Aided Design, Vol. 25, No. 6, pp. 365-370, 1993.
[73] Shpitalni, M., Y. Koren, and C. C. Lo, “Real-time Curve Interpolators,” Computer-Aided Design, Vol. 26, pp. 832-838, 1994.
[74] Suresh, K., D. C. H. Yang, “Constant scallop-height machining of free-form surfaces,” Transactions of the ASME Journal of Engineering for Industry, Vol. 116, pp. 253-259, 1994.
[75] Tam, H. Y., H. Xu, and P. W. Tse, “An algorithm for the interpolation of hybrid curves,” Computer-Aided Design, Vol. 35, pp 267-277, 2003.
[76] Tang, K, C. C. Chang, and Y. Dayan, “Offsetting surface boundaries and 3-axis gouge-free surface machining,” Computer-Aided Design, Vol. 27, No. 12, pp. 915-927, 1995.
[77] Tikhon, M., T. J. Ko, S. H. Lee, and H. S. Kim, “NURBS interpolator for constant material removal rate in open NC machine tools,” International Journal of Machine Tools and Manufacture, Vol. 44, No. 2, pp. 237-245, 2004.
[78] Tsai, M. C., C. W. Cheng, and M. Y. Cheng, “A real-time NURBS surface interpolator for precision three-axis CNC machining,” International Journal of Machine Tools and Manufacture, Vol.43, No. 12, pp. 1217-1227, 2003.
[79] Tsai, M. C., C. W. Cheng, “A real-time predictor-corrector Interpolator for CNC machining,” Transactions of the ASME Journal of Manufacturing Science and Engineering, Vol. 125, pp. 1-12, 2003.
[80] Wang, F. C, P. K. Wright, “Open architecture controllers for machine tools, part 2: A real time quintic spline interpolator,” Transactions of the ASME Journal of Manufacturing Science and Engineering, Vol. 120, pp. 425-432, 1998.
[81] Wang, F. C, P. K. Wright, B. A. Barsky, and D. H. C. Yang, “Approximately arc-length parameterized C3 quintic interpolatory splines,” Transactions of the ASME Journal of Mechanical Design, Vol. 121, pp. 430-439, 1999.
[82] Wang, X., F. Cheng, and B. A. Brian, ”Energy and B-spline interproximation,” Computer-Aided Design, Vol. 29, No. 7, pp485-496, 1997.
[83] Wever, U, “Optimal Parameterization for cubic spline,” Computer-Aided Design, Vol. 23, No. 9, pp. 641-644, 1991.
[84] Wolberg, G., I. Alfy, “An energy-minimization framework for monotonic cubic spline interpolation,” Journal of Computational and Applied Mathematics, Vol. 143, pp. 145-188, 2002.
[85] Xu, Z, C. Jincheng, and F. Zhengjin, “Performance Evaluation of a Real-Time Interpolation Algorithm for NURBS Curves,” International Journal of Advanced Manufacturing and Technology, Vol. 20, pp. 270-276, 2002.
[86] Yan, S., S. Wang, and S. Tong, “Uneven offset method of NC tool path generation for free-form pocket machining,” Computers in Industry, Vol. 43, pp. 97-103, 2000.
[87] Yau, H. T., J. S. Chen, “Reverse Engineering of Complex Geometry Using Rational B-Splines,” International Journal of Advanced Manufacturing Technology, Vol. 13, pp. 548-555, 1997.
[88] Yau H. T., M. J. Kuo, “NURBS machining and feed rate adjustment for high-speed cutting of complex sculptured surfaces,” International Journal of Production Research, Vol. 39, No. 1, pp. 21-41, 2001.
[89] Ye, J, R. Qu, “Fairing of Parametric Cubic Splines,” Mathematical and Computer Modeling, Vol. 30, pp. 121-131,1999.
[90] Yeh, S. S., P. L. Hsu, “The speed-controlled interpolator for machining parametric curves,” Computer-Aided Design, Vol. 31, pp 349-357, 1999.
[91] Yeh, S. S., P. L. Hsu, “Adaptive-feedrate interpolation for parametric curves with a confined chord error,” Computer-Aided Design, Vol. 34, pp 229-237, 2002.
[92] Yong, T., R. Narayanaswami, “A parametric interpolator with confined chord errors, acceleration and deceleration for NC machining,” Computer-Aided Design, Vol. 35, pp. 1249-1259, 2003.
[93] Zhang, C., P. Zhang, and F. Cheng, “Fairing spline curves and surfaces by minimizing energy,” Computer-Aided Design, Vol. 33, pp. 913-923, 2001.
[94] Zhang, Q. G.., R. B. Greeway, “Development and implementation of a NURBS curve motion interpolator,” Robotics and Computer-Integrated Manufacturing, Vol. 14, No.1, pp. 27-36, 1998.