# Optimal Intersection Curves for Surfaces

Authors: Jiwen Gao; Faiza Sarfraz; Misbah Irshad; Jia-Bao Liu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this article, an algorithm has been established to approximate parametric-parametric, explicit-implicit, and explicit-explicit surface intersection. Foremost, it extracts the characteristic points (boundary and turning points) from the sequence of intersection points and fits an optimal cubic spline curve to these points. Moreover, this paper utilizes genetic algorithm (GA) for optimization of shape parameters in the portrayal of cubic spline so that the error is minimal. The proposed algorithm is demonstrated with different types of surfaces to analyze its robustness and proficiency. In the end, all illustrations show the effectiveness of the algorithm which makes it more influential to resolve all complexities arises during intersection with a minimal error.


---

## Body

## 1. Introduction

Surface/surface intersection (SSI) has enormous applications in diverse fields while dealing with two surfaces/curves’ intersection problems. It is a fundamental ingredient in computer graphics to develop different shapes of ultrasonic machines (3D images from ultrasonic machines can be joined with CAD images for good results), airplanes, architecture designs, etc., via a variety of surfaces. With the advancement in 3D technologies, such as in laser scanning, one can scan more precisely even at a significant distance. Similarly, in engineering, curve of intersection (COI) is achieved by the intersection of different solids such as prism-prism, prism-cone, and cone-cone. It deals with complex mathematical geometry which arises in designing of automotive at large scale. A huge collection of work, extending back quite a few years, addresses the issues related to SSI. This is still an important issue in industrial engineering and mathematical fields. Usually, nonempty intersection intends to find an error bound for approximation of intersection curves, see, for example, [1–5] and references therein.The algorithm proposed in [6] focused on evaluating intersection curves of rational polynomial parametric surface patches, which is based on a validated ordinary differential equation system solver. Later on, they emphasized on the marching method [7] for solving problems which offer remarkable advantages, but still their approach is facing some problems because of complicated initial and boundary values. In the same way, an approach in [8] worked on solving differential geometry problems of hypersurfaces; also, they are doing this research [9] by increasing dimensions of surfaces which take more time for showing results. Extracting boundary and turning points of parametric surface intersection curves by the GK method are discussed in [10, 11]. Their topology is still confronting problems of error that come up through surface intersection. Also, the methodology in [12] is used for finding characteristics points, but excess of points are calculated for appropriate results.Explicit and implicit surfaces are not extensively used in a variety of fields, but researchers did remarkable work whatever the circumstances occurred during research. In the medical field, scientists used an explicit surface-based method for the cortical thickness of the brain [13]; still, they are doing their work on that purpose. In CAD, hybrid models can be merged with explicit models [14] for removing ambiguities and getting better graphic results. The problems occurring in ocean-free surface models can be solved explicitly or implicitly. In explicit surfaces, scaling behavior on parallel systems is better than implicit schemes [15] because baro-clinic time steps are used in implicit surfaces and are larger than the time-stepping scheme in explicit surfaces.Collectively, methods involving implicit surfaces are quite diffusive because global communication in each iteration makes the method’s scale poorer; while explicit surface methods have flexibility to resolve all possible difficulties during the iteration process. The combination of these surfaces is good for intersection because if one surface is creating some problem during intersection the other may overcome the situation.Soft computing behavior such as computational intelligence, is a blend of different techniques such as fuzzy logic [16], simulated annealing, genetic algorithm, numerical technics [17], etc., whose objective is to solve computational problems which is based on natural evolution theory [18], which is not easily demonstrated numerically. In this research work, a genetic algorithm is utilized, which is useful in getting optimal outcomes.While a lot of work has been done on SSI issues, still there is hardly any established algorithm which can deal intersection of all types of surfaces. Each approach that was discussed in the previous section has its own disadvantages and limits. This motivated us to develop an optimal technique using genetic algorithm and cubic spline function, which can be used to approximate intersections of wider range of surfaces. The technique proposed in this paper works equally well to approximate intersection curves for following three cases of intersection of surfaces:1
Intersection of two explicit surfaces2
Intersection of one implicit and one explicit surface3
Intersection of two parametric surfacesThis paper is organized as follows. Section2 includes the materials and methods of proposed approach. Genetic algorithm is discussed in Section 3. Results and discussion is given in Section 4. This paper is concluded in Section 5.


