Parallel processing for 2-1/2D machining simulation

ABSTRACT

Continued progress in the area of solid modeler based machining process simulation is hindered by the complexity growth that occurs for a large number of tool paths n. For this reason, many researchers have adopted the Z-buffer approach. Boundary-representation (B-rep), however, remains the dominant choice for commercial modelers. This paper begins by reviewing the current state of solid modeler based machining simulation. Using an industrial example, the growth rate, for a simple feed rate scheduling application, is estimated to be O(n^1.5). It is shown that round robin parallel scheduling quickly becomes inefficient due to the fraction of time spent on tool swept volume Boolean subtractions. The tool path sequence is next heuristically subdivided into nearly equal size neighbor groups. Only the Boolean subtractions required for accurate simulation are included in the group. Each group is then simulated in parallel, achieving a greatly reduced wall clock running time. Computational geometry methods are described that permit rapid identification of tool path neighbors. It is shown that, under practical assumptions, the total number of tool path neighbor pairs is O(n), justifying the benefit of parallel processing. Both dual CPU and networked parallel solutions are implemented. Geometric images and running time plots are included to illustrate. Discussion is included, with proposed steps to further reduce calculation time.

REFERENCES

• 1: Algorithmic Solutions Soitware GmbH, LEDA 4.2.1, Saarbrticken, Germany www.algorithmic-solutions.com.
• 2: Altan, T., Lilly, B.W., Kruth, J.P., K6nig, W., T6nshoff, H.K, van Luttervelt, C.A. and Khairy, A.B., Advanced Techniques for Die and Mold Machining. Annals of the CIRP, 42, 2 (1993), 707-716.
• 3: Anderson, R.O., Detecting and eliminating collisions in NC Machining. Computer-Aided Design, 10, 4 (1978), 231-237.
• 4: Atherton, P.R., Earl, C., and Fred, C., A Graphical Simulation System for Dynamic Five-Axis NC Verification. Proc. Autofact, (Dearborn, MI, Nov. 1987), SME, 2.1-2.12.
• 5: Bailey, T.E., Jenkins, D.M., Spence, A.D. and Elbestawi, M.A., Integrated Modeling for Metal Removal Operations, Proc. IMECE, DSC-58 (Nov. 1996), ASME, 191-198.
• 6: Ivan J. Balaban, An optimal algorithm for finding segments intersections, Proceedings of the eleventh annual symposium on Computational geometry, p.211-219, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220302]
• 7: Broonsvoort, W.F. and Garnaat, H., Incremental Display of CSG Models using Local Updating. Computer-Aided Design 13, 6 (1981), 365-366.
• 8: Ingrid Carlbom, An algorithm for geometric set operations using cellular subdivision techniques, IEEE Computer Graphics and Applications, v.7 n.5, p.44-55, May 1987 [doi>10.1109/MCG.1987.276987]
• 9: CGTech, Irvine, CA, USA, www.cgtech.com/optipath.htm.
• 10: Chappel, I.T., The Use of Vectors to Simulate Material Removed by Numerically Controlled Machining. Computer- Aided Design 15, 3 (May 1983), 156-158.
• 11: Choi, B.K. and Jerard, R.B., Sculptured Surface Machining - Theory and Applications, Kluwer Academic Publishers (1998).
• 12: Jonathan Corney, 3d Modeling Using the Acis Kernel and Toolkit, John Wiley & Sons, Inc., New York, NY, 1997
• 13: El Mounayri, H., Spence, A.D., and Elbestawi, M.A., Milling Process Simulation - A Generic Solid Modeler Based Paradigm. Trans. ASME, J. Manufacturing Science and Engineering, 120, 2 (1998), 213-221.
• 14: Fussell, B.K., Ersoy, C. and Jerard, R.B., Computer Generated CNC Machining Feedrates. Japan/USA Symposium on Flexible Automation, 1 (1992), ASME, 377-384.
• 15: Hemmett, J.G., Fussell, B.K. and Jerard, R.B., A Robust and Efficient Approach to Feedrate Selection for 3-Axis Milling, Proc. IMECE, Symp. on Dynamics and Control of Material Removal Processes, DSC-Vol. 2, (Nov. 2000), ASME, 729- 736.
• 16: Robert B. Jerard , Robert L. Drysdale , Kenneth Hauck , Barry Schaudt , John Magewick, Methods for Detecting Errors in Numerically Controlled Machining of Sculptured Surfaces, IEEE Computer Graphics and Applications, v.9 n.1, p.26-39, January 1989 [doi>10.1109/38.20331]
• 17: Jerard. R.B., Fussell, B.K., Erean, M.T., and HemmeR, J.G., Integration of Geometric and Mechanistic Models of NC Machining into an Open-Architecture Machine Tool Controller, Proc. IMECE, Symp. on Dynamics and Control of Material Removal Processes, DSC-Vol. 2, (Nov. 2000), ASME, 675-682.
• 18: Karger, D., Stein, C., and Wein, J., Scheduling Algorithms, CRC Handbook on Algorithms and Theory of Computation, Atallah, M.J., Ed., (1998), Chapter 35.
• 19: Kline, W.A., DeVor, R.E. and Lindberg, J.R., The Prediction of Cutting Forces in End Milling with Application to Cornering Cuts. Int. J. Machine Tool Design and Research, 22, 1 (1982), 7-22.
• 20: Koenigsberger, F. and Sabberwal, A.J.P., An Investigation into the Cutting Force Pulsations during Milling Operations. Int. J. Machine Tool Design Research, 1 (1961), 15-33.
• 21: Lee, E.H. and Schaffer, B.W., Theory of Plasticity Applied to the Problem of Machining. Journal of Applied Mechanics, 18 (1951), 405-413.
• 22: Martelloti, M.E., An Analysis of the Milling Process. Trans. ASME 63 (1941), 677-700.
• 23: Martelloti, M.E., An Analysis of the Milling Process, Part II: Down Milling. Trans. ASME 67 (1945), 233-251.
• 24: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 25: Menon, J.P. and Robinson, D.M., Advanced NC Verification via massively Parallel Raycasting. Manufacturing Review, 6, 2 (1993), 141-154.
• 26: Merchant, M.E., Mechanics of the Cutting Process I. Journal of Applied Physics, 16 (1945), 267-275.
• 27: Merchant, M.E., Mechanics of the Cutting Process If. Journal of Applied Physics, 16 (1945), 318-324.
• 28: Oliver, J.H., Efficient Intersection of Surface Normals with Milling Tool Swept Volumes for Discrete Three-Axis NC Verification. Trans. ASME, J. Mechanical Design, 114 (June 1992), 283-287.
• 29: Saturley, P.V. and Spence, A.D., Integration of Milling Process Simulation with On-Line Monitoring and Control. Int. J. Adv. Manuf. Technol. 16 (2000), 92-99.
• 30: SETI @ Home, The Search for Extraterrestrial Intelligence, http://setiathome.ssl.berkeley.edu
• 31: Smith, S. and Tlusty, J., An Overview of Modeling and Simulation of the Milling Process. Trans. ASME. J. Eng. Ind., 113 (1991) 169-175.
• 32: Spatial Technology Inc., Boulder, CO, USA, www.spatial.eom.
• 33: Spence, A.D., Solid Modeler Based Machining Process Simulation, Ph.D. Thesis, The University of British Columbia (Vancouver, BC, 1992).
• 34: Spence, A.D., Abrari, F., and Elbestawi, M.A., Integrated Solid Modeler Based Solutions for Machining. Computer- Aided Design, 32, 8-9 (Aug. 2000), 553-568.
• 35: Spence, A.D. and Altintas, Y., A Solid Modeler Based Milling Process Simulation and Planning System. Trans. ASME, J. of Engineering for Industry, 116 (1994), 61-69.
• 36: Structural Dynamics Research Corporation, www.sdrc.com.
• 37: Suzak, H., Koresawa, H., and Sakamoto, M., Development of the Real Time CAM System based on Parallel Processing and the Inverse Offset Method. Trans. NAMRI/SME, XXI (1993), 303-309.
• 38: Takata, S., A Cutting Simulation System for Machinabitity Evaluation Using a Workpiece Model. Annals of the CIRP, 38, 1 (1989), 417-420.
• 39: S Takata , T Sata, Model referenced monitoring and diagnosis - application to the manufacturing system, Computers in Industry, v.7 n.1, p.31-44, Feb. 1986 [doi>10.1016/0166-3615(86)90007-2]
• 40: Voelcker, H.B. and Hunt, W.A., The Role of Solid Modeling in Machining - Process Modeling and NC Verification. SAE Technical Paper 810195 (1981).
• 41: Tim Van Hook, Real-time shaded NC milling display, ACM SIGGRAPH Computer Graphics, v.20 n.4, p.15-20, Aug. 1986
• 42: Wang, W.P. and Wang, K.K., Geometric Modeling for Swept Volume of Moving Solids. IEEE Computer Graphics and Applications, 6, 12 (1986), 8-17.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Design, Measurement, Performance, Theory, Verification

Keywords:
computational geometry, machining simulation, parallel processing