Fast Global Illumination on Dynamic Height Fields

We present a real-time method for rendering global illumination effects from large area and environmental lights on dynamic height fields. In contrast to previous work, our method handles inter-reflections (indirect lighting) and non-diffuse surfaces. To reduce sampling, we construct one multi-resolution pyramid for height variation to compute direct shadows, and another pyramid for each indirect bounce of incident radiance to compute inter-reflections. The basic principle is to sample the points blocking direct light, or shedding indirect light, from coarser levels of the pyramid the farther away they are from a given receiver point. We unify the representation of visibility and indirect radiance at discrete azimuthal directions (i.e., as a function of a single elevation angle) using the concept of a "casting set" of visible points along this direction whose contributions are collected in the basis of normalized Legendre polynomials. This analytic representation is compact, requires no precomputation, and allows efficient integration to produce the spherical visibility and indirect radiance signals. Sub-sampling visibility and indirect radiance, while shading with full-resolution surface normals, further increases performance without introducing noticeable artifacts. Our method renders 512×512 height fields (> 500K triangles) at 36Hz.     

A Fast Parallel Algorithm for Convex Hull Problem of Multi-Leveled Images

In this paper, we propose a parallel algorithm to solve the convex hull problem for an (n×n) multi-leveled image using a reconfigurable mesh connected computer of the same size as a computational model. The algorithm determines parallely the convex hull of all the connected components of the multileveled image. It is based on some geometric properties and a top-down strategy. The complexity of the algorithm is O(logn) times. Using some approximations on the component contours, this complexity is reduced to O(logm) times where m is the number of the vertices of the convex hull of the biggest component of the image.This complexity is reached thanks to the polymorphic properties of the mesh where all the components are simultaneously and separately processed.     

A time-optimal parallel algorithm for three-dimensional convex hulls

