Search

CN-121997571-A - Curve intersection point determining method, equipment and storage medium executed by electronic equipment

CN121997571ACN 121997571 ACN121997571 ACN 121997571ACN-121997571-A

Abstract

The present disclosure provides a curve intersection point determining method, device and storage medium executed by an electronic device, the method including constructing, by an operator, a first root node and a second root node according to respective curve parameter information of the first curve and the second curve in response to a control instruction generated by a controller; the method comprises the steps of obtaining an initial detection result by detecting initial intersection of a first curve and a second curve according to a first root node and a second root node through an arithmetic unit, obtaining an intersection detection result by detecting intersection existence of the first curve and the second curve through the arithmetic unit based on a first endpoint of the first curve and a second endpoint of the second curve, and obtaining at least one intersection by displaying at least one intersection through a display unit.

Inventors

  • CHENG JINSAN

Assignees

  • 中国科学院数学与系统科学研究院

Dates

Publication Date
20260508
Application Date
20251231

Claims (10)

  1. 1. A curve intersection point determination method performed by an electronic device, comprising: Responding to a control instruction generated by a controller, respectively constructing a first root node and a second root node according to respective curve parameter information of a first curve and a second curve by an arithmetic unit, and storing the first root node and the second root node in a register, wherein the curve parameter information comprises control point information, node vector information, a curve first endpoint and a curve second endpoint, the first root node represents a bounding box which surrounds the first curve, and the second root node represents a bounding box which surrounds the second curve; Detecting initial intersection of the first curve and the second curve according to the first root node and the second root node by the arithmetic unit to obtain an initial detection result, and storing the initial detection result in the register, wherein the initial detection result represents the intersection possibility of the first curve and the second curve; Under the condition that the initial detection result represents that the first curve and the second curve possibly intersect, detecting the existence of an intersection point of the first curve and the second curve based on the first endpoint of the curve and the second endpoint of the curve of the first curve and the second curve respectively by the arithmetic unit to obtain an intersection point detection result; When the intersection point detection result represents that an intersection point exists between the first curve and the second curve, executing intersection point solving operation on the first curve and the second curve based on the first root node and the second root node by the arithmetic unit according to the curve parameter information of the first curve and the second curve respectively to obtain at least one intersection point, and storing at least one intersection point in the register; at least one of the intersections is displayed by a display unit.
  2. 2. The method of claim 1, wherein constructing the first root node and the second root node from the respective curve parameter information of the first curve and the second curve comprises: According to the control point information and the node vector information of the first curve and the second curve, respectively determining the effective ranges of the parameter domains of the first curve and the second curve; And respectively constructing the first root node and the second root node according to the respective parameter domain effective ranges of the first curve and the second curve.
  3. 3. The method of claim 1, wherein the performing initial intersection detection on the first curve and the second curve according to the first root node and the second root node, and obtaining an initial detection result includes: determining a root node pair according to the first root node and the second root node; And detecting the initial intersection of the root node pair based on a separation axis theorem to obtain the initial detection result.
  4. 4. The method of claim 1, wherein the detecting the presence of the intersection of the first curve and the second curve based on the first end point of the curve and the second end point of the curve, respectively, comprises: Connecting the curve first end point and the curve second end point of the first curve to obtain a first target line segment, and projecting a point on the first curve onto the first target line segment to obtain a first projection line segment; connecting the curve first end point and the curve second end point of the second curve to obtain a second target line segment, and projecting points on the second curve to the second target line segment to obtain a second projection line segment; Determining the parameter monotonicity of each of the first projection line segment and the second projection line segment; constructing a first curve support band of the first curve based on the first target line segment; constructing a second curve support band of the second curve based on the second target line segment; Determining a first positional relationship between the curve first end point and the curve second end point of the first curve and the second curve support belt, respectively; determining a second positional relationship between the curve first end point and the curve second end point of the second curve and the first curve support belt, respectively; And determining the intersection detection result according to the first position relation of the first end point of the first curve and the second end point of the curve and the second position relation of the first end point of the second curve and the second end point of the curve based on the intersection existence condition and according to the monotonicity of the parameters of the first projection line segment and the second projection line segment.
  5. 5. The method of claim 1, wherein the curve parameter information further includes a subdivision level, and wherein, in a case where the intersection detection result indicates that an intersection exists between the first curve and the second curve, performing an intersection solving operation on the first curve and the second curve based on the first root node and the second root node according to the curve parameter information of each of the first curve and the second curve, to obtain at least one intersection includes: determining the number of intersections between the first curve and the second curve based on the tangential cones of the first curve and the second curve respectively; Under the condition that the number of the intersection points is equal to 1, based on Newton iteration method, according to the curve parameter information of each of the first curve and the second curve, performing a first intersection point solving operation on the first curve and the second curve to obtain the intersection points; And under the condition that the number of the intersection points is greater than or equal to 2, based on the subdivision layers of the first curved surface and the second curved surface, according to the curve parameter information of the first curved surface and the second curved surface, iteratively executing a second intersection point solving operation on the first curved surface and the second curved surface based on the first root node and the second root node until an ending condition is met, and obtaining at least one intersection point.
  6. 6. The method of claim 5, wherein, in the case where the number of intersection points is equal to or greater than 2, based on the number of subdivision layers of each of the first curved surface and the second curved surface, iteratively performing a second intersection point solving operation on the first curved surface and the second curved surface based on the first root node and the second root node according to the curve parameter information of each of the first curved surface and the second curved surface until an end condition is satisfied, the obtaining at least one intersection point includes: The first root node and the first curve are subdivided through the arithmetic unit to obtain a plurality of first leaf nodes and a plurality of first sub-curves corresponding to the plurality of first leaf nodes one by one, and the second root node and the second curve are subdivided through the arithmetic unit to obtain a plurality of second sub-curves corresponding to the plurality of second leaf nodes one by one, wherein the first leaf nodes represent bounding boxes which enclose the first sub-curves, and sub-curve parameter information of the first sub-curves and the second sub-curves comprises subdivision layers, control point information, node vector information, curve first endpoints and curve second endpoints; in the case that the number of subdivision layers of the first sub-curve and the second sub-curve does not reach a preset maximum number of subdivision layers, iteratively executing, by the operator, the following steps for the first sub-curve and the second sub-curve until the number of subdivision layers of the first sub-curve and the second sub-curve reaches the preset maximum number of subdivision layers: Determining a plurality of i-layer candidate leaf node pairs based on the number of subdivision layers of each of the plurality of first sub-curves and the plurality of second sub-curves; each ith layer candidate leaf node pair comprises an ith layer first leaf node and an ith layer second candidate leaf node with the same subdivision layer number, wherein the ith layer first candidate leaf node corresponds to an ith layer first sub-curve, and the ith layer second candidate leaf node corresponds to an ith layer second sub-curve; For each ith layer candidate leaf node pair, carrying out initial intersection detection on the ith layer first sub-curve and the ith layer second sub-curve according to the ith layer first candidate leaf node and the ith layer second candidate leaf node to obtain an ith layer initial sub-detection result, wherein the ith layer initial sub-detection result represents the intersection possibility of the ith layer first sub-curve and the ith layer second sub-curve; Screening a plurality of ith layer target leaf node pairs meeting an intersection point solving condition according to the respective ith layer initial sub-detection results of the plurality of ith layer candidate leaf node pairs, and storing a plurality of ith layer first target leaf nodes, an ith layer second target leaf node, an ith layer first sub-curve and an ith layer second sub-curve which are respectively corresponding to the ith layer target leaf node pairs and each ith layer target leaf node pair in the register, wherein each ith layer target leaf node pair comprises the ith layer first target leaf node and the ith layer second target leaf node, each ith layer first target leaf node corresponds to the ith layer first sub-curve, and each ith layer second target leaf node corresponds to the ith layer second sub-curve; For each ith layer target leaf node pair, detecting the existence of an intersection point of the ith layer first sub-curve and the ith layer second sub-curve based on the curve first end point and the curve second end point of each of the ith layer first sub-curve and the ith layer second sub-curve to obtain an ith layer intersection point sub-detection result, wherein the ith layer intersection point sub-detection result represents the existence of an intersection point between the ith layer first sub-curve and the ith layer second sub-curve; For each ith layer target leaf node pair, determining the number of intersection points between the ith layer first sub-curve and the ith layer second sub-curve based on respective tangent cones of the ith layer first sub-curve and the ith layer second sub-curve under the condition that the ith layer intersection point sub-detection result represents that an intersection point exists between the ith layer first sub-curve and the ith layer second sub-curve; Under the condition that the number of the intersection points is equal to 1, based on Newton iteration method, according to the respective sub-curve parameter information of the first sub-curve of the ith layer and the second sub-curve of the ith layer, executing a first intersection point solving operation on the first sub-curve of the ith layer and the second sub-curve of the ith layer to obtain the intersection points; And under the condition that the number of the intersection points is greater than or equal to 2, subdividing the first target leaf node of the ith layer and the corresponding first sub-curve of the ith layer to obtain a plurality of first leaf nodes of the ith layer and a plurality of first sub-curves of the ith layer+1 layer, which are in one-to-one correspondence with the first leaf nodes of the ith layer, and subdividing the second target leaf node of the ith layer and the corresponding second sub-curve of the ith layer to obtain a plurality of second leaf nodes of the ith layer+1 layer and a plurality of second sub-curves of the ith layer+1 layer, which are in one-to-one correspondence with the second leaf nodes of the ith layer+1.
  7. 7. The method of claim 6, wherein, in the case where the number of intersections is greater than or equal to 2, based on the number of subdivision layers of the first curved surface and the second curved surface, according to the curve parameter information of the first curved surface and the second curved surface, performing a second intersection solving operation on the first curved surface and the second curved surface iteratively based on the first root node and the second root node until an end condition is satisfied, obtaining at least one intersection further includes, for an nth layer target leaf node pair in which the number of subdivision layers reaches the preset maximum number of subdivision layers: Under the condition that the number of the intersection points between the first layer sub-curve and the second layer sub-curve is more than or equal to 2, determining singular situations of the intersection points between the first layer sub-curve and the second layer sub-curve based on the sub-curve parameter information of the first layer sub-curve and the second layer sub-curve; under the condition that the singular situation is tangential point crossing, executing first singular solving operation on the first sub-curve of the nth layer and the second sub-curve of the nth layer according to the respective sub-curve parameter information of the first sub-curve of the nth layer and the second sub-curve of the nth layer to obtain at least one intersecting point; And under the condition that the singular condition is at least one of a sharp point, an selfing point and an endpoint intersection point, executing second singular solving operation on the first sub-curve of the nth layer and the second sub-curve of the nth layer according to the sub-curve parameter information of each of the first sub-curve of the nth layer and the second sub-curve of the nth layer, so as to obtain at least one intersection point.
  8. 8. The method according to any one of claims 1-7, wherein the method is applied in at least one of engineering, architectural, computer animation, face recognition, engineering simulation and path planning fields, the first and second curves characterizing the cartographic design of the first and second geometries, respectively.
  9. 9. An electronic device, comprising: One or more processors; a memory for storing one or more computer programs, Characterized in that the one or more processors execute the one or more computer programs to implement the steps of the method according to any one of claims 1-8.
  10. 10. A computer-readable storage medium, on which a computer program or instructions is stored, which, when executed by a processor, carries out the steps of the method according to any one of claims 1-8.