## 2. Materials and Methods

The proposed approach takes two surfaces as input. These surfaces may consist of two explicit surfacess1 and s2 in R3, which are defined as(1)s1:a1=G1x,y:a=x=b,c=y=d,s2:a2=G2x,y:a=x=b,c=y=d,where a,b,c,d∈R.One implicit and one explicit surfaceh1 and h2 are represented by(2)h1:K1x,y,z=0:a=x=b,c=y=d,e=z=f,h2:z=K2x,y:a=x=b,c=y=d,e=z=f,where a,b,c,d,e,f∈R.Two parametric surfacesz1 and z2in R3 are denoted as(3)z1=F1xs,t,ys,t,zs,t:a=s=b,c=t=d,z2=F2xr,w,yr,w,zr,w:a=r=b,c=w=d,where a,b,c,d∈R.In order to find sequence of intersection points of all above surfaces, the solution of the following equations is required, respectively:(4)a1−a2=0,z−K1x,y,z=0,F1−F2=0.Additionally, its nonempty intersection contains isolated sequence points and curves of intersected pieces.


### 2.1. Characteristic Points

Characteristic points are the subset of the sequence of intersection points which helps to identify the shape of intersection curves, including all the turning and boundary points.


#### 2.1.1. Boundary Points

The boundary points can be determined by imposing the following conditions:x=a,x=b,y=c, y=d, z=e, and z=f in equation (4).


#### 2.1.2. Turning Point

A point where curve changes its direction or where intersected curve makes a sharp turn is called turning point. The turning points can be estimated by finding(i)
The inflection point of equation (4)(ii)
The points where curve (4) has slope 0, 1, or −1(iii)
Where the function changes its curvature(iv)
When derivative changes its sign


### 2.2. Cubic Spline Interpolant

Cubic spline function [19] is used to fit the curve at the points obtained in the previous section. Let Fi and Fi+1, i=1,2,…,n−1, be distinct characteristic points. Moreover, the slope of tangent associated to these points is denoted by Di,Di+1, and vi and wi are shape control parameters. Then, the cubic function is considered as(5)Pit=Ui1−t3+3Vi1−t2t+3Wi1−tt2+Xit3,hi=ti+1−ti,i=1,2,…,n−1,satisfying the following properties:(6)Pti=Fi,Pti+1=Fi+1,P1ti=viDi,P1ti+1=wiDi+1,where P1 denotes first derivative with respect to t, which yields interpolating conditions as(7)Ui=Fi,Xi=Fi+1,Vi=Fi+hiDivi3,Wi=Fi+1−hiDi+1wi3.So,Pit takes the form:(8)Pit=Fi1−t3+3fi+hiDivi31−t2t+3fi+1−hiDi+1wi31−tt2+Fi+1t3.The above equation can be rewritten as(9)Pit=R0,itFi+R1,itVi+R2,itWi+R3,itFi+1,where R0.i=1−t3, R1,i=3t1−t2, R2,i=3t21−t, and R3,i=t3.The functionsRj,i,j=0,1,2,3, are like Bernstein Bezier basis functions such that(10)∑j=03Rj,it=1.Two cases of optimal intersection curve are discussed below.In order to achieve optimal curve fitted to characteristic points, the sum of squares of distances between data (intersection) pointsPi,j′=xi,j,yi,j and approximated points using cubic spline Ptj should be minimized, i.e.,(11)Si=∑j=1miPiti,j−Pi,j′2,i=1,2,…,n,where chord length parameterization which is used for parameter t needs to be minimized.In this procedure, such values of the shape control parametersvi and wi must be chosen with the help of genetic algorithm so that Si (equation (11)) is minimal and the following two cases may arise to do so.Case 1.
vi=wi
Shape parameters are taken as equal in this case, so the objective function (11) depends on one variable only.Case 2.
vi≠wi
Shape parameters are not taken as equal in this case. The process of finding the best curve is the same as above by taking objective function (11) as a function of two variables.
Moreover, in this paper, results are obtained using case 2 as case 1 is special case of case 2.


