JP5407695B2 - Self-intersection detection program and self-intersection detection method in 3D curve model - Google Patents

Description

  The present invention relates to a self-intersection detection program and a self-intersection detection method in a three-dimensional curve model.

  When designing linear flexible objects such as wires, harnesses, cables, etc. incorporated in machinery products and equipment, the linear flexible objects obstruct the operation of the machine parts connected to the linear flexible objects. It is necessary to determine an appropriate length and wiring route of the linear flexible object so as not to interfere with other parts. For this reason, a software for modeling a three-dimensional curve is operated on a three-dimensional CAD system to create a three-dimensional curve model of a linear flexible object in the virtual space, and the movement of the linear flexible object in the virtual space. A method of simulating the above has been conventionally proposed.

  The software described above receives the input of conditions such as the start and end positions and connection direction of the linear flexible object to be designed, the length of the linear flexible object, the cross-sectional radius of the linear flexible object, etc. A three-dimensional curve that satisfies the following conditions and satisfies the laws of mechanics is automatically generated.

  However, the above-described software may generate a three-dimensional curve model having a shape including a self-intersection that is impossible in reality if the input condition is inappropriate or unnatural. Here, the self-intersection means that a part of the same curve and another part intersect at the same coordinate in the space. In other words, the software described above creates a shape that includes a closed loop due to self-intersection, although a linear flexible object can only take a spiral loop shape regardless of parameters. May end up. Since the three-dimensional curve model having the latter shape exhibits a shape that does not actually exist, it is not suitable for the purpose of simulating the movement of the linear flexible object. Therefore, it is required to detect self-intersection in the generated three-dimensional curve at high speed.

International Publication No. 2004/825522 JP-A-9-292873

  In order to detect a self-intersection in a three-dimensional curve, the three-dimensional curve is approximated to a broken line composed of a plurality of (N + 1) point sequences and N line segments each connecting each point, and all lines It is conceivable to check the presence or absence of intersections (that is, common coordinates) for all combinations of two line segments selected from the minutes. In this case, if the simultaneous equations indicating the two line segments in the coordinate system have solutions, it is determined that an intersection exists.

  However, according to this method, the number of calculations for determining whether or not there is an intersection for each set of line segments (hereinafter referred to as “intersection determination calculation”) is N × N at the maximum.

  In view of this, it is an object of the present invention to reduce the amount of calculation for detecting self-intersection in a three-dimensional curve model.

  According to the proposed means, the 3D curve model is projected onto a plurality of virtual planes facing different directions. Then, in each virtual plane, the self-intersection included in the projected curve is detected, and when the self-intersection included in the curve projected on all the virtual planes is detected, the self-intersection is detected in the 3D curve model. Judge that there is.

  The amount of calculation for detecting the self-intersection in the three-dimensional curve model can be reduced.

Block diagram showing the hardware configuration of the computer Flow chart showing 3D curve model generation program The flowchart which shows the self-intersection detection process subroutine of the curve performed in S003 of FIG. Flowchart showing a self-intersection detection subroutine for a curve on a plane executed in S102 of FIG. Flowchart showing a self-intersection detection subroutine for curved lines executed in S104 of FIG. Diagram showing an example of a 3D curve model Diagram showing a 3D curve approximated to a polyline A diagram representing the projection of a 3D curve onto two planes A graph showing the significance of the selected section in the X-axis direction A graph showing the significance of the selected section in the Y-axis direction Figure showing a modified 3D curve model example

Hereinafter, embodiments of the present plan will be described based on the drawings.
<Computer>
FIG. 1 is a hardware configuration diagram of a computer 1 in which a three-dimensional curve model generation program is installed.

  As shown in FIG. 1, the computer 1 is a general computer having a CPU 10, a RAM 11, an input device 12, a display 13, and a hard disk 15 connected to each other by a bus B.

  The CPU 10 is a processing device that reads a program from the hard disk 15 and executes processing according to the program.

  The RAM 11 is a main storage device that expands a work area when the CPU 10 performs the above processing.

  The input device 12 is a keyboard and a pointing device for inputting various commands or data to the CPU 10.

  The display 13 is a display device for displaying a processing result by the CPU 10.

  The hard disk 15 is a solid storage medium that stores various programs and various data. The various programs stored in the hard disk 15 include a three-dimensional CAD program including a three-dimensional curve model generation program 16 that is a module that implements a self-intersection detection program for a three-dimensional curve model.

