JP2001022956A - Device and method for clustering processing - Google Patents

Abstract

PROBLEM TO BE SOLVED: To automatically group many faces constituting a three-dimensional shape into a plurality of areas, while reflecting the intention of a designer. SOLUTION: A clustering part 32 accepts shape models, respectively showing faces constituting a three-dimensional shape and constraint condition data showing which faces among these faces has to be absolutely included in a different (or same) cluster. The part 32 first selects faces that must necessarily be included in the same cluster from a shape model DB 26 and prepares an initial cluster by combining them. Furthermore, the part 32 successively combines clusters with one another the directions of normal lines of which are near and which give smooth frame lines after being combined, and outputs a cluster respectively guaranteeing the area which is equal to or larger than an appropriate area as the final processing result.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a clustering processing apparatus and a method for performing processing (clustering processing) for dividing a three-dimensional surface generated by, for example, a CAD apparatus into one or more surfaces (clusters).

[0002]

2. Description of the Related Art For example, the 'Decimation of Triangular Me
shes, ACM Computer Graphics, Vol. 26, No. 2 (SIGGRA
PH '92), pp. 65-70. (Reference 1) 'and' Mesh Optimiza
tion, ACM Computer Graphics, Vol. 27, (SIGGRAPH '9
3), pp. 19-26. (Reference 2) ', converts a large number of flat triangles constituting a three-dimensional shape designed by a CAD device or the like into a small number of flat triangles without largely changing the shape. A method is disclosed. In this conversion process, a process of evaluating a large number of triangle shapes in order and merging them in descending order of evaluation is performed.

Here, when clustering a three-dimensional shape, it may be more convenient to cluster the three-dimensional shape into a much smaller number of regions than the number of surfaces constituting the shape. For example, the three-dimensional shape data of an industrial product includes a very large number (for example, hundreds to thousands) of curved surfaces.
In general, the size of the mesh element side is often several mm to several tens mm, whereas a very large number (eg, 0.01
Curved surfaces (from about mm to several hundred mm) are often mixed in a three-dimensional shape. In order to obtain a preferable mesh generation result from the three-dimensional shape, it is necessary to combine neighboring curved surfaces into one region by a clustering process.

[0004] However, there has been no method for automatically performing a clustering process on a curved surface constituting a three-dimensional shape for the purpose of generating a mesh. Conventionally, there has not been a method of performing a clustering process on a curved surface instead of a flat triangle as in Literatures 1 and 2. In addition, clustering processing is automatically performed on surfaces constituting a three-dimensional region while reflecting the intention of the designer such as which surfaces are combined into one region and which surfaces are included in different regions. Heretofore, no method has existed.

[0005]

SUMMARY OF THE INVENTION The present invention has been made in view of the above-mentioned problems of the prior art, and it has been proposed that a large number of surfaces constituting a three-dimensional shape be reflected while reflecting the intention of a designer.
Moreover, it is an object of the present invention to provide a clustering processing device and a method thereof that can be automatically grouped into one or more regions. It is another object of the present invention to provide a clustering processing apparatus and a method for classifying a designed three-dimensional shape into regions suitable for realization.

[0006]

[Means for Achieving the Object] [First Clustering Processing Apparatus] In order to achieve the above object, a first clustering processing apparatus according to the present invention includes a plurality of planes in a space, each of which has one or more surfaces. A clustering processing apparatus that performs a process (clustering process) of dividing into one or more sets (clusters) including the surface, wherein the plurality of surfaces are divided based on a constraint condition indicating a condition for restricting the clustering process method. Based on the initial clustering means for clustering and generating one or more initial clusters each including one or more of the faces, the constraint condition, and the relationship between the plurality of adjacent initial clusters, a plurality of adjacent clusters are determined. Are merged with each other,
Cluster merging means for generating zero or more merged clusters including at least the initial cluster.

Preferably, the constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. Is to cluster the faces (first faces) that must be clustered into the same cluster so as to satisfy the constraint condition, so that they are included in the same cluster, and the faces (first faces) that must not be clustered in the same cluster 2) are clustered so as to be included in a cluster other than the same cluster, and the cluster merging unit includes a cluster among the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged. Corresponding to the second surface so as to satisfy the constraint condition, respectively. To merge the non-free the initial cluster with each other.

[0008] Preferably, the cluster merging means merges the initial clusters so as to satisfy the constraint condition and the merging condition to generate zero or more merged clusters; Among the generated merged clusters and the initial clusters, clusters outside the first area condition indicating the area conditions of these clusters (first out-of-range clusters) are defined as the first out-of-range clusters. A second cluster merging unit configured to merge adjacent merging clusters or the initial cluster satisfying a predetermined first merging condition so as to satisfy the constraint condition and generate zero or more new merging clusters; Have.

Preferably, the merging condition indicates continuity between the initial clusters to be merged and a condition of smoothness of a shape around the merged cluster after merging.
The first cluster merging unit merges the initial clusters satisfying the merging condition so as to satisfy the constraint condition, and generates zero or more merged clusters.

Preferably, the first merge condition is a cluster obtained when the first out-of-range cluster and the initial cluster or the merged cluster adjacent to the first out-of-range cluster are merged. The second cluster merging means satisfies the first merging condition between the first out-of-range cluster and the first out-of-range cluster. The initial cluster or the merged cluster is merged so as to satisfy the constraint condition.

Preferably, an area condition creating means for creating a second area condition indicating an area condition of the initial cluster and the merged cluster based on the attribute of the surface; A cluster outside the range of the calculated second area condition (a cluster outside the second range) is adjacent to the cluster outside the second range and satisfies a predetermined second merging condition; There is further provided a third cluster merging unit that merges the merged clusters so as to satisfy the constraint condition and generates zero or more new merged clusters.

Preferably, the area condition creating means creates the second area condition based on the area and orientation of all the surfaces among the attributes of the surface.

Preferably, the second merging condition is a cluster obtained when the second out-of-range cluster and the initial cluster or the merged cluster adjacent to the first out-of-range cluster are merged. And the third cluster merging means sets the second merging condition between the second out-of-range cluster and the first out-of-range cluster. The satisfying initial cluster or the merged cluster is merged so as to satisfy the constraint condition.

Preferably, when the adjacent initial clusters or the first to third clusters satisfy a predetermined third merging condition, the adjacent initial clusters or the first to third clusters are combined. There is further provided a fourth cluster merging unit for merging the clusters.

Preferably, the third merging condition includes: an orientation of the adjacent initial cluster or the first to third clusters; and a shape around the merged cluster obtained when these clusters are merged. And the fourth cluster merging unit merges the initial clusters or the first to third clusters satisfying the fourth merging condition so as to satisfy the constraint condition.

[Second clustering processing device]
A second clustering processing apparatus according to the present invention is a clustering processing apparatus that performs processing (clustering processing) of dividing a plurality of surfaces in a space into one or more sets (clusters) each including one or more surfaces. And an initial cluster generating means for generating one or more initial clusters by dividing the plurality of surfaces, and satisfying a predetermined merging condition.
Cluster merging means for merging the generated initial clusters to generate zero or more merged clusters. [Operation of Clustering Processing Apparatus] The clustering apparatus according to the present invention can be arbitrarily determined by a designer.
Conditions for restricting the contents of the clustering process, such as which face (hereinafter, also referred to as a face) among the above many faces is included in the same cluster, or which face must not be included in the same cluster ( (Restriction condition) is accepted, and the clustering process is always performed on the assumption that the restriction condition is always satisfied.

[Constraint Condition] The constraint condition will be further described.
Two adjacent faces share one or more edges. For example, if two faces (faces) are adjacent to each other, such as the upper half □ and the lower half □ of the kanji “day”, the two faces (faces) are horizontal bars at the center of the “day” character. As a ridgeline.

[Specific Examples of Surfaces Intended to Be Included in Different Clusters] In such a case, two faces (surfaces) are formed at different angles on both sides of a shared ridge line in a space (a three-dimensional surface). ), The ridge shared by the two faces looks like a fold when displayed. Therefore, the designer may want to always include these two faces in different clusters. Further, when it is desired to divide the surface of the three-dimensional shape into a plurality of polygonal surfaces so that a ridge line shared by two specific faces (faces) can be seen, and obtain a mesh, the designer needs to use these two specific faces. Sometimes one wants to include faces in different clusters.

[Specific examples of surfaces intended to be always included in the same cluster] Conversely, two faces (surfaces) are formed at the same angle in space (a three-dimensional surface) on both sides of a shared ridge. If present, the designer may wish to always include these two faces in the same cluster. Further, when it is desired to divide the surface of the three-dimensional shape into a plurality of polygonal surfaces so that a ridge line shared by two specific faces (faces) cannot be seen, and obtain a mesh, the designer must use these specific 2D surfaces. Sometimes one wants to always include two faces in the same cluster.

The constraint condition is used to reflect the intention of the designer in the clustering process. Here, for example, for too many faces,
If the designer had to explicitly set the constraint conditions, it would take too much time. Therefore, the designer would need to explicitly set the constraint conditions as described above for the face (face). Only the constraint condition needs to be set.

[Operation of the Initial Clustering Means] In the clustering apparatus according to the present invention, the initial clustering means first includes a large number of faces constituting the three-dimensional surface in different clusters. Is initialized. Next, the initial clustering means indicates that the constraint condition should be included in the same cluster in accordance with the constraint condition.
Groups must be included in the same cluster, and conversely, faces that indicate that the constraint must not be included in the same cluster must be included in different clusters. Divide and create an initial cluster.

[Structure and Operation of Cluster Merging Means] The cluster merging means includes first to fourth cluster merging means and area condition creating means. With these components, the cluster merging unit sequentially sorts the initial clusters so that the area of the cluster, the continuity between adjacent clusters, and the smoothness of the shape around the new cluster after merging are optimized. , Merge and get the final clustering result.

The first to fourth cluster merging means include:
Merged clusters or initial clusters each including a face (face) indicating that the constraint condition must not be included in the same cluster are not merged, but for simplicity of explanation, the operation of each of these cluster merging means will be described. In the description, satisfying the above constraint is a precondition and is not mentioned. Further, none of the first to fourth cluster merging means merges clusters when there is no cluster that satisfies the condition used by each.

[First Cluster Merging Means] The first cluster merging means firstly assumes a virtual merged cluster obtained when a plurality of adjacent initial clusters are merged into one. Then, an index value indicating the range of change of the normal line in the virtual merged cluster and the smoothness of the shape (frame) around the virtual merged cluster is calculated.

Next, the first cluster merging means determines whether or not the calculated index value satisfies a condition for merging adjacent initial clusters (merging condition), specifically, for example, Then, it is determined whether or not the width of change of the normal in the virtual merged cluster falls within a predetermined range, and whether the periphery of the virtual merged cluster is smoother than a predetermined value. Further, the first cluster merging means, when judging that the index value satisfies the condition that the adjacent initial clusters should be merged with each other, sets the virtual merged cluster as a target of this judgment. Are actually merged with each other to form a new merged cluster.

[Second Cluster Merging Means] Initial clusters and merged clusters whose areas are too small (hereinafter simply referred to as clusters when they are not distinguished)
If the clusters are independent, the number of clusters increases, and the clustering process according to the present invention may not be effective. Therefore, the second cluster merging means calculates the sum of the areas of the faces (areas of the clusters) included in the clusters obtained by the processing so far (the area of the cluster) and calculates a predetermined threshold value (the first area condition). ) And
If the area of the cluster is considered to be smaller than or equal to the appropriate area, the cluster having the smaller area (the cluster outside the first range) and another cluster adjacent to the smaller area (the first cluster) should be further merged (the second cluster). (1 merge condition).

