# Filling Holes in Triangular Meshes of Plant Organs

Zhihui Sun, Xinyu Guo, Shenglian Lu, Weiliang Wen, Youjia Chen

► To cite this version:

Zhihui Sun, Xinyu Guo, Shenglian Lu, Weiliang Wen, Youjia Chen. Filling Holes in Triangular Meshes of Plant Organs. 7th International Conference on Computer and Computing Technologies in Agriculture (CCTA), Sep 2013, Beijing, China. pp.222-231, 10.1007/978-3-642-54341-8_23. hal-01220831

HAL Id: hal-01220831

https://inria.hal.science/hal-01220831

Submitted on 27 Oct 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Filling Holes in Triangular Meshes of Plant Organs

Zhihui Sun¹, Xinyu Guo¹,*, Shenglian Lu¹, Weiliang Wen¹, Youjia Chen¹

¹Beijing Research Center for Information Technology in Agriculture, Beijing 100097, China

*Corresponding author. E-mail address: guoxy@nercita.org.cn

**Abstract.** Data missing was always when scanning plant organs by using 3D laser scanner, and this could lead to holes appearing in the mesh surface generated from the scanned point cloud. Basing on the analyzing to the geometrical features of different types of plant organs, a hole-filling algorithm was proposed which based on the normal vector of the mesh to make the repair area as close as possible to the original model of the organs mesh. The algorithm firstly extracts the hole boundary in the surface mesh, and compute the positions of new points based on the normal vector and normal curvature of the mesh boundary, then connects the new points and boundary points to generate a new triangular mesh. Experiments on different plant organs of geometric shapes were taken and new triangular mesh qualities were evaluated. Results show that the algorithm can fill holes in several kinds of scanned plant organs mesh quickly and efficiently.

**Keywords:** mesh surface, hole-filling, normal vector estimation, normal curvature, plant organs

## 1 Introduction

With the maturity of three-dimensional (3D) laser scanning technology and the popularity of related equipment, the researches of 3D reconstruction from scanned point cloud has became spotlight in recent years. For the measurement of plant morphology, traditional manual method for data collection has shortcomings, such as low speed, low accuracy of the measured data and so on. On the other hand, the 3D laser scanner can measure any object in non-touch approach in the advantages of high scanning speed, real-time, high accuracy etc. [1]. As such laser scanner has been used more and more frequently for plant modeling in recent years. The reconstructed plant model based on 3D laser scanned data not only can present real plant morphology, but also provide accurate structural model for the calculation of plant physiological function, and also has important impact on the display and outreach of the new variety. However, due to the complex in the structural system of plant, such as shelter between organs and the complex optical property of organ surface, the quality of measured data by using 3D scanner could be easily interrupted, result in the data missing and formation of holes in the constructed 3D model of plant organs. This will bring difficulty for further analysis such as calculating area and volume of the plant organ, finite element analysis, textures etc. Therefore, the hole-filling work is very important in 3D plant modeling based on the laser scanning technology.
Many works have been done in hole-filling. Davis *et al.* [2] applied the voxel diffusion to fill the holes, and displayed the mesh model using MC (Marching Cube) algorithm. The application of this algorithm could get good results in hole-filling, but its shortcoming is that the original mesh model was changed. Liepa [3] performed triangulation to the hole and adjusted the new vertices to make the new mesh matching the original one. Wei *et al.* [4] presented a method which firstly filled the holes, then refined and optimized the hole area to get new points inside the hole, and finally fitted the weighted points to create the surface. The new mesh could be adjusted by adjusting inside points of the hole. Zhang *et al.* [5] performed triangulation to the hole and refined it and adjusted its geometry by few times of iteration. In short, all above methods were based on the mesh refinement, which firstly mesh the hole, then adjust the new mesh in order to match the whole mesh model. The difference among them is the application of the algorithms to adjust the new mesh.

Zhao *et al.* [6] combined wave front method and Poisson equation to adjust the vertices of the new mesh. Similarly Wang *et al.* [7] combined wave front method and normal of boundary with Laplacian coordinate to fill the holes. Du *et al.* [8-9] applied RBF to fill the holes, without considering the consistency of the morphology between the hole and surrounding regions. Qian *et al.* [10] suggested a mesh-repairing algorithm through recovering the missing sharp features. The edges and corners of the sharp features could be obtained through establishing parabola functions around the sharp features, then filled the holes using the extend Marching Cube algorithm. Levy [11] flattened the whole mesh model to fill the holes. But the algorithm has low efficiency if the hole is much smaller than the whole mesh. Brunton *et al.* [12] flatten the hole boundary into the reference plane to fill the holes, then embed back to the spatial mesh.

