Nonsplitting Macro Patches for Implicit Cubic Spline Surfaces

Macro patches are important for generating quadric or cubic implicit spline surfaces from the input of a polyhedron. All existing macro patches split the triangular facets of the polyhedron; this paper presents cubic nonsplitting macro patches (NMP) that do not split these facets. The NMP's are based on a necessary and sufficient condition for nonsplitting constructions of implicit cubic spline surfaces. This condition can be satisfied for most practical applications, so the NMP's lead to an efficient and powerful spline surface scheme using implicit cubics. The free parameters in an NMP are set using a new technique for excluding topological anomalies such as extraneous sheets, splits, unwanted holes, self-intersections, and unwanted handles. Each cubic patch obtained by this technique best approximates, in a least-squares sense, a quadric patch from a single algebraic component of a monotone polynomial derived from the input data.     

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

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

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

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

Material interface reconstruction

The paper presents an algorithm for material interface reconstruction for data sets where fractional material information is given as a percentage for each element of the underlying grid. The reconstruction problem is transformed to a problem that analyzes a dual grid, where each vertex in the dual grid has an associated barycentric coordinate tuple that represents the fraction of each material present. Material boundaries are constructed by analyzing the barycentric coordinate tuples of a tetrahedron in material space and calculating intersections with Voronoi cells that represent the regions where one material dominates. These intersections are used to calculate intersections in the Euclidean coordinates of the tetrahedron. By triangulating these intersection points, one creates the material boundary. The algorithm can treat data sets containing any number of materials. The algorithm can also create nonmanifold boundary surfaces if necessary. By clipping the generated material boundaries against the original cells, one can examine the error in the algorithm. Error analysis shows that the algorithm preserves volume fractions within an error range of 0.5 percent per material.     

Quadric and cubic bitetrahedral patches

Algebraic surface patches bounded by tetrahedra are promising building blocks for low-degree implicit spline surfaces. General algebraic surface patches may have topological anomalies such as singular points and multiple sheets. The A-patch technique avoids many of these anomalies but does not ensure that the surface patches are connected and have no holes. Requiring these qualities often places overly restrictive conditions on the patch. We present a technique for building a bitetrahedral patch that is single sheeted, smooth, and singly connected in a pair of face-adjacent tetrahedra. The bitetrahedral patch technique is applicable to most low-degree algebraic surface patches, and it establishes single sheetedness, smoothness, and single connectness when existing techniques fail.     

Bézier representation for cubic surface patches

The paper describes a new method for creating rectangular Bézier surface patches on an implicit cubic surface. Traditional techniques for representing surfaces have relied on parametric representations of surfaces, which, in general, generate surfaces of implicit degree 8 in the case of rectangular Bézier surfaces with rational biquadratic parameterization. The method constructs low-degree algebraic surface patches by reducing the implicit degree from 8 to 3. The construction uses a rectangular biquadratic Bézier control polyhedron that is embedded within a tetrahedron and satisfies a projective constraint. The control polyhedron and the resulting cubic surface patch satisfy all of the standard properties of parametric Bézier surfaces, including interpolation of the corners of the control polyhedron and the convex-hull property.     

Trimming implicit surfaces

Algorithms for trimming implicit surfaces yielding surface sheets and stripes are presented. These two-dimensional manifolds with boundaries result from set-theoretic operations on an implicit surface and a solid or another implicit surface. The algorithms generate adaptive polygonal approximation of the trimmed surfaces by extending our original implicit surface polygonization algorithm. The presented applications include modeling several spiral shaped surface sheets and stripes (based on M. Eschers artworks) and extraction of ridges on implicit surfaces. Another promising application of the presented algorithms is modeling heterogeneous objects as implicit complexes.     

一种跟踪隐式曲面交线的算法*

传统的跟踪方法在求下一个跟踪点时一般是采用迭代法,而迭代法会出现初始值的选取和迭代收敛的问题。为此提出一种跟踪隐式曲面交线的算法。该方法最主要的优点是：在跟踪隐式曲面的交线时,在前一个跟踪交点已经求得的情况下,利用正方形与两个隐式曲面的交点,即可快速有效地求出下一个跟踪点,而不用涉及迭代收敛的判断。     

Adaptive Sampling of Implicit Surfaces for Interactive Modelling and Animation

This paper presents a new adaptive sampling method for implicit surfaces that can be used in both interactive modelling and animation. The algorithm samples implicit objects composed of blending primitives and efficiently maintains this sampling over time, even when their topology changes (during fractures and fusions). It provides two complementary modes of immediate visualization: displaying “scales” lying on the surface, or a “primitive-wise” polygonization. The sampling method efficiently avoids unwanted blending between different parts of an object. Moreover, it can be used for partitioning an implicit surface into local bounding boxes that will accelerate collision detection during animation and ray-intersections during final rendering.     

隐式裁剪曲面的造型及绘制

隐式曲面没有参数域的概念,故对其裁剪问题的研究,很少有人问津.提出了一种隐式裁剪曲面的造型和绘制方法:先把投影平面变换到xy平面,将该xy平面作正交化网格剖分,由参数表示或隐式表示的裁剪曲线在该xy平面定义裁剪区域,再把裁剪后留下的区域内的网格投影到隐式曲面上,从而实现了隐式裁剪曲面的多边形化绘制.     

Adaptive Implicit Surface Polygonization Using Marching Triangles