When the second cluster merging means determines that merging is to be performed, the cluster having a small area and the cluster adjacent thereto are merged into one new merged cluster.
The second cluster merging unit determines whether or not to merge, for example, on the assumption of a virtual merged cluster obtained by merging these clusters, and based on the smoothness of the frame line of the virtual merged cluster.

[Area Calculating Means] The area calculating means calculates the total sum of the areas of all the faces (faces) constituting the designed three-dimensional shape and the range of fluctuation of the normal line of all the faces (faces). Appropriate area of the cluster in the designed three-dimensional shape based on the like (second area condition)
Is calculated.

[Third Cluster Merging Means] The third cluster merging means is similar to the second cluster merging means.
When the area of the cluster is considered to be equal to or less than the appropriate area, the area of the cluster obtained by the processing up to this point is calculated and compared with the appropriate area (second area condition) calculated by the area calculating means. Further determines whether or not the cluster having the small area (the cluster outside the second range) and another cluster adjacent thereto satisfies the condition that the cluster should be merged (the second merging condition). . When the third cluster merging unit determines that merging is to be performed, the cluster having a small area and a cluster adjacent thereto are merged into one new merged cluster. The third cluster merging unit determines whether or not to merge, for example, assuming a virtual merged cluster obtained by merging these clusters, and sets the smoothness of the frame of the virtual merged cluster and the virtual merged cluster. The determination is made based on the difference in the direction of the normal line in the cluster (the range of the normal line fluctuation).

[Fourth Cluster Merging Means] The fourth cluster merging means provides a condition (adjacent to the third merging condition) that adjacent ones of the clusters generated by the above processing should be further merged. ) Is determined, and if it is determined that the clusters should be merged, these clusters are merged to generate one new merged cluster. The fourth cluster merging unit determines whether or not to merge, for example, assuming a virtual merged cluster obtained by merging these clusters,
Whether or not the smoothness of the frame line of the virtual merged cluster is higher than that before the merger, and the difference in the direction of the normal line representing each of the clusters constituting the virtual merged cluster (range of fluctuation of the normal line) Is determined based on whether is small enough.

[Clustering Processing Method] The clustering processing method according to the present invention divides a plurality of faces in a space into one or more sets (clusters) each containing one or more faces (clustering processing). ), Wherein the plurality of surfaces are clustered based on a constraint condition indicating a condition for constraining the clustering method, and one initial cluster including one or more of the surfaces is provided. Above, generate
A plurality of adjacent initial clusters are merged based on the constraint conditions and a relationship between the plurality of adjacent initial clusters, and 0 or more merged clusters each including one or more initial clusters are generated. I do.

Preferably, the constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. To satisfy the above, the faces (first faces) that must be clustered in the same cluster are clustered so as to be included in the same cluster, and the faces (second faces) that must not be clustered in the same cluster are joined together. The clustering is performed so as to be included in a cluster other than the same cluster, and among the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged, the corresponding ones satisfying the constraint condition are satisfied. Other than the initial clusters including the second surface are merged.

[Medium] Further, the medium according to the present invention includes a plurality of surfaces in the space, each including one or more surfaces.
A program for performing a process (clustering process) for dividing into a plurality of sets (clusters), wherein the plurality of surfaces are clustered based on a constraint condition indicating a condition for constraining the clustering process method, and each of the plurality of surfaces is clustered into one. Based on an initial clustering step of generating one or more initial clusters including the above-described surface, the constraint condition, and a relationship between the plurality of adjacent initial clusters,
A plurality of adjacent initial clusters are merged with each other, and a merged cluster including at least one initial cluster is defined as 0
A program including a cluster merging step to be generated is mediated.

Preferably, the constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. In the above, the surfaces (first surfaces) that must be clustered in the same cluster so as to satisfy the constraint condition are clustered so as to be included in the same cluster, and the surfaces (first surface) that must not be clustered in the same cluster 2) clustering so that each other is included in a cluster other than the same cluster; and in the cluster merging step, the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged. Among them, the pair Mediating program for performing the process of merging other than the initial clusters to each other, each containing a said second surface.

