Samuel Peltier

Pascal Lienhardt

Simploidal Sets: a data structure for handling simploidal Bézier spaces

come

Introduction

The design of complex free form objects is an important issue in Geometric Modeling. We are interested in representation models and basic operations for constructing sketches of complex subdivided objects, from which the final geometric object can be obtained by applying techniques of subdivision, deformation and others (e.g. [START_REF] Escobar | A new approach to solid modeling with trivariate t-splines based on mesh optimization[END_REF][START_REF] Zeng | Hybrid volume completion with higher-order bézier elements[END_REF]).

In this context, the complexity lies in the types of cells and the way they are glued together. Many works deal with the definition of geometric models of complex cells, mainly for low dimensions (e.g. [START_REF] Várady | Enhancement of a multi-sided bézier surface representation[END_REF]). Among models defined for higher dimensions, simploids are complex cells which structures correspond to cartesian products of simplices [START_REF] Dahmen | On the linear independence of multivariate b-splines I. Triangulation of simploids[END_REF]. Different models have been defined for representing unstructured meshes (for instance taking into account the refinement process [START_REF] Untereiner | CPH: A compact representation for hierarchical meshes generated by primal refinement[END_REF]). Well known combinatorial structures as simplicial and cubical sets [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] May | Simplicial Objects in Algebraic Topology[END_REF][START_REF] Serre | Homologie singulière des espaces fibrés[END_REF][START_REF] Brown | On the algebra of cubes[END_REF] can be used for representing sketches of subdivided objects. More recently, semi-simploidal sets1 [START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF] have been defined for representing assemblies of Bézier simploids [START_REF] Dahmen | On the linear independence of multivariate b-splines I. Triangulation of simploids[END_REF]. As a cube is the cartesian product of edges (i.e. 1-dimensional simplices), a simploid is the cartesian product of (any) simplices. Simplices and cubes are then simply particular simploids, so all these cells can be handled together using semi-simploidal sets. For example, Figure 1 illustrates an assembly of 3 simploids: a cube and a tetraedron are linked through a prism. This can be interesting for several applications, e.g. related to meshes. Structural relations between semi-simploidal sets and Bézier simploids make it possible to efficiently implement simploidal Bézier spaces using semi-simploidal sets.

When defining a geometric model, it is also important to provide basic operations from which higher-level operations can be designed. Cone and identification (i.e. the merging of cells) are the basic operations associated with simplicial structures, as extrusion and identification are the basic operations associated with cubical structures 2 . Since simploids generalize simplices and cubes, the three operations: cone, cartesian product and identification have to be their associated basic operations. Unfortunately, the cone operation is not defined for semi-simploidal sets.

In order to solve this problem, a new combinatorial structure, namely simploidal sets is defined (cf. Definition 1 page 10), for representing any assembly of simploids, and any simploidal set can be constructed by applying cone, cartesian product and/or identification. Moreover, another operation, degeneracy, is also defined, due to the definition of simploidal sets.

In order to associate simploidal Bézier spaces with simploidal sets, the structural relations between them has to be stated: we first establish this relation for simplicial sets and simplicial Bézier spaces, and then it is generalized for simploidal sets. As a consequence, simploidal Bézier spaces can be efficiently implemented using simploidal sets (cf. Section 4.3): control points can be stored without any redundancy, avoiding problems related to space complexity and possible inconsistencies.

Basic construction operations and topological properties computations can be efficiently implemented, since all the necessary structural information as adjacency and incidence relations between simploids is explicitly represented.

Regarding implementation issues, since the definition of simploidal sets is very close to that of simplicial and cubical sets, the additional cost is very low, with respect to space (cost of data structure), time (cost of operations) or software development (cf. Section 4).

So, the main contributions of this paper are:

• the definition of simploidal sets;

• Property 1, which establishes the precise structural relations between simplicial sets and the control points of triangular Bézier spaces; and Property 2, which extends Property 1 for simploidal sets;

• a data structure implementing simploidal Bézier spaces;

• definitions and algorithms for all basic construction operations: cone, cartesian product, identification and degeneracy (cf. Section 4.4), generalizing the basic construction operations defined for simplicial and cubical sets.

• a comparison with supercomplexes, a "similar" combinatorial structure, proposed by Gugenheim in 1957 for the study of topological properties [START_REF] Gugenheim | On supercomplexes[END_REF] (cf. Theorem 4).

Note that cone and identification operations are defined on semi-simplicial sets, and that simplicial sets extend them so that the cartesian product operation can be defined. Conversely, cartesian product and identification are defined on semi-simploidal sets, and simploidal sets extend them so that the cone operation can be defined. It has to be noticed that the way for deducing simploidal sets from semi-simploidal sets is similar to the way for deducing simplicial sets from semi-simplicial sets, and lies in the fact that simploids (or simplices) can be degenerate ones.

As a consequence, it is possible to represent more general simploids with simploidal sets than with semi-simploidal sets, and this versatility can be of interest for geometric modeling purposes.

It is shown that the simploidal framework is general, coherent and homogeneous, since it contains also the simplicial and cubical sets frameworks as particular cases.

At last, these structures are designed for representing any assembly of cells (e.g. unstructured meshes), so they can be quite space consuming: this is the reason why they are generally employed for the design of sketches of complex geometric objects. But note that the representation can be optimized by applying usual optimization or compression techniques [START_REF] Maglo | 3d mesh compression: Survey, comparisons, and emerging trends[END_REF].

(0) (1) (2)
(3) (2,1)

(1,1) The outline of the paper is the following. For clarity purpose, all necessary notions are presented in a progressive way: notions related to structures without degeneracy operators, namely semi-simplicial, semi-cubical and semi-simploidal sets, are recalled in Section 2. These three structures handle abstract cells (i.e. simplices, cubes and simploids) equipped with face operators associating with an i-dimensional cell the (i -1)-cells of its boundary. Simploids generalize simplices and cubes: as a simplex or a cube is characterized by its dimension, a simploid is characterized by its type (a 1 , • • • , an) (cf. Figure 1(a)): intuitively, a simploid can be seen as the cartesian product of simplices σ 1 × • • • × σn, and a i is the dimension of σ i . So, n-simplices and n-cubes are particular simploids of types (n) and (a 1 = 1, • • • , an = 1). Note that these structures allow the representation of any assembly of simplices, cubes, or simploids. Regarding basic construction operations, cartesian product and identification can directly be defined for semi-simploidal sets, but the cone operation can not (cf. Figure 1(b)).

(1,1,1) (a) (b) (c)
Section 3 focusses on simplicial and cubical sets, which extend semi-simplicial and semi-cubical sets by adding degeneracy operators. The precise relations with Bézier spaces are established.

Simploidal sets are defined in Section 4, by adding degeneracy operators. The relations with simploidal Bézier spaces are established, and a data structure avoiding any redundancy for Bézier embedding is proposed. All basic simplicial and cubical construction operations are extended within the simploidal framework: cone, cartesian product, identification, and degeneracy, and it is shown that the simploidal cone operation can be defined in a simple way thanks to degeneracy operators. So, simploidal sets generalize and homogenize simplicial and cubical sets.

Structures Without Degeneracy

N-dimensional simplicial "objects" or "triangulations" have been studied for a long time in Algebraic Topology. Combinatorial structures, as abstract simplicial complexes or simplicial sets, describe the adjacency and incidence relations of abstract simplices, and a geometric realization can be associated with each structure. For instance, the geometric realization of an abstract simplicial complex is a simplicial complex, whereas the geometric realization of a simplicial set is a CW-complex [START_REF] Agoston | Algebraic Topology, a first course[END_REF][START_REF] May | Simplicial Objects in Algebraic Topology[END_REF][START_REF] Munkres | Elements of algebraic topology[END_REF][START_REF] Massey | A basic course in algebraic topology[END_REF]. Such structures are used for different purposes, in Computational Topology (e.g. computation of topological properties) [START_REF] Edelsbrunner | Computational Topology -an Introduction[END_REF][START_REF] Rubio | Constructive homological algebra and applications[END_REF][START_REF] Dumas | Computing simplicial homology based on efficient smith normal form algorithms[END_REF], Geometric Modeling, CAD/CAM and Computer Graphics (e.g. representation of subdivided geometric objects, meshes) [START_REF] Paoluzzi | Dimension-independent modeling with simplicial complexes[END_REF][START_REF] Frey | Mesh Generation: application to finite elements[END_REF], etc. In particular, structural relations between semi-simplical sets and triangular Bézier spaces [START_REF] Farin | Curves and Surfaces for CAGD: A Practical Guide[END_REF] have been established [START_REF] Lang | Simplicial sets and triangular patches[END_REF], leading to the definition of efficient data structures for handling triangular Bézier spaces.

