A novel algorithm for explicit optimal multi-degree reduction of triangular surfaces

This paper introduces the algebraic property of bivariate orthonormal Jacobi polynomials into geometric approximation. Based on the latest results on the transformation formulae between bivariate Bernstein polynomials and Jacobi polynomials, we naturally deduce a novel algorithm for multi-degree reduction of triangular B~zier surfaces. This algorithm possesses four characteristics： ability of error forecast, explicit expression, less time consumption, and best precision. That is, firstly, whether there exists a multi-degree reduced surface within a prescribed tolerance is judged beforehand; secondly, all the operations of multi-degree reduction are just to multiply the column vector generated by sorting the series of the control points of the original surface in lexicographic order by a matrix; thirdly, this matrix can be computed at one time and stored in an array before processing degree reduction; fourthly, the multi-degree reduced surface achieves an optimal approximation in the norm L2. Some numerical experiments are presented to validate the effectiveness of this algorithm, and to show that the algorithm is applicable to information processing of products in CAD system.     

Multi-degree reduction of NURBS curves based on their explicit matrix representation and polynomial approximation theory

NURBS curve is one of the most commonly used tools in CAD systems and geometric modeling for its various specialties, which means that its shape is locally adjustable as well as its continuity order, and it can represent a conic curve precisely. But how to do degree reduction of NURBS curves in a fast and efficient way still remains a puzzling problem. By applying the theory of the best uniform approximation of Chebyshev polynomials and the explicit matrix representation of NURBS curves, this paper gives the necessary and sufficient condition for degree reducible NURBS curves in an explicit form. And a new way of doing degree reduction of NURBS curves is also presented, including the multi-degree reduction of a NURBS curve on each knot span and the multi-degree reduction of a whole NURBS curve. This method is easy to carry out, and only involves simple calculations. It provides a new way of doing degree reduction of NURBS curves, which can be widely used in computer graphics and industrial design.     

Discrete Interpolation Surface

In this paper,a method to construct a surface with point interpolation and normal interpolation is presented.An algorithm to construct the discrete interpolation is also presented,which has the time complexity O(Nlog N),where N in the number of scattered points.     

Hyperfinite Interpolation, Wu s Method and Blendingof Implicit Algebraic Surfaces

One of the central questions in CAGE^[1] is blending surfaces which provides the theoretical basis for the design technology of space surfaces.We will discuss the general theories and algorithms for multivariate hyperfinite interpolation and their application to the blending of implicit algebraic surfaces,and investigate the existence conditions of hyperfinite interpolation.Based on Wu‘s theory on blending implicit algebraic surfaces,the problem of blending two quadric surfaces is studied.The conditions for the coefficient of gi under which there exists the cubic blending surface S(f) (the lowest degree)are obtained and the concrete expressions of f are presented is they exist.These results can be applied directly to CAGD.     

A new method of mesh simplification for 3-Dimension terrain using Laplace operator

This paper proposes a new method to simplify mesh in 3D terrain.The 3D terrain is presented by digital elevation model.First,Laplace operator is introduced to calculate sharp degree of mesh point,which indicates the variation trend of the terrain.Through setting a critical value of sharp degree,feature points are selected.Second,critical mesh points are extracted by an recursive process,and constitute the simplified mesh.Third,the algorithm of linear-square interpolation is employed to restore the characteristics of the terrain.Last,the terrain is rendered with color and texture.The experimental results demonstrate that this method can compress data by 16% and the error is lower than 10%.     

CIM algorithm for approximating three-dimensional polygonal curves

The polygonal approximation problem is a primary problem in computer graphics,pattern recognition,CAD/CAM,etc.In R^2,the cone intersection method(CIM) is one of the most efficient algorithms for approximating polygonal curves,With CIM Eu and Toussaint,by imposing an additional constraint and changing the given error criteria,resolve the three-dimensional weighted minimum number polygonal approximation problem with the parallel-strip error criterion(PS-WMN)under L2 norm.In this paper,without any additional constraint and change of the error criteria,a CIM solution to the same problem with the line segment error criterion(LS-WMN)is presented,which is more frequently encountered than the PS-WMN is .Its time complexity is O(n^3),and the space complexity is O(n^2) .An approximation algorithm is also presented,which takes O(n^2) time and O(n) space.Results of some examples are given to illustrate the efficiency of these algorithms.     