[0035]

Embodiments of the present invention will be described below.

FIG. 1 shows a CAD (Computer Aided) for realizing the clustering process according to the present invention.
1 is a diagram showing a configuration of a (Design) apparatus 1. As shown in FIG. 1, the CAD device 1 includes a CPU 10 including a microprocessor, a memory, and their peripheral circuits (not shown),
A display device 12 such as a CRT display device or a liquid crystal display device, an input device 14 including a tablet 140, a keyboard 142 and a mouse 144, an output device 16 such as a printer or plotter, and a recording device such as a hard disk device, a magneto-optical disk device or a CD device. It comprises a storage device 18 for recording and reproducing data using the medium 180. That is, the CAD apparatus 1 employs a configuration in which a peripheral device suitable for use as a CAD apparatus is added to a normal computer.

[CAD Program 2] FIG. 2 is a diagram showing a configuration of a CAD program 2 to which the clustering processing according to the present invention is applied. As shown in FIG. 2, the CAD program 2 includes an input unit 20, a CAD unit 22, a shape database (DB) 26, a display / output unit 28, and a clustering processing unit 3.
Is composed of a constraint condition generation unit 30 and a clustering unit 32.

The CAD program 2 is recorded on the recording medium 180, supplied to the CAD device 1 (FIG. 1), loaded from the storage device 18 into the memory of the CPU 10, executed, and performs a three-dimensional shape designing process. This three-dimensional shape is
It is expressed as a set of faces (faces; hereinafter, a case where the face (face) is a quadrilateral face) that fills the surface of the three-dimensional shape without gaps, and each face is a vertex and a ridge line with another adjacent face. Share (edge). CAD
The program 2 performs a process (clustering process) of grouping one or more (many) faces (faces) constituting the three-dimensional shape into one or more regions (clusters).

[Display / Output Unit 28] Display / Output Unit 28
Is designed from the design output data indicating the three-dimensional shape and the mesh created on the surface of the three-dimensional shape (described later with reference to FIG. 16 and the like) designed by the CAD unit 22 and input via the shape DB 26. Display the three-dimensional shape
Or the display / printout
Output data is generated and output to the input unit 20, the display device 12 (FIG. 1), and the output device 16.

The display / output unit 28 is generated by the clustering processing unit 3 (clustering unit 32).
In order to process the clustering data input via the shape DB 26 and to make it easier to discriminate each of the clusters, a process (color classification process) of coloring adjacent clusters with different colors as much as possible is performed. Then, cluster image data indicating the cluster classified by color is generated and output to the input unit 20, the display device 12 (FIG. 1), and the output device 16. The display / output unit 28 is connected to the input unit 20.
The display unit 12 combines the GUI image data and display / output data input from the display unit 12 with each other.

[Design Output Data] FIG. 3A shows a face (face) or a face (face) showing a three-dimensional shape.
FIG. 3B is a diagram exemplifying a normal m of a cluster obtained by performing a clustering process on FIG. 3B. FIG. 3B shows a range (θ; FIG. The CAD unit 22
The design output data input from FIG. 2 to the display / output unit 28 is generally called a shape model and includes data shown in Table 1 below.

[0042]

[Table 1] Table 1: Data included in design output data: (1) Vertex data: identifiers (IDs) assigned to vertices of a large number of faces (faces; for example, quadrilateral faces) constituting a surface of a three-dimensional shape ) And spatial coordinates. (2) Ridge data: identifiers (IDs) assigned to the ridges of faces constituting the surface of the three-dimensional shape, and
The identifiers (ID) of the vertices at both ends of each ridge line are shown. (3) Surface boundary data: Indicates all identifiers (IDs) of vertices and edges of each face (surface). (4) Surface data: Indicates the identifier (ID) assigned to each face (surface), the area of each face, and the ID of the vertex and ridge line of each face. (5) Curved surface geometric data: The curved surface geometry is defined by a coordinate value at an arbitrary position in a face (surface) and a direction of a normal m at a position indicated by the coordinate value as illustrated in FIG. Substituting two variables s and t, these coordinate values (P
(X, y, z)) and normal direction (N (x, y, z))
(For example, P (x, y, z) = f
(S, t), N (x, y, z) = g (s, t)).

In Table 1, the data shown in (1) to (4) indicate the phase information of the face (surface), and the curved surface geometric data shown in (5) is the data of the face (surface). Indicates geometric information.

The clustering data input from the clustering processing unit 3 (clustering unit 32; FIG. 2) to the display / output unit 28 includes the data shown in Table 2 below.

[0045]

[Table 2] (1) Number of clusters: clustering processing unit 3
Shows the total number of clusters created by (clustering unit 32). (2) Face information: Indicates the identifier (ID) of each face (face) included in each cluster and the total number of faces.

[Color Classification Processing] The cluster color classification processing by the display / output unit 28 will be described in detail below. FIG.
3 is a flowchart showing a cluster color classification process (S10) by a display / output unit 28 shown in FIG. As shown in FIG. 4, in step 100 (S100), the display / output unit 28 selects any one of the clusters that have not been subjected to the color classification processing.

In step 102 (S102), the display / output unit 28 determines a color to be assigned to the cluster selected in the processing of S100 so that adjacent clusters do not have the same color.

In step 104 (S104), the display / output unit 28 selects any one of the faces (surfaces) that have not been displayed yet from among the surfaces included in the cluster selected in the process of S100.

In step 106 (S106), the display / output unit 28 attaches the color determined in the processing of S102 to the face (face) selected in the processing of S104, and sends it to the display device 12 (FIG. 1). indicate.

In step 108 (S108), the display / output unit 28 performs S1 for all the faces (faces) included in the cluster selected in the processing of S100.
It is determined whether or not the processing of step S06 has been performed. If the processing of step S106 has been completed for all faces, the processing of step S1
The process proceeds to the process of 10, and otherwise returns to the process of S104.

In step 110 (S110), the display / output unit 28 determines whether or not the processing in S106 has been completed for all the planes included in all the clusters. Otherwise, S1
It returns to the process of 00.

[Input Unit 20] The input unit 20 (FIG. 2) is performed by the designer on the input device 14 or on a GUI image (not shown) displayed on the display device 12. The operation input is accepted, and the design input data indicating the operation related to the three-dimensional shape design among the received operation inputs is CA.
It outputs to the constraint condition creation unit 30 instruction data that is output to the D unit 22 and instructs the clustering processing unit 3 (the clustering unit 32) on the clustering constraint condition.

[CAD unit 22] The CAD unit 22 has a shape D
B26, the shape data including the same information as the design output data (Table 1), and the result of the clustering processing by the clustering processing unit 3 (clustering unit 32) input from the clustering processing unit 3 (clustering unit 32) Based on the design input data input from the input unit 20, a process required for designing a three-dimensional shape is performed on the clustering data indicating the three-dimensional shape, and a design output indicating the designed three-dimensional shape is performed. Data is generated and output to the shape DB 26.

The CAD unit 22 divides the surface of the three-dimensional shape into a plurality of polygonal surfaces (for example, quadrangular surfaces) according to the result of the clustering performed by the clustering processing unit 3 (clustering unit 32), and creates a mesh. The data is output to the shape DB 26 as a part of the output data. In other words, the CAD unit 22 divides each of the clusters created on the surface of the three-dimensional shape so as to close them into clusters, in other words, so that one polygonal surface does not extend over a plurality of clusters. (Described later with reference to FIG. 16).

[Shape DB 26] The shape DB 26 is a CAD
The design output data input from the unit 22 and the clustering data input from the clustering processing unit 3 (clustering unit 32) are stored and managed in the storage device 18 (FIG. 1) or the like, and are stored in the storage device 18 (FIG. 1). On request
These stored and managed data are output to the CAD unit 22, the clustering unit 32, and the display / output unit.

