Approximate General Sweep Boundary of a 2D Curved Object

This paper presents an algorithm to compute an approximation to the general sweep boundary of a 2D curved moving object which changes its shape dynamically while traversing a trajectory. In effect, we make polygonal approximations to the trajectory and to the object shape at every appropriate instance along the trajectory so that the approximated polygonal sweep boundary is within a given error bound ϵ > 0 from the exact sweep boundary. The algorithm interpolates intermediate polygonal shapes between any two consecutive instances, and constructs polygons which approximate the sweep boundary of the object. Previous algorithms on sweep boundary computation have been mainly concerned about moving objects with fixed shapes; nevertheless, they have involved a fair amount of symbolic and/or numerical computations that have limited their practical uses in graphics modeling systems as well as in many other applications which require fast sweep boundary computation. Although the algorithm presented here does not generate the exact sweep boundaries of objects, it does yield quite reasonable polygonal approximations to them, and our experimental results show that its computation is reasonably fast to be of a practical use.     

AD-Frustum: adaptive frustum tracing for interactive sound propagation

We present an interactive algorithm to compute sound propagation paths for transmission, specular reflection and edge diffraction in complex scenes. Our formulation uses an adaptive frustum representation that is automatically sub-divided to accurately compute intersections with the scene primitives. We describe a simple and fast algorithm to approximate the visible surface for each frustum and generate new frusta based on specular reflection and edge diffraction. Our approach is applicable to all triangulated models and we demonstrate its performance on architectural and outdoor models with tens or hundreds of thousands of triangles and moving objects. In practice, our algorithm can perform geometric sound propagation in complex scenes at 4-20 frames per second on a multi-core PC.     

Extreme simplification and rendering of point sets using algebraic multigrid

We present a novel approach for extreme simplification of point set models, in the context of real-time rendering. Point sets are often rendered using simple point primitives, such as oriented discs. However, this requires using many primitives to render even moderately simple shapes. Often, one wishes to render a simplified model using only a few primitives, thus trading accuracy for simplicity. For this goal, we propose a more complex primitive, called a splat, that is able to approximate larger and more complex surface areas than oriented discs. We construct our primitive by decomposing the model into quasi-flat regions, using an efficient algebraic multigrid algorithm. Next, we encode these regions into splats implemented as planar support polygons textured with color and transparency information and render the splats using a special blending algorithm. Our approach combines the advantages of mesh-less point-based techniques with traditional polygon-based techniques. We demonstrate our method on various models.     

基于散乱点的增量式曲面逼近

针对用接触式三维点数据获取设备快速输入的物体表面散乱点云数据,提出了增量式B样条曲面快速逼近算法．该算法首先要获得重建曲面的边界数据,以生成初始曲面;然后对输入的散乱数据点云用投影法计算出其参数值;再用模板子块在曲面上移动,反算出模块子块的控制点;最后更新整个曲面的相应控制点,实现边输入、边逼近,即增量式曲面逼近．在输入过程中可看到曲面逐渐逼近目标曲面的过程,在误差大的区域可以增加输入点来改善曲面逼近效果．对于复杂曲面进行多次投影计算散乱数据点参数及曲面逼近,可达到良好效果．     

Swept Volume Approximation of Polygon Soups

We present a fast algorithm to approximate the swept volume (SV) boundary of arbitrary polygon soup models. Despite the extensive research on calculating the volume swept by an object along a trajectory, the efficient algorithms described have imposed constraints on both the trajectories and geometric models. By proposing a general algorithm that handles flat surfaces as well as volumes and disconnected objects, we allow SV calculation without resorting to preprocessing mesh repair nor deforming offsets. This is of particular interest in the domain of product lifecycle management (PLM), which deals with industrial computer aided design (CAD) models that are malformed more often than not. We incorporate the bounded distance operator used in path planning to efficiently sample the trajectory while controlling the total error. We develop a triangulation scheme that draws on the unique data set created by an advancing front level-set method to tessellate the SV boundary in linear time. We analyze its performance, and demonstrate its effectiveness both theoretically and on real cases taken from PLM.     

基于适应性相关测试和点斜式查表求交的圆形窗口快速裁剪方法

在智能CAD、图形识别与理解等复杂图形应用系统中,由于图元数量多、 图元间关系复杂,且系统实时交互响应要求较高,现有圆形窗口裁剪算法较难满足要求。为 此提出圆形窗口对线段的一种新的快速裁剪算法。该算法由基于切线分隔的圆外线段快速适 应性测试方法、基于最小范围的圆内线段测试方法和基于点斜式查表的线段与窗口圆快速求 交方法三部分组成。通过按端点位置选择适应的测试方法、尽量避免不必要的操作、尽量以 简单操作代替复杂操作等措施,大大提高了圆形窗口对线段的裁剪速度。在图形识别及智能 CAD 等应用中的实验结果表明,采用文中算法可较大地提高效率。     

