Scientific Articles, Reports & Theses
List of Publications
Select tag “Algoryx” for publications affiliated with Algoryx, or “External” for external publications that use or cite Algoryx software.
2011 |
|
![]() | Bodin, Kenneth; Lacoursière, Claude; Servin, Martin: Constraint fluids. IEEE Transactions on Visualization and Computer Graphics, 18 (3), pp. 516–526, 2011. (Type: Journal Article | Abstract | Links | BibTeX | Tags: Algoryx) @article{bodin2011constraintb, title = {Constraint fluids}, author = {Kenneth Bodin and Claude Lacoursière and Martin Servin}, url = {https://www.diva-portal.org/smash/get/diva2:316247/FULLTEXT02 https://www.youtube.com/watch?v=kzFam0UKFoA&ab_channel=Algoryx}, doi = {10.1109/TVCG.2011.29}, year = {2011}, date = {2011-01-01}, journal = {IEEE Transactions on Visualization and Computer Graphics}, volume = {18}, number = {3}, pages = {516--526}, publisher = {IEEE}, abstract = {We present a fluid simulation method based on Smoothed Particle Hydrodynamics (SPH) in which incompressibility and boundary conditions are enforced using holonomic kinematic constraints on the density. This formulation enables systematic multiphysics integration in which interactions are modeled via similar constraints between the fluid pseudoparticles and impenetrable surfaces of other bodies. These conditions embody Archimede's principle for solids and thus buoyancy results as a direct consequence. We use a variational time stepping scheme suitable for general constrained multibody systems we call SPOOK. Each step requires the solution of only one Mixed Linear Complementarity Problem (MLCP) with very few inequalities, corresponding to solid boundary conditions. We solve this MLCP with a fast iterative method. Overall stability is vastly improved in comparison to the unconstrained version of SPH, and this allows much larger time steps, and an increase in overall performance by two orders of magnitude. Proof of concept is given for computer graphics applications and interactive simulations.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {article} } We present a fluid simulation method based on Smoothed Particle Hydrodynamics (SPH) in which incompressibility and boundary conditions are enforced using holonomic kinematic constraints on the density. This formulation enables systematic multiphysics integration in which interactions are modeled via similar constraints between the fluid pseudoparticles and impenetrable surfaces of other bodies. These conditions embody Archimede's principle for solids and thus buoyancy results as a direct consequence. We use a variational time stepping scheme suitable for general constrained multibody systems we call SPOOK. Each step requires the solution of only one Mixed Linear Complementarity Problem (MLCP) with very few inequalities, corresponding to solid boundary conditions. We solve this MLCP with a fast iterative method. Overall stability is vastly improved in comparison to the unconstrained version of SPH, and this allows much larger time steps, and an increase in overall performance by two orders of magnitude. Proof of concept is given for computer graphics applications and interactive simulations. |
![]() | Wan, Yijun: Discrete element method in granular material simulations. 2011. (Type: Masters Thesis | Abstract | Links | BibTeX | Tags: External) @mastersthesis{wan2011discrete, title = {Discrete element method in granular material simulations}, author = {Yijun Wan}, url = {https://pure.tue.nl/ws/portalfiles/portal/47015912/716753-1.pdf}, year = {2011}, date = {2011-01-01}, journal = {Institute of Fraunhofer ITWM Kaiserslautern/Technical University of Kaiserslautern}, abstract = {This thesis describes the theories and simulations of granular material using discrete element method. With wide applications in agriculture and mechanical engineering, granular material exhibits a number of unique physical properties. The understanding of such properties is important in order to evaluate the performance of existing methodologies and to trigger the development of new models for different functionalities in the future. As a microscopic approach, discrete element method has been proved to be adequate in most simulations of granular material. An elaborated description is provided to illustrate a three-phase scheme from the fundamental discrete element model, which includes contact detection, force interaction and time integration. Additional to the conventional scheme, we present a bonding model with a connecting rod between each pair of contacted particles. Two enhanced bonding models are discussed in detail, with special characteristics in accordance with brittle and crack propagation features, respectively. On the contrary, continuum mechanical models give a macroscopic view to investigate granular material behaviors. Difficulties arise from the solving of a complex system of partial differential equations and the connections between model parameters and phenomenological ones. Moreover, triaxial test, uniaxial compression test and blade test are chosen as three representative experiments in granular material study. Simulation results implementing discrete element method are analyzed and discussed regarding the role of different parameters. By carefully choosing models and adjusting parameters, simulation results can have a good quantitative agreement with laboratory measurements. One of our kernel concerns is the computational complexity. Therefore, we focus on exploring effective simplified models with fewer variables.}, keywords = {External}, pubstate = {published}, tppubtype = {mastersthesis} } This thesis describes the theories and simulations of granular material using discrete element method. With wide applications in agriculture and mechanical engineering, granular material exhibits a number of unique physical properties. The understanding of such properties is important in order to evaluate the performance of existing methodologies and to trigger the development of new models for different functionalities in the future. As a microscopic approach, discrete element method has been proved to be adequate in most simulations of granular material. An elaborated description is provided to illustrate a three-phase scheme from the fundamental discrete element model, which includes contact detection, force interaction and time integration. Additional to the conventional scheme, we present a bonding model with a connecting rod between each pair of contacted particles. Two enhanced bonding models are discussed in detail, with special characteristics in accordance with brittle and crack propagation features, respectively. On the contrary, continuum mechanical models give a macroscopic view to investigate granular material behaviors. Difficulties arise from the solving of a complex system of partial differential equations and the connections between model parameters and phenomenological ones. Moreover, triaxial test, uniaxial compression test and blade test are chosen as three representative experiments in granular material study. Simulation results implementing discrete element method are analyzed and discussed regarding the role of different parameters. By carefully choosing models and adjusting parameters, simulation results can have a good quantitative agreement with laboratory measurements. One of our kernel concerns is the computational complexity. Therefore, we focus on exploring effective simplified models with fewer variables. |
2010 |
|
![]() | Bodin, Kenneth; Lacoursière, Claude; Servin, Martin: Method, an apparatus and computer program product for simulating dynamic fluids. 2010, (US Patent 8,762,117). (Type: Patent | Abstract | Links | BibTeX | Tags: Algoryx) @patent{bodin2014method, title = {Method, an apparatus and computer program product for simulating dynamic fluids}, author = {Kenneth Bodin and Claude Lacoursière and Martin Servin}, url = {https://patents.google.com/patent/US8762117B2/pt-PT https://patents.google.com/patent/US8762117B2/en https://patentimages.storage.googleapis.com/38/bd/ef/3d9e47f70c46e3/US8762117.pdf }, year = {2010}, date = {2010-05-26}, publisher = {Google Patents}, abstract = {The invention relates to a method for simulating dynamic fluids comprising a plurality of pseudo particles. The method comprising the steps of defining a fluid mass density of the pseudo particle masses; defining a mass density constraint such that the mass density on each pseudo particle is con strained to a reference mass density of a real fluid, whereby an instant propagation of density fluctuations through the entire fluid system is enabled; performing constraint stabilization on said mass density constraint using a time stepping function, wherein said time stepping function is arranged to conserve global physical symmetries and is stable for violations of said mass density constraint; solving a linear system of equations for said mass density constraint in order to calculate density constraint forces; calculating new time discrete pseudo particle Velocities from previous pseudo particle velocities with addition of velocity increments calculated from said density constraint forces; and calculating new time discrete pseudo particle positions from the previous pseudo particle positions with additions of the position increments calculated from said new pseudo particle velocities. The invention also relates to an apparatus for simulating dynamic fluids and a computer program product for the same. }, note = {US Patent 8,762,117}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {patent} } The invention relates to a method for simulating dynamic fluids comprising a plurality of pseudo particles. The method comprising the steps of defining a fluid mass density of the pseudo particle masses; defining a mass density constraint such that the mass density on each pseudo particle is con strained to a reference mass density of a real fluid, whereby an instant propagation of density fluctuations through the entire fluid system is enabled; performing constraint stabilization on said mass density constraint using a time stepping function, wherein said time stepping function is arranged to conserve global physical symmetries and is stable for violations of said mass density constraint; solving a linear system of equations for said mass density constraint in order to calculate density constraint forces; calculating new time discrete pseudo particle Velocities from previous pseudo particle velocities with addition of velocity increments calculated from said density constraint forces; and calculating new time discrete pseudo particle positions from the previous pseudo particle positions with additions of the position increments calculated from said new pseudo particle velocities. The invention also relates to an apparatus for simulating dynamic fluids and a computer program product for the same. |
![]() | Gunnarsson, Morgan: Robot Design Optimization by means of a Genetic Algorithm and Physics Simulation. 2010. (Type: Masters Thesis | Abstract | Links | BibTeX | Tags: Algoryx) @mastersthesis{gunnarsson2010robot, title = {Robot Design Optimization by means of a Genetic Algorithm and Physics Simulation}, author = {Morgan Gunnarsson}, url = {http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A375435&dswid=-7990 http://umu.diva-portal.org/smash/get/diva2:375435/FULLTEXT01.pdf}, year = {2010}, date = {2010-01-01}, abstract = {This thesis presents a new robot design paradigm that utilizes evolutionary optimization techniques and advanced physics simulations. This technology makes it possible to design and test robots in virtual environments before the physical robots are built, which enables robot manufacturers to improve the performance of their products and decrease the time and cost for development. In this project, a 3D robot model was defined in geometric, kinematic and dynamic terms. Also, a piece of software was developed in C++ to optimize the robot design, and to simulate and visualize the robot model with the aid of a physics engine. A genetic algorithm was developed for the optimization and used to minimize the average positional error and the total torque magnitude under constraints on speed, and the design variables were the PID controller parameters and the torque actuator limits. Only predefined robots can be programmed and simulated with current software packages for offline-programming and robot simulation. It was concluded that such software packages can be improved by robot design optimization using the software developed in this project, by means of a genetic algorithm and simulations using a physics engine.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {mastersthesis} } This thesis presents a new robot design paradigm that utilizes evolutionary optimization techniques and advanced physics simulations. This technology makes it possible to design and test robots in virtual environments before the physical robots are built, which enables robot manufacturers to improve the performance of their products and decrease the time and cost for development. In this project, a 3D robot model was defined in geometric, kinematic and dynamic terms. Also, a piece of software was developed in C++ to optimize the robot design, and to simulate and visualize the robot model with the aid of a physics engine. A genetic algorithm was developed for the optimization and used to minimize the average positional error and the total torque magnitude under constraints on speed, and the design variables were the PID controller parameters and the torque actuator limits. Only predefined robots can be programmed and simulated with current software packages for offline-programming and robot simulation. It was concluded that such software packages can be improved by robot design optimization using the software developed in this project, by means of a genetic algorithm and simulations using a physics engine. |
![]() | Sundholm, Erik: Distance Fields Accelerated with OpenCL. Department of Computing Science, Umeå University, Sweden, 2010. (Type: Masters Thesis | Abstract | Links | BibTeX | Tags: Algoryx) @mastersthesis{sundholm2010distance, title = {Distance Fields Accelerated with OpenCL}, author = {Erik Sundholm}, url = {http://umu.diva-portal.org/smash/record.jsf?pid=diva2:327072 http://umu.diva-portal.org/smash/get/diva2:327072/FULLTEXT01.pdf}, year = {2010}, date = {2010-01-01}, school = {Department of Computing Science, Umeå University, Sweden}, abstract = {An important task in any graphical simulation is the collision detection between the objects in the simulation. It is desirable to have a good general method for collision detection with high performance. This thesis describes an implementation of a collision detection method that uses distance fields to detect collisions. This method is quite robust and able to detect collisions between most possible shapes. It is also capable of computing contact data for collisions. A problem with distance fields is that the performance cost for making a distance field is quite extensive. It is therefore customary to have some way of accelerating the computation of the distance field (usually by only computing select parts of the field). The application implemented in this thesis solves this performance problem by using the parallel framework OpenCL for accelerating the construction of the field.OpenCL enables programmers to execute code on the GPU. The GPU is highly data parallel and a huge increase in performance can be obtained by letting the GPU handle the computations associated with the initiation of the field.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {mastersthesis} } An important task in any graphical simulation is the collision detection between the objects in the simulation. It is desirable to have a good general method for collision detection with high performance. This thesis describes an implementation of a collision detection method that uses distance fields to detect collisions. This method is quite robust and able to detect collisions between most possible shapes. It is also capable of computing contact data for collisions. A problem with distance fields is that the performance cost for making a distance field is quite extensive. It is therefore customary to have some way of accelerating the computation of the distance field (usually by only computing select parts of the field). The application implemented in this thesis solves this performance problem by using the parallel framework OpenCL for accelerating the construction of the field.OpenCL enables programmers to execute code on the GPU. The GPU is highly data parallel and a huge increase in performance can be obtained by letting the GPU handle the computations associated with the initiation of the field. |
![]() | Lacoursière, Claude; Servin, Martin; Backman, Anders: Fast and stable simulation of granular matter and machines. Proceedings of the Fifth International Conference on Discrete Element Methods (DEM5), Citeseer 2010. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{lacoursiere2010fast, title = {Fast and stable simulation of granular matter and machines}, author = {Claude Lacoursière and Martin Servin and Anders Backman}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/faststable2010.pdf}, year = {2010}, date = {2010-01-01}, booktitle = {Proceedings of the Fifth International Conference on Discrete Element Methods (DEM5)}, organization = {Citeseer}, abstract = {We present mathematical models and numerical techniques designed to address the challenges of real-time simulator training for earth moving equipment involving heavy vehicles and granular matter. The same techniques have also been applied to mix granular matter with a nearly incompressible SPH model of water. The central elements in our technique are a unified model based on constrained multibody systems including point particles and rigid bodies, a dynamic resolution technique based on merging and splitting elementary bodies. The numerical integration is based on a time-discrete variational formulation of analytic mechanics, which is closely related to the Rattle and Shake [3] solvers. We have modified these by introducing stabilized linear approximations to avoid solving the nonlinear equations exactly [5]. Frictional contact forces are modeled using a linear complementarity (LCP) formulations similar to those already well-known in this field [8]. Our deviation from these models is mainly in the solution technique, which mixes a direct LCP solver for computing normal forces and a Gauss-Seidel (GS) process to solve for the frictional ones. The SPH model includes kinematic constraints for incompressibility and for the boundary conditions. The latter are formulated as non-penetration conditions producing also buoyancy for immersed bodies. Another novelty of our overall method is the introduction of dynamic resolution using a merge-split technique based on local analysis of contact forces and complementarity conditions. A significant result is the real-time simulation of a tractor, which can shovel granular matter consisting of moderately small elements integrated in an interactive 3D application used for operator training. The conventional computational techniques for granular materials are based either on modeling the system as distinct particles [7] or using continuum mechanics with specific constitutive laws for granular matter and discretization using finite elements or mesh-free methods. In turn, the discrete element techniques are phrased either as penalty methods, e.g., the Hertz contact model, requiring very small time steps. Complementarity formulations of contact models solved using Gauss-Seidel iterations [9] can use larger time steps, but have slow, linear convergence. By contrast, interactive applications put strong constraints on speed and time steps. There are usually roughly 10 milliseconds to compute a 1/60 second update. With this budget, there is usually only time for a single step with size h = 1/60 s. In turn the stable simulation of machines demands precise solutions to maintain stability. One additional reason for the choice of our integration method is that it is solidly anchored in discrete time mechanics and is in fact much more stable than higher order explicit methods. It is also necessary to explicitly compute the Lagrange multipliers with good precision, using a direct method for the most part, or with a good preconditioner. Our experience has shown that neither explicit penalty methods nor GS based solver can be tuned to provide sufficient stability. }, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } We present mathematical models and numerical techniques designed to address the challenges of real-time simulator training for earth moving equipment involving heavy vehicles and granular matter. The same techniques have also been applied to mix granular matter with a nearly incompressible SPH model of water. The central elements in our technique are a unified model based on constrained multibody systems including point particles and rigid bodies, a dynamic resolution technique based on merging and splitting elementary bodies. The numerical integration is based on a time-discrete variational formulation of analytic mechanics, which is closely related to the Rattle and Shake [3] solvers. We have modified these by introducing stabilized linear approximations to avoid solving the nonlinear equations exactly [5]. Frictional contact forces are modeled using a linear complementarity (LCP) formulations similar to those already well-known in this field [8]. Our deviation from these models is mainly in the solution technique, which mixes a direct LCP solver for computing normal forces and a Gauss-Seidel (GS) process to solve for the frictional ones. The SPH model includes kinematic constraints for incompressibility and for the boundary conditions. The latter are formulated as non-penetration conditions producing also buoyancy for immersed bodies. Another novelty of our overall method is the introduction of dynamic resolution using a merge-split technique based on local analysis of contact forces and complementarity conditions. A significant result is the real-time simulation of a tractor, which can shovel granular matter consisting of moderately small elements integrated in an interactive 3D application used for operator training. The conventional computational techniques for granular materials are based either on modeling the system as distinct particles [7] or using continuum mechanics with specific constitutive laws for granular matter and discretization using finite elements or mesh-free methods. In turn, the discrete element techniques are phrased either as penalty methods, e.g., the Hertz contact model, requiring very small time steps. Complementarity formulations of contact models solved using Gauss-Seidel iterations [9] can use larger time steps, but have slow, linear convergence. By contrast, interactive applications put strong constraints on speed and time steps. There are usually roughly 10 milliseconds to compute a 1/60 second update. With this budget, there is usually only time for a single step with size h = 1/60 s. In turn the stable simulation of machines demands precise solutions to maintain stability. One additional reason for the choice of our integration method is that it is solidly anchored in discrete time mechanics and is in fact much more stable than higher order explicit methods. It is also necessary to explicitly compute the Lagrange multipliers with good precision, using a direct method for the most part, or with a good preconditioner. Our experience has shown that neither explicit penalty methods nor GS based solver can be tuned to provide sufficient stability. |
![]() | Lacoursière, Claude; Linde, Mattias; Sabelström, Olof: Direct sparse factorization of blocked saddle point matrices. International Workshop on Applied Parallel Computing, pp. 324–335, Springer, Berlin, Heidelberg 2010. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{lacoursiere2010direct, title = {Direct sparse factorization of blocked saddle point matrices}, author = {Claude Lacoursière and Mattias Linde and Olof Sabelström}, url = {http://umu.diva-portal.org/smash/record.jsf?pid=diva2%3A572327&dswid=-5578}, doi = {10.1007/978-3-642-28145-7_32}, year = {2010}, date = {2010-01-01}, booktitle = {International Workshop on Applied Parallel Computing}, pages = {324--335}, organization = {Springer, Berlin, Heidelberg}, abstract = {We present a parallel algorithm for the direct factorization of sparse saddle-point matrices of moderate size coming from real-time multibody dynamics simulations. We used the specific structure of these problems both for a priori construction of supernodes and to avoid all dynamic permutations during factorization. For the latter, we present a technique we call “leaf swapping” which performs permutations of the supernodes in the elimination tree without any reference to numerical values. The results compare favorably with currently available high performance codes on our problem sets because of the high overhead necessary to process very large problems on increasingly complex supercomputers.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } We present a parallel algorithm for the direct factorization of sparse saddle-point matrices of moderate size coming from real-time multibody dynamics simulations. We used the specific structure of these problems both for a priori construction of supernodes and to avoid all dynamic permutations during factorization. For the latter, we present a technique we call “leaf swapping” which performs permutations of the supernodes in the elimination tree without any reference to numerical values. The results compare favorably with currently available high performance codes on our problem sets because of the high overhead necessary to process very large problems on increasingly complex supercomputers. |
![]() | Hansson, Anders; Servin, Martin: Semi-autonomous shared control of large-scale manipulator arms. Control Engineering Practice, 18 (9), pp. 1069–1076, 2010. (Type: Journal Article | Abstract | Links | BibTeX | Tags: Algoryx) @article{hansson2010semi, title = {Semi-autonomous shared control of large-scale manipulator arms}, author = {Anders Hansson and Martin Servin}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/semiautonomous_cep_2010.pdf }, doi = {10.1016/j.conengprac.2010.05.015}, year = {2010}, date = {2010-01-01}, journal = {Control Engineering Practice}, volume = {18}, number = {9}, pages = {1069--1076}, publisher = {Elsevier}, abstract = {Semi-autonomous operation with shared control between the human operator and control computer has been developed and examined for a large-scalemanipulator for gripping and lifting heavy objects in unstructured dynamical environments. The technique has been implemented on a electro-hydraulic actuated crane arm with redundant kinematic structure. Several modes of automation and interaction were evaluated. Experiments show satisfactory smoothness in the transitions between autonomous, shared and manual control, doubled performance in log loading for inexperienced operators while experienced operators reported reduced workload.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {article} } Semi-autonomous operation with shared control between the human operator and control computer has been developed and examined for a large-scalemanipulator for gripping and lifting heavy objects in unstructured dynamical environments. The technique has been implemented on a electro-hydraulic actuated crane arm with redundant kinematic structure. Several modes of automation and interaction were evaluated. Experiments show satisfactory smoothness in the transitions between autonomous, shared and manual control, doubled performance in log loading for inexperienced operators while experienced operators reported reduced workload. |
![]() | Servin, Martin; Lacoursière, Claude; Nordfelth, Fredrik; Bodin, Kenneth: Hybrid, multiresolution wires with massless frictional contacts. IEEE transactions on visualization and computer graphics, 17 (7), pp. 970–982, 2010. (Type: Journal Article | Abstract | Links | BibTeX | Tags: Algoryx) @article{servin2010hybrid, title = {Hybrid, multiresolution wires with massless frictional contacts}, author = {Martin Servin and Claude Lacoursière and Fredrik Nordfelth and Kenneth Bodin}, url = {https://www.youtube.com/watch?v=H8Xbtl7jX-k http://www.diva-portal.org/smash/get/diva2:317085/FULLTEXT02.pdf }, doi = {10.1109/TVCG.2010.122}, year = {2010}, date = {2010-01-01}, journal = {IEEE transactions on visualization and computer graphics}, volume = {17}, number = {7}, pages = {970--982}, publisher = {IEEE}, abstract = {We describe a method for the visual interactive simulation of wires contacting with rigid multibodies. The physical model used is a hybrid combining lumped elements and massless quasistatic representations. The latter is based on a kinematic constraint preserving the total length of the wire along a segmented path which can involve multiple bodies simultaneously and dry frictional contact nodes used for roping, lassoing, and fastening. These nodes provide stick and slide friction along the edges of the contacting geometries. The lumped element resolution is adapted dynamically based on local stability criteria, becoming coarser as the tension increases, and up to the purely kinematic representation. Kinematic segments and contact nodes are added, deleted, and propagated based on contact geometries and dry friction configurations. The method gives a dramatic increase in both performance and robustness because it quickly decimates superfluous nodes without loosing stability, yet adapts to complex configurations with many contacts and high curvature, keeping a fixed, large integration time step. Numerical results demonstrating the performance and stability of the adaptive multiresolution scheme are presented along with an array of representative simulation examples illustrating the versatility of the frictional contact model.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {article} } We describe a method for the visual interactive simulation of wires contacting with rigid multibodies. The physical model used is a hybrid combining lumped elements and massless quasistatic representations. The latter is based on a kinematic constraint preserving the total length of the wire along a segmented path which can involve multiple bodies simultaneously and dry frictional contact nodes used for roping, lassoing, and fastening. These nodes provide stick and slide friction along the edges of the contacting geometries. The lumped element resolution is adapted dynamically based on local stability criteria, becoming coarser as the tension increases, and up to the purely kinematic representation. Kinematic segments and contact nodes are added, deleted, and propagated based on contact geometries and dry friction configurations. The method gives a dramatic increase in both performance and robustness because it quickly decimates superfluous nodes without loosing stability, yet adapts to complex configurations with many contacts and high curvature, keeping a fixed, large integration time step. Numerical results demonstrating the performance and stability of the adaptive multiresolution scheme are presented along with an array of representative simulation examples illustrating the versatility of the frictional contact model. |
2009 |
|
![]() | Nilsson, Martin: Constraint Fluids on GPU. Department of Computing Science, Umeå University, Sweden, 2009. (Type: Masters Thesis | Abstract | Links | BibTeX | Tags: Algoryx) @mastersthesis{nilsson2009constraint, title = {Constraint Fluids on GPU}, author = {Martin Nilsson}, url = {http://www8.cs.umu.se/education/examina/Rapporter/MartinNilsson.pdf https://www.algoryx.se/mainpage/wp-content/uploads/2021/04/MartinNilsson.pdf https://www.youtube.com/watch?v=0e3p5iu3zj8&t=1s&ab_channel=Algoryx}, year = {2009}, date = {2009-01-01}, publisher = {Citeseer}, school = {Department of Computing Science, Umeå University, Sweden}, abstract = {The processing power of graphics hardware has increased tremendously in the last several years and they are therefore used more and more outside of their intended domain of graphics rendering. This thesis describes the implementation and results of a fluid simulator, using the constraint fluid method, which harnesses the processing power of modern GPUs, in particular NVIDIA’s CUDA platform. As demonstrated in this thesis, particle systems with hundreds of thousands of particles can be simulated and visualized at interactive rates and systems containing up to a million particles can be run at a few frames per second. The biggest performance bottleneck is currently in the solver, in particular the lack of a working preconditioned Conjugate Gradient implementation.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {mastersthesis} } The processing power of graphics hardware has increased tremendously in the last several years and they are therefore used more and more outside of their intended domain of graphics rendering. This thesis describes the implementation and results of a fluid simulator, using the constraint fluid method, which harnesses the processing power of modern GPUs, in particular NVIDIA’s CUDA platform. As demonstrated in this thesis, particle systems with hundreds of thousands of particles can be simulated and visualized at interactive rates and systems containing up to a million particles can be run at a few frames per second. The biggest performance bottleneck is currently in the solver, in particular the lack of a working preconditioned Conjugate Gradient implementation. |
![]() | Bodin, Madelen: Creative interactive environment for doing physics. MPTL 14, University of Udine, Italy, 23-25 September 2009, 2009. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{bodin2009creative, title = {Creative interactive environment for doing physics}, author = {Madelen Bodin}, url = {http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Aumu%3Adiva-53290 http://www.fisica.uniud.it/URDF/mptl14/ftp/Booklet%20MPTL14.pdf}, year = {2009}, date = {2009-01-01}, booktitle = {MPTL 14, University of Udine, Italy, 23-25 September 2009}, abstract = {The Algodoo 2D simulation environment is built upon advanced real-time physicssimulation technology. (Demonstration video is provided on Youtube:http://www.youtube.com/watch?v=qa9xn-xYQQk) It has a graphical user interface whichmakes it possible for anybody to create and explore scenes that are physicallyinteractive. In Algodoo it is possible to create and edit scenes using simple drawingtools, save and load scenes, start and stop simulation, interact with simulation byclick, drag, tilt and shake. Color traces, force and velocity vectors can be addedfor enhanced visualization. The built-in physics simulation engines treat rigidbodies, fluids, chains, gears, gravity, contacts, friction, restitution, springs,hinges, lock, motors and also laser rays and optics. Algodoo is based on highlycompetitive technologies for interactive multiphysics simulation, includingvariational mechanical integrators and high performance numerical methods. Algodoo isparticularly intended to be used in order to encourage and make use of the students’own creativity in order to construct knowledge and giving the student a sense ofownership of their own learning. The sense of having control of the learningsituation is considered being one of the most important factors that generatemotivational behaviour. Algodoo offers new strategies for working with computers inteaching and learning physics. This study demonstrates the use of Algodoo withteacher students in physics and also with 8-9 year old girls in a science class.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } The Algodoo 2D simulation environment is built upon advanced real-time physicssimulation technology. (Demonstration video is provided on Youtube:http://www.youtube.com/watch?v=qa9xn-xYQQk) It has a graphical user interface whichmakes it possible for anybody to create and explore scenes that are physicallyinteractive. In Algodoo it is possible to create and edit scenes using simple drawingtools, save and load scenes, start and stop simulation, interact with simulation byclick, drag, tilt and shake. Color traces, force and velocity vectors can be addedfor enhanced visualization. The built-in physics simulation engines treat rigidbodies, fluids, chains, gears, gravity, contacts, friction, restitution, springs,hinges, lock, motors and also laser rays and optics. Algodoo is based on highlycompetitive technologies for interactive multiphysics simulation, includingvariational mechanical integrators and high performance numerical methods. Algodoo isparticularly intended to be used in order to encourage and make use of the students’own creativity in order to construct knowledge and giving the student a sense ofownership of their own learning. The sense of having control of the learningsituation is considered being one of the most important factors that generatemotivational behaviour. Algodoo offers new strategies for working with computers inteaching and learning physics. This study demonstrates the use of Algodoo withteacher students in physics and also with 8-9 year old girls in a science class. |
Bodin, Kenneth; Lacoursière, Claude; Servin, Martin: Method for simulating dynamic incompressible fluids using particle based spatial discretization and mass density constraints. 2009. (Type: Patent | Abstract | BibTeX | Tags: Algoryx) @patent{bodin2009method, title = {Method for simulating dynamic incompressible fluids using particle based spatial discretization and mass density constraints}, author = {Kenneth Bodin and Claude Lacoursière and Martin Servin}, year = {2009}, date = {2009-01-01}, abstract = {Disclosed is a method of simulating dynamic fluids comprising a set of pseudo particles usedto represent physical quantities of the fluid, a fluid density computed from a weightedaverage over the pseudo particle, and a density constraint on the fluid density constraining itto be incompressible with the reference density of a real physical fluid that is modeled. Theconstraint stabilization forces of the density constraint govern the dynamics of the pseudoparticles and the simulated fluid. The method comprises a combined time stepping andconstraint stabilization and relaxation method that provides global conservation of physicalsymmetries and therefore robust physical and numerical stability under large constraintviolation, and substantial improvement in efficiency over other known methods.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {patent} } Disclosed is a method of simulating dynamic fluids comprising a set of pseudo particles usedto represent physical quantities of the fluid, a fluid density computed from a weightedaverage over the pseudo particle, and a density constraint on the fluid density constraining itto be incompressible with the reference density of a real physical fluid that is modeled. Theconstraint stabilization forces of the density constraint govern the dynamics of the pseudoparticles and the simulated fluid. The method comprises a combined time stepping andconstraint stabilization and relaxation method that provides global conservation of physicalsymmetries and therefore robust physical and numerical stability under large constraintviolation, and substantial improvement in efficiency over other known methods. | |
2008 |
|
![]() | Hansson, Anders; Servin, Martin: Semi-autonomous Shared Control for Redundant Forwarder Cranes. Umeå Universitet 2008. (Type: Technical Report | Abstract | Links | BibTeX | Tags: Algoryx) @techreport{semiauto_servin2008, title = {Semi-autonomous Shared Control for Redundant Forwarder Cranes}, author = {Anders Hansson and Martin Servin}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/Hansson_Servin_Semi-autonomous%20Shared%20Control%20for%20Redundant%20Forwarder%20Cranes.pdf http://umit.cs.umu.se/wiki/Semi-Autonomous_Crane https://www.youtube.com/watch?v=OHj97eEGfxs&ab_channel=UMITResearchLab}, year = {2008}, date = {2008-06-01}, institution = {Umeå Universitet}, abstract = {Semi-autonomous operation with shared control between the human operator and an autonomous control system has been developed and examined for a forwarder crane. Shared control gives the operator and the autonomous control system simultaneous control over the same task. It also enables smooth transitions between manual and autonomous operation. Operators with professional experience of forwarder crane control as well as inexperienced operators have been engaged in experiments where performance was measured. The experiments were conducted on a forwarder crane of reduced size at Smart Crane Lab, Umeå University. Three levels of automation were evaluated: pure manual operation, semi{autonomous operation with traded control and semi{autonomous operation with shared control. The semi-autonomous operation were examined along with two methods for manual operation: conventional joint control and boom-tip control. The time-efficiency of log loading as well as smoothness of transitions between autonomous and manual operation were examined. The experiments show that with the aid of shared control the performance of the inexperienced operators increases with a factor two as compared to manual joint control. The performance of the professional operators decreases somewhat with shared control as compared to manual joint control. With shared control both professional and inexperienced operators experience a reduction in workload. Smoothness of transitions were found satisfactory.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {techreport} } Semi-autonomous operation with shared control between the human operator and an autonomous control system has been developed and examined for a forwarder crane. Shared control gives the operator and the autonomous control system simultaneous control over the same task. It also enables smooth transitions between manual and autonomous operation. Operators with professional experience of forwarder crane control as well as inexperienced operators have been engaged in experiments where performance was measured. The experiments were conducted on a forwarder crane of reduced size at Smart Crane Lab, Umeå University. Three levels of automation were evaluated: pure manual operation, semi{autonomous operation with traded control and semi{autonomous operation with shared control. The semi-autonomous operation were examined along with two methods for manual operation: conventional joint control and boom-tip control. The time-efficiency of log loading as well as smoothness of transitions between autonomous and manual operation were examined. The experiments show that with the aid of shared control the performance of the inexperienced operators increases with a factor two as compared to manual joint control. The performance of the professional operators decreases somewhat with shared control as compared to manual joint control. With shared control both professional and inexperienced operators experience a reduction in workload. Smoothness of transitions were found satisfactory. |
![]() | Servin, Martin; Backman, Anders; Bodin, Kenneth; Bergsten, Urban; Bergström, Dan; Löfgren, Björn; Nordfjell, Tomas; Wästerlund, Iwan: Visual simulation of machine concepts for forest biomass harvesting. 10th Virtual Reality International Conference (VRIC '08 Laval Virtual), Laval, France (2008), 2008. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{servin2008visual, title = {Visual simulation of machine concepts for forest biomass harvesting}, author = {Martin Servin and Anders Backman and Kenneth Bodin and Urban Bergsten and Dan Bergström and Björn Löfgren and Tomas Nordfjell and Iwan Wästerlund}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/Servin_et_al_2008_VRIC_2008.pdf}, year = {2008}, date = {2008-01-01}, booktitle = {10th Virtual Reality International Conference (VRIC '08 Laval Virtual), Laval, France (2008)}, abstract = {We present work-in-progress of applying simulator technology for developing, demonstrating and evaluating new machine concepts and work methods in off-road environments. In particular we consider a new concept machine for making efficient biomass harvesting in the process of thinning in dense forest stands and we describe how this machine concept is realized in a virtual environment and plan for simulator experiments. }, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } We present work-in-progress of applying simulator technology for developing, demonstrating and evaluating new machine concepts and work methods in off-road environments. In particular we consider a new concept machine for making efficient biomass harvesting in the process of thinning in dense forest stands and we describe how this machine concept is realized in a virtual environment and plan for simulator experiments. |
![]() | Servin, Martin; Lacoursière, Claude: Rigid body cable for virtual environments. IEEE Transactions on Visualization and Computer Graphics, 14 (4), pp. 783–796, 2008. (Type: Journal Article | Abstract | Links | BibTeX | Tags: Algoryx) @article{servin2008rigid, title = {Rigid body cable for virtual environments}, author = {Martin Servin and Claude Lacoursière}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/rbcve_ieee_final.pdf}, doi = {10.1109/TVCG.2007.70629}, year = {2008}, date = {2008-01-01}, journal = {IEEE Transactions on Visualization and Computer Graphics}, volume = {14}, number = {4}, pages = {783--796}, publisher = {IEEE}, abstract = {The present paper addresses real-time simulation of cables for virtual environments. A faithful physical model based on constrained rigid bodies is introduced and discretized. The performance and stability of the numerical method are analyzed in detail and found to meet the requirements of interactive heavy hoisting simulations. The physical model is well behaved in the limit of infinite stiffness as well as in the elastic regime, and the tuning parameters correspond directly to conventional material constants. The integration scheme mixes the well known Sto ̈ rmer-Verlet method for the dynamics equations with the linearly implicit Euler method for the constraint equations and enables physical constraint relaxation and stabilization terms. The technique is shown to have superior numerical stability properties in comparison with either chain link systems, or spring and damper models. Experimental results are presented to show that the method results in stable, real-time simulations. Stability persists for moderately large fixed integration step of ∆t = 1/60 s, with hoisting loads of up to 105 times heavier than the elements of the cable. Further numerical experiments validating the physical model are also presented.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {article} } The present paper addresses real-time simulation of cables for virtual environments. A faithful physical model based on constrained rigid bodies is introduced and discretized. The performance and stability of the numerical method are analyzed in detail and found to meet the requirements of interactive heavy hoisting simulations. The physical model is well behaved in the limit of infinite stiffness as well as in the elastic regime, and the tuning parameters correspond directly to conventional material constants. The integration scheme mixes the well known Sto ̈ rmer-Verlet method for the dynamics equations with the linearly implicit Euler method for the constraint equations and enables physical constraint relaxation and stabilization terms. The technique is shown to have superior numerical stability properties in comparison with either chain link systems, or spring and damper models. Experimental results are presented to show that the method results in stable, real-time simulations. Stability persists for moderately large fixed integration step of ∆t = 1/60 s, with hoisting loads of up to 105 times heavier than the elements of the cable. Further numerical experiments validating the physical model are also presented. |
![]() | Servin, Martin; Lacoursière, Claude; Nordfelth, Fredrik: Adaptive resolution in physics based virtual environments. SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden, pp. 47–52, Linköping University Electronic Press 2008. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{servin2008adaptive, title = {Adaptive resolution in physics based virtual environments}, author = {Martin Servin and Claude Lacoursière and Fredrik Nordfelth}, url = {http://www.ep.liu.se/ecp/034/012/ecp083412.pdf https://ep.liu.se/konferensartikel.aspx?series=ecp&issue=34&Article_No=12}, year = {2008}, date = {2008-01-01}, booktitle = {SIGRAD 2008. The Annual SIGRAD Conference Special Theme: Interaction; November 27-28; 2008 Stockholm; Sweden}, number = {034}, pages = {47--52}, organization = {Linköping University Electronic Press}, abstract = {We propose a systematic approach to adaptive resolution in physics based virtual environments (VEs) that combines the conventional requirements of realtime performance; visual appearance with important requirements on the physical simulation; such as accuracy and numerical robustness. In particular; we argue that adaptive resolution is a key element to achieve robustness in fixed time-step VEs. The idea is to adaptively substitute unstable subsystems with more simplified and robust models. The method is demonstrated on systems including stiff wires. The algorithm brings stability; realtime performance and preservation of the important physical invariants to the system. The application to general systems is discussed.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } We propose a systematic approach to adaptive resolution in physics based virtual environments (VEs) that combines the conventional requirements of realtime performance; visual appearance with important requirements on the physical simulation; such as accuracy and numerical robustness. In particular; we argue that adaptive resolution is a key element to achieve robustness in fixed time-step VEs. The idea is to adaptively substitute unstable subsystems with more simplified and robust models. The method is demonstrated on systems including stiff wires. The algorithm brings stability; realtime performance and preservation of the important physical invariants to the system. The application to general systems is discussed. |
2007 |
|
![]() | Lacoursière, Claude: Regularized, stabilized, variational methods for multibodies. Peter Bunus Dag Fritzson, Claus Führer (Ed.): The 48th Scandinavian Conference on Simulation and Modeling (SIMS 2007), 30-31 October, 2007, Göteborg (Särö), pp. 40–48, Linköping University Electronic Press, 2007, ISSN: 1650-3740. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{lacoursiere2007regularized, title = {Regularized, stabilized, variational methods for multibodies}, author = {Claude Lacoursière}, editor = {Peter Bunus, Dag Fritzson, Claus Führer}, url = {http://www.ep.liu.se/ecp/027/005/ecp072705.pdf https://ep.liu.se/en/conference-article.aspx?series=ecp&issue=27&Article_No=5}, issn = {1650-3740}, year = {2007}, date = {2007-10-21}, booktitle = {The 48th Scandinavian Conference on Simulation and Modeling (SIMS 2007), 30-31 October, 2007, Göteborg (Särö)}, pages = {40--48}, publisher = {Linköping University Electronic Press}, abstract = {A time-discrete formulation of the variational principle of mechanics is used to construct a novel first order, fixed time step integration method for multibody systems subject to mixed constraints. The new stepper, coined Spook, includes physics motivated constraint regularization and stabilization terms. The stepper is proved to be stable for the case of linear constraints, for non-zero regularization and stabilization parameters. For fixed stabilization value, the regularization can be made arbitrarily small, corresponding to arbitrarily stiff penalty forces. The “relaxed” constraint formulation permits a separation of time scales so that stiff forces are treated as relaxed constraints. Constraint stabilization makes the stiff forces modeled this way strictly dissipative, and thus, the stepper essentially filters out the high oscillations, but is rigorously symplectic for the rest of the motion. Spook solves a single linear system per time step and is insensitive to constraint degeneracies for non-zero regularization. In addition, it keeps the constraint violations within bounds of O(h 2), where h is the time step. Because it is derived from the discrete variational principle, the stepping scheme globally preserves the symmetries of the physical system. The combination of these features make Spook a very good choice for interactive simulations. Numerical experiments on simple multibody systems are presented to demonstrate the performance and stability properties.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } A time-discrete formulation of the variational principle of mechanics is used to construct a novel first order, fixed time step integration method for multibody systems subject to mixed constraints. The new stepper, coined Spook, includes physics motivated constraint regularization and stabilization terms. The stepper is proved to be stable for the case of linear constraints, for non-zero regularization and stabilization parameters. For fixed stabilization value, the regularization can be made arbitrarily small, corresponding to arbitrarily stiff penalty forces. The “relaxed” constraint formulation permits a separation of time scales so that stiff forces are treated as relaxed constraints. Constraint stabilization makes the stiff forces modeled this way strictly dissipative, and thus, the stepper essentially filters out the high oscillations, but is rigorously symplectic for the rest of the motion. Spook solves a single linear system per time step and is insensitive to constraint degeneracies for non-zero regularization. In addition, it keeps the constraint violations within bounds of O(h 2), where h is the time step. Because it is derived from the discrete variational principle, the stepping scheme globally preserves the symmetries of the physical system. The combination of these features make Spook a very good choice for interactive simulations. Numerical experiments on simple multibody systems are presented to demonstrate the performance and stability properties. |
![]() | Servin, Martin; Lacoursière, Claude: Massless Cable for Real-time Simulation. Computer Graphics Forum, pp. 172–184, Blackwell Publishing Ltd Oxford, UK 2007. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{servin2007massless, title = {Massless Cable for Real-time Simulation}, author = {Martin Servin and Claude Lacoursière}, url = {http://umit.cs.umu.se/modsimcomplmech/docs/papers/Massless.pdf https://www.youtube.com/watch?v=H8Xbtl7jX-k}, doi = {10.1111/j.1467-8659.2007.01014.x}, year = {2007}, date = {2007-01-01}, booktitle = {Computer Graphics Forum}, volume = {26}, number = {2}, pages = {172--184}, organization = {Blackwell Publishing Ltd Oxford, UK}, abstract = {A technique for real-time simulation of hoisting cable systems based on a multibody nonideal constraint is presented. The hoisting cable constraint is derived from the cable internal energies for stretching and twisting. Each hoisting cable introduces two constraint equations, one for stretching and one for torsion, which include all the rigid bodies attached by the same cable. The computation produces the global tension and torsion in the cable as well as the resulting forces and torques on each attached body. The complexity of the computation grows linearly with the number of bodies attached to a given cable and is weakly coupled to the rest of the simulation. The nonideal constraint formulation allows stable simulations of cables over wide ranges of linear and torsional stiffness, including the rigid limit. This contrasts with lumped element formulations including the cable internal degrees of freedom in which computational complexity grows at least linearly with the number of cable elements – usually proportional to cable length – and where numerical stability is sensitive to the mass ratio between the load and the lumped elements.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } A technique for real-time simulation of hoisting cable systems based on a multibody nonideal constraint is presented. The hoisting cable constraint is derived from the cable internal energies for stretching and twisting. Each hoisting cable introduces two constraint equations, one for stretching and one for torsion, which include all the rigid bodies attached by the same cable. The computation produces the global tension and torsion in the cable as well as the resulting forces and torques on each attached body. The complexity of the computation grows linearly with the number of bodies attached to a given cable and is weakly coupled to the rest of the simulation. The nonideal constraint formulation allows stable simulations of cables over wide ranges of linear and torsional stiffness, including the rigid limit. This contrasts with lumped element formulations including the cable internal degrees of freedom in which computational complexity grows at least linearly with the number of cable elements – usually proportional to cable length – and where numerical stability is sensitive to the mass ratio between the load and the lumped elements. |
![]() | Lacoursière, Claude: Ghosts and machines: regularized variational methods for interactive simulations of multibodies with dry frictional contacts. Department of Computing Science, Umeå University, Sweden, 2007. (Type: PhD Thesis | Abstract | Links | BibTeX | Tags: Algoryx) @phdthesis{lacoursiere2007ghosts, title = {Ghosts and machines: regularized variational methods for interactive simulations of multibodies with dry frictional contacts}, author = {Claude Lacoursière}, url = {http://umu.diva-portal.org/smash/get/diva2:140361/FULLTEXT01 http://urn.kb.se/resolve?urn=urn%3Anbn%3Ase%3Aumu%3Adiva-1143}, year = {2007}, date = {2007-01-01}, school = {Department of Computing Science, Umeå University, Sweden}, abstract = {A time-discrete formulation of the variational principle of mechanics is used to provide a consistent theoretical framework for the construction and analysis of low order integration methods. These are applied to mechanical systems subject to mixed constraints and dry frictional contacts and impacts|machines. The framework includes physics motivated constraint regularization and stabilization schemes. This is done by adding potential energy and Rayleigh dissipation terms in the Lagrangian formulation used throughout. These terms explicitly depend on the value of the Lagrange multipliers enforcing constraints. Having finite energy, the multipliers are thus massless ghost particles. The main numerical stepping method produced with the framework is called SPOOK. Variational integrators preserve physical invariants globally, exactly in some cases, approximately but withinfixed global bounds for others. This allows to product realistic physical trajectories even with the low order methods. These are needed in the solution of nonsmooth problems such as dry frictional contacts and in addition, they are computationally inexpensive. The combination of strong stability, low order, and the global preservation of invariants allows for large integration time steps, but without loosing accuracy on the important and visible physical quantities. SPOOK is thus well-suited for interactive simulations, such as those commonly used in virtual environment applications, because it is fast, stable, and faithful to the physics. New results include a stable discretization of highly oscillatory terms of constraint regularization; a linearly stable constraint stabilization scheme based on ghost potential and Rayleigh dissipation terms; a single-step, strictly dissipative, approximate impact model; a quasi-linear complementarity formulation of dry friction that is isotropic and solvable for any nonnegative value of friction coefficients; an analysis of a splitting scheme to solve frictional contact complementarity problems; a stable, quaternion-based rigid body stepping scheme and a stable linear approximation thereof. SPOOK includes all these elements. It is linearly implicit and linearly stable, it requires the solution of either one linear system of equations of one mixed linear complementarity problem per regular time step, and two of the same when an impact condition is detected. The changes in energy caused by constraints, impacts, and dry friction, are all shown to be strictly dissipative in comparison with the free system. Since all regularization and stabilization parameters are introduced in the physics, they map directly onto physical properties and thus allow modeling of a variety of phenomena, such as constraint compliance, for instance. Tutorial material is included for continuous and discrete-time analytic mechanics, quaternion algebra, complementarity problems, rigid body dynamics, constraint kinematics, and special topics in numerical linear algebra needed in the solution of the stepping equations of SPOOK. The qualitative and quantitative aspects of SPOOK are demonstrated by comparison with a variety of standard techniques on well known test cases which are analyzed in details. SPOOK compares favorably for all these examples. In particular, it handles ill-posed and degenerate problems seamlessly and systematically. An implementation suitable for large scale performance and accuracy testing is left for future work.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {phdthesis} } A time-discrete formulation of the variational principle of mechanics is used to provide a consistent theoretical framework for the construction and analysis of low order integration methods. These are applied to mechanical systems subject to mixed constraints and dry frictional contacts and impacts|machines. The framework includes physics motivated constraint regularization and stabilization schemes. This is done by adding potential energy and Rayleigh dissipation terms in the Lagrangian formulation used throughout. These terms explicitly depend on the value of the Lagrange multipliers enforcing constraints. Having finite energy, the multipliers are thus massless ghost particles. The main numerical stepping method produced with the framework is called SPOOK. Variational integrators preserve physical invariants globally, exactly in some cases, approximately but withinfixed global bounds for others. This allows to product realistic physical trajectories even with the low order methods. These are needed in the solution of nonsmooth problems such as dry frictional contacts and in addition, they are computationally inexpensive. The combination of strong stability, low order, and the global preservation of invariants allows for large integration time steps, but without loosing accuracy on the important and visible physical quantities. SPOOK is thus well-suited for interactive simulations, such as those commonly used in virtual environment applications, because it is fast, stable, and faithful to the physics. New results include a stable discretization of highly oscillatory terms of constraint regularization; a linearly stable constraint stabilization scheme based on ghost potential and Rayleigh dissipation terms; a single-step, strictly dissipative, approximate impact model; a quasi-linear complementarity formulation of dry friction that is isotropic and solvable for any nonnegative value of friction coefficients; an analysis of a splitting scheme to solve frictional contact complementarity problems; a stable, quaternion-based rigid body stepping scheme and a stable linear approximation thereof. SPOOK includes all these elements. It is linearly implicit and linearly stable, it requires the solution of either one linear system of equations of one mixed linear complementarity problem per regular time step, and two of the same when an impact condition is detected. The changes in energy caused by constraints, impacts, and dry friction, are all shown to be strictly dissipative in comparison with the free system. Since all regularization and stabilization parameters are introduced in the physics, they map directly onto physical properties and thus allow modeling of a variety of phenomena, such as constraint compliance, for instance. Tutorial material is included for continuous and discrete-time analytic mechanics, quaternion algebra, complementarity problems, rigid body dynamics, constraint kinematics, and special topics in numerical linear algebra needed in the solution of the stepping equations of SPOOK. The qualitative and quantitative aspects of SPOOK are demonstrated by comparison with a variety of standard techniques on well known test cases which are analyzed in details. SPOOK compares favorably for all these examples. In particular, it handles ill-posed and degenerate problems seamlessly and systematically. An implementation suitable for large scale performance and accuracy testing is left for future work. |
![]() | Lacoursière, Claude: A Parallel Block Iterative Method for Interactive Contacting Rigid Multibody Simulations on Multicore PCs. Kågström, Bo; Elmroth, Erik; Dongarra, Jack; Wasniewski, Jerzy (Ed.): Applied Parallel Computing. State of the Art in Scientific Computing, PARA 2006. Lecture Notes in Computer Science, pp. 956–965, Springer Berlin Heidelberg, Berlin, Heidelberg, 2007, ISBN: 978-3-540-75755-9. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: ) @inproceedings{parallell_block_lacoursiere2007, title = {A Parallel Block Iterative Method for Interactive Contacting Rigid Multibody Simulations on Multicore PCs}, author = {Claude Lacoursière}, editor = {Bo Kågström and Erik Elmroth and Jack Dongarra and Jerzy Wasniewski}, url = {http://umu.diva-portal.org/smash/record.jsf?language=sv&pid=diva2%3A916717&dswid=-5162 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.366&rep=rep1&type=pdf }, doi = {10.1007/978-3-540-75755-9_113}, isbn = {978-3-540-75755-9}, year = {2007}, date = {2007-01-01}, booktitle = {Applied Parallel Computing. State of the Art in Scientific Computing, PARA 2006. Lecture Notes in Computer Science}, volume = {4699}, pages = {956--965}, publisher = {Springer Berlin Heidelberg}, address = {Berlin, Heidelberg}, abstract = {A hybrid, asynchronous, block parallel method to approximately solve complementarity problems (CPs) in real-time on multicore CPUs is described. These problems arise from interactive real-time simulations of systems of constrained, contacting rigid bodies, which are useful in virtual operator training systems for instance. A graph analysis phase identifies components which are weakly coupled using simple heuristics. Each component is then solved in parallel using either a block principal pivot or a projected block Gauss-Seidel method running in separate threads. Couplings which generate forces between the subsystems are handled iteratively using a Gauss-Seidel process which communicates updates between the interacting subsystems asynchronously. Preliminary results show that this approach delivers good performance while keeping overhead small.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } A hybrid, asynchronous, block parallel method to approximately solve complementarity problems (CPs) in real-time on multicore CPUs is described. These problems arise from interactive real-time simulations of systems of constrained, contacting rigid bodies, which are useful in virtual operator training systems for instance. A graph analysis phase identifies components which are weakly coupled using simple heuristics. Each component is then solved in parallel using either a block principal pivot or a projected block Gauss-Seidel method running in separate threads. Couplings which generate forces between the subsystems are handled iteratively using a Gauss-Seidel process which communicates updates between the interacting subsystems asynchronously. Preliminary results show that this approach delivers good performance while keeping overhead small. |
2006 |
|
Lacoursière, Claude: A regularized time stepper for multibody systems. Department of Computing Science, Umeå University, 2006. (Type: Book | BibTeX | Tags: Algoryx) @book{lacoursiere2006regularized, title = {A regularized time stepper for multibody systems}, author = {Claude Lacoursière}, year = {2006}, date = {2006-01-01}, publisher = {Department of Computing Science, Umeå University}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {book} } | |
![]() | Servin, Martin; Lacoursière, Claude; Melin, Niklas: Interactive simulation of elastic deformable materials. SIGRAD 2006. The Annual SIGRAD Conference; Special Theme: Computer Games, Linköping University Electronic Press 2006. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{servin2006interactive, title = {Interactive simulation of elastic deformable materials}, author = {Martin Servin and Claude Lacoursière and Niklas Melin}, url = {https://ep.liu.se/ecp/019/005/ecp01905.pdf https://ep.liu.se/konferensartikel.aspx?series=ecp&issue=19&Article_No=5}, year = {2006}, date = {2006-01-01}, booktitle = {SIGRAD 2006. The Annual SIGRAD Conference; Special Theme: Computer Games}, number = {019}, organization = {Linköping University Electronic Press}, abstract = {A novel; fast; stable; physics-based numerical method for interactive simulation of elastically deformable objects is presented. Starting from elasticity theory; the deformation energy is modeled in terms of the positions of point masses using the linear shape functions of finite element analysis; providing for an exact correspondence between the known physical properties of deformable bodies such as Young’s modulus; and the simulation parameter. By treating the infinitely stiff case as a kinematic constraint on a system of point particles and using a regularization technique; a stable first order stepping algorithm is constructed which allows the simulation of materials over the entire range of stiffness values; including incompressibility. The main cost of this method is the solution of a linear system of equations which is large but sparse. Commonly available sparse matrix packages can process this problem with linear complexity in the number of elements for many cases. This method is contrasted with other well-known point mass models of deformable solids which rely on penalty forces constructed from simple local geometric quantities; e.g.; spring-and-damper models. For these; the mapping between the simulation parameters and the physical observables is not well defined and they are either strongly limited to the low stiffness case when using explicit integration methods; or produce grossly inaccurate results when using simple linearly implicit method. Validation and timing tests on the new method show that it produces very good physical behavior at a moderate computational cost; and it is usable in the context of real-time interactive simulations.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } A novel; fast; stable; physics-based numerical method for interactive simulation of elastically deformable objects is presented. Starting from elasticity theory; the deformation energy is modeled in terms of the positions of point masses using the linear shape functions of finite element analysis; providing for an exact correspondence between the known physical properties of deformable bodies such as Young’s modulus; and the simulation parameter. By treating the infinitely stiff case as a kinematic constraint on a system of point particles and using a regularization technique; a stable first order stepping algorithm is constructed which allows the simulation of materials over the entire range of stiffness values; including incompressibility. The main cost of this method is the solution of a linear system of equations which is large but sparse. Commonly available sparse matrix packages can process this problem with linear complexity in the number of elements for many cases. This method is contrasted with other well-known point mass models of deformable solids which rely on penalty forces constructed from simple local geometric quantities; e.g.; spring-and-damper models. For these; the mapping between the simulation parameters and the physical observables is not well defined and they are either strongly limited to the low stiffness case when using explicit integration methods; or produce grossly inaccurate results when using simple linearly implicit method. Validation and timing tests on the new method show that it produces very good physical behavior at a moderate computational cost; and it is usable in the context of real-time interactive simulations. |
2005 |
|
![]() | Backman, Anders: Colosseum3D-Authoring framework for Virtual Environments.. IPT/EGVE, pp. 225–226, Citeseer 2005. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{backman2005colosseum3d, title = {Colosseum3D-Authoring framework for Virtual Environments.}, author = {Anders Backman}, url = {http://www8.cs.umu.se/research/ifor/dl/SEQUENCE%20LEARINIG/colosseum3d_egve05.pdf}, year = {2005}, date = {2005-01-01}, booktitle = {IPT/EGVE}, pages = {225--226}, organization = {Citeseer}, abstract = {This paper describes an authoring environment for real time 3D environments, Colosseum3D. The framework makes it possible to easily create rich virtual environments with rigid-body dynamics, 3D rendering using OpenGL Shaders, 3D sound and human avatars. The creative process of building com- plex simulators is supported by allowing several authoring paths such as a low level C++ API, an ex- pressive high level file format and a scripting layer. To exemplify the use of the framework, an immersive wheelchair simulator application is presented. A natural and intuitive interaction method is implemented using dynamic simulation.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } This paper describes an authoring environment for real time 3D environments, Colosseum3D. The framework makes it possible to easily create rich virtual environments with rigid-body dynamics, 3D rendering using OpenGL Shaders, 3D sound and human avatars. The creative process of building com- plex simulators is supported by allowing several authoring paths such as a low level C++ API, an ex- pressive high level file format and a scripting layer. To exemplify the use of the framework, an immersive wheelchair simulator application is presented. A natural and intuitive interaction method is implemented using dynamic simulation. |
2003 |
|
![]() | Lacoursière, Claude: Splitting methods for dry frictional contact problems in rigid multibody systems: Preliminary performance results. The Annual SIGRAD Conference. Special Theme-Real-Time Simulations. Conference Proceedings from SIGRAD2003, pp. 11–16, Linköping University Electronic Press 2003. (Type: Inproceedings | Abstract | Links | BibTeX | Tags: Algoryx) @inproceedings{lacoursiere2003splitting, title = {Splitting methods for dry frictional contact problems in rigid multibody systems: Preliminary performance results}, author = {Claude Lacoursière}, url = {http://www.ep.liu.se/ecp/010/004/ecp01004.pdf https://ep.liu.se/en/conference-article.aspx?series=ecp&issue=10&Article_No=4}, year = {2003}, date = {2003-01-01}, booktitle = {The Annual SIGRAD Conference. Special Theme-Real-Time Simulations. Conference Proceedings from SIGRAD2003}, number = {010}, pages = {11--16}, organization = {Linköping University Electronic Press}, abstract = {A splitting method for solving LCP based models of dry frictional contact problems in rigid multibody systems based on box MLCP solver is presented. Since such methods rely on fast and robust box MLCP solvers; several methods are reviewed and their performance is compared both on random problems and on simulation data. We provide data illustrating the convergence rate of the splitting method which demonstrates that they present a viable alternative to currently available methods.}, keywords = {Algoryx}, pubstate = {published}, tppubtype = {inproceedings} } A splitting method for solving LCP based models of dry frictional contact problems in rigid multibody systems based on box MLCP solver is presented. Since such methods rely on fast and robust box MLCP solvers; several methods are reviewed and their performance is compared both on random problems and on simulation data. We provide data illustrating the convergence rate of the splitting method which demonstrates that they present a viable alternative to currently available methods. |