The recording medium for storing the three-dimensional curve model generation program 16 is not limited to the hard disk 15, and a recording medium that can be read by a computer or other machine or device (hereinafter, a computer or the like) can be used. The function can be provided by causing a computer or the like to read and execute the program of the recording medium. Here, a computer-readable recording medium is a recording medium that stores information such as data and programs by electrical, magnetic, optical, mechanical, or chemical action and can be read from a computer or the like. Say. Examples of such a recording medium that can be removed from a computer or the like include a flexible disk, a magneto-optical disk, a CD-ROM, a CD-R / W, a DVD, a Blu-ray disk, a DAT, an 8 mm tape, a flash memory, and the like. There are cards. In addition, as a recording medium fixed to a computer or the like, there are a hard disk, a ROM (read only memory), and the like.
<3D curve model generation program>
The flowchart of FIG. 2 shows the process by the 3D curve model generation program 16 among the processes by the 3D CAD program. The flowcharts shown in FIGS. 2 to 5 are described as generating a three-dimensional model of a harness that is an example of a linear flexible object. Of course, can be generated.

  The process shown in FIG. 2 starts when the operator inputs a predetermined command to the CPU 10 executing the CAD program through the input device 12.

  In the first S001 after the start, the CPU 10 inputs a condition related to the harness shape. In FIG. 2, the harness start point and end point positions, the harness connection direction at the start point and the end point, the harness length, and the harness cross-sectional radius are illustrated as conditions regarding the harness shape. , A weight per unit volume may be input. The condition regarding the harness shape may be stored in the hard disk 15 in advance by the operator operating the input device 12, or written on the input screen displayed on the display 13 by the operator 10. It may be a thing.

  In next step S002, the CPU 10 calculates a three-dimensional model of a harness shape having a linear shape that satisfies the conditions input in S001.

  In the next step S003, the CPU 10 detects a self-intersection in the harness-shaped three-dimensional model generated in step S002. The CPU 10 converts the three-dimensional model calculated in S002 into a three-dimensional curve having no thickness as shown in FIG. 6, and uses the three-dimensional curve for the self-intersection detection process in S003.

FIG. 3 is a flowchart showing a self-intersection detection processing subroutine executed in S003. In the first step S101 after entering this subroutine, as shown in FIG. 7, the CPU 10 places a predetermined number (N + 1) of point sequences on the three-dimensional curve so as to equally divide the three-dimensional curve into N line segments. By generating (p _i = {Xi, Yi, Zi}: i = 0, 1, 2,..., N), the three-dimensional curve is approximated to a polygonal line. Note that the start point p ₀ and the end point p _N of the point sequence are generated on the start point and the end point of the three-dimensional curve, respectively.

In the next S102, the CPU 10 projects the point sequence (broken line) generated in S101 onto the first plane (corresponding to the projecting means), and then the polyline connecting the projected point sequence onto the first plane. Is executed to detect whether or not has a self-intersection (corresponding to the on-plane intersection detection means). The first plane and the second plane to be described later may be planes facing in any direction as long as they face in different directions. For example, the plane may include a start point p ₀ , an end point p _N and an arbitrary intermediate point p _k of the point sequence. However, in order to simplify the processing, in the following description, the first plane is a plane parallel to the XY plane and the second plane is a plane parallel to the YZ plane.

FIG. 4 is a flowchart showing a self-intersection detection processing subroutine for curved lines on the plane executed in S102. In the first step S201 after entering this subroutine, the CPU 10 converts the point sequence generated in step S101 into a sequence of points on the XY plane ( _pi = {Xi, Yi}: i = 0) as shown in FIG. , 1,2, ..., N). That is, the CPU 10 projects the point sequence (polygonal line) on the XY plane by deleting the value of the Z coordinate from the coordinate value of each point constituting the sequence.

