Rendering the intersections of implicit surfaces

We present algorithms for rendering the intersection curves of implicit surfaces using octree-based recursive space subdivision techniques. Interval techniques used during the subdivision process increase the algorithms' robustness.     

Point-Based Rendering of Non-Manifold Surfaces

We are concerned with producing high‐quality images of parametric and implicit surfaces, in particular those with non‐manifold features. We present a point‐based technique for rendering implicit surfaces that uses octree spatial subdivision with a natural interval exclusion test that guarantees that no parts of the surface are missed. This allows us to render non‐manifold implicit surfaces at speeds comparable to parametric surfaces. We also derive criteria that guarantee complete pixel coverage of the surface. The point‐based method allows for hidden surface elimination using a z‐buffer, and shadow casting using a shadow buffer. We illustrate the technique with a number of surfaces, and discuss its advantages and disadvantages.     

Novel Techniques for Robust Voxelization and Visualization of Implicit Surfaces

Voxelization is the transformation of geometric surfaces into voxels. Up to date this process has been done essentially using incremental algorithms. Incremental algorithms have the reputation of being efficient but they lack an important property: robustness. The voxelized representation should envelop its continuous model. However, without robust methods this cannot be guaranteed. This article describes novel techniques of robust voxelization and visualization of implicit surfaces. First of all our recursive subdivision voxelization algorithm is reviewed. This algorithm was initially inspired by Duff's image space subdivision method. Then, we explain the algorithm to voxelize implicit surfaces defined in spherical or cylindrical coordinates. Next, we show a new technique to produce infinite replications of implicit objects and their voxelization method. Afterward, we comment on the parallelization of our voxelization procedure. Finally we present our voxel visualization algorithm based on point display. Our voxelization algorithms can be used with any data structure, thanks to the fact that a voxel is only stored once the last subdivision level is reached. We emphasize the use of the octree, though, because it is a convenient way to store the discrete model hierarchically. In a hierarchy the discrete model refinement is simple and possible from any previous voxelized scene thanks to the fact that the voxelization algorithms are robust.     

一种基于八叉树空间剖分技术的光线跟踪算法

光线跟踪算法是生成真实感图形的主要算法之一。为了提高光线追踪速度,在研究和比较各种光线跟踪算法的基础上,提出了一种基于八叉树数据结构的光线追踪算法。并结合基于重心坐标系的快速求交算法来提高光线跟踪的求交效率,使用重心坐标来表示包含三角形面片的参数平面,不用像三角形顶点一样需要长期存储,能够快速判定光线与三角形是否相交并计算出交点。实验结果表明,该算法能够在保证图像质量的同时提高绘制速度。     

Recursive subdivision without the convex hull property

Recursive subdivision is a standard technique in computer aided geometric design for intersecting and rendering curves and surfaces. The convergence of recursive subdivision is critical for its effective use. Bézier and B-spline curves and surfaces have recursive subdivision algorithms that are known to converge. We show more generally that if a recursive subdivision algorithm exists for a given curve or surface type, then convergence is guaranteed if the blending functions are continuous, form a partition of unity, and are linearly independent. Thus, convergence of recursive subdivision does not depend on the convex hull property. We also show that even in the absence of the convex hull property, it is possible to define termination tests based on the flatness of control polygons, and to construct intersection algorithms based on recursive subdivision. Examples are given of polynomial curves to which our theorems apply.     

Detection of loops and singularities of surface intersections

Two surface patches intersecting each other generally at a set of points (singularities), form open curves or closed loops. While open curves are easily located by following the boundary curves of the two patches, closed loops and singularities pose a robustness challenge since such points or loops can easily be missed by any subdivision or marching-based intersection algorithms, especially when the intersecting patches are flat and ill-positioned. This paper presents a topological method to detect the existence of closed loops or singularities when two flat surface patches intersect each other. The algorithm is based on an oriented distance function defined between two intersecting surfaces. The distance function is evaluated in a vector field to identify the existence of singular points of the distance function since these singular points indicate possible existence of closed intersection loops. The algorithm detects the existence rather than the absence of closed loops and singularities. This algorithm requires general C² parametric surfaces.     

Fast Ray Tracing of Arbitrary Implicit Surfaces with Interval and Affine Arithmetic

Existing techniques for rendering arbitrary-form implicit surfaces are limited, either in performance, correctness or flexibility. Ray tracing algorithms employing interval arithmetic (IA) or affine arithmetic (AA) for root-funding are robust and general in the class of surfaces they support, but traditionally slow. Nonetheless, implemented efficiently using a stack-driven iterative algorithm and SIMD vector instructions, these methods can achieve interactive performance for common algebraic surfaces on the CPU. A similar algorithm can also be implemented stacklessly, allowing for efficient ray tracing on the GPU. This paper presents these algorithms, as well as an inclusion-preserving reduced affine arithmetic (RAA) for faster ray-surface intersection. Shader metaprogramming allows for immediate and automatic generation of symbolic expressions and their interval or affine extensions. Moreover, we are able to render even complex forms robustly, in real-time at high resolution .     

