Subdivision is a well-known and established method for generating smooth curves and surfaces from discrete data by repeated refinements. The typical input for such a process is a mesh of vertices. In this work we propose to refine data consisting of vertices of a mesh and a normal vector at each vertex. This is done by replacing the weighted binary arithmetic means in a linear subdivision scheme, represented in terms of repeated binary weighted linear means, by binary averaging operations with the same weights. For the case that the initial data consists of control points only, a naive method for choosing initial normals is proposed.
We begin with introducing a circle average in 2D, which is a new non-linear weighted average of two points and their corresponding normals. We demonstrate
the ability to locally approximate curves by the circle average. With this ability, the circle average is a candidate for modifying linear subdivision schemes refining
points, to schemes refining point-normal pairs. We investigate the modified Lane-Riesenfeld algorithm and the modified 4-point scheme. We first prove the
convergence of these schemes. Next, we extend the existing proximity tool to prove C1 smoothness of the curves generated by these schemes. An example
demonstrates the superiority of the above two modified schemes, with the naive choice of initial normals over the corresponding linear schemes, when applied to a control polygon with edges of significantly different lengths.
Next, we extend the 2D circle average to a 3D binary average of point-normal pairs, and study its properties. We modify classical surface-generating linear subdivision schemes with this average, obtaining surface-generating schemes refining point-normal pairs. The performance of these modified schemes is compared to their linear variants, when operating on the same initial mesh. The main advantage of the modified schemes is the editing capabilities of the initial normals, and the rich geometries that can be generated. This advantage is demonstrated by several examples.
A scheme based on circle average has the disadvantage that the limit normals are not the normals of the limit curve. We solve this problem by proposing
a new averaging method - Bezier quasi-average, and obtain a new family of algorithms based on it. We demonstrate their new editing capabilities and apply
this subdivision technique to smooth a precomputed feasible polygonal point robot path in environment with obstacles.
We provide a link to our repository, where we store the files of the initial and refined meshes of our examples, and the implementation code. Several videos,
demonstrating the editing capabilities of the initial normals are provided in our Youtube channel.
Evgeny recently completed his Ph.D. in Computer Sciences at Tel-Aviv University under the supervision of Prof. Nira Dyn and Prof. Daniel Cohen-Or. The primary field of his studies was geometric modeling, with the goal to improve editing capabilities of a typical Computer Aided Geometric Design system. Prior to that, Evgeny finished M.Sc. in CS and B.Sc. in CS and Math at Tel-Aviv and Bar-Ilan universities respectively. Evgeny held various positions in the high-tech industry in between his masters and doctorate.