Fluid droplets behave significantly different from larger fluid bodies. At smaller scales, surface tension and friction between fluids and the boundary play an essential role and are even able to counteract gravitational forces. There are quite a few existing approaches that model surface tension forces within an SPH environment. However, as often as not, physical correctness and simulation stability are still major concerns with many surface tension formulations. We propose a new approach to compute surface tension that is both robust and produces the right amount of surface tension. Conversely, less attention was given to friction forces at the fluid-boundary interface. Recent experimental research indicates that Coulomb friction can be used to describe the behavior of droplets resting on a slope. Motivated by this, we develop a novel friction force formulation at the fluid-boundary interface following the Coulomb model, which allows us to replicate a new range of well known fluid behavior such as the motion of rain droplets on a window pane. Both forces are combined with an IISPH variant into one unified solver that is able to simultaneously compute strongly coupled surface tension, friction and pressure forces.

Abstract We propose a novel monolithic pure SPH formulation to simulate fluids strongly coupled with rigid bodies. This includes fluid incompressibility, fluid–rigid interface handling and rigid–rigid contact handling with a viable implicit particle‐based dry friction formulation. The resulting global system is solved using a new accelerated solver implementation that outperforms existing fluid and coupled rigid–fluid simulation approaches. We compare results of our simulation method to analytical solutions, show performance evaluations of our solver and present a variety of new and challenging simulation scenarios.

Abstract Throughout the past decades, the graphics community has spent major resources on the research and development of physics simulators on the mission to computer‐generate behaviors achieving outstanding visual effects or to make the virtual world indistinguishable from reality. The variety and impact of recent research based on Smoothed Particle Hydrodynamics (SPH) demonstrates the concept's importance as one of the most versatile tools for the simulation of fluids and solids. With this survey, we offer an overview of the developments and still‐active research on physics simulation methodologies based on SPH that has not been addressed in previous SPH surveys. Following an introduction about typical SPH discretization techniques, we provide an overview over the most used incompressibility solvers and present novel insights regarding their relation and conditional equivalence. The survey further covers recent advances in implicit and particle‐based boundary handling and sampling techniques. While SPH is best known in the context of fluid simulation we discuss modern concepts to augment the range of simulatable physical characteristics including turbulence, highly viscous matter, deformable solids, as well as rigid body contact handling. Besides the purely numerical approaches, simulation techniques aided by machine learning are on the rise. Thus, the survey discusses recent data‐driven approaches and the impact of differentiable solvers on artist control. Finally, we provide context for discussion by outlining existing problems and opportunities to open up new research directions.

Abstract We propose a novel compression scheme to store neighbour lists for iterative solvers that employ Smoothed Particle Hydrodynamics (SPH). The compression scheme is inspired by Stream VByte, but uses a non‐linear mapping from data to data bytes, yielding memory savings of up to 87%. It is part of a novel variant of the Cell‐Linked‐List (CLL) concept that is inspired by compact hashing with an improved processing of the cell‐particle relations. We show that the resulting neighbour search outperforms compact hashing in terms of speed and memory consumption. Divergence‐Free SPH (DFSPH) scenarios with up to 1.3 billion SPH particles can be processed on a 24‐core PC using 172 GB of memory. Scenes with more than 7 billion SPH particles can be processed in a Message Passing Interface (MPI) environment with 112 cores and 880 GB of RAM. The neighbour search is also useful for interactive applications. A DFSPH simulation step for up to 0.2 million particles can be computed in less than 40 ms on a 12‐core PC.

