Abstract:

We present a GPU-based approach to geometric pattern matching. We reduce this problem to ?nding the depth (maximally covered point) of an arrangement of polytopes in transformation space and describe hardware-assisted (GPU) algorithms which exploit the available set of graphics operations to perform a fast rasterized depth computation.

(Applying graphics hardware to achieve extremely fast geometric pattern matching in two and three dimensional transformation space. Dror Aiger and Klara Kedem. Information Processing Letters. 2008.)

This paper studies jump flooding as an algorithmic paradigm in general-purpose computation with GPUs. As an example application of jump flooding, the paper discusses a constant time algorithm on the GPU to compute an approximation to the Voronoi diagram of a given set of seeds in a 2D grid. The errors due to the differences between the approximation and the actual Voronoi diagram are hardly noticeable to the naked eye in all presented experiments. The same approach can also compute in constant time an approximation to the distance transform of a set of seeds in a 2D grid. In practice, such constant time algorithm is useful to many interactive applications involving, for example, rendering and image processing. Besides the experimental evidence, this paper also confirms quantitatively the effectiveness of jump flooding by analyzing the occurrences of errors. The analysis is a showcase of insights to the jump flooding paradigm, and may be of independent interest to other applications of jump flooding. (Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform. Guodong Rong and Tiow-Seng Tan. To appear in 2006 SIGGRAPH Symposium on Interactive 3D Graphics and Games. [I3D 2006] )

This paper by Sud et al. at UNC-Chapel Hill, describes an algorithm for fast computation of discretized 3D distance fields using graphics hardware. It uses bounds on the spatial extent of the Voronoi region of each primitive to cull away many distance functions for each 2D slice. A combination of culling and clamping techniques results in rendering relatively few distance functions to reduce the load on the graphics pipeline. The algorithm is applicable to all geometric models and does not make any assumptions about connectivity or a manifold representation. The application is demonstrated for medial axis evaluation and proximity computations. As compared to earlier approaches, this GPU implementation achieves an order of magnitude improvement in the running time. (DiFi: Fast 3D Distance Field Computation Using Graphics Hardware. Avneesh Sud, Miguel A. Otaduy and Dinesh Manocha in Proc. Eurographics 2004, to appear, 2004.)

This paper presents the computation of the feature distance transform (FDT) with an arbitrary distance function and the corresponding 2D skeleton or Voronoi diagram in DX8 or DX9 graphics hardware. Together with a direct, non-iterative distance measurement, the FDT enables us to compute a simply connected pixel-exact skeleton, which can be continously pruned with a regularization parameter. Real-time distance minimization in the zooming process delivers even sub-pixel accuracy. There are no restrictions on the distance function and additive and multiplicative weights can be applied. An adaptive tiling scheme delivers a ten-fold performance increase over a software or simple hardware implementation. (Generalized Distance Transforms and Skeletons in Graphics Hardware. Robert Strzodka and Alexandru Telea in Proceedings VisSym’04, to appear, 2004)

This paper proposes algorithms for computing extent measures and approximate representations of a stream of points in R² or R³. In particular, we study the problems of computing various extent measures (for example diameter, width, smallest enclosing rectangle, and smallest enclosing disk) and of approximating a set of points by a circle or a line. We show that these problems can be solved efficiently using graphics hardware even in the streaming model. (P. Agarwal, S. Krishnan, N. Mustafa and S. Venkatasubramanian. Streaming Geometric Optimization Using Graphics Hardware. Proc. 11th European Symposium on Algorithms, Sep 2003.)

Abstract: The Sequenced Convex Subtraction (SCS) algorithm for Constructive Solid Geometry (CSG) sequentially subtracts convex volumes from the z-buffer. This paper presents an improvement to subtraction sequence generation which uses object space overlap information to give O(n) length sequences in the best case and (unchanged) O(n²) sequences in the worst case. (Improved CSG Rendering using Overlap Graph Subtraction Sequences. N. Stewart, G. Leach, S. John. International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia – GRAPHITE 2003, pp. 47-53)

This paper by Krishnan et al. demonstrates a large class of non-parametric statistical analysis problems that can be solved using the graphics hardware. It shows how to do duality transforms and operations in primal and dual geometric planes in a robust way using the graphics pipeline. (Hardware-Assisted Computation of Depth Contours. S. Krishnan, N. Mustafa and S. Venkatasubramanian. 13th ACM-SIAM Symposium on Discrete Algorithms).

This paper by Mustafa et al. examines the use of graphics hardware as a general purpose geometry engine to compute simplification of large geographic maps in real-time. (Hardware Assisted View Dependent Map Simplification. N. Mustafa, E. Koutsofios, S. Krishnan and S. Venkatasubramanian. 17th Annual ACM Symposium on Computational Geometry, June 2001)

This paper by Guha et al., to appear in the 2003 ACM SIGGRAPH Symposium on Interactive 3D graphics, shows how the shadow mapping operation in the new NVIDIA GeForce4 cards can be viewed as a two-sided depth test in order to do CSG rendering efficiently. The result is an algorithm that can perform a topological sweep over an arrangement of objects in three dimensions. It also shows the first lower bounds on the number of rendering passes required for a hardware-assisted computation. (Application of the Two-Sided Depth Test to CSG Rendering. S. Guha, K. Munagala, S. Krishnan and S. Venkatasubramanian. To appear in the 2003 ACM SIGGRAPH Symposium on Interactive 3D graphics.)

This SIGGRAPH 2002 course, organized by Dinesh Manocha of UNC Chapel Hill, covered approaches to using graphics hardware for various geometric problems, including voronoi computation, proximity
queries, motion planning, and more.