Method of extracting features from three-dimensional geometric data

• US 5,982,923 A
• Filed: 01/15/1998
• Issued: 11/09/1999
• Est. Priority Date: 12/26/1997
• Status: Expired due to Term

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Oh, Chi Jae, Park, Hwa Gyoo, Kim, Hyun
• Primary Examiner(s): Kelley, Christopher S.
• Application Number:
  US09/007,816
• Time in Patent Office: 663 Days
• Field of Search: 382/154, 382/190, 382/193, 382/204, 345/419, 345/420, 345/421, 345/423, 345/429
• US Class Current: 382/154
• CPC Class Codes: G05B 19/4097 characterised by using design data to control NC machines, e.g. CAD/CAM G05B19/4093 takes precedence
• CPC Class Codes: G05B 2219/35084 Geometric feature extraction, concave and convex regions, object recognition
• CPC Class Codes: G06F 2119/18 Manufacturability analysis or optimisation for manufacturability
• CPC Class Codes: G06F 30/10 Geometric CAD
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

The present invention relates to a method of extracting features from three-dimensional geometric data.

Heretofore, an expert has contrived a process planing by extracting a distinctive point from three-dimensional geometric data and inputting it as processing information.

Taking such contrivance into consideration, the present invention provides a method of obtaining a face-edge connection relation graph from three-dimensional geometric data taken from a CAD system, building it in the form of a face-edge adjacency relation matrix, searching for a cut node which severs the remaining faces by eliminating an optional face therefrom, and extracting the two severed subgraphs as features and a method of extracting features using a multi-cut node which selects an optional face first, eliminates another optional face together with the selected face, searches the connection of the remaining faces and finds for the two subgraphs disconnected by eliminating those two faces in order to overcome the limitations of single cut node.

Therefore, the present invention, when used, makes it easy to obtain data necessary for a process planing by automatically extracting features for processing of machines and so forth from three-dimensional geometric data by means of a computer.

Claims

1. A method of extracting features required for a process planing from three-dimensional geometric data, comprising:

a step of forming a face-edge adjacency relation matrix in the three-dimensional geometric data inputted from a CAD system and thereby forming a connection relation graph,

a step of forming the adjacency relation matrix again and searching for a cut node by eliminating an optional face on the graph created by forming the matrix,

a step of forming a result matrix with the subgraphs divided by the cut node if the graph is divided into two as a result of searching for the cut node,

a step of repeating in turn the above cut node search and result matrix formation steps for all faces by restoring the eliminated face and eliminating again the other optional face and of storing each basic shape for the subgraphs divided into minimum units as a result, and

a step of performing the above steps for all shapes divided into the subgraphs and then extracting and recognizing the above stored result matrix as features.

2. The method of extracting features required for a process planing from three-dimensional geometric data as defined in claim 1, wherein said cut node searching step comprises:

a step (S2) of eliminating an optional face on the face-edge adjacency relation matrix graph,

a step (S3) of forming again the face-edge adjacency relation matrix excluding the eliminated face,

a cut node searching step (S4) which, if there are two disconnected subgraphs in the matrix formed again, determines this face as a cut node, and

a step (S5) of forming the result of searching for the cut node into the matrix again.

3. The method of extracting features required for a process planing from three-dimensional geometric data as defined in claim 1 is a method of extracting features required for a process planing from three-dimensional geometric data, characterized by that it further comprises, in order to overcome the limitations of single cut node, multi-cut node search which, after an optional face is selected first and another optional face is eliminated together with the optional face selected first, searches connection of the remaining faces, and finds the two subgraphs disconnected by the elimination of these two faces and searches for the subgraphs disconnected by the elimination of plural faces increasing the faces eliminated by the above process.