Snow is a complex material. It resists elastic normal and shear deformations, while some deformations are plastic. Snow can deform and break. It can be significantly compressed and gets harder under compression. Existing snow solvers produce impressive results. E.g., hybrid Lagrangian/Eulerian techniques have been used to capture all material properties of snow. The auxiliary grid, however, makes it challenging to handle small volumes. In particular, snow fall and accumulation on surfaces have not been demonstrated with these solvers yet. Existing particle-based snow solvers, on the other hand, can naturally handle small snow volumes. However, existing solutions consider simplified material properties. In particular, shear deformation and the hardening effect are typically omitted. We present a novel Lagrangian snow approach based on Smoothed Particle Hydrodynamics (SPH). Snow is modeled as an elastoplastic continuous material that captures all above-mentioned effects. The compression of snow is handled by a novel compressible pressure solver, where the typically employed state equation is replaced by an implicit formulation. Acceleration due to shear stress is computed using a second implicit formulation. The linear solvers of the two implicit formulations for accelerations due to shear and normal stress are realized with matrix-free implementations. Using implicit formulations and solving them with matrix-free solvers allows to couple the snow to other phases and is beneficial to the stability and the time step size, i.e., performance of the approach. Solid boundaries are represented with particles and a novel implicit formulation is used to handle friction at solid boundaries. We show that our approach can simulate accumulation, deformation, breaking, compression and hardening of snow. Furthermore, we demonstrate two-way coupling with rigid bodies, interaction with incompressible and highly viscous fluids and phase change from fluid to snow.

We present a strong fluid-rigid coupling for Smoothed Particle Hydrodynamics (SPH) fluids and rigid bodies with particle-sampled surfaces. The approach interlinks the iterative pressure update at fluid particles with a second SPH solver that computes artificial pressure at rigid-body particles. The introduced SPH rigid-body solver models rigid-rigid contacts as artificial density deviations at rigid-body particles. The corresponding pressure is iteratively computed by solving a global formulation that is particularly useful for large numbers of rigid-rigid contacts. Compared to previous SPH coupling methods, the proposed concept stabilizes the fluid-rigid interface handling. It significantly reduces the computation times of SPH fluid simulations by enabling larger time steps. Performance gain factors of up to 58 compared to previous methods are presented. We illustrate the flexibility of the presented fluid-rigid coupling by integrating it into DFSPH, IISPH, and a recent SPH solver for highly viscous fluids. We further show its applicability to a recent SPH solver for elastic objects. Large scenarios with up to 90 M particles of various interacting materials and complex contact geometries with up to 90 k rigid-rigid contacts are shown. We demonstrate the competitiveness of our proposed rigid-body solver by comparing it to Bullet.

Abstract We propose a novel smoothed particle hydrodynamics (SPH) formulation for deformable solids. Key aspects of our method are implicit elastic forces and an adapted SPH formulation for the deformation gradient that—in contrast to previous work—allows a rotation extraction directly from the SPH deformation gradient. The proposed implicit concept is entirely based on linear formulations. As a linear strain tensor is used, a rotation‐aware computation of the deformation gradient is required. In contrast to existing work, the respective rotation estimation is entirely realized within the SPH concept using a novel formulation with incorporated kernel gradient correction for first‐order consistency. The proposed implicit formulation and the adapted rotation estimation allow for significantly larger time steps and higher stiffness compared to explicit forms. Performance gain factors of up to one hundred are presented. Incompressibility of deformable solids is accounted for with an ISPH pressure solver. This further allows for a pressure‐based boundary handling and a unified processing of deformables interacting with SPH fluids and rigids. Self‐collisions are implicitly handled by the pressure solver.

Implicit incompressible SPH (IISPH) solves a pressure Poisson equation (PPE). While the solution of the PPE provides pressure at fluid samples, the embedded boundary handling does not compute pressure at boundary samples. Instead, IISPH uses various approximations to remedy this deficiency. In this article, we illustrate the issues of these IISPH approximations. We particularly derive Pressure Boundaries, a novel boundary handling that overcomes previous IISPH issues by the computation of physically meaningful pressure values at boundary samples. This is basically achieved with an extended PPE. We provide a detailed description of the approach that focuses on additional technical challenges due to the incorporation of boundary samples into the PPE. We therefore use volume-centric SPH discretizations instead of typically used density-centric ones. We further analyze the properties of the proposed boundary handling and compare it to the previous IISPH boundary handling. In addition to the fact that the proposed boundary handling provides physically meaningful pressure and pressure gradients at boundary samples, we show further benefits, such as reduced pressure oscillations, improved solver convergence, and larger possible time steps. The memory footprint of fluid samples is reduced and performance gain factors of up to five compared to IISPH are presented.

