隐式曲面的快速适应性多边形化算法

通过将隐式曲面多边形化过程分为“构造”和“适应性采样”两个阶段，实现了隐式曲面多边形逼近网格的适应性构造．通过基于空间延展的Marching Cubes方法得到隐式曲面较为粗糙的均匀多边形化逼近，根据曲面上的局部曲率分布，运用适应性细分规则对粗糙网格进行细分迭代，并利用梯度下降法将细分出的新顶点定位到隐式曲面上；最终得到的多边形网格是适应性的单纯复形网格，其在保持规定逼近精度的前提下，减少了冗余三角形的产生，网格质量有明显改善．该算法可用于隐式曲面的交互式可视化过程．     

基于凸凹性的网格细分综合优化

实际工程中希望表示物体的三角形网格形状优良,同时拓扑逼近真实曲面。但是对非均匀离散点云重建得到的网格进行优化时,这两个标准常常是相互矛盾的。该文针对在实际工程中遇见的这个问题,提出一种结合全局特征以及局部特性的细分算法。该算法避免了一般细分方法对凹区域处理出现的折叠现象,可以获取三角形形状和空间拓扑的综合优化解。最后通过对于工程应用实例的细分计算,得到了与原始网格拓扑一致,但更逼近真实曲面的细分优化网格,表明了所提出简化算法的有效性。     

隐式曲面的多分辨率法向网格逼近

法向网格是一种新型的曲面多分辨率描述方式，其中每个层次都可以表示为其前一个粗糙层次的法向偏移．文中提出一种基于法向网格表示的隐式曲面多分辨率网格逼近算法．首先通过基于空间剖分技术的多边形化算法获得隐式曲面的粗糙逼近网格，并利用网格均衡化方法对粗糙网格进行优化，消除其中的狭长三角形；然后利用法向细分规则迭代地对网格中的三角面片进行细分，并利用区间算术技术沿法向方向对隐式曲面进行逼近．最终生成的隐式曲面分片线性逼近网格为法向网格．该逼近网格为隐式曲面提供了一种多分辨率表示，网格具有细分连通性，其数据量较传统的多边形化算法所生成的网格有大幅度的压缩．该算法可用于隐式曲面的多级绘制、累进传输及相关数字几何处理．     

细分曲面求交裁剪算法研究

基于细分曲面的参数化表示,研究了细分曲面的精确求交、裁剪算法。首先对控制网格建立局部坐标系,将细分曲面表示为一系列小的面片,并对每个控制顶点赋予参数值。然后用改进的轮廓删除法细分控制网格,在关联曲面间进行相交性检测,得到近似交点及其参数值,再用迭代法求得精确解。根据用户指定的裁剪区域确定交线的走向,将被裁剪曲面的控制网格面分为保留面、裁剪面和删除面,设置每个裁剪面的裁剪域,从而实现细分曲面的精确裁剪。算例表明,该文的方法简单、有效。     

基于边光滑度的Loop自适应细分曲面算法

首先研究了传统的Loop细分曲面算法,通过分析发现随着细分次数的增多细分算法中三角形网格片数增长过快。针对这一问题提出一种自适应细分曲面算法。算法根据相邻两个三角形面上的法向量的夹角,判断细分网格中较为光滑和非光滑的区域。实验结果表明,算法提高了数据处理速度,并且模型简单易实现。     

具有特殊效果的混合细分方法

提出了基于三角形和四边形的混合控制网格的细分曲面尖锐特征、半尖锐特征生成和控制方法,避免了已有方法仅局限于初始控制网格为单一的三角形或单一的四边形网格的缺陷.通过局部修改混合细分规则,在光滑混合曲面上产生了刺、尖、折痕、角的尖锐特征效果,并对尖锐特征处局部细分矩阵进行了详细的特征分析,讨论了极限曲面的收敛性及光滑性.同时,用特征处的离散曲率来控制特征处的尖锐程度,实现了半尖锐的特征效果,并通过自适应细分方法,把尖锐特征、半尖锐特征的生成统一起来.该方法具有多分辨率表示能力强、局部性好、简单易操作的特点.实验结果表明,该算法效果好,成功地解决了混合曲面特殊效果生成问题.     

壳空间剖分的隐式曲面三角化

提出了一种曲率自适应的壳空间剖分隐式曲面三角形化新方法.新方法首先采用粒子系统对隐式曲面进行采样,通过高斯曲率约束粒子的生成,使生成的网格模型在曲率大的区域具有较多的小三角形,在曲率小的区域具有较少的大三角形,从而使网格模型更好地逼近隐式曲面.新方法在每个采样粒子处沿曲面法线正负方向延伸适当距离得到两个附加点,对所有附加点进行四面体化形成对隐式曲面逼近的壳空间四面体网格,在每个壳空间四面体中抽取三角形,所有抽取的三角形拼合得到隐式曲面的三角网格表示.与以往方法相比,新的三角网格化方法更具有鲁棒性,可一次性获得高质量的三角形网格.最后给出了对常用隐式曲面进行三角化的实例比较,显示了新方法的有效性.     

