Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

High Performance GPU‐based Proximity Queries using Distance Fields

Proximity queries such as closest point computation and collision detection have many applications in computer graphics, including computer animation, physics‐based modelling, augmented and virtual reality. We present efficient algorithms for proximity queries between a closed rigid object and an arbitrary, possibly deformable, polygonal mesh. Using graphics hardware to densely sample the distance field of the rigid object over the arbitrary mesh, we compute minimal proximity and collision response information on the graphics processing unit (GPU) using blending and depth buffering, as well as parallel reduction techniques, thus minimizing the readback bottleneck. Although limited to image‐space resolution, our algorithm provides high and steady performance when compared with other similar algorithms. Proximity queries between arbitrary meshes with hundreds of thousands of triangles and detailed distance fields of rigid objects are computed in a few milliseconds at high‐sampling resolution, even in situations with large overlap.     

基于图像空间的复杂模型碰撞检测算法

提出一种使用图形硬件用于复杂模型间的快速的碰撞检测算法.算法是基于CULLIDE的执行GPU可见性查询来减少物体模型间没有邻近特征的子集,描述了一个分类方案计算物体潜在碰撞集和碰撞自由子集,提高了裁减的性能.为了减少CPU的负载,利用GPU的可编程性,在GPU上进行精确的物体相交计算.     

Novel Geometrical Voxelization Approach with Application to Streamlines

This paper presents a novel geometrical voxelization algorithm for polygonal models. First, distance computation is performed slice by slice on graphics processing units (GPUs) between geometrical primitives and voxels for line/surface voxelization. A novel solid filling process is then proposed to assist surface voxelization and achieve solid voxelization. Furthermore, using the proposed transfer functions, both binary and anti-aliasing voxelizations are achievable. Finally, the proposed approach can be applied to voxelize streamlines for 3D vector fields using line voxelization. The proposed approach obtains desired experimental results.     

Decentralized spatial partitioning for multi-vehicle systems in spatiotemporal flow-field

We consider the problem of characterizing a generalized Voronoi diagram/partition of a convex polygon in a two-dimensional Euclidean space that encodes information about the proximity relations between a team of aerial/marine vehicles and arbitrary points in the partition space. These proximity relations are determined by the time required for each vehicle to reach an arbitrary point (time-to-go) in the partition space when driven by a locally optimal feedback control law in the presence of a spatiotemporal drift field. The main contribution of this work is the presentation of a partitioning algorithm, which is decentralized, in the sense that each vehicle can independently compute its corresponding cell from the generalized Voronoi partition without computing or receiving information about the cells of the other vehicles. Finally, we present numerical simulations using data from real drift fields to illustrate the key features of the decentralized solution to the proposed class of spatial partitioning problems.     

Computing the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU

We present a GPU algorithm for computing the directed Hausdorff distance between two NURBS surfaces. The algorithm is based on sampling of one surface, and performing numerical iterations on the GPU to compute the minimal distance from each sample to the other surface. An error analysis for the Hausdorff distance computations is performed, based on bounds on the NURBS surfaces. We compare a CUDA implementation of our algorithm to existing methods, demonstrating that the new method addresses limitations of previous hierarchical culling methods such as the sensitivity to the position of the inputs.     

Object-Space Visibility Ordering for Point-Based and Volume Rendering

This paper presents a method to accelerate algorithms that need a correct and complete visibility ordering of their data for rendering. The technique works by pre‐sorting primitives in object‐space using three lists (one for each axis: X, Y and Z), and then combining the lists using graphics hardware by rendering each list to a texture and merging the textures in the end. We validate our algorithm by applying it to the splatting technique using several types of rendering, including point‐based rendering and volume rendering. We also detail our hardware implementation for volume rendering using point sprites.     

On 2-Site Voronoi Diagrams Under Geometric Distance Functions

We revisit a new type of Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, namely, circles and triangles, and analyze the structure and complexity of the nearest- and furthest-neighbor 2-site Voronoi diagrams of a point set in the plane with respect to these distance functions. In addition, we bring to notice that 2-point site Voronoi diagrams can be alternatively interpreted as 1-site Voronoi diagrams of segments, and thus, our results also enhance the knowledge on the latter.     

Decentralized spatial partitioning algorithms for multi-vehicle systems based on the minimum control effort metric

We consider the problem of characterizing a spatial partition of the position space of a team of vehicles with linear time-varying kinematics. The generalized metric that determines the proximity relations between the vehicles and an arbitrary target point in the partition space is the minimum control effort required for each vehicle to reach the latter point with zero miss distance and exactly zero velocity at a prescribed final time. We show that the solution to the generalized Voronoi partitioning problem can be associated with a special class of spatial partitions known as affine diagrams. Because the combinatorial complexity of the affine diagrams is comparable to the one of the standard Voronoi diagrams, their computation does not pose a significant challenge in applications of multi-vehicle systems. Subsequently, we propose an algorithm for the computation of the spatial partition, which is decentralized in the sense that each vehicle can compute an approximation of its own cell independently from the other vehicles from the same team without utilizing a common spatial mesh. Numerical simulations that illustrate the theoretical developments are also presented.     

GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces

We present a parallel GPU-accelerated algorithm for computing the directed Hausdorff distance from one NURBS surface to another, within a bound. We make use of axis-aligned bounding-box hierarchies that bound the NURBS surfaces to accelerate the computations. We dynamically construct as well as traverse the bounding-box hierarchies for the NURBS surfaces using operations that are optimized for the GPU. To compute the Hausdorff distance, we traverse this hierarchy after culling bounding-box pairs that do not contribute to the Hausdorff distance. Our contribution includes two-sided culling tests that can be performed in parallel using the GPU. The culling, based on the minimum and maximum distance ranges between the bounding boxes, eliminates bounding-box pairs from both surfaces that do not contribute to the Hausdorff distance simultaneously. We calculate accuracy bounds for our computed Hausdorff distance based on the curvature of the surfaces. Our algorithm runs in real-time with very small guaranteed error bounds for complex NURBS surfaces. Since we dynamically construct our bounding-box hierarchy, our algorithm can be used to interactively compute the Hausdorff distance for models made of dynamic deformable surfaces.     

Map segmentation for geospatial data mining through generalized higher-order Voronoi diagrams with sequential scan algorithms

Segmentation is one popular method for geospatial data mining. We propose efficient and effective sequential-scan algorithms for higher-order Voronoi diagram districting. We extend the distance transform algorithm to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for higher-order Voronoi diagrams. The algorithm implementation is explained along with efficiencies and error. Finally, a case study based on trade area modeling is described to demonstrate the advantages of our proposed algorithms.     

Fast and reliable collision culling using graphics hardware

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. In order to overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including nonmanifold geometry, deformable models, and breaking objects.     

Hardware‐Assisted Projected Tetrahedra

We present a flexible and highly efficient hardware‐assisted volume renderer grounded on the original Projected Tetrahedra (PT) algorithm. Unlike recent similar approaches, our method is exclusively based on the rasterization of simple geometric primitives and takes full advantage of graphics hardware. Both vertex and geometry shaders are used to compute the tetrahedral projection, while the volume ray integral is evaluated in a fragment shader; hence, volume rendering is performed entirely on the GPU within a single pass through the pipeline. We apply a CUDA‐based visibility ordering achieving rendering and sorting performance of over 6 M Tet/s for unstructured datasets. Furthermore, as each tetrahedron is processed independently, we employ a data‐parallel solution which is neither bound by GPU memory size nor does it rely on auxiliary volume information. In addition, iso‐surfaces can be readily extracted during the rendering process, and time‐varying data are handled without extra burden.     

Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.     

GPU-based offset surface computation using point samples

We present an efficient algorithm to perform approximate offsetting operations on geometric models using GPUs. Our approach approximates the boundary of an object with point samples and computes the offset by merging the balls centered at these points. The underlying approach uses Layered Depth Images (LDI) to organize the samples into structured points and performs parallel computations using multiple cores. We use spatial hashing to accelerate intersection queries and balance the workload among various cores. Furthermore, the problem of offsetting with a large distance is decomposed into successive offsetting using smaller distances. We derive bounds on the accuracy of offset computation as a function of the sampling rate of LDI and offset distance. In practice, our GPU-based algorithm can accurately compute offsets of models represented using hundreds of thousands of points in a few seconds on a GeForce GTX 580 GPU. We observe more than 100 times speedup over prior serial CPU-based approximate offset computation algorithms.     

Hardware-based view-independent cell projection

We present two implementations of a view-independent cell projection algorithm for off-the-shelf programmable graphics hardware. Both implementations perform all computations for the projection and scan conversion of a set of tetrahedra on the graphics hardware and are therefore compatible with many of the hardware-accelerated optimizations for polygonal graphics, e.g., OpenGL vertex arrays and display lists. Apart from our actual implementations, we discuss potential improvements on future, more flexible graphics hardware and applications to interactive volume visualization of unstructured meshes.     

Efficient conservative visibility culling using theprioritized-layered projection algorithm

We propose a novel conservative visibility culling technique based on the Prioritized-Layered Projection (PLP) algorithm. PLP is a time-critical rendering technique that computes, for a given viewpoint, a partially correct image by rendering only a subset of the geometric primitives, those that PLP determines to be most likely visible. Our new algorithm builds on PLP and provides an efficient way of finding the remaining visible primitives. We do this by adding a second phase to PLP which uses image-space techniques for determining the visibility status of the remaining geometry. Another contribution of our work is to show how to efficiently implement such image-space visibility queries using currently available OpenGL hardware and extensions. We report on the implementation of our techniques on several graphics architectures, analyze their complexity, and discuss a possible hardware extension that has the potential to further increase performance     

Efficient Image‐Based Proximity Queries with Object‐Space Precision

We present an efficient algorithm for object‐space proximity queries between multiple deformable triangular meshes. Our approach uses the rasterization capabilities of the GPU to produce an image‐space representation of the vertices. Using this image‐space representation, inter‐object vertex‐triangle distances and closest points lying under a user‐defined threshold are computed in parallel by conservative rasterization of bounding primitives and sorted using atomic operations. We additionally introduce a similar technique to detect penetrating vertices. We show how mechanisms of modern GPUs such as mipmapping, Early‐Z and Early‐Stencil culling can optimize the performance of our method. Our algorithm is able to compute dense proximity information for complex scenes made of more than a hundred thousand triangles in real time, outperforming a CPU implementation based on bounding volume hierarchies by more than an order of magnitude.