Sofian Toujja
email: sofian.toujja@univ-poitiers.fr

Thierry Bay
email: thierry.bay@uphf.fr

Hakim Belhaouari
email: hakim.belhaouari@univ-poitiers.fr

Laurent Fuchs
email: laurent.fuchs@univ-poitiers.fr

Topological Data Structure: The Fast Marching Example

Keywords: Topological Modeling, Generalized Map, Fast Marching Method, Front Propagation, Jerboa

This article lies in the field of front propagation algorithms on a surface represented by triangle meshes. An implementation of the fast marching algorithm using a topological structure, the generalized maps or gmaps, as the data structure of the mesh is presented. G-maps have the advantage of allowing to store and retrieve information related to the neighborhood of a cell. In this article, the necessary knowledge about generalized maps and the fast marching method are reviewed in order to facilitate the understanding of the proposed implementation and the benefits brought by g-maps as underlying data structure. Then some various applications of this implementation are presented.

.

Data: a non-obtuse triangulated mesh X, the source x 0 Result: the front arrival time starting from x 0 to all other vertices d :

the arrival time is 0 */ 4 Fr ← x 0 ; 5 /* list of all frozen vertices */ 6 Nb ← N (x 0 ); 7 /* vertex priority queue narrowband */ 8 Fa ← X \ (Fr ∪ Nb); 9 /* list of all far vertices */ 10 while Fr ̸ = X do 11 /* while all vertices are not frozen */ 12 x min ← argmin x∈Nb d(x); 13 /* The minimal arrival time vertex in Nb */ 14 /* estimate the triangles that share the vertex x min */ 15 foreach triangle (x min , x 2 , x 3 ) ∈ {x min ∈ Nb, x 2 ∈ X, x 3 ∈ Fr c } do 16

Algorithm 2: FMMMeshGoWithoutInit -Apply fast marching on an already initialized mesh.

INTRODUCTION

This article aims to study the benefits of using a topological structure as the data structure for mesh algorithms in order to simplify local data access, storage, and modification. This article is part of a larger project whose objective is to study the volumic object's evolution under constraints. First, the problem of front propagation on a surface or a volume is considered. Among the existing algorithms, the fast marching method [START_REF] Osher | Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations[END_REF] [START_REF] Sethian | Theory, algorithms, and applications of level set methods for propagating interfaces[END_REF] has been chosen because it is a well-known algorithm, rather simple to implement, and gives convincing results in a reasonable time. The originality of the proposed approach lies in the use of a topological structure, more precisely generalized maps (or g-maps), as the data structure to handle the computational data of the algorithms. The use of a topological structure such as g-maps allows us to store and retrieve local information efficiently on the mesh or in the neighborhood of a cell. Even if performance must guarantee a practical use, the goal is not to implement the fastest fast marching algorithm but to offer the possibility to extend the fast marching algorithm versatility by using g-maps. In this work, the software Jerboa [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF], a topological modeler using g-maps, is used to implement the fast marching algorithm on non-obtuse triangulated meshes.

As a preamble, important notions for the understanding of this implementation are presented. First, in section 2, the fast marching method applied to non-obtuse triangulated meshes [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] is presented. Then, in section 3, the generalized maps [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] are introduced. Finally, in section 4, the implementation as well as various practical uses are detailed.

FAST MARCHING METHOD

The necessary principles of the fast marching algorithm to understand the proposed implementation are presented here. Readers interested in fast marching can refer to [START_REF] Osher | Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations[END_REF], [START_REF] Sethian | Theory, algorithms, and applications of level set methods for propagating interfaces[END_REF], [START_REF] Sethian | Fast marching methods[END_REF] and [START_REF] Bronstein | Numerical Geometry of Non-Rigid Shapes[END_REF]. The most common analogy to explain the fast marching method is a forest fire. There may be one or more sources of the fire. The fire spreads at a different speed depending on the land; faster on dry wood than on wet wood, and not at all on water areas. As it spreads, the fire consumes the land and does not return to the already burned areas. The fast marching algorithm calculates the arrival time of a wave propagating on a manifold by approximating a solution of the following Eikonal equation at each point:

∥∇T (x)∥F(x) = 1 T (x 0 ) = 0, F(x) > 0, x, x 0 ∈ R n (1)
with T the arrival time function, F a given speed function, x denotes a point and x 0 denotes a given source point. Based on Dijkstra's algorithm (Dijkstra, 1959), the fast marching algorithm propagates through neighboring vertices. On a surface, fast marching allows to virtually get rid of the edges and cross the faces as can be seen in Figure 1. If F(x) = 1, ∀x ∈ R n then this method can be used to estimate the intrinsic distance between two vertices on a manifold. Initially applicable on an orthogonal n dimensional regular grid [START_REF] Sethian | Theory, algorithms, and applications of level set methods for propagating interfaces[END_REF], the algorithm was later extended to triangulated meshes [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF]. The vertices of the mesh have a state among three states depending on their position relatively to the wave front:

