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.
6288895
A Survey on Hair Modeling: Styling, Simulation, and Rendering
Realistic hair modeling is a fundamental part of creating virtual humans in computer graphics. This paper surveys the state of the art in the major topics of hair modeling: hairstyling, hair simulation, and hair rendering. Because of the difficult, often unsolved problems that arise in alt these areas, a broad diversity of approaches is used, each with strengths that make it appropriate for particular applications. We discuss each of these major topics in turn, presenting the unique challenges facing each area and describing solutions that have been presented over the years to handle these complex issues. Finally, we outline some of the remaining computational challenges in hair modeling
30756082
Sensation preserving simplification for haptic rendering
6243696
Geometry-driven physical interaction between avatars and virtual environments
We present an interactive technique on virtual contact handling for avatars in virtual environments using geometry-driven physics. If a contact has occurred between an articulated avatar and a virtual environment, the global penetration depth and contact points are estimated based on a fast local penetration depth computation for decomposed convex pieces. The penetration depth and contact information are then used to resolve overlap between the avatar and the virtual environment. If applicable, joint angles for an articulated body are computed using an inverse kinematics approach based on cyclic coordinate descent. Resulting dynamic response with friction is modeled with impulse-based dynamics under the Coulomb friction law. We demonstrate the algorithm on a modestly complex virtual environment. The resulting system is able to maintain an interactive frame rate of 30–60 Hz. Copyright © 2004 John Wiley & Sons, Ltd.
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
7169150
A versatile interactive 3D brush model
We present a flexible modeling approach capable of realistically simulating many varieties of brushes commonly used in painting. Our geometric model of brush heads is a combination of subdivision surfaces and hundreds of individual bristles represented by thin polygonal strips. We exploit bristle-to-bristle coherence, simulating only a fraction of the bristles and using interpolation for the remainder. Our dynamic model incorporates realistic physically-based deformation, including anisotropic friction, brush plasticity, and tip spreading. We use an energy minimization framework with a novel geometric representation of the brush head to generate a wider variety of brushes. Finally, we have developed an improved haptic model that provides realistic force feedback, directly related to the results of the brush dynamic simulation. Using this model, we are able to simulate a wide range of brush styles and create an excellent variety of strokes such as the crisp, curvy strokes of Western decorative painting, or rough scratchy strokes like certain Oriental calligraphy. We have also developed an exporter for a popular free 3D modeling package that makes it easier for non-programmers to create any desired style of brush, real or fanciful.
30294156
Cycle embedding in faulty wrapped butterfly graphs
In this paper, we study the maximal length of cycle embedding in a faulty wrapped butterfly graph BFn with at most two faults in vertices and/or edges. When there is one vertex fault and one edge fault, we prove that the maximum cycle length is n2n − 2 if n is even and n2n − 1 if n is odd. When there are two faulty vertices, the maximum cycle length is n2n − 2 for odd n. All these results are optimal because the wrapped butterfly graph is bipartite if and only if n is even. © 2003 Wiley Periodicals, Inc.
16920752
Runlength Limited Codes for Single Error-Detection and Single Error-Correction with Mixed Type Errors
Runlength limited (RLL) codes are used in magnetic recording. The error patterns that occur with peak detection magnetic recording systems when using a runlength-limited code consist of both symmetric errors and shift errors. We refer to shift errors and symmetric errors collectively as mixed type errors. A method of providing error control for mixed type errors that occur in a runlength limited code comprised of (d, k) constrained sequences is examined. The coding scheme is to choose parity blocks to insert in the constrained information sequence. The parity blocks are chosen to satisfy the constraints and to provide some error control. The cases of single error-detection and single error-correction are investigated, where the single error is allowed to be a shift error or a symmetric error. Bounds are discussed on the possible lengths for the parity blocks. It is shown that the single error-detection codes are the best possible in terms of the length of the parity blocks.
17862666
Virtual Interaction for Effective E-Learning
This research investigates whether information technologies, such as automated question answering (QA), can add interactivity into a multimedia-based e-learning system, as well as how this type of virtual interaction affects the effectiveness of e-learning. Based on a review of multiple learning theories and technologies, an exploratory model for studying the effectiveness of interactive e-learning, Learning with Virtual Mentors (LVM), is proposed and a prototype system is developed to implement the LVM model. A series of studies, including a controlled experiment and surveys, have been conducted to explore the relationships among the core constructs of the LVM model: learning phases, system interactivity, learning activity, and learning outcomes. Findings indicate that virtual interaction positively impacts student behaviors by encouraging students to interact more and increasing student satisfaction with the learning process; however, the correlation between virtual interaction and actual learning performance is limited. Consequently, the LVM model needs to be further explored and developed.
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.
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.