Filling trim cracks on GPU-rendered solid models

We present an algorithm for improving the rendering appearance of CAD models with trimmed freeform surfaces when evaluated on graphics processing units (GPUs). Rendering on client GPUs allows mechanical CAD to embrace cloud computing by storing a single auto-synchronized model file in the cloud and transferring only minimal data (control points, trim curves, etc.) to the client nodes for local evaluation/rendering. However, current parallel algorithms that directly evaluate and render trimmed surfaces by masking the trims, without tessellating along the trim curves, suffer from “cracks” along the trim boundaries. We have developed a hybrid CPU–GPU algorithm to remove these artifacts in the rendering stage for a smooth, color- and shading-matched appearance. After dynamically detecting the cracks, our algorithm selectively fills in the affected pixels using a GPU fragment program, while avoiding artifacts at silhouettes. We have implemented this algorithm to demonstrate improvements in the appearance of solid models directly evaluated and rendered on the GPU.     

大规模三维云实时模拟方法

针对虚拟环境中大规模三维云渲染开销大的问题,提出一种大规模三维云实时模拟方法.在云建模方面,利用Navier-Stokes流体力学公式模拟云的动态生成,提出一种基于八叉树的模型化简策略,减少了云模型粒子数;在渲染阶段,提出一种基于Cell的绘制更新策略,结合Impostor技术自动混合绘制三维云与Impostor,实现了大规模三维云的实时模拟.实验结果表明,该方法基于物理的方法模拟云,同时在绘制阶段根据视点的移动实时更新,效果逼真;与同类方法相比,基于Cell的绘制策略更新时计算量更小,有效地避免了绘制更新时常见的抖动和跳变问题.     

Cutting and stitching: converting sets of polygons to manifoldsurfaces

Many real-world polygonal surfaces contain topological singularities that represent a challenge for processes such as simplification, compression, and smoothing. We present an algorithm that removes singularities from nonmanifold sets of polygons to create manifold (optionally oriented) polygonal surfaces. We identify singular vertices and edges, multiply singular vertices, and cut through singular edges. In an optional stitching operation, we maintain the surface as a manifold while joining boundary edges. We present two different edge stitching strategies, called pinching and snapping. Our algorithm manipulates the surface topology and ignores physical coordinates. Except for the optional stitching, the algorithm has a linear complexity and requires no floating point operations. In addition to introducing new algorithms, we expose the complexity (and pitfalls) associated with stitching. Finally, several real-world examples are studied     

Algebraic pruning: a fast technique for curve and surface intersection

Computing the intersection of parametric and algebraic curves and surfaces is a fundamental problem in computer graphics and geometric modeling. This problem has been extensively studied in the literature and different techniques based on subdivision, interval analysis and algebraic formulation are known. For low degree curves and surfaces algebraic methods are considered to be the fastest, whereas techniques based on subdivision and Bézier clipping perform better for higher degree intersections. In this paper, we introduce a new technique of algebraic pruning based on the algebraic approaches and eigenvalue formulation of the problem. The resulting algorithm corresponds to computing only selected eigenvalues in the domain of intersection. This is based on matrix formulation of the intersection problem, power iterations and geometric properties of Bézier curves and surfaces. The algorithm prunes the domain and converges to the solutions rapidly. It has been applied to intersection of parametric and algebraic curves, ray tracing and curve-surface intersections. The resulting algorithm compares favorably with earlier methods in terms of performance and accuracy.     

Curvature-dependent triangulation of implicit surfaces

Implicit surfaces appear in many applications, including medical imaging, molecular modeling, computer aided design, computer graphics and finite element analysis. Despite their many advantages, implicit surfaces are difficult to render efficiently. Today's real-time graphics systems are heavily optimized for rendering triangles, so an implicit surface should be converted to a mesh of triangles before rendering. Our algorithm polyonalizes an implicit surface. The algorithm generates a mesh of close-to-equilateral triangles with sizes dependent on the local surface curvature. We assume that the implicit surface is connected and G¹ is smooth (that is, the tangent plane varies continuously over the surface). The algorithm requires an evaluator for the implicit function defined at all points in space, an evaluator for the function gradient defined at points near the surface, and a bounding box around the surface. The output of the algorithm is good for applications requiring a well-behaved triangulation, such as rendering systems and finite element partial differential equation (PDE) solvers     

Performing Efficient NURBS Modeling Operations on the GPU

