JP2734644B2 - Intersection calculation method between free-form surfaces - Google Patents

Description

Description: BACKGROUND OF THE INVENTION (Industrial application field) The present invention relates to a method of calculating an intersection between free-form surfaces, and in particular, for example, among three-dimensional graphic processing functions provided by a mechanical design support system, two free-form surfaces The present invention relates to a method of calculating an intersecting line between free-form surfaces for obtaining an intersecting line between them.

(Prior Art) Before describing a conventional method of calculating a line of intersection between two free-form surfaces, a method of expressing a free-form surface will be described first.

Conventionally, a B-spline surface has been widely used as a method for expressing a free-form surface in a computer (for example, see Fujio Yamaguchi, Shape Processing Engineering by Computer Display [II], Nikkan Kogyo Shimbun). A B-spline surface is a two-dimensional parameter plane based on positional information of a plurality of points (called control points) in a given three-dimensional space and two sets of non-decreasing numerical sequences (called knot vectors). One point above (u,
This is a method of calculating the position of a point P = (x, y, z) on the curve from v) as follows.

Here, N _i (u) and N _j (v) are B-spline functions of the third order. Q _ij (0 ≦ i ≦ _nu , 0 ≦ j ≦ n _v ) represents a control point. Where n _u and n _v have control points of (n _u +1) × (n _v +1)
Indicates that they are ordered in a grid pattern. Further, two sets of knot vectors are defined as {u _i : 0 ≦ i ≦ _nu + 3}, {v _j : 0 ≦ j
≦ n _v +3｝.

The calculation of the line of intersection between the two surfaces represented by the B-spline surface described above (surface A and surface B) has conventionally been performed using recursive division of the B-spline surface as follows. ing. (For example, Discrete B-Splines
and Subdivision Techniques in Computer-Aided Geom
etric Design and Computer Graphics, COMPUTER GRAPHI
CS AND IMAGE PROCESSING, Vol. 14, pp. 87-111, 1980) Find the minimax box of each of the surface A and the surface B. The minimax box is two planes perpendicular to the x-axis,
The smallest rectangular parallelepiped enclosed by two planes perpendicular to the y-axis and two planes perpendicular to the z-axis and including all control points of the free-form surface. The mini-max boxes of the curved surface A and the curved surface B are referred to as a box A and a box B, respectively.

If box A and box B do not intersect, the process ends.

A comprehensive rectangular parallelepiped of each of the curved surface A and the curved surface B is obtained. The comprehensive rectangular parallelepiped is a rectangular parallelepiped including all the control points of the free-form surface and having a minimum maximum thickness. The comprehensive rectangular parallelepipeds of the curved surface A and the curved surface B are referred to as a rectangular parallelepiped A and a rectangular parallelepiped B, respectively.

If the rectangular parallelepiped A and the rectangular parallelepiped B do not intersect, the process ends.

When the maximum thicknesses of the rectangular parallelepiped A and the rectangular parallelepiped B are both smaller than a predetermined thickness, the intersections are obtained by approximating these with a plane.

When the maximum thickness of the rectangular parallelepiped A is equal to or larger than a predetermined thickness, the curved surface is divided into four by adding a control point and a knot vector to the curved surface A.

Similarly, when the maximum thickness of the rectangular parallelepiped B is equal to or larger than a predetermined thickness, the curved surface B is divided into four.

The intersection of the curved surface A (four curved surfaces generated by division when the curved surface A is divided) and the curved surface B (similarly, four curved surfaces) are obtained by recursively performing the processing of.

(Problems to be Solved by the Invention) When the recursive division of the free-form surface in the conventional method as described above is performed, the data amount increases. Since this increase cannot be determined in advance, dynamic memory management is required in the processing. Further, if a recursive division process is to be performed by a parallel processor, it is necessary to frequently exchange data representing a curved surface between processors. For this reason, the processing efficiency cannot be improved.

(Means for Solving the Problems) In order to solve the above-mentioned problems, in the method of calculating an intersection between free-form surfaces according to the present invention, the control point of the free-form surface A represented by a given B spline is (n _Au +1). ) × (n _Av +1 n _Au indicating that the ordered lattice), with respect to n _Av from (1, 1) (n _Au -3, a natural number of sets of n up _Av -3), the First natural number set generation means for sequentially generating when the notification of 1 is received; control points of the free-form surface B represented by a given B-spline are arranged in a (n _Bu +1) × (n _Bv +1) lattice shape N _Bu and n _Bv , which indicate that
A natural number set up to _Bu- 3, _nBv- 3) is sequentially generated when the second notification or the third notification is received, and the second natural number set is issued when the processing is completed. Generating means; a set of knot vectors ｛u of the surface data in accordance with the given surface data and the natural number set (a, b) sent from the first natural number set generating means or the second natural number set generating means; _i : 0 ≦ i ≦ nu + 3} and {v _j : substrings {u _i : a ≦ i ≦ a + 6} and {v _j : b ≦ j ≦ b + 6} of 0 ≦ j ≦ nv + 3 Control point ｛Q _ij : 0 ≦ i ≦ _nu + 1,0 ≦
a subset {Q _ij of j ≦ n _v +1}: a ≦ i ≦ a + 3, b ≦ j ≦ b
Surface patch generation means for obtaining +3｝; minimax box generation for obtaining minimum and maximum values of x, y, and z coordinate values of 16 control points from the surface patch data obtained by the surface patch generation means Means; x obtained by the minimax box generating means;
a box determination unit that determines whether or not they intersect by comparing the minimum value and the maximum value of the y and z coordinate values, and issues the second notification if they do not intersect; and a box determination unit that is determined by the surface patch generation unit. A comprehensive rectangular parallelepiped generating means for obtaining a rectangular parallelepiped including the 16 control points of the curved surface patch data and having a minimum maximum thickness; and comparing the rectangular parallelepipeds determined by the comprehensive rectangular solid generating means to determine whether or not they intersect, and do not intersect. In this case, a rectangular parallelepiped determination unit that issues the second notification; and an intersection line between the surface patches sent from the surface patch generation unit is obtained by the Newton-Raphson method. Means for calculating an intersecting line between patches for issuing a notification.

(Embodiment) Next, an intersection line calculation method between free-form surfaces of the present invention will be described with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. The intersection of two free-form surfaces is calculated using the method of the present invention as follows.

First, the first natural number set generation means 10 generates a natural number set (1, 1) and sends it to the connected surface patch generation means 30. Similarly, the second natural number set generating means 20 generates a natural number set (1, 1) and sends it to the connected surface patch generating means 30. The surface patch generation means 30 obtains a subsequence of the knot vector and 16 control points corresponding to the transmitted surface data and the set of natural numbers, and calculates this as a minimax box generation means 40 and a comprehensive rectangular parallelepiped generation means 60. It is sent to the intersecting line calculating means 80. Here, the corresponding subsequence of the knot vector indicates {u _i : a ≦ i ≦ a + 6} and {v _j : b ≦ j ≦ b + 6} for (a, b). Also, the corresponding 16 control points are ｛Q _ij : a ≦ i ≦
a + 3, b ≦ j ≦ b + 3}.