In the next S202, the CPU 10 determines the value of the X coordinate of each point P _i constituting the point sequence (p _i = {Xi, Yi}: i = 0, 1, 2,..., N) converted in S101. By reading Xi in the order of the value of suffix i, the section of i in which the X coordinate value Xi in the point sequence is not monotonically increasing or monotonically decreasing is detected. Specifically, CPU 10, when the value X ₁ of the X-coordinate than the value X ₀ of X-coordinate at the starting point p ₀ of point sequences in the second point p ₁ is increasing, the previous The section of _i in which the point P _i where the X coordinate value X _i is smaller than the X coordinate value X _{i-1 at} the point P _i-1 is connected is detected. Further, CPU 10, when the value X ₁ of the X-coordinate than the value X ₀ of X-coordinate at the starting point p ₀ of point sequences in the second point p ₁ is decreasing, the previous point P the value X _i of the X-coordinate than the value X _i-1 of X coordinate detecting the interval of i continuing the P _i-1 that has increased in _i-1. For example, in the example shown in FIG. 9, the value X ₁ of the X-coordinate than the value X ₀ of X-coordinate at the starting point p ₀ of point sequences in the second point p ₁ is increased from the point P ₂ A section up to the point P ₆ is detected as a section of i that is not monotonically increasing.

  In the next S203, the CPU 10 checks whether or not a section that is not monotonically increasing or decreasing is detected in S202. If no section where the change is not monotonous is detected, the CPU 10 sets the return value to “no intersection” in S211, ends the subroutine, and returns the process to the routine of FIG.

  On the other hand, when a section that is not monotonically increasing or decreasing is detected in S202, the CPU 10 advances the process to S204.

In S204, CPU 10, among the values X _i of the X coordinates for a series of points p _i belonging to the detected non-monotonic segment in S202, obtains the minimum value X _min and a maximum value X _max. Then, the CPU 10 selects a section [i_xs, i_xe] of i surrounded by points adjacent to both outer sides of the region where the value X _{i of the} X coordinate is X _min or more and X _max or less. In the example of FIG. 9, the value X ₆ X coordinate of the point p ₆ is X _min, since the value X ₂ of X coordinates for the point p ₂ is X _{m ax,} it is X ₆ or X ₂ or less The section [1,7] of i surrounded by the points p ₁ and p _{7 that} are close to the outer sides of the region is selected.

In the next S205, the CPU 10 reads the value Yi of the Y coordinate of each point p _i belonging to the section [i_xs, i_xe] of i selected in S204 in the order of the value of the suffix i, so that the point sequence ( _{pi_xs˜} The interval of i in which the Y coordinate value Yi in p _{i_xe} ) is not monotonically increasing or decreasing is detected. Specifically, the CPU 10 detects a section of i that is not monotonically increasing or monotonically decreasing by the same method as in S202. For example, in the example shown in FIG. 10, since the interval [1, 7] of i from the point p ₁ to the point p ₇ has already been selected, the point p ₄ to the point p _{7 in the} interval [1, 7]. The section up to is detected as the section of i that is not monotonically increasing.

  In the next S206, the CPU 10 checks whether or not a section that is not monotonically increasing or decreasing is detected in S205. If a non-monotonic section is not detected, the CPU 10 sets the return value to “no intersection” in S211, ends the subroutine, and returns the process to the routine of FIG.

On the other hand, when an interval that is not monotonically increasing or decreasing is detected in S205, S206 is detected.
If it is determined in step S10, the CPU 10 advances the process to step S207. In other words, the CPU 10 goes through S202, S203, S205, and S206, so that if the point sequence on the projected broken line is sequentially traced, the change in values on the two coordinate axes set in each virtual plane is in the same section. The self-intersection can be detected only when each is not monotonous.

In S207, the CPU 10 obtains the minimum value Y _min and the maximum value Y _max among the Y coordinate values Y _i for the series of points p _i belonging to the non-monotonic section detected in S205. Then, CPU 10, among the sequence of points _(p i_xs ~p i_xe), Y-coordinate value Y _i of i surrounded by the points close to the both outer region is less than Y _min or Y _max interval [I_ys , i_ye]. FIG.
In this example, Y-coordinate value Y ₇ for the point p ₇ is Y _min, Y-coordinate value Y ₄ for the point p ₄ is from a Y _max, the section from the point p ₁ to point p ₇ Of these, there is no point close to both outer sides of the region that is y ₇ or more and y ₄ or less. Accordingly, the interval [1,7] surrounded by point p4 and the point p ₇ itself is selected.