The above algorithms can obtain good results while repairing flat areas and small holes. However, due to the complex and diverse morphology of plant organ, the mesh-repairing for plant organ is still a difficult task to address. This paper proposed a filling hole algorithm by modifying the traditional repairing method with considering the curvature of the surface as the constraint, which is more suitable to the surface mesh-repairing of complex plant organ. In the proposed algorithm, the mesh hole boundaries were extracted and the angles between the adjacent boundary edges were calculated. Then the positions of the new points were calculated according to the bisector, the normal vector and the vertex curvature direction. Finally the adjacent vertices were connected to finish the mesh-repairing.

## 2 Filling Holes Method

Our proposed filling holes method includes four steps. Based on an input triangular mesh model, the method firstly finds holes and extracts the boundary of each hole. Then the normal vector of hole boundary was estimated, and the boundary angle was calculated. These information were used at the last step for generating new points to fill the hole.
## 2.1 Extracting the boundary of mesh hole

For the triangular mesh model $M = (V, F, E)$, in which $V, F, E$ indicates the set of vertex, surface and edge, respectively. If $M$ is a closed mesh, the boundary edge of a hole in the mesh should belong to only one triangle. So the boundary edge could be found by traversing the whole mesh in this principle. If $M$ is a non-closed mesh, due to the non-closed mesh has its own boundary, when detecting the hole boundary, one edge of the hole should be interactively selected so as to traverse the whole mesh to find its adjacent edge. The detailed explanation of the algorithm is in reference [13]. This work applied interactive approach to select the boundary triangles. The procedures of the algorithm were as follows:

1) interactively selecting one hole triangle $F$; finding the edge $E$ which belong to only one triangle (assumed the two vertices of $E$ are $v_1$ and $v_2$) as the first hole edge; adding $v_1$ and $v_2$ into array $V$, which includes vertices of boundaries.

2) searching the boundary of the hole along edge $E$ from $v_1$ or $v_2$; traversing the whole triangle mesh from $v_2$ to find the set of edge connected with the hole boundary. Traversing the set of edge to find the edge belong to only one triangle as the adjacent hole edge $E'$; adding the vertices of $E'$ into $V$; deleting duplicate vertices.

3) if one vertex in $E'$ is $v_1$, then stop searching, else, follow step 2 to continue searching the vertex of the hole boundary.

## 2.2 Estimating the normal vector of hole boundary

The normal estimation of vertex on the mesh usually use a normal weighted average on 1-ring of the vertex, the simplest weighted way is area weighted. This method is relative accurate for the estimation of the normal vector for the vertex inside the mesh. But for the boundary points without the complete ring structure, the estimated normal vector is not accurate. To obtain the accurate normal vector of the hole boundary, first patching the missing ring mesh, then calculating the weighted area of ring triangular surface normal, as the normal vector of the vertex. We assumed that the vertex ring region has $K$ numbers of triangular facets, the normal vector of the triangular facets inside the ring region could be calculated from the vector product of both sides of the triangle. The normal vector of triangular facets is assumed as $(i=1, 2, \dots, k)$, the area is assumed as $(i=1, 2, \dots, k)$, equation 1 shows how to calculate the normal vector of vertex. Figure 1 presents the calculation of the normal vector of the vertex of the missing triangle. The dashed line indicated the patched edge.

$$ \mathbf{n}_v = \frac{\sum_{i=1}^{k} A_i \mathbf{n}_i}{\| \sum_{i=1}^{k} A_i \mathbf{n}_i \|} \quad (1) $$
## 2.3 Calculation of boundary angle

To more convenience calculate the boundary angle, firstly, we should orient the repairing mesh and sort the boundary edge clockwise, the detail explanation of the algorithm is in reference [13]. We assumed that each two adjacent edges of the hole polygon corresponding one angle (Fig. 1 mid and right). The a, b, and n are the unit normal vectors of $v_i v_{i-1}$, $v_i v_{i+1}$ and vertex $v_i$, respectively. The angle $\theta$ is determined by the normal vector of the vertex and the vector angle. If the vector product of a and b have the same direction with the normal vector of the vertex, the angle $\theta$ is smaller than 180 degree. Else, the angle $\theta$ is larger than 180 degree. Figure 1 (mid and right) shows the two situations of the hole boundary angle. Equation 2 shows the calculation of the hole boundary angle.