[Constraint Condition Creation Unit 30] In the clustering processing unit 3, the constraint condition creation unit 30 includes instruction data input via the input unit 20 and a shape input from the shape DB 26 via the clustering unit 32. Based on the data, constraint condition data indicating a condition for restricting the clustering process in the clustering unit 32 is generated and output to the clustering unit 32.

FIG. 5 is a diagram exemplifying a GUI image displayed on the display device 12 (FIG. 2) and used for input of a constraint condition. Still referring to FIG.
Will be described in detail. As illustrated in FIG. 5, the designer uses a mouse 144 to display an image showing a face (surface) constituting the surface of the three-dimensional shape displayed on the display device 12.
By pointing at (Fig. 1) etc. and specifying whether to include them in the same cluster or different clusters,
A point indicating a part that must be included in the same cluster on the surface of the three-dimensional shape is instructed to the CAD apparatus 1 (CAD program 2). In addition, the designer performs CAD operations on the surface of the three-dimensional shape to indicate points that must be included in different clusters.
An instruction is given to the device 1 (CAD program 2).

The constraint condition creation unit 30 accepts the above-mentioned operation of the designer as instruction data via the input unit 20. The constraint condition creation unit 30 executes the three-dimensional shape pointed by the designer based on the instruction data. Each of zero or more points on the surface of is associated with a face in the pointed portion. Further, the constraint condition creation unit 30 classifies the 0 or more faces (faces) associated with each other into groups based on the instruction data,
Or more groups, and associate each of the obtained 0 or more groups with their attributes (whether they are included in the same cluster or in different clusters),
The data is output to the clustering unit 32 as constraint condition data.

[Clustering Unit 32] The clustering unit 32 (FIG. 2) converts the constraint condition data input from the constraint condition creation unit 30 and the shape DB2 from the CAD unit 22.
6 is subjected to clustering processing, and clustering data indicating the resulting cluster is output to the shape DB 26 and the CAD unit 22.

[Clustering Processing] The clustering processing in the clustering section 32 will be further described below. FIG. 6 is a flowchart showing the clustering process (S1) in the clustering unit 32 shown in FIG. As shown in FIG. 6, the clustering unit 32 performs an initial cluster process (S20), a primary merging process (S30),
The respective processes of the small cluster merging process (S40), the appropriate area guaranteeing process (S50), and the final merging process (S60) are performed, and clustering data is output from the design output data.

Hereinafter, each processing shown in FIG. 6 will be described in detail. 7, 9, 12 to 14 respectively show the initial clustering process (S20) and the primary merging process (S3) shown in FIG.
0), a small cluster merging process (S40), an appropriate area guaranteeing process (S50), and a final merging process (S60). FIG. 8 shows an initial clustering process (S20),
Primary merging processing (S30), small cluster merging processing (S4
0) is a diagram illustrating clusters output as results of the appropriate area guarantee processing (S50) and the final merging processing (S60).

[Initial Clustering Process (S20)] In the initial clustering process, the clustering processing unit 32 creates one or more clusters each including one face (face) included in the design output data. Further, the clustering processing unit 32 determines whether the clusters are adjacent to each other among the created clusters, and
One or more initial clusters are generated by merging clusters containing faces that have been determined to always be included in the same cluster.

As shown in FIG. 7, step 200 (S2
In the process of (00), the clustering unit 32 initializes a set of clusters so that each face (face) included in the design output data is included in a different cluster. In other words, the clustering unit 32 creates the same number of clusters as the number of faces (faces) constituting the three-dimensional shape, and sets each of these clusters to include a different face (face), so that a cluster set is formed. Is initialized.

In step 202 (S202), the clustering unit 32 selects any unprocessed set from among sets each including two adjacent clusters as a processing target.

In step 204 (S204), the clustering unit 32 determines that the two clusters included in the set selected in the processing of S202 must always be included in the same cluster according to the constraint indicated by the constraint data. Surface) is determined. If such a face is included, the clustering unit 32 returns to the process of S202, and otherwise, proceeds to the process of S206.

In step 206 (S206), the clustering unit 32 merges two adjacent clusters to be processed into one cluster to form a new cluster.

In step 208 (S208), the clustering unit 32 calculates
It is determined whether or not the process of determining whether or not to perform merging has been completed. If the process has been completed, the process of S20 is completed. Otherwise, the process returns to the process of S202. When the initial clustering process (S20) illustrated in FIG. 7 is completed, the clustering unit 32 holds the resulting cluster as an initial cluster, as illustrated with the symbol (a) in FIG. The process proceeds to the primary merging process (S30; FIGS. 6 and 9).

[Primary Merging Process] In the primary merging process, the clustering unit 32 is created in the process of S20 (FIGS. 5 and 7), and becomes the same cluster among the initial clusters adjacent to each other according to the constraint condition. Two faces (faces) that are prohibited from being included are not included, the two faces (faces) have the smallest difference in angle, and the merged frame line is the smoothest. New one
Generate two clusters.

FIG. 9 is a flowchart showing the primary merging process (S
It is a flowchart which shows 30). As shown in FIG. 9, in step 300 (S300), the clustering unit 32 selects a combination of two clusters for which an index value has not yet been calculated from a combination of two adjacent clusters.

In step 302 (S302), the clustering unit 32 combines two of the initial clusters obtained in the processing of S20 (FIGS. 6 and 7) selected in the processing of S300 into one. Assume a virtual raster. Further, the clustering unit 32 obtains the representative normal vectors m and n (FIG. 3A) of the two clusters constituting the virtual cluster, and obtains the normal deviation θ (FIG. 3B) in the virtual cluster. An index value indicating the size is calculated.

In order to calculate this index value, for example, the clustering unit 32 firstly outputs a face (plane) included in each of two clusters constituting a certain virtual cluster.
An area component of each normal vector is calculated, a total value of the calculated area component values of the normal vectors is calculated, and the calculated total value is normalized to form the virtual cluster 2
Representative normal vectors m,
_{n (m = ∫m i / |} ∫m i |, n = ∫n i / | ∫n i |; however, m _i is at one point on the face (face) constituting the virtual cluster each Normal vector, n
_i is the face (plane) that constitutes each virtual cluster
A normal vector at one point on the other one) is calculated.

In practice, the clustering unit 32 selects as many points as possible so as to prevent the distribution from being biased in each of the faces included in a certain virtual cluster, and modulates the points at the selected points. A line vector is calculated, and the sum of these is calculated. Further, the clustering unit 32 calculates the sum of the calculated normal vectors,
The length is normalized so as to be 1, and the representative normal vectors m and n of the two clusters constituting this virtual cluster are calculated. Further, the clustering unit 32
The angle θ between the representative normal vectors m and n of the two clusters constituting the obtained virtual cluster is obtained, and the angle θ
(1 / θ = 1.0 / ang (m, n)) is used as an index value indicating the magnitude of the swing of the normal m in the virtual cluster.

FIG. 10 is a diagram exemplifying the sharing ratio R _i of the frame lines of two adjacent clusters. FIG. 11A shows an angle (contact angle) at a frame of two adjacent clusters.
(B) is a diagram exemplifying the average value Φ _i of the angles of two adjacent clusters. Step 3
04 (S304; FIG. 9), the clustering unit 3
2 calculates an index value indicating the smoothness of the ridge line (frame line) around the virtual cluster assumed in the processing of S302. The clustering unit 32 calculates, for example, as index values indicating the smoothness of the frame lines of the virtual cluster, the sharing ratio R _i of the frame lines of the two clusters constituting the virtual cluster and the average value Φ _i of the contact angles. I do.

As shown in FIG. 10, the clustering unit 32 has a larger value in the ratio of the frame line length shared by the two clusters to the total length of the frame line of each of the two clusters. The other is defined as a frame line sharing ratio R _i . Further, the clustering unit 32 defines a contact angle Φ (Φ = 2π−α−β) at the contact point V of the two clusters A and B, as illustrated in FIG. When two clusters touch each other at two points, the sum of the contact angles of these two points is calculated, and the value of the sum is divided by the number of contacts (the number of contacts is 2 in FIG. 11B). Then, the average value Φ _i of the contact angle is calculated.