A framework for quad/triangle subdivision surface fitting: Application to mechanical objects

In this paper we present a new framework for subdivision surface approximation of three‐dimensional models represented by polygonal meshes. Our approach, particularly suited for mechanical or Computer Aided Design (CAD) parts, produces a mixed quadrangle‐triangle control mesh, optimized in terms of face and vertex numbers while remaining independent of the connectivity of the input mesh. Our algorithm begins with a decomposition of the object into surface patches. The main idea is to approximate the region boundaries first and then the interior data. Thus, for each patch, a first step approximates the boundaries with subdivision curves (associated with control polygons) and creates an initial subdivision surface by linking the boundary control points with respect to the lines of curvature of the target surface. Then, a second step optimizes the initial subdivision surface by iteratively moving control points and enriching regions according to the error distribution. The final control mesh defining the whole model is then created assembling every local subdivision control meshes. This control polyhedron is much more compact than the original mesh and visually represents the same shape after several subdivision steps, hence it is particularly suitable for compression and visualization tasks. Experiments conducted on several mechanical models have proven the coherency and the efficiency of our algorithm, compared with existing methods.     

Voxelized Minkowski sum computation on the GPU with robust culling

We present a new approach for computing the voxelized Minkowski sum (excluding any enclosed voids) of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum, analyzing and adaptively bounding the rounding errors of the culling algorithm to solve the floating point error problem. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without enclosed voids and support high volumetric resolution of 1024³ with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms. It avoids the large number of 3D Boolean operations needed in most existing algorithms and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.     

An approximative solution to the Zookeeper's Problem

Consider a simple polygon P containing disjoint convex polygons each of which shares an edge with P. The Zookeeper's Problem then asks for the shortest route in P that visits all convex polygons without entering their interiors. Existing algorithms that solve this problem run in time super-linear in the size of P and the convex polygons. They also suffer from numerical problems.In this paper, we shed more light on the problem and present a simple linear time algorithm for computing an approximate solution. The algorithm mainly computes shortest paths and intersections between lines using basic data structures. It does not suffer from numerical problems. We prove that the computed approximation route is at most 6 times longer than the shortest route in the exact solution.     

A new subdivision based approach for piecewise smooth approximation of 3D polygonal curves

This paper presents an algorithm dealing with the data reduction and the approximation of 3D polygonal curves. Our method is able to approximate efficiently a set of straight 3D segments or points with a piecewise smooth subdivision curve, in a near optimal way in terms of control point number. Our algorithm is a generalization for subdivision rules, including sharp vertex processing, of the Active B-Spline Curve developed by Pottmann et al. We have also developed a theoretically demonstrated approach, analysing curvature properties of B-Splines, which computes a near optimal evaluation of the initial number and positions of control points. Moreover, our original Active Footpoint Parameterization method prevents wrong matching problems occurring particularly for self-intersecting curves. Thus, the stability of the algorithm is highly increased. Our method was tested on different sets of curves and gives satisfying results regarding to approximation error, convergence speed and compression rate. This method is in line with a larger 3D CAD object compression scheme by piecewise subdivision surface approximation. The objective is to fit a subdivision surface on a target patch by first fitting its boundary with a subdivision curve whose control polygon will represent the boundary of the surface control polyhedron.     

Multi-dimensional asymptotically stable finite difference schemes for the advection–diffusion equation

An algorithm is presented which solves the multi-dimensional advection–diffusion equation on complex shapes to second-order accuracy and is asymptotically stable in time. This bounded-error result is achieved by constructing, on a rectangular grid, a differentiation matrix whose symmetric part is negative definite. The differentiation matrix accounts for the Dirichlet boundary condition by imposing penalty-like terms. Numerical examples in two dimensions show that the method is effective even where standard schemes, stable by traditional definitions, fail. It gives accurate, non oscillatory results even when boundary layers are not resolved.     

Segment Tracing Using Local Lipschitz Bounds

We introduce Segment Tracing, a new algorithm that accelerates the classical Sphere Tracing method for computing the intersection between a ray and an implicit surface. Our approach consists in computing the Lipschitz bound locally over a segment to improve the marching step computation and accelerate the overall process. We describe the computation of the Lipschitz bound for different operators and primitives. We demonstrate that our algorithm significantly reduces the number of field function queries compared to previous methods, without the need for additional accelerating data-structures. Our method can be applied to a vast variety of implicit models ranging from hierarchical procedural objects built from complex primitives, to simulation-generated implicit surfaces created from many particles.     

