GPGPU |
General-Purpose Computation Using Graphics Hardware
|
IntroductionGPGPU stands for General-Purpose computation on GPUs. With the increasing programmability of commodity graphics processing units (GPUs), these chips are capable of performing more than the specific graphics computations for which they were designed. They are now capable coprocessors, and their high speed makes them useful for a variety of applications. The goal of this page is to catalog the current and historical use of GPUs for general-purpose computation.
|
A Flexible Kernel for Adaptive Mesh Refinement on GPU This paper by Boubekeur (TU Berlin) and Schlick (INRIA) presents a flexible GPU kernel for adaptive on-the-fly refinement of meshes with arbitrary topology. By simply reserving a small amount of GPU memory to store a set of adaptive refinement patterns, on-the-fly refinement is performed by the GPU, without any preprocessing or additional topology data structure. The level of adaptive refinement can be controlled by specifying a per-vertex depth tag, in addition to usual position, normal, color and texture coordinates. This depth tag is used by the kernel to instanciate the correct refinement pattern. Finally, the refined patch produced for each triangle can be displaced by the vertex shader, using any kind of geometric refinement, such as Bezier patch smoothing, scalar valued displacement, procedural geometry synthesis or subdivision surfaces. This refinement engine requires no multi-pass rendering, fragment processing, or special preprocessing of the input mesh structure. It can be implemented on any GPU with vertex shading capabilities. (A Flexible Kernel for Adaptive Mesh Refinement on GPU, Tamy Boubekeur and Christophe Schlick, Computer Graphics Forum, 2008.)
Posted: 01 Apr 2008 [GPGPU /Computational Geometry/Surfaces and Modeling] # Applying graphics hardware to achieve extremely fast geometric pattern matching 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.)
Posted: 24 Jan 2008 [GPGPU /Computational Geometry] # Jump Flooding in GPU with Applications to Voronoi Diagram and Distance Transform 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 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 interests 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] )
Posted: 12 Mar 2006 [GPGPU /Computational Geometry] # Generic Mesh Refinement On GPU This paper by Boubekeur
and Schlick of the INRIA IPARLA Team describes a simple and easy-to-
integrate method for "on-GPU refinement" (tesselation + displacement),
adapted to any programmable GPU. This solution to the refinement problem
reduces the usual CPU->GPU bottleneck and memory consumption by using
instantiation over a template refinement pattern. This approach is usuful for
rendering objects that are represented as a simple mesh plus a detailed
displacement requiring deep tesselation (high-res maps, smooth surfaces,
procedural displacement, etc).
(Generic Mesh
Refinement on GPU. Tamy Boubekeur and Christophe Schlick. Proceedings
of Graphics Hardware 2005).
Posted: 15 Jan 2006 [GPGPU /Computational Geometry/Surfaces and Modeling] # To implement dynamic LOD on the GPU, a quadtree structure is created based on a seamless geometry image atlas,and all the nodes in the quadtree are packed into the atlas textures. There are two passes in the approach. In the first pass, the LOD selection is performed in fragment shaders. The resultant buffer is taken as the input texture to the second pass by vertex texturing, and node culling and triangulation are performed in vertex shaders. The LOD algorithm can generate adaptive meshes dynamically, and can be fully implemented on the GPU. It improves the efficiency of LOD selection, and reduces computing load on CPU. (Dynamic LOD on GPU. Junfeng Ji, Enhua Wu, Sheng Li, and Xuehui Liu. Proceedings
of Computer Graphics International 2005.)
Posted: 11 Aug 2005 [GPGPU /Computational Geometry/Surfaces and Modeling] # Hardware Assisted Natural Neighbour Interpolation Natural neighbour interpolation is a popular nonparametric method for interpolating among sample data points and is based on computing Voronoi diagrams. In this paper by Fan, Efrat, Koltun, Krishnan and Venkatasubramanian, we show how natural neighbour interpolation can be performed very efficiently on the GPU. The main advantage of this approach is that multiple interpolation queries can be issued simultaneously; the algorithm creates a scalar field for the interpolated result.
(Hardware Assisted Natural Neighbour Interpolation. Quanfu Fan, Alon Efrat, Vladlen Koltun, Shankar Krishnan, and Suresh Venkatasubramanian. Proc. 7th Workshop on Algorithms Engineering and Experimentation.)
Posted: 12 Dec 2004 [GPGPU /Computational Geometry] # This paper by Valerio Pascucci describes a simple technique to compute isosurfaces on programmable GPUs. Given the vertices of a tetrahedron a simple vertex program computes the position of the vertices, normal and connectivity of the potential portion of an isosurface contained in the tetrahedron (a marching tet approach). One main advantage of this technique is to offload the CPU of the task of computing the isosurface and more importantly to avoid storing the surface in main memory. Interestingly, one could compile a display list for a tetrahedral mesh and display different isosurfaces by changing an OpenGL parameter and always rendering the same list. The paper presents and comments in detail all the source code of the vertex program. ( Isosurface Computation Made Simple: Hardware Acceleration, Adaptive Refinement and Tetrahedral Stripping. V. Pascucci, Proceedings of VisSym 2004)
Posted: 03 May 2004 [GPGPU /Computational Geometry/Surfaces and Modeling] # DiFi: Fast 3D Distance Field Computation Using Graphics Hardware 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.)
Posted: 10 Apr 2004 [GPGPU /Computational Geometry] # Streaming Geometric Optimization using Graphics Hardware This paper proposes algorithms for computing extent measures and approximate representations of a stream of points in R2 or R3. 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.)
Posted: 15 Mar 2004 [GPGPU /Computational Geometry] # Interactive Collision Detection Between Complex Models Using Graphics Hardware This paper by Govindaraju et al. describes an approach for collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. The algorithm uses a two-pass rendering scheme to compute a potentially colliding set (PCS) in linear time using visibility queries with no precomputation or frame buffer read back. ( CULLIDE: Interactive Collision Detection Between Complex Models in Large Environments Using Graphics Hardware. Naga Govindaraju, Stephane Redon, Ming C. Lin and Dinesh Manocha. To appear in Proceedings of Graphics Hardware 2003).
Posted: 08 Jun 2003 [GPGPU /Computational Geometry] # Improved CSG Rendering using Overlap Graph Subtraction Sequences 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(n2) 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)
Posted: 17 Mar 2003 [GPGPU /Computational Geometry] # Hardware Assisted View Dependent Map Simplification 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)
Posted: 23 Jan 2003 [GPGPU /Computational Geometry/GIS] # The power of a two-sided depth test and its application to CSG rendering and depth extraction. 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. (The power of a two-sided depth test and its
application to CSG rendering and depth extraction. S. Guha, K. Munagala,
S. Krishnan and S. Venkatasubramanian. To appear in the 2003 ACM SIGGRAPH
Symposium on Interactive 3D graphics.)
Posted: 23 Jan 2003 [GPGPU /Computational Geometry] # Hardware-Assisted Computation of Depth Contours 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).
Posted: 23 Jan 2003 [GPGPU /Computational Geometry] # |
Categories
|