Working with prescribed velocity gradients is a promising approach to efficiently and robustly simulate highly viscous SPH fluids. Such approaches allow to explicitly and independently process shear rate, spin, and expansion rate. This can be used to, e.g., avoid interferences between pressure and viscosity solvers. Another interesting aspect is the possibility to explicitly process the vorticity, e.g., to preserve the vorticity. In this context, this paper proposes a novel variant of the prescribed-gradient idea that handles vorticity in a physically motivated way. In contrast to a less appropriate vorticity preservation that has been used in a previous approach, vorticity is diffused. The paper illustrates the utility of the vorticity diffusion. Therefore, comparisons of the proposed vorticity diffusion with vorticity preservation and additionally with vorticity damping are presented. The paper further discusses the relation between prescribed velocity gradients and prescribed velocity Laplacians which improves the intuition behind the prescribed-gradient method for highly viscous SPH fluids. Finally, the paper discusses the relation of the proposed method to a physically correct implicit viscosity formulation.

We present a novel implicit formulation for highly viscous fluids simulated with Smoothed Particle Hydrodynamics SPH. Compared to explicit methods, our formulation is significantly more efficient and handles a larger range of viscosities. Differing from existing implicit formulations, our approach reconstructs the velocity field from a target velocity gradient. This gradient encodes a desired shear-rate damping and preserves the velocity divergence that is introduced by the SPH pressure solver to counteract density deviations. The target gradient ensures that pressure and viscosity computation do not interfere. Therefore, only one pressure projection step is required, which is in contrast to state-of-the-art implicit Eulerian formulations. While our model differs from true viscosity in that vorticity diffusion is not encoded in the target gradient, it nevertheless captures many of the qualitative behaviors of viscous liquids. Our formulation can easily be incorporated into complex scenarios with one- and two-way coupled solids and multiple fluid phases with different densities and viscosities.

Abstract The dynamic simulation of mechanical effects has a long history in computer graphics. The classical methods in this field discretize Newton's second law in a variety of Lagrangian or Eulerian ways, and formulate forces appropriate for each mechanical effect: joints for rigid bodies; stretching, shearing or bending for deformable bodies and pressure, or viscosity for fluids, to mention just a few. In the last years, the class of position‐based methods has become popular in the graphics community. These kinds of methods are fast, stable and controllable which make them well‐suited for use in interactive environments. Position‐based methods are not as accurate as force‐based methods in general but they provide visual plausibility. Therefore, the main application areas of these approaches are virtual reality, computer games and special effects in movies. This state‐of‐the‐art report covers the large variety of position‐based methods that were developed in the field of physically based simulation. We will introduce the concept of position‐based dynamics, present dynamic simulation based on shape matching and discuss data‐driven upsampling approaches. Furthermore, we will present several applications for these methods.

Abstract We propose to use Implicit Incompressible Smoothed Particle Hydrodynamics (IISPH) for pressure projection and boundary handling in Fluid‐Implicit‐Particle (FLIP) solvers for the simulation of incompressible fluids. This novel combination addresses two issues of existing SPH and FLIP solvers, namely mass preservation in FLIP and efficiency and memory consumption in SPH. First, the SPH component enables the simulation of incompressible fluids with perfect mass preservation. Second, the FLIP component efficiently enriches the SPH component with detail that is comparable to a standard SPH simulation with the same number of particles, while improving the performance by a factor of 7 and significantly reducing the memory consumption. We demonstrate that the proposed IISPH‐FLIP solver can simulate incompressible fluids with a quantifiable, imperceptible density deviation below 0.1%. We show large‐scale scenarios with up to 160 million particles that have been processed on a single desktop PC using only 15GB of memory. One‐ and two‐way coupled solids are illustrated.