A new mesh simplification algorithm based on triangle collapses

In this paper a new mesh simplification algorithm based on triangle collapses is presented.The algorithm can provide efficient error management and simplify the original mesh greatly.Progressive meshes may be constructed with triangle collapsing operation.To make continuous transition between level of detail (LOD) models possible,a method for interpolating is also presented.Examples illustrate the efficiency of the algorithm.     

New algorithm for 3D facial model reconstruction and its application in virtual reality

3D human face model reconstruction is essential to the generation of facial animations that is widely used in the field of virtual reality (VR). The main issues of 3D facial model reconstruction based on images by vision technologies are in twofold: one is to select and match the corresponding features of face from two images with minimal interaction and the other is to generate the realistic-looking human face model. In this paper, a new algorithm for realistic-looking face reconstruction is presented based on stereo vision. Firstly, a pattern is printed and attached to a planar surface for camera calibration, and corners generation and corners matching between two images are performed by integrating modified image pyramid Lucas-Kanade (PLK) algorithm and local adjustment algorithm, and then 3D coordinates of corners are obtained by 3D reconstruction. Individual face model is generated by the deformation of general 3D model and interpolation of the features. Finally, realistic-looking human face model     

A Radiosity Solution for Curved Surface Environments

Radiosity has been a popular method for photorealistic image generation.But the determination of form factors between curved patches is the most difficult and time consuming procedure,and also the errors caused by approximating source patch‘s radiosity with average values are obvious.In this paper,a radiosity algorithm for rendering curved surfaces represented by parameters is described.The contributed radiosity from differential areas on four vertices of the source patch to a receiving point is calculated firstly,then the contribution from the inner area of the source patch is evaluated by interpolating the values on four corners.Both the difficult problem of determining form-factors between curved surfaces and errors mentioned above have been avoided.Comparison of the experimental results using the new algorithm has been made with the ones obtained by traditional method.Some associated techniques such as the visibility test and the adaptive subdivision are also described.     

广义快子系统的H∞最优模型降阶

In this paper, H∞ optimal model reduction for singular fast subsystems will be investigated. First, error system is established to measure the error magnitude between the original and reduced systems, and it is demonstrated that the new feature for model reduction of singular systems is to make H_ norm of the error system finite and minimal. The necessary and sufficient condition is derived for the existence of the H∞ suboptimal model reduction problem. Next, we give an exact and practicable algorithm to get the parameters of the reduced subsystems by applying the matrix theory. Meanwhile, the reduced system may be also impulsive. The advantages of the proposed algorithm are that it is more flexible in a straight-forward way without much extra computation, and the order of the reduced systems is as minimal as possible. Finally, one illustrative example is given to illustrate the effectiveness of the proposed model reduction approach.     

张量积Bézier曲面降多阶逼近

给出了一种基于最小二乘范数下的Bézier曲面降多阶逼近误差的矩阵计算公式。根据带角点高阶插值条件下原张量积Bézier曲面与降多阶张量积Bézier曲面的误差函数在[0,1]x[0,1]上取极小值,得到降多阶张量积Bézier曲面的控制顶点的矩阵表达式。通过数值例子显示采用该方法所得的降多阶曲面对原曲面有较好的逼近效果。将Bézier曲线降阶逼近的迭代方法推广到曲面,得到曲面降阶逼近的迭代方法,并给出了相应的数值实例。     

带端点插值条件的Bézier曲线降多阶逼近