frozen: the wave front has already passed over the vertex. An arrival time has been calculated and does not change anymore.

narrowband: the wave front is currently on the vertex. An estimate of the arrival time has been calculated but may still change.

far: the wave front has not yet reached the vertex. Its arrival time from the source is still unknown and set to a value representing the infinite value.

Figure 2 illustrates the propagation and the different states of a vertex. The propagation goes from "frozen" vertices to "far" ones. The "narrowband" represents the current front of the propagation.

Initially, the sources are in the state "frozen" and their front arrival time is "0". The other vertices are in the state "far" and their front arrival time is set to infinite value. Each vertex of the mesh has information on the velocity of the front at this point. Basically, the algorithm selects the "narrowband" vertex with the minimal arrival time, set it to "frozen" and calculates an arrival time estimation for its neighbors and put them into the "narrowband" state. It loops until all the vertices are "frozen", see Algorithm 1. For this algorithm, accessing the neighbouring information is one of the key problems. This point motivates the use of a topological structure which efficiently gives access to neighbouring elements containing the necessary information.

GENERALIZED MAPS

A generalized map (or g-map) is a topological structure representing, as a graph, the topology of a manifold (orientable or not) by its boundaries (B-rep) [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF]. Their definition is homogeneous in all dimensions, avoiding having to take into account particular cases when developing dimension-homogeneous algorithms. G-maps represent structured objects by highlighting the adjacency relations between the different composing elements. It is interesting to note that g-maps guarantee us a topological consistency through the respect of some constraints, see [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF]. Relations with other topological structures can be found in [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF].

Construction

G-maps can be constructed intuitively by successive decomposition of a manifold into cells of decreasing dimensions. For a manifold of dimension 2, each face is composed of a set of edges, and each edge is composed of two darts. As darts are atomic elements, the decomposition stops here. The g-map in Figure 3c is obtained. The adjacency relations between the different cells are represented by the notation α i with i the dimension of the two connected cells: two faces (cell of dimension two) are connected by a α 2 link (in blue in Figure 3d), two edges by a α 1 link (in red), two vertices by a α 0 link (in black), and two cells of dimension n by a α n link.

/* for all triangles (x min , x 2 , x 3 ) such as x 3 is not frozen */

Orbits

An orbit is a sub-graph of a g-map. It is a set of darts that can be reached via a list of defined relations and a dart to which it applies. It is noted ⟨α x , α y , . . .⟩(d) with d the optional application dart. If no application dart is mentioned, an orbit type is obtained. It selects all subgraphs corresponding to the set of given relations, see Figure 4a. If the application dart is specified, an instance of orbit is obtained, see Figure 4b. In these two cases, usually the same word "orbit" is used to designate an orbit type or an instance of orbit. In Figure 4b, the orbit ⟨α 1 , α 2 ⟩ starts on dart "a" and only α 1 and α 2 are followed. It is interesting to note that, for example, in Figure 4b: ⟨α 1 , α 2 ⟩(a) = ⟨α 1 , α 2 ⟩(δ) with δ ∈ {b, c, d, e, f , g, h}.

Embeddings

Properties called "embeddings" can be added to a gmap. They are defined by a name, an orbit to which it applies, and a value. The embeddings allow us to store the information required for the fast marching algorithm. In Figure 5, the details of the embeddings of two darts "k" and "b" are highlighted. Both darts have the same value "GREEN" for the embedding "Face", giving the color of a ⟨α 0 , α 1 ⟩ orbit. Similarly, the two darts have different values for the embedding "Vertex", giving the name of a ⟨α 1 , α 2 ⟩ orbit. For one embedding associated with an orbit, the darts in this orbit have the same embedding value. For example, for the "Face" embedding, darts "b" and "k" can not have different values. The embedding consistency is handled via Jerboa: the embedding is shared for all the darts in the same orbit and the access time is optimal.

IMPLEMENTATION

The Jerboa software1 is used to implement the fast marching algorithm with a g-map. The main ideas are to use the embeddings and translate the fast marching algorithm into Jerboa's rules [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF].

The following examples are done in a 3 dimension generated modeler.

Jerboa

Jerboa allows us to perform operations on the g-map through a graph rewriting rule language. Moreover, Jerboa provides a topological inconsistency detection during the creation of these new operations [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF][START_REF] Ben Salah | A general physical-topological framework using rule-based language for physical simulation[END_REF].