The mini-max box generation means 40 obtains the mini-max boxes of the 16 control points and sends them to the box determination means 50. The box determination means 50 determines whether both the sent minimax boxes intersect. If they do not intersect, the second natural number set generation means 20 and the intersecting line calculation means 80
To that effect. The comprehensive rectangular parallelepiped generating means 60 obtains a comprehensive rectangular parallelepiped of 16 control points and sends it to the rectangular parallelepiped generating means 70. The rectangular parallelepiped generation means 70 determines whether both of the sent comprehensive rectangular parallelepipeds intersect. If they do not intersect, the second natural number set generation means 20 and the inter-patch intersection line calculation means 80 are notified to that effect.

The patch straight line intersection calculation means 80 calculates the intersection between the curved surface patches by the Newton-Raphson method, and notifies the second natural number set generation means 20 of the calculation. Further, the patch straight line intersection calculating means 80 is provided with the box determining means 50 during the processing.
Alternatively, upon receiving a notification from the rectangular parallelepiped judging means 70 that no intersection occurs, the processing is interrupted.

In addition, the second natural number set generation unit 20 includes a box determination unit.
50 or the notification that the intersection does not intersect from the rectangular parallelepiped determination means 70, or the notification that the intersection has been obtained from the inter-patch intersection calculation means 80 The notification that the intersection has been obtained from the intersection calculation means 80 When notified, (1,1) to (n _Bu −3, n _Bv −
Of the natural number sets up to 3), a natural number set next to the immediately preceding natural number set is generated. This is repeated up to the processing of the set of natural numbers of (n _Bu −3, n _Bv −3), and when the processing is completed, the first natural number generating means is notified. The first natural number set generation means 10
When receiving the notification that the repetition is completed from the second natural number set generation means 20, the natural number set generated immediately before among the natural number sets from (1,1) to (n _Au −3, n _Av −3) is received. Generate the following set of natural numbers. This is repeated until the processing of a natural number set of (n _Au −3, n _Av −3). Referring to FIG. 2, an application program
91 stores the data of one free-form surface (referred to as surface A), that is, the coordinate values of the control points and a set of knot vectors in the first surface memory 92, and stores the data of the other free-form surface (referred to as surface B). The data is stored in the second curved surface memory 93 (not shown). Next, the application program 91 causes the first pair counter 11 and the second pair counter 21 to start processing.