$$ \begin{cases} \text{if } ((a \times b) \cdot n > 0) \\ \theta = \arccos(a \cdot b) \\ \text{else} \\ \theta = 360 - \arccos(a \cdot b) \end{cases} \qquad (2) $$

<figure><img src="image_2.png" /><figcaption>Fig. 1. Boundary normal vector estimation of and boundary angle calculation. Left: Estimation of boundary normal vector. Mid: angle less than 180 degrees. Right: Angle more than 180 degrees</figcaption></figure>

## 2.4 Calculation of new points

### 2.4.1 Calculation of initial new points

We used the principle of the smallest angle to fill the hole. Firstly, the smallest boundary angle was found, then doing the following steps: if $0 < \theta_i \le 75$, then directly connect $v_{i-1}v_{i+1}$, as shown in figure 2 left, if $75 < \theta_i \le 135$, then the new points were created from the bisector, as shown in figure 2 mid, if $135 < \theta_i < 180$, $v_{new}$ and $v_{new2}$ were created from the three times bisector, as shown in figure 2 right.
<figure><img src="image_3.png" /><figcaption>Fig. 2. Calculation rules of initial new point.
Left: $0 < \theta_i \le 75^\circ$, Mid: $75^\circ < \theta_i \le 135^\circ$, Right: $135^\circ < \theta_i < 180^\circ$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3. Direction of surface bending.
Left: normal curvature is greater than 0; Right: normal curvature is less than 0</figcaption></figure>

### 2.4.2 Estimation of normal curvature

In differential geometry, curvature is the degree of bending of a surface in local area. Normal curvature is the degree of bending of a surface along one tangential direction from one point on the surface, which could be used to investigate the degree of bending of a surface in local area. The geometric meanings of normal curvature include:

(1) the absolute of the normal curvature reflects the bending degree of the surface from one point along one direction;

(2) the positive/negative sign of the normal curvature reflects the bending direction of the surface along one tangential direction.

If the normal curvature is larger than zero, the surface bends in the direction of the normal vector of the point, as shown in figure 3 left; if the normal curvature is less than zero, the surface bends in the reverse direction of the outer normal vector of the point, as shown in figure 3 right. Taubin[14] estimated the curvature as:

$$k_p(T) \approx \frac{2 \langle N, q - p \rangle}{\| q - p \|^2} \quad (3)$$

Where $p$ is one point on the surface, $N$ is the normal vector, $q$ is another point on the surface around $p$, $k_p(T)$ is the curvature along the direction $T$ from the point $p$. $T$ is the projection unit vector of $q-p$ on the tangent plane of point $p$. In this work, the curvature along the $T$ direction of $v_i$ point is:

$$k_{v_i}(T) \approx \frac{2 \langle N, v_{\text{new}} - v_i \rangle}{\| v_{\text{new}} - v_i \|^2} \quad (4)$$
### 2.4.3 Adjusting new points

The initial new points were created from the bisector of the hole boundary angle. Filling hole by connecting the new points cannot reflect the local feature of the surface. So we need to adjust the new points. We assume that the new point $v_{new}$ was created from the angle bisector vector of $\angle v_{i-1}v_{i}v_{i+1}$. Figure 4 shows the schematic diagram for adjusting new points.

The point $v_{new}$ was adjusted on the flat $\pi$. The direction of adjusting was determined by the sign of $k_{v_i}(T)$. If $k_{v_i}(T) >0$, the new point will bend in the direction of the normal vector, that is, the surface is convex in the direction of $T$. The adjusting angle is $\theta$. If $k_{v_i}(T) <0$, the new point will bend in the reverse direction of the normal vector, that is, the surface is concave in the direction of $T$. The adjusting angle is also $\theta$. The angle $\theta$ is determined by the absolute of the normal curvature and the threshold $\eta$, which should set manually.

$$ \begin{cases} v' = v + \eta \cdot |k_{v_i}(T)| \cdot n_i \\ \theta = \arccos(v, v') \end{cases} \qquad (5) $$

