DonNTU   Masters' portal

Abstract

This work propose a new efficient method to simulate various types of solid including rigid, plastic and soft bodies which represented by voxel models.

Content

Introduction

Computers have become an indispensable tool in modeling and simulation. As computational power increases, users and applications are demanding ever increasing levels of realism in these domains. This trend is particulary apparent in computer graphics where more sophisticated geometric shapes and physical objects are being modeled in the context of complex physical enviroments. In particular, the ability to model and manipulate deformable objects is essential to many applications. Approaches for modeling object deformation range from non-physical methods where individual or groups of control points or shape parametes are manually adjusted for shape editing and design – to methods based on continuum mechanics – which account for the effects of material properties, external forces, and environmetal contraints on object deformation[4].

There are plenty of ways to represent three dimensional (3D) models, such as triangle meshes, voxels, CSG (constructive solid geometry), etc. Triangle meshes are the most common format among the others due to their use in computer and video games and hardware support through GPUs. Voxels have many advantages over triangle meshes. Such advantages are memory efficiency, implicit level of detail and resolution boundedness (rather than geometry boundedness). They are not being used in mainstream real-time graphics applications, mainly due to the fact that they are static. It turns out to be quite impossible to animate them.

Voxels are cuboids. The idea is to approximate 3D models with many (several million) little cuboids, as can be seen in figure 1. If the resolution of a voxel model is considerably high (and one does not zoom in too much), its voxels become smaller than the pixels of the display and are not distinguishable anymore. The model is perceived smooth rather than blockish. Image enhancing techniques like anti-aliasing, supersampling and interpolation finally completely hide the underlying cuboid structure of a voxel model – the same way they hide the mesh structure of triangle based models [1].

Figure 1 — Polygonal model and voxel models with low and high quality

Research in the field of physically based animation in computer graphics is concerned with finding new methods for the simulation of physical phenomena such as the dynamics of rigid bodies, deformable objects or fluid flow. The traditional approach to simulating dynamic objects has been to work with forces. At the beginning of each time step, internal and external forces are accumulated. Examples of internal forces are elastic forces in deformable objects or viscosity and pressure forces in fluids. Gravity and collision forces are examples of external forces. Newton’s second law of motion relates forces to accelerations via the mass. So using the density or lumped masses of vertices, the forces are transformed into accelerations. Any time integration scheme can then be used to first compute the velocities from the accelerations and then the positions from the velocities. Some approaches use impulses instead of forces to control the animation. Because impulses directly change velocities, one level of integration can be skipped [6].

Simulation methods need to meet four major requirements to be applicable in computer games. They must be fast, stable, controllable and easy to code in order for game developers to pick them up and use them in their projects [7]. In computer games, where robustness and speed are often more essential than accuracy, simpler unconditionally stable geometric methods such as position based dynamics (PBD) [6] can be sufficient to create the desired physical effects.

1. Theme urgency

Virtual environments in which the user can interact with a virtual world have become very popular in recent years. Three dimensional computer games are an important example. They represent the largest market in this field. Besides computer games, there is a large number of other examples for interactive virtual environments such as medical-, car- and flight simulators [3].

To give the user the impression of a physical world, it is important that objects behave like they do in the real world. Virtual scenes such as those encountered in computer games are composed of a large number of objects most of which are typically represented by surface meshes only. To give the impression of solid physical objects – especially when these objects are deformed or shattered into pieces – voxels or volumetric representations can be used.

Voxel models have become a common shape representation for several reasons. Three-dimensional scanning devices are widely used nowadays and points are an attractive primitive for rendering complex geometry. Nevertheless, there is not much literature on animation of voxel (point clouds) models.

This work is aimed at the development of effective algorithms for voxel models animation. It propose an integrated solution for animation, interaction with dynamic objects and visualization of voxels scene. The main idea is to extend the Position Based Dynamics approach recently introduced in [6] and [7], and apply it to the dynamic sparse octrees structure in which voxel models are stored.

