# Stable Evaluation of 3D Zernike Moments for Surface Meshes
## 3 Algorithms for Computing the 3D Zernike Moments for a Surface Triangular Mesh
### Two Algorithms for Computing Zernike Moments
#### 3.5.2 Finite Precision Zernike Moments for Shapes Described by Surface Triangular Meshes  
While Algorithm 2 is deemed exact, it suffers from two major limitations. First, it requires quadrature rules with large strengths. Such rules include large number of sampling points, leading to an overall time complexity \(O(M\times N^{5})\). Quadrature rules, however, are known to converge fast. As such, it is often not necessary to go to the maximum strength that is required for an exact computation. If we are willing to accept a finite precision, a more efficient procedure can be derived, as described in Algorithm 4. Briefly, the Zernike moments \(c_{nl}^{m}\) over a triangle \(T\) are evaluated over quadrature rules of increasing strengths. When the difference between those Zernike moments computed over two successive rules falls below a tolerance, the quadrature is deemed to have converged and the computation stops. ```
procedureINFO=TRIANGLEADAPT(\(N\), \(A,B,C,TOL\)) Input:\(N\): The maximum order for the 3D Zernike moments. \(A,B,C\): The three vertices defining the triangle. The tolerance TOL for finite precision computation. Initialize:\(c_{nl}^{m}(\text{old})=0\) for\(R\in\{R_{3},\ldots,R_{1}\}\)do (1) Compute \(c_{nl}^{m}(R)=\text{TRIANGLE}(N,A,B,C,R)\) (2) Compute \(\text{err}=||c_{nl}^{m}(R)-c_{nl}^{m}(\text{old})||\) (3) If \(\text{err}<\text{TOL}\), break (4) Set \(c_{nl}^{m}(\text{old})=c_{nl}^{m}(R)\) endfor (5) If \(\text{err}<\text{TOL}\), set INFO = true, otherwise INFO = false. Output: INFO, and the current Zernike moments \(c_{nl}^{m}(R)\) associated with triangle \((A,B,C)\). endprocedure
```  
**Algorithm 4**_Adaptive computation of Zernike moments associated with one triangle of a surface mesh_  
There is a second limitation of Algorithm 1 that remains a problem for Algorithm 4: if the strongest quadrature rule (in our case, 101) is not enough to compute the Zernike moments exactly or to reach the desired tolerance, the algorithms fail. It is expected that the quadrature strength needed to compute correctly the Zernike moments for a tetrahedron \((O,A,B,C)\) is related to the size of the corresponding triangle \((A,B,C)\). To verify this assumption, we performed the following experiment. We considered 8 different discrete spheres represented with a triangular surface mesh. The first mesh corresponds to an icosahedron, while the following meshes are generated consecutively by successive subdivisions of all triangles of the previous mesh. All those meshes are scaled so that they fit within the unit ball, with a maximum radius of 0.75. We applied algorithm TRIANGLEADAPT to all facets of all those meshes, and compared the maximum order on exit of the procedure to the surface area of the corresponding triangle. Results are shown in Figure 4.  
Figure 4 shows that the larger the triangle, the higher the strength of the quadrature. This result hints to a simple procedure to alleviate the second problem described above: if the procedure TRIANGLEADAPT fails, split the triangle into four smaller triangles, possibly recursively. We have implemented this procedure in Algorithm 5. ```
procedureTRIANGLEREC(\(N,A,B,C,TOL\)) Input:\(N\): The maximum order for the 3D Zernike moments. \(A,B,C\): The three vertices defining the triangle. The tolerance TOL for finite precision computation. (1) Compute (INFO, \(c_{nl}^{m}(T)=\)TRIANGLEADAPT(\(N,A,B,C,TOL\)) ifINFO==true then (2) RETURN \(c_{nl}^{m}(T)\) else (3) Find \(A^{\prime},B^{\prime},C^{\prime}\) the middle points of segment \(BC\), \(AC\), \(CA\) (4) Compute (a) \(c_{nl}^{m}(1)=\)TRIANGLEREC(\(N,A,C^{\prime},B^{\prime},TOL\)) \(c_{nl}^{m}(2)=\)TRIANGLEREC(\(N,B,A^{\prime},C^{\prime},TOL\)) \(c_{nl}^{m}(3)=\)TRIANGLEREC(\(N,C,B^{\prime},A^{\prime},TOL\)) \(c_{nl}^{m}(4)=\)TRIANGLEREC(\(N,A^{\prime},B^{\prime},C^{\prime},TOL\)) (5) RETURN \(c_{nl}^{m}(T)=c_{nl}^{m}(1)+c_{nl}^{m}(2)+c_{nl}^{m}(3)+c_{nl}^{m}(4)\).