New algorithms for approximate Nash equilibria in bimatrix games

We consider the problem of computing additively approximate Nash equilibria in non-cooperative two-player games. We provide a new polynomial time algorithm that achieves an approximation guarantee of 0.36392. We first provide a simpler algorithm, that achieves a 0.38197-approximation, which is exactly the same factor as the algorithm of Daskalakis, Mehta and Papadimitriou. This algorithm is then tuned, improving the approximation error to 0.36392. Our method is relatively fast and simple, as it requires solving only one linear program and it is based on using the solution of an auxiliary zero-sum game as a starting point. Finally we also exhibit a simple reduction that allows us to compute approximate equilibria for multi-player games by using algorithms for two-player games.     

Fast and simple hardware accelerated voxelizations using simplicial coverings

Voxelization of solids, that is the representation of a solid by a set of voxels that approximates it, is an operation with important applications in fields like solid modeling, physical simulation or volume graphics. Moreover, the new generation of affordable 3D raster displays has renewed the interest on fast voxelization algorithms, as the scan-conversion of a solid is a basic operation on these devices. In this paper a hardware accelerated method for computing a voxelization of a polyhedron is presented. The algorithm is simple, efficient, robust and handles any kind of polyhedron (self-intersecting, with or without holes, manifold or non-manifold). Three different implementations are described in detail. The first is a conventional implementation in the CPU, the second is a hardware accelerated implementation that uses standard OpenGL primitives, and the third exploits the capabilities of modern GPUs by using vertex programs.     

Flexible point-based rendering on mobile devices

We have seen the growing deployment of ubiquitous computing devices and the proliferation of complex virtual environments. As demand for detailed and high-quality geometric models increases, typical scene size (often including scanned 3D objects) easily reaches millions of geometric primitives. Traditionally, vertices and polygons (faces) represent 3D objects. These representations, coupled with the traditional rendering pipeline, don't adequately support display of complex scenes on different types of platforms with heterogeneous rendering capabilities. To accommodate these constraints, we use a packed hierarchical point-based representation for rendering. Point-based rendering offers a simple-to-use level-of-detail mechanism in which we can adapt the number of points rendered to the underlying object's screen size. Our work strives for flexible rendering - that is, rendering only the interior hierarchy nodes as representatives of the subtree. In particular, we avoid traversal of the entire hierarchy and reconstruction of model attributes (such as normals and color information) for interior nodes because both operations can be prohibitively expensive. Flexible rendering also lets us traverse the hierarchy in a specific order, resulting in a fast, one-pass shadow-mapping algorithm.     

Quintic nonpolynomial spline method for the solution of a second-order boundary-value problem with engineering applications

Nonpolynomial quintic spline functions are used to develop a numerical algorithm for computing an approximation to the solution of a system of second order boundary value problems associated with heat transfer. We show that the approximate solutions obtained by our algorithm are better than those produced by other spline and domain decomposition methods. A comparison of our algorithm with nonpolynomial quadratic spline method is discussed with the help of two numerical examples.     

Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes

We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self‐intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane‐based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.     

一种等值线图的任意复杂多边形窗口裁剪算法

给出了一种新的海量等值线图任意多边形窗口的快速裁剪算法。计算裁剪多边形的外包围盒并创建网格结构,利用网格结构对等值线进行快速预裁剪,通过链式结构对等值线进行细节裁剪得到最终裁剪结果。通过建立行链式结构可以实现以行扫描的方式快速判断点的内外属性,而且还能减少线段求交运算次数,基本能确定实际相交的线段时才进行求交运算。经过大量的实验,证明该算法非常高效且稳定。另外,新算法能有效地处理各种特殊裁剪多边形嵌套情况,克服了以往算法对裁剪多边形的约束条件。该算法程序实现简单且符合工程需求。     

Two Algorithms for Fast Polyhedron Ray-Tracing

ＴｗｏＡｌｇｏｒｉｔｈｍｓｆｏｒＦａｓｔＰｏｌｙｈｅｄｒｏｎＲａｙ－ＴｒａｃｉｎｇＺｈａｎｇＱｉａｎＳｈｉＪｉａｏｙｉｎｇＣａｉＨｏｎｇＣＡＤ＆ＣＧＳｔａｔｅＫｅｙＬａｂ．，ＺｈｅｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，３１００２７ＦｏｓｈａｎＥｎｔｅｒｐｒ...