JPH0724075B2 - Shape data storage / processing method in CAD / CAM system - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (Technical Field of the Invention) The present invention relates to CAD (computer Aided Design) and CAM (Com
Shape data storage of shape modeling system that has both free-form surface shape and mathematical expression shape of automobile, fluid equipment, home appliances, OA equipment, etc. in puter Aided Manufacturing)
It relates to a processing method.

(Technical background of the invention and its problems) When the die machining is to be realized by using the concept of CAD / CAM, which is mainly NC (Numerical Control) machining, the machining operator can quickly It is important to have a function that can sufficiently reflect the operator's know-how such as changing the tool path. Considering this point, when considering the shape processing system, it is necessary to satisfy the following requirements (1) to (3).

The shape definition function and the tool path generation function are completely separated. The tool path can be automatically generated in real time. The mathematical expression and the free-form surface shape can be processed by the same processor. A set of combinations of them. Operation is possible. Easy connection with CAD system. Compact system software. By the way, shape modeling constructs a mathematical model of a three-dimensional object inside a computer and makes it suitable for the required problem. It is to process and express it externally. Therefore, a mathematical model must first be created, and CSG (Constructive Solid Geom
etry) or B-Reps (Boundary Representation) 2
There are mainly two methods.

First, the CSG-based model creates a closed point set area in a three-dimensional space as a three-dimensional object shape model based on one side of the three-dimensional space divided into two by a curved surface, that is, a set of half-space areas. .

On the other hand, B-Reps gives topological relations such as points, edges, and curved surfaces of an object and geometrical information of vertices, edges, and curved surfaces that are elements of the topological relation, and creates a closed two-dimensional manifold in three-dimensional space. This is a shape model of a three-dimensional object.

When defining shapes in conventional CAD and CAM systems, CS
It is customary to express a combination of simple shapes that can be expressed by mathematical expressions like G, and the principle of logical operation (set operation) is used as the combination method.

The conventional system example by CSG has a configuration as shown in FIG. 1, and the shape data input from the shape data input device 10 is separated into object structure data 21 and mathematical expression shape data 22, and these data are the boundaries. It includes the information of the surface indicating. Therefore, the solid shape of FIG. 2 is decomposed into the shape elements (primitives) 210 to 212 of FIG.
A solid shape 200 is obtained by subtracting the primitive 210 from the shape obtained by adding 211 and 212. In this way, the CSG system requires the function information indicating the boundary, so that the conventional CS
G cannot handle free-form surface data and is not included in the shape data 20. The shape data 20 is sent to the shape extraction processing unit 40, and the spatial information SP corresponding to the application-corresponding processing (43) such as display and tool locus generation is input to generate three-dimensional overall shape information TS. That is, the formulated shape data 22 and the spatial information SP are combined in the formulated shape processing 41, and the combined formulated shape SSP is subjected to a set operation 42 together with the object structure data 21 so that the entire shape information TS is obtained.
Is generated. This overall shape information TS is displayed on the screen (10
1), the trajectory of the NC tool is generated (102), the mass property calculation process (103), the face intersection line calculation process (104), and the application information S1 indicating the process corresponding to these applications. ~ S4 is output and converted into spatial information SP in the processing 43 corresponding to the application.

By the way, in the case of CSG, the data structure is simple, and it is considered that high-speed processing is possible based on the processing method.

However, when the hatched shape of FIG. 4 is represented by the shape data 20 by CSG, the object structure data 21 is P
= B−A + C−D, and the mathematical expression shape data 22 is described as shown in FIG.

Here, the formalized shape data of a circle is represented by the coordinates of the center point and the radius, and the rectangle is represented by the length of the long side and the short side, and the data length differs depending on the shape. Therefore, it is necessary to prepare the longest memory area MA of the expected shape as the memory area for storing the shape data of the shape data, and a shape having a smaller data amount than the longest memory area MA was input. In case of blank area BM which is empty
There is a problem that occurs.

(Object of the Invention) The present invention has been made under the circumstances described above.
The object of the present invention is to use the advantages of the CSG method, while being able to handle the free-form surface shape and the mathematical expression shape with the same algorithm, and to use the memory effectively when handling shape data. It is to provide a storage / processing method of shape data in the system.