Jerboa carries out the following features: -Access local information of the g-map via operators of selection of neighborhood cells (the neighboring faces, the neighboring vertices, etc). -Create, modify, and associate embeddings with different orbits. -Check the consistency of the operations.

-View the created operation in a generated modeler of the selected dimension.

Embeddings for Fast Marching

All the vertices (i.e. the orbit: ⟨α 1 , α 2 , α 3 ⟩) store information about their distance from the front, their state among {frozen, narrowband, far} and the front speed over them. The whole connected component (i.e. the orbit: ⟨α 0 , α 1 , α 2 , α 3 ⟩) shares a priority queue containing the "narrowband" vertices sorted by increasing distance. Hence, the g-map structure by itself is able to contain all the needed information.

Operations

In Jerboa, operations on g-maps are modeled by rules that are implemented by graph transforms. The following list of created operations (or rules) changes the value of the embeddings in the g-map.

-FMMInit ⟨α 0 , α 1 , α 2 , α 3 ⟩ initializes the algorithm for the connected component. A fmmPoint with the default values (distance = ∞ ; state = FAR ; speed = 1) is created for each vertex. The priority queue is initialized to be empty.

-FMMSetStart ⟨α 1 , α 2 , α 3 ⟩ The selected vertices become the sources of the propagation (distance = 0 , state = FROZEN).

-FMMMeshComputeFace ⟨α 0 , α 1 , α 3 ⟩ for a vertex in a triangular face, computes the distance based on the face's other two points.

-FMMMeshUmbrella performs FMMMeshCom-puteFace on all faces that share the vertex The chosen distance is the smallest.

-FMMMeshGo ⟨α 0 , α 1 , α 2 , α 3 ⟩ Uses the previous rules to apply fast marching.

Figure 7 illustrates the definition of the rule "FMMInit" in Jerboa's editor. Both circles, called "nodes", represent a set of darts. The left one represents the darts on which the rule applies, here all the darts in the connected component, i.e in the orbit: ⟨α 0 , α 1 , α 2 , α 3 , ⟩. Restrictions can be added in this node to select darts that follow a specific pattern: a face, a vertex, a specific geometry such as triangular faces, and many others, see [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF]. The right node represents the result of the rule. The g-map topology is not changed here, so the right node is similar to the left node, but the value of the embedding "FMMPoint" is changed to return a new FMM-Point object with some default values (distance = ∞ ; state = FAR ; speed = 1). Through this notation, once this rule is applied to a mesh, Jerboa will browse the whole connected component and affect the values of FMMPoint for all the vertices. See [START_REF] Belhaouari | JERBOA: A Graph Transformation Library for Topology-Based Geometric Modeling[END_REF] for other examples of Jerboa rules. It is important to note that these rules are the only development needed to perform fast marching on triangular meshes. Hence, Jerboa prevents from having to deal with boilerplate code and allows to focus on the algorithm itself.

Algorithms

The implementation of the fast marching method on triangle meshes described by Kimmel & Sethian algorithm [START_REF] Kimmel | Computing geodesic paths on manifolds[END_REF] (see Algorithm 1) on g-maps with Jerboa has been done. It represents about one hundred line of code in Jerboa script language. As a matter of example, the exact Jerboa code corresponding to the update function (l. 19 in Algorithm 1) is given in Algorithm 2.

Results

This section presents various applications of the fast marching algorithm using the rules presented in the previous section.

Figure 8a illustrates the application of the fast marching algorithm using three propagation sources. The color gradient goes from red (close to the source) to purple. Figures 8b,8c, and 8d represent the propagation on the mesh at specific times. Red contours are isochrones. Reminding equation (1), Γ t is the closed curve representing the set of points located at distance t from the source [START_REF] Sethian | Fast marching methods[END_REF]. Figure 8d highlights the handling of topological modifications of this approach. The contours merge and continue to propagate.

Comparison with an Existing Solution

Although performance in execution time is not our goal, a comparison has been made with the MATLAB toolbox developed by G. Peyré [START_REF] Peyre | Toolbox fast marching[END_REF], which is often cited in other works on this topic. The comparison has been realized on the same computer in the same context for both implementations.

The numerical values obtained are equal to the resulting ones from the toolbox. To apply fast marching with a single source (always the same source) on the mesh in Figure 9 and display the result, the average time of the toolbox is 0.4637 seconds versus 6.0843 seconds for this first Jerboa implementation. This difference reflects the reverse of the gain in consistency and abstraction brought by the topological structure. It is quite important to remember that, without even mentioning obvious optimisation improvements, the development of these rules in Jerboa is quite straightforward as Jerboa is handling boilerplate developments (to store, access, and maintain consistency of the data, or visualize the results). This methodology allows to focus on the algorithm and to easily explore variants in future works (unstructured mesh in arbitrary dimension).

