domain: qfin info

text:
Eric Innocenti
email: eric.innocenti@univ-corse.fr

Corinne Idda

Dominique Prunetti

Pierre-Régis Gonsolin

Agent-based modelling of a small-scale fishery in Corsica

Keywords: Fishery modelling, Multi-Agent System, NetLogo pattern

In this work we introduce a new multi-stock, multi-fleet, multi-species and bioeconomic model for the complex system of a small-scale fishery. The objective is to study fisheries in order to ensure the renewal of the stock of biomass. This stock represents both a means of subsistence for fishermen but also contributes to food security. We model the system as a Multi-Agent System using both Cellular Automata Model (CAM) and Agent-Based Model (ABM) computational modelling approaches. CAM are used to describe the environment and the dynamics of resources. ABM are used to describe the behaviour of fishing activities. The main interest of the conceptual model lies in the proposed laws and in its capacity to organize hierarchically all the local interactions and transition rules within the simulated entities. We report preliminary results showing that our modelling approach facilitates software parameterization for the specific requirements implied by the context of a small-scale fishery. The main results of this work consist in the creation of a computer modelling structure CAM and ABM, which constitutes a preliminary for an optimized resources management. In a future development, we will improve the behavior of economic agents in order to consider the complexity of their decision making.

Introduction

The deterioration of fishery ecosystems as a consequence of human activity implies the need to develop an effective and sustainable management of fisheries. Hence, there is a need to efficiently manage halieutic resources over time. This regulation cannot be carried out in a uniform way across the globe due to the differences between all the ecosystems.

The development of a sustainable management requires an accurate study of the location's characteristics so as to set appropriate management rules. Given its evolution, computer technology is a promising tool to understand and predict the behaviour of dynamical complex systems. Through computer simulations, Information Technology (IT) tools allow to study numerous cases so as to develop sustainable fishery management and maintain biodiversity in the ecosystems considered. In this pre-liminary work, we present a conceptual model for the design of a small-scale fishery system in the form of a Multi-Agent System (MAS) based on both Cellular-Automata Model (CAM) and Agent-Based Model (ABM) computational modelling approaches [START_REF] Hogeweg | Cellular automata as a paradigm for ecological modeling[END_REF]. As stated in [START_REF] Lindkvist | Navigating complexities: agent-based modeling to support research, governance, and management in small-scale fisheries[END_REF], "small-scale fisheries consist of an intricate network of individuals, institutions and communities. They are also part of a wider mesh of international trade, tourism and technological change. This complexity makes it hard to develop sustainable policies that would be easily applicable." Traditional fishery models in economics are based on strong hypotheses regarding both the fishermen's decision-making and population dynamics in space. They are based on emphasised analytical solutions in terms of equilibrium conditions leading to adopt simplifying assumptions such as representative agent approach, a perfect rationality of economic agents, the absence of interactions amongst agents and an instantaneous adjustment to equilibrium. On the other hand, modelling a complex fishery system using computational modelling approaches looks promising to embrace complexity and overcome issues caused by the paucity of information [START_REF] Lindkvist | Navigating complexities: agent-based modeling to support research, governance, and management in small-scale fisheries[END_REF]. In this paper, we develop a MAS of the spatio-temporal dynamics of a small-scale fishery to deal with the limitations in traditional bioeconomic fishery models. The MAS deals with heterogeneous behaviours both in economic agents' decision-making and in population dynamics in space, shaped by many interacting components. To achieve our modelling purpose, our main assumption is that the complex multi-scale dynamic system is based on a set of local interactions and transition rules organised hierarchically within enough simply entities to be simulated on traditional computers.

We obtain an effective model to produce modular and scalable experimentation that can serve as a guide for specific management scenarios. The following sections of this paper are organised as follows: in a second part, we present the state of the art in both the literature of economics and the literature of complex systems. In a third part, we define the dynamic complex system of a fishery. In a fourth part, we review the modelling concepts that underlie this work. In a fifth part, we present the conceptual model and its bioeconomic dynamics. In a sixth part, we detail the main components of the resulting computer model. An example of computer simulation is presented in the seventh part. General preliminary results are commented and discussed in an eighth part. Finally, we conclude and present research perspectives in the last part.

State of the art

The economic literature on fisheries developed significantly in the 1950s. The first major works in the field were from [START_REF] Gordon | The economic theory of a commonproperty resource: the fishery[END_REF] and [START_REF] Schaefer | Some considerations of population dynamics and economics in relation to the management of the commercial marine fisheries[END_REF], who are considered as the first authors of bioeconomic models for the regulation of fishery resources. They applied these models to the issues of resource over-exploitation by developing the maximum sustainable yield concept. Since these pioneering works, many advances have been made thanks to the contributions of game theory and spatial economics. In this case, agents are considered as perfectly rational individuals (which implies to model fishermen as individuals able to perfectly apprehend all the impacts resulting from the activity of fellow fishermen). These various impacts are assimilated to negative externalities [START_REF] Pigou | The Economics of Welfare[END_REF] that result from the fact that the exploitation of the fishery resource by one agent affects the actions of other fishermen. Indeed, through the fishing activity, the stock of resources deteriorates, which affects all fishermen, each of them seeing their own stock reduced. This effect was examined by [START_REF] Levhari | The great fish war: an example using a dynamic cournot-nash solution[END_REF]) in a Cournot duopoly in which these authors examine a cod war between Iceland and Great Britain and highlight this conflict's inherent economic implications.

Further improvements in the modelling scope were achieved thanks to the introduction of dynamics. Several authors, among them [START_REF] Dockner | Noncooperative solutions for a differential game model of fishery[END_REF], [START_REF] Clark | The optimal management of renewable resources[END_REF], [START_REF] Dockner | Differential games in economics and management science[END_REF], [START_REF] Van Long | A survey of dynamic games in economics[END_REF], [START_REF] Long | Dynamic games in the economics of natural resources: a survey[END_REF], [START_REF] Benchekroun | Transboundary fishery: a differential game model[END_REF], [START_REF] Jørgensen | Developments in differential game theory and numerical methods: economic and management applications[END_REF], [START_REF] Benchekroun | Comparative dynamics in a productive asset oligopoly[END_REF], [START_REF] Colombo | Consumer surplusenhancing cooperation in a natural resource oligopoly[END_REF] and [START_REF] Benchekroun | On the impact of trade in a common property renewable resource oligopoly[END_REF], studied the applications of dynamic and differential game theories to the management of fishery resources. For the basic analytical framework, dynamic and differential games adopt assumptions that are similar to those used by static games. Thus, there is a set of perfectly rational players, each seeking to maximise their own objective. However, these models have some limitations. Notably, in the real world, fishermen have no perfect knowledge of the state of biomass stocks or their migration. It is therefore unrealistic to assume that these negative externalities are perfectly taken into consideration and that fishermen are perfectly rational. Moreover, the optimum cannot be reached without perfect information. Finally, the heterogeneities between fishermen are poorly considered in this kind of model -if considered at all.