(Summary of the Invention) The present invention provides an input device to which shape data and object structure data are input, a shape extraction processing unit that performs a set operation using the shape data and the object structure data, and a shape extraction processing unit. In a CAD / CAM system including an application processing unit that performs screen display processing based on the output overall shape information, in the CAD / CAM system, as the shape data, the mathematical expression shape data and / or the parameter space that represents the mathematical expression shape in the real space. Input the free-form surface data representing the free-form surface shape, input the object structure data, store the object structure data in the memory by the reverse Polish description method together with the formulated shape data, and store the free-form surface data as it is in the memory. Stored in the reverse polish description object structure data and formulated shape data and / or The curved surface data is sequentially read, and the mathematical expression shape data and / or the free curved surface data is expressed from an arbitrary position in the real space by a convergence calculation using the read mathematical expression shape data and / or the free curved surface data. The surface normal vector to the surface is obtained, the distance and direction are calculated and stored in the storage area, and the operation code in the read object structure data is compared with the processing result stored in the storage area. Then, a series of processes of performing calculation and storing the result in the storage area again are repeated, and finally the overall shape information is stored in the storage area.

(Embodiment of the Invention) FIG. 6 shows an example of a system for realizing the method of the present invention in correspondence with FIG. First, shape data input device
Enter the shape data from 10. It is desired that the shape input method be intuitively understandable by humans and that the expression ability be rich. Here, a combination of primitive input and set operation is used. Since complex shapes are created step by step, modification operations such as deformation, addition and deletion of shapes also play a major role in constructing shapes.

Primitive input is a method in which a simple figure such as a rectangular parallelepiped or a cylinder is registered as a basic shape, and this is taken out as needed.

As the shape data 20 by the CSG, the function information of the surface indicating the boundary is used, and the free-form surface data 23 does not include the boundary data.

Therefore, when one of the application processes such as the screen display process 101 is executed, the data SI and the like from the process are input to the processes 43 and 44 corresponding to the application. The process 43 corresponding to the application sends it as SP1 to the mathematical shape processing 41. Application-aware process 44 SP it
2 is sent to the free-form surface calculation processing 45. Formulation and shape processing 41
Evaluates and determines each data of the formulated shape data 22 based on SP1, and stores the result in the shape information stack area 46. On the other hand, the free-form surface evaluation calculation processing 45 makes an evaluation / judgment based on SP2 for each data of the free-form surface data 23, and stores the result in the shape information stack area 46. The evaluation / determination in the mathematical expression shape processing 41 and the free-form surface evaluation calculation processing 45 will be described in detail later.
The set operation 42 has a shape information stack area 46.
Based on the object structure data 20, the set operation is performed on the evaluation results of the individual shape data stored in. The resulting TS is returned to the application processing such as the screen display processing 101.

For example, the screen display process 101 will be described. In order to display the overall shape, it is only necessary to be able to determine whether or not an arbitrary point in the real space is inside or outside the overall shape. Therefore, regarding the coordinate information from the screen display processing 101, for each shape data, the mathematical expression shape processing 41 or the free-form surface evaluation calculation processing 45 evaluates whether it is the inside or the outside, that is, which half space side, and the evaluation result By performing a set operation on the basis of the object structure data 21, it is possible to determine whether the coordinate position is inside or outside of the overall shape. To display the outline of the entire shape, it is sufficient to search for a coordinate position having an evaluation value of 0, not on the inside or outside.

By the way, although the shape data is divided into the object structure data 21 and the mathematical expression shape data 22 and the two-dimensional shape is explained above, the mathematical expression data of the sphere is represented by the central coordinates and the radius, and the rectangular parallelepiped is shown in FIG. As shown in (A), it is represented by three points CB1 to CB3 defining one surface and a width W orthogonal to the surface. The cylinder is represented by the center and radius of the bottom circle and the unit vector and height in the axial direction, and the cone is the center CP1 and radius r of the bottom circle and the unit in the axial direction as shown in FIG. 7 (B). It is represented by the vector and height H, and the inclination angle Θ of the slope.

