Abstract: Triangulations for surface unorganized points have been applied to 3-D reconstruction widely. A new direct triangulation method was proposed in this study. Firstly, an original triangle is built. Then this direct triangulation method is executed according to slick rule, angle of two normal vectors maximized rule, threshold distance rule and internal minimal angle maximized rule. When points are distributed asymmetrically, this method connects sparse region and dense region by Delaunay circumsphere rule. When sum of points is oversize, this method predigests topological structure of the whole points set by segmentation. Experimental results showed that surface unorganized points can be triangulated fast and precisely by this new direct triangulation method.
INTRODUCTION
Triangulations for surface unorganized points have been applied to many fields such as computer vision (Lin et al., 2004), surface design (Huang and Menq, 2002) and 3-D reconstruction (Chaine, 2003). All triangulation methods can be divided two kinds: mapping method and direct method (Wei and Ren, 2005). Mapping method (Zhang et al., 2003) is composed of three steps. Surface unorganized points are projected to a 2-D plane in first step. Then a 2-D triangulation is carried out in this plane. Finally, deepness is added into every triangle peak. Mapping method needs a little time. But many narrow triangles will come forth when deepness is high. Direct method (Choi et al., 1988) triangulates in 3-D space rightly. At first an original triangle will be built. Then triangulation will be executed according to some rules. When all 3-D points have been used, the triangulation is finished. Direct method has two shortcomings. One is that narrow triangulation will appear when points are distributed asymmetrically. Another is that self-intersection of new triangles and anterior triangles will happen when points are oversize. A new direct triangulation method was presented to resolve these two problems in this study.
THE NEW DIRECT TRIANGULATION METHOD
First an original triangle is built. Then direct triangulation is executed based on every side of the original triangle. New points are added into triangulation continually. When all points are used up, the triangulation is finished.
Creation of original triangle: Creation of original triangle is shown in Fig. 1.
Find out a point P as initiative point near the center of all points. Then look for the nearest point Q to P and connect Q with P to form original side PQ. And then find a point H which has the biggest angle with side PQ. The original triangle will be built by connecting H with P and Q.
| Fig. 1: | Creation of original triangle |
| Fig. 2: | Slick rule |
If there are two or more points having the same biggest angle with side PQ, the distance difference of every point to P and Q need to be computed. The point having the smallest distance difference will be selected as H.
Triangulation will be symmetrically executed because the original triangle is built near the center of all points.
Process of triangulation: Since, the original triangle has been built, triangulation is executed according to 4 rules. These rules are slick rule, angle of two normal vectors maximized rule, threshold distance rule and internal minimal angle maximized rule.
Slick rule: The describing of slick rule is shown in Fig. 2.
ΔABC is a basal triangle. During triangulation, ΔABP and ΔABP’ are two possible extended triangles based on side AB. In order to make surface slick, the angle between ΔABC plane and new triangle plane had better be an obtuse angle.
So, the normal vector of every triangle has to be computed. Let n1, n2, n3 denote the normal vector of ΔABC, ΔABP, ΔABP’ respectively. And n1, n2, n3 can be computed as follows:
| (1) |
| (2) |
| (3) |
Let, α1 be the angle of n1 and n2 and let α2 be the angle of n1 and n3. Then cosine of α1 and α2 can be obtained by Eq. 4-5:
| (4) |
| Fig. 3: | Angle of two normal vectors maximized rule |
| Fig. 4: | Threshold distance rule |
| (5) |
Because of cosα1<0 and cosα2<0, we can know: the angle of n1 and n2 is an obtuse angle and that the angle of n1 and n3 is a sharp angle. So, ΔABP is selected as the extended triangle according to slick rule.
If the angle of basal triangle plane and new triangle plane is a right angle, other rules should be added to judge whether this triangle can be chosen as an extended triangle of the triangulation.
Angle of two normal vectors maximized rule: When there are two or more points to tally with slick rule, the angle of two normal vectors maximized rule will be introduced. Description of this rule is shown in Fig. 3.
In Fig. 3, point P and point P’ are both satisfied with slick rule. That’s, the angle of n1 and n3 is also an obtuse angle as well as the angle of n1 and n2. Here, angle of two normal vectors maximized rule will be used in choosing an optimal point. Because the angle of n1 and n2 is biggish, ΔABP should be a better triangulation than ΔABP’.
Threshold distance rule: Threshold distance rule is used in enacting a searching scale. Points out of this scale will not be taken into account. This rule is expressed in Fig. 4.
In Fig. 4, ΔABP and ΔABP’ are two possible triangles according slick rule. But ΔABP’ plane has a bigger angle with ΔABC plane. Restricted by angle of two normal vectors maximized rule, ΔABP will be washed out.
| Fig. 5: | Internal minimal angle maximized rule |
However, P’ is very far to side AB. This triangulation will lose many details. So, a threshold is enacted to limit searching of possible points beforehand.
If no feat points were found in this searching scale, threshold distance should be enlarged automatically till right point is found out.
Internal minimal angle maximized rule: There is a peculiar instance during triangulation. It is shown in Fig. 5.
In Fig. 5, ΔABP and ΔABP’ both tally with slick rule and threshold distance rule. Moreover their planes have the same angle with ΔABC plane. Which triangle is optimal on earth?
Here, internal minimal angle maximized rule has to be introduced. In Fig. 5, p1 and p2 are internal minimal angle of ΔABP and ΔABP’ respectively. Further more p1 is bigger than p2. According to internal minimal angle maximized rule, ΔABP should be kept down.
When surface points are symmetrical and skimp, direct triangulation can be executed according above four rules. In fact, there are a large number of points on many surfaces. And points are distributed asymmetrically. Under these two conditions, nether methods are used.
When points are distributed asymmetrically: When points are distributed asymmetrically, there are many sparse regions and dense regions. If sparse region and dense region are connected by four rules described earlier many narrow triangles will come into being.
In this study, Delaunay thinning treatment is introduced to connect sparse region and dense region. There is a long distance from boundary of sparse region to boundary of dense region. If no points are found when threshold distance is too big, we will consider that there is the joint of sparse region and dense region. Here, Delaunay thinning treatment will be used.
By Delaunay thinning treatment, all triangles should satisfy with Delaunay circumsphere rule. That’s, there is a circumsphere to every triangle at least and there is no vertex of other triangle inside this circumsphere.
| Fig. 6: | Delaunay thinning treatment, (a) Before treatment and (b) after treatment |
| Fig. 7: | Two instances in partition, (a) Ecumenical surface and (b) close surface |
If a triangle doesn’t satisfy with this rule, Delaunay thinning treatment will be carried out. It is shown in Fig. 6.
In Fig. 6a, point D is included inside the circumsphere of ΔABC. The center point O of this circumsphere will be added into triangulation. During new triangulation, more triangles come into being such as ΔAEO, ΔOBC, ΔAOD, ΔDOC and ΔEOB in Fig. 6b.
By Delaunay thinning treatment, narrow triangles will not come forth and sparse region and dense region are connected preferably.
When points are oversize: When sum of points is oversize, we divide all points into many regions. In every region, there is a small quantity of points. Then direct triangulation described in earlier is carried out. Finally, all regions are connected using the method in earlier.
Two instances should be considered in partition. They are shown in Fig. 7.
In Fig. 7a, all points are projected to O-x-y plane and every point has exclusive x coordinate and y coordinate. Partition of these points is finished according to 2-D coordinate compositor of all points. In Fig. 7b, there are a few points to have the same x coordinate and y coordinate. Here, a projective plane β is introduced. All points are divided into two parts by plane β. Then points are projected to plane β. All points in every part have their unique x coordinate and y coordinate.
| Fig. 8: | Experimental results. (a) Triangulation of LOG operator, (b)
triangulation of |
Partition in every part is achieved by 2-D coordinate compositor of all points.
When the shape of surface is complicated, more projective planes will be introduced.
Two problems should be considered to decide how many points are included in every region. One is the sum of surface points. The other is the robustness of direct triangulation. On the one hand more points should be involved as possible in every region. On the other hand, the number of points should be within measure to ensure that self-intersection can not come into being.
EXPERIMENTS AND ANALYSIS
Large numbers of experiments are performed by using the triangulation method presented in this study. Four typical experimental results are shown in Fig. 8.
Triangulation of LOG operator is shown in Fig. 8a. Triangulation
of
| Table 1: | The sum of points and triangulation time of 4 experiments |
Triangulation and 3-D reconstruction of a scalp surface are shown in Fig. 8c. Triangulation and 3-D reconstruction of a face surface are shown in Fig. 8d.
From Fig. 8, we can see that this triangulation method is effective to both regular surface (e.g., Fig. 8a) and irregular surface (e.g., Fig. 8b). Triangle grids of the surface triangulated by this method are symmetrical. The boundaries of sparse region and dense region are connected availably by using this triangulation method (e.g., Fig. 8d).
The sum of points and triangulation time of each surface in Fig. 8 are shown in Table 1.
From Table 1, we can see that the speed of this triangulation method is very fast. For example, more than 5000 points of the face surface in Fig. 8d are triangulated within 9 sec.
DISCUSSION
This new direct triangulation method benefits from Choi’s triangulation theory (Choi et al., 1988). But 4 rules used in this new method is different with Choi’s. And two actual problems are considered in this new method. One is that sum of points is oversize, anther is that points are distributed asymmetrically. Therefore, partition and Delaunay thinning are used in solving these problems specifically. It is significantly different from Choi’s method.
CONCLUSIONS
A new direct triangulation method was proposed in this study. This method finishes triangulation according to slick rule, angle of two normal vectors maximized rule, threshold distance rule and internal minimal angle maximized rule.
When points are distributed asymmetrically, Delaunay thinning treatment is introduced to connect sparse region and dense region. By this treatment, narrow triangles can not come into beings.
When sum of points is oversize, all points are divided into many small regions. By this way, triangulation avoids self- intersection effectively.
Experimental results show that this method is fast and the triangle grids of this method are symmetrical.
ACKNOWLEDGMENT
This study was supported by the Research Fund from National Defence Key Laboratory of Autonomous Underwater Vehicle Technology (20080006), the Harbin Special Fund of Technological Innovation Talent (2010RFQXG039), the Scientific and Technological Project of Education Department of Heilongjiang Province (11541046) and the Postdoctoral Sustentation Fund of Heilongjiang Province with postdoctoral No. (69449).