N-dimensional cubical "objects" have been studied [START_REF] Serre | Homologie singulière des espaces fibrés[END_REF][START_REF] Brown | On the algebra of cubes[END_REF] for similar purposes in Topology, Geometric Modeling, etc. So, semi-simplicial, semi-cubical and semi-simploidal sets [START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF] describe sets of (products of) simplices, such that any assembly of cells can be represented. This section is mainly based upon the papers [START_REF] Lang | Geometric modeling with simplicial sets[END_REF][START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF], in which algorithms implementing basic operations for handling semi-simplicial sets and semi-simploidal sets are also described.

Semi-Simplicial Sets

Combinatorial structure. Most well-known triangulated objects are simplicial complexes [START_REF] Agoston | Algebraic Topology, a first course[END_REF], which are sets of geometric simplices satisfying some properties, a i-dimensional simplex (or i-simplex) being the convex hull of i + 1 linearly independent points. The corresponding combinatorial structure is also well-known: an abstract simplicial complex is a set of abstract simplices, and an abstract i-simplex is a set of i + 1 (abstract) vertices.

A n-dimensional semi-simplicial set (or ∆-complex) [START_REF] Eilenberg | Semi-simplicial complexes and singular homology[END_REF][START_REF] Hatcher | Algebraic Topology[END_REF]

S = (K, (d j )) is a family of sets K = (K i ) i∈[0.
.n] , such that each K i is equipped with face operators: d j : K i → K i-1 for 1 ≤ i ≤ n and 0 ≤ j ≤ i; the face operators satisfy "commutation properties": for σ ∈ K i , and 0 ≤ l < j ≤ i, σd j d l = σd l d j-1 , where σd j d l denotes d l • d j (σ). K i is the set of i-dimensional (abstract) simplices (or i-simplices); the i + 1 face operators defined for a i-simplex σ associate with σ the (at most) i + 1 (i -1)-simplices of its boundary. Intuitively, if σ is assimilated with a sequence

(v 0 , • • • , v j , • • • , v i ) of i + 1 vertices, σd j corresponds to the sequence (v 0 , • • • , v j-1 , v j+1 , • • • , v i ).
More generally, the "commutation properties" involve that at most i+1 j+1 j-simplices belong to the boundary of a i-simplex. Semi-simplicial sets generalize abstract simplicial complexes, since the definition of a simplex boundary through face operators permits to handle i-simplices which are incident to less than (i + 1) vertices (cf. Figure 2); moreover, simplices are not necessarily linearly embedded (cf. below).

Let σ be a i-simplex; σd j is its j th -face. Simplex τ is a face of σ if it can be obtained from σ by applying a non-empty sequence of face operators. The boundary of σ is the subset of S restricted to the faces of σ. The star of σ is the set of simplices of which σ is a face. σ is a main simplex if its star is empty. The boundary of a complete i-simplex contains exactly (i + 1) 0-simplices. For example in Figure 2(b): y and b are faces of m; the boundary of n contains the simplices {a, g, f, v, w}; the star of w is the set {f, g, a, c, e, n, m}; m,n and e are the main simplices; all simplices but n and g are complete. This terminology can be extended in a straightforward way for all structures described in this paper. Triangular Bézier spaces and relation with semi-simplicial sets. As abstract simplicial complexes can be associated with simplicial complexes, semi-simplicial sets can be associated with triangular Bézier spaces. A triangular Bézier space is a set of Bézier simplices satisfying some conditions (see [START_REF] Farin | Curves and Surfaces for CAGD: A Practical Guide[END_REF]).

More precisely, the set Γ i d of i-dimensional multi-indices of degree d is defined by