Description

Curve intersection point determining method, equipment and storage medium executed by electronic equipment Technical Field The present disclosure relates to the field of computer graphics, computer curve intersection techniques, and more particularly, to a curve intersection determination method, apparatus, and storage medium executed by an electronic device. Background With the rapid development of computer aided design, computer graphics, robot path planning, medical imaging, geographic information systems (Geographic Information System, GIS) and other technologies, two-dimensional spline curve intersection gradually becomes a key technology for fine design and accurate calculation. In many practical applications, the representation of complex shapes and boundaries often requires the use of continuous, smooth curves, whereas spline curves are widely used criteria due to their flexible surface expression capabilities. However, in geometric computation, especially in the scene of interaction of polygons and multiple curved surfaces, there are many challenges to accurately solving the intersections of spline curves, and these intersections have important significance for accurate construction of models, determination of geometric relationships, and visualization of data. Calculating the intersection point of a parametric curve and a curved surface is a fundamental challenge in the fields of CAGD (Computer Aided Geometric Design, computer aided geometry design) and geometry modeling, wherein the solution of the intersection point between parametric curves is not only a key link of the problem, but also an important premise for realizing high-precision geometry calculation and complex shape analysis. The accuracy and efficiency of the process directly influence the subsequent geometric modeling, shape optimization and the overall performance of engineering application, so that the method has remarkable research value in both theory and application level. In the spline curve, a Bezier curve defined by a Bernstein base function and control points is used as a base curve representation method by parameterization conciseness and geometric intuitiveness. The B spline curve is used as a generalized form of Bezier, strengthens local support through node vectors and a segmented polynomial structure, has global smoothness and flexible shape regulation and control capability, and is widely applied to geometric modeling, animation and interpolation calculation. NURBS (Non-Uniform Rational B-Splines, non-uniform rational B-spline) further expands B-spline to rational domain, realizes fine adjustment of curve shape by introducing control point weight parameters, and has the capability of accurately describing conical curve and complex free-form surface, thus becoming a standard geometric expression tool of CAD (Computer AIDED DESIGN)/CAGD and engineering design. In the process of realizing the conception of the present disclosure, the inventor finds that the related method has the problems of low calculation efficiency, unstable numerical value, failure to authenticate the intersection point and the like in the process of processing the NURBS curve intersection point calculation, and wastes calculation resources. Disclosure of Invention In view of this, the present disclosure provides a curve intersection point determining method, apparatus, device, medium, and program product that are executed by an electronic device. The first aspect of the disclosure provides a curve intersection point determining method executed by an electronic device, which comprises the steps of responding to a control instruction generated by a controller, respectively constructing a first root node and a second root node according to respective curve parameter information of a first curve and a second curve through an operator, and storing the first root node and the second root node in a register, wherein the curve parameter information comprises control point information, node vector information, a first end point of a curve and a second end point of the curve, the first root node represents a bounding box which surrounds the first curve, the second root node represents a bounding box which surrounds the second curve, performing initial intersection detection on the first curve and the second curve according to the first root node and the second root node through the operator to obtain initial detection results, and storing the initial detection results in the register, wherein the initial detection results represent intersection possibility of the first curve and the second curve, under the condition that the initial detection results represent the first curve and the second curve possibly intersect, performing intersection point detection on the first end point and the second end point based on the first curve and the second curve respectively, performing intersection point detection on the first curve and the second curve, performing intersec