## 2.1. Characteristic Points

Characteristic points are the subset of the sequence of intersection points which helps to identify the shape of intersection curves, including all the turning and boundary points.


### 2.1.1. Boundary Points

The boundary points can be determined by imposing the following conditions:x=a,x=b,y=c, y=d, z=e, and z=f in equation (4).


### 2.1.2. Turning Point

A point where curve changes its direction or where intersected curve makes a sharp turn is called turning point. The turning points can be estimated by finding(i)
The inflection point of equation (4)(ii)
The points where curve (4) has slope 0, 1, or −1(iii)
Where the function changes its curvature(iv)
When derivative changes its sign


## 2.1.1. Boundary Points

The boundary points can be determined by imposing the following conditions:x=a,x=b,y=c, y=d, z=e, and z=f in equation (4).


## 2.1.2. Turning Point

A point where curve changes its direction or where intersected curve makes a sharp turn is called turning point. The turning points can be estimated by finding(i)
The inflection point of equation (4)(ii)
The points where curve (4) has slope 0, 1, or −1(iii)
Where the function changes its curvature(iv)
When derivative changes its sign


## 2.2. Cubic Spline Interpolant

Cubic spline function [19] is used to fit the curve at the points obtained in the previous section. Let Fi and Fi+1, i=1,2,…,n−1, be distinct characteristic points. Moreover, the slope of tangent associated to these points is denoted by Di,Di+1, and vi and wi are shape control parameters. Then, the cubic function is considered as(5)Pit=Ui1−t3+3Vi1−t2t+3Wi1−tt2+Xit3,hi=ti+1−ti,i=1,2,…,n−1,satisfying the following properties:(6)Pti=Fi,Pti+1=Fi+1,P1ti=viDi,P1ti+1=wiDi+1,where P1 denotes first derivative with respect to t, which yields interpolating conditions as(7)Ui=Fi,Xi=Fi+1,Vi=Fi+hiDivi3,Wi=Fi+1−hiDi+1wi3.So,Pit takes the form:(8)Pit=Fi1−t3+3fi+hiDivi31−t2t+3fi+1−hiDi+1wi31−tt2+Fi+1t3.The above equation can be rewritten as(9)Pit=R0,itFi+R1,itVi+R2,itWi+R3,itFi+1,where R0.i=1−t3, R1,i=3t1−t2, R2,i=3t21−t, and R3,i=t3.The functionsRj,i,j=0,1,2,3, are like Bernstein Bezier basis functions such that(10)∑j=03Rj,it=1.Two cases of optimal intersection curve are discussed below.In order to achieve optimal curve fitted to characteristic points, the sum of squares of distances between data (intersection) pointsPi,j′=xi,j,yi,j and approximated points using cubic spline Ptj should be minimized, i.e.,(11)Si=∑j=1miPiti,j−Pi,j′2,i=1,2,…,n,where chord length parameterization which is used for parameter t needs to be minimized.In this procedure, such values of the shape control parametersvi and wi must be chosen with the help of genetic algorithm so that Si (equation (11)) is minimal and the following two cases may arise to do so.Case 1.
vi=wi
Shape parameters are taken as equal in this case, so the objective function (11) depends on one variable only.Case 2.
vi≠wi
Shape parameters are not taken as equal in this case. The process of finding the best curve is the same as above by taking objective function (11) as a function of two variables.
Moreover, in this paper, results are obtained using case 2 as case 1 is special case of case 2.


## 3. Genetic Algorithm

