The deformation of cloth is one of the essential aspects to increase the sense of reality in the area of VR (Virtual Reality) or game programming. In contrast, when a character wearing clothes or hanging a flag moves abruptly and rapidly, it is not easy to express the natural movement of the cloth in a limited time. In this paper, the position-based approximation method that considers the nonlinearity which is a vital feature in the realistic deformation of cloth and responds to the abrupt and frequent external forces as well is proposed. Our method that processes the non-linear deformation properties geometrically can produce a fast and stable cloth animation. In addition, it reflects the physical attributes to the geometrical relation so that the visibly-plausible movement of cloth can be generated. As a result, cloth animation that is stable despite the fast movement of a car and realistic to the external environmental change such as the driving direction of the car or the surface of the road, can be created.

Abstract Many fine art pieces have been reproduced in digital form. The digital reproductions have been used to store and transmit the original work. In contrast, mobiles, or moving sculptures, such as those designed by Alexander Calder cannot be reproduced realistically by photographs and/or static images. The real characteristics of mobiles come from the motions generated by interactive external forces applied to their structures. Hence people could not fully enjoy them through static images or even static three‐dimensional models. We present a virtual mobile system where users can easily control the mobile and can feel the impressions that the artist originally intended to provide. Virtual winds are generated by blowing on a microphone which then exert external forces to the mobile. This microphone interface lets users control the mobile while they are watching it through a monitor. We introduce a linear time solution for the constraint dynamics and an improved impulse dynamics to speed up the simulation. Using these techniques, we achieve a real‐time simulation of the mobile on personal computers. The techniques presented can easily be extended to simulate other interactive dynamics systems. Copyright ©2001 John Wiley & Sons, Ltd.

We introduce a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity. Ongoing experimental work in testing and evaluating these algorithms has thus far shown very promising results.

We describe an efficient parallel algorithm to solve the single function coarsest partition problem. The algorithm runs in O (log n) time using O(n log log n) operations on the arbitrary CRCW PRAM. The previous best-known algorithms run in O(log2 n) time using O(n log2n) operations on the CREW PRAM, and O(log n) time using O (n log n) operations on the arbitrary CRCW PRAM. Our solution is based on efficient algorithms for solving several subproblems that are of independent interest. In particular, we present efficient parallel algorithms to find a minimal starting point of a circular string with respect to lexicographic ordering and to sort lexicographically a list of strings of different lengths.

Parallel algorithms for several important combinatorial problems such as the all nearest smaller values problem, triangulating a monotone polygon, and line packing are presented. These algorithms achieve linear speedups on the pipelined hypercube, and provably optimal speedups on the shuffle-exchange and the cube-connected-cycles for any number p of processors satisfying 1>

A hypercube algorithm to solve the list ranking problem is presented. Let n be the length of the list, and let p be the number of processors of the hypercube. The algorithm described runs in time O(n/p) when n= Omega (p/sup 1+ epsilon /) for any constant epsilon >0, and in time O(n log n/p+log/sup 3/ p) otherwise. This clearly attains a linear speedup when n= Omega (p/sup 1+ epsilon /). Efficient balancing and routing schemes had to be used to achieve the linear speedup. The authors use these techniques to obtain efficient hypercube algorithms for many basic graph problems such as tree expression evaluation, connected and biconnected components, ear decomposition, and st-numbering. These problems are also addressed in the restricted model of one-port communication.>