We propose a novel formulation of the projection method for Smoothed Particle Hydrodynamics (SPH). We combine a symmetric SPH pressure force and an SPH discretization of the continuity equation to obtain a discretized form of the pressure Poisson equation (PPE). In contrast to previous projection schemes, our system does consider the actual computation of the pressure force. This incorporation improves the convergence rate of the solver. Furthermore, we propose to compute the density deviation based on velocities instead of positions as this formulation improves the robustness of the time-integration scheme. We show that our novel formulation outperforms previous projection schemes and state-of-the-art SPH methods. Large time steps and small density deviations of down to 0.01 percent can be handled in typical scenarios. The practical relevance of the approach is illustrated by scenarios with up to 40 million SPH particles.

ABSTRACT We propose a method for handling elastic solids in smoothed particle hydrodynamics fluids. Our approach samples triangulated surfaces of solids using boundary particles. To prevent fluid particle tunneling in case of large expansions, additional boundary particles are adaptively generated to prevent gaps and undesired leakage. Furthermore, as an object compresses, particles are adaptively removed to avoid unnecessary computations. We demonstrate that our approach produces plausible interactions of smoothed particle hydrodynamics fluids with both slowly and rapidly deforming solids. Copyright © 2013 John Wiley & Sons, Ltd.

Realistic handling of fluid-air and fluid-solid interfaces in SPH is a challenging problem. The main reason is that some important physical phenomena such as surface tension and adhesion emerge as a result of inter-molecular forces in a microscopic scale. This is different from scalar fields such as fluid pressure, which can be plausibly evaluated on a macroscopic scale using particles. Although there exist techniques to address this problem for some specific simulation scenarios, there does not yet exist a general approach to reproduce the variety of effects that emerge in reality from fluid-air and fluid-solid interactions. In order to address this problem, we present a new surface tension force and a new adhesion force. Different from the existing work, our surface tension force can handle large surface tensions in a realistic way. This property lets our approach handle challenging real scenarios, such as water crown formation, various types of fluid-solid interactions, and even droplet simulations. Furthermore, it prevents particle clustering at the free surface where inter-particle pressure forces are incorrect. Our adhesion force allows plausible two-way attraction of fluids and solids and can be used to model different wetting conditions. By using our forces, modeling surface tension and adhesion effects do not require involved techniques such as generating a ghost air phase or surface tracking. The forces are applied to the neighboring fluid-fluid and fluid-boundary particle pairs in a symmetric way, which satisfies momentum conservation. We demonstrate that combining both forces allows simulating a variety of interesting effects in a plausible way.

Abstract This paper presents a novel method that improves the efficiency of high‐quality surface reconstructions for particle‐based fluids using Marching Cubes. By constructing the scalar field only in a narrow band around the surface, the computational complexity and the memory consumption scale with the fluid surface instead of the volume. Furthermore, a parallel implementation of the method is proposed. The presented method works with various scalar field construction approaches. Experiments show that our method reconstructs high‐quality surface meshes efficiently even on single‐core CPUs. It scales nearly linearly on multi‐core CPUs and runs up to fifty times faster on GPUs compared to the original scalar field construction approaches.

We propose a momentum-conserving two-way coupling method of SPH fluids and arbitrary rigid objects based on hydrodynamic forces. Our approach samples the surface of rigid bodies with boundary particles that interact with the fluid, preventing deficiency issues and both spatial and temporal discontinuities. The problem of inhomogeneous boundary sampling is addressed by considering the relative contribution of a boundary particle to a physical quantity. This facilitates not only the initialization process but also allows the simulation of multiple dynamic objects. Thin structures consisting of only one layer or one line of boundary particles, and also non-manifold geometries can be handled without any additional treatment. We have integrated our approach into WCSPH and PCISPH, and demonstrate its stability and flexibility with several scenarios including multiphase flow.