As cubic spline has two parametersvi and wi, in case of achieving optimal values of v and w, a soft computing technique, i.e., genetic algorithm (GA) [18] is used. Genetic algorithm is one of the powerful evolutionary-based optimization technique to tackle complicated optimization problems. It forms adaptive patterns of searching, based on natural genetics and designs of natural selection. Natural evolution process works under some genetic operators (selection, crossover, and mutation). This procedure moves from one parent population (chromosomes) to another by using genetic operators where every chromosome consists of more than one bit strings. Selection operator helps selecting chromosome which allowed to reproduce and would die out. Crossover operator generates new chromosomes by exchanging some area of two bit strings (chromosomes) mutually. Mutation operator disseminates some new characteristics among the bit strings for more variety of chromosomes. Figure 1 shows an example of crossover and mutation operator for some particular choice of chromosomes.Figure 1
Execution of crossover and mutation operator.GA does not need any lengthy mathematical formulation for better results and rise as a significant technique which solves complex problems in short time with appropriate results. GA choses random values of the parametersvi,wi from certain population and application of iterated process of GA along with genetic operators, selection, mutation, and crossover which specifically fit the optimal curve to intersection points by finding optimal values of shape control parameters vi,wi.For best curve fitted to given data, those values of shape parameters are required, for which the sumsSi should be minimized. GA is used to optimize the values of parameters which help in minimizing the error.In literature, different methods are used for finding the error. The error occurs when approximated points do not lie on the exact location. The error calculated by the proposed technique in this paper is shown in Tables1–3. The minimized error gives best approximated curve which shows the efficiency of the proposed approach. Table 4 displays values of parameters which are used for GA.Table 1
Iterative values with characteristic points of Example1.
SPVTE (seconds)E (SSE)TOIPCP1st iterationv=0.22w=0.310.0470.02941762(–1.85,–0.39)(0.19, 0.82)(–0.15,–0.39)(2, 1.77)(–2, 0.5)2nd iterationv=0.41w=0.560.0390.00572Optimal curvev=0.9w=0.90.0236.7×10−5Table 2
Iterative values with characteristics points of Example2.
SPVTE (seconds)E (SSE)TOIPCP1st iterationv=1.06w=1.170.1240.00365217(0, 1.249, 1.562)(0, −1.249, 1.562)(1.249, 0, –1.562)(–1.249, 0, –1.562)(1.414, 1.414, 0)(–1.414, –1.414, 0)(1.414, –1.414, 0)(–1.414, 1.414, 0)2nd iterationv=1.22w=1.340.0860.00021Optimal curvev=3.82w=3.82  =  3.820.1351.1×10−7Table 3
Iterative values with characteristics points of Example3.
SPVTE (seconds)E (SSE)TNIPCS1st iterationv=1.49(1/3, 1/3)w=1.560.0490.0169167(0.993, 0.284)2nd iterationv=1.67w=1.770.0520.00021Optimal curvev=2.99w=2.990.0471.8×10−8Table 4
Parameters utilized for GA.
Sr. no.NameValues1Population size25–302Genome length153Selection rate0.54Mutation rate0.01


### 3.1. Proposed Algorithm Steps

The overall proposed scheme can be described in the form of an algorithm.Step 1: input surface dataStep 2: find intersection of surfaces by the method mentioned in Section2Step 3: extract the characteristics points through criteria given in Section2Step 4: fit the spline curve to the points attained in Step 3Step 5: compute the best optimal value of parametersv and w by using GAStep 6: if the optimal curve has been accomplished in Step 5, then go to Step 7, otherwise go to Step 4 and repeat these steps until the desired optimal curve is achievedStep 7: Stop


## 3.1. Proposed Algorithm Steps

The overall proposed scheme can be described in the form of an algorithm.Step 1: input surface dataStep 2: find intersection of surfaces by the method mentioned in Section2Step 3: extract the characteristics points through criteria given in Section2Step 4: fit the spline curve to the points attained in Step 3Step 5: compute the best optimal value of parametersv and w by using GAStep 6: if the optimal curve has been accomplished in Step 5, then go to Step 7, otherwise go to Step 4 and repeat these steps until the desired optimal curve is achievedStep 7: Stop


## 4. Results and Discussion