In this paper we present an O(1/ logn)-time parallel algorithm for computing the convex hull ofn points in ³. This algorithm usesO(@#@ n^1+a) processors on a CREW PRAM, for any constant 0 < 1. So far, all adequately documented parallel algorithms proposed for this problem use time at least O(log² n). In addition, the algorithm presented here is the first parallel algorithm for the three-dimensional convex hull problem that is not based on the serial divide-and-conquer algorithm of Preparata and Hong, whose crucial operation is the merging of the convex hulls of two linearly separated point sets. The contributions of this paper are therefore (i) an O(logn)-time parallel algorithm for the three-dimensional convex hull problem, and (ii) a parallel algorithm for this problem that does not follow the traditional paradigm.This paper was presented in preliminary form at the 9th Annual ACM Symposium on Computational Geometry, San Diego, CA, May 1993 [32]. The work of N. M. Amato was supported in part by an AT&T Bell Laboratories Graduate Fellowship, the Joint Services Electronics Program (U.S. Army, U.S. Navy, U.S. Air Force) under Contract N00014-90-J-1270, and NSF Grant CCR-89-22008. This work was done while N. M. Amato was with the Department of Computer Science at the University of Illinois. The work of F. P. Preparata was supported in part by NSF Grants CCR-91-96152, CCR-91-96176, and ONR Contract N00014-91-J-4052, ARPA order 8225.     

Fast Soft Self‐Shadowing on Dynamic Height Fields

We present a new, real‐time method for rendering soft shadows from large light sources or lighting environments on dynamic height fields. The method first computes a horizon map for a set of azimuthal directions. To reduce sampling, we compute a multi‐resolution pyramid on the height field. Coarser pyramid levels are indexed as the distance from caster to receiver increases. For every receiver point and every azimuthal direction, a smooth function of blocking angle in terms of log distance is reconstructed from a height difference sample at each pyramid level. This function's maximum approximates the horizon angle. We then sum visibility at each receiver point over wedges determined by successive pairs of horizon angles. Each wedge represents a linear transition in blocking angle over its azimuthal extent. It is precomputed in the order‐4 spherical harmonic (SH) basis, for a canonical azimuthal origin and fixed extent, resulting in a 2D table. The SH triple product of 16D vectors representing lighting, total visibility, and diffuse reflectance then yields the soft‐shadowed result. Two types of light sources are considered; both are distant and low‐frequency. Environmental lights require visibility sampling around the complete 360 ° azimuth, while key lights sample visibility within a partial swath. Restricting the swath concentrates samples where the light comes from (e.g. 3 azimuthal directions vs. 16‐32 for a full swath) and obtains sharper shadows. Our GPU implementation handles height fields up to 1024 × 1024 in real‐time. The computation is simple, local, and parallel, with performance independent of geometric content.     

Numerical stability of a convex hull algorithm for simple polygons

A numerically stable and optimalO(n)-time implementation of an algorithm for finding the convex hull of a simple polygon is presented. Stability is understood in the sense of a backward error analysis. A concept of the condition number of simple polygons and its impact on the performance of the algorithm is discussed. It is shown that if the condition number does not exceed (1+O())/(3), then, in floating-point arithmetic with the unit roundoff, the algorithm produces the vertices of a convex hull for slightly perturbed input points. The relative perturbation does not exceed 3(1+O()).J. W. Jaromczyk was partially supported by a grant from the Center for Robotics and Manufacturing Systems at the University of Kentucky and G. W. Wasilkowski was partially supported by the National Science Foundation under Grants CCR-89-05371 and CCR-91-14042.     

一种高效的平面点集凸包递归算法

凸包是计算几何的基本结构, 在许多图形图像相关领域得到了广泛应用. 本文提出了一种简单快速的平面点集凸包算法, 使用了主成分分析法(Principle component analysis, PCA)对点集进行预处理, 并研究了适用的排序规则和凸包边缘点判定原则. 该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取. 系统将提取的凸包区域进行掩码标记, 从而避免密集残留点造成相位展开错误, 保证了三维形貌重构的准确性. 实验结果表明, 该算法准确可靠, 并且运行效率较高.     

Lower bounds for maximal and convex layers problems

In this paper we derive tight lower bounds for the maximal and convex layers problems in the plane. Our lower bound proofs for the maxima problem and convex hull problem are simpler than those previously known. We also obtain an (nlog n) lower bound for the maximal depth problem, and the convex depth problem, when the points are given in sorted order of their x-coordinates.     

Fast linear expected-time algorithms for computing maxima and convex hulls

This paper examines the expected complexity of boundary problems on a set ofN points inK-space. We assume that the points are chosen from a probability distribution in which each component of a point is chosen independently of all other components. We present an algorithm to find the maximal points usingKN + O (N^1–1/K log^1/K N) expected scalar comparisons, for fixedK 2. A lower bound shows that the algorithm is optimal in the leading term. We describe a simple maxima algorithm that is easy to code, and present experimental evidence that it has similar running time. For fixedK 2, an algorithm computes the convex hull of the set in 2KN + O(N^1–1/K log^1/KN) expected scalar comparisons. The history of the algorithms exhibits interesting interactions among consulting, algorithm design, data analysis, and mathematical analysis of algorithms.This work was performed while this author was visiting AT&T Bell Laboratories.     

A Novel Pose Estimation Algorithm Based on Points to Regions Correspondence

A novel pose estimation algorithm is put forward in this paper. Given the points on an object and the convex regions in which the correspondent image points lie, the concrete values of position and orientation (t and R) between the object and the camera are found based on a points to regions correspondence. The unit quaternion representation of rotation matrix and convex Linear Matrix Inequalities (LMI) optimization methods are used to estimate the pose. By loosening the requirement of precise point to point correspondence and using convex LMI formulations, this algorithm provides a more robust and faster pose estimation method. The effect of this method is verified by simulation and laboratory experiment results.

Constructing strongly convex hulls using exact or rounded arithmetic

One useful generalization of the convex hull of a setS ofn points is the -strongly convex -hull. It is defined to be a convex polygon with vertices taken fromS such that no point inS lies farther than outside and such that even if the vertices of are perturbed by as much as , remains convex. It was an open question as to whether an -strongly convexO()-hull existed for all positive . We give here anO(n logn) algorithm for constructing it (which thus proves its existence). This algorithm uses exact rational arithmetic. We also show how to construct an -strongly convexO( + )-hull inO(n logn) time using rounded arithmetic with rounding unit . This is the first rounded-arithmetic convex-hull algorithm which guarantees a convex output and which has error independent ofn.     

Hierarchical Convex Approximation of 3D Shapes for Fast Region Selection

Given a 3D solid model S represented by a tetrahedral mesh, we describe a novel algorithm to compute a hierarchy of convex polyhedra that tightly enclose S. The hierarchy can be browsed at interactive speed on a modern PC and it is useful for implementing an intuitive feature selection paradigm for 3D editing environments. Convex parts often coincide with perceptually relevant shape components and, for their identification, existing methods rely on the boundary surface only. In contrast, we show that the notion of part concavity can be expressed and implemented more intuitively and efficiently by exploiting a tetrahedrization of the shape volume. The method proposed is completely automatic, and generates a tree of convex polyhedra in which the root is the convex hull of the whole shape, and the leaves are the tetrahedra of the input mesh. The algorithm proceeds bottom‐up by hierarchically clustering tetrahedra into nearly convex aggregations, and the whole process is significantly fast. We prove that, in the average case, for a mesh of n tetrahedra O(n log² n) operations are sufficient to compute the whole tree.     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

Scalable Height Field Self‐Shadowing

We present a new method suitable for general purpose graphics processing units to render self‐shadows on dynamic height fields under dynamic light environments in real‐time. Visibility for each point in the height field is determined as the exact horizon for a set of azimuthal directions in time linear in height field size and the number of directions. The surface is shaded using the horizon information and a high‐resolution light environment extracted on‐line from a high dynamic range cube map, allowing for detailed extended shadows. The desired accuracy for any geometric content and lighting complexity can be matched by choosing a suitable number of azimuthal directions. Our method is able to represent arbitrary features of both high‐ and low‐frequency, unifying hard and soft shadowing. We achieve 23 fps on 1024×1024 height fields with 64 azimuthal directions under a 256×64 environment lighting on an Nvidia GTX 280 GPU.     

点集模型的直接可见性测试与基于视点的绘制

点集模型作为一种新兴的三维几何形体表示形式,近年来备受关注.本文运用点集法向计算与凸包构建等技术,对原始点集模型进行直接可视性计算,并利用可见性计算的结果对点集模型进行基于视点的绘制.算法首先对原始模型进行基于视点的精简,剔除大部分不可见点;再对精简后的模型进行球面对称变换,并构建变换后点集的凸包,进而提取出可见点集;最后运用真实感图形绘制技术实现可见点集的快速绘制.实验证明,本文算法能够快速地计算点集模型中采样点的可见性.该算法可应用于点集模型基于视点的绘制与曲面重建,以及点集模型的阴影绘制等领域.     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

Randomized quickhull

This paper contains a simple, randomized algorithm for constructing the convex hull of a set ofn points in the plane with expected running timeO(nlogh) whereh is the number of points on the convex hull. Supported in part by NSA Grant MDA904-93-H-3026 and by the NSF Regional Geometry Institute (Smith College, July 1993) Grant DMS-90 13220.     

基于凸包和网格索引技术的快速TIN生成算法及应用

在原有凸包推进算法的基础上,提出了一种针对散乱点集的快速生成TIN的算法.通过在三角形外接圆的最小网格覆盖中查找点扩展三角形,使得每次查找的点的个数与且只与散乱点的分布有关,而与散乱点集的大小无关;同时利用有向凸包和动态修正前沿圈等技术避免生成重复三角形,从而大大提高了建网的速度.实践证明,该算法具有可操作性和较强的实用性.该算法实现了两类基于不规则三角网数字地面模型的分析应用.     

Computing a (1+ε)-Approximate Geometric Minimum-Diameter Spanning Tree

Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. For several years, the best upper bound on the time to compute a GMDST was cubic with respect to the number of points in the input set. Recently, Timothy Chan introduced a subcubic time algorithm. In this paper we present an algorithm that generates a tree whose diameter is no more than (1 + ) times that of a GMDST, for any > 0. Our algorithm reduces the problem to several grid-aligned versions of the problem and runs within time $O(^-3+ n) and space O(n).     

超球流形约束下的3DMM分步全局优化

通过综合运用人脸空间的超球流形约束、基于梯度的启发式全局优化、光照的球面谐波描述以及凸包可见点集的直接消隐方法,提出一种三维可形变模型的图像匹配方法.首先通过形状超球流形约束下的全局优化算法求解摄像机参数和形状参数,然后使用以上参数和凸包点集的直接消隐方法确定物像点对应关系,最后根据物像点对应关系由反射率超球流形约束下的全局优化算法求解光照参数和反射率参数.定量的对比实验结果表明,该方法无需借助分区域拟合、人为估计参数值、层次匹配策略或复杂的特征组合,即可由单幅图像恢复三维可形变模型(3DMM)的全部参数.