Abstract This paper presents a parallel framework for simulating fluids with the Smoothed Particle Hydrodynamics (SPH) method. For low computational costs per simulation step, efficient parallel neighbourhood queries are proposed and compared. To further minimize the computing time for entire simulation sequences, strategies for maximizing the time step and the respective consequences for parallel implementations are investigated. The presented experiments illustrate that the parallel framework can efficiently compute large numbers of time steps for large scenarios. In the context of neighbourhood queries, the paper presents optimizations for two efficient instances of uniform grids, that is, spatial hashing and index sort. For implementations on parallel architectures with shared memory, the paper discusses techniques with improved cache‐hit rate and reduced memory transfer. The performance of the parallel implementations of both optimized data structures is compared. The proposed solutions focus on systems with multiple CPUs. Benefits and challenges of potential GPU implementations are only briefly discussed.

In this paper, we consider the problem of determining the elasticity properties of deformable objects with a mobile manipulator equipped with a force sensorb. We learn the parameters by establishing a relation between the applied forces and the corresponding surface deformations. To determine the parameters, we minimize the difference between the observed surface of an object that is deformed by a real manipulator and the deformed surface obtained with a deformation simulator based on finite element methods. To establish the correspondences between the surfaces, our approach applies a 3D registration technique based on point-clouds which is used as the basis for comparing the results of the simulation system with the observations of the real deformations. As we demonstrate in real-world experiments, our system is able to estimate appropriate parameters that can be used to predict future deformations. This information can directly be incorporated into motion planning approaches that are designed for robots operating with deformable objects.

In this paper, we consider the problem of mobile robots navigating in environments with non-rigid objects. Whereas robots can plan their paths more effectively when they utilize the information about the deformability of objects, they also need to consider the influence of the interaction with the deformable objects on their measurements during the execution of their navigation task. In this paper, we present a probabilistic approach to identify the measurements influenced by the deformable objects. Based on a learned statistics about the influence of the deformable objects on the measurements, the robot is able to perform a sensor-based collision avoidance of unforeseen objects. We present experiments carried out with a real robot that illustrate the practicability of our approach.

Abstract Collision handling is a comparatively time‐consuming task in dynamic simulations and the computational efficiency of collision handling techniques can vary significantly dependent on the spatial configuration of the environment. These issues have to be addressed in interactive simulations such as games or surgical simulators, where a pre‐defined response time should be guaranteed for each simulation step. We present a time‐critical collision handling approach for deformable objects. The technique employs spatial subdivision for the detection of collisions and penetration depth information is computed to estimate penalty forces. Detection, penetration depth estimation, and response are divided into atomic tasks. In case of an interruption, the algorithm basically resumes in the next time step. If collisions are not completely handled in one simulation step, the algorithm ensures that persistent collisions are handled in a subsequent simulation step. If an exact response cannot be computed in a given time frame, the algorithm efficiently approximates penalty forces for colliding points. Experiments indicate that the proposed technique provides a physically plausible collision handling in the case of incomplete or inconsistent collision information. User‐defined limits for the computation time can be guaranteed with an efficiency gain of up to factor three. Copyright © 2009 John Wiley & Sons, Ltd.

We propose a novel boundary handling algorithm for particle-based fluids. Based on a predictor-corrector scheme for both velocity and position, one- and two-way coupling with rigid bodies can be realized. The proposed algorithm offers significant improvements over existing penalty-based approaches. Different slip conditions can be realized and non-penetration is enforced. Direct forcing is employed to meet the desired boundary conditions and to ensure valid states after each simulation step. We have performed various experiments in 2D and 3D. They illustrate one- and two-way coupling of rigid bodies and fluids, the effects of hydrostatic and dynamic forces on a rigid body as well as different slip conditions. Numerical experiments and performance measurements are provided.