Concerning the spatial approach, space is generally considered as homogeneous in the economic literature. The consideration of its heterogeneous nature led the authors to focus on the impact of biological characteristics on fishing and species recruitment. The resource is not uniformly distributed in space, due to the fact that some fishing patches are more fertile and have higher growth rates than others. Furthermore, fishery resources are not static and migrate in time and space. These migration phenomena are modelled in the following contributions: [START_REF] Tuck | Marine protected areas for spatially structured exploited stocks[END_REF], [START_REF] Sanchirico | Bioeconomics of spatial exploitation in a patchy environment[END_REF], [START_REF] Sanchirico | A bioeconomic model of marine reserve creation[END_REF] and [START_REF] Smith | The economics of spatial-dynamic processes: applications to renewable resources[END_REF]. Although these works brought forward significant advances regarding the issue of over-exploitation of fishery resources, they suffer from certain limitations. The decisions regarding locations by fishermen are the result of an economic computation allowing the optimisation of their rent. In accordance with the rent dissipation hypothesis in the Gordon and Smith models, fishermen determine the location of their activity according to the relative profitability of fishing patches until the rent is dissipated over all patches. This is due to the adoption in these models of an "open access" fishing hypothesis over the whole space, which is unrealistic, as is the optimisation of the rent.

Because of all the limitations in these models, we focus in this work on the spatio-temporal modelling of the complex fishery system using agents. The use of agents will allow us to gradually introduce the complexity inherent to this kind of system [START_REF] Arthur | Complexity and the Economy[END_REF], [START_REF] Tesfatsion | Modeling economic systems as locally-constructive sequential games[END_REF]. The fishery's complex system is composed of a large number of heterogeneous entities. The behavioural descriptions that can result from it require modelling multiple interactions between many entities. The modelling process primarily involves conceptual and computer models formulations which are performed by modellers. The use of [START_REF] Idda | Agent-based multicomponent spatial simulation of a fishery[END_REF].

agents will allow us not to limit our scope to the study of an equilibrium, and also to understand the different interactions between agents. On the other hand, fishermen are no longer supposed to be perfectly rational and homogeneous, which means that we can simulate scenarios in the "digital world" closer to the behaviour of fishing activity in the "real world".

Modelling a complex fishery system in the form of an ABM has been developed over the recent years [START_REF] Carrella | Repeated discrete choices in geographical agent based models with an application to fisheries[END_REF], [START_REF] Bailey | A computational approach to managing coupled human-environmental systems: the poseidon model of ocean fisheries[END_REF], [START_REF] Cenek | An adaptable agentbased model for guiding multi-species pacific salmon fisheries management within a ses framework[END_REF], [START_REF] Carrella | Simple adaptive rules describe fishing behaviour better than perfect rationality in the us west coast groundfish fishery[END_REF], and [START_REF] Burgess | Opportunities for agentbased modelling in human dimensions of fisheries[END_REF]. In these ABM, authors develop algorithms for decisionmaking processes within fishing agents. [START_REF] Carrella | Repeated discrete choices in geographical agent based models with an application to fisheries[END_REF] used 13 different (mostly adaptive) strategies in their POSEIDON ABM to evaluate the outcome on fishermen's profits. They have shown that the bandit strategy is the most effective in their case. Nevertheless, in their ABM, agents are not heterogeneous, which limits the scope of their result. [START_REF] Carrella | Simple adaptive rules describe fishing behaviour better than perfect rationality in the us west coast groundfish fishery[END_REF] compared predicted to observed fishing models. They find that ABM with adaptive agents perform better predictions. On the other hand, when the ABM assumes that fishermen are maximisers, profits will be overestimated. Although these ABM provide important insights, they include a limited consideration of space and heterogeneity of the different agents, as well as the economic model in which fishermen interact. One of the main difficulties faced by the modeller stems from the treatment of different scales of time and space. Spatial scales are particularly difficult to model because most fish species are highly mobile.

The complex fishery system

Fishery science refers to a complex bioeconomic system characterised by a natural or artificial aquatic environment exploited by industrial, artisan and recreational fishers. This general definition is the experimental frame from which the dynamics of the system are usually observed [START_REF] Bommel | Conception objet dans le cadre des systèmes d'information spatiaux: agrégation spatiale et généralisation[END_REF].

On figure 1, we consider three main entity categories: -the environment, the locus of stakeholders movements and interactions; -the biomass exploited for economic purposes and that generally evolves according to a global population law; -fishermen operating in the environment and interacting by harvesting biomass from different stocks (patches in the environment). Consequently, in a computer simulation it is a matter of representing a set of hierarchically interconnected entities, localised in space and time, representing "a very large number of fish, a fragmented space and fishermen" (Bousquet, 1995, p. 150). The difficulty of modelling this kind of system is accentuated by the fact that the observations of this system require perspectives belonging to different disciplinary fields, and consequently the different modellers perceive this system in very different ways. Only recognised unifying concepts such as CAM and ABM allow to work in this direction.

Modelling concepts 4.1. MAS paradigm

As often reported in the literature, when dealing with the simulation of the spatio-temporal dynamics of a complex system of a set of autonomous and interacting constituents, the MAS paradigm is particularly well suited. This paradigm implies to consider the complex system through the prism of a set of subsystems that can be static or dynamic, connected and hierarchically organised. These are subsystems which interact in a unique environment which for the observer constitutes a MAS. The strength of the MAS perspective lies in its capacity to formulate the explanation of the behavioural dynamics of the complex system considered, as the result of a set of autonomous constituents called agents. Agents here are individual entities that interact in the environment according to interaction links. These agents are therefore the key concepts from the point of view of MAS and are generally sufficient to formulate an agent-based conceptual model. Thus, the conceptual model of a MAS is the abstract representation of a complex system in which clearly identified entities, called agents, interact with each other as well as with an environment. The interaction mechanisms linked to these interactions can be of different natures and evolve over time.

They are generally expressed in the form of interaction rules which describe the mechanisms of interaction between agents and which are clearly stated. The modelling process based on the MAS paradigm is illustrated in figure 2. In computer simulation science, the MAS paradigm is nowadays considered as one of the best methods for modelling complex dynamic systems. It is the source of two major modelling processes: one leading to the formulation of CAM and the other leading to the formulation of ABM [START_REF] Bonabeau | Agent-based modeling: Methods and techniques for simulating human systems[END_REF].

Cellular Automata

Cellular Automata (CA), initially proposed by Stanislas Ulam and by John von Neumann in the late 1940s, are multicomponent conceptual models that are generally organised at two levels of abstraction [START_REF] Innocenti | A multicomponent modeling approach for fishery simulations[END_REF]. A first level of abstraction called "local" or "micro" is structured according to a regular grid of com- ponents. A second level of abstraction called "global" or "macro" is considered to observe the outputs of the model through the composition of the "local states" of these components. In a CA, the components are called cells and each of them has a finite state that can evolve over time according to a deterministic or stochastic transition rule. During the simulation process, at each time step, the same transition rule is applied simultaneously to all the cells in the grid. It generates a new population of cells whose states entirely depend on the states of the previous generation. The computation of the state of a cell at time t+1 is a function of the state of this cell at time t and of the states of the finite subset of cells N called neighborhood. In this paper, the CA model essentially provides the conceptual foundation used to represent marine space.

Cellular Automata Models