The execution of proposed approach on intersection of explicit-explicit, implicit-explicit, and parametric-parametric surfaces has been shown in the following examples.Example 1.
Two explicit surfaces are given by(12)s1:z=y2+2x|0≤x,y≤1,s2:z=2y3−x2|0≤x,y≤1.
Both explicit surfaces are shown in Figures2 and 3. Figure 4 depicts intersection of surfaces, while Figure 5 epitomizes the xy-view of intersection along with boundary and turning points which extracted through criteria given in Section 2. Approximation of sequence of points is displayed in Figure 6. Figures 7 and 8 show how cubic spline is used to fit the curve through 1st and 2nd iterations of GA. The best optimal curve is given in Figure 9 and achieved in 20th iteration of GA.Figure 2
Explicit surface 1.Figure 3
Explicit surface 2.Figure 4
Intersection of both surfaces.Figure 5
xy-view of intersection along with boundary and turning points.Figure 6
Sequence of points.Figure 7
Cubic spline fitted for 1st iteration of GA.Figure 8
Cubic spline fitted for 2nd iteration of GA.Figure 9
Best optimal curve achieved.Example 2.
Implicit and explicit surfaces are given by(13)s1:x2+y2+z2=4|0≤x,y,z≤1,s2:−x2+y2=z|0≤x,y,z≤1.
Explicit and implicit surfaces are displayed in Figures10 and 11. Figure 12 portrays intersection of surfaces, while Figure 13 denotes the xy-view of intersection along with boundary and turning points which are extracted through criteria given in Section 2. Approximation of sequence of points is publicized in Figure 14. Figures 15 and 16 represent how cubic spline is used to fit the curve through 1st and 2nd iterations of GA. The best optimal curve is shown in Figure 17 and obtained after 24th iteration of GA.Figure 10
Implicit surface.Figure 11
Explicit surface.Figure 12
Intersection of both surfaces.Figure 13
xy-view of intersection along with boundary and turning points.Figure 14
Sequence of points.Figure 15
Cubic spline fitted for 1st iteration of GA.Figure 16
Cubic spline fitted for 2nd iteration of GA.Figure 17
Best optimal curve achieved.Example 3.
Two parametric surfaces with parametersx,y are given by(14)s1:3x,3y,18xyx−1y−1|0≤x,y≤1,s2:3x+1,−18x3y2+18x3y+27x2y2−27x2y−9xy2+9xy+1,3y−1|0≤x,y≤1.
Both parametric surfaces are shown in Figures18 and 19. Figure 20 illustrates intersection of surfaces, while Figure 21 demonstrates the xy-view of intersection along with boundary and turning points which extracted through criteria given in Section 2. Approximation of sequence of points is shown in Figure 22. Figures 23 and 24 exemplify how cubic spline is used to fit the curve through 1st and 2nd iterations of GA. The best optimal curve is depicted in Figure 25 and produced in 31st iteration.
Some randomly selected values of shape parameters by GA and characteristics points of Example1–3 are shown in Tables 1–3. In these tables, CS denotes characteristics points, TNIP denotes the total number of intersection points, E denotes the error, TE denotes time elapsed, and SPV denotes shape parameter values.Figure 18
Implicit surface.Figure 19
Explicit surface.Figure 20
Intersection of both surfaces.Figure 21
xy-view of intersection along with boundary and turning points.Figure 22
Sequence of points.Figure 23
Cubic spline fitted for 1st iteration of GA.Figure 24
Cubic spline fitted for 2nd iteration of GA.Figure 25
Best optimal curve achieved.


## 5. Conclusion

A new scheme together with a genetic algorithm has been introduced to approximate surface to surface (parametric-parametric, explicit-implicit, and implicit-implicit) intersection curves. Characteristics points are evaluated from sequence points of surface intersection and fit optimal curve using cubic spine. Finest shape parameter values in cubic spline are selected by genetic algorithm. Moreover, it does not include any extra points for approximation. Finally, the optimal outcomes from the proposed technique suggested that it is more reliable scheme with GA in order to overcome surface intersection problems.



---

*Source: 9945984-2021-08-17.xml*