Topology

In computer science, most of the computations require a discretization in space of the considered simulation domain. This discretization therefore implies to define the domain as a collection of subsets. Regarding the Finite Element Method (FEM), the domain is divided into small elements. These elements and their connectedness establish the topology. The topology can be used for the computation, the visualization, the collision, etc. It is therefore a transversal aspect of the simulation.

We consider meshes that are cellular complexes made of k-simplices (triangulations, tetrahedralisation) or k-cubes (quad or hexahedron meshes). These meshes are the most commonly used in real-time surgery simulation and can be hierarchically decomposed into k-cells, edges being 1-cells, triangles and quads being 2-cells, tetrahedron and hexahedron being 3-cells. To take advantage of this feature, the different mesh topologies are structured as a family tree where children topologies are made of their parent topology.

Loading a topology

MeshLoaders

When simulating the physics of an object, its topology must therefore be loaded. To do so, many loaders are available in SOFA depending on the format of the loaded file. Among others:

All MeshLoaders share a common API, especially several available data:

filename: corresponding to the path and filename of the file you are aiming at loading. This data is required.
flipNormals: to flip the mesh normals
triangulate: to divide all polygons into triangles
createSubelements: to divide all n-D elements into their (n-1)-D boundary elements (e.g. tetrahedra to triangles)
onlyAttachedPoints: to keep only points attached to elements of the mesh

Additional data (translation, rotation and scale3d) are available but it rather advised to use a TransformEngine to apply a transformation to your geometry.

All MeshLoaders propose several data as output (for the most used): * position: vector of vertices of the mesh loaded * edges: vector of edges of the mesh loaded * triangles: vector of triangles of the mesh loaded * quads: vector of quads of the mesh loaded * polygons: vector of polygons of the mesh loaded * tetrahedra: vector of tetrahedra of the mesh loaded * hexahedra: vector of hexahedra of the mesh loaded * normals: vector of the normals per vertex

Fig. 1 - Elements of topology available in SOFA

TopologyContainers

As shown in Fig. 1, these loaders will load the different elements of the topology (if any), namely: the points, edges, triangles, quads, hexas and tetras. These elements need to be saved into a TopologyContainer. This container stores all the topological information in vectors. It indicates how vertices are connected to each other by edges, triangles or any type of mesh element and implements all the related functions (e.g. getTetrahedraAroundVertex(), getTriangleIndex()). There is one container per topological element:

PointSetTopologyContainer
EdgeSetTopologyContainer
TriangleSetTopologyContainer
QuadSetTopologyContainer
TetrahedronSetTopologyContainer
HexahedronSetTopologyContainer

If the topology is uploaded from an .obj file with a topology involving tetrahedra, it would be written as:

<MeshObjLoader name="ObjLoader" filename="path_to_my_mesh.obj" />
<MechanicalObject name="StateVectors" src="@ObjLoader" />
<TetrahedronSetTopologyContainer name="TetraTopologyContainer" src="@meshLoader" />

Thus, the loader give the tetrahedral information to the TopologyContainer. From this information, the rest of the topology can be recovered, namely the triangles (faces), edges and points.

Example: examples/Demos/liver.scn

Algorithms on the geometry

Once loaded, one may want to perform computations based on the geometry. SetGeometryAlgorithms classes are already available in SOFA to access geometrical algorithms (e.g. computeTriangleArea(), isPointInTetrahedron()). The SetGeometryAlgorithms include all geometrical functions specific to the topological elements and also implement the visualization options for this topology (e.g. showing point indices, drawing triangles). One class is implemented per topological element. Thus, it exists:

PointSetGeometryAlgorithms
EdgeSetGeometryAlgorithms
TriangleSetGeometryAlgorithms
QuadSetGeometryAlgorithms
TetrahedronSetGeometryAlgorithms
HexahedronSetGeometryAlgorithms

In the XML scene, we have:

<MeshObjLoader name="ObjLoader" filename="path_to_my_mesh.obj" />
<MechanicalObject name="StateVectors" src="@ObjLoader" />
<TetrahedronSetTopologyContainer name="TetraTopologyContainer" src="@meshLoader" />
<TetrahedronSetGeometryAlgorithms name="TetraAlgorithms" template="Vec3d" drawTetrahedra="1"/>

Inheritance

When a topology is loaded in a node of the graph, the child nodes will automatically inherit from the parent's topology.

Topological changes

In some simulations, the topology may evolve. Elements could be removed, added or separated: this is dynamic topological changes. Some components in SOFA do support such topological changes. In a scene with a dynamic topology, two components are compulsory:

SetTopologyModifier: defines all the basic operations (add or remove tetrahedra) and their process
SetTopologyAlgorithms: defines more specific algorithms (e.g. subDivideTetrahedronsWithPlane(), InciseAlongEdge(), etc.)

The XLM scene looks like:

<MeshObjLoader name="ObjLoader" filename="path_to_my_mesh.obj" />
<MechanicalObject name="StateVectors" src="@ObjLoader" />
<TetrahedronSetTopologyContainer name="TetraTopologyContainer" src="@meshLoader" />
<TetrahedronSetTopologyModifier   name="Modifier" />
<TetrahedronSetTopologyAlgorithms name="TopoAlgo"   template="Vec3d" />
<TetrahedronSetGeometryAlgorithms name="TetraAlgorithms" template="Vec3d" />

Then, the nature of the topological changes can either:

be scheduled using a specific component: the TopologicalChangeProcessor (many examples are available in the folder examples/Component/Topology/Container/Dynamic/)
or be developed for a specific need, e.g. simulating of cutting when a contact is detected. A class managing the topological change can be implemented using all functions implemented in the class SetTopologyModifier. Functions implementing standard removal or adding of elements are available in these modifiers. The class TopologicalChangeManager is a good example.

Topological mappings

Multi-model representation

One of the significant strength of SOFA is to allow several representation of a same object. For instance, an object can have a coarse triangular representation for the collision, a tetrahedral representation of the mechanics and a very detailed quad surface for the visualization. However, this means that these different representations must be linked one to another. This is the role of the mappings. When you run a simulation with such several representations, it assumes to load the different topologies in the scene.

From a topology to another

It is possible to define a mesh topology from another mesh topology using the same degrees of freedom. Again, the mappings make it possible. Mappings can be used either to go from one topology to a lower one in the topological hierarchy (from tetrahedra to triangles), or to split elements (quads into triangles). As usual mappings, forces applied on the slave topology are propagated onto the master one. Both topologies will therefore be assigned to the same MechanicalObject. The existing TopologicalMappings are:

Hexa2TetraTopologicalMapping
Hexa2QuadTopologicalMapping
Quad2TriangleTopologicalMapping
Tetra2TriangleTopologicalMapping
Triangle2EdgeTopologicalMapping

Topological subset

Finally, SOFA allows to select a subset of the topology using a SubsetTopologicalMapping. A part of the topology in the parent node can thus be selected to be used in a child node.

All examples are available in the folder examples/Component/Topology/Mapping/.