# Algebraic Point Projection for Immersed Boundary Analysis on Low Degree NURBS Curves and Surfaces
## 4 Methodology of Algebraic Point Projection
### Time Complexity of the Algebraic Point Projection Algorithm  
The generic pseudo-code of algebraic point projection for both NURBS curves and surfaces is listed in Algorithm 2. As can be seen in Algorithms 1 and 2, algebraic level sets (ALS) and algebraic point projection (APP) are closely connected. Algebraic level sets provide the closest Bezier segment for the first point projection, but also restrict the target curve or surface to be low degree \((p,q\leq 3)\) so as to avoid double points.  
The time complexity for Algorithm 2 is now presented for both curves and surfaces. Consider a NURBS curve of degree \(p\) or a NURBS surface of degree \(p\times q\), decomposing into \(n\) Bezier segments. For each step in finding the point projection, the time complexity is a function of the degree and is given in Table 3. As shown in Section 3.5, computing the algebraic level set at a point costs \(O(np^{3})\) time for a curve and \(O(np^{3}q^{3})\) time for a surface. Choosing the closest Bezier segment requires finding the minimum of the level sets of \(n\) Bezier segments and costs \(O(n)\) time. Projection in the physical space to the closest Bezier segment involves finding the gradient and Hessian of the Bezout/Dixon matrix, which requires the solution to a linear system (see Equations (21) and (22)). This costs \(O(p^{3})\) time for curves and \(O(p^{3}q^{3})\) time for surfaces. Point inversion to parametric coordinates requires  
Figure 14: Illustration of the second projection onto an adjacent Bézier surface segment if the first projection yields an out-of-span solution.  
solving a resultant system (Equations (30) and (34)), which also requires \(O(p^{3})\) time for curves and \(O(p^{3}q^{3})\) time for surfaces. Finally, the parametric coordinates of the Bezier segment are scaled and offset to obtain the parametric coordinates of the NURBS curve/surface. This can be done in \(O(1)\) time. Thus, the total time complexity of algebraic point projection is the same as that of computing the algebraic level sets, i.e., \(O(np^{3})\) for NURBS curves and \(O(np^{3}q^{3})\) for NURBS surfaces.  
```
0: NURBS curve or surface \(\mathbf{C}(\mathbf{u})\) and given point \(\mathbf{x}\)
0: Parameter \(\mathbf{u}_{f}^{N}\) of footpoint on NURBS entity \(\mathbf{C}\).
1:functionAlgebraic_Point_Projection(\(\mathbf{C},\mathbf{x}\))
2:\(\mathcal{B}(\mathbf{C})\leftarrow\) Split NURBS entity \(\mathbf{C}\) into a Bezier set with segments \(B_{i}\), \(i=1,2,\cdots,n\)
3:for\(i\gets 1,n\)do\(\triangleright\) Loops are independent, parallelization is possible
4:\(d_{i}\leftarrow\)Algebraic_Distance(\(B_{i},\mathbf{x}\))
5:endfor
6:\(\mathbf{x}_{f}\leftarrow\mathbf{x}-d_{B_{j}}(\mathbf{x})\mathbf{n}_{B_{j}( \mathbf{x})}\triangleright\)\(j=\arg\min_{i\in[1,n]}d_{i}\), and \(d_{B_{j}}\) is the distance to \(j\)th Bezier segemnt using 1 st or 2 nd order approximation, \(\mathbf{n}_{B_{j}(\mathbf{x})}\) is normal vector of \(d_{B_{j}}\)
7:\(\mathbf{u}_{f}^{B}\leftarrow\) Solve Equation (30) with \(\mathbf{M}^{B}(\mathbf{x}_{f})\) or Equation (34) with \(\mathbf{M}^{D}(\mathbf{x}_{f})\)
8:if\(\mathbf{u}_{f}^{B}\) is out of span then
9:\(\mathbf{u}_{f}^{B}\leftarrow\) Carryout the second projection based on Figure 12 or Figure 14
10:if Second projection is infeasible or \(\mathbf{u}_{f}^{B}\) is still out of span then
11:\(\mathbf{u}_{f}^{B}\leftarrow\) Compute corresponding parameter value on \(B_{j}\) boundary
12:endif
13:endif
14:\(\mathbf{u}_{f}^{N}\leftarrow\) Scale and offset \(\mathbf{u}_{f}^{B}\) based on knot span of \(\mathbf{C}\)
15:endfunction
```  
**Algorithm 2** Algebraic point projection algorithm.