In step 306 (S306), the clustering unit 32 combines two index values calculated in the processing of S304 into one cluster by merging the two clusters constituting the virtual cluster, that is, either A merge priority value indicating whether two clusters constituting the virtual cluster should be preferentially merged is calculated. The clustering unit 32 simply adds, for example, two index values and sets the sum as a merge priority value.

In step 308 (S 308), the clustering unit 32 performs
It is determined whether or not the calculation of the merge priority value has been completed. If the calculation has been completed, the process proceeds to S310; otherwise, the process returns to S300.

In step 310 (S310), the clustering unit 32 creates a list in which the virtual clusters are arranged in descending order of their merge priority values.

In step 312 (S312), the clustering unit 32 determines whether or not there is a virtual cluster whose merge priority value is higher than a predetermined reference value in the list created in the process of S310. ,
If there is such a virtual cluster, the process proceeds to S314; otherwise, the process ends.

In step 314 (S314), the clustering unit 32 selects a virtual cluster having the highest merge priority value among the unprocessed virtual clusters in the list created in the process of S310 as a processing target.

In step 316 (S 316), the clustering unit 32 includes two clusters constituting the virtual cluster to be processed, each of which has a face (face) set to be not included in the same cluster due to the constraint condition. It is determined whether or not it is included. If it is not included (satisfies the constraint condition), the process proceeds to S318; otherwise, the process returns to S312.

In step 318 (S 318), the clustering unit 32 actually merges the two clusters that make up the processing target virtual cluster into one cluster, and sets it as a new cluster.

In step 320 (S320), the clustering unit 32 selects one cluster for which the merge priority with the new cluster has not been calculated from the clusters adjacent to the new cluster created in S318. I do.

In step 322 (S322), S
Assuming a new virtual cluster composed of the cluster created in the process of 318 and other clusters adjacent to this cluster, the swing of the normal m of the new virtual cluster is the same as in the process of S302. (FIG. 3
An index value indicating the magnitude of (B)) is calculated.

In step 324 (S324), the clustering unit 32 calculates the index value indicating the smoothness of the ridge line (frame line) around the virtual cluster newly assumed in the processing of S322, similarly to the processing of S304. calculate.

In step 326 (S 326), the clustering unit 32 calculates the merge priority of the virtual cluster newly assumed in the process of S 322, as in the process of S 306.

In step 328 (S328), the clustering unit 32 determines whether or not the processing of S320 to S326 has been completed for all the new virtual clusters. If the processing has been completed, the process proceeds to S330. Otherwise, the process proceeds to S330.

In step 330 (S330), the clustering unit 32 inserts the virtual cluster newly assumed in the processing of S322 into the list created in the processing of S310, and arranges the virtual clusters in the descending order of the merging priority values. Rearrange the order of the virtual clusters.

When the primary merging process (S30) shown in FIG. 9 is completed, the clustering unit 32 adds the resulting cluster (the first cluster) as shown in FIG. (S40; FIGS. 6 and 12).

[Small Cluster Merging Process] In the small cluster merging process, the clustering unit 32 determines that the cluster whose area does not reach the predetermined reference value is the smoothest after merging among other adjacent clusters satisfying the constraint condition. Merge with any that gives a border.

FIG. 12 is a flowchart showing the small cluster merging process (S40) shown in FIG. As shown in FIG. 12, in step 400 (S400), the clustering unit 32 selects any of the clusters that have not yet been subjected to the processing of S402 and whose area has not been calculated.

In step 402 (S402), the clustering unit 32 obtains the total area of the faces (faces) included in the clusters obtained in the processing of S30 (FIGS. 6 and 9) and selected in the processing of S400, that is,
Calculate the area of each cluster.

In step 404 (S404), the clustering unit 32 determines that the area of the cluster to be processed is
It is determined whether or not the area is equal to or less than a predetermined reference value. If the area of the cluster is equal to or less than the reference value, this cluster is determined to be a minute cluster (cluster outside the first range) and is processed. Then, the process proceeds to S 406. Otherwise, the process proceeds to S 418.

In step 406 (S406), the clustering unit 32 selects one cluster for which an index value indicating smoothness has not been calculated from clusters adjacent to the minute cluster.

In step 408 (S 408), the clustering unit 32 treats the cluster entrusted in the processing of S 406 as a processing target, and
It is determined whether or not the minute cluster includes faces that are set not to be included in the same cluster due to the constraint condition. If these clusters do not include such a plane, the clustering unit 32 returns to the processing of S406, and otherwise returns to S4.
It returns to the process of 10.

In step 410 (S410), the clustering unit 32 performs the processing in S304 (FIG. 9) on the virtual cluster obtained by assuming that the microcluster to be processed and the cluster adjacent thereto are merged.
In the same manner as in the processing of (1), an index value representing the smoothness of the frame line of this virtual cluster is calculated.

In step 412 (S 412), the clustering unit 32 calculates an index value obtained by the processing in S 410 for all virtual clusters assumed between the processing target minute cluster and another adjacent cluster. It is determined whether or not has been completed. If the calculation has been completed, the process proceeds to S414; otherwise, the process proceeds to S406.
Return to the processing of.

In step 414 (S 414), the clustering unit 32 determines whether or not the small cluster selected as the processing target in the processing of S 404 and the virtual cluster assumed between the small cluster and the adjacent cluster are S 4.
The two clusters included in the virtual cluster having the highest index value calculated in the process of step 10 are merged to form a new one.

In step 416 (S 416), the clustering unit 32 regards the new cluster obtained by the processing in S 414 as an unprocessed cluster that is not subjected to the small cluster merging processing,
A state in which the processing can be performed in steps 404 to S414 is set.

In step 418 (S418), the clustering unit 32 determines whether or not the small cluster merging processing (S400 to S416) has been completed for all clusters. If the processing has been completed, the processing ends. Otherwise, the process returns to S404.