Considering such a three-dimensional shape, the redundancy of the memory capacity of the shape data storage unit is further increased. For this reason, in the present invention, the shape data described by the reverse Polish description method is sequentially stored in the memory so that the required memory capacity is not wasted. That is, in this example, the shape data store portion is not divided into object structure data and mathematical expression shape data, but is organized into one piece of shape data 24 described in reverse polish as shown in FIG. That is, the object structure data is described in reverse polish, and the formula data is attached to the structure data of the formula shape data. However, the data of free-form surface data itself is secured independently.

Hereinafter, the overall processing of the system shown in FIG. 8 will be described.

First, the formulated shape data, free-form surface data and object structure data are input to the shape data input device 10. At this time, the shape data input device 10 performs compiler processing on the input object structure data. For example, in the case of the shape shown in FIG. 4, the input (P
= B-A + C-D) 11 is subjected to compiler processing 12, which is a general computer software processing, to obtain shape data 24 described in reverse Polish. If such a storage method is used, the shape data is stored in order from the beginning of the memory area MA. The shape data can be sequentially input and stored within the range of the memory area MA.

Although FIG. 9 shows an example of collectively obtaining the shape data 24 described in reverse polish by the compiler processing 12, the shape data 24 can be sequentially obtained according to the flow shown in FIG. First, "P" indicating that the input shape is P is stored in the memory (step S1), and when the mathematical expression shape data of the shape B is input (step S2), the data is converted into a format suitable for internal processing of the computer. Converted (step S3) and stored in memory (step S3)
Four). Next, the operation code (-) is input (step S5), the formulated shape data of the shape A is input and data is converted, and the result is stored in the memory (steps S6 to S8). After that, the operation code (-) is stored in the memory (step S9), then the operation code (+) is input (step S10),
Further, the formulated shape data of the shape C is input (step S1
1) Similarly, the data is converted and the result is stored in the memory (steps S12 and S13). The operation code (+) is stored in the memory (step S14), the operation code (-) is input (step S15), and the formulated shape data of the shape D is input (step S16).
After the data conversion, the result is stored in the memory, the operation code (-) is input and "=" is input (steps S17 to S20), and the shape data 24 as shown in FIG. 9 is generated. It is stored in the memory for inputting shape data.

In the present invention, the formulated shape data is further stored along with the structure data in a series of memories immediately after that.

The shape data 24 described in reverse polish and stored in the memory as described above is processed by the shape extraction processing unit 40 to store the entire shape information TS in the shape information stack area 46A.

Description will be made with reference to FIG. First, when one of the application processes such as the screen display process 101 is executed, the data S1 and the like from the process are processed by the application.
Entered in 3, 44. The process 43 corresponding to the application sends it as SP1 to the mathematical shape processing 41. The process 44 corresponding to the application sends it to the free-form surface calculation process 45 as SP2. Next, information is transferred to the shape extraction processing unit 40 in order from the start address of the shape data 24. Shape extraction processing unit
Reference numeral 40 determines whether the information is formulated shape data, object structure data (operation code) or free-form surface data. As a result, if it is the formulated shape data, the formulated shape processing 41 executes SP for the data.
The evaluation / judgment based on 1 is performed, and the result is stored in the shape information stack area 46A. If it is free-form surface data, free-form surface evaluation calculation processing 45
The evaluation / judgment based on 2 is performed, and the result is stored in the shape information stack area 46A. If it is object structure data (operation code), set operation
42A performs an operation based on the operation code for the two evaluation results stored in the shape information stack area 46A, and the result is again calculated in the shape information stack area 46A.
To store. In this way, by sequentially introducing data from the shape data 24 and the free-form surface data 23 described in reverse polish and repeating the above processing, the evaluation result for the entire shape is finally stored in the shape information stack area 46A. Will be. Then, the result is returned to the application processing such as the screen display processing 101 as a TS.

The above processing will be described below with a specific example shown in FIG.

