JPH01175682A - Inter-polygon intersection line calculation system - Google Patents

Abstract

PURPOSE:To reduce calculation required quantity and to shorten a processing time by sorting the intersection point of an edge and a plane found not in order at a spatial position relation and finding an intersection line in the order. CONSTITUTION:A polygon supplying means 12 fetches the equation data of a plane B and the three-dimentional coordinate value of both edge points of the each edge of a polygon A in order from a storage means 11, and an intersection point calculating means 13 calculates the coordinate value of an intersection point. A sorting means 14 sorts the coordinate value of the intersection point and sends the result to an intersection line judging means 15. Next, in the same way, the edge of a polygon B and the intersection point of a plane A are found, and the sorted result is sent to the intersection line judging means 15. The intersection line judging means 15 finds an area involved in common in either area to link the intersection point of the (2n-1)-th and the 2n-th of the sorting result of the intersection point of the polygon A and the plane B and in either area to link the intersection point of the (2m-1)-th and the 2m-th of the sorting result of the intersection point of the polygon B and the plane A as the intersection line of the polygon A and the polygon B. Thus, it is satisfied only by the twice sorting of the intersection point, and calculation required quantity is reduced.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a method for determining an intersection line between two polygons among three-dimensional graphic processing functions provided by, for example, a mechanical design support system.

[Conventional technology]

Conventionally, the line of intersection between two polygons is found using the following procedure.

(2) Find the intersection between the sides of one polygon (hereinafter referred to as polygon A) and the plane (hereinafter referred to as plane B) that includes the other polygon (hereinafter referred to as polygon B).

■ From the positional relationship between the intersection obtained in ■ and the vertices of polygon B,
It is determined whether this intersection is included inside polygon B. Hereinafter, this determination process will be referred to as inside/outside determination process.

■ Perform processing ■ and ■ for all sides of polygon A,
Find all intersections contained within polygon B.

■ Perform the same processing as ■, ■, ■ between the sides of polygon B and the plane containing polygon A (referred to as plane A), and find all the intersections included inside polygon A. .

■ Among all the intersection points found in the above procedure, the line connecting two adjacent intersection points is defined as the intersection line.

[Problem that the invention seeks to solve]

In the conventional method, the process of ■ is performed after repeating the processes of ■ and ■ above many times, but the process of determining the inside/outside of ■ usually requires a large amount of calculation compared to the process of ■. This slows down the overall processing time.

SUMMARY OF THE INVENTION An object of the present invention is to provide a polygon quantity intersection line calculation method that solves the above-mentioned problems, reduces the amount of calculation required, and shortens processing time.

[Means for solving problems]

As shown in FIG. 1, the system of the present invention is comprised of the following five means.

■) For each of the two polygons, storage means 11° that holds the equation of the plane in which the polygon is included and the coordinate values of both end points of all sides 2) The equation of the plane in which the polygon is included and the coordinate values of both end points of all sides Polygon supply means 12゜ which takes out the coordinate values of from the storage means 11 and sends them to the intersection calculation means 3) Intersection calculation means 13゜ which calculates the intersection between a line segment in three-dimensional space and a plane 4) On a straight line in three-dimensional space Sorting means for sorting the intersection points existing in 2 of the intersection sequence of one of the regions and the other set
Intersection line determination means 15° for determining a region that is commonly included in any of the regions connecting the m-1th and 2mth intersection points.However, n does not exceed the number of points included in the former intersection sequence. m represents a natural number where 2m does not exceed the number of points included in the latter intersection sequence.

[Effect]

In the method of the present invention, the intersections between the sides and the plane, which are obtained in random order, are sorted according to their spatial positional relationship, and based on the order, the intersections included within any polygon are detected and the intersection lines are obtained. The specific processing procedure will be explained below.

■ Find the intersections of all sides of polygon A and plane B.

② The intersection found in ② exists on the − straight line (intersection line of plane A and plane B). The intersection points are sorted based on this linear adjacency relationship.

■ Sort the intersections of the sides of polygon B and plane A in the same way as in ■ and ■.

■ Among the sorting results of ■, 2n-1st and 2n
The line segment connecting the th intersection point is the intersection line between polygon A and plane B, and similarly, the line segment connecting the 2m-1th and 2mth intersection points is the intersection line between polygon A and plane A. Let be the intersection line of The common portion of these lines of intersection is defined as the line of intersection between polygon A and polygon B.

To carry out the above-described processing procedure, first, the storage means 11 stores the coordinate values of both end points of all sides of polygon A and polygon B and the equations of plane A and plane B.

The polygon supply means 12 first obtains the plane B from the storage means 11.
Next, the three-dimensional coordinate values of both end points of each side of the polygon A are sequentially extracted, and these data are sent to the intersection calculation means 13.