2. Goal and tasks of the research

Development of an approach to simulate various dynamics of solid including rigid, plastic and soft bodies which stored in voxel octtrees structure is the goal of research.

Main tasks of the research:

  1. Analysis existing methods of 3D polygonal models animation.
  2. Analysis existing methods of voxel models animation and interactive simulation.
  3. Design of a novel approach of voxel models animation and dynamic interaction.
  4. Develop programming functionality and software that implements the proposed approach.

Research object: animation of voxel models

Research subject: development of methods and algorithms for animation and interactive simulation of objects represented by voxel models.

3. Description of the proposed approach of voxel model animation and dynamic interaction

Volume graphics is one of the latest developments in computer graphics, yet it is evident that it has the potential to become one of the most useful techniques in three dimensional object manipulation and representation. Voxel-based models are used in a variety of applications, including (but not limited to) medical imaging, fluid dynamics, terrain modeling, texture generation, and lately even in computer games [9].

Probably, the simplest storage format for voxel models is a uniform grid. It can be realized as a 3D array wherein every single cell describes one voxel (its appearance). This data structure is very memory inefficient. A more efficient solution and the most commonly used one is the sparse voxel octree (SVO). It is a tree data structure in which every node can have up to eight children. It is sparse in the sense that it does not include the subtrees corresponding to empty space. The major idea is to start with one large cuboid and evenly split it up into eight smaller cuboids and repeat this process for every child recursively until the leaves sufficiently approximate the shape of an object. Figure 2 illustrates this concept.

Figure 2 — Octree structure format

SVOs are very memory efficient (state of the art voxel rendering engines can compress the memory footprint of one voxel down to one bit) and their hierarchical nature benefits many operations used in computer graphics. Voxels are suited for representing models with great mesostructural detail, such as rocks, mountains, terrain, plants, vegetation, nature. Especially if those models have surface characteristics like hangovers which cannot be faked by techniques like parallax mapping [1].

Voxels are inappropriate for representing flat surfaces, which can be found in architecture and furniture for example. Such surfaces can be modeled with very few triangles, whereas voxel models must always have maximal resolution to appear smooth – no matter the kind of shape they represent [1].

This is the main reason why one should not stick to one technology exclusively but mix both, tapping their full potential.

In computer graphics and especially in computer games it is often desirable to have direct control over positions of objects or in this case over positions of octree nodes. The user might want to attach a node to a kinematic object or make sure the it always stays outside a colliding object. The position based dynamic (PBD) approach works directly on positions which makes such manipulations easy.

In the original PBD form the objects to be simulated are represented by a set of N particles and a set of M constraints. Each particle i has three attributes, namely

Table 1 — Attributes of the particle

A constraint j is defined by the five attributes shown in Table 2. With type bi lateral is satisfied if Cj(xi1,...,xinj)=0. If its type is unilateral then it is satisfied if Cj(xi1,...,xinj ) ≥ 0. The stiffness parameter kj defines the strength of the constraint in a range from zero to one.

Table 2 — Attributes of the constraint

So the main features and advantages of position based dynamics are:

  1. Position based simulation gives control over explicit integration and removes the typical instability problems.
  2. Positions of vertices and parts of objects can directly be manipulated during the simulation.
  3. Position based simulation allows the handling of general constraints in the position based setting.
  4. The explicit position based solver is easy to understand and implement.

Simulation results of objects interaction are shown on figure 3 (control points and constraints are depicted on left image, result – on right image). In this example the ball is a solid object and the mesh (control nodes are shown as red points) is deformable system. All calculation during simulation are performed using experimental implementation of position based approach.

Simulation results of objects interaction (Control nodes and constraints) simulation results of objects interaction

Figure 3 – Simulation results of objects interaction
(animation: 18 frames, 10 cycles of repeating, 140 KB)

The main idea of animating sparse voxel octrees:

  1. Treat every node of a SVO like an separate particle, that can be transformed independently from all other nodes inside the octree.
  2. Every child node of a SVO either have their properties and constraints or inherit them from parent node.
  3. Apply the transformation to each node during the rendering phase.
  4. Correct positions and velocities with position based approach.