In the next S208, the suffix i is the interval [i_ys, i_ye] for all combinations of two line segments selected from all line segments constituting a line connecting a series of points _p i_ys ~p i_ye belonging to cross (i.e., Attempt to calculate (common coordinates). That is, the CPU 10 tries to calculate a solution of simultaneous equations indicating two line segments in the XY coordinate system.

  In the next step S209, the CPU 10 performs self-intersection on the XY plane based on whether or not the solution (that is, the coordinates of the intersection) is calculated for any combination of line segments as a result of the calculation in step S208. Check if it exists. If it is determined that there is no self-intersection on the XY plane, the CPU 10 sets the return value to “no intersection” in S211, ends the subroutine, and returns the process to the routine of FIG.

  On the other hand, if it is determined in S209 that there is a self-intersection on the XY plane, the CPU 10 advances the process to S210. In other words, through S204 and S207, the CPU 10 selects two points each having a value on both outer sides of a section where the change in value is not monotonous on any one of the coordinate axes. And CPU10 calculates | requires the intersection of each line segment which exists between the said selected 2 points | pieces in the said broken line through S208 and S209, and is self-intersection only when the intersection can be calculated in any two line segments. Can be detected.

In S210, the CPU 10 ends the subroutine by using four points p _i dividing the two line segments for which “there is an intersection” and the solution is calculated, and returns the processing to FIG.

  In FIG. 3 in which the process is returned, the CPU 10 checks whether the return value from the process of S102 is “with intersection” or “without intersection” in S103 after S102. If the return value is “no intersection”, the CPU 10 sets the return value to “no intersection” in S108, ends the subroutine, and returns the process to the main routine of FIG.

On the other hand, if the return value is “with intersection”, the CPU 10 advances the process to S104. In S104, the CPU 10 projects the point sequence generated in S101 onto the second plane (YZ plane) (corresponding to the projecting means), and then connects the projected point sequence onto the second plane. A process of detecting whether the broken line has a self-intersection is executed (corresponding to a self-intersection detecting means on a plane). FIG. 5 is a flowchart showing the self-intersection detection subroutine for the curved line on the plane executed in S104. In the flowchart of FIG. 5, compared to the flowchart of FIG. 4, the plane on which the point sequence is projected is the YZ plane, and thus the coordinate values to be processed are the Y coordinate value and the Z coordinate value. It is different only in that. For example, in S301 in FIG. 5 corresponding to S201 in FIG. 4, the value of the X coordinate is deleted from the coordinate value of each point constituting the point sequence generated in S101, so that the point sequence ( _pi = { Xi, Yi, Zi}: i = 0,1,2, ..., N) is projected onto the YZ plane. In other respects, FIG. 5 is the same as FIG.

  In the next S105, the CPU 10 checks whether the return value from the process of S104 is “with intersection” or “without intersection”. If the return value is “no intersection”, the CPU 10 sets the return value to “no intersection” in S108, ends the subroutine, and returns the process to the main routine of FIG.

On the other hand, if the return value is “with intersection”, the CPU 10 advances the process to S106. In S106, the CPU 10 determines whether or not the four points p _i included in the return value in S102 (S210) match the four points p _i included in the return value in S104 (S310). That is, the CPU 10 determines, based on the determination result, the position of the intersection of the curve projected on the first plane (XY plane) and the intersection of the curve projected on the second plane (YZ plane). Check if the position is the same. If the positions of the intersections of the curves projected on both planes are not the same, the CPU 10 sets the return value to “no intersection” in S108, ends the subroutine, and proceeds to the main routine of FIG. return.

  On the other hand, if the positions of the intersections of the curves projected onto the two planes are the same, the CPU 10 sets the return value to “intersection” in S107, ends the subroutine, and performs the process of FIG. Return to the main routine. S103, S105, and S106 to S107 described above are determination means for determining that there is a self-intersection in the three-dimensional curve model when a self-intersection included in curves projected on all virtual planes is detected. Equivalent to.

  In the main routine to which the process is returned, the CPU 10 checks whether the return value from the process of S003 is “with intersection” or “without intersection” at S004 after S003. If the return value is “no intersection”, the CPU 10 ends the process by the three-dimensional curve model generation program 16.

On the other hand, if it is determined in S004 that the return value is “with intersection”, the CPU 10 advances the process to S005. In S005, the CPU 10 adjusts the condition input in S001 to calculate a harness-shaped three-dimensional model having a linear shape that satisfies the adjusted condition. After completion of S005, the CPU 10 ends the process by the three-dimensional curve model generation program 16.
<Action>
According to the present embodiment described above, the three-dimensional curve model of the harness is projected onto the first surface and the second surface, respectively, and the two-dimensional curve projected onto each surface has self-intersection. It is detected (S102, S104).

  In the detection of self-intersection with respect to the two-dimensional curve projected on each surface, if a non-monotonic section is detected on one coordinate axis (S202, S203), it approaches the outer sides of the non-monotonic section on the axis. A section delimited by points is selected (S204). As a result, the entire section that overlaps the non-monotonous section on one axis is selected.

  However, the selected section may form a loop or may simply meander.

Therefore, it is detected whether there is a non-monotonous section on the other axis for the selected section (S205, S206). This is because if there is a section that is not monotonous on the other axis, the case of simple meandering is eliminated. If a non-monotonous section is detected on the other axis, a section delimited by points adjacent to both sides of the non-monotonic section on the axis is further selected (S207).

  However, the above processing also leaves a possibility that the selected section is merely spiral. Therefore, as a precaution, the intersection is calculated for each line segment constituting the section (S208). In this case, unlike the conventional technique, the calculation is performed in two dimensions, so that the calculation is simplified and the section to be calculated is divided in advance, so that the calculation amount is greatly reduced. If the possibility of forming a spiral shape is low due to the characteristics of the program that generates the three-dimensional curve model, S207 to S208 can be omitted.

  As a result of the above processing, when a self-intersection is detected on only one surface, it is determined that the three-dimensional curve model is merely a spiral, and therefore it is finally determined that there is no intersection (S108). ).

  On the other hand, even if self-intersection is detected on both sides, if the positions where self-intersection is detected on each side (that is, intersecting line segments) are different, the three-dimensional curve is still used. It is determined that the model is merely a spiral (S106: No). Therefore, in this case, it is finally determined that there is no intersection (S108).

  On the other hand, when the self-intersection is detected on both surfaces and the position where the self-intersection is detected on each surface is the same, it is determined that the three-dimensional curve model draws a spiral (S106: Yes). ). Therefore, in that case, it is finally determined that there is an intersection (S108).

  As described above, according to the present embodiment, there is an advantage that the calculation amount of the intersection calculation is significantly reduced as compared with the conventional case.

