Dr. Hongwei lin Chinese Version

Global Image Vectorization by Incremental T-spline Image Fitting.pdf

Technical Report, TR-ZJUCAD-2012-001, Zhejiang University

Hongwei Lin, Zhiyu Zhang

Vector graphics has been increasingly adopted to represent images because of its compactness, scalability, and editability. However, current image vectorization methods are performed mainly in a patch-by-patch manner, which requires significant skill and complex processing. In this paper, we present an incremental T-spline image-fitting algorithm for transforming an entire image into a T-spline representation. The algorithm consists of two alternately executed procedures: progressive fitting and sub-regional knot insertion. As an iterative method, the iteration speed of progressive fitting is steady and insensitive to the growing number of unknown T-mesh vertices; thus, this approach is able to perform global image vectorization efficiently for large raster images. Additionally, progressive fitting presents a unified solution for vectorizing images with or without holes. Moreover, because of the adaptivity of T-spline fitting , our method is able to capture the features of a raster image automatically and faithfully by sub-regional knot insertion and thereby greatly reduce the number of control mesh vertices. Finally, transforming a T-spline represented image into a raster image is a fast process that is usually completed in seconds.

Filling Triangular Mesh Model with All-Hex Mesh by Volume Subdivision Fitting.pdf

Technical Report, TR-ZJUCAD-2012-002, Zhejiang University

Hongwei Lin, Hongwei Liao, Chongyang Deng

The hexahedral mesh (hex mesh) is preferred to the tetrahedral mesh (tet mesh) in finite element methods for numerical simula- tion. However, generating a hex mesh with desirable qualities of- ten requires significant geometric decomposition and considerable user interactions. Therefore, this process may require days or even weeks in the case of complex shapes. In this paper, we develop a method based on subdivision fitting to fill a given triangular mesh model with an all-hex volume mesh. Our method first constructs an initial control solid, which consists of a face-to-face combination of several cubes, based on the skeleton of the given model. The orientation of each cube is determined by the local orientation of the skeleton and the local shape of the given model. Therefore, the shape of the control solid is close to that of the given model. Next, the surface mesh of the initial control solid is extracted and fitted to the given mesh model by an iterative subdivision fitting method. In each iteration, the movement of the surface mesh is diffused to the inner vertices by an optimization technique. After the iteration stops, an all-hex volume mesh that fills the given triangular mesh model can be generated by subdividing the control solid with the multi-linear cell-averaging (MLCA) volume subdivision rule. The smoothness of the MLCA subdivision rule guarantees that the qual- ity of the generated all-hex volume mesh is good. Empirical data show that our algorithm is effective and efficient.

Uniform B-spline Curve Interpolation with Prescribed Tangent and Curvature Vectors.pdf

IEEE Transactions on Visualization and Computer Graphics, in press. (SCI/EI)

S. Okaniwa, A. Nasri, Hongwei Lin, A. Abbas, Y. Kineri, T. Maekawa

This paper presents a geometric algorithm for the generation of uniform cubic B-spline curves interpolating a sequence of data points under tangent and curvature vectors constraints. To satisfy these constraints, knot insertion is used to generate additional control points which are progressively repositioned using corresponding geometric rules. Compared to existing schemes, our approach is capable of handling plane as well as space curves, has local control, and avoids the solution of the typical linear system. The effectiveness of the proposed algorithm is illustrated through several comparative examples. Applications of the method in NC machining and shape design are also outlined.

Extended T-mesh and Data Structure for the Easy Computation of T-spline.pdf

Journal of Information and Computational Science, 9(3), 583-593, 2012. (EI)

Hongwei Lin, Ye Cai, Shuming Gao

T-spline overcomes the topological constraints of the control net of NURBS model successfully. However, the introduction of T-junctions, L-junctions and the isolated vertices in the T-mesh makes its topological structure very flexible. As a result, not only the T-mesh is hard to be represented, but the computation and local refinement of T-spline are difficult to be implemented as well. This hinders the studies and applications of T-splines in practice. In this paper, we develop the extended T-mesh, which can be represented in an obj -like format file, and converted into the face-edge-vertex data structure conveniently. With such data structure, the computation of T-splines can be made much easier. Furthermore, we develop a new local refinement algorithm, by virtue of the extended T-mesh. The new algorithm is easy to be implemented, by separating the local refinement into two procedures, the mesh refinement, and blending function refinement.

