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.
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.
16043357
Six-degree-of-freedom haptic display using localized contact computations
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 contact regions. We first decompose the surface of each polyhedron into convex pieces and construct bounding volume hierarchies for fast proximity queries. Once the objects are intersecting, the penetration depth (PD) is estimated in the contact neighborhood between each pair of decomposed convex pieces, using a new incremental method based on local optimization. Given the computed PD values, multiple contacts near a local region are clustered together to further speed up contact force determination. We have implemented these algorithms and applied them to complex contact scenarios consisting of multiple contacts.
14636806
Channel density reduction by routing over the cells
We propose a new approach for reducing the density of a channel by routing some nets (or subnets) over the cells (i.e., outside the channel). Previous research assumed that the more nets being routed over the cells the greater the reduction in the channel density. We show that only the removal of critical nets contributes to the re- duction in the channel density. We divide channel into zones where each zone has a zone density and the removal of any net from a zone will reduce its density by one. In order to reduce the channel density, only certain critical zones need to have their nets routed over the cells. A bipartite graph is used to represent the relationship between nets and zones. The problem is transformed into a constrained covering problem and formulated as an integer linear programming problem. In comparison with previous research, our approach reduces more channel densities while using fewer tracks over the cells. For Deutsch's difficult khannel, a previous aiiproach needs 15 tracks over the cells to reduce the channel density by 3 while we need only 5 tracks to achieve the same result . Index Terms-Over-the-cell routing, channel density reduction, stan- dard-cell layout, VLSI routing, integer linear programming.
205481590
Fast and simple algorithms to count the number of vertex covers in an interval graph
This study provides the following fast and simple algorithms for an interval graph: (1) an algorithm for counting the number of vertex covers, and (2) an algorithm for counting the number of minimal vertex covers.
50312
The distributed program reliability analysis on ring-type topologies
Abstract Distributed computing system (DCS) has become very popular for its high fault-tolerance, potential for parallel processing, and better reliability performance. One of the important issues in the design of the DCS is the reliability performance. Distributed program reliability (DPR) is addressed to obtain this reliability measure. In this paper, we propose a polynomial-time algorithm for computing the DPR of ring topology and show that solving the DPR problem on a ring of trees topology is NP-hard. Scope and purpose The widespread use of distributed computing system is due to the price–performance revolution in microelectronics, the development of cost-effective and efficient communication subsets, the development of resource sharing software, and the increased user demands for communication, economical sharing of resources, and productivity. This article is concerned with the analysis of distributed program reliability on a ring-distributed computing system. The distributed program reliability is a useful measure for reliability evaluation of distributed computing system. The distributed program reliability analyses also give a good index for designing a high-reliability-performance-distributed computing system.
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.
16198203
On Semantics of Reactive Rule-Based Systems
In this paper we address special issues which arise when the rule-based programming paradigm is emlployed in development of reactive real-time systems. We begin by presenting a rule-based language which has emerged while developing intelligent cruise control systems. We describe a naive operational semantics based on an an implemented inference engine, and explain why the semantics is not appropriate in safety-critical real-time contexts. We then deene a number of correct-ness criteria ensuring termination, consistency and determinism, based on a formal declarative semantics. However, the declarative semantics is non-constructive. In order to be able to build an implementation satisfying the correctness criteria, two alternative approaches are proposed. Both approaches build upon static checks of a rule-based program. In the rst approach some correctness criteria are met by accepting only stratiied programs after the static checks. In the second approach we accept programs which are correct with respect to a constructive semantics. For both approaches we present the analysis methods and soundness results with respect to the desired declarative semantics. Abstract In this paper we address special issues which arise when the rule-based programming paradigm is emlployed in development of reactive real-time systems. We begin by presenting a rule-based language which has emerged while developing intelligent cruise control systems. We describe a naive operational semantics based on an an implemented inference engine, and explain why the semantics is not appropriate in safety-critical real-time contexts. We then deene a number of correct-ness criteria ensuring termination, consistency and determinism, based on a formal declarative semantics. However, the declarative semantics is non-constructive. In order to be able to build an implementation satisfying the correctness criteria, two alternative approaches are proposed. Both approaches build upon static checks of a rule-based program. In the rst approach some correctness criteria are met by accepting only stratiied programs after the static checks. In the second approach we accept programs which are correct with respect to a constructive semantics. For both approaches we present the analysis methods and soundness results with respect to the desired declarative semantics.