Estimation of Point Normals from Positional Relationship ofThree-Dimensional Scattered Point Data
Taku Itoh1
11

Faculty of Science and Technology, Seikei University, Japan

Introduction

The surface reconstruction problem for three-dimensional (3D) scattered point data derived from 3D range
scanners has been investigated in ﬁelds such as computer
graphics (CG) and computer-aided design (CAD) [1, 2].
By using an implicit function-based method, the surface
reconstruction problem can be solved. However, it must
be noted here that, for generation of an implicit function
in general domain, point normals on each of given points
may be required. For example, the multi-level partitionof unity implicits (MPU) method [2], which is a typicalmethod for generating an implicit function, requires thepoint normals. However, there are some cases that point
data do not contain normal data. In this case, surface
reconstruction from 3D scattered point data is not easy.
Hence, development of an estimation method of point normals from complicated point data is desired.
The purpose of the present study is to propose an estimation method of point normals from a positional relationship of given point data.
2

Roughly-Generated Scalar-Valued Function

For a constant data value surface, it is well known thatthe gradient vector is normal to the surface. Therefore
we can estimate point normals from given point data if
a scalar-valued function is generated. Since an implicit
function is one of the scalar-valued functions, we consider
generation of an implicit function f (p) from given point
data P = {p1 , p2 , . . . , pn } that do not contain the point
normals. Here, n is the number of given points.
To generate an implicit function, constraint points P̂ ={pn+1 , pn+2 , . . . , pn+m }, together with scalar height values H = {hn+1 , hn+2 , . . . , hn+m } have to be placed. Here,m is the number of constraint points. Usually, P̂ and H
are set by using point normals. However, we assume thatgiven point data do not have point normals. Hence, we use
the method described in Ref. [3] for setting P̂ and H. Byusing P, P̂ and H, an implicit function f (p) can roughly
be generated [3].
The diﬀerence between the proposed method and themethod described in Ref. [3] is modiﬁcation procedures ofestimated normals that are generated as −∇f (p)/|∇f (p)|.
Thus, the proposed modiﬁcation procedures of estimatednormals are described in the next section.
3

Modification of Estimated Normals

A generated surface by the Delaunay tetrahedralization
with the estimated normals occasionally has redundant triangles. The redundant triangles can be decreased by re-Fig. 1. Left: Triangles around pk without redundant triangles. Here, nsi is the surface normal of Tik , where Tik is
the ith triangle around pk , and θik is the angle of cornerof Tik . In addition, mk is the number of triangles around
pk . Right: Triangles around pk with redundant triangles.

execution of the Delaunay tetrahedralization with moreaccurate normals. In this section, we present a method for
modiﬁcation of the estimated normals.
3.1

Estimated Point Normals Generated by Average of Surface Normals

For modiﬁcation of the kth normal nk , the triangles
around pk are ﬁrst found. Let these triangles be Tk =k}, where mk is the number of triangles{T1k , T2k , . . . , Tmkk}
around pk . After that, the sum of angles {θ1k , θ2k , . . . , θmkk
that are corner of Ti around pk is calculated. Here, weassume that triangles of Tk are approximately placed on aplane surface locally. Under this assumption, if redundant
triangles do not exist in Tk , the sum of angles of thesetriangles may be close to 2π. An ideal case is illustrated
in the left of Fig. 1. In this case, the kth point normals nk
is estimated as the average of {ns1 , ns2 , . . . , nsmk }, wherensi is the surface normal of Tik . However, in case that thesum of {ns1 , ns2 , . . . , nsmk } nearly equals to zero, the nk
can not be estimated by the average of surface normals.
In this case, the nk is estimated by other procedures. In
addition, the sum of angles is not close to 2π, the nk isalso estimated by other procedures.
3.2

Recognition of Redundant Triangles

If the sum of angles is greater than 2π, some redundant
triangles may exist around pk (see the right of Fig. 1).
In this case, the kth point normals nk is estimated after recognition of redundant triangles. For recognizing redundant triangles, we ﬁrst obtain {sk1 , sk2 , . . . , skmk }, where
ski is the maximum length of three sides of Tik , since redundant triangles tend to have large sides in comparison with other triangles (see experimental result shown
kin Fig. 2b). After that, {T1k , T2k , . . . , Tm} are renumberedkkkk
in ascending order of {s1 , s2 , . . . , smk }. After renumber-ing, the sum of the angles {θ1k , θ2k , . . . , θjk } and the sum of{ns1 , ns2 , . . . , nsj } are calculated, where j is determined so∑jthat 2π − i=1 θik < ε is satisﬁed. Here, we set ε = 0.1.
Note that j occasionally does not exist. If j is found, wekkk
consider {Tj+1, Tj+2, . . . , Tm} as redundant triangles, andk
nk will be estimated by the average of {ns1 , ns2 , . . . , nsj }. If
j is not found, we consider that recognition of redundant
triangles is diﬃcult. Hence, nk will be estimated by aweighted average of other point normals. Note that, even∑jif j is found,ns is nearly equal to zero infrequently.
i=1 i
In this case, nk will also be estimated by the weighted
average.
3.3

a)

b)

c)

d)

e)

f)

Estimated Normals by Weighted Average

After the above procedures are ﬁnished, some point normals do not estimated. For this case, we employ a weighted
average of other point normals as follows:
k∑Nnp

n̂k =

k
i=1 w(rki )ni,kNnp
i=1 w(rki )∑nk =n̂k,∥n̂k ∥2

where rki = ∥pki − pk ∥2 , and w(r) is a weight function,{w(r) =( )21−6r
R( )3+8r
R0,−3( )4r
R,

for r ≤ R,
for r > R,

where R is the radius of the support. In addition,k
the collection of the Nnp
nearest points from pk arekkk{p1 , p2 , . . . , pN k }, and the estimated point normals
np{nk1 , nk2 , . . . , nkN k } correspond to these points, respecnp

tively. Note that {pk1 , pk2 , . . . , pkN k } are selected from thenp
points that already have the estimated point normals afk
ter ﬁnishing the ﬂow chart of Fig. 1. Here, Nnp
is determined as the number of points that are contained in
the k-th radius of the support Rk , where Rk is obtained
kby Rk = Rk + αRini that is iterated until Nnp≥ Nmin .
We set α = 0.1 and Nmin = 40. In addition, Rini =βR max(xmax − xmin , ymax − ymin , zmax − zmin ), where βR
is a small positive value like 0.05.
4Experiments

In this section, some experiments are conducted todemonstrate the proposed method by using the data illustrated in Fig. 2a. First, ℓ denotes the number of repetitions of the normal modiﬁcation procedures described inSect. 3. The initial surface is shown in Fig. 2b. For theinitial surfaces, we set ℓ = 0.
In Fig. 2b, obvious redundant triangles cover an expected surface. Figures. 2c, 2d and 2e show the reconstructed results with ℓ = 3, 7 and 14, respectively. We
see from Figs. 2c, 2d and 2e that the redundant trianglesof Fig. 2b are gradually decreased. In addition, an implicit surface f (p) = 0 that is generated from P and theestimated normals in Fig. 2e is shown in Fig. 2f. Here,
we investigate the accuracy of the implicit function f (p)for generating Fig. 2f. To this end,
we employ the root√∑n[f (pi )]2 /n. The
mean-square (RMS) error εRMS =i=1−5
result is εRMS = 2.2 × 10 . From this result, since thereconstructed result of Fig. 2f is visually suﬃcient, we consider that the implicit function has suﬃcient accuracy forvisualization. Therefore we consider that accurate normals
can be estimated by using the proposed method.

Fig. 2. Results of the surface reconstruction from the given
point data shown in a). Here, b) is an initial surface (ℓ =0). Obvious redundant triangles cover an expected surface.
In addition, c), d) and e) are reconstructed results withℓ = 3, 7 and 14 respectively. f) is the implicit surface
generated from P and the estimated normals in Fig. 2e.
5Conclusion

An estimation method of point normals from a positional relationship of given point data has been proposed. In the experiments, the performance of the proposed method has been investigated by using “Hand”
model that has concave aspects.
The experiments show that, by using the proposed
method, redundant triangles are gradually decreased andthe reconstructed result can ﬁnally be obtained. In addition, the reconstructed result has suﬃcient accuracy forvisualization. Therefore we consider that the point normals can be estimated from a positional relationship ofpoint data by using the proposed method.
Acknowledgement
We would like to thank the FarField Technology Ltd for
the Hand model.
References[1] T. Taniguchi and K. Moriwaki, Automatic Mesh Generation for 3D FEM - Robust Delaunay Triangulation(in Japanese). Tokyo: Morikita, 2006.
[2] Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P.
Seidel, “Multi-level partition of unity implicits,” ACM
Trans. on Graph., vol. 22, no. 3, pp. 463–470, 2003.
[3] T. Itoh, “A method of boundary estimation from 3D
scattered point data without normals by implicit function and Delaunay tetrahedralization,” Journal of Visualization, vol. 14, no. 4, pp. 381–391, 2011.