14643295
Adaptive grouping and subdivision for simulating hair dynamics
We present a novel approach for adaptively grouping and subdividing hair using discrete level-of-detail (LOD) representations. The set of discrete LODs include hair strands, clusters and strips. Their dynamic behavior is controlled by a base skeleton. The base skeletons are subdivided and grouped to form clustering hierarchies using a quad-tree data structure during the precomputation. At run time, our algorithm traverses the hierarchy to create continuous LODs on the fly and chooses both the appropriate discrete and continuous hair LOD representations based on the motion, the visibility, and the viewing distance of the hair from the viewer. Our collision detection for hair represented by the proposed LODs relies on a family of "swept sphere volumes" for fast and accurate intersection computations. We also use an implicit integration method to achieve simulation stability while allowing us to take large time steps. Together, these approaches for hair simulation and collision detection offer the flexibility to balance between the overall performance and visual quality of the animated hair. Furthermore, our approach is capable of modeling various styles, lengths, and motion of hair.
7639620
Stable and responsive six-degree-of-freedom haptic manipulation using implicit integration
In this paper we present a novel approach for simulating the rigid body dynamics of a haptically manipulated object using implicit integration. Our formulation requires the linearization of contact and manipulation forces, and it provides higher stability and responsiveness than previous methods. The linearization of contact forces, coupled with fast, perceptually based collision detection algorithms, enables us to perform highly stable and responsive 6-degree-of-freedom haptic rendering of complex polygonal models.
206451107
Sensation-Preserving Haptic Rendering
Most human-computer interactive systems focus primarily on the graphical rendering of visual information and, to a lesser extent, on the display of auditory information. Haptic interfaces have the potential to increase the quality of human-computer interaction by accommodating the sense of touch. They provide an attractive augmentation to visual display and enhance the level of understanding of complex data sets. A haptic rendering system generates contact or restoring forces to prevent penetration into the virtual objects and create a sense of touch. The system computes contact forces by first detecting if a collision or penetration has occurred. Then, the system determines the (projected) contact points on the model surface. Finally, it computes restoring forces based on the amount of penetration. Researchers have recently investigated the problem of rendering the contact forces and torques between 3D virtual objects. This problem is known as six-degrees-of-freedom (6-DOF) haptic rendering, as the computed output includes both 3-DOF forces and 3-DOF torques. This article presents an overview of our work in this area. We suggest different approximation methods based on the principle of preserving the dominant perceptual factors in haptic exploration.
15734500
Fast Animation of Lightning Using an Adaptive Mesh
We present a fast method for simulating, animating, and rendering lightning using adaptive grids. The "dielectric breakdown model" is an elegant algorithm for electrical pattern formation that we extend to enable animation of lightning. The simulation can be slow, particularly in 3D, because it involves solving a large Poisson problem. Losasso et al. recently proposed an octree data structure for simulating water and smoke, and we show that this discretization can be applied to the problem of lightning simulation as well. However, implementing the incomplete Cholesky conjugate gradient (ICCG) solver for this problem can be daunting, so we provide an extensive discussion of implementation issues. ICCG solvers can usually be accelerated using "Eisenstat's trick," but the trick cannot be directly applied to the adaptive case. Fortunately, we show that an "almost incomplete Cholesky" factorization can be computed so that Eisenstat's trick can still be used. We then present a fast rendering method based on convolution that is competitive with Monte Carlo ray tracing but orders of magnitude faster, and we also show how to further improve the visual results using jittering
9041268
Modeling ice dynamics as a thin-film Stefan problem
Large, 3D ice formations such as icicles exhibit a high degree of geometric and optical complexity. Modeling these features by hand can be a daunting task, so we present a novel physically-based algorithm for simulating this phenomenon. Solidification is usually posed as a so-called 'Stefan problem', but the problem in its classic form is inappropriate for simulating the ice typically found in a winter scene. We instead use the 'thin-film' variant of the Stefan problem to derive velocity equations for a level set simulation. However, due to the scales involved in the problem, even an adaptive grid level set solver is still insufficient to track the tip of an icicle. Therefore, we derive an analytical solution for the icicle tip and use it to correct the level set simulation. The results appear to be in agreement with experimental data. We also present a physically-based technique for modeling ripples along the ice surface that alleviates the need to explicitly track small-scale geometry. To our knowledge, our approach is the most complete model available, and produces complex visual phenomena that no previous method has been able to capture.
8273317
A video-based rendering acceleration algorithm for interactive walkthroughs
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 using MPEG compression to represent sets of objects that are far from each cell. At runtime, we decode the MPEG streams and use rendering algorithms that provide nearly constant-time random access to any frame. The resulting system has been implemented and used for an interactive walkthrough of a model of a house with 260,000 polygons and realistic lighting and textures. It is able to render this model at 16 frames per second (an eightfold improvement over simpler algorithms) on average on a Pentium II PC with an off-the-shelf graphics card.
33339608
Almost Optimal Solutions for Bin Coloring Problems
In this paper we study two interesting bin coloring problems: Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC), motivated from several applications in networking. For the MinBC problem, we first show that it is NP-complete, and then present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT+2 and OPT+1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio.
760636
Accelerated occlusion culling using shadow frusta
Many applications in computer graphics and virtual environments need to render datasets with large numbers of primitives and high depth complexity at interactive 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 frustumare culled. The algorithmhierarchicallytraverses 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 complexity of the model. In the worst case it is linear in the input size with a small constant. In this paper, we demonstrate its performance on a city model composed of 500;000 polygons and possessing varying depth complexity. We are able to cull an average of 55% of the polygons that would not be culled by view-frustum culling and obtain a commensurate improvement in frame rate. The overall approach is e ective and scalable, is applicable to all polygonal models, and can be easily implemented on top of view-frustum culling.
45057698
The distributed program reliability analysis on star topologies
Abstract A distributed computing system consists of processing elements, communication links, memory units, data files, and programs. These resources are interconnected via a communication network and controlled by a distributed operating system. The distributed program reliability in a distributed computing system is the probability that a program which runs on multiple processing elements and needs to retrieve data files from other processing elements will be executed successfully. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. In this paper, we show that computing the distributed program reliability on the star distributed computing systems is NP-hard. We also develop an efficiently solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. Scope and purpose Recent advances in VLSI circuitry have a tremendous impact on the price-performance revolution in microelectronics. This development has led to an increased use of workstations connected in the form of a powerful distributed computing system. Potential benefits offered by such distributed computing systems include better cost performance, enhanced fault tolerance, increased system throughput, and efficient sharing of resources. Distributed program reliability is an important measure that should be examined for designing a high fault-tolerance distributed computing system. This reliability varies according to (1) the topology of the distributed computing system, (2) the reliability of the communication edges, (3) the data files and programs distribution among processing elements, and (4) the data files required to execute a program. This article is concerned with the analysis of distributed program reliability on star distributed computing systems.
9086045
The distributed program reliability analysis on star topologies
We show that computing distributed program reliability on the star distributed computing system is NP-hard. We develop a polynomially solvable case to compute distributed program reliability when some additional file distribution is restricted on the star topology. We also propose a polynomial time algorithm for computing distributed program reliability with an approximate solution when the star topology is not satisfied with the additional file distribution.
2903221
Algorithms for clique-independent sets on subclasses of circular-arc graphs
A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K2-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given.