We present algorithms for evaluating and performing modeling operations on NURBS surfaces using the programmable fragment processor on the Graphics Processing Unit (GPU). We extend our GPU-based NURBS evaluator that evaluates NURBS surfaces to compute exact normals for either standard or rational B-spline surfaces for use in rendering and geometric modeling. We build on these calculations in our new GPU algorithms to perform standard modeling operations such as inverse evaluations, ray intersections, and surface-surface intersections on the GPU. Our modeling algorithms run in real time, enabling the user to sketch on the actual surface to create new features. In addition, the designer can edit the surface by interactively trimming it without the need for retessellation. Our GPU-accelerated algorithm to perform surface-surface intersection operations with NURBS surfaces can output intersection curves in the model space as well as in the parametric spaces of both the intersecting surfaces at interactive rates. We also extend our surface-surface intersection algorithm to evaluate self-intersections in NURBS surfaces.     

反求工程中的混合切片技术

提出一种基于平面与“点云”、平面与NURBS曲面求交计算的混合切片方法．该方法可以保证切片曲线在点云和曲面的连接处达到G^1连续，在此基础上的重构曲面既能保证与相邻曲面的连续性要求，又能满足对点云的逼近精度要求，对反求建模尤其是过渡特征的重建有着重要意义．文中详细探讨了平面与曲面求交和点云切片两个核心算法，并对基于模型特征的混合切片方案的选择原则以及不同方法进行了论述和比较．最后用实例证明该方法在反求建模中是切实可行的．     

An Algorithm for Geometric Set Operations Using Cellular Subdivision Techniques

Geometric set operations play an integral role in systems for CAD/CAM, for robot planning, and for modeling objects such as underground formations from empirical data. Two major issues in the implementation of geometric set operations are efficiency in the search for geometric intersections and effectiveness in the treatment of singular intersection cases. This article presents an algorithm for geometric set operations on planar polyhedral nonmanifold objects that addresses both these issues. First, an efficient search for geometric intersections is obtained by localizing the search to small regions of object space through a cellular subdivision scheme using the polytree data structure. Second, an effective treatment of singular intersection cases is obtained by mapping each singular intersection occurring in a region into one of a small set of cases.     

一种改进的自适应三角剖分算法*

现有的大多数散乱点云三角剖分算法存在细节特征表现不足和适应性不强的问题,为此改进了一种自适应的三角网格剖分算法。此方法将Shepard曲面插值与多尺度分析方法相结合;引入改进的八叉树搜索思想,加细搜索进而估算出点云中每个测量点的曲率;生成带自适应分辨率的分层空间栅格,最终实现自适应的三角网格重构。实验结果表明,经改进的算法,形成的三角网格质量较高,能够较好地再现原三维物体的细节特征,且效率较高,适用广泛。     

大规模孔洞点云的快速重建算法研究 *

针对实际中经常存在的含有孔洞的点云数据 ,在原多层重建算法的基础上提出了一种可以进行点云补洞的快速曲面重建算法。首先对散乱点云数据进行空间自适应八叉剖分 ,然后对点云数据进行由粗到精的多层插值 ,建立隐式曲面方程 ,最后提出了两种加快重建的方法。加速算法可以减少重建时间 ,非常有利于处理大规模点云。实验结果证明 ,本算法对点云孔洞修补效果良好 ,重建速度快 ,效率高。     

动态非均质半透明物体的实时绘制算法

现有的对半透明物体的绘制算法中大部分都是为均质材质设计的,虽然有少数算法可以绘制非均质材质,但效率不高,为此提出一种图形硬件加速的动态非均质半透明物体的实时绘制算法.首先将模型的采样点组织成八叉树的形式,将双向次表面散射反射函数(BSSRDF)表达绑定为顶点属性,同时充分利用图形硬件的并行性来实现八叉树的快速建立和遍历;然后以树的结点之间的空间距离和材质的相似度为准则提出一种新的采样方法来提高表面积分的效率.由于整个过程不需要任何预计算,因此该算法可以很容易地扩展到动画场景或者变化的材质,并且还可以灵活地选择BSSRDF的表达方式.实验结果表明,文中算法可以达到实时的绘制帧率和良好的视觉效果.     

Real-Time Ray Tracing of Implicit Surfaces on the GPU

Compact representation of geometry using a suitable procedural or mathematical model and a ray-tracing mode of rendering fit the programmable graphics processor units (GPUs) well. Several such representations including parametric and subdivision surfaces have been explored in recent research. The important and widely applicable category of the general implicit surface has received less attention. In this paper, we present a ray-tracing procedure to render general implicit surfaces efficiently on the GPU. Though only the fourth or lower order surfaces can be rendered using analytical roots, our adaptive marching points algorithm can ray trace arbitrary implicit surfaces without multiple roots, by sampling the ray at selected points till a root is found. Adapting the sampling step size based on a proximity measure and a horizon measure delivers high speed. The sign test can handle any surface without multiple roots. The Taylor test that uses ideas from interval analysis can ray trace many surfaces with complex roots. Overall, a simple algorithm that fits the SIMD architecture of the GPU results in high performance. We demonstrate the ray tracing of algebraic surfaces up to order 50 and nonalgebraic surfaces including a Blinn's blobby with 75 spheres at better than interactive frame rates.