Fast Marching on Regular Volume Grids

As g-maps are defined homogeneously in any dimension, this allows us to realize a unique fast marching rule for both 2D and 3D regular orthogonal grids, see Figure 10. Moreover, for regular grids this implementation extends to any desired dimension. Obviously, for all dimensions, the velocity field can be variable to add local zones where the front velocity is strongly penalized.

Figure 10: Same unique rule is used to apply fast marching on 2D and 3D orthogonal regular grids.

Fast Marching and Contour Detection

As a playful application, fast marching can find the shortest path in a maze, see Figure 11. For this purpose, a 2-dimensional grid was created, on which we have assigned a vertex of the g-map to each pixel of the maze image. The front velocity on a vertex is proportional to the intensity of the corresponding pixel (black pixel = low velocity). Once the g-map is set with the appropriate velocities, fast marching is applied until the chosen destination point is reached. We then backtrack from the destination to the source by selecting the shortest local distance value at each step.

CONCLUSION AND PERSPECTIVES

This work provides g-maps as a data structure for the fast marching algorithm to add abstraction with the view to be able to apply this algorithm in unstructured meshes in arbitrary dimension. G-maps also allow the storage and retrieval of personalized information through embeddings and ease of accessing neighborhoods thanks to the notion of orbits. To illustrate these points, a naive implementation of the fast marching algorithm on regular grids (in arbitrary dimension) and on triangulated surfaces is proposed. This work also shows that embeddings-only algorithms can be implemented through Jerboa graphical language, which simplifies the development thanks to its boilerplate management (visualization, embedding consistency, optimal information storing and retrieval). Furthermore, both of these choices lead to multiple future works. Indeed, the simplicity brought by Jerboa allows to prototype and explore variants made possible by g-maps. Finally, although performance is not the main aspect in our work, it could be improve by parallelizing the calculation. This work is part of a larger project aiming at modeling the evolution of volumes under constraints using a topological structure as the underlying data structure. We thus plan to continue the work towards contour prediction on a surface [START_REF] Chassagne | A new geometrical approach for fast prediction of front propagation[END_REF] and then towards the modeling of the inside of a contour.

Figure 1 :

 1 Figure 1: Dijkstra and fast marching.

Figure 2 :

 2 Figure 2: Illustration of fast marching propagation.

17

  Nb ← Nb ∪ x 3 ; 18 /* x 3 is narrowband */ 19 U pdate(x min , x 2 , x 3 ); 20 /* estimate d(x 3 ) from d(x min ) and d(x 2 ) */ 21 end 22 /* x min is frozen */ 23 Nb ← Nb \ x min ; 24 Fr ← Fr ∪ x min ; 25 end (a) Geometric representation. (b) Adjacent faces. (c) G-map obtained. (d) Zoom on dart and relations. Figure 3: G-map by successive decompositions.

  Figure 4: G-map orbits.

Figure 5 :

 5 Figure 5: Several embeddings.

  Figure 6depicts these embeddings on a surface on which the fast marching is being applied. Each vertex (i.e the orbit: ⟨α 1 , α 2 , α 3 ⟩) has information. The connected component (i.e the orbit: ⟨α 0 , α 1 , α 2 , α 3 ⟩) has a priority queue, here empty, accessible from each vertex.

Figure 6 :

 6 Figure 6: Embeddings used for the implementation of fast marching

Figure 7 :

 7 Figure 7: FMMInit operation in Jerboa editor.

Figure 8 :

 8 Figure 8: Fast marching with multiple sources.

Figure 9 :

 9 Figure 9: Comparison mesh (∼ 300 000 darts).

  Data: a dart b ∈ Ω, with Ω = ⟨α 0 , α 1 , α 2 , α 3 ⟩ Result: the distance between the source and all other vertices 1 /* first iteration on the faces linked to the source vertices to feed browse Ω by using the priority queue */ 13 while Ω. f mmPriorityQueue ̸ = empty do 14 FMMPoint currentPoint ← Ω. f mmPriorityQueue.pop();

  Figure 11: Obstacle detection and shortest path.

https://xlim-sic.labo.univ-poitiers.fr/jerboa/ and https: //xlim-sic.labo.univ-poitiers.fr/logiciels/Jerboa/

ACKNOWLEDGEMENTS

This research has received financial support from the region Nouvelle-Aquitaine, for the project JACTUM, convention N • AAPR2021-2020-11919510.