Automatic cage generation by improved OBBs for mesh deformation.pdf

The Visual Computer, Volume 28, Number 1, 21-33, 2012. (SCI/EI)

Chuhua Xian, Hongwei Lin, Shuming Gao

In cage-based deformation, the most tedious task is to construct the coarse cage bounding a model. Currently, the coarse cage is constructed mainly by hand, and the construction usually takes several hours, even longer. Therefore, it is important to develop a convenient method to generate the coarse cage bounding a model. In this paper, we devise a method to construct the coarse cage automatically using the improved OBB tree, while allowing the users to modify the cage easily. Firstly, the OBB tree bounding the model is generated, where we propose an improved OBB slicing rule to make the generated OBBs close to the model it contains. Secondly, the OBBs are adjusted and merged into a whole entity by the boolean union operation. Finally, the outer surface of the entity is extracted as the coarse cage. Empirical results demonstrate the effectiveness and efficiency of the automatic coarse cage-generation method.

Variational progressive-iterative approximation for fairing curve and surface generation.pdf

In Proceedings of Computer-Aided Design and Computer Graphics’2011, 258-261, Jinan, China, 2011. (EI)

Honwei Lin, Yu Zhao

Fairing curve and surface generation is an important topic in geometric design. However, the conventional method for generating the fairing curve and surface, which fit the giving data points, is hard to control the fitting precision, because it is a minimization problem where the objective function is the weighted sum of a fitting term and a fairness term. In this paper, we develop the variational progressive-iterative approximation (abbr. variational PIA) method for fitting a data point sequence. While the variational PIA is easy to control the fitting precision, the generated fitting curve or surface is the most fairing one in some scope. Lots of comparisons show that the fairness results of the variational PIA are comparable to that of the conventional method.

The PIA Property of Low Degree Non-uniform Triangular B-B Patches.pdf

In Proceedings of Computer-Aided Design and Computer Graphics’2011, 239-243, Jinan, China, 2011. (EI)

Hongwei Lin, Yu Zhao

Progressive-iterative approximation presents an intuitive way to generate a sequence of curves or patches, whose limit interpolates the given data points. It has been shown that the blending curves and tensor product blending patches with normalized totally positive basis have the progressiveiterative approximation property. In this paper, we prove that, the quadratic, cubic, and quartic non-uniform triangular Bernstein- B´ezier patches also have the progressive-iterative approximation property. Since the most often empolyed in geometric design are the low degree curves or patches, especially the cubic curves and patches, the result shown in this paper has practical significance for geometric design.

细分曲面拟合的局部渐进插值方法.pdf

计算机研究与发展, 2012第8期. (EI)

赵宇, 蔺宏伟, 鲍虎军

The quality of subdivision surface generated by the approximating scheme is usually better than that by the interpolating scheme, while the approximating subdivision surface is unable to interpolate the vertices of the initial control mesh. Traditional methods that make the approximating subdivision surface interpolate the initial mesh need to solve a global linear system. It is computation intensive, and hard to deal with dense meshes. Without solving a linear system, the progressive interpolation calculates the approximating subdivision surface that interpolates the initial mesh by adjusting the vertices of the control mesh iteratively. It can handle control meshes of any size and any topology while generating smooth subdivision surfaces that faithfully resemble the shape of the initial meshes. In this paper, we show the local property of the progressive interpolation for approximating subdivision schemes. That is, if only a subset of the vertices of the control mesh are adjusted, and others remain unchanged, the limit of the subdivision surface generated in the progressive interpolation procedure still interpolates the corresponding subset of the vertices in the initial mesh. The local property of the progressive interpolation brings more flexibility for shape controlling, and makes the adaptive fitting possible. Lots of experimental examples presented in this paper illustrate the shape controlling and adaptive fitting capabilities of the local progressive interpolation.

基于GPU和区间分析的隐式曲面绘制和网格化.pdf

计算机辅助设计与图形学学报, 23(5), 763-770, 2011. (EI)

秦阳, 蔺宏伟, 冼楚华, 高曙明

