Efficient Contact Determination Between Geometric Models (2005)
The problem of interference detection or contact determination between two or more objects in dynamic environment is fundamental in computer graphics, robotics, and virtual environments. Most of the...
Accurate Minkowski Sum Approximation of Polyhedral Models (2004)
Gokul Varadhan, Dinesh Manocha, Rod Bunny, Bunny Offset
We present an algorithm to approximate the 3D Minkowski sum of polyhedral objects. Our algorithm decomposes the polyhedral objects into convex pieces, generates pairwise convex Minkowski sums and...
International Journal of Computational Geometry Applications (2004)
Jonathan Cohen, Dinesh Manocha
We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each...
Simplifying Polygonal Models Using Successive Mappings (2004)
Jonathan Cohen, Dinesh Manocha, Marc Olano
We present the use of mapping functions to automatically generate levels of detail with known error bounds for polygonal models. We develop a piece-wise linear mapping function for each...
Quick-VDR: Interactive View-Dependent Rendering of Massive Models (2004)
Sung-eui Yoon, Brian Salomon, Russell Gayle, Dinesh Manocha
We present a novel approach for interactive view-dependent rendering of massive models. Our algorithm combines view-dependent simplification, occlusion culling, and out-of-core rendering. We...
Fast Computation of Database Operations using Graphics (2004)
Naga K. Govindaraju, Brandon Lloyd, Wei Wang, Ming Lin, Dinesh Manocha
We present new algorithms on commodity graphics processors for performing fast computation of several common database operations. Specifically, we consider operations such as conjunctive selections,...
Interactive and Continuous Collision Detection for Avatars in Virtual Environments (2003)
Stephane Redon, Young J. Kim, Ming C. Lin, Dinesh Manocha, Jim Templeman
We present a fast algorithm for continuous collision detection between a moving avatar and its surrounding virtual environment. We model the avatar as an articulated body using line-skeletons with...
Feature-Sensitive Subdivision and Isosurface Reconstruction (2003)
Gokul Varadhan, Shankar Krishnan, Young J. Kim, Dinesh Manocha
We present improved subdivision and isosurface reconstruction algorithms for polygonizing implicit surfaces and performing accurate geometric operations. Our improved reconstruction algorithm uses...
Collision And Proximity Queries (2003)
INTRODUCTION In a geometric context, a collision or proximity query reports information about the relative configuration or placement of two objects. Some of the common examples of such queries...
M. Doggett, W. Heidrich, W. Mark, A. Schilling (editors, Naga K. Govindaraju, Stephane Redon, ...
We present a novel approach for fast collision detection between multiple deformable and breakable objects in a large environment using graphics hardware. Our algorithm takes into account low...
Sung-eui Yoon, Brian Salomon, Dinesh Manocha
This paper presents a novel algorithm combining view-dependent rendering and conservative occlusion culling for interactive display of complex environments. A vertex hierarchy of the entire scene is...
We present an incremental algorithm to compute image-based simplifications of a large environment. We use an optimization-based approach to generate samples based on scene visibility, and from each...
Interactive Shadow Generation in Complex Environments (2003)
Naga K. Govindaraju, Brandon Lloyd, Sung-eui Yoon, Avneesh Sud, Dinesh Manocha
We present a new algorithm for interactive generation of hard-edged, umbral shadows in complex environments with a moving light source. Our algorithm is based on a hybrid approach that combines some...
Incremental Penetration Depth Estimation Between Convex Polytopes Using Dual-space Expansion (2003)
Young J. Kim, Ming C. Lin, Dinesh Manocha
We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski...
Interactive Visibility Culling in Complex Environments using (2003)
Naga K. Govindaraju, Avneesh Sud, Sung-eui Yoon, Dinesh Manocha
We present occlusion-switches for interactive visibility culling in complex 3D environments. An occlusionswitch consists of two GPUs (graphics processing units) and each GPU is used to either compute...
Brian Salomon, Maxim Garber, Ming C. Lin, Dinesh Manocha
We present a novel approach for interactive navigation in complex 3D synthetic environments using path planning. Our algorithm precomputes a global roadmap of the environment by using a variant of...
PRECISE: Efficient Multiprecision Evaluation of Algebraic (2003)
Shankar Krishnan, Mark Foskey, Tim Culver, John Keyser, Dinesh Manocha
Many geometric problems such as generalized Voronoi diagrams, medial axis computations, and boundary evaluation involve computation and manipulation of non-linear algebraic primitives such as curves...
Shankar Krishnan, Dinesh Manocha
Computing the visible portions of curved surfaces from a given viewpoint is of great interest in many applications. It is closely related to the hidden surface removal problem in computer graphics...
Closest Point Query Among The Union Of Convex Polytopes Using Rasterization Hardware (2002)
Young J. Kim, Kenneth Hoff, Ming C. Lin, Dinesh Manocha
We present a novel approach using rasterization hardware to perform the following query: Given a collection of convex polytopes in 3D, find the closest point from some given point inside the...
IRW: An Incremental Representation for Image-Based Walkthroughs (2002)
David Gotz, Ketan Mayer-patel, Dinesh Manocha
We present a new representation for image-based interactive walkthroughs. The target applications reconstruct a scene from novel viewpoints using samples from a spatial image dataset collected from a...
Out-of-Core Rendering of Massive Geometric Environments (2002)
Gokul Varadhan, Dinesh Manocha
We present an external memory algorithm for fast display of very large and complex geometric environments. We represent the model using a scene graph and employ different culling techniques for...
Form Metrics for Interactive Rendering via . . . (2002)
Advisor Prof, Stephen Pizer, Gary Bishop, Reader Prof, Dinesh Manocha, Prof Anselmo Lastra, ...
Robert A. Katz ###################################### ################################ (Under the direction of Professor Stephen M. Pizer) This work presents a method for quantifying important form...
Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement (2002)
We present a novel and fast algorithm to compute penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translation distance to separate them...
Fast Penetration Depth Computation for Physically-based Animation (2002)
Young J. Kim, Miguel A. Otaduy, Ming C. Lin, Dinesh Manocha
We present a novel and fast algorithm to compute penetration depth (PD) between two polyhedral models for physically-based animation. Given two overlapping polyhedra, it computes the minimal...
Parallel Occlusion Culling for Interactive Walkthroughs using Multiple GPUs (2002)
Naga K. Govindaraju, Avneesh Sud, Sung-eui Yoon, Dinesh Manocha
We present a new parallel occlusion culling algorithm for interactive display of large environments. It uses a cluster of three graphics processing units (GPUs) to compute an occlusion...
Mark Foskey, Dinesh Manocha, Tim Culver, John Keyser
this paper. Exact Computation as a Practical Approach. There is no question that EGC is slower than computation relying solely on machine precision arithmetic. The question is whether the slowdown is...
International Journal of Computational Geometry Applications (2002)
Crin-cnrs Inria Lorraine, Batiment Loria, Communicated Ming, C. Lin, Dinesh Manocha
Recognizing 3D objects from their 2D silhouettes is a popular topic in computer vision. Object reconstruction can be performed using the volume intersection approach.
GigaWalk: Interactive Walkthrough of Complex Environments (2002)
William V. Baxter, Iii Avneesh, Sud Naga, K. Govindaraju, Dinesh Manocha
We present a new parallel algorithm for interactive walkthrough of complex, gigabyte-sized environments. Our approach combines occlusion culling and levelsof -detail and uses two graphics pipelines...
Kenneth E. Hoff Iii, Andrew Zaferakis, Ming Lin, Dinesh Manocha
We present an approach for computing generalized proximity information between arbitrary polygonal models using graphics hardware acceleration. Our algorithm combines object-space localization,...
Spatially-Encoded Far-Field Representations for Interactive Walkthroughs (2002)
Andrew Wilson, Ketan Mayer-pate, Dinesh Manocha
We introduce the notion of spatially encoded video and use it for efficiently representing image-based impostors for interactive walkthroughs. As part of a pre-process, we automatically decompose the...
DEEP: Dual-space Expansion for Estimating Penetration depth between convex polytopes (2002)
Young J. Kim, Ming C. Lin, Dinesh Manocha
We present an incremental algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the...
Spatially-Encoded Far-Field Representations for Interactive Walkthroughs (2002)
Andrew Wilson, Ketan Mayer-patel, Dinesh Manocha
We introduce the notion of spatially encoded video and use it for efficiently representing image-based impostors for interactive walkthroughs. As part of a pre-process, we automatically decompose the...
Spatially-Encoded Far-Field Representations for Interactive (2001)
Andrew Wilson, Ketan Mayer-patel, Dinesh Manocha
We introduce the notion of spatially encoded video and use it for efficiently representing image-based impostors for interactive walkthroughs. As part of a pre-process, we automatically decompose the...
Six-Degree-of-Freedom Haptic Display Using Localized Contact Computations (2001)
We present a six-degree-of-freedom haptic rendering algorithm using localized contact computations. It takes advantage of high motion coherence due to fast force update and spatial locality near the...
Simplification Envelopes (2001)
Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, ...
We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model. Our approach guarantees that all points of an approximation...
Amitabh Varshney, Frederickp Brooks, David C. Richardson, William V. Wright, Dinesh Manocha
Aparallel, analytic approach for de#ning and computing the inter- and intra-molecular interfaces in three dimensions is described. The molecular interface surfaces are derivedfrom approximations to...
Dinesh Manocha, Amitabh Varshney, Hans Weber
We highlight a new algorithm for evaluating the surface intersection curve using a matrix formulation. The projection of the intersection curve is represented as the singular set of a bivariate...
Simplification Envelopes (2001)
Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, ...
We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model. Our approach guarantees that all points of an approximation...
Efficient Rendering of Trimmed NURBS (2001)
We present an algorithm for interactive display of trimmed NURBS surfaces. The algorithm converts the NURBS surfaces to B'ezier surfaces and NURBS trimming curves into B'ezier curves. It tessellates...
DAB: Interactive Haptic Painting with 3D Virtual Brushes (2001)
Bill Baxter, Vincent Scheib, Ming C. Lin, Dinesh Manocha
We present a novel painting system with an intuitive haptic interface, which serves as an expressive vehicle for interactively creating painterly works. We introduce a deformable, 3D brush model,...
DAB: Interactive Haptic Painting with 3D Virtual Brushes (2001)
Bill Baxter, Vincent Scheib, Ming C. Lin, Dinesh Manocha
We present a novel painting system with an intuitive haptic interface, which serves as an expressive vehicle for interactively creating painterly works. We introduce a deformable, 3D brush model,...
Fast Distance Queries with Rectangular Swept Sphere Volumes (2001)
Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha
: We present new distance computation algorithms using hierarchies of rectangular swept spheres. Each bounding volume of the tree is described as the Minkowski sum of a rectangle and a sphere, and...
Fast and Simple 2D Geometric Proximity Queries Using Graphics Hardware (2000)
Kenneth E. Hoff Iii, Andrew Zaferakis, Ming Lin, Dinesh Manocha
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,...
A Hybrid Approach for Determinant Signs of (2000)
Tim Culver, John Keyser, Dinesh Manocha, Shankar Krishnan
Many geometric computations have at their core the evaluation of the sign of the determinant of a matrix. A fast, failsafe determinant sign operation is often a key part of a robust implementation....
A Voronoi-Based Hybrid Motion Planner for Rigid Bodies (2000)
Mark Foskey, Maxim Garber, Ming C. Lin, Dinesh Manocha
We present a hybrid path planning algorithm for rigid bodies translating and rotating in a 3D workspace. Our approach generates a Voronoi roadmap in the workspace and combines it with "bridges"...
Fast Proximity Queries with Swept Sphere Volumes (2000)
Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha
: We present novel algorithms for fast proximity queries using swept sphere volumes. The set of proximity queries includes collision detection and both exact and approximate separation distance...
Simplification Envelopes (2000)
Jonathan Cohen, Amitabh Varshney, Dinesh Manocha, Greg Turk, Hans Weber, Pankaj Agarwal, ...
We propose the idea of simplification envelopes for generating a hierarchy of level-of-detail approximations for a given polygonal model. Our approach guarantees that all points of an approximation...
V-COLLIDE: Accelerated Collision Detection for VRML (2000)
Thomas C. Hudson, Ming C. Lin, Jonathan Cohen, Stefan Gottschalk, Dinesh Manocha
Collision detection is essential for many applications involving simulation, behavior and animation. However, it has been regarded as a computationallydemanding task and is often treated as an...
Six Degree-of-Freedom Haptic Display of Polygonal Models (2000)
Arthur Gregory, Ajith Mascarenhas, Stephen Ehmann, Ming Lin, Dinesh Manocha
: We present an algorithm for haptic display of moderately complex polygonal models with a six degree of freedom (DOF) force feedback device. We make use of incremental algorithms for contact...
A Voronoi-Based Hybrid Motion Planner for Rigid Bodies (2000)
Mark Foskey, Maxim Garber, Ming C. Lin, Dinesh Manocha
We present a hybrid path planning algorithm for rigid bodies translating and rotating in a 3D workspace. Our approach generates a Voronoi roadmap in the workspace and combines it with "bridges"...
A Video-Based Rendering Acceleration Algorithm for Interactive Walkthroughs (2000)
Andrew Wilson, Ming C. Lin, Dinesh Manocha, Boon-lock Yeo, Minerva Yeung
We present a new approach for faster rendering of large synthetic environments using video-based representations. We decompose the large environment into cells and pre-compute video based impostors...
Accurate Computation of the Medial Axis of a Polyhedron (2000)
Tim Culver, John Keyser, Dinesh Manocha
: We present an accurate and efficient algorithm to compute the internal Voronoi region and medial axis of a 3-D polyhedron. It uses exact arithmetic and representations for accurate computation of...
MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves (2000)
John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan
: Wepresent MAPC, a library for exact representation of geometric objects -- specifically points and algebraic curves in the plane. Our library makes use of several new algorithms, whichwe present...
Six Degree-of-Freedom Haptic Display of Polygonal Models (2000)
Arthur Gregory, Ajith Mascarenhas, Stephen Ehmann, Ming Lin, Dinesh Manocha
: We present an algorithm for haptic display of moderately complex polygonal models with a six degree of freedom (DOF) force feedback device. We make use of incremental algorithms for contact...
Six Degree-of-Freedom Haptic Display of Polygonal Models (2000)
Arthur Gregory, Ajith Mascarenhas, Stephen Ehmann, Ming Lin, Dinesh Manocha
: We present an algorithm for haptic display of moderately complex polygonal models with a six degree of freedom (DOF) force feedback device. We make use of incremental algorithms for contact...
Fast Distance Queries with Rectangular Swept Sphere Volumes (2000)
Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha
We present new distance computation algorithms using hierarchies of rectangular swept spheres. Each bounding volume of the tree is described as the Minkowski sum of a rectangle and a sphere, and fits...
Hierarchical Levels of Detail for Fast Display of Large Static and Dynamic Environments (2000)
We present a new approach for fast display of large static and dynamic environments. Given a geometric dataset, we represent it using a scene graph and automatically compute levels of detail (LODs)...
Computing Boolean Combinations Of Solids Composed Of Free-Form Surfaces (2000)
Shankar Krishnan, Dinesh Manocha
We present efficient and accurate algorithms for Boolean combinations of solids composed of sculptured models. The surface of each solid is represented as a collection of trimmed and untrimmed spline...
Daniel Aliaga, Jon Cohen, Andrew Wilson, Eric Baker, Hansong Zhang, Carl Erikson, ...
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...
Randomized Path Planning for a Rigid Body Based on Hardware Accelerated Voronoi Sampling (1999)
Charles Pisula, Kenneth Hoff Iii, Ming C. Lin, Dinesh Manocha
Probabilistic roadmap methods have recently received considerable attention as a practical approach for motion planning in complex environments. These algorithms sample a number of configurations in...
Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware (1999)
Kenneth E. Hoff Iii, Tim Culver, John Keyser, Ming Lin, Dinesh Manocha
: We present a new approach for computing generalized 2D and 3D Voronoi diagrams using interpolation-based polygon rasterization hardware. We compute a discrete Voronoi diagram by rendering a three...
Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware (1999)
Kenneth E. Hoff Iii, Tim Culver, John Keyser, Ming Lin, Dinesh Manocha
We present a new approach for computing generalized 2D and 3D Voronoi diagrams using interpolation-based polygon rasterization hardware. We compute a discrete Voronoi diagram by rendering a three...
MAPC: A library for Efficient and Exact Manipulation of Algebraic Points and Curves (1999)
John Keyser, Tim Culver, Dinesh Manocha, Shankar Krishnan
: We present MAPC, a library for exact representation of geometric objects---specifically points and algebraic curves in the plane. Our library makes use of several new algorithms, which we present...
Kenneth Hoff, Iii Tim, Culver John, Keyser Ming, C. Lin, Dinesh Manocha
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...
Kenneth Ho, Iii Tim, Culver John, Keyser Ming, C. Lin, Dinesh Manocha
We present techniques for fast motion planning by using discrete approximations of generalizedVoronoi diagrams, computed with graphics hardware. Approaches based on this diagram computation are...
High Speed and High Fidelity Visualization of Complex CSG Models (1999)
High Speed, High Fidelity Visualization, Subodh Kumar, Shankar Krishnan, Dinesh Manocha, Atul Narkhede
We present a system for fast and accurate display of CSG (constructive solid geometry) models. Such models have as primitives, polyhedra and solids whose boundaries can be represented using rational...
Numeric-Symbolic Algorithms for Evaluating One-Dimensional Algebraic Sets (1999)
Shankar Krishnan, Dinesh Manocha
: We present efficient algorithms based on a combination of numeric and symbolic techniques for evaluating one-dimensional algebraic sets in a subset of the real domain. Given a description of a...
Representation, Boundary Computation and Fast Display of CSG Models with NURBS Primitives (1999)
Shankar Krishnan, Subodh Kumar, Dinesh Manocha
We present efficient and accurate algorithms for Boolean combinations of solids composed of sculptured models. The boundary of each solid is represented as a collection of trimmed spline surfaces and...
Shankar Krishnan, Dinesh Manocha
Computing the visible portions of curved surfaces from a given viewpoint is of great interest in many applications. It is closely related to the hidden surface removal problem in computer graphics...
John Keyser, Shankar Krishnan, Dinesh Manocha
We present efficient representations and algorithms for exact boundary computation on low degree sculptured CSG solids using exact arithmetic. Most of the previous work using exact arithmetic has...
Algebraic Pruning: A Fast Technique for Curve and Surface Intersection (1999)
Dinesh Manocha, Shankar Krishnan
: Computing the intersection of parametric and algebraic curves and surfaces is a fundamental problem in computer graphics and geometric modeling. This problem has been extensively studied in the...
John Keyser, Shankar Krishnan, Dinesh Manocha
We present efficient algorithms for exact boundary computation on low degree sculptured CSG solids using exact arithmetic. These include algorithms for computing the intersection curves of low-degree...
Solving Algebraic Systems using Matrix Computations (1999)
Dinesh Manocha, Shankar Krishnan
: Finding zeros of algebraic sets is a fundamental problem in scientific and geometric computation. It arises in symbolic and numeric techniques used to manipulate sets of polynomial equations. In...