The adjusted new points are calculated as:

$$ v'_{new} = v_i + \frac{1}{2}(\|v_{i-1}v_i\| + \|v_i v_{i+1}\|) \cdot \frac{v'}{\|v'\|} \qquad (6) $$

<figure><img src="image_5.png" /><figcaption>Fig. 4. Adjustment of new point</figcaption></figure>
# 3 Results and Discussion

## 3.1 Experimental results and analysis

To test the effect of this algorithm for filling holes in triangular mesh, we used this algorithm on several scanned mesh models of plant organs. A handheld 3D laser scanner (Polhemus Ins. FastScan) was used to scan real plant organs. Mesh models were constructed from the obtained 3D point cloud using RBF software attached by the scanner. The fruits of green pepper and cucumber were scanned directly from the plants in greenhouse. Mustard and ginger were removed to the lab for scanning, but without additional treatment like spray white. Figure 5 presents the mesh models with holes, the holes patching model, the enlarge effect of the holes patching (from left to right) of green pepper fruit, cucumber fruit, mustard and ginger (from the top down). Table 1 shows the number of new vertices, the number of new triangles, and the repairing time in holes patching processing for green pepper fruit, maize leaf, cucumber fruit, mustard and ginger.

The experimental results show that this algorithm is fast and effective for patching holes in mesh model. The patching results matched well with the initial density and the morphology of the mesh. For the flat area with little variation of curvature, like the mesh model of cucumber fruit (Fig. 5), a good result obtained by setting a smaller threshold. However, for the area with large variation of curvature, like the mesh model of ginger (Fig. 5), a good result could be obtained by setting different thresholds. The new point is determined by the length of the boundary of the hole, so the effect of patching is related with the initial mesh. If the initial mesh is even distributed, and the length of each edge of the hole boundary equal to the mean length of the edges of the whole mesh, the patching results could match well with the density of the initial mesh. If the initial mesh is uneven distributed, the patching result is not good. From table 1, the patching time correlated with the size of the hole, but not correlated with the size of the initial mesh. For example, the number of the initial mesh of mustard was more than that of cucumber fruit, but the number of new points and the patching time of mustard were less than those of cucumber fruit.

## 3.2 Evaluation of hole patching

We use a method proposed in [15] to evaluate the quality of the filled triangular mesh by using the above mentioned algorithm. The method assumed that $R_a$ is the radius of the inscribed circle of a triangle, $R_b$ is the radius of the circumscribed circle of the triangle. The quality of the mesh is defined as $\mu = 2R_a / R_b$. If the triangle is regular triangle, the value of $\mu$ is 1. The value of $\mu$ is more closer to 1, the quality of the created triangular mesh is better. Usually, the quality of the triangular mesh is deemed as good when the value of $\mu$ larger than 0.5. The figures of the quality of the mesh patching were automatic created by the program of algorithm (Fig. 6), in which the horizontal axis indicates the value of $\mu$, while the ordinate indicates the number of triangles. We retained two decimal digits in the data analysis for better
counting the number of triangles. Figure 6 presents the quality of the mesh patching for green pepper fruit, cucumber fruit, ginger and mustard, respectively.

The quality of the patching triangular mesh shown in Fig. 6 is high. The value of $\mu$ were mostly larger than 0.6, concentrated in the interval (0.9, 1.0), which indicates the created triangle meshes closer to regular triangle. The mean values of $\mu$ was larger than 0.85 for all organ models, which indicates that the proposed algorithm in this work could well patch the mesh holes of different plant organs.

<figure><img src="image_6.png" /><figcaption>**Fig. 5.** The holes patching results of plant organs of five variety: the mesh model with holes, the holes patching model, the enlarge effect of the holes patching (from left to right)</figcaption></figure>
<table><caption>**Table 1.** The number of new meshes and the patching time in holes patching processing</caption><thead><tr><th>Model name</th><th>Original mesh number (Np)</th><th>New added vertex number (Np)</th><th>New added triangle number (Nm)</th><th>Repairing time (s)</th></tr></thead><tbody><tr><td>Green pepper</td><td>8931</td><td>15</td><td>50</td><td>4.234</td></tr><tr><td>Leaf of maize</td><td>6725</td><td>18</td><td>75</td><td>5.485</td></tr><tr><td>Cucumber</td><td>11498</td><td>68</td><td>194</td><td>8.922</td></tr><tr><td>Ginger</td><td>13608</td><td>116</td><td>356</td><td>15.781</td></tr><tr><td>Mustard</td><td>12434</td><td>65</td><td>190</td><td>8.813</td></tr></tbody></table>

<figure><img src="image_7.png" /><figcaption>**Fig. 6.** The quality statistics of patching mesh.
Up left: green pepper model; Up right: cucumber model; Down left: ginger model; Down right: mustard model</figcaption></figure>

## 4 Conclusions

This work proposed a mesh hole patching algorithm due to the data missing during the scanning in using 3D laser scanner. The algorithm firstly extracts the hole boundary in the triangular mesh, and compute the positions of new points based on the normal vector and normal curvature of mesh boundary, then connects the new points and boundary points to generate a new triangular mesh. The experimental results indicates that the algorithm could effectively patch the mesh with large hole area and large variation of curvature. However, all the evaluations in this work were in organ scale. For the whole plant, the shelter between organs is more serious. It means more complex holes will appear when using 3D laser scanner to scan the plant. We would test the usability of the proposed method on plant scale in the near future.
Acknowledgment

This work is supported by National Natural Science Foundation of China Grant No. 31171454, China National Science and Technology Support Program Grant No. 2012BAD35B01 and Special Fund for Agro-scientific Research in the Public Interest Grant No. 201203026.

References

1. Zhao C. J., Lu S. L., Guo X. Y. et al. Exploration of digital plant and its technology system. Scientia Agricultura Sinica, 2010, 43(10): 2023-2030.

2. Davis J., Marschne S. R., Garr M. et al. Filling holes in complex surfaces using volumetric diffusion. Proceedings of the First International Symposium on 3D Data Processing Visualization, and Transmission. Los Alamitos: IEEE Computer Society Press, 2002: 428-438.

3. Liepa P. Filling holes in meshes. Proceedings of the Eurographics, ACM SIGGRAPH Symposium on Processing, Aachen, Germany, 2003. 200-205.

4. Zhang J., Yue W. N., Wang N. et al. Anisotropic Hole Filling Algorithm for Triangle Mesh Models. Journal of Computer-Aided Design & Computer Graphics, 2007, 19(7): 892-897.

5. Wei Z. L., Zhong Y. X., Yuan C. L. et al. Research on Smooth Filling Algorithm of Large Holes in Triangular Mesh Model. China Mechanical Engineering, 2008, 19(8): 949-954.

6. Zhao W., Gao S. M., Lin H. W. A robust hole-filling algorithm for triangular mesh. The Visual Computer, 2007, 23(12): 987-997.

7. Wang X. C., Cao J. J., Liu X. P. et al. Advancing Front Method in Triangular Meshes Hole-Filling Application. Journal of Computer-Aided Design & Computer Graphics, 2011, 23(6): 1048-1054.

8. Du J., Zhang L. Y., Wang H. T. et al. Hole Repairing in Triangular Meshes Based on Radial Basis Function. Journal of Computer-Aided Design & Computer Graphics, 2005, 17(9): 1976-1982.

9. Wang H. T., Zhang L. Y., Li Z. W. et al. Repairing Holes in Triangular Meshes Based on Radial Basis Function Neural Network. China Mechanical Engineering, 2005, 16(23): 2072-2079.

10. Qian G. P., Pan R. F., Tong R. F. Feature-preserving Mesh Completion. Journal of Image and Graphics, 2010, 15(2): 334-339.

11. Lévy B. Dual domain extrapolation. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, New York, ACM Press, 2003: 364-369.

12. Brunton A., Wuhrer S., Shu C. et al. Filling hole in triangular meshes by curve unfolding. Proceedings of IEEE International Conference on Shape Modeling and Applications, Beijing: Institute of Electrical and Electronics Engineers Press, 2009: 66-72.

13. Zhang L. Y., Zhou R. R., Zhou L. SH. Research on the Algorithm of Hole Repairing in Mesh Surfaces. Journal of Applied Sciences, 2002, 20(3): 221-224.

14. Taubin G. Estimating the tensor of curvature of a surface from a polyhedral approximation. Proceedings of Fifth International Conference on Computer Vision (ICCV' 95), June 1995: 902-907.

15. Field D. A. Qualitative measures for initial meshes. Numerical Methods in Engineering, 2000, 47(4): 887-906.