Γ i d = {α = (α 0 , • • • , α i ) ∈ N i+1 | |α| = α 0 + • • • + α i = d}. In the following, multi-index (α 0 , • • • , α i ) is denoted α 0 • • • α i . For instance, Γ 1 3 = {03,
(u) = d α u α 0 0 • • • u α i i , with α ∈ Γ i d , and d α = d! α 0 !•••α i !
are multinomial coefficients, and {u j } are the barycentric coordinates of u, a point of the standard i-simplex, i.e. {u j } satisfies: ∀j, 0 ≤ j ≤ i, 0 ≤ u j ≤ 1 and i j=0 u j = 1. A Bézier i-simplex of degree d is defined by

P (u) = α∈Γ i d PαB d α (u)
, where {Pα, α ∈ Γ i d } is its set of control points (cf. Figure 3), which can be stored in a simplicial array, according to the lexicographical order of the multi-indices [START_REF] Derose | Functional composition algorithms via blossoming[END_REF]. The index in a simplicial array of any control point Pα can be retrieved using algorithm 1. The idea is the following: let α = α 0 . . . α i be the multi-index of a control point. If i = 1 then the point is stored at index α 0 . If i > 1, then it is necessary to store first α 0 sets of control points corresponding to (i -1)-dimensional Bézier simplices of degrees decreasing from d to d -α 0 + 1, and then to store the point in the same way as if it would belong to the set of control points of a (i -1)-dimensional Bézier simplex of degree d -α 0 .

Algorithm 1: multiIndex2Index

Input : α = α 0 • • • α i : MultiIndex Γ i d Output: pos : Integer if i == 1 then pos = α 0 ; else offset = d j=d-α 0 +1 | Γ i-1 j |; pos = offset + multiIndex2Index(α 1 • • • α i );
return pos; A triangular Bézier space can easily be implemented by a set of simplicial arrays, such that each simplicial array contains the control points of a main Bézier simplex. Several construction operations as cone and identification (cf. operations below) can be easily implemented for handling this data structure. But all simplices are not explicitly represented, nor adjacency and incidence relations. So, such a structure is not well suited for implementing several operations, for instance the computation of topological properties as homology. Moreover, the control points which are "shared" by adjacent main simplices are duplicated. For example in figure 3(b), the control points surrounded by dashed lines have to be the same.

More efficient data structures can be defined, based upon the following relation between triangular Bézier spaces and semisimplicial sets. It is well known that a Bézier i-simplex β contains its boundary, i.e. the boundary of β is a set of lower dimensional Bézier simplices defined by subsets of control points of β. More precisely, all control points Pα of β such that the j th component of α is 0 define a (i -1) Bézier simplex. For instance in Figure 3(b), the points numbered 003, 102, 201, 300 of each triangle define a Bézier curve of degree 3. So, the following constraint has to be satisfied in order to represent a triangular Bézier space: let σ be a i-simplex, 1 ≤ i, and µ = σd j , for 0 ≤ j ≤ i; let P = Pα 0 •••α j •••α i be a control point of σ such that α j = 0; then point

P α 0 ••• α j •••α i of µ is equal to P , where α j means α j is removed.
Consequently, a data structure can be defined, based upon semi-simplicial sets, such that any simplex is associated with its proper control points, i.e. control points Pα such that no component of α is null (cf. Figure 3(c)). The set of proper control points of an i-simplex of degree d has the structure of a i-simplex of degree d -(i + 1), and thus contains d-1 i control points. This set can be stored in a simplicial array as before, by using the lexicographical order of multi-indices.

The set of all control points of a simplex can be retrieved from its proper control points and from the control points of the simplices of its boundary, by taking into account the face operators indices. For instance, let σ be a triangle of Figure 3(c In this SemiSimplicialSet data structure, it is assumed that all Bézier simplices of a given Bézier space have the same degree, allSimplices gives access to the lists of i-simplices, 0 ≤ i ≤ dim, where dim is the dimension of the set.

Regarding the Simplex structure, dim is its dimension, faceOps gives access to the (dim-1)-simplices of its boundary, set gives access to its semi-simplicial set and ctrlPoints stores its proper control points, ordered by lexicographical order. Algorithm 3 can be used to deduce which proper multi-index α is stored at index pos by computing firstly α = index2M ultiIndex(i, d-(i+1), pos), and then α is obtained by adding 1 to each α j , 0 ≤ j ≤ i.

Algorithm 3: index2MultiIndex

Input : i, d, pos : integer /* i is the dimension, d is the degree, and pos the index */ Output: α:

MultiIndex of Γ i d Algorithm 2: index2MIrec Input : i, d, pos, j : integer Output: α = α 0 , • • • , α i : MultiIndex of Γ i d if i == 1 then α 0 = pos; α 1 = d -pos; else offset = i+d-j-1 i-1 ; if pos <= of f set -1 then α 0 = j; α 1 • • • α i =index2MIrec(i-1,d-j,pos,0 ); else α=index2MIrec(i,d,pos-offset,j+1 );
return α; return index2MIrec(i,d,pos,0 ); Data structure variants. Obviously, this structure can be adapted for handling Bézier simplices with different degrees, using for instance well-known results about degree elevation for controling the continuity [START_REF] Farin | Curves and Surfaces for CAGD: A Practical Guide[END_REF]. A list of accesses can be added for any i-simplex, in order to access the (i + 1)-simplices of its star.

Basic Operations. Any semi-simplicial set S can be constructed by applying two basic operations, namely cone and identification [START_REF] Lang | Geometric modeling with simplicial sets[END_REF].

The cone of S consists in adding a 0-simplex v to S, and in creating a new (i + 1)-simplex µ incident to σ and v for any i-simplex σ of S (cf. Figure 4). The proper control points of µ can be computed for instance by linear interpolation between the proper control points of σ and the control point associated with v. Note that a complete i-simplex (with its boundary) is a cone upon a complete (i -1)-simplex (with its boundary). The identification operation can be applied to two distinct i-simplices σ and τ , if they share the same boundary. The operation consists in replacing σ and τ by a new i-simplex µ such that its boundary is equal to the boundary of σ (and τ ), and its star is the union of the stars of σ and τ . More precisely, if νd j = σ or νd j = τ before operation, then νd j = µ after operation. For instance, the semi-simplicial set of Figure 2(b) can be obtained from the one of Figure 2(a) by identifying 0-simplices v1 and v2, 0-simplices w1, w2 and w3, and 1-simplices a1 and a2. As for the cone operation, the proper control points of new simplices can be computed for instance by linear interpolation of the proper control points of the identified simplices.

Higher-level construction operations have been defined: for instance, any two i-simplices can be identified, by first identifying their boundaries by increasing dimensions, then by identifying the i-simplices themselves. See also the identification of subsets of simplices, split operation, flip operation, etc. [START_REF] Bechmann | Informatique graphique, modélisation géométrique et animation[END_REF]. Operations for computing topological properties, as homology, have also been defined [START_REF] May | Simplicial Objects in Algebraic Topology[END_REF].

Semi-Cubical Sets

A n-dimensional semi-cubical set S = (K, (d i j )) is a family of sets K = (K p ) p∈[0.

.n] together with face operators: An element σ of K p is a p-cube. Intuitively, a p-cube is the cartesian product of p 1-simplices σ 1 × . . . × σ i × . . . × σp, and face operator d i j associates σ with the (p -1)-cube corresponding to σ 1 × . . . × σ i d j × . . . × σp (cf. Figure 5). Note that the cartesian product of a p-cube by a vertex is a p-cube.

d i j : K p → K p-1 satisfying commutation properties: for 1 ≤ p ≤ n, 1 ≤ i ≤ p and j ∈ {0, 1}, d i j d k l = d k l d i-1 j if k < i.
A Bézier patch is the product of Bézier curves, a cubical Bézier space is a set of Bézier patches satisfying some conditions, and the correspondence described above between semi-simplicial sets and triangular Bézier spaces is retrieved here for semi-cubical sets and cubical Bézier spaces (cf. Figure 5). Note that the degrees of the generating edges can be different, and that the control points of a i-dimensional patch are denoted by i-tuples of 1-dimensional multi-indices. Note that a generating edge of degree d contains d-1 proper control points, so a i-cube obtained from i edges of degrees d Any semi-cubical set can be constructed by applying two basic operations: extrusion and identification. Extrusion is the particular case of the cartesian product by a 1-simplex (and its boundary); note that any complete p-cube can be constructed by the extrusion of a complete (p -1)-cube. Two cubes can be identified if their boundaries are equal, and if their control points have the same structure. Obvioulsy, higher-level operations have been defined: identification and cartesian product of semi-cubical subsets, split, homology computation, etc.

Semi-Simploidal Sets

Combinatorial Structure. A semi-simploidal set is a set of simploids on which act face operators (cf. Figure 6). In fact, semi-simploidal sets generalize semi-simplicial and semi-cubical sets, according to the intuitive fact that a simploid is the cartesian product of simplices of any dimensions. So, a simploid σ is characterized by its type (a 1 , . . . , an). Intuitively, a i is the dimension of its i th generating simplex, and a i > 0 for any 1 ≤ i ≤ n since the cartesian product by a vertex is the identity. The face operator d i j associates with σ the same product of simplices, except that the i th component is replaced by its j th face. So, the type of

σd i j is (a 1 , • • • , a i -1, • • • , an) if this j th face is not a vertex, (a 1 , • • • , a i-1 , a i+1 , • • • , an) otherwise.
For example in Figure 6, let σ = µ × τ be the simploid of type (2, 1), µ be the 2-simplex and τ the 1-simplex. Simploids σd 1 j (resp. σd 2 j ) are faces of type (1, 1) (resp. (2)) as it corresponds to the simploids µd j × τ (resp. µ × τ d j ).

The formal definition of semi-simploidal sets is not provided here (cf. [START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF]), it can be retrieved by keeping only (I)-1 and (II) from definition 1 of simploidal sets (cf. Section 4). Note that the definitions of semi-simplicial sets and semi-cubical sets can also be retrieved from definition 1 by keeping only (I)-1 and (II), and by considering i-simplices as simploids of type (i), and i-cubes as simploids of type (a 1 = 1, . . . , a i = 1).

Bézier Embedding. A simploidal Bézier space is a set S of Bézier simploids such that the intersection of any two simploids σ and τ of S is either empty or a simploid of S, corresponding to a common face of σ and τ . A Bézier simploid of type (a 1 , . . . , an) and degree (d 1 , . . . , dn) is defined by: For clarity purpose, only a part of its boundary is displayed and some of its control points are displayed in c).

P (u 1 , . . . , u n ) = α 1 ∈Γ a 1 d 1 . . . α n ∈Γ an dn P (α 1 ,...,α n ) B d 1 α 1 (u 1 ) × . . . × B dn α n (u n ) where any u i is a point of the standard a i -simplex and {P (α 1 ,••• ,α n ) } is its set of control points.
As before, a correspondence exists between the semi-simploidal set structure and the structure of n-tuples of multi-indices: cf. Figure 6. This correspondence makes it possible to associate its proper control points with any simploid, and to retrieve all control points (and their tuples of multi-indices) of a simploid from its proper control points and the proper control points of the simploids of its boundary, using the numbering of the face operators.

Algorithm 4: index2TupleMultiIndex

/* Returns the pos th tuple of multiIndex of

Γ i 1 d 1 × • • • × Γ i k d k according to the lexicographical order. */ Input : type = [(i 1 , d 1 ), • • • , (i k , d k )] : List< (Integer, Integer) > ; pos : integer Output: α = (α 1 , • • • , α k ) : k-tuple of multi-index if (len(type)==1) then α = (index2MultiIndex((i 1 , d 1 ,pos))); else card = k j=2 i j +d j i j ; α = (index2MultiIndex(i 1 , d 1 ,pos/card)) + index2TupleMultiIndex([(i 2 , d 2 ), • • • , (i k , d k )], pos%card); return α;
As before, control points can be stored into a simploidal array, using the lexicographical order of the tuples of multi-indices, which induces a correspondence between the index of a point in the array and its associated tuple of multi-indices [START_REF] Derose | Functional composition algorithms via blossoming[END_REF] (cf. Algorithm 4). A data structure for implementing semi-simploidal sets embedded as simploidal Bézier spaces can be deduced from the data structure presented in Section 4.3.

Basic Operations. Any semi-simploidal set can be constructed using the cartesian product and the identification operations. The cartesian product definition can be deduced from the fact that the cartesian product of two simploids of types (a

1 , • • • , an) and (b 1 , • • • , bm) is a simploid of type (a 1 , • • • , an, b 1 , • • • , bm).
The control points of the resulting simploid can be computed for instance by "adding" the control points (i.e. their coordinates) of the initial simploids (Minkowski sum). For instance on Figure 6(c), the control point P 111,22 can be defined as the "sum" of the control points P 111 and P 22 of Figure 6(a). As before, two simploids can be identified if they share the same boundary, and if their control points have the same structure. As before, higher level operations can be easily defined.

Simplicial sets

This section is mainly based upon [START_REF] May | Simplicial Objects in Algebraic Topology[END_REF][START_REF] Lang | Simplicial sets and triangular patches[END_REF]. Our main contribution here is Property 1, which establishes relations between degeneracy operators and control points.

Combinatorial Structure. The cartesian product operation is not directly defined for semi-simplicial sets, but it is defined in a direct way on simplicial sets, thanks to the notion of degenerate simplex: cf. Figure 7.

A simplicial set S = (K, (d j ), (s j )) is a family K = (K i ) i∈N of simplices together with two families of maps, such that (K, (d j )) is a semi-simplicial set, and (s j ) are degeneracy operators: ∀i ≥ 0, ∀j, 0 ≤ j ≤ i, s j : K i → K i+1 ; the degeneracy operators satisfy the commutation properties: An (i + 1)-simplex µ is degenerate if µ = σs j for some σ and some j: intuitively, if σ is assimilated with a sequence of i + 1

• s j s l = s l s j+1 if l ≤ j; • s j d l = d l s j-1 if l < j, s j d l = d l-1 s j if l > j + 1, and s j d j = s j d j+1 = Id. (a) (b) (c) (d) (e) (f)
vertices (v 0 , • • • , v j , • • • , v i ), µ corresponds to (v 0 , • • • , v j , v j , • • • , v i ).
Note that the geometric realization of µ is the one of σ.

From a theoretical point of view, all degererate simplices deduced from a simplex by a sequence of degeneracy operators exist in a simplicial set: thus any simplicial set contains an infinite number of degenerate simplices. For instance, the existence of all these degenerate simplices makes it possible to get a very simple definition of the cartesian product (cf. below). But from a practical point of view, only the explicit representation of non degenerate simplices and their faces (degenerate or not) is required (cf. Figures 7(c) and 7(d)); the other degenerate simplices, can be implicitly handled. Indeed, any degenerate simplex can be obtained by applying a sequence of degeneracy operators to a non degenerate simplex. So, the degenerate simplices which appear only in the boundary of degenerate simplices can be implicitly handled, through the corresponding non degenerate simplex and the sequence of indices of the corresponding degeneracy operators. Compared with the implementation of semi-simplicial sets, the additional cost of the implementation of simplicial set is thus low, and related to the object which has to be represented (for instance, if there are no degenerate simplices in the boundary of any non degenerate simplex, the additional cost is quite null). Obviously, this implicit representation of degenerate simplices has to be taken into account when implementing the construction operations.

Bézier embedding. Let σ be any i-simplex of a simplicial set: a Bézier simplex is associated with σ. The relation between the proper control points of σ and those of σd j , for any j, is the relation described for semi-simplicial sets. If µ is degenerate (i.e. µ = σs j ), Property 1 has to be satisfied, in order to guarantee that µ has same shape as σ (cf. Figure 8). Property 1. Let σ be a i-simplex, and let Bσ be its corresponding Bézier simplex defined by the set of control points {Pα}. Let µ = σs j , 0 ≤ j ≤ i, and let Bµ be its corresponding Bézier simplex defined by the set of control points {P α }. If all control points

P α 0 •••α j α j+1 •••α i+1
such that :

• α k = α k , for 0 ≤ k ≤ j -1,
• α j + α j+1 = α j , for 0 ≤ α j ≤ α j and 0 ≤ α j+1 ≤ α j ,

• α k = α k-1 , for j + 2 ≤ k ≤ i + 1 are equal to Pα 0 •••α i , then Bσ = Bµ.
Proof. The complete proof is not provided, since it is quite straightforward: for a given Pα, it is sufficient to show that:

α j +α j+1 =α j d α 0 • • • α j α j+1 • • • α i u α 0 0 • • • u α j j u α j+1 j+1 • • • u α i i = d α u α 0 0 • • • (u j + u j+1 ) α j • • • u α i i
. This is quite direct, since (u j + u j+1 ) Figure 8: (a) According to Property 1, if all the control points of the degenerate edge are equal to the vertex, then the Bézier simplex corresponding to the edge is equal to the Bézier simplex corresponding to the vertex. (b) illustrates an edge and its two possible degenerate triangles. According to Property 1, if all control points (of a triangle) which are aligned vertically are equal to the control point on the edge in the same alignment, then the Bézier triangles and the Bézier edge are equal. (c) Cartesian product of two edges: the useful degenerate simplices are represented up to dimension 2. According to Property 1, all proper control points of the degenerate edge αs 0 (resp. γs 0 ) are equal to control point P 4 of vertex α (resp. γ); and proper control points P 211 and P 121 (resp. P 112 ) of the degenerate edge βs 0 are equal to control point P 31 (resp. P 22 ) of β. Similarly, proper control points P 121 and P 112 (resp. P 211 ) of degenerate simplex βs 1 are equal to control point P 13 (resp. P 22 ) of β. (d) the simplicial set resulting from the cartesian product of the two edges of (c). Each 2-simplex in (d) is the simplex resulting from the cartesian product of the two 2-simplices of the same color in (c). For example, βs 0 × β s 1 is the simplex (βs 0 , β s 1 ). For clarity purpose, the control points are displayed in (e).

α j = α j k=0 α j k u α j -k j u k j+1 4
So, a triangular Bézier space can be associated with any simplicial set. From a practical point of view, only the control points of non degenerate simplices are needed. The control points of any simplex (degenerate or not) can be retrieved from its proper control points and from the relations corresponding to face and degeneracy operators: in particular, when the simplex is degenerate, its control points can be deduced from the control points associated with the highest dimensional non degenerate simplex of its boundary, using Property 1. So, the additional cost for embedding simplicial sets, compared with semi-simplicial sets, is null, except the computing time for accessing the control points of a degenerate simplex: in this case, the access time is lower than the dimension of the simplex, with an adequate data structure (cf. Section 4.3). Note that, as for the semi-simplicial case, it is assumed that the degrees of all Bézier simplices are equal, whether they are degenerate or not (and as before, it is possible to avoid this constraint by applying results about the degree elevation: cf. [START_REF] Farin | Curves and Surfaces for CAGD: A Practical Guide[END_REF]).

Data structure. The following data structure is a a direct extention of the semi-simplicial set data structure presented in Section 2. As mentioned before, only degenerate simplices that are faces of non degenerate simplices are usefull for handling Bézier spaces. So, for any simplex σ, σ.degenOps references its "usefull" degenerate simplices in the following way: each element (i, τ ) corresponds to σs i = τ . Note that if a simplex σ is degenerate, then its access ctrlP ts is null, since its control points can be deduced from those of the highest non degenerate simplex of its boundary. The cone definition is a direct extension of the cone of a semi-simplicial set. The identification of two i-simplices σ and µ having same boundary (cf. Algorithms 5 and 6) implies now the identification two by two of all degenerate simplices deduced from σ and µ by the same sequence of degeneracy operators. More precisely, let K be the set of simplices of S before identification of σ and µ, K can be partitionned into K = C 0 ∪ • • • ∪ Cn ∪ K such that for any i, all simplices belonging to C i have to be identified, and all simplices of K remains after the operation. So, after the identification of σ and µ, the resulting simplicial set contains one simplex γ i for each equivalence class C i , and all simplices of K . Notation 1. Let S = (K, (d j ), (s j )) be a simplicial set, and let K = C 0 ∪ • • • ∪ Cn ∪ K be a partition of the simplices as described above. Algorithm 6 uses the following notations:

• for any simplex τ ∈ C i , for any i, rep(τ ) = γ i is the resulting simplex associated with C i ;

• for any C i , τ i is any simplex of C i ;

• star(C i ) denotes the set of simplices of S having a face in C i ;

• boundary(C i ) denotes the set of simplices of S having a degenerate simplex in C i .

So, the identification of two simplices σ and µ having same boundary consists in computing the set of equivalence classes C 0 ...Cn, and then to merge each equivalent class into a simplex γ i of same dimension. Then, for each simplex γ i , to set its face and degeneracy operators according to equivalent classes, and finally, to update the face operators of its star (only for simplices belonging to K ), and to update the degeneracy operators of its boundary (only for simplices belonging to K ).

S [C 0 , • • • , Cn]=buildIdentification({σ,µ}); K = {ν ∈ S | ν / ∈ [C 0 , • • • , Cn]}; for i in 0..n do γ i = new Simplex(dim(C i )) /* dim(C i ) is the dimension of the simplices in C i */ add(S,γ i );
for each γ i do for j in 0..dim(γ i ) do

γ i d j = rep(τ i d j ); γ i s j = rep(τ i s j ); for τ in star(C i ) s.t. τ ∈ K do for j in 0..dim(τ ) do if τ d j ∈ C i then τ d j = γ i for τ in boundary(C i ) s.t. τ ∈ K do for j in 0..dim(τ ) do if τ s j ∈ C i then τ s j = γ i remove(S, C i );
The cartesian product of two simplicial sets S and S can be easily defined: a i-simplex µ from S × S is associated with any pair (σ, σ ) of i-simplices of S and S , such that for any j, µd j = (σd j , σ d j ) and µs j = (σs j , σ s j ) (cf. Figure 8(d)). The control points associated with µ can be computed by "adding" the corresponding points of σ and σ (Minkowski sum). For instance on Figure 8(e), point P 121 of (βs 1 , β s 0 ) corresponds to the sum of P 13 of β (and thus P 121 of βs 1 ) and P 31 of β (and thus P 121 of βs 0 ). In practice, only the degenerate simplices having a dimension lower than the sum of the dimensions of S and S are needed for computing the cartesian product of S and S . At last, note that it is possible to directly deduce the cartesian product of two semi-simplicial sets by implicitly handling the degenerate simplices (and thus the degeneracy operators): cf. [START_REF] Lienhardt | Cartesian product of simplicial and cellular structures[END_REF]. These results can be extended for cubical sets [START_REF] Serre | Homologie singulière des espaces fibrés[END_REF][START_REF] Brown | On the algebra of cubes[END_REF], which can be defined in the following way. A cubical set S = (K, (d i j ), (s i )) is a family K = (K p ) p∈N of cubes together with two families of maps, such that (K, (d i j )) is a semi-cubical set, and (s i ) are degeneracy operators: ∀p ≥ 0, ∀i, 0 ≤ i ≤ p, s i : K p → K p+1 , which satisfy:

s i s k = s k s i+1 if k ≤ i, s i d k j = d k j s i-1 if k ≤ i, s i d k j = d k-1 j s i if k > i + 1 and s i d i+1 j = Id.

Simploidal

As seen in section 2, semi-simploidal sets contain and generalize semi-simplicial and semi-cubical sets.

Similarly to simplicial and cubical sets, simploidal sets are defined by adding degeneracy operators to semi-simploidal sets. In particular, it is then possible to define the cone operation (cf. Figure 10) thanks to these operators.

σd i j T = (a 1 , ..., a i -1, ..., an) if a i > 1 (a 1 , ..., a i-1 , a i+1 , ..., an) otherwise 2) σs i j T = (a 1 , ..., a i + 1, ..., an) 1 ≤ i ≤ n, 0 ≤ j ≤ a i (a 1 , ..., a i , 1, a i+1 , ..., an) 0 ≤ i ≤ n, j = -1 (III) Commutation of degeneracy operators 1) s i -1 s k -1 = s k -1 s i+1 -1 k ≤ i 2) if l = -1, s i -1 s k l = s k l s i -1 if k ≤ i s k-1 l s i -1 if i < k -1 3) if j, l = -1, s i j s k l = s k l s i j if i = k s k l s i j+1 if i = k, l ≤ j (II) Commutation of face operators 1) d i j d i l = d i l d i j-1 l < j, a i > 1 2) d i j d k l = d k l d i j if a k > 1 d k l d i-1 j otherwise k < i (IV) Commutation of face/degeneracy operators 1) if l = -1, s i l d i j =    d i j s i l-1 if j < l d i j-1 s i l if j > l + 1 s i l d i j+1 = Id if j = l 2)if l = -1, s i-1 l d i j = Id
In the other cases:

3) if k ≤ i -1, s k l d i j = d i j s k l if l = -1 d i-1 j s k l otherwise 4) else (i.e. k ≥ i), s k l d i j = d i j s k l if a i > 1 d i j s k-1 l otherwise
Let σ be a simploid of type (a 1 , ..., an): n is the length of σ, and its dimension is n i=1 a i , or 0 if n = 0. Intuitively, and as explained in section 2.3, a simploid is either a vertex, or the cartesian product of n "generating simplices" of respective dimensions a 1 , ..., an, with a i > 0 for any i. No "0" appears in the type of a simploid, since the cartesian product by a vertex is, from a structural point of view, equal to the identity. This explains the fact that several cases are distinguished in the definition of simploidal sets, even if these cases are intuitively similar. More generally, Definition 1 can be retrieved from the previous remark, the properties of face and degeneracy operators of simplicial sets, and from the fact that the actions of two operators on two different "generating simplices" are independent.

Equations (I) denotes the action of an operator on the simploid type (equations (I-1) for a face operator, equations (I-2) for a degeneracy operator). The action of a face (resp. degeneracy) operator on a "generating simplex" decreases (resp. increases) its dimension; hence, if a zero appears after the application of a face operator (i.e. if a i = 1 and d i j is applied), it is removed from the type. Conversely, the application of degeneracy operator s k -1 intuitively consists in adding a degenerate edge as new "generating simplex".

