# Algebraic Point Projection for Immersed Boundary Analysis on Low Degree NURBS Curves and Surfaces
## 4 Methodology of Algebraic Point Projection
### Algebraic Point Projection for a NURBS Curve
#### 4.1.1 First Order Algebraic Point Projection in Physical Space  
From Equation (14), the gradient of the normalized approximate distance function to a Bezier segment is derived as:  
\[\
abla d=\left(\mathbf{I}-\frac{\Gamma}{\left\|\
abla\Gamma\right\|^{2}} \mathbf{H}\right)\frac{\
abla\Gamma}{\left\|\
abla\Gamma\right\|} \tag{19}\] \begin{table}
\begin{tabular}{l c c} \hline \hline \multirow{2}{*}{**Step**} & \multicolumn{2}{c}{**Time Complexity**} \\ \cline{2-3}  & **Curve** & **Surface** \\ \hline Convex hull construction & \(O(p\log(p))\) & \(O(pq\log(pq))\) \\ Distance field of convex hull & \(O(p)\) & \(O(pq)\) \\ Computing Dixon resultant & \(O(p^{3})\) & \(O(p^{3}q^{3})\) \\ Normalization of resultant & \(O(p^{3})\) & \(O(p^{3}q^{3})\) \\ Trimming operation & \(O(1)\) & \(O(1)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Time complexity of each step in Algorithm 1 for computing the algebraic level sets for a Bézier segment. Time complexities are listed for Bézier curves of degree \(p\) and Bézier surfaces of degree \(p\times q\). where \(\mathbf{I}\) is the identity matrix and \(\mathbf{H}\) is the Hessian of function \(\Gamma(\mathbf{x})\). Using the above gradient, the physical footpoint \(\mathbf{x}_{f}\) can now be approximately located as:  
\[\mathbf{x}_{f}=\mathbf{x}-d\,\frac{\
abla d}{\|\
abla d\|} \tag{20}\]  
To calculate \(d\) and \(\
abla d\) using Equations (14) and (19), it would appear at first glance as though \(\Gamma\), \(\
abla\Gamma\), and \(\mathbf{H}\) need to be evaluated for every test point. However, the following derivation as well as procedural detail show that \(d\) and \(\
abla d\) can be computed efficiently without explicitly calculating \(\Gamma\), \(\
abla\Gamma\) or \(\mathbf{H}\). One can express \(\
abla\Gamma\) and \(\mathbf{H}\) in terms of Bezout matrix \(\mathbf{M}^{B}\) and its components \(\mathbf{M}_{x}^{B}\) and \(\mathbf{M}_{y}^{B}\) (the superscript \(B\) is dropped in the following for ease of reading):  
\[\
abla\Gamma =|\mathbf{M}| \begin{bmatrix}\text{tr}\left(\mathbf{M}^{-1}\frac {\partial}{\partial x}\mathbf{M}\right)\\ \text{tr}\left(\mathbf{M}^{-1}\frac{\partial}{\partial y}\mathbf{M}\right) \end{bmatrix} =|\mathbf{M}| \begin{bmatrix}\text{tr}\left(\mathbf{M}^{-1} \mathbf{M}_{x}\right)\\ \text{tr}\left(\mathbf{M}^{-1}\mathbf{M}_{y}\right)\end{bmatrix} =\Gamma \tilde{\mathbf{g}} \tag{21}\] \[\mathbf{H} =|\mathbf{M}| \begin{bmatrix}\text{tr}^{2}\left(\mathbf{M}^{-1} \mathbf{M}_{x}\right)&\text{tr}\left(\mathbf{M}^{-1}\mathbf{M}_{x}\right) \text{tr}\left(\mathbf{M}^{-1}\mathbf{M}_{y}\right)\\ -\text{tr}\left(\left(\mathbf{M}^{-1}\mathbf{M}_{x}\right)^{2}\right)&-\text{ tr}\left(\left(\mathbf{M}^{-1}\mathbf{M}_{x}\right)\left(\mathbf{M}^{-1} \mathbf{M}_{y}\right)\right)\\ \text{tr}\left(\mathbf{M}^{-1}\mathbf{M}_{y}\right)\text{tr}\left(\mathbf{M}^ {-1}\mathbf{M}_{x}\right)&\text{tr}^{2}\left(\mathbf{M}^{-1}\mathbf{M}_{y} \right)\\ -\text{tr}\left(\left(\mathbf{M}^{-1}\mathbf{M}_{y}\right)\left(\mathbf{M}^{-1 }\mathbf{M}_{x}\right)\right)&-\text{tr}\left(\left(\mathbf{M}^{-1}\mathbf{M} _{y}\right)^{2}\right)\end{bmatrix} =\Gamma\tilde{\mathbf{H}} \tag{22}\]  
where \(\tilde{\mathbf{g}}\) and \(\tilde{\mathbf{H}}\) are the vector/matrix multiplying \(|\mathbf{M}|\) in the above equations, respectively. Substituting Equations (21) and (22) back into Equations (14) and (19), one obtains:  
\[d =\frac{1}{\|\tilde{\mathbf{g}}\|} \tag{23}\] \[\
abla d =\frac{\tilde{\mathbf{g}}}{\|\tilde{\mathbf{g}}\|}-\frac{\tilde{ \mathbf{H}}\tilde{\mathbf{g}}}{\|\tilde{\mathbf{g}}\|^{3}} \tag{24}\]  
The efficiency of algebraic point projection in two-dimensional physical space is summarized as follows:  
1. Component matrices \(\mathbf{M}_{x}\), \(\mathbf{M}_{y}\), and \(\mathbf{M}_{w}\) are constant for a given rational parametric curve. Therefore, they can be pre-computed and repeatedly used at a point \(\mathbf{x}\). 2.