Cosserat nets are networks of elastic rods that are linked by elastic joints. They allow to represent a large variety of objects such as elastic rings, coarse nets, or truss structures. In this paper, we propose a novel approach to model and dynamically simulate such Cosserat nets. We first derive the static equilibrium of the elastic rod model that supports both bending and twisting deformation modes. We further propose a dynamic model that allows for the efficient simulation of elastic rods. We then focus on the simulation of the Cosserat nets by extending the elastic rod deformation model to branched and looped topologies. To round out the discussion, we evaluate our deformation model. By comparing our deformation model to a reference model, we illustrate both the physical plausibility and the conceptual advantages of the proposed approach.

The ability to reliably navigate through the environment is an important prerequisite for truly autonomous robots. In this paper, we consider the problem of path planning in environments with non-rigid obstacles such as curtains or plants. We present an approach that combines probabilistic roadmaps with a physical simulation of object deformations to determine a path that optimizes the trade-off between the deformation cost and the distance to be traveled. We describe how our approach utilizes Finite Element theory for calculating the deformation cost. Since the high computational requirements of the corresponding simulation prevent this method from being applicable online, we present an approximation that uses a preprocessing step to determine a deformation cost function for each object. This cost function allows us to estimate the deformation costs of arbitrary paths through the objects and is used to evaluate the trajectories generated by the roadmap planner online. We present experiments which demonstrate that the resulting algorithm plans nearly identical trajectories compared to the method that relies on computationally intense simulations. At the same time, our approach allows the robot to quickly calculate paths in environments with deformable objects.

Abstract In this paper, we present an adaptive model for dynamically deforming hyper‐elastic rods. In contrast to existing approaches, adaptively introduced control points are not governed by geometric subdivision rules. Instead, their states are determined by employing a non‐linear energy‐minimization approach. Since valid control points are computed instantaneously, post‐stabilization schemes are avoided and the stability of the dynamic simulation is improved. Due to inherently complex contact configurations, the simulation of knot tying using rods is a challenging task. In order to address this problem, we combine our adaptive model with a robust and accurate collision handling method for elastic rods. By employing our scheme, complex knot configurations can be simulated in a physically plausible way.

Collision detection is an enabling technology for many virtual environments, games, and virtual prototyping applications containing some kind of physically-based simulation (such as rigid bodies, cloth, surgery, etc.). The persistent interest in collision detection by both academia and industry is due to the large variety of applications as well as new challenges in new application domains, such as virtual clothes fitting. This tutorial will give an overview of the different classes of algorithms, and then provide attendees with in-depth knowledge of some of the important algorithms within each class, focusing in particular on recent approaches, such as stochastic methods or image-space techniques. Attendees will learn to select the one most appropriate for their application, and implement it with only very little further research. The intended audience are practitioners and students working in 3D computer graphics. Topics to be addressed - hierarchical collision detection - stochastic methods - distance fields - spatial subdivisions - image-space techniques - continuous collision detection - non-polygonal object representations (e.g., point clouds)

Abstract Interactive environments for dynamically deforming objects play an important role in surgery simulation and entertainment technology. These environments require fast deformable models and very efficient collision handling techniques. While collision detection for rigid bodies is well investigated, collision detection for deformable objects introduces additional challenging problems. This paper focuses on these aspects and summarizes recent research in the area of deformable collision detection. Various approaches based on bounding volume hierarchies, distance fields and spatial partitioning are discussed. In addition, image‐space techniques and stochastic methods are considered. Applications in cloth modeling and surgical simulation are presented.

We present a new approach for simulating deformable objects. The underlying model is geometrically motivated. It handles pointbased objects and does not need connectivity information. The approach does not require any pre-processing, is simple to compute, and provides unconditionally stable dynamic simulations.The main idea of our deformable model is to replace energies by geometric constraints and forces by distances of current positions to goal positions. These goal positions are determined via a generalized shape matching of an undeformed rest state with the current deformed state of the point cloud. Since points are always drawn towards well-defined locations, the overshooting problem of explicit integration schemes is eliminated. The versatility of the approach in terms of object representations that can be handled, the efficiency in terms of memory and computational complexity, and the unconditional stability of the dynamic simulation make the approach particularly interesting for games.

