CN117893655B - Method for improving search speed of clipping points and GPU speed - Google Patents
Method for improving search speed of clipping points and GPU speed Download PDFInfo
- Publication number
- CN117893655B CN117893655B CN202310417737.2A CN202310417737A CN117893655B CN 117893655 B CN117893655 B CN 117893655B CN 202310417737 A CN202310417737 A CN 202310417737A CN 117893655 B CN117893655 B CN 117893655B
- Authority
- CN
- China
- Prior art keywords
- gpu
- sub
- bezier
- curved surface
- speed
- 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
- 238000000034 method Methods 0.000 title claims abstract description 65
- 238000009966 trimming Methods 0.000 claims abstract description 7
- 238000010008 shearing Methods 0.000 claims abstract description 4
- 239000011800 void material Substances 0.000 claims abstract description 4
- 238000004364 calculation method Methods 0.000 claims description 8
- 238000000691 measurement method Methods 0.000 claims description 6
- 230000011218 segmentation Effects 0.000 claims description 4
- 230000001133 acceleration Effects 0.000 claims description 3
- 238000006243 chemical reaction Methods 0.000 claims description 3
- 238000011156 evaluation Methods 0.000 claims description 3
- 230000008569 process Effects 0.000 abstract description 9
- 230000006870 function Effects 0.000 description 6
- 238000011960 computer-aided design Methods 0.000 description 4
- 238000009877 rendering Methods 0.000 description 4
- 230000009471 action Effects 0.000 description 3
- 238000007792 addition Methods 0.000 description 3
- 230000008878 coupling Effects 0.000 description 3
- 238000010168 coupling process Methods 0.000 description 3
- 238000005859 coupling reaction Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 238000004891 communication Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 238000005192 partition Methods 0.000 description 2
- 230000007547 defect Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000007781 pre-processing Methods 0.000 description 1
- 230000009467 reduction Effects 0.000 description 1
- 230000003252 repetitive effect Effects 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T15/00—3D [Three Dimensional] image rendering
- G06T15/005—General purpose rendering architectures
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T1/00—General purpose image data processing
- G06T1/20—Processor architectures; Processor configuration, e.g. pipelining
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T15/00—3D [Three Dimensional] image rendering
- G06T15/06—Ray-tracing
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Graphics (AREA)
- Image Generation (AREA)
Abstract
The invention discloses a method for improving the search speed of clipping points and the speed of a GPU, which comprises the following steps: converting the cut NURBS curved surface into a rational Bezier curved surface through node refinement; subdividing the Bezier curved surface into a plurality of sub-curved surfaces so as to meet the flatness requirement of the curved surface; and shearing and removing the curved surface of the void by a trimming curve. The invention improves the data structure algorithm in the process of tracking NRUBS curved surfaces of the light rays, calculates the intersection point of the light rays and the unclamped Bezier subsurface by using the boundary body hierarchical structure with the axis alignment boundary box and the Newton iteration method, can achieve the real-time performance on the GPU, and improves the speed of the GPU by 20% -30%, and the method can be better utilized on the modern GPU with the dynamic surface subdivision function, thereby achieving the real-time performance of tens of thousands to hundreds of millions of light rays projected on the GPU in a complex scene comprising hundreds of thousands of NURBS curved surfaces and clipping curves.
Description
Technical Field
The invention relates to the technical field of geometric surface modeling, in particular to a method for improving the search speed of clipping points and the speed of a Graphic Processing Unit (GPU).
Background
The invention is mainly based on the background of two aspects, namely, the trimmed NURBS curved surface is a most commonly used modeling mode in the field of geometric modeling, and the number of modeling by using the method is rapidly increased in recent years; secondly, ray tracing has become a rapidly developing method for generating computer-real graphic images of geometric models.
The NURBS curved surface is a powerful mathematical tool, can uniformly represent various curved surfaces such as planes, quadrics, beta splines, beziers and the like, supports a modeling system of the NURBS, and can functionally produce most practical complex curved surfaces. Particularly in Computer Aided Design (CAD), NURBS surfaces have the advantage of great flexibility in representing shapes and ease of locally predicting shape manipulation during modeling.
The 3D model is typically represented by a set of base NURBS surfaces and a set of clipping curves when represented by a clipped NURBS surface. Each surface of this geometry consists of two parts, one being the basic 3D shape represented by NURBS surfaces and the other being a circular non-intersecting clipping curve represented by NURBS curves in the 2D parameter domain. The clipping curve specifies which regions on the parametric surface of the relevant shape are valid, thereby creating geometric regions such as holes. The curves represented by NURBS are mathematically similar to surfaces created by the tensor product of the two curves.
The use of a clipped NURBS surface to represent geometric models has become a standard for the CAD industry.
The prior art has the following defects: in CAD applications, surface rendering is usually solved by surface subdivision and z-buffer rendering, however, such rendering method is prone to visible artifacts, because fixed rendering can cause highlighting of triangle edges, furthermore, triangle meshes may become very large and occupy a large amount of memory, so ray tracing calculation of NURBS surfaces is difficult to realize in real-time due to the fact that the calculation is complex and the calculation amount is large, and thus, the method for improving the clipping point searching speed and GPU speed based on a two-dimensional data structure is not widely used in industry, so a need exists at present.
The above information disclosed in the background section is only for enhancement of understanding of the background of the disclosure and therefore it may include information that does not form the prior art that is already known to a person of ordinary skill in the art.
Disclosure of Invention
The invention aims to provide a method for improving the searching speed of clipping points and the GPU speed, and provides a two-dimensional data structure which can realize faster searching of the positions of the clipping required points through Newton iteration method based on the method step of carrying out ray tracing on NURBS curved surfaces, thereby realizing faster ray tracing, simultaneously realizing that the representation of the method needs less memory and less preprocessing time, and using self-adaptive curved surface subdivision about the view points, the method can achieve real-time performance on the GPU, can be better utilized on the modern GPU with dynamic curved surface subdivision function, thereby achieving the real-time performance of tens of thousands to hundreds of millions of rays per second in the complex scene comprising the NURBS curved surfaces and clipping curves, and improving the GPU performance by nearly 20-30 percent so as to solve the problems in the background technology.
In order to achieve the above object, the present invention provides the following technical solutions: 1. a method of increasing crop point search speed and GPU speed, comprising the steps of:
Step one: converting the cut NURBS curved surface into a rational Bezier curved surface through node refinement;
step two: subdividing the Bezier curved surface into a plurality of sub-curved surfaces so as to meet the flatness requirement of the curved surface;
When the intersection point of the Bezier curved surface and the ray is calculated by using Newton iteration method, the Bezier curved surface is flat enough to provide a good initial estimated value close to the real intersection position, the original Bezier curved surface is subdivided into sub-curved surfaces according to the flatness standard, and the calculation is directly completed on the converted rational Bezier curved surface
Step three: shearing and removing the curved surface of the void by a trimming curve;
After creating the Bezier sub-surfaces, the system forms an axis aligned bounding box for each sub-surface, each sub-surface is defined by a control point, and the generated surface is positioned in a convex hull of the control point, so that the tight axis aligned bounding box on the control point also comprises the sub-surfaces, once the axis aligned bounding box is projected into the UV coordinate parameter space as a line segment, whether the sub-surfaces intersect with the 2D shape can be checked, and if the sub-surfaces do not intersect, the sub-surfaces are deleted from the sub-surface list;
step four: constructing a trimming data structure of each curved surface;
step five: constructing a global acceleration data structure for ray tracing of the tight bounding box of the sub-surface;
Various ray tracing measurement techniques are used, as GPUs can in principle use any valid data structure for ray tracing;
using a boundary body hierarchical structure with an axis alignment boundary frame, wherein the boundary body hierarchical structure is constructed by geometric median segmentation, firstly, the boundary body hierarchical structure is segmented along the longest axis, then, the boundary body hierarchical structure is segmented according to a circulation sequence, and finally, the boundary body hierarchical structure is optimized through interpolation;
step six: serializing all prepared data to an array buffer area and transmitting the data to a GPU memory;
step seven: ray tracing is performed on the constructed data structure.
Preferably, in the seventh step, the method includes the steps of:
a. traversing a data structure for ray tracing on the GPU to a leaf containing a Bezier sub-surface;
b. calculating the intersection point of the ray and the Bezier sub-surface to obtain two-dimensional point coordinates (U, V) in the parameter space UV coordinates;
c checking two-dimensional points (U, V) on the clipping curve of the two-dimensional space.
Preferably, in step a, a plurality of ray tracing measurement techniques are used, since the GPU may in principle use any valid data structure for ray tracing;
The boundary body hierarchical structure with the axis alignment boundary box is used, the boundary body hierarchical structure is constructed by geometric median segmentation, the boundary body hierarchical structure is firstly segmented along the longest axis, then segmented according to a circulation sequence, and finally optimized through interpolation.
Preferably, in step B, the intersection point of the ray and the unclamped Bezier subsurface is calculated by using Newton's iterative method, and for the bottom layer evaluation algorithm of the 3D point given a pair of (U, V) coordinates, an algorithm with complexity of O (N 2) is used, which can increase the speed of the GPU by 20% -30%;
in the algorithm, firstly, a rational Bezier curve in a ternary is defined:
p(t)＝Π(P(t))
wherein:
in the above equation, P i＝bi(xi,yi,zi, w), the projection operator pi is defined as:
Π(x，y，z，w)＝(x/w，y/w，z/w)
the points and tangents to the curve can be found using the following formula structure:
P(t)＝(1-t)Q(t)+tR(t) (A)
wherein:
The straight line tangent to the curve in equation a can be found as:
q(t)-r(t)≡Π(Q(t))-Π(R(t))
The derivative of p (t) is:
the values of Q (t) and R (t) find the bernstein polynomial by pseudo-base conversion using a modified holner algorithm:
where u=t/(1-t), i＝0，1，...，n-1。
Preferably, if the curve is to be calculated multiple times, the pre-calculation is ignoredAnd part of nested multiplication:
N-1 multiplication and addition operations are performed on four coordinates of x, y, z, w, and post-multiplication (1-t) n-1 is not required because:
Thus, the point P (t) and its tangential direction can be calculated by multiplying 2n times and adding the coordinates for four x, y, z, w;
The method uses the following formula in the interval of 0.5-1:
wherein u= (1-t)/t;
A tensor product rational Bezier surface is defined as follows:
p(s，t)＝Π(P(s，t))
wherein:
Ps (s, t) can also be expressed by the following formula:
P(s，t)＝(1-s)(1-t)P00(s,t)+s(1-t)P10(s,t)+(1-s)tP01(s,t)+stP11(s,t)
wherein:
tangential vector P s (s, t) is parallel to the line:
Π((1-t)P00(s,t)+tP01(s,t))-Π((1-t)P10(s,t)+tP11(s，t))
tangential vector P s (s, t) is parallel to the line:
Π((1-s)P00(s,t)+tP10(s,t))-Π((1-s)P01(s,t)+sP11(s,t))
The hall algorithm for the tensor product surface is obtained by defining the following formula:
Wherein the method comprises the steps of N rows of four binary polynomials are multiplied and added m-1 times to calculate the components of each x, y, z, w, and the final value of t is multiplied and added n-1 times to the components of each x, y, z, w.
Preferably, if m=n, the four surfaces P 00(s,t)、P01(s,t)、P10 (s, t) and P 11 (s, t) are evaluated by multiplying n 2 -1 times and adding n 2 -1 times for each of the four x, y, z, w components, totaling 16n 2 -16 times and 16n 2 -16 times.
In the technical scheme, the invention has the technical effects and advantages that:
The invention improves the data structure algorithm in the process of tracking NRUBS curved surfaces of the light rays, calculates the intersection point of the light rays and the unclamped Bezier subsurface by using the boundary body hierarchical structure with the axis alignment boundary box and the Newton iteration method, can achieve the real-time performance on the GPU, and improves the speed of the GPU by 20% -30%, and the method can be better utilized on the modern GPU with the dynamic surface subdivision function, thereby achieving the real-time performance of tens of thousands to hundreds of millions of light rays projected on the GPU in a complex scene comprising hundreds of thousands of NURBS curved surfaces and clipping curves.
Drawings
In order to more clearly illustrate the embodiments of the present application or the technical solutions in the prior art, the drawings required for the embodiments will be briefly described below, and it is apparent that the drawings in the following description are only some embodiments described in the present application, and other drawings may be obtained according to these drawings for a person having ordinary skill in the art.
FIG. 1 is a flow chart of a method for ray tracing NURBS surfaces that is a method for improving the speed of clipping point search and GPU speed according to the present invention.
FIG. 2 is a schematic diagram of the curve in the present invention.
Detailed Description
Example embodiments will now be described more fully with reference to the accompanying drawings. However, the exemplary embodiments may be embodied in many forms and should not be construed as limited to the examples set forth herein; rather, these example embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the concept of the example embodiments to those skilled in the art. The drawings are merely schematic illustrations of the present disclosure and are not necessarily drawn to scale. The same reference numerals in the drawings denote the same or similar parts, and thus a repetitive description thereof will be omitted.
Furthermore, the described features, structures, or characteristics may be combined in any suitable manner in one or more example embodiments. In the following description, numerous specific details are provided to give a thorough understanding of example embodiments of the disclosure. One skilled in the relevant art will recognize, however, that the aspects of the disclosure may be practiced without one or more of the specific details, or with other methods, components, steps, etc. In other instances, well-known structures, methods, implementations, or operations are not shown or described in detail to avoid obscuring aspects of the disclosure.
The invention provides a method for improving the search speed of clipping points and the speed of a GPU (graphics processing Unit), which is shown in figures 1-2, and comprises the following steps:
Step one: converting the cut NURBS curved surface into a rational Bezier curved surface through node refinement;
step two: subdividing the Bezier curved surface into a plurality of sub-curved surfaces so as to meet the flatness requirement of the curved surface;
In the second step, when the intersection point of the Bezier surface and the ray is calculated by using the Newton iteration method, the Bezier surface must be flat enough to provide a good initial estimated value close to the real intersection position, the original Bezier surface needs to be subdivided into sub-surfaces according to the flatness standard, but the calculation is directly completed on the converted rational Bezier surface, so that the subdivision process must be strict enough to ensure that the root search method used on the rational Bezier surface can converge;
step three: shearing and removing the curved surface of the void by a trimming curve;
In the third step, after creating the Bezier sub-surfaces, the system forms an axis aligned bounding box for each sub-surface, each sub-surface is defined by a control point, the generated surface must be located in the convex hull of its control point, so that the tight axis aligned bounding box on the control point must also contain sub-surfaces, once the axis aligned bounding box is projected as a line segment into the UV coordinate parameter space, it can check if the sub-surfaces intersect with the 2D shape, if not, it is deleted from the list of sub-surfaces, and at the same time, using the clipping method in the NURBS model of specific clipping may result in a significant reduction of the sub-surfaces;
step four: constructing a trimming data structure of each curved surface;
step five: constructing a global acceleration data structure for ray tracing of the tight bounding box of the sub-surface;
in step five, a number of ray tracing measurement techniques are used, since the GPU can in principle use any effective data structure for ray tracing, using a Bounding Volume Hierarchy (BVH) with axis aligned bounding boxes, built from geometric median partitions, first along the longest axis, then in circular order, and finally optimized by interpolation;
step six: serializing all prepared data to an array buffer area and transmitting the data to a GPU memory;
The memory layout and data transfer from the CPU to the GPU in this step is trivial, as the data on the CPU is put into the buffer and transferred into the GPU memory;
Step seven: performing ray tracing on the constructed data structure;
The method comprises the following steps:
a. traversing a data structure for ray tracing on the GPU to a leaf containing a Bezier sub-surface;
In this step, a number of ray tracing measurement techniques are used, since the GPU can in principle use any effective data structure for ray tracing, using a Bounding Volume Hierarchy (BVH) with axis aligned bounding boxes, built from geometric median partitions, first along the longest axis, then in circular order, and finally optimized by interpolation;
b. Calculating the intersection point of the ray and the Bezier sub-surface to obtain two-dimensional point coordinates (u, v) in the parameter space UV coordinates;
in this step Newton's iterative method is used to calculate the intersection of the ray with the unclamped Bezier subsurface, using a complexity of the underlying evaluation algorithm for the 3D point given a pair of (U, V) coordinates
O (N 2) can increase the speed of the GPU by 20% -30%, possibly due to the small amount of registers used in the algorithm.
In the algorithm, firstly, a rational Bezier curve in a ternary is defined:
p(t)＝Π(P(t))
wherein:
In the above formula, P i＝wi(xi,yi,zi, l), the projection operator pi is defined as
Π(x，y，z，w)＝(x/w，y/w，z/w)；
It should be noted that in these formulas, the uppercase bold variables will be used to represent the quadruples (homonyms), and the lowercase bold indicates the points in the triples;
the points and tangents to the curve can be found using the following formula structure:
P(t)＝(1-t)Q(t)+tR(t)
wherein:
The straight line tangent to the curve in formula (3) is Q (t) -R (t) ≡pi (Q (t)) -pi (R (t)), and the schematic diagram is shown in fig. 2, and the derivative of p (t) is:
the values of Q (t) and R (t) can be found by pseudo-base conversion using a modified holner algorithm to find the bernstein polynomial:
where u=t/(1-t),
If the curve is to be calculated for a plurality of times, the pre-calculation is ignoredAnd part of nested multiplication:
N-1 multiplication and addition operations are performed on four coordinates of x, y, z, w, and post-multiplication (1-t) n-1 is not required because:
thus, the point P (t) and its tangential direction can be calculated by multiplying about 2n times and adding the coordinates for four x, y, z, w;
This method has a problem in the vicinity of t=1, and therefore, the following formula is preferably used in the interval 0.5.ltoreq.t.ltoreq.1:
Where u= (1-t)/t.
A tensor product rational Bezier surface is defined as follows:
p(s,t)＝Π(P(s,t))
wherein:
p (s, t) can also be expressed by the following formula:
P(s，t)＝(1-s)(1-t)P00(s,t)+s(1-t)P10(s,t)+(1-s)tP01(s,t)+stP11(s，t)
wherein:
tangential vector P s (s, t) is parallel to the line:
Π((1t)P00(s,t)+tP01(s,t))-Π((1-t)P10(s,t)+tP11(s,t))
tangential vector P t (s, t) is parallel to the line:
Π((1-s)P00(s,t)+tP10(s,t))-Π((1-s)P01(s,t)+sP11(s，t))
The hall algorithm for the tensor product surface is obtained by defining the following formula:
Wherein the method comprises the steps of All n lines of the four binary polynomials can be multiplied and added m-1 times to calculate the components of each x, y, z, w, and the final value of t is multiplied and added n-1 times to the components of each x, y, z, w;
Thus, if m=n, the four surfaces P 00(s,t)、P01(s,t)、P10 (s, t) and P 11 (s, t) can be evaluated by multiplying n 2 -1 times and adding n 2 -1 times for each of the four x, y, z, w components, for a total of 16n 2 -16 times and 16n 2 -16 times additions;
c checking two-dimensional points (u, v) on a clipping curve in two-dimensional space;
The invention improves the data structure algorithm in the flow of tracking NRUBS curved surfaces of the light rays, calculates the intersection point of the light rays and the unclamped Bezier subsurface by using a boundary body hierarchical structure (BVH) with an axis alignment boundary box and a Newton iteration method, can achieve the real-time performance on the GPU, and improves the speed of the GPU by 20% -30%. The method can be better utilized on a modern GPU with a dynamic surface subdivision function, so that the quantity of rays projected on the GPU can reach real-time performance of tens of thousands to hundreds of millions of rays per second in a complex scene containing hundreds of thousands of NURBS surfaces and clipping curves.
While certain exemplary embodiments of the present invention have been described above by way of illustration only, it will be apparent to those of ordinary skill in the art that modifications may be made to the described embodiments in various different ways without departing from the spirit and scope of the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature and not as restrictive of the scope of the invention, which is defined by the appended claims.
It is noted that relational terms such as first and second, and the like, if any, are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises an element.
It should be understood that, in various embodiments of the present application, the sequence numbers of the foregoing processes do not mean the order of execution, and the order of execution of the processes should be determined by the functions and internal logic thereof, and should not constitute any limitation on the implementation process of the embodiments of the present application.
Those of ordinary skill in the art will appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, or combinations of computer software and electronic hardware. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the solution. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present application.
It will be clear to those skilled in the art that, for convenience and brevity of description, specific working procedures of the above-described systems, apparatuses and units may refer to corresponding procedures in the foregoing method embodiments, and are not repeated herein.
In the several embodiments provided by the present application, it should be understood that the disclosed systems, devices, and methods may be implemented in other manners. For example, the apparatus embodiments described above are merely illustrative, e.g., the division of the units is merely a logical function division, and there may be additional divisions when actually implemented, e.g., multiple units or components may be combined or integrated into another system, or some features may be omitted or not performed. Alternatively, the coupling or direct coupling or communication connection shown or discussed with each other may be an indirect coupling or communication connection via some interfaces, devices or units, which may be in electrical, mechanical or other form.
The units described as separate units may or may not be physically separate, and units shown as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution of this embodiment.
In addition, each functional unit in the embodiments of the present application may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit.
The functions, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution, in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present application. And the aforementioned storage medium includes: a U-disk, a removable hard disk, a read-only memory (ROM), a random access memory (random access memory, RAM), a magnetic disk, or an optical disk, or other various media capable of storing program codes.
The foregoing is merely illustrative of the present application, and the present application is not limited thereto, and any person skilled in the art will readily recognize that variations or substitutions are within the scope of the present application. Therefore, the protection scope of the present application shall be subject to the protection scope of the claims.
Claims (6)
1. A method for improving the speed of a crop point search and the speed of a GPU, comprising the steps of:
Step one: converting the cut NURBS curved surface into a rational Bezier curved surface through node refinement;
step two: subdividing the Bezier curved surface into a plurality of sub-curved surfaces so as to meet the flatness requirement of the curved surface;
When the intersection point of the Bezier curved surface and the ray is calculated by using Newton iteration method, the Bezier curved surface is flat enough to provide a good initial estimated value close to the real intersection position, the original Bezier curved surface is subdivided into sub-curved surfaces according to the flatness standard, and the calculation is directly completed on the converted rational Bezier curved surface
Step three: shearing and removing the curved surface of the void by a trimming curve;
After creating the Bezier sub-surfaces, the system forms an axis aligned bounding box for each sub-surface, each sub-surface is defined by a control point, and the generated surface is positioned in a convex hull of the control point, so that the tight axis aligned bounding box on the control point also comprises the sub-surfaces, once the axis aligned bounding box is projected into the UV coordinate parameter space as a line segment, whether the sub-surfaces intersect with the 2D shape can be checked, and if the sub-surfaces do not intersect, the sub-surfaces are deleted from the sub-surface list;
step four: constructing a trimming data structure of each curved surface;
step five: constructing a global acceleration data structure for ray tracing of the tight bounding box of the sub-surface;
Various ray tracing measurement techniques are used, as GPUs can in principle use any valid data structure for ray tracing;
using a boundary body hierarchical structure with an axis alignment boundary frame, wherein the boundary body hierarchical structure is constructed by geometric median segmentation, firstly, the boundary body hierarchical structure is segmented along the longest axis, then, the boundary body hierarchical structure is segmented according to a circulation sequence, and finally, the boundary body hierarchical structure is optimized through interpolation;
step six: serializing all prepared data to an array buffer area and transmitting the data to a GPU memory;
step seven: ray tracing is performed on the constructed data structure.
2. The method for improving the crop point search speed and the GPU speed according to claim 1, wherein in the seventh step, the method comprises the following steps:
a. traversing a data structure for ray tracing on the GPU to a leaf containing a Bezier sub-surface;
b. calculating the intersection point of the ray and the Bezier sub-surface to obtain two-dimensional point coordinates (U, V) in the parameter space UV coordinates;
c checking two-dimensional points (U, V) on the clipping curve of the two-dimensional space.
3. A method of increasing the crop point search speed and GPU speed according to claim 2, wherein in step a, a plurality of ray tracing measurement techniques are used, since the GPU can in principle use any valid data structure for ray tracing;
The boundary body hierarchical structure with the axis alignment boundary box is used, the boundary body hierarchical structure is constructed by geometric median segmentation, the boundary body hierarchical structure is firstly segmented along the longest axis, then segmented according to a circulation sequence, and finally optimized through interpolation.
4. A method for increasing the speed of a cut point search and the speed of a GPU according to claim 3, wherein in step B, newton's iterative method is used to calculate the intersection of the ray with the unclamped Bezier subsurface, and for the underlying evaluation algorithm of the 3D point given a pair of (U, V) coordinates, an algorithm with complexity O (N 2) is used, which can increase the speed of the GPU by 20% -30%;
in the algorithm, firstly, a rational Bezier curve in a ternary is defined:
p(t)＝ΠP(t))
wherein:
in the above equation, P i＝bi(xi,yi,zi, w), the projection operator pi is defined as:
Π(x，y，z，w)＝(x/w，y/w，z/w)
the points and tangents to the curve can be found using the following formula structure:
P(t)＝(1-t)Q(t)+tR(t) (A)
wherein:
The straight line tangent to the curve in equation a can be found as:
q(t)-r(t)≡Π(Q(t))-Π(R(t))
the derivative of R (t) is:
the values of Q (t) and R (t) find the bernstein polynomial by pseudo-base conversion using a modified holner algorithm:
where u=t/(1-t), i＝0，1，...，n-1。
5. The method of claim 4, wherein if the curve is to be computed multiple times, the pre-computation is ignoredAnd part of nested multiplication:
N-1 multiplication and addition operations are performed on four coordinates of x, y, z, w, and post-multiplication (1-t) n-1 is not required because:
Thus, the point P (t) and its tangential direction can be calculated by multiplying 2n times and adding the coordinates for four x, y, z, w;
The method uses the following formula in interval 0.5-1:
wherein u= (1-t)/t;
A tensor product rational Bezier surface is defined as follows:
p(s，t)＝Π(P(s，t))
wherein:
p (s, t) can also be expressed by the following formula:
P(s，t)＝(1-s)(1-t)P00(s,t)+s(1-t)P10(s,t)+(1-s)tP01(s,t))+stP11(s，t)
wherein:
tangential vector P s (s, t) is parallel to the line:
Π((1-t)P00(s,t)+tP01(s,t))-Π((1-t)P10(s,t)+tP11(s，t))
tangential vector P s (s, t) is parallel to the line:
Π((1-s)P00(s,t)+tP10(s,t))-Π((1-s)P01(s,t)+sP11(s，t))
The hall algorithm for the tensor product surface is obtained by defining the following formula:
Wherein the method comprises the steps of N rows of four binary polynomials are multiplied and added m-1 times to calculate the components of each x, y, z, w, and the final value of t is multiplied and added n-1 times to the components of each x, y, z, w.
6. The method of claim 5, wherein if m-n, the four surfaces P 00(s,t)、P01(s,t)、P10 (s, t) and P 11 (s, t) are evaluated by multiplying n 2 -1 times and adding n 2 -1 times for each of the four x, y, z, w components, totaling 16n 2 -16 times and 16n 2 -16 times.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310417737.2A CN117893655B (en) | 2023-04-18 | 2023-04-18 | Method for improving search speed of clipping points and GPU speed |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202310417737.2A CN117893655B (en) | 2023-04-18 | 2023-04-18 | Method for improving search speed of clipping points and GPU speed |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN117893655A CN117893655A (en) | 2024-04-16 |
| CN117893655B true CN117893655B (en) | 2024-09-06 |
Family
ID=90641868
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202310417737.2A Active CN117893655B (en) | 2023-04-18 | 2023-04-18 | Method for improving search speed of clipping points and GPU speed |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117893655B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101539769A (en) * | 2009-04-28 | 2009-09-23 | 中国科学院数学与系统科学研究院 | Method for fitting and interpolating G01 code based on quadratic B spline curve |
| CN115453753A (en) * | 2022-09-23 | 2022-12-09 | 中国科学院长春光学精密机械与物理研究所 | High-precision ray tracing method and device for optical system based on NURBS surface |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8982121B2 (en) * | 2011-01-14 | 2015-03-17 | Dassault Systemes Solidworks Corporation | Direct rendering of CAD models on the GPU |
| CN108345744B (en) * | 2018-02-09 | 2019-02-01 | 西北工业大学 | A kind of cutter profile design space calculation method |
-
2023
- 2023-04-18 CN CN202310417737.2A patent/CN117893655B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101539769A (en) * | 2009-04-28 | 2009-09-23 | 中国科学院数学与系统科学研究院 | Method for fitting and interpolating G01 code based on quadratic B spline curve |
| CN115453753A (en) * | 2022-09-23 | 2022-12-09 | 中国科学院长春光学精密机械与物理研究所 | High-precision ray tracing method and device for optical system based on NURBS surface |
Also Published As
| Publication number | Publication date |
|---|---|
| CN117893655A (en) | 2024-04-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Von Funck et al. | Vector field based shape deformations | |
| Frisken et al. | Adaptively sampled distance fields: A general representation of shape for computer graphics | |
| Edmunds et al. | Surface-based flow visualization | |
| KR101265810B1 (en) | Triangulating procedural geometric objects | |
| US8537158B2 (en) | Parallel triangle tessellation | |
| US5774124A (en) | Finite element modeling method and computer system for converting a triangular mesh surface to a quadrilateral mesh surface | |
| KR100707841B1 (en) | Surface Deformation Apparatus Using 3D Target Curve and Its Method | |
| JP6734044B2 (en) | 3D modeled object defined by a grid of control points | |
| JP2016157429A (en) | Engraving 2d image on subdivision surface | |
| JPH0786885B2 (en) | Computer model system | |
| CN113077553A (en) | Three-dimensional model segmentation method based on surface attributes | |
| Azariadis et al. | Drawing curves onto a cloud of points for point-based modelling | |
| Hel-Or et al. | Relaxed parametric design with probabilistic constraints | |
| Kang et al. | Mesh-based morphing method for rapid hull form generation | |
| Breen et al. | 3d scan-conversion of CSG models into distance, closest-point and colour volumes | |
| Vyatkin | Method of binary search for image elements of functionally defined objects using graphics processing units | |
| CN117893655B (en) | Method for improving search speed of clipping points and GPU speed | |
| WO2023144676A1 (en) | Computer-implemented method for the simplification of a mesh of a three-dimensional graphical object | |
| Shah et al. | GPU-accelerated post-processing and animated volume rendering of isogeometric analysis results | |
| Nieser et al. | Patch layout from feature graphs | |
| Fayolle et al. | Rounding, filleting and smoothing of implicit surfaces | |
| Pasko et al. | Implicit curved polygons | |
| JP2008533614A (en) | System and method for generating matched contour profiles | |
| Mykhaylov et al. | 3D shape modeling using perturbation functions | |
| Liu et al. | High quality compatible triangulations for planar shape animation |
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 |