Equations (II) (resp. (III), (IV)) corresponds to the commutation relation of face operators (resp. degeneracy operators, degeneracy and face operators). Several cases correspond to the commutation properties of simplicial sets, i.e. when operators are applied on the same "generating simplex": cf. equation (II-1), the last case of equation (III-3), equation (IV-1). Equation (IV-2) corresponds to the removal, by a face operator, of a new 1-dimensional "generating simplex" issued from a degeneracy operator (i.e. nothing is modified).

The other cases correspond to the independence of the actions of operators applied to distinct "generating simplices":

• equations (II-2) : two cases are distinguished, according to the fact that a 1-dimensional "generating simplex" disappears when a face operator is applied;

• equations (III-1), (III-2) and the first case of equation (III-3) : these cases are distinguished, according to the number of new "generating simplices" created by operator s -1 ; note that there is no commutation property in equation (III-2) when k = i + 1, since σs k-1 -1 s k l T = (a 1 , . . . , a k-1 , 2, . . . , an) (the first degeneracy operator creates a new 1-dimensional "generating simplex", on which another degeneracy operator is applied);

• equations (IV-3) and (IV-4): these cases are distinguished, according to the creation or removal of 1-dimensional "generating simplices".

The following theorem comes directly from the definition of simploidal sets.

Theorem 2. A unique simploidal set can be associated with:

• any simplicial set

• any cubical set.

The proof of Theorem 2 is straightforward:

• given a simplicial set S = (K, (d j ), (s j )), a simploidal set S = (K , (d 1 j ), (s 1 j )) can be defined, such that: 1. a simploid of type (n) is associated with any n-simplex; 2. d 1 j (resp. s 1 j ) corresponds to d j (resp. s j ) for any j. • This is similar for cubical sets: a simploid of type (a 1 , • • • , an), such that a i = 1 for any i, is associated with any n-cube.

Even if the definition of simploidal sets seems complicated since the face and degeneracy operators have to satisfy many properties, its implementation is direct, contrary to the simpler definition of supercomplexes proposed by Gugenheim in 1957, for topological purposes (cf. section 4.5 for a comparison of simploidal sets and supercomplexes).

Simploidal sets are also efficient, since the properties of the definition are not implemented explicitly. These properties have to be satisfied by the construction operations, but this involves no particular cost. More precisely, and as for simplicial sets, only non degenerate simploids and theirs faces (degenerate or not) have to be explicitly represented. So, the additional cost of simploidal sets is low, even compared with semi-simplicial sets; it is related to the representation of the type of any simploid, and to the "complexity" of the object which has to be represented (cf. section 4.3).

Bézier embedding