Each of the first pair counter 11 and the second pair counter 21 notifies the connected patch generator 31 of a natural number (1, 1).

The patch generator 31 outputs a natural number set (a, b) from the connected first pair counter 11 or second pair counter 21.
Receiving the patch data from the connected first surface memory 92 or the second surface memory 93, the patch memory 94
And notifies the mini-max box processor 41, the comprehensive rectangular parallelepiped processor 61, and the intersection calculation processor 81. The surface patch data are knot vector subsequences {u _i : a ≦ i ≦ A + 6} and {v _j : b ≦ j ≦ b + 6}, and
16 control points {Q _ij : a ≦ i ≦ a + 3, b ≦ j ≦ b + 3}.

Minimax box processor 41 has patch memory
The minimum value and the maximum value of x, y, and z of the coordinate values of the control points stored in 94 are obtained and sent to the box determiner 51.

The box determiner 51 compares the two transmitted minimax boxes, and sends a signal to the second pair counter 21 and the intersection calculation processor 81 if they do not intersect.

Based on the coordinate values of the control points stored in the patch memory 94, the comprehensive rectangular parallelepiped processor 61 obtains a comprehensive rectangular parallelepiped of these control points and sends it to the rectangular parallelepiped determiner 71.

The rectangular parallelepiped determiner 71 compares the two comprehensive rectangular parallelepipeds that have been sent, and sends a signal to the second pair counter 21 and the intersection calculation processor 81 if they do not intersect.

The intersection calculation processor 81 calculates the coordinate value of the intersection between the curved surface patches included in the two patch memories 94. Since a surface patch is represented by a polynomial as follows, it can be solved by the Newton-Raphson method.

P (u, v) = [N _{u, 0} (u), N _{u, 1} (u), N _{u, 2} (u), N _{u, 3} (u)] Here, N _{u, i} (u) and N _{v, i} (v) are B-spline functions and are the following polynomials.

_{N u, i (u) =} L i, 4 (u: u a, u a + 1, u a + 2, u a + 3, u a + 4, u a + 5, u a + 6) N v _{, 1} (v) = L _{i, 4} (v: v _b , v _{b + 1} , v _{b + 2} , v _{b + 3} , v _{b + 4} , v _{b + 5} , v _{b + 6} ) Is represented by the recurrence formula of

L _{i, 1} (t: t ₀ , t ₁ , t ₂ , t ₃ , t ₄ , t ₅ , t ₆ ) = 1 (t _i ≦ t <t _i +1) = 0 (other than the above) When the process for finding the intersection is completed, a signal is sent to the second pair counter 21. If a signal is sent from the box determiner 51 or the cuboid determiner 71 during the processing, the processing is interrupted.