了通过并行化技术提高隐式曲面绘制和网格化的速度，提出一种基于GPU并行计算架构的区间分析方法来网格化和绘制隐式曲面．首先按照给定的绘制分辨率将绘制空间离散成体素表示，充分利用GPU的并行计算能力，采取Ⅸ间分析方法并行计算隐函数在所有体素上的取值区间，从而确定出包含隐函数零等值面的特征体索；进一步，抽取特征体素的外表面对其进行拓扑校正，确保得到的网格是二维流形f然后使用Laplace操作对这个网格进行光滑处理，得到隐式曲面的网格表示．大量实验结果表明，隐式曲面的网格化和绘制时间一般小于0.1s，达到了实时化的水平.

An extended iterative format for the progressive-iteration approximation.pdf

Computers & Graphics, 35(5), 967-975, 2011. (SCI/EI)

Hongwei Lin, Zhiyu Zhang

Progressive-iteration approximation (PIA) is a new data fitting technique developed recently for blending curves and surfaces. Taking the given data points as the initial control points, PIA constructs a series of fitting curves (surfaces) by adjusting the control points iteratively, while the limit curve (surface) interpolates the data points. More importantly, progressive-iteration approximation has the local property, that is, the limit curve (surface) can interpolate a subset of data points by just adjusting a part of corresponding control points, and remaining others unchanged. However, the current PIA format requires that the number of the control points equals that of the data points, thus making the PIA technique inappropriate to fitting large scale data points. To overcome this drawback, in this paper, we develop an extended PIA (EPIA) format, which allows that the number of the control points is less than that of the given data points. Moreover, since the main computations of EPIA are independent, they can be performed in parallel efficiently, with storage requirement O(n), where n is the number of the control points. Therefore, due to its local property and parallel computing capability, the EPIA technique has great potential in large scale data fitting. Specifically, by the EPIA format, we develop an incremental data fitting algorithm in this paper. In addition, some examples are demonstrated in this paper, all implemented by the parallel computing toolbox of Matlab, and run on a PC with a four-core CPU.

CAD mesh model segmentation by clustering.pdf

Computers & Graphics, 35(3), 685-691, 2011 (SCI/EI)

Dong Xiao, Hongwei Lin, Chuhua Xian, Shuming Gao

CAD mesh models have been widely employed in current CAD/CAM systems, where it is quite useful to recognize the features of the CAD mesh models. The first step of feature recognition is to segment the CAD mesh model into meaningful parts. Although there are lots of mesh segmentation methods in literature, the majority of them are not suitable to CAD mesh models. In this paper, we design a mesh segmentation method based on clustering, dedicated to the CAD mesh model. Specifically, by the agglomerative clustering method, the given CAD mesh model is first clustered into the sparse and dense triangle regions. Furthermore, the sparse triangle region is separated into planar regions, cylindrical regions, and conical regions by the Gauss map of the triangular faces and Hough transformation; the dense triangle region is also segmented by the mean shift operation performed on the mean curvature field defined on the mesh faces. Lots of empirical results demonstrate the effectiveness and efficiency of the CAD mesh segmentation method in this paper.

Curvature of singular Bézier curves and surfaces.pdf

Computer Aided Geometric Design, 28(4), 233-244, 2011. (SCI/EI)

Sederberg T. W., Hongwei Lin, Xin Li

This paper presents a general approach for finding the limit curvature at a singular endpoint of a rational Bézier curve and the singular corner of a rational Bézier surface patch. Conditions for finite Gaussian and mean limit curvatures are expressed in terms of the rank of a matrix.

The convergence of the geometric interpolation algorithm.pdf

Computer-Aided Design (2010), doi:10.1016/j.cad.2010.01.006 (SCI/EI)

Hongwei Lin

the geometric interpolation algorithm is proposed by Maekawa et. al. in Interpolation by geometric algorithm, Computer-Aided Design, 39, 313-323, 2007. Without solving a system of equations, the algorithm generates a curve(surface) sequence, of which the limit curve(surface) interpolates the given data points. However, the convergence of the algorithm is a conjecture in the reference above, and demonstrated by lots of empirical examples. In this paper, we prove the conjecture given in the reference in theory, that is, the geometric interpolation algorithm is convergent for a blending curve(surface) with normalized totally positive basis, under the condition that the minimal eigenvalue λmin(Dk) of the collocation matrix Dk of the totally positive basis in each iteration satisfies λmin(Dk) >α> 0. As a consequence, the geometric interpolation algorithm is convergent for Bezier, B-spline, rational Bezier, and NURBS curve(surface) if they satisfy the condition aforementioned, since Bernstein basis and B-spline
basis are both normalized totally positive.

Local progressive-iterative approximation format for blending curves and patches. pdf

