CN118569003B - A universal parametric curve or surface self-intersection calculation method, device and storage medium - Google Patents
A universal parametric curve or surface self-intersection calculation method, device and storage medium Download PDFInfo
- Publication number
- CN118569003B CN118569003B CN202411054668.4A CN202411054668A CN118569003B CN 118569003 B CN118569003 B CN 118569003B CN 202411054668 A CN202411054668 A CN 202411054668A CN 118569003 B CN118569003 B CN 118569003B
- Authority
- CN
- China
- Prior art keywords
- intersection
- bvh
- curve
- self
- node
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F30/00—Computer-aided design [CAD]
- G06F30/20—Design optimisation, verification or simulation
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Data Mining & Analysis (AREA)
- General Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Computational Mathematics (AREA)
- Pure & Applied Mathematics (AREA)
- Databases & Information Systems (AREA)
- Mathematical Optimization (AREA)
- Mathematical Analysis (AREA)
- Algebra (AREA)
- Computer Hardware Design (AREA)
- Evolutionary Computation (AREA)
- Geometry (AREA)
- Image Generation (AREA)
Abstract
本发明公开了一种通用的参数曲线或曲面自交计算方法、设备及存储介质，包括：通过间隔重叠的划分方法对参数曲线或参数曲面的参数域进行划分、构建BVH并实现对参数曲线或参数曲面的细分，从而将整个参数曲线或曲面划分为若干子线段或子面片，然后采用特定方法快速遍历BVH进行自交的检测以寻找相交盒子对，之后对于相交盒子对进行拓扑重建，最后采用追踪的方法计算自交点和自交线。本发明的方法可有效处理各种复杂度和形式的参数曲线或曲面，具有广泛适用性、高效性和充分的鲁棒性。
The present invention discloses a general parametric curve or surface self-intersection calculation method, device and storage medium, including: dividing the parameter domain of the parametric curve or parametric surface by an interval overlapping division method, constructing a BVH and realizing the subdivision of the parametric curve or parametric surface, thereby dividing the entire parametric curve or surface into a plurality of sub-segments or sub-faces, and then using a specific method to quickly traverse the BVH to detect self-intersections to find intersecting box pairs, then topologically reconstructing the intersecting box pairs, and finally using a tracking method to calculate self-intersection points and self-intersection lines. The method of the present invention can effectively process parametric curves or surfaces of various complexities and forms, and has wide applicability, high efficiency and sufficient robustness.
Description
Technical Field
The invention belongs to the field of computer aided design and manufacture, and relates to a general parameter curve or curved surface selfing calculation method, equipment and a storage medium.
Background
Computer-aided design and Manufacturing (CAD/CAM) has an extremely important role in the field of modern engineering, construction and Manufacturing. It enables engineers, designers, and creative personnel to design and develop in a faster, more accurate, and more flexible manner by providing a digitized design environment. The use of CAD/CAM is not limited to the traditional mechanical design field, and plays a key role in the fields of construction, electronics, aerospace, automobiles, medical treatment and the like, and becomes an indispensable core technology for modern engineering design.
The CAD kernel is a software component for implementing the core functions of CAD software. The CAD kernel provides a series of algorithms and data structures for processing geometries, implementing geometric transformations, performing collision detection, performing boolean operations (e.g., union, intersection, difference), and the like. CAD kernels are typically object-oriented, having a variety of kinds and methods that can be used in a programming environment. CAD software developers can build their applications with CAD kernels, thereby speeding up the development process and providing high-performance design and analysis functions.
In CAD kernels, handling curves and surface selfing is an important issue because it can lead to unexpected behavior, especially when boolean operations, cuts, or other geometric operations are performed. When a curve or surface has selfing in two or three dimensions, it may lead to challenges and problems that unique parameters cannot be defined, that a point on the curve or surface may have multiple parameter values corresponding to it, which makes accurate positioning on the curve or surface difficult, and that geometric operation problems, that curve or surface selfing may lead to erroneous results when performing geometric operations (such as intersection detection, boolean operations, etc.), because the intersection point may be repeatedly calculated or mistaken for two different points.
In CAD kernels, boolean operations support building complex solid models from simple primitives. In order to transform a solid model into its boundary representation, intersection algorithms need to be used to handle the intersection of free-form surfaces. In existing intersection algorithms, it is generally assumed that the input surface is free of self-intersection. However, in some cases, such as when the surface is an offset surface or a scan surface, we need to consider the possibility of the input surface self-intersecting.
Numerical control tool path generation is a widely used technique in computer aided design and manufacturing (CAD/CAM). It is used to generate a path for controlling the numerically controlled machine tool to perform cutting operations in order to translate the designed geometry into the tool path required in the actual manufacturing process. Generating the cutting path by means of an offset curved surface is an efficient way, for example generating a tool path along an equidistant profile of the offset curved surface. In the offset curved surface generating process, sometimes, a self-intersecting condition occurs, which causes problems in the numerical control tool path generating process, for example, accidental collision of tools in the machining process can be caused, the machining quality is affected, and even a workpiece or the tools are damaged. Therefore, the detection and elimination of self-intersections in offset surfaces has long been an important issue in numerical control tool path generation applications.
Based on the method, the invention provides a general parameter curve and curved surface selfing calculation method, and the method can effectively detect the parameter curve or the parameter curved surface selfing.
The parameter curves can be formally described as:
Wherein, Indicating the position on the parameter curve,、AndThe coordinates on the curve are represented as such,Representing the parameter values. Equation (1) represents a slave parameter valueTo coordinate points in space (three-dimensional parametric curve)Or coordinate points on a plane (two-dimensional parametric curve)Is mapped to the mapping of (a). On this basis, the curve selfing problem can be described as:
Wherein the method comprises the steps of Indicating the presence of two different parameter values on the curveAndMapping to the same locationAll positions of (3)Is a set of (3). In general terms, the process is carried out,Is a collection of series of self-intersections.
The parametric surface can be formally described as:
Wherein, Representing the location on the parametric surface,、AndRepresenting the coordinates on the curved surface,AndRepresenting the parameter values. Equation (3) represents a slave parameter pointTo coordinate points in spaceIs mapped to the mapping of (a).
On this basis, the curved surface selfing problem can be described as:
Wherein the method comprises the steps of Indicating the presence of two distinct parameter points on a surfaceAndMapping to the same locationAll surface positions of (a)Is a set of (3). In general terms, the process is carried out,Is a set of a series of selfing curves and selfing points. It should be noted that the algorithm used in the present invention can be applied to arbitrary parametric curves and surfaces, and only the parametric curves or surfaces are required to calculate the parameters from given pointsTo space coordinatesIs mapped to the mapping of (a).
Disclosure of Invention
The invention aims to provide a general parameter curve and curved surface selfing calculation method aiming at the defects of the prior art, and the method is mainly based on the subdivision idea, divides the whole curve or curved surface into sub-line segments or sub-surface pieces, and converts the self-intersecting problem into the intersecting problem of non-adjacent sub-line segments or sub-surface pieces on the same curve or curved surface. In order to accelerate the intersection judgment of the sub-line segments and the sub-patches and avoid the algorithm efficiency problem caused by violent search, the invention uses a BVH structure to accelerate the intersection judgment. Conventional BVH is typically built by dichotomy, but this construction assumes that the input curve or surface is not self-intersecting, and its partitions are typically non-overlapping, which can result in the algorithm being unable to determine the self-intersection at the partition boundaries. On the basis, the invention provides a tracking-based method for realizing the calculation of a final self-intersecting line.
The technical scheme adopted by the invention is as follows:
A general parameter curve or curved surface selfing calculation method comprises the steps of dividing parameter fields of a parameter curve or a parameter curved surface by a dividing method of interval overlapping, constructing BVH and realizing subdivision of the parameter curve or the parameter curved surface, so that the whole parameter curve or the curved surface is divided into a plurality of sub-line segments or sub-patches, then the BVH is rapidly traversed by a specific method to carry out selfing detection to find intersecting box pairs, then topology reconstruction is carried out on the intersecting box pairs, and finally a tracking method is adopted to calculate self-intersecting points and self-intersecting lines.
The bounding box hierarchical structure (BVH) adopted by the invention uses an Axis Alignment Bounding Box (AABB), and each BVH node stores information such as a parameter domain, explicit storage of the size of the parameter domain, leaf node marks and the like besides the bounding box. BVH adopts a three-tree structure, and each BVH node has three pointers to child nodes. In the curve selfing, the parameter domain is one-dimensional and comprises the minimum value and the maximum value of the parameter domain, and in the curve selfing, the parameter domain is two-dimensional and comprisesAndMinimum and maximum values in the direction. In addition, the invention adopts a key value mapping table as a data structure of a division mode, and records the corresponding relation of the length of the parameter domain before and after division.
On the basis, the invention provides a construction process of curve selfing and curve selfing BVH, which mainly comprises three parts, namely an initialization process, a leaf node judgment process, a BVH tree construction process and a BVH tree construction process, wherein the initialization process is used for initializing BVH nodes according to the length or the size of a parameter domain, allocating memory for the BVH nodes, the leaf node judgment process is used for checking whether the nodes are leaf nodes or not and setting leaf node marks according to the length or the size of the parameter domain, the BVH tree construction process is used for recursively constructing the BVH tree, obtaining the domain length of the sub nodes according to a partition table, calling the initialization process to initialize the sub nodes, calculating the parameter domain according to the domain length of the sub nodes, calling the leaf node judgment process to judge whether the current node is the leaf node, and then recursively calling and constructing the BVH process for the three sub nodes of the current node.
On the basis of completing BVH structure construction, calculation of a leaf node bounding box is realized by sampling on a curve or a curved surface, the process is that the step length of sampling is calculated on the curved surface according to the input sampling times, the step length is sampled every time the curve or the curved surface is walked from the minimum parameter value, point coordinates of the curve at corresponding parameters are calculated, and then parameters of the bounding box are updated according to the coordinates of the points. The construction process of the BVH bounding box from bottom to top adopts a recursive manner. Recursion will start from the root node of BVH, first recursively construct bounding boxes of children nodes until the children nodes are leaf nodes, then merge the bounding boxes of all children nodes together as the bounding box of the node.
On the basis of the completion of BVH bounding box construction, the region where the self-intersection exists is found by traversing the BVH. The traversal process comprises the steps of checking the validity of BVH nodes, judging whether AABB bounding boxes intersect or not, recursively performing intersection traversal and the like. The traversal is to start from the root node of BVH, firstly recursively perform self-intersecting traversal on three child nodes of the current node, then judge the overlapping condition of bounding boxes of the three child nodes, namely, perform intersecting traversal on two child nodes overlapped by the bounding boxes, and perform pruning of BVH tree on two child nodes not overlapped by the bounding boxes without any processing. In the intersecting traversal, three children of the larger parameter domain node and another node are used each time for recursive intersecting traversal until both nodes are leaf nodes. If the bounding boxes of two leaf nodes overlap, this indicates that a pair of intersecting box pairs is found.
Topology reconstruction will be performed on the basis of finding intersecting box pairs of leaf nodes. The method aims to connect all adjacent curve segments and curved surface pieces to form a large curve and curved surface, so that the step length can be correctly calculated when the self-intersection point and the self-intersection curve are solved by using a travelling method in the follow-up process.
And finally, solving the selfing problem through a curve and surface intersection algorithm, wherein the method comprises the steps of finding a starting point by utilizing a Newton iteration method and calculating points on a series of intersection lines by adopting a tracking method. Finally, fitting all the result points into a B spline curve. The whole process mainly depends on BVH technology and a numerical calculation method to solve the problem of selfing of curves and curved surfaces.
Compared with the prior art, the invention has the beneficial effects that:
(1) The curve or curved surface selfing calculation method provided by the invention has wide applicability. The method is suitable for processing parameter curves or curved surfaces of various complexity and forms, including but not limited to polynomial curves, bezier curves, NURBS curves and various curved surface models.
(2) The curve or curved surface selfing calculation method provided by the invention has remarkable high efficiency. According to the method, through ingenious modification of BVH, the problem of self-intersection of the curve or the curved surface can be solved by using a mature curve or curved surface intersection algorithm, so that the self-intersection algorithm can achieve almost the same calculation efficiency as the existing curve or curved surface intersection algorithm.
(3) The curve or curved surface selfing calculation method provided by the invention has sufficient robustness, and can stably process complex situations such as multiple selfing points and selfing curves, similar selfing points and selfing curves, annular selfing curves and the like.
Drawings
FIG. 1 is a schematic diagram of curve and surface division by dichotomy;
FIG. 2 is a simplified solution schematic of solving the common boundary brought by dichotomy;
FIG. 3 is a schematic diagram of the curve and the curve division used in practice of the present invention;
Fig. 4 is a process diagram of the selfing curve construction BVH;
fig. 5 is a process diagram of the selfing surface configuration BVH;
fig. 6 is a process diagram of BVH traversal of an selfing curve;
fig. 7 is a process diagram of BVH traversal of a selfing surface;
FIG. 8 is a schematic diagram of tasks performed by topology reconstruction;
FIG. 9 is a schematic view of a curved surface segment intersecting a plurality of non-adjacent curved surface segments;
FIG. 10 is a schematic illustration of a curved surface self-intersecting to form a self-intersecting curve;
FIG. 11 is a schematic illustration of a curved surface self-intersecting to form a closed self-intersecting curve;
FIG. 12 is a schematic illustration of a curved surface self-intersecting to form two closely spaced self-intersecting curves;
FIG. 13 is a schematic illustration of a curved surface self-intersecting to form two long-distance short self-intersecting curves;
FIG. 14 is a schematic illustration of a curve self-intersecting to form a self-intersection;
FIG. 15 is a schematic illustration of a curve self-intersecting to form a plurality of self-intersecting points;
FIG. 16 is a schematic illustration of a curve self-intersecting to form two close-range self-intersections;
FIG. 17 is a schematic illustration of a polyline self-intersecting, forming a self-intersection of three parameters mapped to the same point;
FIG. 18 is a flow chart comparing selfing calculation and intersection calculation;
Detailed Description
The invention provides a calculation method for curve and curve selfing, which is characterized in that five parts of algorithm basic principle, BVH construction, BVH traversal, topology reconstruction and self-intersection point and self-intersection line calculation are used for describing the scheme in detail, wherein the first four parts complete the problem transformation from curve selfing calculation to curve intersection calculation, and the method is also the key point of the invention. The contribution of the invention can be summarized as:
(1) Aiming at the problem of curve and curved surface self-intersection, the invention provides a general curve and curved surface self-intersection solving framework, the parameter domains of the parameter curves and the curved surfaces are divided by a special dividing method, the dividing method is applied to BVH to realize subdivision of the curves and the curved surfaces, then the BVH is traversed by the special method to carry out self-intersection detection to find an intersecting box pair, after that, topology reconstruction is carried out on the intersecting box pair, and finally, the self-intersection point and the self-intersection line are calculated by adopting a tracking method. Therefore, the detection of the self-intersection of the curve and the curved surface and the rapid calculation of the self-intersection point and the self-intersection curve are realized.
(2) Aiming at the parameter domain dividing method of the parameter curve and the curved surface, the invention provides a dividing mode of 'interval overlapping', which adds an intermediate interval area on the basis of a dichotomy and additionally adds an area to be partially overlapped with other areas. Therefore, the problem of selfing detection of the dichotomy on adjacent boundaries is solved, and the performance consumption caused by parameter domain division is reduced.
(3) Aiming at the 'interval overlapping' dividing method, the invention provides a storage mode of the dividing method and respectively applies the dividing method to a data structure and a construction process of the curve selfing BVH and the curve selfing BVH. The three-fork tree is built, the parameter domain division and the BVH structure building are completed from top to bottom in each node storage parameter domain of the tree, then the bounding box of each leaf node is calculated, and finally the bounding box of each non-leaf node is calculated from bottom to top. Thus, the construction of BVH and the subdivision of parameter curves and curved surfaces are completed rapidly.
(4) Aiming at the BVH structure based on the interval overlapping dividing method, the invention provides a self-intersecting BVH traversing algorithm. The self-crossing and crossing conditions of the three child nodes are checked by recursively performing self-crossing traversal on the three child nodes of each non-leaf node and performing crossing traversal on the three child nodes. For each pair of leaf nodes, checking whether the bounding boxes of the leaf nodes have intersection or not, and recording all parameter domains and bounding boxes with the intersected leaf nodes. Thus, the rapid BVH traversal and the search of the intersecting box pairs are realized.
(5) Aiming at all intersection box pairs, the invention provides a topology reconstruction algorithm. The parameter domains of all intersecting box pairs are constructed into a graph, all adjacent parameter domains are connected together through a breadth-first traversal algorithm, and then a complete parameter domain is constructed according to connection information, so that the correct selection of step sizes in the subsequent intersecting line calculation by adopting a tracking method is realized.
(6) Aiming at the calculation of the self-intersection point and the self-intersection line, the invention uses Newton iteration method to find the starting point of the tracking method in the curved surface intersection and the intersection point in the curved surface intersection, and adopts the tracking method to calculate the intersection line in the curved surface intersection. The self-intersecting problem of the curve or the curved surface is calculated by using the curve or the curved surface intersection algorithm by replacing the BVH construction and the traversal process in the curve or the curved surface intersection algorithm with the self-intersecting BVH construction and the traversal process in the steps (2) to (4). The technical scheme of the invention is further described in detail below by referring to the accompanying drawings and specific examples, wherein the content is 1-5 in five sections:
1. basic principle of algorithm
The main idea of the curve and surface selfing algorithm is that based on the subdivision idea, the whole curve or surface is divided into a plurality of sub-line segments or sub-patches, and then the self-intersecting problem of the curve and the surface is converted into the intersecting problem of two non-adjacent sub-line segments or sub-patches on the same curve or surface, so that the selfing problem can be solved by using the intersecting algorithm.
Consider first a simple division, as shown in FIG. 1 (a), when a curve is divided into two partsDivided into two smaller partsIn the time-course of which the first and second contact surfaces,Can be through the selfing of (a)AndRecursive self-cross-summation of (2)AndIs calculated by the intersection of (a) and (b). But this simple division causes a problem due toAndAdjacent when proceeding toAndThe connection point is typically used as the result of the intersection calculation. Checking whether they are smoothly connected or locally intersecting at a common point typically does not create significant performance overhead for two curves. When this is extended to a curved surface, however, two curved surface pieces are defined as shown in FIG. 1 (b)AndThe computational cost of whether the connection is smooth or locally intersecting along its common boundary is high. Conventional subdivision-based algorithms typically result in significant performance overhead by recursively subdividing the surface into smaller and smaller patches along a common boundary.
One simple remedy is to curve the edges covering a common boundary curveA self-intersecting test was performed as shown in fig. 2 (b). Under such division, two things need to be guaranteed, each part performs self-intersection detection, and intersection detection is performed between each two parts. Meanwhile, it is required to ensure that the intersection detection of any two adjacent parts should be replaced by the selfing detection of one large curved surface. Thus, can be used forAndThe intersection computation of (a) is replaced by. Meanwhile, since the intersection detection is required between any two sub-patches, the detection is also requiredAndIs a cross-over calculation of (2).
In order to more conveniently use BVH to represent the dividing process and reduce the performance cost caused by differencing operation on the curved surface, the curved surface can be usedIs divided into three partsThis division is implemented as shown in fig. 3 (b). Under this divisionAndNot directly adjacent but slightly spaced apart such thatAndThe intersection calculation of (2) can be performed directly. Spaced apart curved sheets use symbolsAnd (3) representing. Sub-dough sheetAt the same time coverAndAndIs a part of the same. Under this division, a curved surfaceThe selfing calculation of (a) can be converted into a pairPerforming recursive selfing calculation, andIs a cross-over calculation of (2).
Recursively subdividing the surface into three smaller parts means that each non-leaf node of the BVH structure will have three children, a left child, a middle child and a right child, which are responsible for recursive selfing. Meanwhile, the difference operation may be implicitly represented by limiting the parameter field of the subtree when performing the intersection calculation, without constructing an additional BVH structure, which will be described in detail in section 3.
Data structure and construction procedure of BVH
2.1 Background knowledge
2.1.1 Bounding volume hierarchy
The bounding volume (Bounding Volume) is a simple geometry for approximating or bounding a more complex object or collection for more efficient operation in computation. In computer graphics, bounding volumes are commonly used to accelerate collision detection, visibility testing, and spatial partitioning tasks. Some bounding volumes commonly used in computer graphics include bounding boxes (Bounding Box) representing the bounding extent of an object or collection of objects using a rectangle or cube, bounding balls (Bounding Sphere) representing the bounding extent of an object or collection of objects using a three-dimensional sphere, typically defined by calculating the center and radius of an object or collection of objects, bounding cones (Bounding Cone) representing the bounding extent of an object or collection of objects using a three-dimensional cone, which in some graphics applications may provide a more compact approximation, bounding cylinders (Bounding Cylinder) using a three-dimensional cylindrical approximation to the bounding object, which in some applications is used to accelerate collision detection and other geometric calculations, and bounding cones (Bounding Frustum) using a three-dimensional conical approximation to the bounding object, typically used to represent the view cone of a camera, which is used to cull objects that are not within the view cone, improving rendering performance. An Axis alignment bounding box (Axis-Aligned Bounding Box, AABB) is a special bounding box with edges parallel to the coordinate axes, which makes the testing and computation of the Axis alignment bounding box simpler, since only the minimum and maximum values on each coordinate Axis need to be checked, and an orientation bounding box (Oriented Bounding Box, OBB) is another bounding box with edges rotatable in any direction, which can more compactly enclose objects, but computation is more complex than AABB.
The bounding volume hierarchy (Bounding Volume Hierarchy, BVH) is a widely used data structure in the fields of computer graphics, computer games, ray tracing, etc. The main purpose of BVH is to accelerate the computation of search, collision detection, ray tracing, etc. of objects in space. BVH is typically composed of a tree structure, with each node representing an bounding volume (Bounding Volume), and the leaf nodes containing the actual objects or geometries. This hierarchy makes it more efficient to quickly locate and process objects in a scene.
2.1.2 Key mapping
A key-value map (Key Value Mapping) is a data structure or abstract data type that establishes a mapping from unique keys to corresponding values. In this configuration, each key uniquely identifies a value, allowing the value associated therewith to be accessed and manipulated by the key. Such a mapping is commonly referred to as a Dictionary (Dictionary), map, or associative array (Associative Array). The data structures implementing such mappings are different in different programming languages. Some common implementations include:
hash table, which uses hash function to map the key to a certain position in the memory to realize quick insert, search and delete operation. In C++, std:. Unordered _map is a key-value map implemented based on a hash table.
Red black tree-ordered key-value pairs are maintained by a self-balancing binary search tree. In C++, std:: map and std:: multimap are associated containers based on a red-black tree implementation.
Array or list the array or list is used to store key-value pairs and the value corresponding to the key is found by a linear search. The seek speed of this implementation is relatively slow, but still useful in certain scenarios.
2.2 Symbol description
In the selfing algorithm of the present invention, an Axis Aligned Bounding Box (AABB) is used as a bounding volume used by the Bounding Volume Hierarchy (BVH). Meanwhile, in each BVH node, other information is stored besides bounding volumes, including a parameter field, explicit storage of parameter field size, leaf node markers. Because BVH used in the invention is a three-tree, BVH nodes also comprise three pointers pointing to child nodes. Furthermore, since the parameter fields in the curve are one-dimensional, and the parameter fields in the surface are two-dimensional, there are different attribute values for the terms "explicit storage of parameter field size" and "parameter field", which are described in the application fields in the table below. The symbols used in the construction of BVH are as follows:
It should be noted that the number of the substrates, 、Is the parameter domain in the curve selfing BVH nodeA sub-item;、、、 Is a parameter domain in a curved-surface selfing BVH node Sub-items. Furthermore, in the following "." will be used to denote access to node properties, e.g. the symbol ""Represents the parameter domain of the access node".
The BVH construction algorithm will also use the leaf node mapping table,Is a key value map. Since the selfed special BVH causes that it will have repeated leaf nodes at the leaf node level, in order to avoid repeated sampling when computing bounding boxes, it is necessary to useTo complete the mapping from the parameter domain to the duplicate BVH leaf node set.The key of (a) is the parameter domainSet of BVH node pointers. In an implementation of the present invention, std + + map containers are used as the data structures that make up the leaf node mapping table.
Because the selfing algorithm of the invention adopts a special BVH dividing method and a corresponding dividing mode needs to be stored, the related data structure of the dividing table is now described, and the description of some symbols is as follows:
The nodes forming the dividing table The key is a key value mapping table, the key is the parameter domain length before division, and the value is the node formed by each item in the table. It should be noted that, hereinafter, we will use the symbol "[ key ]" to denote accessThe middle key is the node to which the "key" corresponds, and the symbol "," is used to access items in the node. For exampleIndicating that the obtained length isWhen dividing parameter domain of (a)The length of the region.
In an implementation of the present invention, std:: map container in c++ is used as the data structure that makes up the partition table. At the same time, the following table gives the results of the use of the present inventionThe relevant parameters, it should be noted that,Other parameters may be employed in different applications and requirements.
2.3 Construction of BVH
The construction of BVH is mainly divided into three parts, namely, firstly, the division of a parameter domain is finished from top to bottom, meanwhile, the construction of a BVH tree structure is finished, then, bounding boxes of all leaf nodes are calculated, the sampling on a curved surface and a curve is finished, and finally, the construction of the bounding boxes of all the nodes is finished from bottom to top. Most of the processes of curve selfing and surface selfing are similar, but because the parameter domain of the curve is one-dimensional and the parameter domain of the surface is two-dimensional, the calculation processes of the curve selfing and the surface selfing are slightly different, and the BVH construction process of the curve selfing and the surface selfing are separately described below.
2.3.1 Curve selfing
In the first part, the division of the curve parameter domain and the construction of the BVH for curve selfing will be completed, and the construction process will be performed in a recursive manner. The BVH construction algorithm also requires two sub-processes, namely initializing the BVH node (Init) and determining if the BVH node is a leaf node (DETERMINE). The construction process is shown in fig. 4.
In the initialization process, the parameter domain length of the node is input, the process applies for memory for one node, the parameter domain length of the node is written into the data of the node, and the pointer of the node is returned. If the length of the input is not valid, the process will return a null pointer directly. The process is described below using pseudocode:
In the process of judging the leaf node, a leaf node pointer is input, the process checks whether the parameter domain length of a leaf node is1 or not, and marks the leaf node of the node Set to the correct value. At the same time, the leaf node pointer is added to the leaf node mapping tableIn the set corresponding to the correct key in (c). If the input node pointer is invalid, the process will not proceed with any processing, and the pseudo code of this process is described as follows:
the process of constructing the curve selfing BVH mainly uses the domain length of the current node to inquire the dividing table Obtaining the domain length of the three sub-nodes, calling the Init process to initialize the sub-nodes, calculating the parameter domain of the sub-nodes according to the domain length of the current node, calling DETERMINE process to set the correct value for the leaf node mark of the sub-nodes, and completing the leaf node mapping tableFor use in computing bounding boxes. Then, the Generation procedure is recursively invoked on three children of the current node to complete the construction of BVH.
In the second part, the computation of bounding boxes for all leaf nodes will be completed. The process is that firstly, the step length of sampling on the curved surface is calculated according to the input sampling times, the step length of sampling is walked on the curved surface each time from the minimum parameter value, the point coordinates of the curved surface at the corresponding parameters are calculated, and then the parameters of the bounding box are updated according to the coordinates of the point. Finally, use leaf node mapping tableAnd setting a bounding box of the leaf nodes in the same parameter domain in the BVH.
Furthermore, since this portion is computationally intensive, it may be done using multithreading or using a GPU. The implementation of the invention adopts the OpenMP technology to carry out parallel acceleration. OpenMP (Open Multi-Processing) is an Application Programming Interface (API) for parallel programming that allows programmers to write parallel programs using shared memory. Serial codes can be easily converted into parallel codes through OpenMP to fully utilize the performance of multi-core processors and shared memory systems.
Non-uniform rational B-splines (Non-Uniform Rational B-Splines, NURBS) are widely used in the field of Computer Aided Design (CAD) because of their flexibility, accuracy and efficient representation and manipulation of curves and surfaces. Thus, the present invention uses NURBS as a parametric curve map.
A NURBS curve of order p is defined as:
Wherein the method comprises the steps of The representation is defined at the node vector asB-spline basis function with node vector length ofIn generalAnd (2) and;Control points representing parameter curves, the number of the control points being;Representing the weight of each control point. The computation of the B-spline basis function may be performed in a recursive manner:
the calculation process of the bounding box of the leaf node using the pseudo code is described below, and the symbols will be used in the algorithm Representing the passing parametersCalculating coordinates on NURBS curves:
in the third part, the construction process of the self-intersecting BVH bounding box of the curve from bottom to top is completed, and the construction is also performed in a recursive manner. First, the bounding box of the child node is constructed recursively until the child node is a leaf node or is empty. The bounding boxes of all child nodes are then merged together as the bounding box of the node, described below using pseudo code:
2.3.2 Curved surface selfing
In the first part, the division of the curved surface parameter domain and the construction of BVH used by curved surface selfing are completed. Similar to curve selfing, the build process also requires an initialization process (Init) and a leaf node decision process (DETERMINE). The construction process is shown in fig. 5.
In curved surface selfing, the initialization BVH node sub-process is similar to the initialization process in curved surface selfing, but because the parameter domain of the curved surface is two-dimensional, the use ofAndRecorded respectively inDirection and directionThe parameter domain length in the direction needs to be used at the same timeRecording the size of the parameter domain, and describing the process of initializing the curved surface selfing node by using a pseudo code as follows:
The judging leaf node algorithm in the curved surface selfing is basically consistent with the judging leaf node algorithm in the curved surface selfing, and only the judging condition is changed from the length (one dimension) of the parameter domain to the size (two dimensions) of the domain, and the judging process of the leaf node is described as follows by using pseudo codes:
Similar to curve selfing, the construction of BVH will be accomplished using a recursive process. However, unlike BVH, where the curves are selfed, the partitioning of the parameter domain will alternate in two directions, each time the partitioning will be done for the longer side, the partitioning process is described using pseudocode as follows:
In the second part, the computation of bounding boxes for all leaf nodes will be completed. The calculation process is similar to that of the leaf node bounding box in curve selfing, but since the parameter domain of the curved surface is two-dimensional, the calculation of the sampling step length and the walking will be performed in two directions. Similar to curve selfing, the invention uses NURBS as parameter surface mapping and adopts OpenMP technology to accelerate in parallel.
A NURBS surface of the p-order in the u-direction and the q-order in the v-direction is defined as:
Wherein the method comprises the steps of Is shown inThe direction is defined as the node vectorB-spline basis function of length of;Is shown inThe direction is defined as the node vectorB-spline basis function of length of;Representing a network of control points; Representing the weight of each control point. The computation of the B-spline basis function is identical to that in the NURBS curve.
The calculation process of the bounding box of the leaf node using the pseudo code is described below, and the symbols will be used in the algorithmRepresenting passing parameter pairsCalculating coordinates on the NURBS surface:
In the third part, the construction process of the curved surface selfing BVH bounding box from bottom to top is completed, and the process is identical to the algorithm 2-5 in the curved surface selfing, and will not be repeated here.
BVH traversal and selfing algorithm
The construction of BVH required for calculating curve selfing and curved surface selfing is completed in section 2, and on the basis, the area with the self-intersecting can be searched by traversing the BVH. Since the BVH structure of curve selfing is the same as that of curved selfing, the BVH traversal process described below is applicable to both curve selfing and curved selfing.
According to the description of the algorithm in section 1, in the process of calculating the selfing, the selfing calculation is performed on the child nodes recursively, and the intersections of three non-adjacent areas are calculated, which will show two parts of the selfing and the intersection in the algorithm.
The following will first describe the intersecting part, the intersecting traversal process will accept two BVH node pointers and two parameter fields as parameter field restrictions for the subtree rooted at these two BVH nodes, this parameter field restriction will pass down as recursion proceeds. During the intersection traversal, the algorithm always keeps one node stationary, and three children of another node are used to recursively perform the intersection traversal. First the algorithm will check the validity of the input and if any BVH node pointer is a null pointer, the algorithm will not do anything. The algorithm will then check if there is an intersection of the AABB bounding boxes stored in the current two BVH nodes, and if the bounding boxes in the two BVH nodes do not intersect, indicating that there will be no intersection of nodes in the BVH subtree rooted at these two nodes, at which point the algorithm will return directly to implement pruning of the BVH tree. Otherwise, the algorithm uses three child nodes of the larger node to recursively traverse with another node, in order to ensure that the larger node is divided during each recursion, the algorithm compares the size of the parameter domain stored in the node, and for curve selfing, the algorithm comparesFor curved surface selfing, the comparison is that. The traversal of the curves and surfaces is shown in fig. 6 and 7.
The traversal ends when both current nodes are leaf nodes, at which point the algorithm checks whether the parameter fields of both nodes are in the corresponding constraint parameter fields. If the check passes, the description algorithm finds a pair of leaf nodes with the possibility of intersection, and then the algorithm inserts the parameter fields corresponding to the pair of leaf nodes into the intersection table. Intersection tableIs a hash table, and is mainly used for removing duplication of the cross-over. The pseudocode for the traversal procedure is described as follows:
The selfing part will be described next, from the parametric curve Or parametric surfacesThe BVH root node of the current node begins by recursively invoking the self-traversal process for three children of the current node, and stopping recursion when a child is a null pointer or leaf node. Then, the intersection of the three parts is calculated. Here, the algorithm will calculate the limits of the parameters and pass them in as parameters for the intersection process. It is worth noting that for intersecting pairs that do not require parameter domain restriction, the original parameter domain will be directly imported. The pseudo code of the selfthrough procedure is described as follows:
4. Topology reconstruction
In the algorithm of section 3, we can obtain all curve segments and pairs of curved surface sheets that need to be intersected. In this section, topology reconstruction is performed on these curve segment and curved surface segment pairs, and the task of topology reconstruction is to connect all adjacent curve segments and curved surface segments to obtain a large curve and curved surface. This is done in order to be able to calculate the step size of the travel correctly when solving the self-intersection point and the self-intersection curve later using the travel method. The tasks that the topology reconstruction needs to accomplish are shown in fig. 8.
In the process of topology reconstruction, a topology reconstruction table is needed, and the related data structure of the topology reconstruction table is described, and the meanings of some symbols are as follows:
The nodes forming the topology reconstruction table, the topology table Is a key-value mapping table, whose key is a parameter domain and whose value is a node formed by each item in the table. It should be noted that, due to the different dimensions of the curve and the curved surface parameter domain, the table is dividedThe actual implementation differs between curve selfing and curved surface selfing, but the algorithm flow is approximately the same.
First, it is necessary to initialize topology rebuild tableThe process is mainly as follows, for the intersection table obtained in section 3The parameter fields of the topology reconstruction table are used as key values of the topology reconstruction table, and the corresponding parameter fields are added into a set of intersecting parameter fields corresponding to the key values. Then, for each entry in the topology rebuilding table, its key is fetched as the current parameter domain, and it is checked whether neighbors around the current parameter domain are in the topology rebuilding table. If so, the parameter domain of the neighbor is added to the neighbor parameter domain set of the key value corresponding to the current parameter domain in the topology rebuilding table. It should be noted that, in the curve selfing and the curved surface selfing, the data of the neighbor nodes to be inspected are different because of the different dimensions of the parameter domain.
After the topology reconstruction table is constructed, the topology relationship can be reconstructed by using the topology reconstruction table. The algorithm traverses the topology reconstruction table once to ensure that every element in the topology reconstruction table is processed. For each element in the topology reconstruction table, the algorithm will first detect the validity of the element, i.e. ensure that the element that has completed processing will not be processed again. Then, if this element passes the legitimacy detection, then this element is added to the stackAnd then a round of parameter domain connection operation is performed.
In each round of connection, the stack is first of all fromPopping up a parameter field as the currently processing parameter fieldAnd willAnd a currently federated parameter domainIs a copy of (a)And (5) combination.
We then query all and using the topology reconstruction tableThere is a parameter domain of the intersection relationship. In these parameter fields, find all intersecting parameter field sets that are currently being processedParameter domains with adjacent relations exist and are added to the setIs a kind of medium. Then according to the collectionComputing and updating complete parameter fields in which all parameter fields are joined together. The case of one curved surface piece or curve segment and a plurality of curved surface pieces or curve segments is mainly considered here, as shown in FIG. 9, and thereforeThe parameter fields with the intersecting relationship cannot be directly added toIn which additional connectivity checks are required, otherwise this would result inIs expanded.
If it isAndOverlap, description pairProcessing results in a current parameter domain join failure, in which case we willPut in a stackAmong these, the parameter field is processed as the next round. Otherwise we update the current parameter domain using the duplicate parameter domain and sendPut parameter fields of all unprocessed neighbor nodes on the stackIs a kind of medium.
Each time stackWhen empty, the one-time association is explained as completed. In this case, the parameter fields that have been completed by the connection are put into the result set and all temporary variables are reset for the next federation. The algorithm is described using pseudocode as follows:
5. Calculation of self-intersection points and self-intersection lines
The method is mainly used for converting the curve and the curve selfing problem into the intersecting problem, and no additional optimization is carried out on the calculation of the selfing point and the selfing curve. Curve intersection and curved surface intersection currently exist more calculation methods. In this section, the calculation method of the intersection point and the intersection line used in the present invention is mainly briefly described from the viewpoint of methodology. In the present invention, the intersection problem is solved mainly using the tracing method, and the BVH technique is used to calculate the starting point in the tracing method. The curved surface intersection algorithm flow adopting the tracking method is introduced as follows:
1) BVH used for establishing the intersection problem is that the BVH structure constructed by intersecting the curve and the curved surface is different due to the different dimensions of the parameter domain. For curve intersection, BVH is a binary tree, while surface intersection uses a quadtree. In BVH of the intersection problem, each division of the parameter domain will no longer use the division of the specified length in the selfing, but a uniform and non-overlapping division is employed. The depth of the BVH is determined by the parameters of the incoming.
2) Traversing intersection problem BVH find intersection box pairs traversing BVH for two curves or surface constructions. Traversal will start from the root node of two BVHs, if the bounding boxes of the two nodes intersect, then all their child nodes will go to the next round of intersection decision, otherwise, it is stated that there is no intersection of the subtrees rooted at the two nodes, and the algorithm will prune. Until it is determined that the leaf node level is reached, all the intersection box pairs are obtained.
3) And carrying out Newton iteration on each pair of boxes to find a starting point, namely using the intersected box pair as the starting point, generally adopting a coordinate point corresponding to the midpoint of the parameter domain in the two boxes as the starting point of the iteration, and adopting a Newton iteration method or other numerical calculation methods to calculate the starting point. Meanwhile, it is necessary to exclude unusable starting points, including points outside the parameter domain, points already in the result set, tangential points, degenerate points, and the like. Meanwhile, if a starting point approaches the degradation point for the robustness of the algorithm, the starting point is also excluded. It should be noted that the problem of curve intersection is solved at this step, and the starting point found by the newton iteration method is the intersection point of the curve intersection problem.
4) The tracking method is used to calculate the points on a series of intersections, and after a starting point is calculated, the tracking method can be used to calculate the points on a series of intersections. The basic idea of the tracking method is to start with a starting point, walk a given step along a certain direction of travel to find the next point on the intersection, and loop this way until either the starting point is returned (in case the intersection is a loop) or the limit of the parameter field is taken.
5) Fitting all the resulting points to a B-spline curve, i.e. a series of intersections are obtained in step 4), which are fitted to a B-spline curve at the end of the algorithm, typically by means of a least squares method or other mathematical optimization method. It should be noted that steps 3) to 5) are usually performed together to ensure that the newly found starting point is not on the intersection line where the calculation has been completed.
The selfing problem is solved by using the intersection solving algorithm, and only the step 1) and the step 2) of the process are replaced by the selfing BVH constructing algorithm in the section 2 and the selfing BVH traversing algorithm in the section 3, so that the intersection solving box pair can be obtained. The BVH used in the intersection algorithm and the BVH used in the selfing algorithm have different structures at higher layers, but have the same structure at the leaf node layer.
It should be noted that, according to the BVH partitioning method used in section 2 of the present invention, the leaf nodes are a grid of 128×128, which is the same as the leaf node structure of the intersecting BVH using 8-layer full quadtree, and if intersecting BVH with different depth is used, the partitioning method in section 2 needs to be modified.
Some examples of selfing calculations performed using the methods of the present invention are shown in FIGS. 10-17. It can be seen that the method of the present invention can effectively process parameter curves or curved surfaces of various complexity and forms, and has wide applicability, high efficiency and sufficient robustness.
There is also provided, in accordance with a specific embodiment of the present invention, an electronic device including a memory, a processor, and a computer program stored on the memory and executable on the processor, the processor implementing the steps of any one of the methods described above when the program is executed.
According to a specific embodiment of the present invention, there is also provided a computer readable storage medium having stored thereon a computer program which when executed by a processor performs the steps of any of the methods described above.
The foregoing descriptions of specific exemplary embodiments of the present invention are presented for purposes of illustration and description. It is not intended to limit the invention to the precise form disclosed, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. It is apparent that the present invention is not limited to the above-described specific embodiments, and that various changes or modifications may be made by those skilled in the art within the scope of the claims without affecting the essential content of the present invention. The exemplary embodiments were chosen and described in order to explain the specific principles of the invention and its practical application to thereby enable one skilled in the art to make and utilize the invention in various exemplary embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims and their equivalents.
Claims (10)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411054668.4A CN118569003B (en) | 2024-08-02 | 2024-08-02 | A universal parametric curve or surface self-intersection calculation method, device and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411054668.4A CN118569003B (en) | 2024-08-02 | 2024-08-02 | A universal parametric curve or surface self-intersection calculation method, device and storage medium |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN118569003A CN118569003A (en) | 2024-08-30 |
| CN118569003B true CN118569003B (en) | 2024-12-24 |
Family
ID=92479684
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411054668.4A Active CN118569003B (en) | 2024-08-02 | 2024-08-02 | A universal parametric curve or surface self-intersection calculation method, device and storage medium |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN118569003B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118864474B (en) * | 2024-09-26 | 2025-01-28 | 八维通科技有限公司 | Self-intersection detection method and program product of spiral surface model in geometry engine |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117115393A (en) * | 2023-07-24 | 2023-11-24 | 浙江大学 | A GPU-based parallel intersection method, equipment and storage medium for NURBS surfaces |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7952583B2 (en) * | 2000-06-19 | 2011-05-31 | Mental Images Gmbh | Quasi-monte carlo light transport simulation by efficient ray tracing |
| US8188997B2 (en) * | 2000-06-19 | 2012-05-29 | Mental Images Gmbh | Accelerated ray tracing using shallow bounding volume hierarchies |
| US20230298127A1 (en) * | 2022-03-18 | 2023-09-21 | Intel Corporation | Apparatus and method for biased bvh traversal path |
-
2024
- 2024-08-02 CN CN202411054668.4A patent/CN118569003B/en active Active
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117115393A (en) * | 2023-07-24 | 2023-11-24 | 浙江大学 | A GPU-based parallel intersection method, equipment and storage medium for NURBS surfaces |
Also Published As
| Publication number | Publication date |
|---|---|
| CN118569003A (en) | 2024-08-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Pham | Offset curves and surfaces: a brief survey | |
| CN112669434B (en) | Collision detection method based on grid and bounding box | |
| Rossignac et al. | Offsetting operations in solid modelling | |
| Raghothama et al. | Boundary representation deformation in parametric solid modeling | |
| CN104361632B (en) | A kind of triangle gridding filling-up hole method based on Hermite RBFs | |
| Cameron | Efficient intersection tests for objects defined constructively | |
| CN118569003B (en) | A universal parametric curve or surface self-intersection calculation method, device and storage medium | |
| CN119129183B (en) | A collision detection method for 3D CAD models based on BVH and sum-of-squares programming | |
| CN118886412B (en) | Shaft part feature recognition method and system based on STEP | |
| Du et al. | Robust computation of implicit surface networks for piecewise linear functions | |
| CN115859524B (en) | A Method of Cylindrical Boolean Difference Based on STL Model | |
| Lee et al. | Computing the medial surface of a 3-D boundary representation model | |
| CN117274524A (en) | Data processing method and device, electronic equipment and storage medium | |
| Xu | An approach to develop 3d Geo-DBMS topological operators by re-using existing 2d operators | |
| Städtler et al. | Topological queries in a space partitioning model: Definition, visualization and exports of results | |
| Huang et al. | Delaunay growth algorithm based on point cloud curvature smoothing improvement | |
| CN119047165B (en) | An intelligent segmentation generation method for large-span irregular rigid bodies | |
| Gauthier et al. | CAD-driven analysis and beautification of reverse engineered geometric models | |
| CN117349914B (en) | Boolean operation method based on surrounding number | |
| Li et al. | Improved internal voxelization algorithm based on depth buffer | |
| CN120125764A (en) | Terrain generation method, electronic device and medium | |
| CN119312521A (en) | A BVH construction and elimination method for parametric surface intersection | |
| Zhu et al. | Generation of hierarchical multi-resolution medial axis for CAD models | |
| Jablokow et al. | Verification of boundary representations of solid models | |
| Paskaleva | Procedural shape contraction: Integration of architectural details into 3d conceptual models |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |