## Normal variation for adaptive feature size

Nina Amenta and Tamal K. Dey

∗ †

August 5, 2014

## Background

Let Σ be a closed, smooth surface in R 3 . For any two sets X,Y ⊂ R 3 , let d X,Y ( ) denote the Euclidean distance between X and Y . The local feature size f ( x ) at a point x ∈ Σ is defined to be the distance d x, M ( ) where M is the medial axis of Σ . Let n p denote the unit normal (inward) to Σ at point p . Amenta and Bern in their paper [1] claimed the following:

Claim 1 Let q and q ′ be any two points in Σ so that d q, q ( ′ ) ≤ ε min { f ( q , f ) ( q ′ ) } for ε ≤ 1 3 . Then, ∠ n , n q q ′ ≤ ε 1 -3 ε .

Unfortunately, the proof of this claim as given in Amenta and Bern [1] is wrong; it also appears in the book by Dey [2]. In this short note, we provide a correct proof with an improved bound of ε 1 -ε .

Theorem 2 Let q and q ′ be two points in Σ with d q, q ( ′ ) ≤ εf ( q ) where ε ≤ 1 3 . Then, ∠ n , n q q ′ ≤ ε .

1 -ε

## Definitions and Preliminaries

For any point p ∈ R 3 , let ˜ p denote the closest point of p in Σ . When p is a point in Σ , the normal to Σ at p is well defined. We extend this definition to any point p ∈ R 3 . Define the normal n p at p ∈ R 3 \ M as the normal to Σ at ˜ p . Similarly, we extend the definition of local feature size f to R 3 . For any point p ∈ R 3 , let f ( p ) be the distance of p to the medial axis of Σ . Notice that f is 1 -Lipschitz. If two points x and y lie on a surface F ⊂ R 3 , let d F ( x, y ) denote the geodesic distance between x and y . The following facts are well known in differential geometry.

∗ Dept. of CS, U. of California, Davis, CA 95616, amenta@cs.ucdavis.edu

† Dept. of CSE, Ohio State U., Columbus, OH 43210, tamaldey@cse.ohio-state.edu

Proposition 3 Let F be a smooth surface in R 3 . Let q and q ′ be two points in F . Then,

$$\lim _ { d \to 0 } \frac { d _ { F } ( q, q ^ { \prime } ) } { d ( q, q ^ { \prime } ) } = 1.$$

Proposition 4 Consider the geodesic path between q, q ′ on a smooth surface F in R 3 . Let κ m be the maximum curvature on this geodesic path. Then ∠ n , n q q ′ ≤ κ m F d ( q, q ′ ) .

## The Proof

Weare to measure ∠ n , n q q ′ for two points q and q ′ in Σ . One approach would be to use the propositions above to bound the length of a path from p to q on Σ and then use that length to bound the change in normal direction, but we can get a better bound by considering the direct path from p to q .

Let Σ ω denote an offset of Σ , that is, each point in Σ ω has distance ω from Σ . Formally, consider the distance function

$$h \colon \mathbb { R } ^ { 3 } \rightarrow \mathbb { R }, \ h ( x ) \mapsto d ( x, \Sigma ).$$

↦

$$\text{Then, } \Sigma _ { \omega } = h ^ { - 1 } ( \omega ).$$

Claim 5 For ω ≥ 0 let p be a point in Σ ω where ω &lt; f p (˜) . There is an open set U ⊂ R 3 so that σ p = Σ ω ∩ U is a smooth 2 -manifold which can be oriented so that n x is the normal to σ p at any x ∈ σ p .

PROOF. Since ω &lt; f p (˜) , p is not a point on the medial axis. Therefore, the distance function h is smooth at p . One can apply the implicit function theorem to claim that there exists an open set U ⊂ R 3 where

$$\sigma _ { p } = h ^ { - 1 } ( \omega ) \cap U$$

is a smooth 2 -manifold. The unit gradient ( ∇ h ‖∇ ‖ h ) x = x -˜ x ‖ x - ‖ ˜ x which is precisely n x up to orientation is normal to σ p at x ∈ σ p .

PROOF. [ Proof of Theorem 2 ] Consider parameterizing the segment qq ′ by the length of qq ′ . Take two arbitrarily close points p = p t ( ) and p ′ = p t ( +∆ ) t in qq ′ for arbitrarily small ∆ t &gt; 0 . Let θ t ( ) = ∠ n , n q p t ( ) and ∆ α = ∠ n , n p p ′ . Then, | θ t ( +∆ ) t -θ t ( ) | ≤ ∆ α giving

$$| \theta ^ { \prime } ( t ) | \leq \lim _ { \Delta t \rightarrow 0 } \frac { \Delta \alpha } { \Delta t }.$$

If we show that lim ∆ t → 0 ∆ α ∆ t is no more than 1 (1 -ε f ) ( q ) we are done since then

$$\underset { \Delta t \to 0 } { \mu } \overline { \Delta t } \text{ is in one una } \overline { \underset { ( 1 - \varepsilon ) f ( q ) } { \nu } } \text{ we are out} \\ \underset { \zeta } { \mu } n _ { q }, n _ { q ^ { \prime } } & \leq \int _ { q q ^ { \prime } } | \theta ^ { \prime } ( t ) | d t \\ & \leq \int _ { q q ^ { \prime } } \frac { 1 } { ( 1 - \varepsilon ) f ( q ) } d t \\ & = \frac { d ( q, q ^ { \prime } ) } { ( 1 - \varepsilon ) f ( q ) } \\ & \leq \frac { \varepsilon } { ( 1 - \varepsilon ) }. \\ \tilde { p } ) \, < \, d ( q, p ) + d ( p, \tilde { p } ) \text{ and } d ( q, p ) \, < \, \varepsilon f ( q ).$$

We have d q, p ( ˜) ≤ d q, p ( ) + d p, p ( ˜) and d q, p ( ) ≤ εf ( q ) . Since also ω = d p, p ( ˜) ≤ d p, q ( ) ≤ εf ( q ) , we have ω ≤ 2 ε 1 -2 ε f (˜) p (by a standard argument using the fact that the function f is 1 -Lipshitz). Therefore, ω &lt; f p (˜) for ε &lt; 1 3 / , and there is a smooth neighborhood σ p ⊂ Σ ω of p satisfying Claim 5.

Let r be the closest point to p ′ in Σ ω , and let ∆ t be small enough so that r and the geodesic between p and r in σ p lies in σ p . Notice that , by Claim 5, ∆ α = ∠ n , n p p ′ = ∠ n , n p r .

$$\text{Claim} \, 6 \, \lim _ { \Delta t \rightarrow 0 } \frac { d ( p, r ) } { \Delta t } \leq 1.$$

PROOF. Consider the triangle prp ′ . If the tangent plane to σ p at r separates p and p ′ , the angle ∠ prp ′ is obtuse. It follows that d p, r ( ) ≤ d p, p ( ′ ) = ∆ t . In the other case when the tangent plane to σ p at r does not separate p and p ′ , the angle ∠ prp ′ is non-obtuse. Let x be the foot of the perpendicular dropped from p on the line of p r ′ . Wehave d p, r ( ) cos α ≤ d p, p ( ′ ) where α is the acute angle ∠ rpx . Combining the two cases we have d p, r ( ) / ∆ t ≤ 1 cos α . Since α goes to 0 as ∆ t goes to 0 , we have lim ∆ t → 0 d p,r ( ) ∆ t ≤ 1 .

Now consider the geodesic between p and r in σ p , and let m be the point on the geodesic at which the maximum curvature κ m is realized. Recall that d σ p ( p, r ) denotes the geodesic distance between p and r on σ p . Let r m be the radius of curvature corresponding to κ m , i.e., κ m = 1 /r m . Clearly, f ( m ) ≤ r m . So, Proposition 4 tells us that

$$\Delta \alpha \leq \frac { d _ { \sigma _ { p } } ( p, r ) } { f ( m ) }.$$

Therefore,

$$\lim _ { \Delta t \to 0 } \frac { \Delta \alpha } { \Delta t } \ \leq \ \lim _ { \Delta t \to 0 } \frac { d _ { \sigma _ { p } } ( p, r ) } { \Delta t \, f ( m ) }$$

In the limit when ∆ t goes to zero, d σ p ( p, r ) approaches d p, r ( ) which in turn approaches ∆ t (Proposition 3 and Claim 6). Meanwhile, d q, m ( ) ≤ d q, p ( ) + d p, r ( ) approaches d q, p ( ) ≤ εf ( q ) as ∆ t goes to zero (again by Claim 6). So, in the limit, f ( m &gt; ) (1 -ε f ) ( q ) (again using the fact that f is 1 -Lipshitz). Therefore,

$$\lim _ { \Delta t \rightarrow 0 } \frac { \Delta \alpha } { \Delta t } \leq \frac { 1 } { ( 1 - \varepsilon ) f ( q ) }$$

which is what we need to prove.

Remark : The bound on normal variation can be slightly improved to -ln(1 -ε ) by observing the following. We used that d q, p ( ) ≤ εf ( q ) to arrive at the bound f ( m &gt; ) (1 -ε f ) ( q ) . In fact, one can observe that d q, p ( ) ≤ εtf ( q ) giving f ( m &gt; ) (1 -εt f ) ( q ) . This gives | θ ′ ( ) t | ≤ 1 (1 -εt f ) ( q ) . We have

$$\zeta n _ { q }, n _ { q ^ { \prime } } \leq \int _ { q q ^ { \prime } } \frac { 1 } { ( 1 - \varepsilon t ) f ( q ) } d t = - \frac { d ( q, q ^ { \prime } ) \ln ( 1 - \varepsilon ) } { \varepsilon f ( q ) } = - \ln ( 1 - \varepsilon ).$$

Acknowledgement We thank Siu-Wing Cheng, Jian Sun, and Edgar Ramos for discussions on the normal variation problem.

## References

- [1] N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom. 22 (1999), 481-504.
- [2] T. K. Dey. Curve and surface reconstruction : Algorithms with mathematical analysis. Cambridge University Press, New York, 2006.
Nina Amenta Tamal K. Dey
Normal variation for adaptive feature size
The change in the normal between any two nearby points on a closed, smooth
surface is bounded with respect to the local feature size (distance to the
medial axis). An incorrect proof of this lemma appeared as part of the analysis
of the "crust" algorithm of Amenta and Bern.