1 computer 10 CPU
12 Input device 15 Hard disk 16 3D curve model generation program

Claims (5)

Computer
Projection means for projecting a three-dimensional curve model onto a plurality of virtual planes facing different directions,
Self-intersection detecting means on the plane for detecting self-intersection included in the projected curve in each virtual plane, and
When self-intersections included in curves projected on all virtual planes are detected by the self-intersection detection unit on the plane, and the positions where the self-intersections are detected in the respective virtual planes are the same A program for detecting a self-intersection in a three-dimensional curve model that functions as a determination unit that determines that the three-dimensional curve model has a self-intersection. The projecting means projects the three-dimensional model onto the plurality of virtual planes as a broken line composed of a plurality of linear segments separated by a plurality of point sequences,
The on-plane self-intersection detection means, in each virtual plane, if the point sequence on the projected polygonal line is traced in order, the change in values on the two coordinate axes set in each virtual plane is monotonous in the same section. 2. The self-intersection detection program for a three-dimensional curve model according to claim 1, wherein self-intersection can be detected in the projected curve when it is not. The on-plane self-intersection detection means, in each virtual plane, if the point sequence on the projected polygonal line is traced in order, the change in values on the two coordinate axes set in each virtual plane is monotonous in the same section. And two points having values close to both outer sides of a section where the change in value is not monotonous on any one of the coordinate axes, and exists between the selected two points in the broken line 3. The three-dimensional curve model according to claim 2, wherein the intersection between each line segment is obtained, and the self-intersection can be detected in the projected curve only when the intersection can be calculated in any two line segments. Self-intersection detection program. The self-intersection detecting means on the plane further specifies two line segments for which intersection points can be calculated,
The determination means is a case where a self-intersection included in a curve projected on all virtual planes is detected by the self-intersection detection means on the plane, and each virtual plane is detected by the self-intersection detection means on the plane. 4. The self-intersection in the three-dimensional curve model according to claim 3, wherein it is determined that the three-dimensional curve model has a self-intersection only when two line segments for which the specified intersection point can be calculated match. Detection program. The computer projects the 3D curve model onto a plurality of virtual planes facing different directions,
In each of the virtual planes, self-intersections included in the projected curves are detected, respectively.
When self-intersections included in curves projected on all virtual planes are detected and the positions where self-intersections are detected in the respective virtual planes are the same, the self-intersection is added to the three-dimensional curve model. A method for detecting self-intersection in a three-dimensional curve model, characterized by determining that there is an intersection.

Images