Associating a simploidal set with a simploidal Bézier space can be done by extending the results described for the simplicial case. From a theoretical point of view, assume a Bézier simploid is associated with any simploid; the following property has to be satisfied in order to represent a simploidal Bézier space: Property 2. Let S = (K, (d i j ), (s k l ) be a simploidal set, let σ be a simploid of type (a 1 , ..., an) of K, let

P σ = {P (α 1 ,...,α n ) , α i ∈ Γ a i d i
, 1 ≤ i ≤ n} be its set of control points, and let Bσ be the Bézier simploid associated with σ.

(1) Let µ = σd i j , let P µ be its set of control points, and let Bµ be the Bézier simploid associated with µ. If any control point P σ (α 1 ,...,α i ,...,α n ) is equal to:

• P µ (α 1 ,...,α i-1 ,α i ,α i+1 ,...,α n ) , where α i = α i 0 • • • α i j-1 α i j+1 • • • α i a i if a i > 1 and α i j = 0, • P µ (α 1 ,...,α i-1 ,α i+1 ,...,α n ) , if a i = 1, then Bσ(u) = Bµ(u ) where: • u = (u 1 , • • • , u n ), • u = (u 1 , • • • , u i-1 , u i , u i+1 • • • , u n ), where u i = (u i 0 , • • • , u i j-1 , u i j+1 , • • • , u i a i ), if a i > 1 and u i j = 0, • u = (u 1 , • • • , u i-1 , u i+1 • • • , u n ) if a i = 1.
(2) Let µ = σs i j , let P µ be its set of control points, and let Bµ be the Bézier simploid associated with µ. If: • if j ≥ 0: all control points P µ (α 1 ,...,α i ,...,α n ) are equal to the control point P σ (α 1 ,...,α i ,...,α n ) , where

α i k = α i k for k < j, α i j + α i j+1 = α i j , α i k = α i k-1 for k > j + 1, for any a 1 , • • • , a i-1 , a i+1 , • • • , an, • if j = -1: all control points P µ (α 1 ,...,α i ,α i+1 ,α i+1 ,...,α n ) of σs i -1 are equal to the control point P σ (α 1 ,...,α n ) , where α i+1 ∈ Γ 1 d i+1 , then Bσ = Bµ
As a consequence of Property 2, it is sufficient in practice to associate its proper control points with any non degenerate simploid. The set of control points of any simploid σ can be reconstructed according to Property 2 and to the numbering of face operators:

• if σ is a vertex, a point is associated with it;

• else, if σ is not degenerate, its associated control points can be retrieved from its proper control points, and from the proper control points of the simploids of its boundary, using the numbering of face operators. If σ is degenerate, it is necessary to access the control points of its associated non degenerate simploid, using the numbering of degeneracy operators and the Property 2, which links the control points of simploids σ and σs i j . . Remember also that the computation of all Bézier simploids of a simploidal set can be useless, depending on the application: for example, only non degenerate main simploids are required in order to display a simploidal set.

At last, note that control points of non degenerate simploids can be stored into a simploidal array according to the lexicographical order of tuples of multi-indices [START_REF] Derose | Functional composition algorithms via blossoming[END_REF]. For instance, let P = P (α 1 ,...,α n ) be a control point of a Bézier simploid of type (a 1 , . . . , an) and degree (d 1 , . . . , dn). If n = 1, then the simploid corresponds to a simplex, and P is stored as described in section 2.1. If n > 1, it is necessary to store all control points of a simploid of type (a 2 , . . . , an) of degree (d 2 , . . . , dn) for each multi-index of Γ a 1 d 1 preceding α 1 ; then point P can be stored as if it would be a control point of a Bézier simploid of type (a 2 , . . . , an) and degree (d 2 , . . . , dn), with a tuple of multi-indices equal to (α 2 , . . . , α n ).

Data Structure

The following data structure is a possible implementation of simploidal sets associated with simploidal Bézier spaces, where each simploid is associated with its proper control points. In this way, no control point is duplicated. In order to compute the Bézier space corresponding to a simploidal set, the control points of main Bézier simploids can be retrieved thanks to the boundary operators. Note that if a simploid σ is degenerate (i.e. σ = µs i j for some i and j), then σ and µ have the same shape, so there is no need to store its control points of σ (i.e. σ.ctrlP ts is null). Regarding the SimploidalSet structure, dim is the dimension of the simploidal set, allSimploids stores the lists of simploids, ordered by increasing dimensions; degree is the degree of each "generating simplex". It is thus assumed here that, whatever its type, the degree of a simploid of length n is (d 1 = degree, . . . , dn = degree); this simplifies several operations. Else it could be necessary to modify some degrees [START_REF] Farin | Curves and Surfaces for CAGD: A Practical Guide[END_REF], for instance for identifying two simploids having same types but different degrees.

Regarding the Simploid structure, let σ be a simploid of type (a 1 , ..., an) and degree (d 1 , . . . , dn), set gives access to its simploidal set. n is the length of its type, a i corresponds to σ.type[i] and d i corresponds to σ.set.degree.

Let d = σ.n i=1 σ.type[i] be the dimension of σ. faceOps gives access to the boundary simploids of dimension d -1. ctrlPts is an access to the array containing the proper control points of σ, ordered by lexicographical order, the access is null for degenerate simploids. The n-tuple of multi-indices of a point can be retrieved from its index in the array.

Remember that only simploids which are in the boundaries of non degenerate simploids are explicitly represented. So, it is assumed that there are few degenerate simploids (compared to non degenerate ones). So, in the presented structure, degenOps stores only useful degeneracy operators: if σs i j = τ and τ is a face of a non degenerate simploid, then the element ((i, j), τ ) is stored in degenOps. Another solution would be to define degenOps as a reference to an array of references to simploids. At each index of the array, a reference is either null, either corresponds to a degenerate simploid. The respective interests of these solutions depend on the objects which are represented.

Note that it could be interesting to access all simploids of dimension d + 1 in the star of σ; these accesses corresponds to the inverse of the face operators, and can be represented by a list of * Simploid associated with each simploid.

If σ is degenerate, it is important to access the corresponding non degenerate simploid τ . In fact, τ is in the boundary of σ, and can be accessed by using the face operators, thanks to the relations between face and degeneracy operators. In order to optimize the access to τ , i.e. to avoid to check all face operators, it can be interesting to associate with σ a list of numberings, corresponding to the face operators accessing the face from which σ is degenerate.

The structure can be optimized for different subclasses of simploidal sets, for instance for semi-simploidal sets, cubical sets (only the dimensions of cubes are required, since the type of a d-dimensional cube is the d-tuple (1, . . . , 1)). Other optimizations can be proposed, for instance for manifolds: all simploids have the same dimension, and face operators are replaced by adjacency operators.

At last, note that the additional cost, compared with a similar structure implementing simplicial sets, is low, since it corresponds to the types which have to be explicitly associated with all simploids: it is thus at most the dimension of the simploidal set times the number of simploids.

Remark: similarly to triangular Bézier spaces (cf. section 2.1), another possible data structure for handling Bézier simploidal spaces is a list of simploidal arrays, where each array contains the control points of a main Bézier simploid. The main drawbacks are related to:

• the redundancy of the representation, since control points of a non main simploid appear in all simploidal arrays associated with the main simploids of its star: this may lead to inconsistency and space complexity problems;

• the efficiency of several construction operations and topological properties computations, since all simploids are not represented nor the adjacency and incidence relations between simploids.

Basic Operations

From a theoretical point of view, and similarly to the simplicial case, all degenerate simploids associated with any simploid exist in a simploidal set; so, a simploidal set contains an infinite number of simploids. In practice, only the non degenerate simploids and their faces (degenerate or not) are represented. For some operations, additional degenerate simploids can be of interest. For example, a simploid can be simply degenerate using the identification operation with a degenerate simploid.

Cartesian Product (cf. Algorithm 7) As for semi-simploidal sets, the definition of the cartesian product of two simploidal sets S 1 and S 2 is deduced from the following property: the cartesian product of two simploids σ 1 of type (a 1 , ..., a k ), and σ 2 of type (b 1 , ..., b l ) is a simploid σ of type (a 1 , ..., a k , b 1 , ..., b l ).

So, the cartesian product of S 1 and S 2 consists in creating all simploids σ 1 × σ 2 for each σ 1 ∈ S 1 and σ 2 ∈ S 2 . The creation of each new simploid σ involves the computation of its control points if σ is not degenerate. Then, its face operators are set according to the following property : σd

i j = σ 1 d i j × σ 2 for 1 ≤ i ≤ k, σd i+k j = σ × σ 2 d i j for 1 ≤ i ≤ l.
Then, degeneracy operators are set according to the following property: σs

i j = σ 1 s i j × σ 2 for 0 ≤ i ≤ k, σs i+k j = σ × σ 2 s i j for 0 ≤ i ≤ l. Note that τ 1 = σ 1 s k -1 × σ 2 and τ 2 = σ 1 × σ 2 s 0 -1 correspond
to the same simploid, so τ 1 and τ 2 have to be merged if they both are not null.

This operation can be easily extended in order to define the cartesian product of subsets of given simploidal sets.

Identification As for semi-simploidal sets, two simploids σ and µ can be identified under some structural conditions (equality of type and boundary) and geometrical conditions (equality of degree). The algorithm can directly be deduced from Algorithm 6 is possible to define the cone operation for a simploidal subset.

Homology computation: Homology of semi-simploidal sets has been studied in [START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF]. Its computation is based on the notion of simploid boundary, which can be deduced from the simploidal face operators. This notion can be extended for simploidal sets: only non degenerate simploids are taken into account; in particular if a degenerate simploid τ is a face of a non degenerate simploid σ, then τ does not appear in the boundary of σ.

Obviously, other construction operations can be defined, based on these basic operations, in order to construct simploidal sets.

Discussion about Gugenheim's definition

Supercomplexes were defined in 1957 (cf. [START_REF] Gugenheim | On supercomplexes[END_REF] page 37). By mimicking the definition of simploidal sets, (the structure of) supercomplexes could be defined in the following way:

Definition 3. A supercomplex S = (K, (d i j ), (s i j )
) is a set of simploids equipped with a type operator T : K → ∞ i=1 N i , face operators d i j and degeneracy operators

s k l . Let σT = (a 1 , • • • , an): σd i j (resp. σs k l ) is defined if 1 ≤ i ≤ n, a i > 0, 0 ≤ j ≤ a i (resp. 1 ≤ k ≤ n and 0 ≤ l ≤ a k ). Operators satisfy:
• σd i j T = (a 1 , ..., a i -1, ..., an), σs i j T = (a 1 , ..., a i + 1, a i+1 , ..., an); • face and degeneracy operators having the same exponent satisfy the commutation properties of face and degeneracy operators of simplicial sets;

• face and degeneracy operators having different exponents commute. for i in 1..k do for j in 0..ai do σd i j = σd i j ;

for each s i j defined for σ do σs i j = σs i j ;

Obviously, this definition of supercomplexes is simpler than the definition of simploidal sets given in 4.1. This is due to the fact that the type of a simploid may contain components equal to 0. Let σ be a supercomplex of type (2, 1) (i.e a prism), then the type of σd 2 0 is (2, 0) (i.e. a triangle). Conversely, in order to associate a degenerate cube with a square, the type of the square has to be for instance (1, 1, 0), so the degeneracy operator s 2 0 can be applied. This simple definition of supercomplexes is based on the fact that, implicitly, an equivalence relation exists between types which differ only by components equal to 0: this corresponds to the fact that the cartesian product by a vertex is (structurally speaking) equal to the identity. Note that Gugenheim was not interested in the definition of embedding, construction operations nor implementation, and that this equivalence relation was never explicitly stated. Let Q be the set of supercomplexes quotiented by this equivalence relation. Theorem 4. The set of simploidal sets is equivalent to Q.

The proof is not provided here because it is rather technical. The definition of supercomplexes is not well suited for a direct implementation. In particular, the length of the type of a n-dimensional simploid is not bounded, since it can contain any number of zeros. So, contrary to simploidal sets, it is not possible to bound the complexity of the space representation nor that of operations as simple as the comparison of two types, which is necessary for instance for the identification operation.

In order to warrant the unicity of the types, no 0 appears in the type of a simploid. So, our definition of simploidal sets contains more constraints over boundary and degeneracy operators, since many cases have to be distinguished in the definition; but, as said above, this does not involve any additional cost, since the properties of the operators don't involve any requirement in space nor in computation. The properties described by equations (I) to (IV) are taken into account by the modifications which are performed during the application of an operation, but they don't involve a particular computation. Even if it would be necessary, checking that the properties of a simploidal set are satisfied would not involve additional space or time requirements, compared with supercomplexes.

So, our definition is more efficient regarding implementation issues, and the definition of relations with simploidal Bézier spaces as that of construction operations is quite simple, compared with similar operations defined on simplicial and cubical sets. The counterpart is the fact that the commutation properties of the face and degeneracy operators cannot be expressed as simply as in the supercomplexes definition. Otherwise said, our definition corresponds to the one of Gugenheim such that for each equivalence class, we chose the representative simploid with no 0.

Conclusion -Future Work

Simploidal sets generalize simplicial sets and cubical sets: they are defined in a similar way, by abstract simploids on which act face and degeneracy operators. All basic operations defined in the simplicial and cubical frameworks are extended for simploidal sets: cone, cartesian product, degeneracy and identification. Relations between simploidal sets and simploidal Bézier spaces generalize similar relations between simplicial (resp. cubical) sets and triangular (resp. cubical) Bézier spaces.

The simploidal framework presented in this paper is thus general and coherent, meaning that it is possible to conceive softwares implementing simploidal sets embedded with Bézier spaces (e.g. for computing topological properties or for geometric modeling), which make it possible to handle also simplicial sets or cubical sets as particular cases. Moreover, it is possible to handle simultaneously different types of cells, for hybrid meshes applications for instance.

The cost of this generalization is not significant, since the definition of simploidal sets is very close to the definitions of simplicial and cubical sets: the main difference, when implementing simploidal sets, is that the type of a simploid has to be explicitly represented.

Note that a difference exists between semi-simplicial sets and semi-simploidal sets. It is possible to directly adapt the definition of the cartesian product of simplicial sets for semi-simplicial sets, by implicitly handling degeneracy operators [START_REF] Lienhardt | Cartesian product of simplicial and cellular structures[END_REF]: this comes from the fact that the cartesian product of any two simplices (and their boundaries) can be described as a semi-simplicial set. Unfortunately, it is not possible to directly adapt the definition of the cone of simploidal sets for semi-simploidal sets, because the cone of a simploid is not necessarily a simploid.

The relations between simploidal sets and simploidal Bézier spaces have been stated. The basic data structure presented in this paper is a straightforward implementation of the combinatorial structure, but some optimizations can be considered for subclasses of simploidal sets. For instance, for manifolds, it is sufficient to represent the main cells and their adjacency relations (cf. [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] chapter 10). When dealing with low-dimensional simploidal sets (e.g. 2 or 3), even the basic data structure can obviously be optimized. More generally, optimization techniques related to mesh compression can be applied [START_REF] Maglo | 3d mesh compression: Survey, comparisons, and emerging trends[END_REF].

Figure 1 :

 1 Figure 1: (a) Simploids and their types. (b) Counterexamples of simploids: a pentagon and a pyramid (i.e. a cone on a square face): the main cells are not the cartesian product of simplices. (c) A geometric representation of a simploidal set made of 3 3-dimensional simploids: a tetraedron (type (3)), a cube (type (1, 1, 1)) and a prism (type (2, 1) or (1, 2)).

Figure 2 :

 2 Figure 2: (a) A semi-simplicial set. Semi-simplicial set (b) is obtained by identifying vertices v1 and v2, vertices w1, w2 and w3, and edges a1 and a2. (c) A geometric representation of semi-simplicial set (b). The commutation properties satisfied by face operators guarantee the consistency of the data structure. For example, for any triangle σ: σd 2 d 1 = σd 1 d 1 , σd 2 d 0 = σd 0 d 1 , and σd 1 d 0 = σd 0 d 0 , so a triangle has at most 3 vertices in its boundary.

Figure 3 :

 3 Figure 3: (a) An example of Bézier space of degree 3. (b) Main storage: only the control points of the main simplices are stored. (c) Distributed storage: only the proper control points are stored.

1 dim- 1 ]

 11 ): the proper control points numbered 21, 12 of the edge σd 0 (resp. σd 1 and σd 2 ) correspond to the control points numbered 021, 012 (resp. 201, 102 and 210, 120) of σ, as shown in Figure 3(b). Data structure. The following data structure is a straightforward implementation of semi-simplicial sets associated with triangular Bézier spaces of degree degree. The notation *Type denotes an access to a Type data ; [x..y] of Type and [] of Type denote an array of Type: in the first case, the indices are specified; List<Type> denotes a list of Type data. type Simplex is record : dim : integer faceOps : [0..dim] of *Simplex ctrlPts : [0..C set.degree-of CtrPt set : *SemiSimplicialSet end record type SemiSimplicialSet is record : dim : integer degree : integer allSimplices : [0..dim] of List<*Simplex> end record

Figure 4 :

 4 Figure 4: The semi-simplicial set b) can be obtained by a cone operation applied to the semi-simplicial set of a), v is the new vertex. c) is a geometric representation of semi-simplicial set b).