研究了两端点具有任意阶插值条件的Bézier曲线降多阶逼近的问题.对于给定的首末端点的各阶插值条件,给出了一种新的一次降多阶逼近算法,应用Chebyshev多项式逼近理论达到了满足端点插值条件下的近似最佳一致逼近.此算法易于实现,误差计算简单,且所得降阶曲线具有很好的逼近效果,结合分割算法,可获得相当高的误差收敛速度.     

GC^1约束的三角Bézier曲面降阶逼近研究

研究给定的n次三角Bézier曲面在L2范数下的一次降多阶的逼近问题,给出了在无约束条件下的三角Bézier曲面降阶求解的详细过程,将降阶问题转化为非线性最优化问题求解,并将降阶过程与曲面的几何连续拼接结合在一起,给出了降阶同时满足GC^1拼接的实现过程。实验结果表明,该方法简单实用,降阶逼近效果好。     

有理曲线曲面的降阶逼近

基于齐次坐标空间，提出了一种NURBS曲线曲面和有理Bezier曲线曲面降阶的简便方法。在齐次坐标空间中，使降阶后的曲线曲面与原曲线曲面的差的L2范数达到极小，将有理曲线曲面降多阶问题转化为二次规划问题求解，并给出了误差估计。实验结果表明，该方法计算速度快，降阶逼近效果好。     

Said-Bézier型广义Ball曲线显式降多阶

给出了计算Said-Bézier型广义Ball曲线(SBGB曲线)在L₂范数下保持端点约束的一种最佳降多阶算法.基于SBGB基函数、幂基函数和Jacobi基函数之间的相互转换关系,得到了SBGB基函数和Jacobi基函数之间的显式转换矩阵;进一步利用Jacobi基的正交性和上述转换矩阵的逆矩阵,导出了SBGB曲线在L₂范数下的显式约束降多阶算法.此算法蕴含了Said-Ball曲线、Bézier曲线以及位置介于这两类曲线之间的一大类参数曲线的相应降多阶算法.证明了这是一种可以预报最佳误差且满足端点高阶约束的一次性降多阶算法.最后用数值实例说明了算法的正确性和优越性.     

An algorithm for the interpolation of hybrid curves

Real time tool path generation consists of off-line design and real time interpolation of tool paths. An hybrid curve is the intersection of a parametric surface and an implicit surface. Previous work in tool path interpolation focused mainly in the interpolation of parametric curves. Tool paths designed by drive surface methods are hybrid curves which, in general, cannot be represented as parametric curves. An algorithm for the interpolation of hybrid curves is proposed in this paper. The algorithm is based on interpolation of the projection of the hybrid curve into the parametric domain. Each increment involves a second-order interpolation step augmented by iterative error reduction.Simulations of hybrid curve interpolation have been carried out. They are based on practical surfaces represented as NURB surfaces and implicit surfaces including a plane, a cylinder and a high order algebraic surface. They demonstrate that under typical machining conditions, interpolation error is well within the accuracy requirements of typical machining and that the use of one iteration error reduction can significantly reduce the path deviation. These show that the proposed algorithm is potentially useful for tool path interpolation for the machining of parametric surfaces.     

Constructing triangular patch by basic approximation operator plus additional interpolation operator

~~Constructing triangular patch by basic approximation operator plus additional interpolation operator1. Barahill, R. E., Birkhoff, G., Gordon, W. J., Smooth interpolation in triangles, J. Approx. Theory, 1973, 8: 114-128. 2. Gregory, J. A., Smooth interpolation without twist constraints, in Computer Aided Geometric Design (eds. Barn-hill, R. E., Riesenfeld, R. R), New York: Academic Press, 1974, 71-88. 3. Charrot, P., Gregory, J. A., A pentagonal surface patch for comput…     

区间三角Bézier曲面的降阶逼近

给出了高次区间B-B(Bernstein-Bézier)曲面的降阶逼近算法.这里主要采用了线性规划方法,对降一阶情况还给出了分析求解方法.降阶逼近的结果可用于满足不同CAD系统之间数据转换的需要,也可用于节省一些几何操作的计算时间.