Computer Aided Geometric Design (2010), doi:10.1016/j.cagd.2010.01.003 (SCI/EI)

Hongwei Lin

Just by adjusting the control points iteratively, progressive-iterative approximation presents an intuitive and straightforward way to fit data points. It generates a curve or patch sequence with finer and finer precision, and the limit of the sequence interpolates the data points. The progressive-iterative approximation brings more flexibility for shape controlling in data fitting. In this paper, we design a local progressive-iterative approximation format, and show that the local format is convergent for the blending curve with normalized totally positive basis, and the bi-cubic B-spline patch, which is the most commonly used patch in geometric design. Moreover, a special adjustment manner is designed to make the local progressive-iterative approximation format is convergent for a generic blending patch with normalized totally positive basis. The local progressive-iterative approximation format adjusts only a part of the control points of a blending curve or patch, and the limit curve or patch interpolates the corresponding data points. Based on the local format, data points can be fit adaptively.

Bisection approach for pixel labelling problem. pdf

Pattern Recognition 43, 1826–1834, 2010. (SCI/EI)

Dengfeng Chai, Hongwei lin , Qunsheng Peng

this paper formulates pixel labelling as a series of two-category classification. Unlike existing techniques, which assign a determinate label to each pixel, we assign a label set to each pixel and shrink the label set step by step. Determinate labelling is achieved within log2n (n is size of label set) steps. In each step, we bisect the label set into two subsets and discard the one with higher cost of assigning it to the pixel. Simultaneous labelling of an image is carried out by minimizing an energy function that can be minimized via graph cut algorithm. Based on the bisection approach, wep ropose a bitwise algorithm for pixel labelling, which set one bit of each pixel’s label in each step. We apply the proposed algorithm to stereo matching and image restoration. Experimental results demonstrate that both good performance and high efficiency are achieved.

FEA-mesh editing with feature constrained. pdf

Proceedings of CAD/CG’09.

Chuhua Xian, Shuming Gao, Hongwei Lin, and Dong Xiao.

this paper proposes a framework for FEA-mesh editing with feature constrained. In the framework, cage-based technique is first used to edit the base-decomposition model. Vertices of the constrained featureare transformed into a local form, and then reconstructed after determining the common boundary. Feature rotation constraint derives from the normal change of the boundary plane. Parameters are analyzed before editing operation, and our method permits the user to add constraints on the parameters of the feature. This framework can also keep consistence for the disconnected assembly mesh model. Experimental results show that constrained features hold precisely after mesh editing. Additionally, experimental datav alidate the efficiency of our method, achieving real-time response.

Automatic generation of coarse bounding cages from dense meshes. pdf

IEEE International Conference on Shape Modeling and Applications 2009, 21-27.

Chuhua Xian, Hongwei Lin, Shuming Gao.

the coarse bounding cage of a dense mesh plays important roles in computer graphics, computer vision, and geometric design. Specifically, in volume-based deformation, a coarse bounding cage is required to manipulate the dense mesh model it enclosed; in subdivision surface fitting, the fitting starts from a coarse cage bounding the fitted dense mesh or point set; and so on. However, the generation of a coarse bounding cage is mainly by interactive ways, which are very tedious and time-consuming. In this paper, we develop a fully automatic method to generate a coarse cage bounding a dense mesh model. the automatically generated coarse bounding cage can keep the topological structure and major geometric features of the original mesh model, which is validated by theoretical analysis and experimental data presented in this paper. Further more, we employ the automatically generated coarse bounding cage in some applications, such as deformation, and subdivision fitting, producing good results.

On the derivative formula of a rational Bezier curve at a corner. pdf

Applied Mathematics and Computation, 210(1), 197-201, 2009.(SCI/EI)

Hongwei Lin

In this paper, we develop the exact arbitrary order derivative formula of a rational Bezier curve at its corner. Some examples are presented to demonstrate the computation of the exact derivatives.

Poisson based reuse of freeform features with NURBS representation. pdf

Computers in Industry, 60(1), 64-74, 2009. (SCI/EI)

Wei Zhao, Shuming Gao, Yusheng Liu, Hongwei Lin.