The small cluster merging process (S
After the completion of (40), the clustering unit 32 holds the resulting cluster (second merged cluster), as illustrated with the symbol (c) in FIG. 8, and performs the appropriate area guarantee processing (S50). The process proceeds to FIGS.

[Appropriate Area Guarantee Processing] In the appropriate area guarantee processing, the clustering unit 32 calculates an appropriate cluster area based on the total area, inclination, and the like of the faces, and calculates the appropriate cluster area among the clusters obtained so far. A cluster whose area is equal to or smaller than the calculated proper area is adjacent to the other clusters satisfying the constraint condition and has the smallest difference in the angle between the two faces. The two lines having the smoothest lines are merged to generate a new cluster.

FIG. 13 is a diagram showing the proper area guarantee processing (S50) shown in FIG. As shown in FIG. 13, in step 500 (S500), the clustering unit 3
2 obtains the total _Sall of the areas of all the faces constituting the three-dimensional shape and the magnitude of the normal deflection. For example, the clustering unit 32 calculates the representative normal vector (FIG. 3A) of each face (face) by performing the same processing as in S302 (FIG. 9) on each face (face). Further, an angle θ (FIG. (B)) between the calculated representative normal vectors is calculated, and the reciprocal (1 / θ) of the maximum value of the calculated angles θ is calculated as the normal deviation. Size.

Further, the clustering unit 32 calculates the total area of all the obtained faces (faces) and the deflection of the normal line.
Substituting into the following equation 1, an appropriate area S of the cluster is calculated.

[0104]

S = (a / θ + b) × S _all (1) where a and b are constants obtained based on experience of clustering processing for a plurality of three-dimensional shapes.

In step 502 (S502), the clustering unit 32 selects one of the clusters not yet subjected to the processing of S504 and whose area has not been calculated.

In step 504 (S504), the clustering unit 32 calculates the total area of faces included in the cluster to be processed, that is, the area of the cluster to be processed.

In step 506 (S506), the clustering unit 32 determines that the area of the cluster to be processed is
It is determined whether or not the area is equal to or more than the appropriate area calculated in the processing of S500. If the area is on the appropriate area, the process proceeds to S508. Otherwise, the cluster determined to be less than the appropriate area S is determined. It is selected as a processing target, and the process proceeds to S510.

In step 508 (S508), the clustering unit 32 determines that all clusters are in S502 to S502.
It is determined whether or not the processing of step 506 has been performed, that is, whether or not the processing for all clusters has been completed. If the processing has been completed, the processing is terminated. Otherwise, any of the unprocessed clusters has been processed. One is selected for the next processing, and S
It returns to the process of 502.

In step 510 (S510), the clustering unit 32 selects one of the clusters adjacent to the cluster determined to be equal to or smaller than the appropriate area S for which the merge priority value has not been calculated in the processing of S506.

In step 512 (S512), the clustering unit 32 assumes a virtual cluster including each of the clusters to be processed in the process of S506 and one of the clusters adjacent to the cluster to be processed. The clustering unit 32 determines whether the two clusters included in the virtual cluster do not include a face that must be included in a different cluster, that is, whether the virtual cluster satisfies the constraint. If the constraint condition is satisfied, S514
Otherwise, the process returns to S510.

In step 514 (S 514), the clustering unit 32 calculates an index value indicating the magnitude of the fluctuation of the normal line of the virtual cluster to be processed, similarly to the processing of S 302 shown in FIG.

In step 516 (S516), the clustering unit 32 calculates an index indicating the smoothness of the frame line of the virtual cluster to be processed, similarly to the processing of S304 shown in FIG.

In step 518 (S518), the clustering unit 32 calculates the merge priority value of the virtual cluster to be processed, as in the processing of S306 shown in FIG.

In step 520 (S520), the clustering unit 32 determines whether or not the processing in S510 to S518 has been completed for all of the virtual clusters assumed in the processing in S512.
The process proceeds to the process of S22, and otherwise returns to the process of S510.

In step 522 (S522), S
In S518, of the virtual clusters including the clusters to be processed in the process of 506, the two clusters included in the virtual cluster with the highest merge priority are merged to form one new cluster. Generate. The clustering unit 32 defines the newly generated cluster as S
The process returns to the processing of S508, assuming that the cluster is not the processing target of the processing from 502 to S506.

The appropriate area guarantee processing shown in FIG. 13 (S5
Upon completion of (0), the clustering unit 32 holds the resulting cluster (third merged cluster), as illustrated with the symbol (d) in FIG. 8, and performs the final merge processing (S60; Proceed to FIGS.

[Final merging processing] In the final merging processing,
The clustering unit 32 further selects two of the clusters that are adjacent to each other and satisfy the constraint condition, in which the difference between the angles of the two faces is the smallest and the frame line after merging is the smoothest. Merge to generate one new cluster.

FIG. 14 shows the final merging process (S
It is a flowchart which shows 60). As illustrated in FIG. 14, in step 600 (S600), the clustering unit 32 selects one of the unprocessed sets from the two adjacent cluster sets as a processing target.

In step 602 (S602), the clustering unit 32 assumes a virtual cluster including the two clusters of the set selected in the processing of S600,
It is determined whether the two clusters included in this virtual cluster each include a face (face) that must be included in a different cluster, that is, whether the processing target virtual cluster satisfies the constraint condition, If the constraint condition is satisfied, the process proceeds to S604; otherwise, the process returns to S600.

In step 604 (S604), the clustering unit 32 calculates a representative normal of each of the two clusters constituting the virtual cluster to be processed, similarly to the processing of S302 shown in FIG.

In step 606 (S606), the clustering unit 32 calculates the angle between the representative normals of the two clusters generated in the processing of S604, and the calculated angle is equal to or smaller than a predetermined reference value. It is determined whether or not the value is equal to or smaller than the reference value. If the value is equal to or smaller than the reference value, the process proceeds to S608. Otherwise, the process proceeds to S600.

In step 608 (S608), the clustering unit 32 determines the index value indicating the smoothness of the frame line of each of the two virtual clusters included in the virtual cluster to be processed, similarly to the processing of S304 shown in FIG. Is calculated.

In step 610 (S610), the clustering unit 32 calculates an index value indicating the smoothness of the frame line of the virtual cluster to be processed, similarly to the processing of S304 shown in FIG.

In step 612 (S612), the clustering unit 32 divides the two clusters constituting the virtual cluster into one based on the index value calculated in the processing of S608 and the index value calculated in the processing of S610. It is determined whether or not the merged one makes the frame line smoother. If the frame line becomes smoother, the process proceeds to S614; otherwise, the process returns to S600.

In step 614 (S614), the clustering unit 32 merges the two clusters included in the processing-target virtual cluster to generate one new cluster.

In step 616 (S 616), the clustering unit 32 executes S
It is determined whether or not the processing of steps S600 to S612 has been completed. If the processing has been completed, the processing is terminated.
It is considered that the processing of S600 to S612 has not been performed on the new cluster generated in the processing of 614, and the processing returns to S600.

[0127] The clustering unit 32 executes
Through the processing of 20 to S60, a final clustering result is obtained as exemplified by adding the symbol (e) to FIG.

[Overall processing of CAD program 2]
With further reference to FIG. 15, CAD program 2 (FIG. 2)
Will be described. FIG. 15 shows the CAD data shown in FIG.
9 is a flowchart showing the entire processing (S7) of the program 2.

As shown in FIG. 15, step 700 (S
700), the designer uses the CAD unit 22 of the CAD program 2 (FIG. 2) to execute a three-dimensional shape (shape model)
Is designed, the CAD unit 22 outputs design output data indicating the designed three-dimensional shape (shape model) to the shape DB 26. In addition, the designer determines which of the faces (faces) included in the shape model must be included in the same cluster, and which of the faces (faces) must be included in different clusters.
When an instruction is given to the constraint condition creating unit 30 of the clustering processing unit 3, the constraint condition creating unit 30 generates constraint condition data indicating these, and outputs it to the clustering unit 32.

When the designer designates a shape model (design output data) to be processed and causes the clustering unit 32 to start the clustering process, the clustering unit 3
2 requests the designated design output data from the shape DB 26, and the shape DB 26 outputs the design output data to the clustering unit 32 in response to a request from the clustering unit 32.

FIG. 16 illustrates a cluster generated by the clustering unit 32 when the constraint condition is changed, and a mesh generated by the CAD unit 22 (FIG. 2) performing a division process according to the generated cluster. FIG. In step 702 (S702), the clustering unit 32 performs the clustering processing shown in FIGS. 6 to 13 (S20 to S60 in FIG. 6).

For example, as shown by the symbol (a) in FIG. 16, the three-dimensional surface has twelve faces (faces).
, The constraint conditions are the first and second constraints.
16 indicate that the faces (surfaces; surfaces 1 and 2) must always be included in the same cluster, as shown by the symbol (b) in FIG. , 2) are always included in the same cluster. Conversely, if the constraint condition indicates that these faces (faces; faces 1 and 2) must always be included in different clusters, as shown by the symbol (d) in FIG.
These faces (planes; planes 1 and 2) are always included in different clusters.

In step 704 (S704; FIG. 15), the display / output unit 28 performs a cluster color classification process (S10) as shown in FIG. 4, and displays the color-coded cluster on the display device 12.

In step 706 (S706), C
The AD unit 22 selects any of the clusters for which mesh generation has not yet been performed as a processing target.

In step 708 (S708), C
The AD unit 22 performs closed processing for each cluster obtained in the processing of S702, divides the surface of the three-dimensional shape into a plurality of polygonal surfaces (for example, quadrilateral surfaces), and creates a mesh. As shown by the symbol (c) in FIG. 16, from the cluster generated according to the constraint condition that the two exemplified faces (faces; faces 1 and 2) must be always included in the same cluster, As a result of the processing of S706, the ridge line shared by these two faces (faces; faces 1 and 2)
A mesh is generated that does not appear as a quadrilateral boundary.

Conversely, as shown by the symbol (e) in FIG. 16, the two faces (faces; faces 1 and 2) are generated in accordance with the constraint condition indicating that they must always be included in different clusters. From the clusters thus generated, as a result of the processing in S706, a mesh is generated in which the ridge line shared by these two faces (faces: faces 1 and 2) appears as a boundary of a quadrangular face.

In step 710 (S710), C
The AD unit 22 determines whether or not mesh generation has been completed for all clusters.
Otherwise, the process returns to S706.

In step 712 (S712), C
The AD unit 22 displays the mesh created in the processing of S706 to S710 on the display device 12 (FIG. 1) or prints out the mesh from the output device 16.

[Effects] The effects of the clustering process according to the present invention executed by the CAD apparatus 1 (FIG. 1) (CAD program 2 (FIG. 2)) will be further described with reference to FIGS. 17 to 19 are diagrams showing a first example of generating a mesh by performing a clustering process according to the present invention, and FIG. 17 illustrates a first three-dimensional shape to be subjected to the clustering process. 18 is FIG.
FIG. 19 illustrates a cluster obtained as a result of performing a clustering process on the three-dimensional shape illustrated in FIG.
19 illustrates a mesh created using the cluster shown in FIG.

FIGS. 20 to 22 are diagrams showing a second example of generating a mesh by performing the clustering process according to the present invention. FIG. 20 illustrates a second three-dimensional shape to be subjected to the clustering process. 21 illustrates a cluster obtained as a result of performing the clustering process on the three-dimensional shape illustrated in FIG. 20, and FIG. 22 illustrates a mesh created using the cluster illustrated in FIG. I do.

FIGS. 23 to 25 show a third example of generating a mesh by performing the clustering process according to the present invention. FIG. 23 shows a third three-dimensional shape to be subjected to the clustering process. 24 illustrates a cluster obtained as a result of performing the clustering process on the three-dimensional shape illustrated in FIG. 23, and FIG. 25 illustrates a mesh created using the cluster illustrated in FIG. I do.

The first to third examples illustrated in FIGS.
The surface of the three-dimensional shape is composed of hundreds to thousands of faces (faces).
When the clustering process is performed by the AD program 2, clustering results can be obtained as indicated by different shaded lines in FIGS. 18, 21, and 24, respectively. As can be seen with reference to FIGS.
Each of the obtained clusters is used to create a mesh that is extremely elongated and elongated, is extremely small as compared with a quadrangular surface (FIGS. 19, 23, 25), or has an extremely sharp boundary line. It can be seen that there is no shape that tends to have an adverse effect.

Further, when meshes closed for each cluster are created by using the clustering results illustrated in FIGS. 18, 21, and 24, the generated quadrangular surface has
As can be seen with reference to Figures 22 and 25, a very small number of extremely elongated elongated quadrangular surfaces, extremely sharp vertices, or extremely obtuse rectangular surfaces are included. It can be seen that the surfaces of the first to third three-dimensional shapes exemplified in FIGS. 17, 20, and 23 are divided into good quadrangular surfaces. When the clustering process is performed according to the present invention to create a mesh closed to a cluster, the faces (faces) are already appropriately grouped before the mesh is created. Can be divided into

[Modification] A modification of the processing of the CAD apparatus 1 (CAD program 2) according to the present invention will be described below.

[Arbitraryness of Constraint Condition Setting] The designer can arbitrarily decide whether or not to set the constraint condition. If the designer does not set the constraint condition, the constraint condition creation unit 30 sets It goes without saying that no constraint data is generated.

[Representative Normal Vector] Clustering Unit 3
In calculating the representative normal vector, instead of integrating and normalizing the normal vector in the cluster (face; face), some normals on the ridge line around the cluster (face; face) are used. It is also possible to approximate the normal vector using the vector.

The clustering unit 32 creates a representative normal vector by a method such as the processing of S302 shown in FIG. 9, and also generates another representative vector among the normal vectors of a cluster or a face (face). Alternatively, a normal vector that has the largest angle with the representative normal vector of the face (face) may be used as the cluster or the representative normal vector of the face (face).

[Arbitraryness of Combination of Processes] In the clustering unit 32, of the initial clustering process (S20) to the final merging process (S60) shown in FIG. May be arbitrarily combined with any one or more according to the use or the like, and the clustering process may be performed.

[0149]

As described above, according to the clustering processing apparatus and method according to the present invention, a large number of surfaces constituting a three-dimensional shape can be automatically reflected while reflecting the intention of the designer. They can be grouped into one or more regions. Further, according to the clustering processing apparatus and method thereof according to the present invention, the designed three-dimensional shape can be divided into regions suitable for realization.

[Brief description of the drawings]

FIG. 1 is a diagram illustrating a configuration of a CAD (Computer Aided Design) apparatus that implements a clustering process according to the present invention.

FIG. 2 is a diagram showing a configuration of a CAD program to which a clustering process according to the present invention is applied.

FIG. 3A is a face showing a three-dimensional shape;
Alternatively, FIG. 9B is a diagram illustrating a normal m of a cluster obtained by performing a clustering process on a face, and FIG.
FIG. 6 is a diagram illustrating a range of change (θ; run-out) of a normal line in the curved surface patch or cluster shown in FIG.

FIG. 4 is a flowchart showing a cluster color classification process (S10) based on display and output shown in FIG. 2;

FIG. 5 is a diagram illustrating a GUI image displayed on the display device (FIG. 2) and used for input of a constraint condition.

FIG. 6 is a flowchart illustrating a clustering process (S1) in the clustering unit illustrated in FIG. 2;

FIG. 7 shows an initial clustering process (S2) shown in FIG. 6;
FIG.

FIG. 8 shows an initial clustering process (S2) shown in FIG. 6;
0), a primary merging process (S30), a small cluster merging process (S40), an appropriate area guaranteeing process (S50), and a final merging process (S60).

FIG. 9 is a flowchart showing a primary merging process (S30) shown in FIG. 6;

FIG. 10 shows the sharing ratio R _i of the frame lines of two adjacent clusters.
FIG.

FIG. 11A is a diagram defining an angle (contact angle) of a frame line between two adjacent clusters, and FIG.
FIG. 5 is a diagram illustrating an average value Φ _i of angles of two adjacent clusters.

FIG. 12 shows a small cluster merging process (S4) shown in FIG. 6;
It is a flowchart which shows 0).

