This is the first of two papers evaluating the performance of general-purpose feature detection techniques for geometric models. In this paper, six different methods are described to identify sets of faces that bound depression and protrusion faces. Each algorithm has been implemented and tested on eight components from the National Design Repository. The algorithms studied include previously published general-purpose feature detection algorithms such as the single-face inner-loop and concavity techniques. Others are improvements to existing algorithms such as extensions of the two-dimensional convex hull method to handle curved faces as well as protrusions. Lastly, new algorithms based on the three-dimensional convex hull, minimum concave, visible and multiple-face inner-loop face sets are described. These algorithms provide a basis for the comparative analysis that is the subject of the second paper.
HanJ.-H.PrattM.RegliW. C.Manufacturing feature recognition from solid models: A status report. IEEE Trans. Robotics and Automation, 2000, 16(6), 782–796.
2.
KyprianouL. K.Shape classification in computer aided design. PhD dissertation, Kings College, University of Cambridge, 1980.
3.
JaredG. E. M.Shape features in geometric modeling. In Solid Modeling by Computers: From Theory to Applications (Ed. PickettM. S.BoyseJ. W.), 1984, pp. 121–133 (Plenum Press, New York).
4.
ChoiB. K.BarashM. M.AndersonD. C.Automatic recognition of machined surfaces from a 3D solid model. Computer Aided Des., March 1984, 16(2), 81–86.
5.
StaleyS. M.HendersonM. R.AndersonD. C.Using syntactic pattern recognition to extract feature information from a solid geometric data base. Computers in Mech. Engng, September 1985, 61–66.
6.
LiR. K.A part-feature recognition system for rotational parts. Int. J. Prod. Res., 1988, 26(9), 1451–1475.
7.
HendersonM. R.Feature recognition in geometric modeling. In Proceedings of CAM-I'S 13th Annual Meeting and Technical Conference, Clearwater Beach, Florida, 13–15 November 1984, pp. 5–1-5–13.
8.
HummelK. E.Coupling rule-based and object-oriented programming for the classification of manufacturing features. In Proceedings of the ASME Computers in Engineering Conference, San Francisco, California, 1989, pp. 409–418.
9.
ChanA. K. W.CaseK.Process planning by recognizing and learning machining features. Int. J. Computer Integrated Mfg, 1994, 7(2), 77–99.
10.
MarefatM.KashyapR. L.Geometric reasoning for recognition of three-dimensional object features. IEEE Trans. Pattern Analysis and Mach. Intell., October 1990, 12(10), 949–965.
11.
De FlorianiL.Representation and extraction of shape features in a solid model. In Theoretical Foundation of Computer Graphics and CAD, NATO ASI Series, 1987, pp. 919–940.
12.
De FlorianiL.Feature extraction from boundary models of three-dimensional objects. IEEE Trans. Pattern Analysis and Mach. Intell., August 1989, 2(8), 785–798.
13.
De FlorianiL.BruzzoneE.Building a feature based object description from a boundary model. Computer Aided Des., 1989, 21(10), 602–603.
14.
JoshiS.ChangT. C.Graph-based heuristics for recognition of machined features from a 3D solid model. Computer Aided Des., March 1988, 20(2), 58–66.
15.
SakuraiH.GossardD. C.Recognising shape features in solid models. IEEE Computer Graphics and Applic., September 1990, 10(9), 22–32.
16.
GavankarP.HendersonM. R.Graph-based extraction of protrusions and depressions from boundary representations. Computer Aided Des., 1990, 22(7), 442–450.
17.
ChuangS. H.HendersonM. R.Three-dimensional shape pattern recognition using vertex classification and vertex-edge graphs. Computer Aided Des., 1990, 22(6), 377–387.
18.
CorneyJ.ClarkD. E. R.Method for finding holes and pockets that connect multiple faces in 2 1/2D objects. Computer Aided Des., 1991, 23(10), 658–668.
19.
CorneyJ.ClarkD. E. R.A feature recognition algorithm for multiply connected depressions and protrusions in 2 1/2D objects. In Proceedings of Symposium on Solid Modeling Foundations and CAD/CAM Applications, June 1991, pp. 171–183 (ACM Press).
20.
ChuangS. H.HendersonM. R.Using subgraph isomorphism to recognise and decompose boundary representation features. Trans. ASME, J. Mech. Des., September 1994, 116, 793–117.
21.
TrikaS. N.KashyapR. L.Geometric reasoning for extraction of manufacturing features in iso-oriented polyhedrons. IEEE PAMI, 1994, 16(11), 1087–1100.
22.
KumaraS. R. T.KaoC.-Y.GallagherM. G.KasturiR.3-D interacting manufacturing feature recognition. Ann. CIRP, 1994, 43(1), 133–136.
23.
GaoS.ShahJ. J.Automatic recognition of interacting machining features based on minimal condition subgraph. Computer Aided Des., August 1998, 30(9), 727–739.
24.
LittleG.TuttleR.ClarkD. E. R.CorneyJ.The Heriot-Watt featurefinder: CIE97 results. Computer Aided Des., November 1998, 30(13), 991–996.
25.
LaakkoT.MantylaM.Feature modelling by incremental feature recognition. Computer Aided Des., August 1993, 25(8), 479–492.
YongY.MurrayJ. L.CorneyJ. R.ClarkD. E. R.Convex hull of a planar set of straight and circular line segments. Engng Computations, 1999, 16(8), 858–875.
28.
XuX.HindujaS.Recognition of rough machining features in 2 1/2D components. Computer Aided Des., June 1998, 30(7), 503–516.
29.
VandenbrandeJ. H.RequichaA. A. G.Spatial reasoning for the automatic recognition of machinable features in solid models. IEEE Trans. Pattern Analysis and Mach. Intell., 1993, 15(2), 1–17.
30.
VandenbrandeJ. H.RequichaA. A. G.Geometric computations for the recognition of spatially interacting machinable features. In Advances in Feature Based Manufacturing (Ed. ShahJ. J.MantylaM.NauD. S.), 1994, pp. 83–106 (Elsevier Science, Amsterdam).
31.
RegliW. C.Geometric algorithms for recognition of features from solid models. PhD thesis, University of Maryland, 1995.
32.
HanJ.-H.3D geometric reasoning algorithms for feature recognition. PhD thesis, University of Southern California, Los Angeles, California, 1996.
33.
HanJ.-H.RequichaA. A. G.Integration of feature based design and feature recognition. Computer Aided Des., 1997, 29(5), 393–403.
34.
HanJ.-H.RequichaA. A. G.Feature recognition from CAD models. IEEE Computer Graphics and Applic., 1998, 18(2), 80–94.
35.
HanJ.-H.RequichaA. A. G.Modeller-independent feature recognition in a distributed environment. Computer Aided Des., 1998, 30(6), 453–463.
36.
VandebrandeJ.RequichaA. A. G.Spatial reasoning for automatic recognition of interacting form features. In ASME Computer in Engineering Conference, Boston, Massachusetts, 1990, pp. 251–256.
37.
WooT. C.Interfacing solid modeling to CAD and CAM: Data structures and algorithms for decomposing a solid. IEEE Computer, December 1984, pp. 44–49.
38.
KimT. S.Recognition of form features using convex decomposition. Computer Aided Des., 1992, 24(9), 461–476.
WangE.KimY. S.Form feature recognition using convex decomposition: Results presented at the 1997 ASME CIE Feature Panel Session. Computer Aided Des., November 1998, 30(13), 983–989.
41.
TsengY.-J.JoshiS. B.Recognising multiple interpretations in 2 1/2D machining of pockets. Int. J. Prod. Res., 1994, 32(5), 1063–1086.
42.
TsengY.-J.JoshiS. B.Recognising multiple interpretations of interacting machining features. Computer Aided Des., September 1994, 26(9), 667–688.
43.
SakuraiH.ParagD.Volume decomposition and feature recognition. Part I: Polyhedral objects. Computer Aided Des., November 1995, 27(11), 833–843.
44.
SakuraiH.ParagD.Volume decomposition and feature recognition. Part II: Curved objects. Computer Aided Des., June 1996, 28(6–7), 519–537.
45.
WangM. T.ChangT. C.Feature recognition for automated process planning. In Proceedings of ASME Manufacturing International Conference, 1990, Vol. 2, pp. 49–55 (American Society of Mechanical Engineers, New York).
46.
FerreiraJ. C. E.HindujaS.Convex hull-based feature-recognition method for 2.5D components. Computer Aided Des., 1990, 22(1), 41–49.
47.
GuerraA. R. O.HindujaS.Modelling turned components with non-axisymmetric features. Computer Aided Des., May 1997, 29(5), 343–359.
48.
GadhR.PrinzF. B.Recognition of geometric form using the differential depth filter. Computer Aided Des., November 1992, 24(11), 583–598.
49.
SonthiR.GadhR.MMCs and PPCs as constructs of curvature regions for form feature determination. Computer Aided Des., November 1998, 30(13), 997–1001.
50.
GibsonP.IsmailH. S.SabinM. A.HonK. K. B.Interactive programmable feature recognisor. Ann. CIRP, 1997, 46(1), 407–410.
51.
PrabhakarS.HendersonM. R.Automatic form feature recognition using neural network-based techniques on boundary representation of solid models. Computer Aided Des., 1992, 24(7), 391–393.
52.
NezisK.VosniakosG.Recognizing 2 1/2D shape features using a neural network and heuristics. Computer Aided Des., July 1997, 29(7), 523–539.
53.
ZulkifliA. H.MeeranS.Decomposition of interacting features using a Kohonen self-organizing feature map neural network. Engng Applic. Artif. Intell., February 1999, 12(1), 59–78.
54.
GrahamR. L.An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Lett., 1972, 1, 132–133.
55.
JarvisR. A.On the identification of the convex hull of a finite set of points in the plane. Information Processing Lett., 1973, 2, 18–21.
56.
BarberC. B.DobkinD. P.HuhdanpaaH. T.The Quickhull algorithm for convex hulls. ACM Trans. Math. Software, December 1996, 22(4), 469–483.
57.
GaoS.ShahJ. J.Automatic recognition of interacting machining features based on minimal condition subgraph. Computer Aided Des., August 1998, 30(9), 727–739.
De MartinoT.FalcidienoB.GianniniF.HassingerS.OvtcharovaJ.Feature-based modelling by integrating design and recognition approaches. Computer Aided Des., August 1994, 26(8), 647–653.