混合网格的可调细分算法

论文主要研究混合网格的曲面细分问题,提出了一种带有可调参数的细分算法。该算法适用于多边形网格、三角形网格,以及两者的混合网格情形,且对开的和闭的拓扑结构都能进行处理。由于在算法中引入了可调参数,这样既可产生光滑曲面,也可产生具有尖锐特征的曲面,且通过调整参数还可产生标准的Catmull-Clark细分和Loop细分。另外,实现该算法不需要复杂的数据结构。     

反求工程中的隐式曲面快速自适应性多边形算法

论文给出一种反求工程中基于三角形细分的隐式曲面快速自适应性多边形化方法。该文先由输入的三维扫描数据点利用空间延展的MarchingCubes方法得到隐式曲面较为粗糙的三角形表面网格形状,再利用该文的自适应性优化方法对粗糙网格从三个方面自适应性调整,即调整网格顶点法向,控制曲率,再补偿网格抽样率。从而生成的三角网格和采样点具有局部适应性,能随着曲率的变化自动控制采样点的疏密程度,消除了逼近网格中的T-形边。实验表明,恢复的隐式曲面能很好地反映形状特征,能满足反求工程的实时需求。     

六角形网格细分曲面算法介绍

细分曲面算法通常采用三角形、四角形面片，最近基于六角形面片的细分算法成为研究的热点。六角形在其他领域的应用已经取得了良好的效果，这为其在细分领域的应用打下了良好的基础。本文分别讨论了三种六角形网格细分曲面算法，并对三者进行了比较。由于在实际应用中，六角形网格并不经常遇到，所以我们还讨论了两种不同的三角形到六角形的转变技术。     

A Shrink Wrapping Approach to Remeshing Polygonal Surfaces

Due to their simplicity and flexibility, polygonal meshes are about to become the standard representation for surface geometry in computer graphics applications. Some algorithms in the context of multiresolution representation and modeling can be performed much more efficiently and robustly if the underlying surface tesselations have the special subdivision connectivity. In this paper, we propose a new algorithm for converting a given unstructured triangle mesh into one having subdivision connectivity. The basic idea is to simulate the shrink wrapping process by adapting the deformable surface technique known from image processing. The resulting algorithm generates subdivision connectivity meshes whose base meshes only have a very small number of triangles. The iterative optimization process that distributes the mesh vertices over the given surface geometry guarantees low local distortion of the triangular faces. We show several examples and applications including the progressive transmission of subdivision surfaces.     

Polynomial surfaces interpolating arbitrary triangulations

Triangular Bezier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous triangular Bezier patches of degree five. The resulting surface has an explicit closed form representation and is defined locally. In this paper, we introduce a new method for visually smooth interpolation of arbitrary triangle meshes based on a regular 4-split of the domain triangles. Ensuring tangent plane continuity of the surface is not enough for producing an overall fair shape. Interpolation of irregular control-polygons, be that in 1D or in 2D, often yields unwanted undulations. Note that this undulation problem is not particular to parametric interpolation, but also occurs with interpolatory subdivision surfaces. Our new method avoids unwanted undulations by relaxing the constraint of the first derivatives at the input mesh vertices: The tangent directions of the boundary curves at the mesh vertices are now completely free. Irregular triangulations can be handled much better in the sense that unwanted undulations due to flat triangles in the mesh are now avoided.     

An Algorithm for Parametric Quadric Patch Construction

An algorithm for constructing arbitrary parametric quadratic quadric triangles in rational Bézier form is presented. The algorithm does not require the knowledge of the underlying quadric, an important property in view of applying this method for the interpolation of triangulated 3D data points. The algorithm consists of four steps starting with the arbitrary choice of the three corner points and corner weights of the patch, by then constructing a certain triangle and a tetrahedron by means of which the remaining inner control points and weights are obtained guaranteeing the resulting patch to lie on a quadric surface.     

Adaptive polygonization of parametric surfaces

This paper describes an algorithm for dividing a (u, v)-parametric surface into the least possible number of plane triangular elements that closely follow the surface they approximate. The concept, of closeness defined here is based on a set of three subdivision criteria: unit-normal criterion, chord-distance criterion, and edge-refinement criterion.The triangles generated by the subdivision, together with the unit normals at their vertices, serve as input to the ray-tracing program, which generates a shaded image of the surface with photographic realism.     