FIG. 13 is a diagram showing an appropriate area guarantee process (S50) shown in FIG. 6;

FIG. 14 is a flowchart showing a final merging process (S60) shown in FIG. 6;

FIG. 15 is a flowchart showing an entire process (S7) of the CAD program shown in FIG. 2;

16 is a diagram exemplifying a cluster generated by the clustering unit when the constraint condition is changed, and a mesh generated by the CAD unit (FIG. 2) performing a division process according to the generated cluster;

FIG. 17 is a diagram illustrating a first three-dimensional shape to be subjected to a clustering process;

18 is a diagram illustrating a cluster obtained as a result of performing a clustering process on the three-dimensional shape illustrated in FIG. 17;

FIG. 19 illustrates a mesh created using the cluster shown in FIG. 18;

FIG. 20 is a diagram illustrating a second three-dimensional shape to be subjected to a clustering process;

FIG. 21 is a diagram illustrating a cluster obtained as a result of performing a clustering process on the three-dimensional shape illustrated in FIG. 20;

FIG. 22 illustrates a mesh created using the cluster shown in FIG. 21;

FIG. 23 is a diagram illustrating a third three-dimensional shape to be subjected to clustering processing;

FIG. 24 is a diagram illustrating a cluster obtained as a result of performing a clustering process on the three-dimensional shape shown in FIG. 23;