This paper presents several improvements to the marching triangles algorithm for general implicit surfaces. The original method generates equilateral triangles of constant size almost everywhere on the surface. We present several modifications to adapt the size of the triangles to the curvature of the surface. As cracks may arise in the resulting polygonization, we propose a specific crack-closing method invoked at the end of the mesh growing step. Eventually, we show that the marching triangles can be used as an incremental meshing technique in an interactive modeling environment. In contrast to existing incremental techniques based on spatial subdvision, no extra data-structure is needed to incrementally edit skeletal implicit surfaces, which saves both memory and computation time.     

基于最佳圆弧样条逼近的快速距离曲面计算

距离曲面是一种常用的隐式曲面,它在几何造型和计算机动画中具有重要的应用价值,但以往往在对距离曲面进行多边形化时速较慢,为了提高点到曲线最近距离计算的效率,提出了一种基于最佳圆弧样条逼近的快速线骨架距离曲面计算方法,该算法对于一条任意的二维NURBS曲线,在用户给定的误差范围内,先用最少量的圆弧样条来逼近给定的曲线,从而把点到NURBS曲线最近距离的计算问题转化为点到圆弧样条最近距离的计算问题,由于在对曲面进行多边形化时,需要大量的点到曲线最近距离的计算,而该处可以将点到圆弧样条最近距离很少的计算量来解析求得,故该算法效率很高,该实验表明,算法简单实用,具有很大的应用价值。     

Polygonization of implicit surfaces with sharp features by edge-spinning

This paper presents an adaptive approach for polygonization of implicit surfaces. The algorithm generates a well-shaped triangular mesh with respect to a given approximation error. The error is proportional to a local surface curvature estimation. Polygonization of surfaces of high curvature, as well as surfaces with sharp features, is possible using a simple technique combined with a particle system approach. The algorithm is based on a surface tracking scheme, and it is compared with other algorithms based on a similar principle, such as the marching cube and the marching triangle algorithms.     

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

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

基于网格优化的隐式曲面自适应多边形化

隐式曲面多边形化是隐式曲面绘制的一种常用算法.基于网格优化的隐式曲面快速自适应多边形化算法,首先用多边形化算法生成一个粗糙的初始网格,再利用网格优化方法从网格顶点位置、规则性和网格法向三个方面对粗糙网格进行调整,最后根据网格的局部曲率用多边形细分策略细分优化后的网格.实验结果表明,该算法在网格生成速度和网格规则性上都胜于Marching Cubes的多边形化算法,恢复的隐式曲面能较好地反映形状特征.     

Incremental Polygonization of Implicit Surfaces

This paper describes an incremental polygonization technique for implicit surfaces built from skeletal elements. Our method is dedicated to fast previewing in an interactive modeling system environment. We rely on an octree decomposition of space combined with Lipschitz conditions to recursively subdivide cells until a given level of precision is reached and converge to the implicit surface. We use a trilinear interpolation approximation of the field function to create a topologically consistent tessellation characterized by an adjacency graph. Our algorithm aims at updating the mesh locally in regions of space where changes in the potential field occurred. Therefore, we propose an octree inflating and deflating strategy to preserve the octree structure as much as possible and to avoid useless or redundant computations. Timings show that our incremental algorithm dramatically speeds up the overall polygonization process for complex objects.     

Adaptive polygonization of geometrically constrained surfaces

n -dimensional space, where n>3. This definition can be used for given surfaces that are implicit or parametric. This paper presents a robust, adaptive polygonization algorithm for evaluating and visualizing geometrically constrained surfaces. Let be the constrained surface, a 2-surface in n-space, and let π() be its projection into the subspace spanned by the first three coordinates. Our polygonization algorithm computes π(). The method works directly with the n-space representation, but performs all major computations in 3-space. Techniques for triangulation, polygon decimation, and local refinement are also presented.     

Interactive Visualization of Implicit Surfaces with Singularities

This paper presents work on two methods for interactive visualization of implicit surfaces: physically-based sampling using particle systems and polygonization followed by physically-based mesh improvement which explicitly makes use of the surface-defining equation. While most previous work applied to bounded manifolds without singularities and without boundary (topological spheres) we broaden the scope of the methods to include surfaces with such features, in particular cusp points and surface self-intersections. These aspects are not (yet) essential for computer graphics modelling with implicit surfaces but they naturally occur in simulations of interest in mathematical visualization. In this paper we use the Kummer family of algebraic surfaces as an example.     

3维图像中边界曲面的分类追踪及抽取

3维图像分析中,边界曲面的检测与重构是一个非常重要的问题。已有的连续隐边界曲面的抽取及逼近计算技术存在着把某些零交叉曲面片错误地识别为边界曲面片的缺陷。为此,提出一个新的边界曲面的追踪及抽取的方法。该方法首先将包含边界曲面的全部立方体分为两类:包含一个连通零交叉曲面片的立方体叫第1类边缘立方体,包含两个及其以上不连通零交叉曲面片的立方体叫第2类边缘立方体;然后根据边界曲面的连续性连通性,便可追踪出两类边缘立方体;对于追踪出的第1类边缘立方体直接提取边界曲面片,对于追踪出的第2类边缘立方体的边界曲面片通过其相邻的第1类边缘立方体来提取。实验结果表明本文方法是可行有效的,而且可以有效地克服已有技术的缺陷。     

Cutting cubesvisualizing implicit surfaces by adaptive polygonization

A method for visualizing implicit surfaces is discussed. This method makes as few assumptions as possible concerning the surface and representation of its defining function. The surface may contain singularities, for instance, because it has self-intersections or it is reducible. A userdefined part of space is filled by a set of cubes, cutting pieces (called facets) off the surface. The set of cubes is controlled by an octree converging to the surface. The set of resulting facets can be taken as a piecewise linear approximation, which is sufficiently close to the given surface with respect to criteria specified by the user. Finally, some examples obtained with this method are presented.