JP2003271687A - Interference model detection apparatus, method, and storage medium - Google Patents

Abstract

(57) [Summary] [PROBLEMS] To quickly detect an interference state between models constituting an assembly. SOLUTION: An input unit 11, an input reading unit 12, a shape storage unit 13, a model boundary interference determination unit 14, a surface boundary interference determination unit 15, a polygon boundary interference determination unit 16, a shape display unit 1.
7, which detects the state of interference between models constituting a three-dimensional assembly represented by a polygon mesh. It has a model bounding box information table for storing bounding box information in a three-dimensional space for each model constituting the assembly. Based on the positional relationship of the bounding boxes in each model in the assembly, it is determined whether or not the model may interfere. If there is a possibility of judgment, the subsequent calculations omit a detailed check that requires a calculation cost, and obtain a combination of models that may not interfere with each other at high speed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a three-dimensional shape interference detection apparatus and method, and more particularly to a CAD (Compu
ter Added Design / CAM (Com
putter Added Manufacturin
Regarding the shape evaluation method in g), it relates to a three-dimensional shape interference detection apparatus and method suitable for use in a three-dimensional shape evaluation apparatus using a computer.

[0002]

2. Description of the Related Art With the spread of three-dimensional CAD / CG systems, etc., the number of users of three-dimensional shape data has expanded, and
Opportunities to effectively use 3D shape data have increased in various situations such as simulation and verification of assembly. C
The process of analyzing / verifying on a computer before transferring the three-dimensional shape data generated by the AD system or the like to the manufacturing process is now becoming commonplace. Above all, in an assembly composed of a plurality of models, the function of detecting interference between the individual models is a useful function for checking design mistakes and input mistakes.

In many cases, the data used to represent a shape in a three-dimensional shape viewer is a polygon mesh that is approximately generated from free-form surface data. When detecting the interference state using a polygon mesh,
If the brute force interference check is performed between polygon meshes that form individual models, a huge amount of processing time is required for a large-scale assembly, and interactive operability is significantly impaired. However, in order to detect the interference state of a plurality of three-dimensional shapes represented by a polygon mesh, the interference calculation between polygons is finally performed to determine whether or not the models actually interfere with each other. There is a need.

[0004]

Therefore, before performing costly interference detection between polygons, a rectangular parallelepiped region (hereinafter referred to as a bounding box) that represents a minimum outermost contour in a three-dimensional space including a model is used. Then, the rough check is performed, and the non-interference state is excluded early, so that the overall processing speed can be improved.

The rough check using the bounding box is not limited to the model, but the surface (Fa) which is a component of the model.
c)) is similarly performed, and interference detection between polygons can be omitted for surfaces that do not interfere with each other. Further, for each polygon in the polygon mesh, the rough check between the polygonal bounding boxes can be performed to increase the speed.

As described above, when detecting the interference state between arbitrary models, the rough check using the bounding box is performed for each model or each component element of the model, and it is unavoidable to finally perform the rough check between polygons. By reducing the number of detailed interference checks of, it becomes possible to realize the interference check between models in a large-scale assembly while ensuring interactive operability.

It is an object of the present invention to provide an apparatus, method and medium for recording the program for detecting the interference state between the models constituting the assembly at high speed and obtaining the result.

[0008]

According to a first aspect of the present invention, there is provided an interference model detecting device for detecting an interference state between models constituting an assembly in a three-dimensional shape assembly represented by a polygon mesh, It is determined whether or not the models may interfere with each other from the model boundary box information table that stores the boundary box information in the three-dimensional space for each model that constitutes the assembly and the positional relationship between the boundary boxes in each model during assembly. And a model boundary interference determination unit.

According to a second aspect of the present invention, in the first aspect of the present invention, a surface bounding box information table that stores bounding box information in a three-dimensional space for each surface forming the model, and a boundary between the surfaces in the model. From the positional relationship of the boxes, a surface boundary interference determination unit that determines whether or not there is a possibility of surface interference, and for the two models determined to have interference by the model boundary interference determination unit, The feature is that whether or not there is a possibility that the surfaces interfere with each other is determined from the positional relationship of the bounding boxes of the surfaces forming the model.