When the second pair counter 21 receives a signal from the box determiner 51, the rectangular parallelepiped determiner 71, or the intersection calculation processor 81, the second pair counter 21 (1,2) → (1,3) →... → (n _Bu −3, n _Bv -3) and a set of natural numbers are generated and sequentially sent to the patch generator 31. This is repeated until the processing of the natural number set of (n _Bu −3, n _Bv −3) is completed, and a signal is sent to the first pair counter 11 when the processing is completed.

When receiving the signal from the second pair counter 21, the first pair counter 11 receives (1,2) → (1,3) →... → (n _Au −3, n _Av −
3) and a natural number set is generated and sent to the patch generator 31 sequentially. This is repeated until the processing of (n _Au −3, n _Av −3) natural number sets.

(Effects of the Invention) As described above, in the present invention, since a curved surface is decomposed into a curved surface patch represented by a single polynomial, recursive division is not required for calculating an intersection with a straight line. This eliminates the need for dynamic memory management for calculations,
Furthermore, even when the processing is performed in parallel, the surface patches are independent of each other, so that the degree of parallel processing can be increased.

[Brief description of the drawings]

FIG. 1 is a block diagram showing one embodiment of the present invention, and FIG. 2 is a block diagram showing a specific embodiment of the present invention. 10 first natural number set generating means 20 20 second natural number set generating means 30 curved surface patch generating means 40 minimax box generating means 50 box determining means 60 comprehensive cuboid generation Means 70 cuboid determination means 80 inter-patch intersecting line calculation means 11 first pair counter 21 second pair counter 31 patch generator 41 mini-max box processor 51 … Box determiner, 61… comprehensive rectangular parallelepiped processor, 71… rectangular parallelepiped determiner, 81… intersection line calculation processor, 91… application program, 92… first surface memory, 93… second surface memory, 94
...... Patch memory.

Claims (1)

(57) [Claims] 1. For n _Au , n _Av indicating that the control points of the free-form surface A represented by a given B-spline are ordered in a (n _Au +1) × (n _Av +1) grid. (1,
First natural number set generating means for sequentially generating a set of natural numbers from 1) to (n _Au −3, n _Av −3) when receiving the first notification; and a free-form surface represented by a given B-spline For n _Bu , n _Bv indicating that the control points of B are ordered in a (n _Bu +1) × (n _Bv +1) grid, (1,1) to (n _Bu
-3, n _Bv -3) generating a second set of natural numbers that sequentially generates a set of natural numbers when the second notification or the third notification is received and that issues the first notification when the processing is completed. Means; a set of knot vectors ｛u ₁ of the surface data according to the given surface data and the natural number pairs (a, b) sent from the first natural number pair generating means or the second natural number pair generating means. _{: 0 ≦ i ≦ n u +3} } and _{{v j: 0 ≦ i ≦} n v +3 subsequence {u _i of}: a ≦ i ≦ a + 6} and {v _j: seeking b ≦ j ≦ b + 6} ,
Further, control points ｛Q _ij of the surface data: 0 ≦ i ≦ _nu + 1, 0 ≦ j ≦
n _v subset of _{+1} {Q ij: a ≦} i ≦ a + 3, b ≦ j ≦ b +
Surface patch generation means for obtaining 3｝; minimax box generation for obtaining minimum and maximum values of x, y, and z coordinate values of 16 control points from the surface patch data obtained by the surface patch generation means Means; x obtained by the minimax box generating means;
a box determination unit that determines whether or not they intersect by comparing the minimum value and the maximum value of the y and z coordinate values, and issues the second notification if they do not intersect; and a box determination unit that is determined by the surface patch generation unit. Surface patch data
A comprehensive rectangular parallelepiped generating means for obtaining a rectangular parallelepiped including 16 control points and having a minimum maximum thickness; and comparing the rectangular solids determined by the comprehensive rectangular solid generating means to determine whether or not they intersect. 2
A rectangular parallelepiped judging means for issuing a notice of the following; a line of intersection between the surface patches sent from the surface patch generating means is obtained by the Newton-Raphson method, and when the processing is completed, the interval between the patches for issuing the third notice is obtained. Intersection calculation means; and an intersection calculation method between free-form surfaces.