CAMs are specialisations of the basic CA conceptual model. Thus, in a CAM the fixed agents of the environment play a prominent role in the mechanisms of interaction. The vast majority of these models are based on the specification of interactions between agents that can extend over several levels of abstraction, generally two or three. We consider CAMs as an increasing specialisation of the basic CA, where space and time are discrete and interactions are always local but where the environment, cells and interactions are more developed than in CA. Nowadays, they are usually used as conceptual tools to model spatial spreading dynamics as observed in some complex systems in physics [START_REF] Rui | Forest fire spread simulation algorithm based on cellular automata[END_REF], biology [START_REF] Schimit | A model based on cellular automata to estimate the social isolation impact on covid-19 spreading in brazil[END_REF], as well as in economics [START_REF] Chen | Simulating urban growth boundaries using a patch-based cellular automaton with economic and ecological constraints[END_REF]. Formally, they group together in the same entity more complex variations of the basic conceptual model of the CA. However, the definition of local transition rules in discrete space must remain quite simple to implement, even in the case a large number of components distributed on several abstraction levels. Moreover, the simulation of executable CAMs makes it possible to exploit the computing parallel (GPGPU and multi-core processors) and distributed computer hardware architectures [START_REF] Innocenti | A software framework for fine grain parallelization of cellular models with openmp: Application to fire spread[END_REF]. Finally, as CAM inherit the characteristics of CA, they also benefit from the emergence phenomenon which appears during some of the simulation experiments. It should be noted that the CA model and its CAM extensions also offer many technical benefits: they are adapted to Object Oriented Programming (O.O.P.). They also allow the production of computational models through the expression of modular and scalable components.

Agent-Based Models

ABMs are CAM extensions that have additional agents that can move in the environment. Their basic components are fixed agents and mobile agents. The environment is also considered as an agent. Figure 3 illustrates schematically the difference between a conceptual CAM model and an ABM type. In life sciences, ABMs are called "Individual-Based Models" (IBMs). CAMs and ABMs often benefit from an intrinsic capacity to describe many phenomena from the reality with great realism, mainly through the expression of transition rules formulated on very simple mathematical bases. The scientific literature presents the good performance of these models in many cases. Thus, the ABM allows to apprehend the complexity of a natural system according to a reductionist modeling process, easier to conceptualise. In the case of fisheries, they allow to use simplified formulations of a local economic behavior. They are based on the description of local autonomous entities and interactions, leaving the modeller to observe the behaviour of the system as a whole, from the appearance of new properties, not known a priori, through the emergence phenomenon.

Conceptual modelling

In this model we chose to focus on the interaction between fish population dynamics (ecological dynamics) and fleet dynamics associated with fishing decision processes (economic dynamics), as is usually the case in fishery science [START_REF] Bousquet | Les systèmes multi-agents et la modélisation de la pêche dans le delta central du niger: remarques sur une expérimentation[END_REF]. In a fishery model conceptualised as a MAS, the entities of interest, i.e. economic agents (fishermen) and biological agents (biomass, fish), are spatially distributed in an environment consisting of fixed cells (CAM). Some of the agents are modelling individuals who move and interact in the fishery environment, especially considering different temporal granularity (ABM). The integration of the economic rules of fishing is obtained through the formulation of interaction rules between fishing agents (and biological agents) in subsets of cells describing different fishing patches (stocks).

Agents' biological dynamics

Our biological agents are based on a metapopulation model defined as a group of subpopulations distributed in spatially discrete habitats and interconnected via dispersion rates. Since the spatial dynamics of the population is described in a CAM, the evolution of the biomass in discrete time B N,ω,t of different patches of the discrete space N is given by:

B i,ω,t+1 = B i,ω,t + F(B i,ω,t ) -H(B i,ω,t , E i,p,t ) +D(B i,ω,t , 8 m=1 m̸ =i B m,ω,t ) (1)
Index i corresponds to a fishing patch, i = {1, ..., N}. Index m corresponds to the adjacent cells that constitute a patch i. Index ω represents the different fish species present in the patch i. p = {1, ..., P} is the set of fishermen agents in the model.

F(B i,ω,t ) is the instantaneous biomass evolution function in a patch i, such that:

F(B i,ω,t ) = r(B i,ω,t )(1 - B i,ω,t K i ) (2)
This corresponds to the logistic function of the (Verhulst, 1838) model in which r is the intrinsic growth rate and K i is the carrying capacity in the patch i.

We assume that the fishing function H(B i,ω,t , E i,p,t ) in i can be represented in linear form. It depends on the fishing effort E i,p,t in i and the quantity of biomass (B i,ω,t ) in i. qp is the catchability coefficient of a fishing agent p. This coefficient describes the level of technology of the agent, i.e. the higher qp, the greater the quantity of biomass caught for the same level of effort. Furthermore, we assume that all species fished can be caught with the same fishing gear. Thus, the fishing effort and the catchability coefficient are not dependent on the species ω. So, we express H, such that:

H(B i,ω,t , E i,p,t ) = qpB i,ω,t P p=1 E i,p,t si Z t = Z i 0 otherwise (3)
where Z i = [px i ; py i ] and Z t = [px t ; py t ] respectively represent the coordinates of the patch i and of the fishing agent p.

A fisherman agent only fishes if it reaches the patch i it chose during its internal decision process. Biomass migration occurs in Moore's neighborhood from the corresponding 8 adjacent cells, i.e.:

D(B i,ω,t , 8 m=1 m̸ =i B m,ω,t ) = In i,t -Out i,t (4) With • In i,t = d m,i,t 8 m=1 m̸ =i B m,ω,t • Out i,t = d i,m,t 8 m=1 m̸ =i B i,ω,t ; m = {1, ..., 8}
In i,t corresponds to the entries in the patch i at a percentage d m,i,t and Out i,t represents the exits from the patch i to the 8 cells of the neighborhood at a percentage d i,m,t .

Departures from a patch must coincide with arrivals in the destination patch, as long as the K carrying capacity of the destination patch has not been reached. Otherwise, the excess biomass is considered zero at destination in the patch.

Temporal granularity ∆t of the model (time step) corresponds to one hour, which makes it possible to take into account the fleet's travel time in a more refined way. Furthermore, we assume that a fishing trip does not exceed 24 hours. In other words, we only consider fishing campaigns of the "small-scale" type (artisan fishing). Our model can be adapted to be extended seamlessly to other types of fishing (coastal fishing, offshore fishing or large-scale fishing) by adapting temporal granularity. We assume that during a trip a fisherman only exploits one patch per fishing decision from the home port. A fisherman has a fixed effort that he entirely deploys in the chosen fishing patch. The decision process related to the choice of a fishing patch is exclusively based on the location of this fishing patch.

Agents' economic dynamics

The computation of the fishing rent of a fishing agent is given by:

R(B i,ω,t , E i,p,t ) = Ω ω=1 [pωH(B i,ω,t , E i,p,t )] -cpH(B i,ω,,t , E i,p,t ) 2 -γS i (5)
with pω ≥ 0 corresponding to the sale price of ω species. We assume that the selling price of a given species is a regional price. Since biomass is considered to be homogeneous throughout the entire territory, its selling price is also identical. This assumption is usual in bioeconomic models in which a world price is generally assumed for simplification purposes.

There are two components in the cost function. ( 1) cpH(B i,ω,t , E i,p,t ) 2 represents the direct fishing cost. This cost is assumed to be quadratic and convex. Thus, an increase in fishing is associated with a higher cost at an increasing rate, due to the fact that a large fishery implies a decrease in the biomass stock which becomes more and more costly to harvest. (2) γS i represents the portion of the cost related to the travel of a fishing agent. It is assumed to be linear with the distance S i travelled to reach the chosen patch i (number of cells to reach the patch i from the home port of the fishing agent).

Furthermore, we assume that if a fisherman fails to earn a positive rent, he leaves the market after a certain number of periods (fixed at three months). The logic movement of a fisherman agent is illustrated in figure 4. The travel logic of the fishing agents is modelled according to four finite states of activity over a period cor-responding to the working week of the French legislation such as:

