Separating and intersecting spherical polygons: computing machinability on three-, four-, and five-axis numerically controlled machines

ABSTRACT

We consider the computation of an optimal workpiece orientation allowing the maximal number of surfaces to be machined in a single setup on a three-, four-, or five-axis numerically controlled machine. Assuming the use of a ball-end cutter, we establish the conditions under which a surface is machinable by the cutter aligned in a certain direction, without the cutter's being obstructed by portions of the same surface. The set of such directions is represented on the sphere as a convex region, called the visibility map of the surface. By using the Gaussian maps and the visibility maps of the surfaces on a component, we can formulate the optimal workpiece orientation problems as geometric problems on the sphere. These and related geometric problems include finding a densest hemisphere that contains the largest subset of a given set of spherical polygons, determining a great circle that separates a given set of spherical polygons, computing a great circle that bisects a given set of spherical polygons, and finding a great circle that intersects the largest or the smallest subset of a set of spherical polygons. We show how all possible ways of intersecting a set of n spherical polygons with v total number of vertices by a great circle can be computed in O(vn log n) time and represented as a spherical partition. By making use of this representation, we present efficient algorithms for solving the five geometric problems on the sphere.

REFERENCES

• 1: David Avis , Rephael Wenger, Polyhedral line transversals in space, Discrete & Computational Geometry, v.3 n.3, p.257-265, Jan., 1988 [doi>10.1007/BF02187911]
• 2: BAUMC, ART, B. 1975. A polyhedron representation for computer vision. In Notional Computer Conference, AFIPS Conference Proceedings. AFIPS, Arlington, Va., 589 596.
• 3: Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
• 4: Bernard Chazelle , Leo J. Guibas , D. T. Lee, The power of geometric duality, BIT, v.25 n.1, p.76-90, 1985 [doi>10.1007/BF01934990]
• 5: CHEN I,. L., AND CHOV, S. Y. 1992. Optima} parting directions by partial visibility. In Proceedings of the Symposium on Concurrent Engineering. ASME, New York.3
• 6: CHEN, L. L., AND W(xL T. C. 1992. Computational geometry on the sphere for automated machining. ASME J. Mech. Des. 114, 2, 288-295.
• 7: CIfrx, L. L., CHOU, S. Y., ANO WOO, T. C. 1992. Optimal parting directions for mold and di~ design. Tech. Rep. 92-105, Dept. of Industrial and Manufacturing Systems Engineering, Iowa State Univ., Ames, Iowa.
• 8: CHVATAL V. 1979. A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 3, 233 235.
• 9: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 10: EDELSI4RtrNNER, H., GUIBAS, L. J., AND SHARIR, M. 1989. The upper envelope ofpiecewise linear functions: Algorithms and applications. Discr. Comput. Geom. 4, 4, 311 336
• 11: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: GRAHAM, R. L., AND Y^O, F.F. 1983. Finding the convex hull of a simple polygon. J. Alg. 4, 4, 324-331.
• 14: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 15: J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
• 16: HILBEIrr, D., AND COHN-VOSSEN, S. 1952. Geometry and the Imagination. Chelsea, New York.
• 17: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 18: JOHNSON, D. S., AND Pgr. PARaT^, F.P. 1978. The densest hemisphere problem. Theoret. Comput. Sci. 6, 1, 93-107.
• 19: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 20: MARCINIAK, K. 1991. Geometric Modelling for Numerically Controlled Machining. Oxford University Press, New York.
• 21: O~OURKE, J., CHIEN, C., OLSON, T., AND NADOOR, D. 1982. A new linear algorithm for intersecting convex polygons. Comput. Graph. Image Process. 19, 4, 384-391.
• 22: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 23: RYe, P.J. 1986. Euclidean and Non-Euclidean Geometry: An Analytic Approach. Cambridge University Press, Cambridge, Mass.
• 24: SHIN, S. Y., AND WOO, T.C. 1986. Finding the convex hull of a simple polygon in linear time. Part. Recog. 19, 6, 453-458.
• 25: SPYR1DI, A. J., AND REQUICHA, A. A.G. 1989. Accessibility analysis for the automatic inspection of mechanical parts by coordinate measuring machines. Tech. Rep., Computer Science Dept., Univ. of Southern California.
• 26: Jorge Stolfi, Oriented projective geometry, Academic Press Professional, Inc., San Diego, CA, 1991
• 27: K. Tang , T. Woo, Algorithmic aspects of alternating sum of volumes part 1: data structure and difference operation, Computer-Aided Design, v.23 n.5, p.357-366, June 1991 [doi>10.1016/0010-4485(91)90029-V]
• 28: K. Tang , T. Woo, Algorithmic aspects of alternating sum of volumes. Part 2: Nonvergence and its remedy, Computer-Aided Design, v.23 n.6, p.435-443, July/Aug. 1991 [doi>10.1016/0010-4485(91)90011-K]
• 29: G. E. Thyer, Computer numerical control of machine tools, Industrial Press, Inc., New York, NY, 1988
• 30: Woo, T. C. 1985. A combinatorial analysis of boundary data structure schemata. IEEE Comput. Graph. Appl. 5, 3, 19-27.
• 31: Woo, T.C. 1982. Feature extraction by volume decomposition. In Proceedings of the Conference on CAD / CAM Technology in Mechanical Engineering (Cambridge, Mass.).
• 32: WOOOW~K, J. 1986. Computing Shape. Butterworths, Boston.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided manufacturing (CAM)

General Terms:
Algorithms, Design, Performance

Keywords:
bisection, densest hemisphere, minimal/maximal intersection, numerically controlled machining, separation, spherical algorithm, visibility algorithm