Figure 5 :

 5 Figure 5: The 2-cube in (b) results from the product of the vertical edge by the horizontal edge in (a), so face operators d 1 j (resp. d 2 j ) which acts on the 2-cube "are oriented" vertically (resp. horizontally). A cubical Bézier space corresponding to a cubical set containing two 3-cubes, one 2-cube and one 1-cube as main cells.

Figure 6 :

 6 Figure6: a) and b): correspondence between the product of two simplices (and their boundaries) and a simploid of type (2, 1). For clarity purpose, only a part of its boundary is displayed and some of its control points are displayed in c).

Figure 7 :

 7 Figure 7: a) a semi-simplicial set and (b) its associated Bézier triangular space. (c) a simplicial set: the green edge µ is degenerate into the bottom vertex σ. Otherwise said, µ = σs 0 . (d) the corresponding triangular Bézier space: the degenerate edge is reduced to a point, corresponding to its incident vertex. Note that edge µ is the only degenerate simplex which is a face of a non degenerate one. (e) a simplicial set representing an edge (and its boundary) and all its degenerate simplices up to dimension 2 (in green) and f ) its corresponding Bézier triangular space.

Figure 9 :

 9 Figure9: A simploidal Bézier space of dimension 3. Note that σ 1 is a prism (i.e. simploid of type (2, 1)) connecting the simplex σ 2 and the cube σ 3 , σ 4 is a square (i.e. simploid of type (1, 1)) such that one of its edge is a self loop, σ 6 is a cube (i.e. simploid of type (1, 1, 1)) with a degenerate edge, and σ 5 is a cone over a square face (i.e. a simploid of type (1, 1, 1) with a degenerate face).