Method for intersecting algebraic surfaces with rational polynomial patches

The paper presents a hybrid algorithm for the computation of the intersection of an algebraic surface and a rational polynomial parametric surface patch. This algorithm is based on analytic representation of the intersection as an algebraic curve expressed in the Bernstein basis; automatic computation of the significant points of the curve using numerical techniques, subdivision and convexity properties of the Bernstein basis; partitioning of the intersection domain at these points; and tracing of the resulting monotonic intersection segments using coarse subdivision and faceting methods coupled with Newton techniques. The algorithm described in the paper treats intersections of arbitrary order algebraic surfaces with rational biquadratic and bicubic patches and introduces efficiency enhancements in the partitioning and tracing parts of the solution process. The algorithm has been tested with up to degree four algebraics and bicubic patches.     

A parallelized surface extraction algorithm for large binary image data sets based on an adaptive 3D delaunay subdivision strategy

In this paper we describe a novel 3D subdivision strategy to extract the surface of binary image data. This iterative approach generates a series of surface meshes that capture different levels of detail of the underlying structure. At the highest level of detail, the resulting surface mesh generated by our approach uses only about 10% of the triangles in comparison to the marching cube algorithm (MC) even in settings were almost no image noise is present. Our approach also eliminates the so-called "staircase effect" which voxel based algorithms like the MC are likely to show, particularly if non-uniformly sampled images are processed. Finally, we show how the presented algorithm can be parallelized by subdividing 3D image space into rectilinear blocks of subimages. As the algorithm scales very well with an increasing number of processors in a multi-threaded setting, this approach is suited to process large image data sets of several gigabytes. Although the presented work is still computationally more expensive than simple voxel-based algorithms, it produces fewer surface triangles while capturing the same level of detail, is more robust towards image noise and eliminates the above-mentioned "staircase" effect in anisotropic settings. These properties make it particularly useful for biomedical applications, where these conditions are often encountered.     

Dynamically refining animated triangle meshes for rendering

We present a method to dynamically apply local refinements to an irregular triangle mesh as it deforms in real time. The method increases surface smoothness in regions of high deformation by splitting triangles in a fashion similar to one or two steps of Loop subdivision. The refinement is computed for an arbitrary triangle mesh, and the subdivided triangles are simply passed to the rendering engine, leaving the mesh itself unchanged. The algorithm can thus be easily plugged into existing systems to enhance the visual appearance of animated meshes. The refinement step has very low computational overhead and is easy to implement. We demonstrate the use of the algorithm in a physics-based facial animation system.     

An Arbitrary Triangular Bezier Sudivision Slgorithm and its Applications

ＡＮＡＲＢＩＴＲＡＲＹＴＲＩＡＮＧＵＬＡＲＢＥＺＩＥＲＳＵＢＤＩＶＩＳＩＯＮＡＬＧＯＲＩＴＨＭＡＮＤＩＴＳＡＰＰＬＩＣＡＴＩＯＮＳＬｕＸｉａｏｌｉｎ；ＭａＬｉｚｈｕａｎｇ；ＨｅＺｈｉｊｕｎＡＮＡＲＢＩＴＲＡＲＹＴＲＩＡＮＧＵＬＡＲＢＥＺＩＥＲＳＵＢＤ...     

General triangular midpoint subdivision

In this paper, we introduce triangular subdivision operators which are composed of a refinement operator and several averaging operators, where the refinement operator splits each triangle uniformly into four congruent triangles and in each averaging operation, every vertex will be replaced by a convex combination of itself and its neighboring vertices. These operators form an infinite class of triangular subdivision schemes including Loop's algorithm with a restricted parameter range and the midpoint schemes for triangular meshes. We analyze the smoothness of the resulting subdivision surfaces at their regular and extraordinary points by generalizing an established technique for analyzing midpoint subdivision on quadrilateral meshes. General triangular midpoint subdivision surfaces are smooth at all regular points and they are also smooth at extraordinary points under certain conditions. We show some general triangular subdivision surfaces and compare them with Loop subdivision surfaces.     

基于曲面精确表示的距离极值点的计算及在刀具干涉检测中的应用

针对基于曲面精确表示的刚体碰撞检测中裁剪曲面距离极值点的求解问题,提出了 利用平面向量场估计初始曲面距离极值点的方法,避免了曲面过度细分,讨论了距离极值点满足 的微分几何条件,给出了解析曲面/参数曲面、参数曲面/参数曲面、点/参数曲面和曲线/参数曲面 的距离极值点迭代算法。实例验证分析了该算法的高效性和可靠性。