the effective reuse of freeform features represented by NURBS is still an open issue. In this paper, a novel approach to the reuse of freeform features with NURBS representation is proposed. Firstly, the conditions for preserving differential properties of reused freeform features are derived, and a reuse-oriented representation of freeform features is put forward. Based on them, a reuse algorithm of freeform features is developed, which adopts Poisson equation, knots insertion and degree elevation to achieve the preservation of the differential geometry properties and the adaptability. The approach is implemented and some examples are given.

A Simple Method for Approximating Rational Bezier Curve Using Bezier Curves. pdf

Computer Aided Geometric Design, 25(8), 697-699 , 2008. (SCI/EI)

Youdu Huang, Huaming Su, Hongwei Lin.

this paper presents a simple method for approximating a rational Bézier curve with Bézier curve sequence, whose control points are those of degree-elevated rational Bézier curves. It is proved that the derivatives with any given degree of the Bézier curve sequence constructed this way would niformly converge to the corresponding derivatives of the original rational Bézier curve.

Watertight trimmed NURBS. pdf

ACM transactions on Graphics, 27(3), 2008. (SCI/EI)

thomas W. Sederberg, G. Thomas Finnigan, Xin Li, Hongwei Lin, Heather Ipson.

this paper addresses the long-standing problem of the unavoidable gaps that arise when expressing the intersection of two NURBS surfaces using conventional trimmed-NURBS representation. the solution converts each trimmed NURBS into an untrimmed T-Spline, and then merges the untrimmed T-Splines into a single, watertight model. the solution enables watertight fillets of NURBS models, as well as arbitrary feature curves that do not have to follow isoparameter curves. the resulting T-Spline representation can be exported without error as a collection of NURBS surfaces.

Adaptive Patch-based Mesh Fitting in Reverse Engineering. pdf

Computer-Aided Design, 39(12), 1134-1142, 2007.12. (SCI/EI)

Hongwei Lin, Wei Chen, Hujun Bao

In this paper, we propose a novel adaptive mesh fitting algorithm that fits a triangular model with G1 smoothly stitching bi-quintic Bezier patches. Our algorithm first segments the input mesh into a set of quadrilateral patches, whose boundaries form a quadrangle mesh. For each boundary of each quadrilateral patch, we construct a normal curve and a boundary-fitting curve, which fit the normal and position of its boundary vertices respectively. By interpolating the normal and boundary-fitting curves of each quadrilateral patch with a Bezier patch, an initial G1 smoothly stitching Bezier patches is generated. We perform this patch-based fitting scheme in an adaptive fashion by recursively subdividing the underlying quadrilateral into four sub-patches. The experimental results show that our algorithm achieves precision-ensured Bezier patches with G1 continuity and meets the requirements of reverse engineering.

Generating strictly non-self-overlapping structured quadrilateral grids. pdf

Computer-Aided Design. 39(9), 709-718, 2007.9. (SCI/EI)

Hongwei Lin, Kai Tang, Ajay Joneja, Hujun Bao.

In this paper, we present a BPM (Bezier patch mapping) algorithm which generates a strictly non-self-overlapping structured quadrilateral grid in a given four-sided planar region. Given four pieces of polynomial curves which enclose a simple region in the plane, the algorithm first constructs a Bezier patch which interpolates the four curves (as its four boundary curves), while the inner control points of its control grid remain unknown. In this paper, we show that, for the bijective condition to be satisfied, it is sufficient that the interior points satisfy a set of quadratic inequality equations. Exploiting this key result, we formulate the mapping algorithm as an optimization problem where the constraints are the bijective condition of the Bezier patch mapping (BPM), and the objective is to find out the best from all of the non-self-overlapping grids. thus, commercial optimization solvers can be used to find the bijective mapping. If a solution to the optimization problems exists, then so does a solution to the mapping problem, and vice-versa. the BPM method is simple and intuitive, and some examples presented in this paper demonstrate its effectiveness.

A Robust Hole-Filling Algorithm for Triangular Mesh. pdf

the Visual Computer, 23(12), 987-997, 2007.12. (SCI/EI)

Wei Zhao, Shuming Gao, Hongwei Lin.

this paper presents a novel hole-filling algorithm that can fill arbitrary holes in triangular mesh models. First, the advancing front mesh technique is used to cover the hole with newly created triangles. Next, the desirable normals of the new triangles are approximated using our desirable normal computing schemes. Finally, the three coordinates of every new vertex are re-positioned by solving the Poisson equation based on the desirable normals and the boundary vertices of the hole. Many experimental results and error evaluations are given to show the robustness and efficiency of the algorithm.