• Waiting → Waiting: activity state Waiting symbolises periods of fishing inactivity related to the presence of the fishing agent in the home port (e.g. when leaving and after returning from a fishing activity). Between two trips, the period of inactivity of a fishing agent is given by: ∆ 1,t = 24 -4 j=2 ∆ j,t . • Waiting → Navigating: activity state Navigating corresponds to the agent's travel activity from his home port to the target fishing patch or vice versa. The behaviours related to this state of activity imply taking into account travel times between home ports and fishing patches.

We assume that the fishing agents' travel time does not exceed 24 units of time and remains strictly inferior to 10 units of time, i.e. ∆ 2,t < 10. • Fishing : this state corresponds to the fishing activity, time of setting the nets in the patch i. The fishing time ∆ 3,t is fixed at two time steps. • Loading : the latter is the time of nets removal. This time is given by ∆ 4,t = 2.

Each state transition is done in one hour, i.e. in one time step.

As for the four sequences mentioned above, they are repeated every week with the following recurrence:

• Waiting → Navigating → Fishing → Navigating: This sequence takes place at each restart of the activity, i.e. on the first day of each week. At the beginning of a week of fishing, each fisherman leaves the home port to reach the fishing patch they have chosen, throw nets and then return to the home port. • Waiting → Navigating → Loading → Navigating → Fishing → Navigating: This sequence is repeated over the next four days/outings. Fishermen leave the home port, go to the first fishing patch, take up their nets, go back to the second fishing patch, throw their nets again and return to the home port.

• Waiting → Navigating → Loading → Navigating: This sequence corresponds to the last fishing day of the week. Fishermen leave the home port for their previous fishing patch, take up their nets and return directly to the port. • Waiting: This last one represents a day of rest for fishermen. They stay in the home port for one day.

The fishing automaton can be represented by the following state-transition table: et al., 1995). Since then, the use of DP has progressively been spreading and allowed the unambiguous expression of generic and reusable computer code. Thus, DP will make it possible to disseminate good design practices, in particular those related to the know-how of specialists on the basis of a precise language and vocabulary that is common to all designers and developers. Many books dealing with DP have been published, including [START_REF] Hunt | Scala design patterns -Patterns for Practical Reuse and Design[END_REF][START_REF] Buck | Les design patterns de Cocoa[END_REF][START_REF] Buschmann | Pattern-Oriented Software Architecture Volume 1: A System of Patterns[END_REF]. In computer simulation, DP offer the opportunity to capitalise on valuable knowledge acquired from the know-how of experts in the field. The NetLogo Design Pattern is derived from the generic ABM proposed by Uri Wilensky and implemented in the Net-Logo simulation environment [START_REF] Wilensky | An introduction to agentbased modeling: modeling natural, social, and engineered complex systems with NetLogo[END_REF][START_REF] Tisue | Netlogo: Design and implementation of a multi-agent modeling environment[END_REF]. It provides a simple and efficient mechanism for simulating the behaviour of agents in CAMs or ABMs with four categories of abstract compo-nents: an omniscient observer (Observer), cells (Patches), turtles (Turtles) and links (Links). In this pattern, the Observer component is a single agent whose role consists in observing the environment and giving orders to other various agents of the model (whether mobile or not). Patches are agents which model fixed locations in space. For example, they can implement the cells of a CAM [START_REF] Innocenti | A multicomponent modeling approach for fishery simulations[END_REF]. Turtles are mobile agents that move on the patches of the environment, as for example on the cells of an ABM [START_REF] Innocenti | An iterative process to construct an interdisciplinary abm using mr potatohead: an application to housing market models in touristic areas[END_REF]. Links are special agents that are used to link Turtles agents together. They are essentially used to integrate conceptual models based on graphs into agent-based computer models. According to the Netlogo Design Pattern, we describe the agents of our ABM in the light of the three groups of generic agents: observer, patches and turtles. For that, as mentioned on figure 5, turtle agents will have to be specialised using the inheritance mechanism of O.O.P [START_REF] Banos | Agent-Based Spatial Simulation with NetLogo[END_REF]. Thus, using the NetLogo simulation environment this process will be very much simplified.

Agents organisation

In our ABM, the fishery consists of fishing patches (Stock agents) which are composed of one or many locations (Patch agents). Patch agents are linked to Stock agents and produce the biomass from each species each year. Particular patches are placed in the environment at the boundary of a stock determining the outer edges of the Moore neighborhoods of a stock location. Fishermen agents are at the source of the biomass harvesting behaviour in stocks.

Materials and Methods

Netlogo simulation platform

By organising the computer model's objects according to the Netlogo Design Pattern, it is easy to very quickly prototype an executable ABM that can be run on the Netlogo simulation environment [START_REF] Tisue | Netlogo: Design and implementation of a multi-agent modeling environment[END_REF]. Netlogo is also an effective tool for setting and visualising the results from observation. It also facilitates the calibration process from experimental data. We can thus verify the validity of the modelling hypotheses by quickly implementing them [START_REF] Prunetti | Abm/lucc of a complex economic system of land and home markets facing an intense residential development[END_REF][START_REF] Beauchemin | Tutorial on agent-based models in netlogo applied to immunology and virology[END_REF].

Simulation algorithm

The context of the study is the marine resources management in Corsica, where artisan fishing is the most widely spread. Indeed, Corsica only has 195 professional reported fishing units among which 182 are small units ("Petits Métiers Côtiers", PMC) called "pointus" (pointed-shaped fishing boats), 5 are longliner units (PML), and 8 are large trawlers (CHA). Fishing activity takes place along the entire coastline of Corsica, up to 3 nautical miles away from the shore, and along 1,045 km of coasts. Fishing areas are grouped in four corporations ("prud'homie"): Ajaccio/Propriano/Cargèse, Bonifacio, Bastia/Cap Corse and Balagne. In this work, the agents' transitions are simulated sequentially, performing the main steps depicted in Figure 8.

Each day, fisherman agents proceed to a fishing action in stock agents. Fishermen agents only relate fish in au-

Results and Discussion

We have reported here preliminary results showing that our modelling approach facilitates software parameterisation for specific requirements implied by the Corsican coastal fisheries context. Unlike other fields of study, when it comes to gain experimental data on fisheries, only observations of a real system allow to acquire this data. This mainly relates the observation of fishing activity provided by fishermen (fishing form, logbook data, sell sheet, etc.) or observations acquired by sampling throughout research campaigns. In this work, we have partly received this data in the context of the Moonfish research project (University of Corsica, 2016) that we initiated in 2016 and from the literature [START_REF] Le Manacha | Preliminary estimate of total marine fisheries catches in corsica[END_REF]. In the future, we hope to be able to integrate this data further into the model to improve it and remove random parameters. Experimental data will be acquired later during scientific field campaigns and will help to improve the computer model. This data can also provide calibration elements for the computer model.

Conclusion

In this preliminary work, we have presented a multi-stock, multi-fleet, multi-species and bioeconomic model for small-scale fisheries. As an example, Corsican coastal fisheries are described as a MAS. The model's structure complies with both CAM and ABM computational modelling approaches. Discrete time simulations are performed with the NetLogo simulation environment to evaluate our model's capabilities and deficiencies. Regarding the improvement of the behaviour of economic agents, our next step will consist in considering decision-making processes based on bandit-like reinforcement learning [START_REF] Sutton | Reinforcement learning: An introduction[END_REF]. On the basis of the work of [START_REF] Hanaki | Observational and reinforcement pattern-learning: An exploratory study[END_REF], we will use multi-armed bandit-like reinforcement strategies to determine the location chosen by fishermen for their fishing activity based on conditional probabilities.

