Abstract

Kinematically consistent paths for multiple mobile robots that are collision free for the next T steps are generated by forming collision free polygons (CFP). The polygons can be generated in a distributive fashion for each robot. All paths inside CFP that are kinematically feasible for a certain robot are collision free with all other robots in the same collision cluster for the next T time samples and with any other robot in the workspace in general. The construction of CFP is through two log-linear complex operations. The first one involves computing the intersection of the path container polygon (PCP) of a robot with PCP of other robots in the cluster. The second involves computing the convex hull of intersecting points arising from the intersection of PCPs. Once CFP is computed for a robot it chooses a point within the CFP (its next waypoint) that minimizes a cost function and moves towards the point. The process is repeated till the goal is reached. The main advantage of this method is that the best and worst-case times for finding a T-step ahead collision free path is always log-linear. In many randomized search methods, finding the paths till the next waypoint results in a worst case complexity exponential in number of robots. The efficacy of the current method is well portrayed through simulations. Comparative results show that the following method finds a collision free path to next way point much quicker.

Abstract

No Results Found

Abstract

No Results Found

Abstract

Terrains and other geometric models have been traditionally stored locally. Their remote access presents the characteristics that are a combination of file serving and realtime streaming like audio-visual media. This paper presents a terrain streaming system based upon a client server architecture to handle heterogeneous clients over low-bandwidth networks. We present an efficient representation for handling terrains streaming. We design a client-server system that utilizes this representation to stream virtual environments containing terrains and overlayed geometry efficiently. We handle dynamic entities in environment and the synchronization of the same between multiple clients. We also present a method of sharing and storing terrain annotations for collaboration between multiple users. We conclude by presenting preliminary performance data for the streaming system

Abstract

Points, lines, and polygons have been the fundamental primitives in graphics. Graphics hardware is optimized to handle them in a pipeline. Other objects are converted to these primitives before rendering. Programmable GPUs have made it possible to introduce a wide class of computations on each vertex and on each fragment. In this paper, we outline a procedure to accurately draw high-level procedural elements efficiently using the GPU. The CPU and the vertex shader setup the drawing area on screen and pass the required parameters. The pixel shader uses ray-casting to compute the 3D point that projects to it and shades it using a general shading model. We demonstrate the fast rendering of 2D and 3D primitives like circle, conic, triangle, sphere, quadric, box, etc., with a combination of specularity, refraction, and environment mapping. We also show combination of objects, like Constructive Solid Geometry (CSG) objects, can be rendered fast on the GPU. We believe customized GPU programs for a new set of high-level primitives – which we call GPU Objects – is a way to exploit the power of GPUs and to provide interactive rendering of scenes otherwise considered too complex.

Abstract

We present a reordering-based procedure for the multiresolution decomposition of a point cloud in this paper. The points are first reordered recursively based on an optimal pairing. Each level of reordering induces a division of the points into approximation and detail values. A balanced quantization at each level results in further compression. The original point cloud can be reconstructed without loss from the decomposition. Our scheme does not require local reference planes for encoding or decoding and is progressive. The points also lie on the original manifold at all levels of decomposition. The scheme can be used to generate different discrete LODs of the point set with fewer points in each at low BPP numbers. We also present a scheme for the progressive representation of the point set by adding the detail values selectively. This results in the progressive approximation of the original shape with dense points even at low BPP numbers. The shape gets refined as more details are added and can reproduce the original point set. This scheme uses a wavelet decomposition of the detail coefficients of the multiresolution decomposition. Progressiveness is achieved by including different levels of the DWT decomposition at all multiresolution representation levels. We show that this scheme can generate much better approximations at equivalent BPP numbers for the point set.

Abstract

Visibility culling of a scene is a crucial stage for interactive graphics applications, particularly for scenes with thousands of objects. The culling time must be small for it to be effective. A hierarchical representation of the scene is used for efficient culling tests. However, when there are multiple view frustums (as in a tiled display wall), visibility culling time becomes substantial and cannot be hidden by pipelining it with other stages of rendering. In this paper, we address the problem of culling an object to a hierarchically organized set of frustums, such as those found in tiled displays and shadow volume computation. We present an adaptive algorithm to unfold the twin hierarchies at every stage in the culling procedure. Our algorithm computes from-point visibility and is conservative. The precomputation required is minimal, allowing our approach to be applied for dynamic scenes as well. We show performance of our technique over different variants of culling a scene to multiple frustums. We also show results for dynamic scenes.

Abstract

In this paper we present a new method for layer extraction by tracking a non-rigid body with no fixed motion model, in a video. The method integrates the graph cuts approach with robust point based tracking to achieve good tracking of the whole object over frames of a video. With the help of a little user interaction our method can perform layer extraction over irregular motion and difficult object boundaries. To achieve this we apply the 3D graph cuts on a pair of frames and propagate the labels obtained in the earlier frame to new frame by use of robust tracking method. The user is shown the results of the layer extraction and can provide extra strokes to improve the results.

Abstract

In this paper, we present a new approach for object removaland video completion of indoor scenes. In indoor images, the frames arenot affine related. The region near the object to be removed can havemultiple planes with sharply different motions. Dense motion estimationmay fail for such scenes due to missing pixels. We use feature tracking tofind dominant motion between two frames. The geometry of the motionof multiple planes is used to segment the motion layers into componentplanes. The homography corresponding to each hole pixel is used to warpa frame in the future or past for filling it. We show the application ofour technique on some typical indoor videos.

Abstract

Depth Images are viable representations that can be computed from the real world using cameras and/or other scanning devices. The depth map provides 2-kD structure of the scene. A set of Depth Images can provide hole-free rendering of the scene. Multiple views need to blended to provide smooth hole-free rendering, however. Such a representation of the scene is bulky and needs good algorithms for real-time rendering and efficient representation. In this paper, we present a discussion on the Depth Image representation and provide a GPU-based algorithm that can render large models represented using DIs in real time. We then present a proxy-based compression scheme for Depth Images and provide results for the same. Results are shown on synthetic scenes under different conditions and on some scenes generated from images. Lastly, we initiate discussion on varying quality levels in IBR and show a way to create representations using DIs with different trade-offs between model size and rendering quality. This enables the use of this representation for a variety of rendering situations.