Therefore, the shape information stack area 46A has three areas AR1.
~ It is divided into AR3. First, when the information indicating that it is the shape P is transferred, it is discriminated and stored in the area AR1 (state ST1), and then the formulated shape data B is transferred and stored in the area AR2 (state ST2). ). After that, the following formulated shape data A is transferred and stored in the area AR3 (state ST3), and the operation code (-) is transferred to calculate (BA) in the area AR2, and as a result, S1 is obtained. Stored in area AR2 (state ST
Four). When the next formulated shape data C is transferred, it is stored in the area AR3 as in the state ST5, and then the operation code (+) is transferred, so that the result S of the area AR2 is obtained.
1 and the mathematical expression shape data C of the area AR3 are added, and the result (S1 + C) is stored in the area AR2 (state ST
6). After that, the formulated shape data D is transferred to the area A.
Stored in R3 (state ST7), the operation code (-) is transferred to calculate (S2-D) and stored in area AR2 (state ST8). When "=" is transferred, state ST9 Thus, (S2-D), that is, P = BA + CD is stored in the area AR1. As a result, the input shape data P is input to the shape information stack area 46A.
The entire shape information of is stored. Therefore,
The memory capacity of the shape information stack area 46A is also small.

Next, the processing in the free-form surface evaluation calculation processing 45 will be described in detail. That is, this is a process of evaluating which side of a half space a certain coordinate position of a free-form surface is divided into.

Therefore, as shown in FIG. 12, it is calculated what kind of positional relationship the coordinate values (x, y, z) specified in the real space have with respect to the curved surface 1 which is parameterized (u, v). To do. The calculation method uses a convergence calculation. The outline of the convergence calculation will be described below, and then the details thereof will be described.

The basic concept of half-space domainization is the realization of evaluation in the space of free-form surfaces. Now, as shown in FIG. 13, a point P is assumed above the free curved surface, and a distance from an arbitrary point N on the curved surface 1 to a given point P is E. When the distance E is calculated for all infinite positions existing on the curved surface 1 and points on the curved surface 1 having the same value of the distance E are connected, as shown in FIG.
A contour line of distance E can be drawn above. FIG. 15 is a diagram showing this with the E axis and the u and v axes on the curved surface. This is a distance function from the curved surface 1 to the given point P, and this function is set to Ψ (u, v). Then, for this function, the curved surface 1
When the directional differential coefficient is obtained for the above u direction, Becomes Let θ be the unit vector and the angle made by grad Ψ be θ ₁ . To get Similarly for v direction To get Now, to find the minimum value of this potential function, The following conditions must be met. Also, Therefore, if | ▽ Ψ | ≠ 0, cos θ ₁ = 0, cos θ ₂
Must be = 0. Therefore, θ ₁ = 90 °, θ ₂ = 90 °
Becomes Here, since θ is the angle formed by each direction on the curved surface and grad Ψ, E, which minimizes the potential function value, is the distance from the given point P to the given point P in the direction of the surface line.

The minimum potential value indicates the shortest distance of a given point to a curved surface, which is a value for spatially evaluating a curved surface expressed parametrically.