The intersection calculation means 13 determines whether the side intersects with the plane based on the equation data of the plane B and the coordinate values of both end points of each side of the polygon A, and if the side intersects with the plane, calculates the coordinate values of the intersection point and uses the sorting means Send on 14th.

When the above-mentioned processing is completed, the sorting means 14 sorts the coordinate values of the intersection points taken up to that time, and sends the results to the intersection line determination means 15.

Next, in the same manner as described above, the intersections between the sides of the polygon B and the plane A are determined, and the sorted results are sent to the intersection line determining means 15.

The intersection line determining means 15 selects one of the areas connecting the 2n-1st and 2nth intersections of the sorting results of the intersections of polygon A and plane B, and 2m- of the sorting results of the intersections of polygon B and plane A. A region that is commonly included in any of the regions connecting the 1st and 2mth intersection points is determined as the intersection line of polygon A and polygon B. However, n and :m are natural numbers as described above.

〔Example〕

An embodiment of the present invention will be explained using two polygons shown in FIG.

FIG. 2(a) shows a polygon a (21) and a polygon b (22) that intersect with each other.

The storage means 11 in FIG. 1 stores the coordinate values of both end points of all sides of polygon a (21) and polygon b (22), and the planes (plane a and plane b) containing each polygon a and b. Keep the equation. When the polygon supply means 12 extracts the data of the plane polygon a from the storage means 11 and sends it to the intersection point calculation means 13, the intersection point calculation means 13 finds the intersection point indicated by the mark . in FIG. 2(b). These intersection points are plane a and plane b (24
) exists on the intersection line 25. Next, sorting means 1
4 sorts the intersection points in Figure 2 (b) and then displays Figure 2 (C).
Order as follows.

Similarly, for polygon b (22) and plane a (23), find the intersection indicated by the circle in Fig. 2(d),
The order is as shown in FIG. 2(e). Finally, the intersection line determination means 15 detects the intersection points 1 and 2, 3 and 4, and 5 and 6 of the marks represented by the thick line at the top of FIG. 2(f). No. 1 and 2, No. 3 and No. 4, No. 5 and No. 6 of the intersections of the ○ marks, which are represented by the thick line between the area connecting the numbers and the middle line of Figure 2 Cf').
The common area of the areas connecting the numbers (the area represented by the thick bottom line in FIG. 2(f)) is determined. This is the intersection line of polygon a (21) and polygon b (22) to be found. However, although the three lines in FIG. 2(f) are drawn separately for the sake of explanation, they are the same straight line in space. The relationship between the obtained intersection line and polygon a (21) and polygon b (22) is shown in FIG. 2(g). In the figure, the intersection lines are indicated by thick lines.

〔Effect of the invention〕

According to the method of the present invention, although sorting of intersection points is required, inside/outside determination processing is not necessary.

The inside/outside determination process requires a large amount of calculation compared to the sorting of intersection points.Furthermore, in the conventional method, it is necessary to perform the inside/outside determination process for the number of intersections, whereas the method of the present invention only sorts the intersection points twice. Just go. Therefore, the method of the present invention reduces computational requirements.

[Brief explanation of the drawing]

FIG. 1 is a configuration diagram of the polygon quantity intersection line calculation method of the present invention, FIG. 2 is a diagram representing one embodiment of the present invention. 1 to 6...Order of intersections 11... Memory means 12...Polygon supply means 13... Intersection calculation means 14... Sorting means 15...Intersection line determination means 21...Polygon a 22...Polygon b 23...plane a 24...plane b 25...Intersection line of plane a and plane S Agent Patent Attorney Yoshiyuki Iwa

Claims (1)

[Claims] (1) For each of the two polygons, a storage means that stores the equation of the plane in which the polygon is included and the coordinate values of both end points of all sides; A polygon supply means that extracts coordinate values from the storage means and sends them to an intersection calculation means, and 3.3 from the equation and coordinate values sent from the polygon supply means.
Intersection calculation means for calculating the intersection between a line segment (side) in a dimensional space and a plane; and a sorting means for sorting and ordering the intersection points existing on a straight line in the three-dimensional space calculated by the intersection calculation means; Based on two sets of ordered intersection sequences existing on a line, 2n- corresponding to all natural numbers n in which 2n does not exceed the number of intersections included in the intersection sequence of one set
2m - 1st and 2m corresponding to all natural numbers m where 2m does not exceed the number of points included in the intersection sequence in either of the areas connecting the 1st and 2nth intersections and the other set of intersection sequences.
An inter-polygon intersection line calculation method comprising an intersection line determining means for determining a region commonly included in any of the regions connecting the th intersection point.