Objects and scenes in virtual worlds such as 3D computer games are typically represented by polygonal surface meshes. On the other hand, physically-based simulations of deformations or fracture effects require volumetric representations such as tetrahedral meshes. In this paper we propose techniques to generate volumetric meshes dynamically for objects represented by surface meshes allowing the simulation of physical effects such as motion, deformation and fracture. We use the finite element method based on cubical elements of uniform size. Regular cube meshes have several advantages over geometrically more complex representations. Because of their simplicity, cube meshes can be generated quickly by voxelizing objects while neither geometry nor stiffness information needs to be stored explicitly. The low memory consumption makes physically-based animation possible for large scenes even on game consoles. We animate the original high resolution surface mesh by coupling it to the underlying volumetric mesh. This way, the regular structure of the volumetric mesh is hidden from the user. We also propose a technique to fracture the surface mesh along with the cube mesh which keeps the surface watertight and results in realistic fracture patterns

We present a versatile and robust model for geometrically complex deformable solids. Our approach can be applied to deformable tetrahedral meshes and to deformable triangle meshes. The model considers elastic and plastic deformation. It handles a large variety of material properties ranging from stiff to fluid-like behavior. Due to the computational efficiency of our approach, complex environments consisting of up to several thousand primitives can be simulated at interactive speed. The presented approach to deformable modeling is part of a simulation environment with integrated collision handling for tetrahedral meshes. For visualization purposes, tetrahedral meshes can be coupled with high-resolution surface meshes. Results are presented for deformable tetrahedral meshes and for deformable triangle meshes which are used to represent cloth and discrete shells.

This paper presents an algorithm for rendering of point-sampled CSG models. The approach works with arbitrary CSG trees of surfel models with arbitrary sampling densities. Edges and corners are rendered by reconstructing the involved surfaces separately. The reconstructed surfaces are clipped at intersections. This way, blurring at any magnification is avoided. As opposed to existing methods, which resample surfaces close to object intersections, the proposed approach preserves the original object representation. Since no resampling is needed, dynamic scenes can be handled very flexible. Complex intersections involving any number of objects can be rendered.

Abstract In this paper, we present a method for simulating the interaction of fluids with deformable solids. The method is designed for the use in interactive systems such as virtual surgery simulators where the real‐time interplay of liquids and surrounding tissue is important. In computer graphics, a variety of techniques have been proposed to model liquids and deformable objects at interactive rates. As important as the plausible animation of these substances is the fast and stable modeling of their interaction. The method we describe in this paper models the exchange of momentum between Lagrangian particle‐based fluid models and solids represented by polygonal meshes. To model the solid‐fluid interaction we use virtual boundary particles. They are placed on the surface of the solid objects according to Gaussian quadrature rules allowing the computation of smooth interaction potentials that yield stable simulations. We demonstrate our approach in an interactive simulation environment for fluids and deformable solids. Copyright © 2004 John Wiley & Sons, Ltd.

We introduce an algorithm that consistently and accurately processes arbitrary intersections in tetrahedral meshes in real-time. The intersection surfaces are modeled up to the current cut tool position at every point in time. Tetrahedra are subdivided by using a progressive method, which inserts the required sub-structures step by step. A state machine tracks the topology of each tetrahedron and controls the progressive subdivision. In order to keep the state machine as small and clear as possible, each topological pattern of a tetrahedral intersection appears only once. These topological patterns are mapped onto the actual case of a tetrahedral intersection by some given transformation operations. The state transitions, which contain the specific subdivision operations, are described in a predefined lookup table, which is written in a simple script language. The handling of reverse movements and possible trembling of the users hand, as well as a recursive continuation of the state machine concept, complement the proposed algorithm. In three examples, covering free form modeling, volume visualization, and surgery simulation, we indicate the large field of applications in which our algorithm can be utilized.