--
UlucSaranli? - 10 Jun 2003
Review of available rigid body simulation systems
Created Thu May 29 18:27:36 EDT 2003 by Uluc Saranli
There are a number of criteria that we will use to compare various
options for simulations systems:
1. Integrator accuracy. Independent of how the system dynamics are
computed, all simulation environments incorporate an integrator
which evaluates the system dynamics and computes the system state
at subsequent time steps. Possibilities range from first order
Euler method to Runge Kutta 45 with adaptive time step adjustment
as well as various stiff integrators.
2. Enforcement of contact constraints. All the systems we consider
incorporate collision detection and dyamically form and break
contacts between objects. Methods for enforcing the contacts are
different for each system though. Possibilities range from penalty
based methods to generation of joint constraints between
objects. Another aspect of this is the friction model that is
associated with contacts.
3. Accuracy of contact detection. Whether the system does iterative
refinement of the time step to identify the "exact" time of
collision will influence the accuracy of the simulation. Most
systems use a fixed time step and rely on the constraint solver to
pull the contact back to a nonpenetrating state.
4. Available collision geometries. In most cases, polygonal
geometries are sufficient to detect collisions and deal with
contact forces. However, there are cases when smoother geometries
may be required for accurate simulation. For example, one would
need the ability to define a true cylinder or a sphere as a wheel
for smooth rolling on flat surfaces. A discretized polygonal
approximation would create behavioral errors as each edge/vertex
collides with the ground, deviating from the ideal behavior.
5. Architectural ease of use. We need to incorporate the simulation
system with our robot control software. The architectural design,
platform requirements and closed/open source nature of various
systems have impact on how easily this can be accomplished.
6. Documentation, code maturity and support.
Below is a list of existing systems that I have identified and their
conformance to the criteria that I have outlined above. The order in
which they are presented is arbitrary and should not be regarded as a
preferential order.
Open Dynamics Engine
Information:
1. Integrator accuracy: Currently only supports first order Euler
method. The API is not very transparent and it would be fairly
involved to implement more accurate integrators.
2. Enforcement of contact constraints: Their documentation gives the
impression that contacts, when they are formed at each step of the
simulation, are treated as joints and become "hard"
constraints. So, in contrast to penalty based methods which
require penetration to enforce contact constraints, this system
will enforce the contact more successfully. From what I can tell,
it supports a lot of useful parameters for the handling of
contacts. So, this is an average implementation of an LCP solver
with approximate friciton for speed.
ODE adopts an approximate Coulomb friction model. There are two
models to choose from: a. constant limits on tangential friction
forces, independent of normal force, b. a two step algorithm to
introduce some approximate dependence on normal force. Both of
these replace circular friction cone with local axis aligned
rectangular cones. The second ption is approximate in the sense
that it first computes the normal force assuming zero friction,
then in the second iteration, it uses Coulomb limits based on the
normal force from the previous step.
3. Accuracy of contact detection: There is no explicit refinement
mechanism for identifying exact collision time. The system relies
on a mechanism which corrects for constraint drift to bring the
contact back to a nonpenetrating state. The initial detection
error will depend on the constant time step that was chosen as
well as the speed of colliding objects.
4. Available collision geometries: box, sphere, plane, capped
cylinder, ray. Triangular mesh support is somewhat preliminary and
not very stable. I believe that the collision detection and
contact constraints take into account the true smooth shape of
these primitives rather than polygonal approximations. Collision
detection is extensible though, so one could imagine building the
primitives we need (somewhat painful).
5. Architecturally, ODE is quite suitable for integration with
RHexLib. It does not enforce much in the way of building
simulations and has the option of replacing most components
(including graphics) with your favorite package. Runs both on
Linux and windows. The project is open-source and hence
integration will be relatively easy.
6. Documentation is not bad. There is also a very active developer
mailing list
http://q12.org/pipermail/ode/ where useful
discussions are actively going on. As with all OS projects though,
the source code will be the best resource.
CMLabs Vortex Engine
Information:
- http://www.cm-labs.com/products/vortex/
- Contact: Carlos at (514) 287 1166
- Office is localted in Montreal 420 Notre Dame Street West, suite 505 Montreal, Quebec, Canada H2Y? 1V3
- Commercial package
- Chris Urmson from RI working with Whittaker and Simmons also bought the package.
- Uses an LCP solver
- Academic pricing seems to be $4500+$2700 for support and maintenance.
1. Integrator accuracy: Vortex also currently uses a first order
Euler method based integrator. However, I have been informed that
their new version 3 (currently 2.0.1) has a flexible architecture
for incorporating new integrators and should shortly after have
more accurate integrators. Of course, as with most commercial
companies, no idea about the timeline.
2. Enforcement of contact constraints: This aspect is not very
explicitly described in their documentation. Their examples seemed
to involve a lot more surface penetration than expected if the
constraint satisfaction were more accurate. It will probably be
hard to get details on how the internals of their system work.
Their documentation says they use LCP solver to enforce the
constraints, which leads me to believe that the actual enforcement
is accurate. Perhaps the penetration is caused by inaccurate
detection of collisions?
3. Accuracy of contact detection: Cortex also uses constant time step
iterations and hence does not accurately detect collisions. It may
be possible to play tricks at the higher level simulation loop to
do iterative refinement, but this may involve some nontirivial
hacking. On the other hand, they seem to have a "safetime"
feature which eliminates problems when small but fast traveling
objects (such as bullets) pass through thin stationary objects
(such as walls).
4. Available collision geometries: The collision geometries provided
by Vortex are fairly extensive. They support geometrical
primitives such as boxes, cones, cylinders, planes and spheres, as
well as mesh types such as convex mesh, triangle mesh and triangle
list. They also support heigh fields and composite models. I don't
think there is any way to extend the collision models in an
integrated way, although callbacks etc. are provided to
potentially enable custom collision handling.
5. Architectural ease of use: Vortex is also very suitable for
integration with RHexLib. The main simulation loop is not hidden
and can be easily embedded in a separate application. Vortex is a
development library rather than a standalone system, so
integration will be easy. Visualization can be done through the
facilities supplied with the library or any other package we may
choose to use. I had a few minor problems with compilation due to
compiler and library mismatches, but these should be relatively
easy to deal with. The major concern is the closed source nature
of the library and the dependence on the company in case of
lacking features.
6. API documentation is very good, although it lacks some of the
technical details on the algorithms that are used. They have a
number of good source code examples. The code seems fairly mature
and stable, but there are some features lacking as mentioned
above. Support is responsive, although we probably will not get
too much technical support unless we purchase one of their support
packages.
Adams/Solver
Information:
1. Integrator accuracy: Adams is our best option in this regard. They
feature 5 or 6 different integrators with various accuracy and
stability properties. Their target market is much more accuracy
oriented than other game-oriented systems. However, I had the
impression that their constraint solver is Lagrangian based and
hence deals with contacts through penalty methods. I am not 100%
sure of this, but it may reproduce less reliable results than, for
example, an LCP based solver designed to exactly satisfy contact
constraints.
2. Enforcement of contact constraints: As mentioned above, ADAMS uses
penalty based methods which make contact constraints not so
accurate. I believe joints are enforced through Lagrange
multipliers and are hence accurately maintained. Maybe their
choice of penalty based methods is historical as their system was
designed before LCP methods were widely known
3. Accuracy of contact detection: I don't have much information or
experience in this regard. However, knowing that ADAMS is widely
used in a number of commercial settings which require accuracy, I
would guess that they handle collision detection fairly
accurately.
4. Available collision geometries: Once again, I don't have much
information in this regard. CMU has site license for Adams and I
am trying to get a copy to check this stuff out.
5. Architectural ease of use: This is where Adams loses. Currently,
it is Windows based (Unix version is in the works, except the Sun
version which is somewhat crippled based on our earlier
interfacing efforts) and it is a standalone application rather
than a library. As a consequence, any interfacing to RHexLib will
have to take place through socket type interfaces and over the
network, which will be rather painful to implement and
use. Furthermore, I am not sure whether it will be possible to
implement a scheme where RHexLib is the "master" of the simulation
and controls execution flow.
6. Overall, I think the documentation is good for their interactive
version. However, for the kinds of interfacing that we want to do,
it may not be that helpful. The kind of application we have in
mind does not conform to their mainstream target market, which is
more interested in interactive design and evaluation than control
through a custom C interface. Once again, though, I do not have
extensive experience in this regard.
Darwin 2K
Information:
1. Integrator accuracy: Seems to use an adaptive time step RK45,
which is good. However, due to the insufficiency of the
documentation, I could not find what the constraint solver is
based on, neither for joints nor for contacts. So, we would need
to do some source-digging to figure out what is going on.
2. Enforcement of contact constraints: Again, the documentation is
not sufficient for an assesment. I will probably try to contact
Chris for more info.
3. Accuracy of contact detection: From what I could tell, there isn't
any explicit iteration for accurate contact detection. I am not
100% sure though.
4. Available collision geometries: darwin 2K uses RAPID for its
collision detection and hence only supports polygonal meshes for
collision detection and contacts. This will result in inaccuracies
when trying to model things like wheels.
5. Architectural ease of use: Darwin 2K is open source, but its
design is not as suitable for RHexLib integration os, for example,
ODE. However, my impression from the source code was that it will
be fairly straightforward to make it into a slave simulation
engine to controller execution on RHexLib.
A big drawback of
Darwin2K? is that its core design is somewhat
polluted with its target domain, which is evolution of robot
designs for optimization. It willrequire some architectural
reworking to isolate the simulator to be embedded in our
applications.
6. This is the worst aspect of Darwin 2K. Even though there is some
reference documentation about the source, there is practically
nothing explaining the overall structure of the library or the
details of the methods used. Chris' thesis and the book based on
the thesis are very high level and do not particularly address the
implementation details of Darwin 2K. So, we will need to do a fair
bit of reverse engineering to get things working. Given the
unceertainities about the constraint satisfaction methods and
such, I am not sure whether this is a very good option.
SD/Fast
Information:
1. Integrator accuracy: SDFast comes with a RK4 integrator but it is
possible and easy to use other integrators including other
commercially available packages.
2. Enforcement of contact constraints: SDFast solves DAE based
constraints. From the documentation, I got the impression that no
unilateral constraints (inequality) are supported. As a
consequence, it does not seem to have native support for
contacts. We would need to implement contact management ourselves
with possibly discrete transition mechanisms etc. I suspect this
would be
very involved.
3. Accuracy of contact detection: There is no contact detection. We
would need to come up with contact models and implement iterative
solution methods for their accurate detection.
4. Available collision geometries: No collision detection support.
5. Architectural ease of use: SDFast outputs C code which can then be
compiled and linked into anything we want. In that respect, it is
very flexible. However, lack of support for collision and contact
constraints makes it pretty much unusable alone. We would need
additional software for those capabilities. One potential problem
is that Linux does not seem to be supported?
6. SDFast is very well documented and mature. There is also a large
number of people who have used it for accurate simulation
purposes.
Arachi Simulation Engine
Information:
- http://www.arachi.com/ (very poor website with no info)
- Contacts: Diego Ruspini <druspini@arachi.com>, Kyong-Sok Chang <kcchang@arachi.com>
- Commercial library, mainly developed on windows but works under Linux
1. Integrator accuracy: Supports Euler, mid-point and huen 2nd order integrators. There seems to be flexibility in adding higher order integrators, but in presence of collisions the higher timesteps may not be desirable. Overall, the developers are knowledgeable about this issue and their systems seems to provide adequate accuracy.
2. Enforcement of contact constraints: Uses Baraff style LCP. Multibody dynamics are modeled using the Featherstone algorithm. Also handles closed chains.
3. Accuracy of contact detection: Uses a variant of Brian Mirtich's timewarp algorithm. Uses iterative methods to find exact time of collision. Currently does not handle missed collisions due to discrete time steps, but they are open to the idea of adding swept volume capabilities. Seems to be the implementation with most complete features out there.
4. Available collision geometries: r-neighborhood around a convex hull. So, primitives like sphere, capped cylinder or rounded box can be modeled exactly. Library is equipped with means of specifying arbitrary polygonal shapes, but will slow simulation down due to the modeling of the geometries with each triangle as a convex hull of itself. Seems to be a little bit troublesome. As with other library style packages, the geometry needs to be built with function calls. We would need to write a "creature description language" wrapper around this, which is also true for CMLabs Vortex engine or other open-source libraries.
5. Architectural ease of use: It is a library with a well defined API, so it should be no problem to use it with
RHexLib. Access to all simulation information is possible through API calls. Detection of collisions and online creation of constraints can be done. The developers are very responsive and helpful.
6. This is a fairly new system, so documentation is limited. The company was very responsive and they seem to be open to working together on improving their system as well. Given the rich feature-set, I think this is a system which could work for us.
update: I have obtained a evaluation version of the library and discovered that the documentation is currently very far behind. However, the developers have answered all my questions with a fairly impressive level of detail, which makes me a lot more comfortable. Another problem is that they currently do not have an evaluation version for Linux, but one of the developers will soon (2 weeks?) get back to me with a Linux compiled version of the library. It looks like the core library is platform independent, but their examples are setup to use GLUT and QHULL, for which they have only worked with Windows versions. Clearly, before I get a working Linux version, we cannot commit to this library.
Rise Web>ClimbingRobot > RobotSimulation>SimulationComparison (10 Sep 2003, AlRizzi? )
Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.