If the surface interpolation formula is (u, v), then the potential value is Ψ (u, v) ＝ ｜ － ｜ (6), and considering the direction of potential, (u, v) ＝ － (U, v)… (7) Now find the point on the surface that gives the minimum potential value
Given u ₁ and v ₁ , the potential vector is (u ₁ , v ₁ ) = − (u ₁ , v ₁ ) ... (8). Since the direction of giving a potential minimum u _1, v surface normal on ₁ and Ψ (u _1, v ₁₎ is consistent, S = (u ₁ When the surface normal vector of u _1, v _1, v ₁ ) ··· (9), the sign of the potential can be determined,
As a result, the orientation of the half-space region can be performed.

Parameter value on the surface with the smallest potential (u ₁ , v ₁ )
By calculating, the half-space area can be divided into the free-form surface. The parameter value (u ₁ , v ₁ ) should be obtained based on the above, but analytically (u ₁ ,
Since it is impossible to obtain v ₁ ), it is necessary to use a search method. That is, the search initial position (u ₀ ,
v ₀₎ is set and the minimum value with respect to at that time Ψ (u _0, v ₀₎ is _{-grad Ψ (u 0, v 0} ) be in the direction understandable.

here Therefore, − ▽ Ψ = − ・ ｜ ▽ Ψ | cosθ ₁ − ・ ｜ ▽ Ψ | cosθ ₂ …
… (11) This is (-| ▽ Ψ | cosθ ₁ ,-| ▽ Ψ | cosθ
₂ ) It shows that there is a desired solution in the direction. Here, since Ψ (u ₀ , v ₀ ) is obviously the distance from the given point P, the position to be obtained next is u ₁ = −Ψ (u ₀ , v ₀ ) · | ▽ Ψ | cos θ ₁ + u ₀ v ₁ = −Ψ (u ₀ , v ₀ ) ・ | ▽ Ψ | cos θ ₂ + v ₀ (12) Here, assuming that = (u, v), the above equation (12) is generally expressed as follows: _i = Ψ ( _i−1 ) · ▽ Ψ ( _i−1 ) + _i−1 .
You can write (13). Ψ ( _i−1 ) is the search step, − ▽ Ψ (
_i-1 ) indicates the search direction. The next search position is obtained from this formula, and S = (-( _i )). (Is the surface normal) ... (14) may be monitored for each search position. X _i when S≈1 or S≈−1 is the minimum potential position.

The above theory will be specifically described.

As shown in FIG. 16, the curved surface 1 is represented by two parameters u and v, and the position vector of a point arbitrarily designated in the real space is defined as. Now, assuming that the initial parameter value is (Pu, Pv) and the position vector (Pu, Pv) on the curved surface 1, the vector becomes =-(Pu, Pv) ... (15), and for this vector ＝ ∂ / ∂u × ∂ / ∂v …… (16) / |｜ ≒ / |｜ (17), || is the shortest distance from the curved surface 1 to an arbitrary point. Next, a method for obtaining parameters (Pu, Pv) that satisfy the above equation (17) will be described. Figure 17 shows the curved surface 1 at the parameter (Pu, Pv) points.
The tangent vector 1A of FIG. Calculating ′ by projecting a vector on this tangential plane 1A, the direction of the vector is calculated by ′ ＝ (×) × …… (18), and then ′ ＝ || sin θ ・ '/ |' | It can be obtained by calculating.

Then, with respect to this vector ', the components in the tangent vector (u, v) in the u, v directions existing on the tangent plane 1A are calculated. The calculation is that each direction component is TU, TV,
Letting θ and Ψ be the angles between the u and x axes and the v and y axes, TU = V′x cos θ−Vy sin θ (20) TV = V′x sin Ψ−Vy cos Ψ (21). It can be said that the parameters moved from the initial parameters by the amount of the parameter corresponding to the TU and TV indicate the curved surface positions that may further satisfy the above equation (17). This parameter is calculated as follows: PUnew = PU + TU / DU (22) PVnew = PV + TV / DV (23), where DU and DV are the boundary lengths of the curved surfaces in the u and v directions. Based on this result, we return to equation (14) again,
This process is repeated until the expression (17) is satisfied. (17)
|| that satisfies the expression represents the distance from the surface. However, as it is, it is not clear which direction the surface is facing, so it is necessary to determine the polarity described below.

Therefore, for ′ that satisfies the above equation (17), As shown below, when the opening angle of and 'is 90 ° or more, AN is negative, and when it is 90 ° or less, AN is positive. Since and ′ are almost on the same straight line, AN ≈ 1; same direction as the surface normal vector −1; opposite direction to the surface normal vector, and the evaluation function value is Then, the evaluation function can determine whether the shape is inside or outside.

As the handling of the evaluation function at the surface boundary, there is a range of areas to which the evaluation function can be applied. The evaluation function is represented by the distance in the surface normal direction of the surface expressing the shape with respect to an arbitrary scan point. Therefore, there is an applicable range as shown in FIG. However, when performing the calculation of the evaluation function, (2
The results of Eqs. 2) and (23) may fall outside this range. Since this position does not exist on the curved surface 1, it is impossible to set a surface normal to the scan point from that position, and special consideration must be given to the handling of the evaluation function outside the region.

Here, the vector shown in FIG. 19 is used as the evaluation vector. That is, with respect to the surface normal 6 perpendicular to the boundary line 5 of the patch 4, a vector orthogonal to the boundary line 5 is considered, and the vertical direction vector is set as the evaluation vector.
By using such an evaluation vector, although the evaluation function is approximately, the distance from the patch curved surface 4 is clarified as shown in FIG. 20, and the vertical relationship (front-back relationship) with respect to the surface 4 is clarified. The calculation method is (22) and (23) above.
It is determined where the result of the expression belongs to the areas A to H shown in FIG. This is a region determination on the parameter space. For this judgment, prepare a relation (4) for each boundary line such that F (u, v) ≤ 0 that makes the region expressing the inside of the shape negative in the parameter space, and compare all the values. Can be done easily. Next, as shown in FIG. 22, the intersection point IP of the straight line and the shape boundary that can be obtained from the previous search position P1 in the parameter space and the result P2 of the above equations (22) and (23) is obtained. . The straight line formula is Therefore, the intersection IP can be easily obtained. Based on this parameter, the processing for obtaining V'is performed again. If the result P2 of the equations (22) and (23) is out of the area even after this processing, the boundary line and the scan point are searched as shown in FIG. 23, and ′ · = 0 ...... The polarities for obtaining the evaluation function values as shown in Fig. 16 are the same as those described above. In addition,
FIG. 23 shows a vector'between the point (u, v) on the boundary line 5 and the scan point SC, and a tangent vector at the point (u, v). The method for obtaining the result of equation (27) is as shown in FIG. The above is the evaluation method for the free curved surface in the free curved surface evaluation calculation means 45.

Since the free-form surface can be evaluated as described above, the line of intersection between two free-form surfaces as shown below can be obtained. As shown in FIG. 25, two curved surfaces 4A and 4B
The scan line 7 is set on one of the surfaces, and the evaluation method based on the above method is used for points on the line 7. At this time, the relationship between the evaluation function calculated by this evaluation method and the scan line is as shown in FIG. 26, and the position where the evaluation function becomes 0 is the intersection of the scan line 7 and the surface 4A, and all scans are performed. When this intersection is obtained for the line 7, the intersection group represents the intersection between the curved surfaces 4A and 4B. The above processing is the same as in the mathematical expression shape processing 41.

(Effects of the Invention) As described above, according to the shape data storage / processing method of the present invention, it is possible to effectively use the memory while making the most of the advantage of the CSG method, and to calculate the mathematical expression even if the free curved surface shape is included. It can be processed in the same manner as the modified shape.

BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram showing an example of a conventional system using CSG, FIGS. 2 and 3 are diagrams for explaining a set operation, and FIGS. 4 and 5 are shape data. FIG. 6 is a block diagram showing an example of a system for implementing the method of the present invention, FIGS. 7 (A) and 7 (B) are diagrams for explaining formulated shape data, and FIG. FIG. 9 is a block diagram showing an example of a graphic data processing system according to the present invention, FIGS. 9 to 11 are diagrams for explaining generation and processing of shape data described in reverse Polish, and FIGS. Is a diagram for explaining the principle of evaluation of a free-form surface according to the present invention, and FIGS. 18 to 26 are diagrams for explaining a method for determining the polarity of a free-form surface. 4 ... Patch, 10 ... Shape data input device, 12 ... Compiler processing, 20 ... Shape data, 30 ... Formulation shape processing unit, 31 ... Processing information, 40 ... Shape extraction processing unit, 41 ... … Mathematics processing, 42… Set operation, 43, 44…
… Application-compatible processing, 45 …… Free-form surface evaluation calculation processing, 46,46A …… Shape information stack area, 200 ……
Three-dimensional shape.

Claims (1)

[Claims] 1. An input device to which shape data and object structure data are input, a shape extraction processing unit that performs a set operation using the shape data and the object structure data, and an entire output from the shape extraction processing unit. In a CAD / CAM system equipped with an application processing unit that performs screen display processing and the like based on shape information, the free-form surface in the parameter space and / or the mathematical expression shape data that represents the mathematical expression shape in the real space as the shape data. The free-form surface data representing the shape is input and the object structure data is input, the object structure data is stored in the memory by the inverse Polish notation method together with the formulated shape data, and the free-form surface data is stored in the memory as it is, The object structure data described in the reverse polish and the formulated shape data and / or the free-form surface data are A surface from an arbitrary position in the real space to a surface represented by the formulated shape data and / or the free-form surface data by a convergence operation using sequentially read and the read free-form surface data and / or the free-form surface data. The normal vectors are respectively obtained, the processing for obtaining the distances and the orientations thereof is performed and stored in the storage area, and the operation code in the read object structure data is operated on the processing result stored in the storage area. Shape data storage in a CAD / CAM system characterized by repeating a series of processes of storing the result again in the storage area, and finally storing the overall shape information in the storage area. Processing method.