Conclusion

This paper presents a new approach for animation of voxel models. There are many methods and algorithms to animate 3D polygonal models, but there is very little in the literature about animation 3D voxel models.

Master's work is devoted to development new efficient approach of voxel models animation.

Based on analysis of the literature the main algorithms and data stuctures have been determined.

Further studies focused on the following aspects:

  1. Extend and adapt highlighted methods and approaches to work efficient with voxel models representation.
  2. Qualitative improvement of the proposed approach.
  3. Programmatic implementation of the proposed approach.
  4. Simulation dynamics of rigid bodies, deformable objects or fluid flow.
  5. Analisis experimental results and effectiveness of developed approach.
  6. Develop cross-platform functionality and computer-aided design of software that implements the proposed approach.

This master's work is not completed yet. Final completion: December 2012. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Bautembach D., Animated Sparse Voxel Octrees // Bachelor’s Thesis – University of Hamburg, Department of Informatics, 2011, http://www.bautembach.de ...
  2. Crassin C., GigaVoxels: A Voxel-Based Rendering Pipeline For Efficient Exploration Of Large And Detailed Scenes // PhD thesis – Universite de Grenoble, 2011 http://www.maverick.inria.fr ...
  3. Muller M., Teschner M., Gross M., Physically-Based Simulation of Objects Represented by Surface Meshes // Proceedings of Computer Graphics International (CGI), Crete, Greece, Jun 16-19 2004, pp 26-33, http://www.matthiasmueller.info ...
  4. Gibson S., Mirtich B., A Survey of Deformable Modeling in Computer Graphics // Mitsubishi electric research laboratories, Technical Report TR-97-19, MERL, 1997 http://www.merl.com ...
  5. Nealen A., Muller M., Keiser R., Boxerman E., Carlson M., Physically Based Deformable Models in Computer Graphics // Computer Graphics Forum, 2006, Volume 25, pp 809–836, http://citeseerx.ist.psu.edu ...
  6. Muller M., Heidelberger B., Hennix M., Ratcliff J., Position Based Dynamics // Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys), – Madrid, 2006, – pp 71-80, http://www.matthiasmueller.info ...
  7. Muller M., Hierarchical Position Based Dynamics // Proceedings of Virtual Reality Interactions and Physical Simulations (VRIPhys2008), Grenoble, 2008 http://www.matthiasmueller.info ...
  8. Muller M., Chentanez N., Solid Simulation with Oriented Particles // ACM Transactions on Graphics (SIGGRAPH 2011), 2011, pp 92:1-92:10, http://www.matthiasmueller.info ...
  9. Karabassi A., Papaioannou G., Theoharis T., A Depth Buffer Based Voxelization Algorithm // Department of Informatics, University of Athens, 2000 http://www.cgi.di.uoa.gr ...
  10. Figueiredo M., Oliveira J., Araujo B., Pereira J., An efficient collision detection algorithm for point cloud models // International conference on computer graphics and vision GraphiCon, 2010, http://www.graphicon.ru ...
  11. Limtrakul S., Hantanong W., Kanongchaiyos P., Nishita T., Reviews on physically based controllable fluid animation // Engineering Journal, Vol 14, 2010, http://www.engj.org ...
  12. Belyaev S., Laevsky I., Chukanov V., Real-time Animation, Collision and Rendering of Grassland // International conference on computer graphics and vision GraphiCon, 2011, http://www.graphicon.ru ...
  13. Катасонов А.В., Вяткин С.И., Долговесов Б.С., Вокселизация функциональных форм // International conference on computer graphics and vision GraphiCon, 2005, http://www.graphicon.ru ...
  14. Семакин М.М., Метод синтеза движений в задачах трехмерной компьютерной анимации // International conference on computer graphics and vision GraphiCon, 2002, http://www.graphicon2002 ...