Figure 1 .

 1 Figure 1. Illustration of the complex fishery system[START_REF] Idda | Agent-based multicomponent spatial simulation of a fishery[END_REF].

Figure 2 .

 2 Figure 2. Formulation of a conceptual model according to the MAS paradigm, based on (Innocenti et al., 2020).

Figure 3 .

 3 Figure 3. MAS: CAM versus ABM (Innocenti et al., 2019).

Figure 4 .

 4 Figure 4. Status diagram of the fishing agents.

Figure 5 .

 5 Figure 5. The main agents of the computer model.

Figure 6 .

 6 Figure 6. Organisation and interactions of the objects of the computer model.

Figure 7 .

 7 Figure 7. The digital world of the executable model under Netlogo.

Figure 7

 7 Figure 7 is an illustration of the parameterisation of the model in Netlogo with 5 fish population species, 10 fishermen (white arrows), 4 home ports (white houses) and 21 stocks (red circles).

Figure 8 .

 8 Figure 8. The Discrete-Time Simulation algorithm.

Design patterns and Netlogo pattern

  The Design Pattern (DP) concept comes from A pattern language: towns, building, construction dealing with the work of building architects Christopher Alexander, Sara Ishikawa and Murray Silverstein. These authors worked on architectural design in the 1970s and defined the notion of pattern, such as: "Each pattern describes a problem which occurs over and over again in our environment, and then describes the core of the solution to that problem, in such a way that you can use this solution a million times over, without ever doing it the same way twice." This sentence defines a DP as the description of a recurring problem associated to its solution, a specific context, an architecture and the expression of the associated generic solution. However, it is only in 1995 that the use of DP boomed with O.O.P. and the famous work by "GoF"(Gang of Four) of Erich Gamma, Richard Helm, Ralph Johnson and Jhon Vlissides(Johnson

	6. Computer model
	6.1.
	Current state	Input	Next state	Output
	Waiting	δ1	Navigating	Move
	Navigating	δ2	Fishing	Throwing of the nets
	Fishing	δ3	Navigating	Move
	Navigating	δ 4	Waiting	Return to home port
	Navigating	δ5	Loading	Recover the fish
	Loading	δ 6	Navigating	Move
	Waiting	δ7	Waiting	Nothing

Acknowledgements

This work supports one of the research themes of the BIO-DIVCORSE Project (BIODIVCORSE Explorer la biodiversité de la Corse) funded by the Collectivity of Corsica. We would also like to thank Antoine Belgodere for his patience with regard to our "noisy" meetings.


Fabien Vivodtzev
email: fabien.vivodtzev@imag.fr

Georges-Pierre Bonneau
email: georges-pierre.bonneau@imag.fr

Paul Le Texier
email: paul.letexier@cea.fr

G.-P Bonneau

Topology Preserving Simplification of 2D Non-Manifold Meshes with Embedded Structures

Keywords: Computational Geometry and its Applications, LOD Techniques, Multi-resolution

Mesh simplification has received tremendous attention over the past years. Most of the previous works deal with a proper choice of error measures to guide the simplification. Preserving the topological characteristics of the mesh and possibly of data attached to the mesh is a more recent topic, the present paper is about. We introduce a new topology preserving simplification algorithm for triangular meshes, possibly non-manifold, with embedded polylines. In this context embedded means that the edges of the polylines are also edges of the mesh. The paper introduces a robust test to detect if the collapse of an edge in the mesh modifies either the topology of the mesh or the topology of the embedded polylines. This validity test is derived using combinatorial topology results. More precisely we define a so-called extended complex from the input mesh and the embedded polylines. We show that if an edge collapse of the mesh preserves the topology of this extended complex, then it also preserves both the topology of the mesh and the embedded polylines. Our validity test can be used for any 2-complex mesh, including non-manifold triangular meshes. It can be combined with any previously introduced error measure. Implementation of this validity test is described. We demonstrate the power and versatility of our method with scientific data sets from neuroscience, geology and CAD/CAM models from mechanical engineering.

Introduction

We assume the reader is familiar with mesh simplification techniques in general and their importance in Scientific Visualization. Most of the previous works on mesh simplification are devoted to the development of a specific scalar error measure, taking into account the geometry of the mesh and possibly the values of data attached to the mesh. A more recent topic in mesh simplification is the preservation of topological characteristics of the mesh and of data attached to the mesh. In this paper a new topology preserving simplification algorithm is introduced for triangular meshes, possibly non-manifold, in which polylines are embedded. In this context embedded means that the edges of the polylines are also edges of the mesh. The mesh is simplified by repeated edge collapses, following the classical scheme introduced in previous works. For each edge of the mesh, the cost of its collapse is computed and inserted in an ordered heap of edges. The algorithm iteratively pops the edge collapse introducing the lowest error in the simplified mesh, checks for the validity of the collapse (i.e. geometry, topology or attribute consistency) and if this operation is accepted, update both the mesh and the heap. Since the polylines form a subset of the edges of the mesh, edge collapses modify both the mesh and the set of polylines embedded in the mesh. The main contribution of this paper is a robust validity algorithm, that detects whether or not an edge collapse preserves the topology of the mesh as well as the topology of the embedded polylines. To this end we define a so-called extended complex that implicitly encodes both topologies. Thereafter edge collapses that preserve the topology of this extended complex are detected. We show that these edge collapses preserve also both the topologies of the mesh and the embedded polylines. As we will see in this introduction, the preservation of these topological characteristics is crucial in several applications.

Many application areas may produce meshes with embedded polylines. This work has been motivated by three applications, for which the topology of the mesh and the topology of the embedded polylines must be preserved throughout the simplification.

Neuroscience

One of the great challenges of these years, in neuroscience, is to automate the brain mapping. As annotating brains is complicated and time consuming, neuroscientists are working on a unified atlas created from a collection of different brains which will later be use to directly transfer information to the patient. One method to map brains is to segment the cortical surface according to the main features (i.e. the gyri and the sulci) and to match these features. This segmentation produces polylines surrounding these features on the cortical surface. The topology of the polylines is simple: they form closed curves without self-intersections. Due to the high complexity of the surface, pre-processing needs to be done. Simplifiying the surface while preserving the main folds is one possible method. In this context it is critical to preserve the topology of the polylines and the mesh: the mesh should remain a manifold surface, and the polylines should remain closed curves without self-intersections.

Geology

Understanding the soil quality is fundamental for the agriculture or to estimate the health of the environment. Soil surveys are presented as maps encoding the proportion of each soil within a specific area. The boundaries of these domains are really important because they will be used to drive a specific land use (e.g. oil exploitation). In terms of visualization, data reduction is often used because of the difference between the area of interest (e.g. country) and the size of one soil type. While these data are characterized by a fairly simple surface representing a height field, embedded structures such as the boundaries among soil types can be really complex. It is crucial to preserve the topology formed by these boundaries in order to properly recover the different soil types in the simplified model. Also in a volume these layers of soils are creating multiple surfaces intersecting each oters which can be seen as a complex non-manifold surface. CAD/CAM CAD/CAM models are based on a geometry produced by a modeler and adapted to the design of a mechanical model. The hand-made geometry can be highly complex and features, such as materials, can be added to the mesh. In addition there is a coherence between the material interfaces and the geometric features that is important for the consistency of the whole CAD/CAM model. 2D Numerical simulations based on FEM (Finite Element Methods) on a CAD/CAM model produce a triangular mesh, possibly non-manifold, in which the edges follow the geometric features of the CAD/CAM model, as well as the interfaces separating the different materials. Preserving the topology of the polylines formed by these characteristic edges is essential to maintain the consistency of the CAD/CAM model throughout the simplification. This paper is structured as follows. Section 2 reviews related works, and points out differences with the present paper. Section 3 recalls the previously introduced topological tests for edge collapses in 2-complexes, as these results are used to detect valid edges in the extended complex. Section 4 explains how the extended complex is defined, and describes the actual implementation of the validity algorithm. Finally section 5 presents results in the different application areas cited above, and section 6 gives a conclusion with future works.

Related Work

Research on surface simplification in Computer Graphics and Scientific Visualization has led to a substantial number of methods within the last twelve years. An exhaustive description of this field is beyond the scope of this paper and one can refer to the many surveys [START_REF] Cignoni | A comparison of mesh simplification algorithms[END_REF][START_REF] Luebke | A developer's survey of polygonal simplification algorithms[END_REF][START_REF] Garland | Multiresolution modeling: Survey & future opportunities[END_REF] available. In the remainder of this section we only review the methods close to our work.

Surface Simplification

In order to decimate a discrete surface, different operators can be applied on its elements (i.e vertex, edges, faces). Historically started with region merging [START_REF] Haemer | Simplification of objects rendered by polygonal approximations[END_REF], numerous methods followed such as surface re-tiling [START_REF] Turk | Re-tiling polygonal surfaces[END_REF], vertex decimation [START_REF] Schroeder | Decimation of triangle meshes[END_REF], vertex clustering [START_REF] Rossignac | Multi-resolution 3d approximation for rendering complex scenes[END_REF], subdivision meshes [START_REF] Eck | Multiresolution analysis of arbitrary meshes[END_REF] or wavelet decomposition [START_REF] Gross | Efficient triangular surface approximations using wavelets and quadtree data structures[END_REF]. Amongst these decimation methods the local iterative edge collapse operator has been widely used in order to control precisely the simplification error. These methods highly depend on the metric used to determine the order of the modifications and many heuristics have been proposed depending on the application. Particularly relevant algorithms used progressive meshes [START_REF] Hoppe | Progressive meshes[END_REF], tolerance volumes [START_REF] Guziec | Surface simplification inside a tolerance volume[END_REF], plane deviations [START_REF] Ronfard | Full-range approximation of triangulated polyhedra[END_REF], quadric-based metrics [START_REF] Garland | Surface simplification using quadric error metrics[END_REF] or the memoryless simplification [START_REF] Lindstrom | Fast and memory efficient polygonal simplification[END_REF]. While this wide range of methods deal well this the geometry, models used in Computer Graphics or in Solid Modeling may have different non-geometric attributes defined on the surface which need to be preserved through the simplification process.

Attribute Preserving Simplification

Discontinuities are often observed in the non-geometric attribute field of a surface such as high color varitation due to shadows projected on a surface or texture coordinates defined on vertices. Attribute errors can be estimated on each face to compute an error-bounded simplification [START_REF] Bajaj | Error-bounded reduction of triangle meshes with multivariate data[END_REF], treated with dedicated datastructure such as wedges [START_REF] Hoppe | Efficient implementation of progressive meshes[END_REF] or integrated into the computation of a quadric error metric [START_REF] Garland | Simplifying surfaces with color and texture using quadric error metrics[END_REF]. [START_REF] Erikson | GAPS: general and automatic polygonal simplification[END_REF] tracks attribute variations by minimizing an error computed on point clouds defined by these field values. A Resampling of the attributes can also be used as in [START_REF] Cignoni | A general method for preserving attribute values on simplified meshes[END_REF], where a displacement map is computed on high resolution and applied as a texture on the simplifed mesh. [START_REF] Cohen | Appearancepreserving simplification[END_REF] dynamically computes a texture deviation metric used to decouple the sampling of the attributes and to ensure an error bound of the simplification. In some cases, attributes can describe geometric features of a surface but usually specialized structures and algorithms are required, especially when these features are defined in different dimensions.

Application Driven Simplification

Feature-guided simplification provides dedicated error metrics to integrate strong constrains on subsets of the original model such as intersection of roads on a terrain data. These metrics highly depend on the application because the definition itself of a feature is based on the field of study. Many methods have been proposed to extract a collection of piecewise linear curves on the surface [START_REF] Kass | Snakes: Active contour models[END_REF][START_REF] Rossl | Extraction of feature lines on triangulated surfaces using morphological operators[END_REF][START_REF] Hubeli | Multiresolution feature extraction for unstructured meshes[END_REF]. Once such features have been extracted, associated weights can be used to integrate them in any kind of error mesure previously presented like [START_REF] Rossl | Extraction of feature lines on triangulated surfaces using morphological operators[END_REF] which extends the quadric-based error metric of [START_REF] Garland | Surface simplification using quadric error metrics[END_REF]. User-guided simplification also provides specific error metrics to simplify chosen features.

Terrain Simplification is a stand-alone branch of the mesh simplification field as it has been studied for almost 30 years and has led to an incredible number of methods. Among others, [START_REF] Floriani | Multiresolution models for topographic surface description[END_REF][START_REF] Luebke | Level of Detail for 3D Graphics[END_REF] provide survey of this wide field. Several papers deal with the preservation of the topology of polylines on these terrains. However, due the nature of terrain data, they are restricted to height field meshes having a very simple topology. All these methods are either extension of the Douglas-Peucker [START_REF] Douglas | Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[END_REF] algorithm (which does not deal with the topology) for curve simplification or based on heuristics defined by the local topology around the polyline vertices.

Material boundaries are special properties of CAD-/CAM models. Preservation of the material interface through simplification in CAD/CAM applications has been mentioned in some previous works, including [START_REF] Gregorski | Multiresolution Representation of Datasets with Material Interfaces[END_REF] for volume data. In these cases, the interface is integrated in a scalar attribute such as a color and the global geometric appearance is maintained through simplifcation. Preservation of the topology of a scalar field and isosurfaces defined on this field, has been considered and guaranteed in several methods like [START_REF] Gerstner | Topology preserving and controlled topology simplifying multiresolution isosurface extraction[END_REF]. However, in our framework we are interested in preserving the topology of such properties defined for the model (i.e. patches of surfaces), for the material boundaries (i.e. subsets of the mesh edges) and for the intersections amongst boundaries (i.e. specific vertices of these boundaries). Existing methods lack a unique combinatorial validity test preserving the topology of all the elements defined in all dimensions lower or equal to 3.

Topology Preserving Simplification

Surface mesh simplification algorithms transform a general simplicial complex in another one. Edge collapse is the most used operator to remove sub-simplicies from the input because it allows to control efficiently and accurately the deformation introduced in the initial mesh. Some of these algorithms preserve the topology of the simplified mesh by investigating the organisation of the triangles around an edge leading to a certain number of cases. In some situations the edge collapse is rejected as it would introduce topological error [START_REF] Hoppe | Mesh optimization[END_REF]. A similar treatement can be done on feature lines based on local tests in between the edges around a collapse and the triangulation. However non-manifold surfaces can not be treated with this method and there is not an obvious extension to higher dimensions in contrast with our results, as pointed out in Section 6.

More recently, [START_REF] Dey | Topology preserving edge contraction[END_REF] has proven that the complex obtained after an edge collapse is homeomorphic to the first one if the neighborhood of the edge collapse satisfies the link condition. This result based on concepts of Computational Topology has been more and more used, even in volume simplification as it is not restrictived to 2-complexes. Especially, non-manifold surfaces can be treated with this method using the link condition.

Preserving the Topology of 2-Complexes

Appendix A recalls the basic definitions from combinatorial topology needed in the following sections. Given a simplicial complex, and an edge (a 2-simplex) in this complex, the problem of detecting if the collapse of this edge modifies the topology of the complex has been extensively studied in [START_REF] Dey | Topology preserving edge contraction[END_REF]. For 2-and 3-complexes, necessary and sufficient conditions have been developed, ensuring that a continuous one-to-one mapping between the complex before edge collapse and the complex after edge collapse exists. These conditions are slightly more restrictive than topology preservation since the mapping is required to be the identity outside a neighbourhood of the edge being contracted. In this section we state the results developed in [START_REF] Dey | Topology preserving edge contraction[END_REF] for 2-complexes, as they will be used later in this paper. The reader is referred to the original paper for details.

Order of a Simplex in a 2-Complex

The order of a simplex τ in a complex K measures the topological complexity of the neighbourhood of τ in K. It is denoted by ord τ . For a 2-complex, the order of simplices may be 0, 1 or 2. A simplex τ has an order 0 if St τ is homeomorphic to an open disc. This is the simplest case, where locally the complex is a 2-manifold. The order is 1 if St τ is homeomorpic to p triangles sharing a common edge with p = 2. This is for example the case for non-manifold edges and boundary edges. In all other cases the order of the simplex is 2. Note that all triangles have order 0, and that edges may have order 0 or 1 only. Figure 1 (a) illustrates the order of vertices and edges in a 2-complex.

Fig. 1 (a) Order of simplices in a 2-complex: the green vertex has order 0, black vertices have order 1, yellow vertices order 2, black edges order 0, yellow edges order 1, all triangles have order 0. (b) shows the edges and vertices in the first boundary of the 2-complex shown in (a). The two yellow vertices form the second boundary of this complex.

Boundaries of a 2-Complex

The topological tests rely on a generalized notion of a boundary. The j-th boundary in a 2-complex K is defined as the set of all simplices with order j or higher:

Bd j K = {τ ∈ K|ord τ ≥ j}.
The 0-th boundary of K is K. Figure 1 (b) illustrates the first and second boundaries of a 2-complex. Note that the first boundary contains not only the usual boundary edges, but also non-manifold edges adjacent to three triangles or more. Since only vertices may have order 2, the second boundary of a 2-complex is always a set of vertices.

Topological test

Let ω be a dummy vertex, define

K ω = K ∪ (ω • Bd 1 K) and G ω = Bd 1 K ∪ (ω • Bd 2 K).
See Appendix A for the definition of the cone ω • T , where T is a set of simplices. Let Lk ω 0 τ and Lk ω 1 τ denote the link of τ in K ω and G ω respectively. With all these definitions at hand, one can now state the main result of [START_REF] Dey | Topology preserving edge contraction[END_REF] for 2-complexes.

Topological Test:

Theorem 1 Let K be a complex and L be the complex obtained by contracting the edge uv in K. The following two conditions ensure that L has the same topology as K:

(i) Lk ω 0 u ∩ Lk ω 0 v = Lk ω 0 uv (ii) Lk ω 1 u ∩ Lk ω 1 v = ∅.
Conditions (i) and (ii) are illustrated in Figure 2 for a non-manifold edge.

Topology Preserving Edge Collapse With Embedded Structures

Let K be a 2-complex and E be a set of edges in K. The closure E of E is a collection of edges and vertices that may be viewed as a set of several polylines embedded in K, with possible self intersections. These polylines together with the polylines formed by all boundary and non-manifold edges of K define a 1-complex F = E ∪ Bd 1 K, whose topology is an important characteristic of the data, and should be preserved. Contracting edges in K possibly modifies both the topology of K and the topology of F . Our goal is to develop a robust test to detect which edge collapse preserves the topology of the 2-complex K together with the topology of the polylines embedded in K. The key idea of the paper is to implicitly encode the topology of the polylines F and of the embedding complex K in a single extended 2-complex K. Thereafter the topological test developed in [START_REF] Dey | Topology preserving edge contraction[END_REF] (see Section 3) can be used to select the valid edge collapses in the extended 2-complex K. K is built in such a way that valid edge collapses in K preserve the topology of both K and the embedded polylines F .

Implicitly Encoding the Topology of the Embedded Structures

We can assume that the collection of edges E contains only order 0 edges, without changing F : if there is an order 1 edge in E, it is also in Bd 1 K. The extended complex K is built by adding to K the cones from the dummy vertex ω to each edge in E. More precisely:

K = K ∪ w.E
In other words, the embedded edges are extended to a 2D sub-complex of the extended complex K. Figure 3 illustrates an extended complex with two intersecting embedded polylines. The extended complex K is defined such that its first boundary equals F .

Lemma 1 Bd 1 K = F

Proof An edge in E has an order 0, i.e. it has exactly 2 adjacent triangles in K, and three adjacent triangles in K. Thus it has an order 1 in K. An edge of order 1 in K ω Fig. 3 Extended complex: the extended complex is defined by adding to the mesh all edges and faces connecting a dummy vertex ω with the vertices and edges of the embedded polylines.

is not in E, therefore it has the same star in K and K, and is still of order 1 in K. Thus we have F ⊂ Bd 1 K. Now let e be an edge of order 1 in K. e has one or three or more triangles in its star. If e has only one triangle in its star, it is in the boundary of K. If it has three or more triangles in its star, it is either a non-manifold edge of K, or an edge in E. Thus we have also Bd 1 K ⊂ F . Lemma 1 means that the topology of the embedded structure F is encoded implicitly in the extended complex K. An edge contraction in K corresponds to an edge contraction in K. After an edge contraction, the modified set of polylines F can be retrieved as the set of edges facing the dummy vertex ω in a triangle. The following Lemma applied to the extended complex K, proves that if an edge contraction preserves the topology of K, it also preserves the topology Bd 1 K, i.e. it also preserves the topology of the modified set of polylines F , since Bd 1 K = F from Lemma 1.

Lemma 2 Let K be a 2-complex and (uv) be an edge in K such that (i) and (ii) are satisfied. Then the contraction of (uv) preserves the topology of Bd 1 K.

Proof Let M = Bd 1 K, and M w = Bd 0 (M ) ∪ ω • Bd 1 (M ). M is a 1-complex: it is the closure of the set of order 1 edges in K. Since M is a 1-complex, it is sufficient to show that there is no vertices in the intersection of the links of u and v in M w . Since Bd 1 M = Bd 1 (Bd 1 K) ⊂ Bd 2 K, any vertex in the link of u (resp. v) in M w , is also in the link of u (resp. v) in G ω . Therefore condition (ii) implies the lemma.

Implementation of the Topological Preservation Test

In this section we describe the actual implementation of the algorithm that detects if an edge e = (u, v) can be collapsed without changing the topology of the surface nor the topology of any polyline defined on the triangle edges.

1. Initialisation: Set up local variables in the neighborhood of the 2 vertices u and v of the edge e. For each edge e i adjacent to u or v, add dummy triangles (ω•e i ) if e i is either on a polyline or in the first boundary of the mesh. This amounts to locally computing the extended complex.

2. Compute the vertices in Lk ω 0 u: Loop through the edges e i adjacent to u in the extended complex. For each edge e i , store the vertex facing u in Lk ω 0 u. In some cases the opposite vertex is the dummy vertex ω if the edge is in a polyline, or in the first boundary of the mesh. This case is implicit and it is not treated explicitly as the neighborhoods of u and v have been triangulated by adding dummy cells using the dummy vertex ω.

Compute the edges in Lk ω

0 u: Loop through the faces f i adjacent to u in the extended complex. For each face f i , store the edge facing u in Lk ω 0 u. Figure 4 illustrates the computation of the link around a non-manifold vertex.

Applications and Results

We have applied our topology preserving simplification algorithm on a wide range of datasets. The error measure used in all examples to sort the edges in the heap is a simple weighted combination taking into account the maximal normal deviation of the faces and the polyline's edges, before and after collapse. This simple error measure gives already satisfactory results, but we insist on the fact that our algorithm can be combined with any error measure. All simplifications run at about 20000 removed edges per second on a 1.7Ghz Pentium M laptop.

In the following section, all decimation percentages are taken from the original number of triangles in the mesh. The first paragraph shows an neuroscience application involving a complicated surface geometry but with a really simple feature line topology. Then a CAD/CAM application is presented illustrating both a complicated geometry and feature line topology. Finally, geological data allow us to validate our method with a simple geometry but an extremely complex polyline topology.

Geology Data with Non-manifold Models As our edge collapse criteria for preserving topology is valid for 2-complexes, non-manifold models can directly be simplified with the same topological test. Figure 5 shows the simplification of geological data. Several layers separating different soil type create a non manifold surface. Linear features are present in the model which give a specific information on a subset of the data and thus need to be handle in the simplification process. Even with a high simplification ratio of 95%, the topology of the nonmanifold surface is preserved as well as the linear features embedded on the triangle edges. Note that several polylines are crossing a non-manifold region which leads to a vertex of order two which is successfully preserved after the collapses.

Neuroscience

We have applied our simplification algorithm on a triangle mesh extracted from MRI data and segmented according to the sulci and the gyri (Figure 6). Thus we were able to generate a low resolution mesh while preserving its main features: the mesh remains a manifold surface, and the polylines remain closed curves without self-intersections. The close-up view shows the effect of the simplification on a feature. Note that the boundaries are preserved despite the reduction of vertices along them. As many features can be small and close to each other, allowing the collapse of edges around and along the boundaries is essential to keep the simplification rate low. features are removed through the simplification (i.e it would introduced a topological modification of the polylines).

Conclusion

This paper has introduced a new topology preserving simplification algorithm, based on edge collapse, for nonmanifold triangular meshes with embedded polylines. The

Fig. 2

 2 Fig. 2 Topological test for an edge e=(u,v): the left and right parts illustrate respectively the first and second conditions. Left part: Lk ω 0 u contains the yellow and red vertices and the yellow edges, Lk ω 0 v contains the green and red vertices and the green edges, Lk ω 0 e contains the red vertices: the first condition is fulfilled. Right part: Lk ω 1 u contains the three yellow vertices, Lk ω 1 v contains the two green vertices, the intersection is empty: the second condition is fulfilled.

Fig. 4

 4 Fig.[START_REF] Cohen | Appearancepreserving simplification[END_REF] Link of a non-manifold vertex on the intersection of several surfaces (lef t). Link of a vertex on the intersection of several polylines. In the extended complex, dummy triangles are added from the segment polylines modifying the link of the vertex as shown (right).

4 .

 4 Compute Lk ω 0 v: The exact same process is applied around v in order to compute Lk ω 0 v. 5. Compute Lk ω 0 e: Loop through the faces f i adjacent to e in the extended complex. For each face f i , store the vertex facing e in Lk ω 0 e. 6. Compare Lk ω 0 u ∩ Lk ω 0 v and Lk ω 0 e: The intersection of Lk ω 0 u and Lk ω 0 v is computed. If this intersection contains an edge, the edge collapse is rejected, as Lk ω 0 e contains only vertices. Compare the number of vertices in Lk ω 0 u ∩ Lk ω 0 v with the number of vertices in Lk ω 0 e. The edge collapse is rejected if these numbers are not equal. It is sufficient to compare the number of vertices, and not the actual indices of the vertices, since in any case the vertices in Lk ω 0 e form a subset of the vertices in Lk ω 0 u ∩ Lk ω 0 v. 7. Compute Lk ω 1 u: Loop through the edges e i adjacent to u and in the first boundary of the extended complex. For each edge e i store the vertex facing u in Lk ω 1 u. Note that if u is in the second boundary of the mesh, then the edge (ω, u) is in G ω (more precisely in (ω • Bd 2 K)) and thus the dummy vertex ω is in Lk ω 1 u. 8. Compute Lk ω 1 v: The exact same process is applied around v computing the Lk ω 1 v.

Fig. 5

 5 Fig. 5 Geological data showing several surfaces separating different soil types. Linear features are present in the data for cetain layers. This set of interfaces among soil type creates non-manifold surfaces.

9 .

 9 Compute Lk ω 1 u ∩ Lk ω 1 v: The intersection of Lk ω 1 u and Lk ω 1 v is computed. If this intersection is not empty then the edge e is rejected for collapse as the second link condition breaks. 10. Accept collapse of e: If the edge e has not been rejected in previous steps, it can now be contracted. The dummy cells introduced in the first step are removed.

Fig. 6

 6 Fig. 6 Segmented surface of a human Cortex. The sulci and gyri of the cortex (i.e. main features) are preserved by the simplification.

Fig. 7 Fig. 8

 78 Fig. 7 CAD/CAM model of a piston simplified by preserving its material properties.

topology of the polylines as well as the mesh is preserved throughout the simplification using a unified and robust validity algorithm to select edges that can be collapsed.

Our algorithm is based on powerful combinatorial topology results, and can be applied to general triangular meshes, including non-manifold meshes. The idea of the extended complex, encoding implicitly the topologies of the mesh and the polylines in a unified way, is at the heart of our results. One of the main appeal of this idea is its possible extension to 3-complexes. We are currently working on it, in order to generalize this concept to tetrahedral meshes with embedded 2D and 1D structures. Appendix A A n-simplex τ is the set of convex combinations of n +1 affinely independent points called the vertices of τ . A simplex η whose vertices are a subset of the vertices of τ is called a face of τ . This is denoted η ≤ τ or τ ≥ η. If η is a face of τ then τ is called a coface of η. A complex K is a collection of simplices such that:

(i) if τ ∈ K then all faces of τ are also in K.

(ii) if η, τ ∈ K then η ∩ τ is empty or a face of η and τ .

The star, the closure and the link of a set of simplices T in a complex K are denoted respectively St (T ), T , Lk (T ), and defined by:

If τ is a simplex and ω is a point affinely independant of the vertices of v 1 , • • • , v n of τ then the cone from ω to τ is denoted by ω • τ and defined as the simplex with vertices ω, v 1 , • • • , v n . If T is a set of simplices, then the cone from ω to T is the union of the cones from ω to τ , with τ ∈ T . It is denoted by ω • T .