A third aspect of the present invention is the interference model detecting apparatus according to the second aspect of the present invention, which is a polygonal bounding box information table storing bounding box information in a three-dimensional space for each polygon included in a surface. A polygon boundary interference determination unit that determines whether or not polygons may interfere with each other based on the positional relationship of the boundary boxes of the polygons in the plane, and the surface boundary interference determination unit may cause interference. With respect to the determined two surfaces belonging to different models, whether or not there is a possibility that the polygons interfere with each other is determined from the positional relationship of the boundary boxes of the polygons included in the surfaces.

According to a fourth aspect of the present invention, in the second or third aspect of the invention, the data structure used in the interference model detecting apparatus according to the second or third aspect stores the vertex coordinates in a three-dimensional space. The apex coordinate table and an index table indicating the elements in the apex coordinate table are configured for each model (indexed facet format), and the index table is stored in order from the top for each face that configures the model. It is a thing.

According to a fifth aspect of the present invention, the data structure according to the fourth aspect has a polygon mesh format of indexeds.
It is characterized in that it has a trip set format.

According to a sixth aspect of the invention, the data structure according to the fourth aspect has a polygon mesh format indexed.
It is characterized in that it is in the fanset format.

According to a seventh aspect of the present invention, the data structure according to the fourth aspect has a polygon mesh format of indexeds.
It is characterized in that it is in a trip and fan set format.

According to an eighth aspect of the present invention, in a three-dimensional shape assembly represented by a polygon mesh, there is provided an interference model detection method for detecting an interference state between models constituting the assembly, wherein The feature is that whether or not there is a possibility that the models interfere with each other is determined from the positional relationship of the bounding boxes in the three-dimensional space.

The invention of claim 9 is based on the positional relationship of the bounding boxes in the three-dimensional space of each surface forming the models for the two models judged to have the possibility of interference in the invention of claim 8. It is characterized by determining whether there is a possibility that the surfaces interfere with each other.

According to a tenth aspect of the invention, in the case of the ninth aspect of the invention, when it is determined that there is a possibility of interference between two surfaces belonging to different models, the polygons included in the surface are displayed in a three-dimensional space. It is characterized by determining whether or not there is a possibility that polygons will interfere with each other, based on the positional relationship of the bounding box.

An eleventh aspect of the present invention is a computer-readable recording medium in which a program for executing the interference model detecting method according to any one of the eighth to tenth aspects using a computer is recorded.

[0019]

1 is a system configuration diagram of a three-dimensional shape processing apparatus to which the present invention is applied. The apparatus is a bus 1, a CPU 2, a memory 3, an external storage device 4, an input device 5, and a display. It is realized by a computer system including the device 6 and a program operating on the computer system.

FIG. 2 is a functional block diagram of a three-dimensional shape processing apparatus to which the present invention is applied.
The input reading unit 12, the shape storage unit 13, the model boundary interference determination unit 14, the surface boundary interference determination unit 15, the polygon boundary interference determination unit 16, and the shape display unit 17 are configured.

FIG. 3 is a flow chart for explaining the operation until the measurement is obtained, and the present invention operates as follows. S1. Bounding box information in the three-dimensional space of the model forming the assembly is calculated and stored in the table. The bounding box information of the model is defined by a total of 6 values of the minimum value and the maximum value in each direction (x, y, z) of the existence area in the three-dimensional space of all the vertex coordinate values of the polygon mesh forming the model. To be done.

S2. In all combinations that extract two models from the assembly, check if the bounding boxes of the models interfere. If it is determined that the bounding boxes of the models do not interfere, the process moves to the next model combination. If the boundary boxes of the models do not satisfy the condition of not interfering, it is considered that the two models may interfere, and the process proceeds to the subsequent steps. Here, it may be possible to obtain a result that the two models have a possibility of interference and move the process to the next combination of models. In that case, a combination of models that may interfere may be obtained at high speed by omitting the detailed check that requires a calculation cost thereafter (claim 1,
8). The interference state between the bounding boxes requires that the minimum value in one of the bounding boxes exceeds the maximum value in the other, x, y,
It is possible by the determination method that the bounding box does not interfere if it is satisfied in any one direction of z.

