We present a new approach for computing generalized proximity information of arbitrary 2D objects using graphics hardware. Using multi-pass rendering techniques and accelerated distance computation, our algorithm performs proximity queries not only for detecting collisions, but also for computing intersections, separation distance, penetration depth, and contact points and normals. Our hybrid geometry and image-based approach balances computation between the CPU and graphics subsystems. Geometric object-space techniques coarsely localize potential intersection regions or closest features between two objects, and image-space techniques compute the low-level proximity information in these regions. Most of the proximity information is derived from a distance field computed using graphics hardware. We demonstrate the performance in collision response computation for rigid and deformable body dynamics simulations. Our approach provides proximity information at interactive rates for a variet...

No abstract available.

We present techniques for fast motion planning by using discrete approximations of generalized Voronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are applicable to both static and dynamic environments of fairly high complexity. We compute a discrete Voronoi diagram by rendering a 3D distance mesh for each Voronoi site. The sites can be points, line segments, polygons, polyhedra, curves and surfaces. The computation of the generalized Voronoi diagram provides fast proximity query toolkits for motion planning. The tools provide the distance to the nearest obstacle stored in the Z-buffer, as well as the Voronoi boundaries, Voronoi vertices and weighted Voronoi graphs extracted from the frame buffer using continuation methods. We have implemented these algorithms and demonstrated their performance for path planning in a complex dynamic environment composed of more than 140,000 polygons.

We present a system for rendering very complex 3D models at interactive rates.We select a subset of the model as preferred viewpoints and partition the space into virtual cells.Each cell contains near geometry, rendered using levels of detail and visibility culling, and far geometry, rendered as a textured depth mesh.Our system automatically balances the screen-space errors resulting from geometric simplification with those from textureddepth-mesh distortion.We describe our prefetching and data management schemes, both crucial for models significantly larger than available system memory.We have successfully used our system to accelerate walkthroughs of a 13 million triangle model of a large coal-fired power plant and of a 1.7 million triangle architectural model.We demonstrate the walkthrough of a 1.3 GB power plant model with a 140 MB cache footprint.

This paper presents a new method for interactive rendering of globally illuminated static scenes. Global illumination is decomposed into view-independent (diffuse) and view-dependent (non-diffuse) components. The two are recombined during rendering using a hybrid geometry- and image-based approach along with multi-pass blending techniques. This approach allows the preprocessing of both components and the fast rendering of globally illuminated scenes. The view-independent component uses a traditional precomputed geometry-based radiosity solution that is rendered using standard graphics hardware. The view-dependent component is decomposed into “what is reflected ” (radiance with depth) and “how it is reflected ” (BRDF), and precomputed and rendered using image-based approaches. Radiance is stored as images with depth, and rendered using perspective reprojection; the BRDF is decomposed into an integration of incoming radiance and a directional modulation. The radiance integration term is approximated by convolving the reflected image with precomputed kernel textures based on material properties. The directional modulation is stored as a reflectance modulation texture based on material properties and is rendered using spheremapping during a blending pass.

Article Fast computation of generalized Voronoi diagrams using graphics hardware Share on Authors: Kenneth E. Hoff University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , John Keyser University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Ming Lin University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Dinesh Manocha University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile , Tim Culver University of North Carolina at Chapel Hill, Department of Computer Science University of North Carolina at Chapel Hill, Department of Computer ScienceView Profile Authors Info & Claims SIGGRAPH '99: Proceedings of the 26th annual conference on Computer graphics and interactive techniquesJuly 1999 Pages 277–286https://doi.org/10.1145/311535.311567Published:01 July 1999 311citation3,192DownloadsMetricsTotal Citations311Total Downloads3,192Last 12 Months86Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

: Many applications in computer graphics and virtual environments need to render datasets with large numbers of primitives and high depth complexityatinteractive rates. However, standard techniques like view frustum culling and a hardware z-bu#er are unable to display datasets composed of hundred of thousands of polygons at interactive frame rates on current high-end graphics systems. We add a #conservative" visibility culling stage to the rendering pipeline, attempting to identify and avoid processing of occluded polygons. Given a moving viewpoint, the algorithm dynamically chooses a set of occluders. Each occluder is used to compute a shadow frustum, and all primitives contained within this frustum are culled. The algorithm hierarchicallytraverses the model, culling out parts not visible from the current viewpoint using e#cient, robust, and in some cases specialized interference detection algorithms. The algorithm's performance varies with the location of the viewpoint and the depth...

Spline surfaces are routinely used to represent large-scale models for CAD and rmimation applications.In this paper, we present algorithms for interactive walkthrough of complex NURBS models composed of tens of thousands of patches on current graphics systems.Given a spline model, the algorithm precomputes simplification of a collection of patches and represents them hierarchically.Given a changing viewpoint, the algorithm combines these simplifications with dynamic tessellations to generate appropriate levels of detail.We also propose a system pipeline for parallel implementation on multi-processor configurations.Diiferent components, such as visibtit y and dynamic tessellation, are divided into independent threads.We describe an implement ation of our algorithm and report its performance on an SGI Onyx with Reality Enginez graphics accelerator and using three R4400 processors.It is able to render models composed of ahnost than 40,000 B6zier patches at 7-15 frames a second, almost an order of magnitude faster than previously known algorithms and implementations.

This paper presents a novel method for fast and efficient backface culling we reduce.the backface test to one logical operation per polygon while requiring only two bytes extra storage per polygon.The nornrafmask is introduced,where each bit is associated with a cluster of normals in a normal-space partitioning.A polygon's normal is approximated by the cluster of normals in which it falls; the cluster's normal mask is stored with the polygon in a preprocessing step.Although conceptually the normal masks require as many bits as the number of clusters, we observe that only two bytes are actually necessary.For each tkame (and for each viewing volume), we calculate the bockfuce mask by ORing the normals masks of all normal clusters that are backfacing.'he backface test finally reduces to a single logical AND operotwn between the polygon's normal maskand the backfacemask.

We present hierarchical occlusion maps (HOM) for visibility culling on complex models with high depth complexity.The culling algorithm uses an object space bounding volume hierarchy and a hierarchy of image space occlusion maps.Occlusion maps represent the aggregate of projections of the occluders onto the image plane.For each frame, the algorithm selects a small set of objects from the model as occluders and renders them to form an initial occlusion map, from which a hierarchy of occlusion maps is built.The occlusion maps are used to cull away a portion of the model not visible from the current viewpoint.The algorithm is applicable to all models and makes no assumptions about the size, shape, or type of occluders.It supports approximate culling in which small holes in or among occluders can be ignored.The algorithm has been implemented on current graphics systems and has been applied to large models composed of hundreds of thousands of polygons.In practice, it achieves significant speedup in interactive walkthroughs of models with high depth complexity.