FIG. 25 illustrates a mesh created using the cluster shown in FIG. 24;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... CAD device 10 ... CPU 12 ... Display device 14 ... Input device 140 ... Tablet 142 ... Keyboard 144 ... Mouse 16 ... Output device 18 ... Storage device 180 recording medium 2 CAD program 20 input unit 22 CAD unit 26 shape DB 28 display / output 3 clustering processing unit 30 constraint conditions Creation unit 32 ・ ・ ・ Clustering unit

Continued on the front page (72) Inventor Keisuke Inoue 1623-14 Shimotsuruma, Yamato-shi, Kanagawa Prefecture Inside the Tokyo Research Laboratory, IBM Japan, Ltd. (72) Takayuki Ito 1623-14, Shimotsuruma, Yamato-shi, Kanagawa Prefecture IBM Japan, Ltd.Tokyo Basic Research Laboratory (72) Inventor Atsushi Yamada 1623-14 Shimotsuruma, Yamato-shi, Kanagawa Prefecture IBM Japan, Ltd.Tokyo Basic Research Laboratory (72) Inventor Furuhata Tomotake 1623-14 Shimotsurumama, Yamato-shi, Kanagawa Japan F-term (reference) 5B046 CA04 FA18 GA01 GA02 GA04 5B050 BA07 CA04 EA28 FA06 5B080 AA13 AA19

Claims (15)

[Claims] 1. A clustering processing apparatus for performing a process (clustering process) of dividing a plurality of surfaces in a space into one or more sets (clusters) each including one or more of the surfaces. The plurality of surfaces are clustered based on a constraint condition indicating a condition for constraining the method, and an initial cluster including one or more surfaces is defined as one cluster.
The plurality of initial clusters are merged based on the constraint condition and the relationship between the plurality of adjacent initial clusters, and one or more of the initial clusters are merged. And a cluster merging unit that generates zero or more merged clusters including: 2. The constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. The initial clustering means includes: The faces (first faces) that must be clustered in the same cluster are clustered so as to be included in the same cluster so as to satisfy the constraint condition, and the faces (second faces) that are not to be clustered in the same cluster are clustered. Planes) are clustered so as to be included in clusters other than the same cluster, and the cluster merging unit includes the clusters among the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged. Including the corresponding second surface so as to satisfy a constraint condition, Clustering processing apparatus according to claim 1 for merging the other period cluster together. 3. The first cluster merging means for merging the initial clusters so as to satisfy the constraint condition and the merging condition to generate zero or more merged clusters. Among the merged clusters and the initial clusters, a cluster (a first out-of-range cluster) outside the range of a first area condition indicating an area condition of these clusters is adjacent to the first out-of-range cluster. And a second cluster merging unit that merges with the merged cluster or the initial cluster that satisfies a predetermined first merging condition so as to satisfy the constraint condition and generates zero or more new merged clusters. Item 3. A clustering processing device according to Item 2. 4. The merging condition indicates continuity between the initial clusters to be merged and a condition of smoothness of a shape around the merging cluster after merging, wherein the first cluster The clustering processing device according to claim 3, wherein the merging unit merges the initial clusters satisfying the merging condition so as to satisfy the constraint condition, and generates zero or more merged clusters. 5. A method according to claim 1, wherein the first merging condition is a cluster surrounding a cluster obtained when the first out-of-range cluster and the initial cluster or the merged cluster adjacent to the first out-of-range cluster are merged. The second cluster merging means, wherein the initial cluster satisfying the first merging condition between the first out-of-range cluster and the first out-of-range cluster 4. The clustering processing device according to claim 3, wherein the merging cluster is merged so as to satisfy the constraint condition. 6. An area condition creating means for creating a second area condition indicating an area condition of the initial cluster and the merged cluster based on the attribute of the surface; A cluster outside the range of the calculated second area condition (a cluster outside the second range) is adjacent to the cluster outside the second range, and the initial cluster or the merger that satisfies a predetermined second merge condition. A third cluster in which clusters are merged so as to satisfy the constraint condition and zero or more new merged clusters are generated;
The clustering processing apparatus according to claim 5, further comprising: a cluster merging unit. 7. The clustering processing apparatus according to claim 6, wherein said area condition creating means creates said second area condition based on the areas and orientations of all of said surfaces among said surface attributes. 8. The second merging condition is defined as: a cluster surrounding the cluster obtained when the second out-of-range cluster and the initial cluster or the merged cluster adjacent to the first out-of-range cluster are merged. The third cluster merging means satisfies the second merging condition between the second out-of-range cluster and the first out-of-range cluster. 8. The clustering processing device according to claim 6, wherein an initial cluster or the merged cluster is merged so as to satisfy the constraint condition. 9. The method according to claim 1, wherein the initial cluster or the first
When the third cluster satisfies a predetermined third merge condition, the adjacent initial cluster or the first to third clusters
The clustering processing device according to claim 6, further comprising a fourth cluster merging unit that merges the third clusters. 10. The third merging condition includes: an orientation of the adjacent initial cluster or the first to third clusters;
The condition of the smoothness of the shape around the merged cluster obtained when these clusters are merged is shown, wherein the fourth cluster merging means is the first cluster or the first to the first cluster satisfying the fourth merge condition. The clustering processing apparatus according to claim 9, wherein the third clusters are merged so as to satisfy the constraint condition. 11. A clustering processing apparatus for performing a process (clustering process) of dividing a plurality of surfaces in a space into one or more sets (clusters) each including one or more of the surfaces, wherein: Cluster generating means for generating one or more initial clusters by dividing the generated initial clusters, and cluster merging means for merging the generated initial clusters and generating zero or more merged clusters so as to satisfy a predetermined merging condition And a clustering processing device. 12. A clustering processing method for performing a process (clustering process) of dividing a plurality of surfaces in a space into one or more sets (clusters) each including one or more of the surfaces. The plurality of faces are clustered based on a constraint condition indicating a constraint condition of the method, and an initial cluster including at least one of the faces is defined as one cluster.
A plurality of adjacent initial clusters are merged based on the constraint condition and the relationship between the plurality of adjacent initial clusters, and a merged cluster including one or more initial clusters Clustering processing method for generating zero or more. 13. The constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. In addition, the surfaces (first surfaces) that must be clustered in the same cluster are clustered so as to be included in the same cluster, and the surfaces (second surfaces) that must not be clustered in the same cluster are the same. Clustering is performed so as to be included in a cluster other than the cluster, and among the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged, a corresponding second one is satisfied so as to satisfy the constraint condition. 12. The cluster according to claim 11, wherein other than the initial clusters including the respective surfaces are merged. Taringu processing method. 14. A program for performing a process (clustering process) of dividing a plurality of surfaces in a space into one or more sets (clusters) each including one or more of the surfaces. The plurality of surfaces are clustered based on a constraint condition indicating a constraint condition, and an initial cluster including one or more of the surfaces is defined as one cluster.
The plurality of initial clusters are merged based on the initial clustering step to be generated, the constraint condition, and the relationship between the plurality of adjacent initial clusters. A medium for mediating a program including a cluster merging step of generating zero or more merged clusters including: 15. The constraint condition indicates which of the faces must be clustered in the same cluster and which of the faces must not be clustered in the same cluster. In the initial clustering step, The faces (first faces) that must be clustered in the same cluster are clustered so as to be included in the same cluster so as to satisfy the constraint condition, and the faces (second faces) that are not to be clustered in the same cluster are clustered. Surface), and clustering so that they are included in clusters other than the same cluster; and in the cluster merging step, the initial clusters satisfying a merging condition indicating a condition between the initial clusters to be merged. , So as to satisfy the constraint condition. Medium of claim 13, which mediates the program and a process of merging other than the initial clusters to each other including a serial second surface, respectively.