S3. The bounding box information of the faces (Faces) forming the model is stored in a table for the two models that may cause interference. The boundary box information of the surface is defined by a total of 6 values of the minimum value and the maximum value in each direction (x, y, z) of the existence area in the three-dimensional space of all the vertex coordinate values of the polygon mesh forming the surface. To be done. When tracing the part that constitutes a specific surface in the polygon mesh information that represents the model, if the data structure in which the indices that refer to the vertex coordinates are grouped for each surface and lined up from the beginning, the polygon mesh is acquired for each surface. It is very efficient (Claim 4). Polygon mesh format is indexed str
ip set and indexed fan set,
Or indexed strip and fan
The same can be applied to the case of set (Claims 5, 6, and 7).

S4. It is checked whether the bounding boxes of the surfaces interfere with each other in all combinations in which two surfaces are extracted from two different models. If it is determined that the bounding boxes of the faces do not interfere, the process moves to the next face combination. If the bounding box of the faces does not satisfy the condition of not interfering, it is considered that there is a possibility of interference between the two faces, and the process proceeds to the subsequent steps. Here, it is possible to obtain the result that there is a possibility of interference on the two surfaces, and move the processing to the next combination of surfaces. In that case, by omitting the subsequent detailed check that requires calculation cost, it is possible to obtain a combination of surfaces that may interfere with each other at high speed (claims 2 and 9).

S5. The bounding box information of each polygon forming the surface is stored in the table for the two surfaces that may cause interference. The boundary box information of a polygon is obtained by calculating the minimum value and the maximum value in each direction (x, y, z) of the existing area in the three-dimensional space of three or more vertex coordinates that form the polygon. Is defined.

S6. It is checked whether the boundary boxes of polygons interfere with each other in all the combinations in which two polygons are extracted from two surfaces on two different models. If it is determined that the polygonal bounding boxes do not interfere, the process moves to the next polygon combination. If the bounding box of the polygons does not satisfy the condition that they do not interfere, the two polygons are considered to possibly interfere with each other and proceed to the subsequent processing (claims 3 and 1).
0).

S7. With respect to the two polygons having the possibility of interference, it is checked whether the polygons are in the interference state.
If it is determined that the polygons do not interfere with each other, the process proceeds to the next polygon combination in S6. As a method of checking the interference between polygons, a generally known geometrical analysis method may be used. For example, there is a method of performing interference calculation between a line segment connecting vertices forming one polygon and a plane on which the other polygon lies, and determining whether or not the obtained intersection exists in the polygon. When it is determined that the polygons interfere with each other, it is possible to obtain a result that the two models interfere with each other at the surface of interest and the position of the polygon. here,

When the result that the S7-1.2 model is interfering is obtained, by repeating the process to the next polygon combination in S6, all the interfering polygons can be detected. .

S7-2. Further, by omitting the subsequent checks between the same planes and repeating the process to the combination of the next planes in S4, the interfering planes are minimized while minimizing the number of processings described in S5 to S7. Can detect all.

S7-3. Further, by omitting subsequent checks between the same planes and checks between the same models, and repeating the process of shifting to the next model combination in S2, the number of processes described in S3 to S7 is minimized. , Can detect all interfering models.

[0031]

According to the invention described in claim 1 or claim 8, by performing the rough check by the boundary box of the model, it is possible to obtain a combination of models having a possibility of interference at high speed, and When performing detailed detection of the interference state, it is possible to perform the narrowing down so as to perform the interference detection of the boundary box of the surface only for the combination of models having the possibility of the interference.

According to the invention described in claim 2 or claim 9, by performing the rough check by the boundary box of the surfaces, it is possible to obtain a combination of surfaces having a possibility of interference at high speed. In the case of detecting the interference state, it is possible to perform the narrowing down so as to perform the interference detection of the polygonal bounding box only for the combination of the surfaces having the possibility of interference.

According to the invention described in claim 3 or claim 10, by performing the rough check by the boundary box of polygons, it is possible to obtain a combination of polygons having a possibility of interference at high speed, and further, a calculation cost. When such interference detection of polygons is performed, it is possible to perform narrowing down so as to perform only for combinations of polygons that may cause interference.

According to the fourth aspect of the present invention, it is possible to efficiently obtain information when the polygon mesh representing the model is obtained in units of faces.