4. 1

 1 Combinatorial Structure Definition 1. A simploidal set S = (K, (d i j ), (s k l )) is a set of simploids equipped with a type operator T : K → ∞ i=0 N * i , face operators d i j and degeneracy operators s k l . Let σ ∈ K; σT is the type of σ. Let σT = (a 1 , • • • , an): σd i j (resp. σs k l ) is defined if 1 ≤ i ≤ n, 0 ≤ j ≤ a i (resp. 0 ≤ k ≤ n and l = -1, or 1 ≤ k ≤ n and 0 ≤ l ≤ a k ). Operators satisfy: (I) Action on the type 1)

Figure 10 :

 10 Figure 10: (a) The cone applied to a square (and its boundary) is a square-based pyramid (d). Thanks to degeneracy operators, the cone operation consists in an extrusion (a) -(b) followed by the degeneracy of the copy of the original simploidal set (in orange in (b). In practice, the computation can be improved by creating directly all the degenerate simploids incident to the new vertex and then setting all the boundary and degeneracy operators (c). (e) the structure of the control points of a lateral Bézier square face of (d) is different from the structure of the control points of a Bézier triangle (f ).

Algorithm 8 : 1 = σ; σd k+1 0 =

 810 Cone Input : S : SimploidalSet ; v : Vertex Output: S : SimploidalSet S = degenerateToVertex(S, v); S = S ∪ S ; K = {} /* for storing new simploids of the cone */ for σ ∈ S do (a1, • • • , a k )=type(σ); σ = create Simploid of type (a1, • • • , a k , 1); add(K,σ); σd k+1 getSimploidOfType(S " , σ)/* S " contains only one simploid of each type */ add(S ,K); for σ ∈ K do (a1, • • • , a k , 1)=type(σ);

Note that in[START_REF] Peltier | Simploidals sets: Definitions, operations and comparison with simplicial sets[END_REF], the term "simploidal" meant "semi-simploidal". This terminology is modified here in order to be consistent with those related to simplicial and cubical structures.

i.e. any simplicial object can be constructed using cone and identification, as any cubical object can be constructed using extrusion and identification.

Acknowledgments: The authors gratefully acknowledge Laurent Fuchs for helpful discussions and encouragements.

Algorithm 7: Cartesian Product Input : S 1 , S 2 : SimploidalSet Output: S : SimploidalSet σ, σ1, σ2 : Simploid; S.dim = S 1 .dim + S 2 .dim; S.degree = S 1 .degree; for σ 1 ∈ S 1 do for σ 2 ∈ S 2 do σ = create Simploid σ 1 × σ 2 ; add(S, σ)

/* Setting face and degeneracy operators */ for σ = σ 1 × σ 2 ∈ S do (a1, • • • , a k ) =type(σ 1 );

for i in 1..l do for j in 0..bi do

for each s i j defined for σ 1 do σs i j = σ 1 s i j × σ 2 ; for each s i j defined for σ 2 do

defined for simplicial sets. The basic identification operation is also defined for two simploids having same boundary. As for simplicial sets, the identification of σ and µ induces the identifications of their degenerate simploids. When σ and µ are not degenerate, the computation of the control points of the simploid resulting from the identification of σ and µ can be done as in the semi-simploidal framework. If σ or µ is degenerate, then the resulting simploid is degenerate. This basic operation can be generalized in order to identify simploidal subsets: the identification of two simploids induces then the identification of their boundaries.

Note that two simploids σ and µ may have similar "shapes" but different types; in these cases, σ and µ can not be directly identified:

• When the type of σ is a permutation of the type of µ. For instance, a simploid of type (1, 2) is not a simploid of type (2, 1)

(the cartesian product is not commutative). A similar remark can be stated for simplicial sets, since simplicial sets exist, which are not isomorphic, but their geometric realizations are.

• When a simploid has degenerate faces: for instance, in Figure 10(d), the 4 lateral faces of the pyramid are simploids of type (1, 1) but look like triangles (type (2)), because one of their edges is degenerate. But the difference of such simploids with triangles is clear regarding the structure of their control points (cf. Figures 10(e) and 10(f)).

Degeneracy From a theoretical point of view, there is no atomic operation of degeneracy. In fact, degenerating a simploid µ consists in an identification of µ with a degenerate simploid having same boundary. More precisely, degenerating µ into one of its faces σ consists in identifying µ with a degenerate simploid of same type, associated with σ by a degeneracy operator.

In practice, µ can be degenerate into σ if it has the same boundary as a degenerate simplex σs i j for some i and j. In case σs i j is not explicitly represented, then it is just necessary to set the degeneracy operator σs i j to µ. Note that if µ is a main simploid, then µ can simply be removed from the simploidal set.

This operation can be generalized in order to degenerate a simploidal set S into a single vertex: this can be achieved by identifying all vertices of S, and then by iteratively identifying all edges and in degenerating the resulting edge, then in applying the same process to all 2-dimensional simploids (according to their types), and so on. Note that the resulting simploidal set S " contains only degenerate simploids except the vertex. More precisely, S " contains one simploid of each type contained in S. In practice, degenerating S into a single vertex can simply be done by creating one simploid of each type contained in S, and then to set all the face and degeneracy operators according to the type. For example, when a prism is degenerate into a vertex, the resulting simploidal set contains one simploid of each type (0), (1), ( 2), (1, 1), and (2, 1). Then all face and degeneracy operators are set according to the simploid types.

Cone Intuitively, the cone operation of a simploidal set S with a vertex v consists in extruding S by an edge incident to v; and then in degenerating S × v into v (cf. Figures 10(a In practice, it is not necessary compute the extrusion and then to degenerate S × v into v. As said before, degenerating S into v can simply be done by creating one simploid of each type of S, and then by setting all the face and degeneracy operators according to the simploid types. Then, for each simploid σ ∈ S of type (a 1 , • • • , a k ), a new simploid σ of type (a 1 , • • • , a k , 1) is created. Its face and degeneracy operators are set according to Algorithm 8. Finally, as mentionned for the cartesian product, it