According to the invention described in claim 5, the effect of claim 4 can be obtained when the polygon mesh format is the index strip set format.

According to the invention of claim 6, the effect of claim 4 can be obtained when the polygon mesh format is the index fanset format.

According to the seventh aspect of the invention, the polygon mesh format is index strip and fa.
The effect of claim 4 is obtained in the case of the n set format.

According to the eleventh aspect of the present invention, a program for executing the interference model detecting method according to any one of the eighth to tenth aspects using a computer is stored in, for example, a removable recording medium. To be done.

[Brief description of drawings]

FIG. 1 is a system configuration diagram of a three-dimensional shape processing apparatus to which the present invention is applied.

FIG. 2 is a functional block diagram of a three-dimensional shape processing apparatus to which the present invention is applied.

FIG. 3 is a flowchart illustrating the operation of the present invention until measurement is obtained.

[Explanation of symbols]

1 ... Bus, 2 ... CPU, 3 ... Memory, 4 ... External storage device, 5 ... Input device, 6 ... Display device, 11 ... Input unit, 12
Input reading unit, 13 ... Shape storage unit, 14 ... Model boundary interference determination unit, 15 ... Surface boundary interference determination unit, 16 ... Polygon boundary interference determination unit, 17 ... Shape display unit.

Claims (11)

[Claims] 1. An interference model detection device for detecting an interference state between models constituting an assembly in a three-dimensional shape assembly represented by a polygon mesh, wherein each model constituting the assembly has a three-dimensional space. From the model bounding box information table that stores the above bounding box information and the positional relationship of the bounding boxes in each model during assembly,
An interference model detection device, comprising: a model boundary interference determination unit that determines whether or not there is a possibility of model interference. 2. The possibility of surface interference due to the surface boundary box information table storing the boundary box information in the three-dimensional space for each surface forming the model and the positional relationship of the boundary box in each surface in the model. And a surface boundary interference determination unit that determines the presence / absence of each of the two models that are determined to have a possibility of interference by the model boundary interference determination unit. The interference model detection device according to claim 1, wherein it is determined whether there is a possibility that the surfaces interfere with each other. 3. An interference model detection device, wherein a polygonal bounding box information table that stores bounding box information in a three-dimensional space for each polygon included in a surface and a positional relationship between the bounding boxes in each polygon within the surface. And a polygon boundary interference determination unit that determines whether there is a possibility that the polygons will interfere with each other, and two surfaces that belong to different models and that are determined by the surface boundary interference determination unit to have the possibility of interference. 3. The interference model detection device according to claim 2, wherein the presence / absence of polygons may be determined from the positional relationship of the bounding boxes of the polygons included in the surface. 4. A data structure used in the interference model detection device according to claim 2 or 3, wherein a vertex coordinate table storing vertex coordinates in a three-dimensional space and an index indicating an element in the vertex coordinate table. 4. A table is configured for each model (indexed facet format), and the index table is stored in order from the head for each surface that configures the model.
The interference model detection device described in 1. 5. The data structure according to claim 4, wherein the format of the polygon mesh is indexed strip set.
An interference model detection device characterized by having a format. 6. The interference model detection device according to claim 4, wherein the polygon mesh has an indexed fanset format. 7. The data structure according to claim 4, wherein the format of a polygon mesh is indexed strip and
An interference model detection device having a fan set format. 8. A three-dimensional shape assembly represented by a polygon mesh, which is an interference model detection method for detecting an interference state between models constituting the assembly, wherein each model in the assembly has a three-dimensional space. An interference model detection method characterized by determining whether or not there is a possibility of model interference based on the positional relationship of the bounding boxes. 9. With respect to two models determined to have a possibility of interference, it is determined whether or not there is a possibility of surface interference based on the positional relationship of the bounding boxes in the three-dimensional space of each surface constituting the model. The interference model detection method according to claim 8. 10. When it is determined that there is a possibility of interference between two surfaces belonging to different models, the polygons interfere with each other based on the positional relationship of the bounding boxes in the three-dimensional space of each polygon included in the surfaces. The interference model detection method according to claim 9, wherein the presence or absence of the possibility is determined. 11. A computer-readable recording medium recording a program for executing the interference model detecting method according to claim 8 by using a computer.