The Meccano Method for Automatic Tetrahedral Mesh Generation of Complex Genus-Zero Solids
J.M. Cascn1 , R. Montenegro2 , J.M. Escobar2, E. Rodr o guez2, 2 and G. Montero
Department of Economics and Economic History, Faculty of Economics and Management, University of Salamanca, Spain casbar@usal.es Institute for Intelligent Systems and Numerical Applications in Engineering, University of Las Palmas de Gran Canaria, Campus Universitario de Tara, Las Palmas de Gran Canaria, Spain {rmontenegro,jmescobar,erodriguez,gmontero}@siani.es http://www.dca.iusiani.ulpgc.es/proyecto2008-2011
Abstract. In this paper we introduce an automatic tetrahedral mesh generator for complex genus-zero solids, based on the novel meccano technique. Our method only demands a surface triangulation of the solid, and a coarse approximation of the solid, called meccano, that is just a cube in this case. The procedure builds a 3-D triangulation of the solid as a deformation of an appropriate tetrahedral mesh of the meccano. For this purpose, the method combines several procedures: an automatic mapping from the meccano boundary to the solid surface, a 3-D local renement algorithm and a simultaneous mesh untangling and smoothing. A volume parametrization of the genus-zero solid to a cube (meccano) is a direct consequence. The eciency of the proposed technique is shown with several applications. Keywords: Tetrahedral mesh generation, local renement, nested meshes, mesh untangling and smoothing, surface and volume parametrization.

1 Introduction

Many authors have devoted great eort to solving the automatic mesh generation problem in dierent ways [3, 13, 14, 26], but the 3-D problem is still open [1]. In the past, the main objective has been to achieve high quality adaptive meshes of complex solids with minimal user intervention and low computational cost. At present, it is well known that most mesh generators are based on Delaunay triangulation and advancing front technique. However, problems related to mesh quality, mesh adaption and mesh conformity with the solid boundary, still remain. We have recently introduced the meccano technique in [21, 2, 22] for constructing adaptive tetrahedral meshes of solids. The method requires a surface

J.M. Cascn et al. o

triangulation of the solid, a meccano and a tolerance that xes the desired approximation of the solid surface. The name of the method stems from the fact that the process starts from an outline of the solid, i.e. a meccano composed by connected polyhedral pieces. A particular case is a meccano consisting only of connected cubes, i.e. a polycube [25, 19, 27]. The method generates the solid mesh as a deformation of an appropriate tetrahedral mesh of the meccano. The main idea of the new mesh generator is to combine an automatic parametrization of surface triangulations [6], a local renement algorithm for 3-D nested triangulations [17] and a simultaneous untangling and smoothing procedure [4]. In this paper, we present signicant advances in the method. We dene an automatic parametrization of a solid surface triangulation to the meccano boundary. For this purpose, we rst divide the surface triangulation into patches with the same topological connection as the meccano faces. Then, a discrete mapping from each surface patch to the corresponding meccano face is constructed by using the parameterization of surface triangulations proposed by M. Floater in [6, 7, 8, 9]. Specically, we describe the procedure for a solid whose boundary is a surface of genus 0; i.e. a surface that is homeomorphic to the surface of a sphere. In this case, the meccano is a single cube, and the global mapping is the combination of six patch-mapping. The solution to several compatibility problems on the cube edges will be discussed. The extension to more general solids is possible if the construction of an appropriate meccano is assumed. In the near future, more eort should be made in an automatic construction of the meccano when the genus of the solid surface is greater than zero. Currently, several authors are working on this aspect in the context of polycube-maps, see for example [25, 19, 27]. They are analyzing how to construct a polycube for a generic solid and, simultaneously, how to dene a conformal mapping between the polycube boundary and the solid surface. Although surface parametrization has been extensively studied in the literature, only a few works deal with volume parametrization and this problem is still open. A meshless procedure is presented in [18] as one of the rst tentative to solve the problem. In addition, Floater et al [10] give a simple counterexample to show that convex combination mappings over tetrahedral meshes are not necessarily one-to-one. In the following Section we present a brief description of the main stages of the method for a generic meccano composed of polyhedral pieces. In Section 3 we analyze the algorithm in the case that the meccano is formed by a simple cube. In Section 4 we show test problems and practical applications which illustrate the eciency of this strategy. Finally, the conclusions and future research are presented in Section 5.

2 Meccano Technique Algorithm
The main steps of the meccano tetrahedral mesh generation algorithm are summarized in this Section. A rst approach of this method can be found
The Meccano Method for Automatic Tetrahedral Mesh Generation
in [21, 2, 22]. The input data of the algorithm are the denition of the solid boundary (for example a surface triangulation) and a given precision (corresponding to the approximation of the solid boundary). The following algorithm describes the mesh generation approach. Meccano tetrahedral mesh generation algorithm
1. Construct a meccano approximation of the 3-D solid formed by polyhedral pieces. 2. Dene an admissible mapping between meccano and solid boundaries. 3. Construct a coarse tetrahedral mesh of the meccano. 4. Generate a local rened tetrahedral mesh of the meccano, such that the mapping (according step 2) of the meccano boundary triangulation approximates the solid boundary for a given precision. 5. Move the boundary nodes of the meccano to the solid surface according to the mapping dened in 2. 6. Relocate the inner nodes of the meccano. 7. Optimize the tetrahedral mesh by applying the simultaneous untangling and smoothing procedure.
The rst step of the procedure is to construct a meccano approximation by connecting dierent polyhedral pieces. The meccano and the solid must be equivalent from a topological point of view, i.e., their surfaces must have the same genus. Once the meccano is assembled, we have to dene an admissible one-to-one mapping between the boundary faces of the meccano and the boundary of the solid. In step 3, the meccano is decomposed into a coarse tetrahedral mesh by an appropriate subdivision of its initial polyhedral pieces. This mesh is locally rened and its boundary nodes are virtually mapped to the solid surface until it is approximated to within a given precision. Then, we construct a mesh of the domain by mapping the boundary nodes from the meccano plane faces to the true boundary surface and by relocating the inner nodes at a reasonable position. After those two steps, the resulting mesh is generally tangled, but it has an admissible topology. Finally, a simultaneous untangling and smoothing procedure is applied and a valid adaptive tetrahedral mesh of the object is obtained.
3 Meccano Technique for a Complex Genus-Zero Solid

In this Section, we present the application of the meccano algorithm in the case of the solid surface being genus-zero and the meccano being formed by one cube. We assume as datum a triangulation of the solid surface. We introduce an automatic parametrization between the surface triangulation of the solid and the cube boundary. To that end, we divide the surface triangulation into six patches, with the same topological connection than cube faces, so that each patch is mapped to a cube face. We note that even being poor the quality of this initial triangulation, the meccano method can reach a high quality surface and volume triangulation.

Meccano

A simple cube, C, is dened as meccano. We associate a planar graph, GC to the meccano in the following way: Each face of the meccano corresponds to a vertex of the graph. Two vertices of the graph are connected if their corresponding meccano faces share an edge.
Figure 1 shows the numbering of cube faces and their connectivities, and Figure 2 represents the corresponding planar graph.
Fig. 1. Meccano formed by one cube: (a) notation of nodes and faces of the cube and (b) connectivities of faces
Fig. 2. Planar graph GC associated to the cube
The position of the cube is crucial to dene an admissible mapping between the cube and solid boundary, as we analyze later. However, its size is less important, because it only aects the eciency of the mesh optimization step. For a genus-zero solid, if the center of the cube is placed inside the solid, the existence of an admissible mapping is ensured.
Mapping from Cube Faces to Solid Surface Patches
Once the cube is xed, we have to determine a mapping between the cube faces and the solid surface triangulation. First, we dene the concept of admissible mapping for a cube. Let C be the boundary of the cube and S the boundary of the solid, given by a surface triangulation TS. We denote i i by C the i-th face of the cube, i.e. C = 5 C. Let : C S be a i=0 i i i i piecewise function, such that |C = where i : C i (C ) S. Then, is called an admissible mapping if it satises:
j i i, j = 0,. , 5, with i = j and C C =. b) Global mapping is continuous and bijective between C and S. j i a) Functions { i }5 are compatible on C. That is | i j = | j i , i=0

C C C C

We dene an automatic admissible mapping in the following Sections. For this purpose, we rst construct a partition of the solid surface triangulation into six patches, maintaining the topology of the graph in Figure 2, then we parametrize each patch to a cube face. Partition of the Solid Surface Triangulation In the following we call connected subtriangulation to a set of triangles of TS whose interior is a connected set. Given a decomposition of the surface triangulation TS in any set of connected subtriangulations, we can associate a planar graph, GS , to this partition in the following way: Each subtriangulation corresponds to a vertex of the graph. Two vertices of the graph are connected if their corresponding subtriangulations have at least one common edge.

We say that a solid surface partition and the meccano are compatible if their graphs are isomorphic, GS = GC. In our case, since the solid surface is isomorphic to a sphere, it is clear that a compatible partition exists. We now propose an algorithm to obtain a decomposition of the given solid surface i triangulation TS into six subtriangulations {TS }5. We distinguish three i=0 steps: a) Subdivision in connected subtriangulations. We construct the Voronoi diagram associated to the centers of the six cube faces. We consider that a triangle F TS belongs to the i-th Voronoi cell if its barycenter is inside this cell. We generate a partition of TS in maximal connected subtriangulations with this criterion, i.e. two subtriangulations belonging to the ij same cell can not be connected. We denote as TS the j-th connected subtriangulation belonging to the i-th Voronoi cell, and ni is the total number of subtriangulation in the i-th cell.
b) Construction of the graph. We associate a planar graph, GS to the partition generated in the previous step. If the center of the cube is inside the solid and the surface triangulation is ne enough, there is one compatible subtriangulation for each Voronoi cell, i.e. there is one head subtriangulai0 tion TS , vertex of the graph GS , with the same connection as the vertex associated to the i-th cube face in GC. Otherwise, the subtriangulation i0 with the greatest number of elements is chosen as TS. c) Reduction of the graph. In order to achieve a decomposition of TS , we propose an iterative procedure to reduce the current graph GS. In each jk i0 step all triangles of TS are included in the head subtriangulation TS if: i0 TS is the head subtriangulation with the fewest number of triangles. jk i0 TS and TS are connected. k is higher than zero. jk Then, the vertex TS is removed from the graph and its connectivities are i0 inherited by TS. The connectivity of the graph is updated. i0 After this process, TS could be connected to other subtriangulations il il TS of the same i-th cell. In this case, the triangles of all TS are included in i0 il TS , the graph vertices TS are removed from the graph, their connectivities are inherited and the graph connectivities are updated. Therefore, the connected subtriangulations are always maximal in all algorithm steps. This procedure continues iteratively until the graph GS is comprised only six head vertices, but the compatibility of GS with GC can not be ensured. As the computational cost of this algorithm is low, a movement i in the cube center, in order to obtain a compatible partition {TS }5 , i=0 does not aect the eciency of the meccano technique. In what follows i i we denote S the solid surface patch dened by the triangles of TS. Parametrization of the Solid Surface Triangulation

Once the given solid surface S is decomposed into six patches S ,. , S , i i we map each surface patch S to the corresponding cube face C by using i the parametrization of the surface triangulations TS proposed by M. Floater 1 i 1 i i i i [6]. So, we dene : S C and we denote F = i (TS ) i i i as the planar triangulation of C associated to TS. To obtain F , Floater parametrization xes their boundary nodes and the position of their inner nodes is given by the solution of a linear system based on convex combii i i i nations. Let {P1 ,. , Pn } be the inner nodes and {Pn+1 ,. , PN } be the i boundary nodes of TS , respectively, where N denotes the total number of i i nodes of TS. Fixed the position of boundary nodes {Qn+1 ,. , QN } of F , i i the position of the inner nodes {Q1 ,. Qn } is given by the solution of the system:

Qi = k

kl Qi , l

k = 1,. , n.

The values of the weights of the convex combinations {kl }l=1,.,N verify k=1,.,n kl = 0, kl > 0,
if Pk and Pl are not connected if Pk and Pl are connected for k = 1,. n.

kl = 1,

In [6] three alternatives are analyzed: uniform parametrization, weighted least squares of edge lengths and shape preserving parametrization. Another choice, called mean value coordinate, is presented in [8]. The goal is to obtain an approximation of a conformal mapping. In order to ensure the compatibility of { i }5 , the boundary nodes of i=0 i 5 {F }i=0 must coincide on their common cube edges. The six transformations { i }5 dene an admissible mapping between C and S , i.e. the cube i=i boundary triangulation F = i=0 F is a global parametrization of the solid surface triangulation TS. Two important properties of mapping are: (a) the triangulations F and TS have the same topology, (b) each triangle of F is completely contained in one face of the cube. We note that usual polycube-maps [25, 19] verify property (a), but they do not verify property (b), i.e., a triangle belonging to TS can be transformed by a polycube-map into a triangle whose vertices are placed on dierent faces of the polycube. The proposed mapping is used in a following step of the meccano algorithm to map a new triangulations K (obtained on C by application of the renement algorithm of Kossaczky [17]) to the solid boundary. Several problems can appear in the application of this transformation due to the fact that a valid triangulation K = F on C can be transformed by into a non-valid one on the solid surface. 3.3 Coarse Tetrahedral Mesh of the Meccano

We build a coarse and high quality tetrahedral mesh by splitting the cube into six tetrahedra [17], see Figure 3(a). The resulting mesh can be recursively and globally bisected to x a uniform element size in the whole mesh. Three consecutive global bisections for a cube are presented in Figures 3 (b), (c) and (d). The resulting mesh of Figure 3(d) contains 8 cubes similar to the one shown in Figure 3(a). Therefore, the recursive renement of the cube mesh produces similar tetrahedra to the initial ones. 3.4 Local Rened Tetrahedral Mesh of the Meccano
The next step in the meccano mesh generator includes a recursive adaptive local renement strategy, by using Kossaczkys algorithm [17], of those tetrahedra with a face placed on a boundary face of the initial coarse tetrahedral
Fig. 3. Renement of a cube by using Kossaczkys algorithm: (a) cube subdivision into six tetrahedra, (b) bisection of all tetrahedra by inserting a new node in the cube main diagonal, (c) new nodes in diagonals of cube faces and (d) global renement with new nodes in cube edges
mesh of the cube. The renement process is done in such a way that the given solid surface triangulation TS is approximated by a new triangulation within a given precision. That is, we seek an adaptive triangulation K on the cube boundary C , so that the resulting triangulation after node mapping (K ) is a good approximation of the solid boundary. The user has to introduce as input data a parameter , which is a tolerance to measure the separation allowed between the linear piecewise approximation (K ) and the solid surface dened by the triangulation TS. At present, we have considered two criteria: the rst related to the Euclidean distance between both surfaces and the second attending to the dierence in terms of volume. To illustrate these criteria, let abc be a triangle of K placed on the meccano boundary, and a b c the resulting triangle of (K ) after mapping the nodes a, b and c on the given solid surface S , see Figure 4. We dene two dierent criteria to decide whether it is necessary to rene the triangle (and consequently the tetrahedron containing it) in order to improve the approximation. For any point Q in the triangle abc we dene d1 (Q) as the euclidean distance between the mapping of Q on S , Q , and the plane dened by a b c. This denition is an estimate of the distance between the surface of the solid and the current piecewise approximation (k ). We also introduce a measure in terms of volume and then, for any Q in the triangle abc, we dene d2 (Q) as the volume of the virtual tetrahedron a b c Q. In this case, d2 (Q) is an estimate of the lost volume in the linear approximation by the face a b c of the solid surface. The threshold of whether to rene the triangle or not is given by a tolerance i xed by the user. We note that other measures could be introduced in line with the desired approximation type (curvature, points properties, etc.). The renement criterion decides whether a tetrahedron should be rened attending to the current node distribution of triangulation K on the cube boundary C and their virtual mapping (K ) on the solid boundary S. The separation between triangulations (K ) and (F ) = TS is used in the renement criterion for tetrahedron T :

Renement criterion

Tetrahedron T is marked to be rened if it satises the following two conditions: 1. T has a face F K on the cube boundary. 2. di (Q) i for some node Q F located on face F of T.
From a numerical point of view, the number of points Q (analyzed in this strategy) is reduced to the set of nodes of the triangulation F (dened by the parametrization of Floater) that are contained in face F. We use the nested mesh genealogy to implement the renement criterion eciently. Finally, the renement procedure for constructing a local rened tetrahedral mesh of the meccano is summarized in the following algorithm: Renement procedure
1. Given the coarse tetrahedral mesh of the meccano. 2. Set a tolerance i. 3. Do a) Mark for renement all tetrahedra that satisfy the renement criterion for a distance di and a tolerance i. b) Rene the mesh. While any tetrahedron T is marked.

P a b c

b P c b P
(b) Fig. 4. Node mapping from meccano to real domain: (a) mapping from external nodes a, b, c, P to a , b , c , P , and (b) relocation of an inner node P in P
We denote nb the number of levels of the nested tetrahedral mesh sequence and K the resulting triangulation of the cube boundary associated to the nest level of the sequence. We note that the renement procedure automatically concludes according to a single parameter, i.e. i. 3.5 External Node Mapping on Solid Boundary
Once we have dened the local rened tetrahedral mesh by using the method proposed in the previous Section, the nodes of the triangulation K are mapped to the solid surface. Therefore, the triangulation (K ) is the new approximation of the solid surface. After this process, due to the properties of Floaters parametrization, (K ) is generally a valid triangulation. However, unacceptable triangulations can appear. We have checked that this problem only appear when the mesh size of surface approximation (K ) is the same order than the mesh size of TS. So, if a more precise approximation of the solid surface is demanded to the meccano approximation, a simple solution is to rene the given solid surface triangulation TS. In addition, a tangled tetrahedral mesh is generated because the position of the inner nodes of the cube tetrahedral mesh has not changed. 3.6 Relocation of Inner Nodes

Even if (K ) is an acceptable triangulation, an optimization of the solid tetrahedral mesh is necessary. Since it is better that the optimization algorithm starts from a mesh with as good a quality as possible, we propose to relocate the inner nodes of the cube tetrahedral mesh in a reasonable position before the mesh optimization. Although this node movement does not solve the tangle mesh problem, it normally reduces it. In other words, the resulting number of inverted elements is lower and the mean quality of valid elements is greater. There would be several strategies for dening an appropriate position for each inner node of the cube mesh. The relocation procedure should modify their relative position as a function of the solid surface triangulation before and after their mapping , see Figure 4(b). However, an ideal relocation of inner nodes requires a volume mapping from the cube to the complex solid. Obviously, this information is not known a priori. In fact, we will reach an approximation of this volume mapping at the end of the mesh generation. An interesting idea is to use an specic discrete volume mapping that is dened by the transformation between a cube tetrahedral mesh and the corresponding solid tetrahedral mesh. In practice, a good strategy is: we start meshing the solid by using a high value of (a coarse tetrahedral mesh of the solid is obtained) and we continue decreasing it gradually. In the rst step of this strategy, no relocation is applied. In this case, the number of nodes of the resulting mesh is low and the mesh optimization algorithm is fast. In the
following steps a relocation of inner nodes is applied by using the mapping that is dened by the previous iteration. 3.7 Solid Mesh Optimization: Untangling and Smoothing
The proposed relocation procedure, based on volumetric parametrization, is ecient but does not solve the tangling problem completely. Therefore, it is necessary to optimize the current mesh. This process must be able to smooth and untangle the mesh and is crucial in the proposed mesh generator. The most usual techniques to improve the quality of a valid mesh, that is, a mesh with no inverted elements, are based upon local smoothing. In short, these techniques consist of nding the new positions that the mesh nodes must hold, in such a way that they optimize an objective function. Such a function is based on a certain measurement of the quality of the local submesh, N (v), formed by the set of elements connected to the free node v, whose coordinates are given by x. We have considered the following objective function derived from an algebraic mesh quality metric studied in [16],

K (x) =

where M is the number of elements in N (v), qm is an algebraic quality measure of the m-th element of N (v) and p is usually chosen as 1 or 2. Specically, we have considered the mean ratio quality measure, which for a

2 tetrahedron is q = and for a triangle is q = |S|2 , |S| being the Frobenius |S|2 norm of matrix S associated to the ane map from the ideal element (usually equilateral tetrahedron or triangle) to the physical one, and = det (S). Other algebraic quality measures can be used as, for example, the metrics based on the condition number of matrix S, q = |S||S 1 | , where = 2 for triangles and = 3 for tetrahedra. It would also be possible to use other objective functions that have barriers like those presented in [15]. We have proposed in [4] an alternative to the procedure of [12, 11], so the untangling and smoothing are carried out in the same stage. For this purpose, we use a suitable modication of the objective function such that the it is regular all over R3. It consists of substituting the term in quality metrics with the positive and increasing function h() = 1 ( + 2 + ). 2 When a feasible region (subset of R3 where v could be placed, N (v) being a valid submesh) exists, the minima of the original and modied objective functions are very close and, when this region does not exist, the minimum of the modied objective function is located in such a way that it tends to untangle N (v). With this approach, we can use any standard and ecient unconstrained optimization method to nd the minimum of the modied objective function.
In addition, a smoothing of the boundary surface triangulation could be applied before the movement of inner nodes of the domain by using the procedure presented in [5, 20].

4 Test Examples

We have implemented the meccano technique using:
The parametrization toolbox of the geometry group at SINTEF ICT, Department of Applied Mathematics. The module of 3D renement of ALBERTA code. Our optimization mesh procedure describes in Section 3.7.
i The parametrization of a surface triangulation patch TS to a cube face is done with GoTools core and parametrization modules from SINTEF ICT, available on the website http://www.sintef.no/math software. This code implements Floaters parametrization in C++. Specically, in the following applications we have used the mean value method for the parametrization of the inner nodes of triangulation, and the boundary nodes are xed with chord length parametrization [6, 8]. ALBERTA is an adaptive multilevel nite element toolbox [24] developed in C. This software can be used to solve several types of 1-D, 2-D or 3D problems. ALBERTA uses the Kossaczky renement algorithm [17] and requires an initial mesh topology [23]. The recursive renement algorithm could not terminate for general meshes. The meccano technique constructs meshes that verify the imposed restrictions of ALBERTA relative to topology and structure. In addition, the minimum quality of rened meshes is function of the initial mesh quality. The performance of our novel tetrahedral mesh generator is shown in the following applications. The rst corresponds to a Bust and the second to the Stanford Bunny. We have obtained a surface triangulation of these objects from internet. For both examples, the meccano is just a cube.

Example 1: Bust

The original surface triangulation of the Bust has been obtained from the website http://shapes.aimatshape.net, i.e. AIM@SHAPE Shape Repository, and it is shown in Figure 5(a). It has 64000 triangles and 32002 nodes. The bounding box of the solid is dened by the points (x, y, z)min = (120, 30.5, 44) and (x, y, z)max = (106, 50, 46). We consider a cube, with an edge length equal to 20, as meccano. Its center is placed inside the solid at the point (5, 3, 4). We obtain an initial subdivision of Bust surface in seven maximal connected subtriangulations. In order to get a compatible decomposition of the surface triangulation, we use the proposed iterative procedure to reduce the current seven vertices of the graph i GS to six. Figure 5(a) shows the resulting compatible partition {TS }5. i=0
Fig. 5. (a) Original surface triangulation of the Bust with a compatible partition i {TS }5 after applying our reduction algorithm and (b) the resulting valid tetrahei=0 dral mesh generated by the meccano method
i i We map each surface patch S to the cube face C by using the Floater parametrization [6]. Once the global parametrization of the Bust surface triangulation is built, see Figure 6(a), the denition of the one-to-one mapping between the cube and Bust boundaries is straightforward. Fixing a tolerance 2 = 0.1, the meccano method generates a tetrahedral mesh of the cube with 147352 tetrahedra and 34524 nodes; see Figures 6(b) and 7(a). This mesh has 32254 triangles and 16129 nodes on its boundary and it has been reached after 42 Kossaczky renements from the initial subdivision of the cube into six tetrahedra. The mapping of the cube external nodes to the Bust surface produces a 3-D tangled mesh with 8947 inverted elements; see Figure 7(b). The relocation of inner nodes by using volume parametrizations reduces the number of inverted tetrahedra to 285. We apply the mesh optimization procedure [4] and the mesh is untangled in 2
i Fig. 6. (a) Floaters parametrization of {TS }5 on corresponding cube faces for i=0 the bust application, (b) cube tetrahedral mesh obtained by the meccano method
iterations. The mesh quality is improved to a minimum value of 0.07 and an average q = 0.73 after 10 smoothing iterations. We note that the meccano technique generates a high quality tetrahedral mesh (see Figure 5(b)): only 1 tetrahedron has a quality less than 0.1, 13 less than 0.2 and 405 lees than 0.3. In Figure 7, we display two cross sections of the cube and Bust meshes before and after the mesh optimization. The location of the cube is shown in Figure 7(b). The CPU time for constructing the nal mesh of the Bust is 93.27 seconds on a Dell precision 690, 2 Dual Core Xeon processor and 8 Gb RAM memory. More precisely, the CPU time of each step of the meccano algorithm is: 1.83 seconds for the subdivision of the initial surface triangulation into six patches, 3.03 seconds for the Floater parametrization, 44.50 seconds for the Kossaczky recursive bisections, 2.31 seconds for the external node mapping and inner node relocation, and 41.60 seconds for the mesh optimization. 4.2 Example 2: Bunny

The original surface triangulation of the Stanford Bunny has been obtained from the website http://graphics.stanford.edu/data/3Dscanrep/ , i.e. the Stanford Computer Graphics Laboratory, and it is shown in Figure 8(a). It has 12654 triangles and 7502 nodes. The bounding box of the solid is dened by the points (x, y, z)min = (10, 3.5, 6) and (x, y, z)max = (6, 2, 6). We consider a unit cube as meccano. Its center is placed inside the solid at the point (4.5, 10.5, 0.5). We obtain an initial subdivision of the Bunny surface in eight maximal connected subtriangulations using Voronoi diagram. We reduce the surface partition to six patches and we construct the Floater
Fig. 7. Cross sections of cube (a) and Bust tetrahedral meshes before (b) and after (c) the application of the mesh optimization procedure
Fig. 8. (a) Original surface triangulation of the Stanford Bunny and (b) the resulting valid tetrahedral mesh generated by the meccano method
i parametrization from each surface patch S to the corresponding cube face i C. Fixing a tolerance 2 = 0.0005, the meccano method generates a tetrahedral mesh with 54496 tetrahedra and 13015 nodes. This mesh has 11530
Fig. 9. Cross sections of cube (a) and Bunny tetrahedral meshes before (b) and after (c) the application of the mesh optimization process
triangles and 6329 nodes on its boundary and has been reached after 44 Kossaczky renements from the initial subdivision of the cube into six tetrahedra. The mapping of the cube external nodes to the Bunny surface produces a 3-D tangled mesh with 2384 inverted elements, see Figure 9(b). The relocation of inner nodes by using volume parametrizations reduces the number of inverted tetrahedra to 42. We apply 8 iterations of the tetrahedral mesh optimization and only one inverted tetrahedra can not be untangled. To solve this problem, we allow the movement of the external nodes of this inverted tetrahedron and we apply 8 new optimization iterations. The mesh is then untangled and, nally, we apply 8 smoothing iterations xing the boundary nodes. The mesh quality is improved to a minimum value of 0.08 and an average q = 0.68. We note that the meccano technique generates a high quality tetrahedral mesh: only 1 tetrahedron has a quality below 0.1, 41 below 0.2 and 391 below 0.3. In Figure 9, we display two cross sections of the cube and Bunny meshes before and after the mesh optimization. The location of the cube can be observed in Figure 9(b). The CPU time for constructing the nal mesh of the Bunny is 40.28 seconds on a Dell precision 690, 2 Dual Core Xeon processor and 8 Gb RAM memory. More precisely, the CPU time of each step of the meccano algorithm is: 0.24 seconds for the subdivision of the initial surface triangulation into six patches, 0.37 seconds for the Floater parametrization, 8.62 seconds for the Kossaczky recursive bisections, 0.70 seconds for the external node mapping and inner node relocation, and 30.35 seconds for the mesh optimization.

5 Conclusions and Future Research
The meccano technique is a very ecient mesh generation method for creating adaptive tetrahedral meshes of a solid whose boundary is a surface of genus 0. We highlight the fact that the method requires minimum user intervention
and has a low computational cost. The procedure is fully automatic and it is only dened by a surface triangulation of the solid, a cube and a tolerance that xes the desired approximation of the solid surface. In addition, the quality of the resulting meshes is high. The denition of an automatic parametrization of a solid surface triangulation to the meccano boundary is a signicant advance for the method. To that end, we have introduced an automatic partition of the given solid surface triangulation for xing an admissible mapping between the cube faces and the solid surface patches. In future works, the meccano technique can be extended for meshing a complex solid whose boundary is a surface of genus greater than zero. In this case, the meccano can be a polycube or a set of polyhedral pieces with compatible connections.

Acknowledgments

This work has been supported by the Secretara de Estado de Universidades e Investigacin of the Ministerio de Ciencia e Innovacin of the Spanish o o Government and FEDER, grant contracts: CGL2008-06003-C03.

References

1. Bazilevs, Y., Calo, V.M., Cottrell, J.A., Evans, J., Hughes, T.J.R., Lipton, S., Scott, M.A., Sederberg, T.W.: Isogeometric analysis: Toward unication of computer aided design and nite element analysis. In: Trends in Engineering Computational Technology, pp. 116. Saxe-Coburg Publications, Stirling (2008) 2. Cascn, J.M., Montenegro, R., Escobar, J.M., Rodr o guez, E., Montero, G.: A new meccano technique for adaptive 3-D triangulations. In: Proc. 16th Int. Meshing Roundtable, pp. 103120. Springer, Berlin (2007) 3. Carey, G.F.: Computational grids: generation, adaptation, and solution strategies. Taylor & Francis, Washington (1997) 4. Escobar, J.M., Rodr guez, E., Montenegro, R., Montero, G., Gonzlez-Yuste, a J.M.: Simultaneous untangling and smoothing of tetrahedral meshes. Comput. Meth. Appl. Mech. Eng. 192, 27752787 (2003) 5. Escobar, J.M., Montero, G., Montenegro, R., Rodr guez, E.: An algebraic method for smoothing surface triangulations on a local parametric space. Int. J. Num. Meth. Eng. 66, 740760 (2006) 6. Floater, M.S.: Parametrization and smooth approximation of surface triangulations. Comp. Aid. Geom. Design 14, 231250 (1997) 7. Floater, M.S.: One-to-one Piece Linear Mappings over Triangulations. Mathematics of Computation 72, 685696 (2002) 8. Floater, M.S.: Mean Value Coordinates. Comp. Aid. Geom. Design 20, 1927 (2003) 9. Floater, M.S., Hormann, K.: Surface parameterization: a tutorial and survey. In: Advances in Multiresolution for Geometric Modelling, Mathematics and Visualization, pp. 157186. Springer, Berlin (2005)

10. Floater, M.S., Pham-Trong, V.: Convex Combination Maps over Triangulations, Tilings, and Tetrahedral Meshes. Advances in Computational Mathematics 25, 347356 (2006) 11. Freitag, L.A., Knupp, P.M.: Tetrahedral mesh improvement via optimization of the element condition number. Int. J. Num. Meth. Eng. 53, 13771391 (2002) 12. Freitag, L.A., Plassmann, P.: Local optimization-based simplicial mesh untangling and improvement. Int. J. Num. Meth. Eng. 49, 109125 (2000) 13. Frey, P.J., George, P.L.: Mesh generation. Hermes Sci. Publishing, Oxford (2000) 14. George, P.L., Borouchaki, H.: Delaunay triangulation and meshing: application to nite elements. Editions Hermes, Paris (1998) 15. Knupp, P.M.: Achieving nite element mesh quality via optimization of the jacobian matrix norm and associated quantities. Part II-A frame work for volume mesh optimization and the condition number of the jacobian matrix. Int. J. Num. Meth. Eng. 48, 11651185 (2000) 16. Knupp, P.M.: Algebraic mesh quality metrics. SIAM J. Sci. Comp. 23, 193218 (2001) 17. Kossaczky, I.: A recursive approach to local mesh renement in two and three dimensions. J. Comput. Appl. Math. 55, 275288 (1994) 18. Li, X., Guo, X., Wang, H., He, Y., Gu, X., Qin, H.: Harmonic Volumetric Mapping for Solid Modeling Applications. In: Proc. of ACM Solid and Physical Modeling Symposium, pp. 109120. Association for Computing Machinery, Inc. (2007) 19. Lin, J., Jin, X., Fan, Z., Wang, C.C.L.: Automatic polyCube-maps. In: Chen, F., Jttler, B. (eds.) GMP 2008. LNCS, vol. 4975, pp. 316. Springer, Heidelberg u (2008) 20. Montenegro, R., Escobar, J.M., Montero, G., Rodr guez, E.: Quality improvement of surface triangulations. In: Proc. 14th Int. Meshing Roundtable, pp. 469484. Springer, Berlin (2005) 21. Montenegro, R., Cascn, J.M., Escobar, J.M., Rodr o guez, E., Montero, G.: Implementation in ALBERTA of an automatic tetrahedral mesh generator. In: Proc. 15th Int. Meshing Roundtable, pp. 325338. Springer, Berlin (2006) 22. Montenegro, R., Cascn, J.M., Escobar, J.M., Rodr o guez, E., Montero, G.: An Automatic Strategy for Adaptive Tetrahedral Mesh Generation. Appl. Num. Math. 59, 22032217 (2009) 23. Schmidt, A., Siebert, K.G.: Design of adaptive nite element software: the nite element toolbox ALBERTA. Lecture Notes in Computer Science and Engineering, vol. 42. Springer, Berlin (2005) 24. Schmidt, A., Siebert, K.: ALBERTA - An Adaptive Hierarchical Finite Element Toolbox, http://www.alberta-fem.de/ 25. Tarini, M., Hormann, K., Cignoni, P., Montani, C.: Polycube-maps. ACM Trans. Graph 23, 853860 (2004) 26. Thompson, J.F., Soni, B., Weatherill, N.: Handbook of grid generation. CRC Press, London (1999) 27. Wang, H., He, Y., Li, X., Gu, X., Qin, H.: Polycube Splines. Comp. Aid. Geom. Design 40, 721733 (2008)

A complete list of validation sites has to be provided in the Supplementary Informations - Form S.6 See annexed list of regions 3 Please use ISO country codes as described in annexed notes V2 : 30 July 97

Co-ordinator:

Name of Institution/Organisation University College London City + Postal Code London, WC1E 6BT Region1 UK55 Country 2 GB
Contact person from the Co-ordinating Contractor:
Title, First Name, Name Tel: E-mail 1: Professor Peter Kirstein +44 (0)7286 Kirstein@cs.ucl.ac.uk Address: Fax: E-mail 2: University College London Gower Street London WC1E 6BT +44 (0)1397

Other Contractors:

Participants Code3 Name of Institution/Organisation City + Postal Code Region1 Country 2
C2 C3 C4 C5 C6 C7 C8 A1.1 A6.1 A7.1 A7.2 A7.3 A8.1
Academic Computer Centre CYFRONET Communications Research Centre Hewlett Packard Limited Institut National de Recherche en Informatique et Automatique Universitetet i Oslo Universitaet Stuttgart TELES GmbH School of Slavonic and East European Studies, UCL New Learning AS Universitaet Erlangen-Nuernburg Universitaet Freiburg Universitaet Mannheim Universitaet Bremen
Krakow 30-950 Ottawa K2H 8S2

Bracknell

N/a N/a UK52 FR82 N/a DE11 DE301 UK55 N/a DE22 DE13 DE126 DE5
PL CA GB FR NO DE DE GB NO DE DE DE DE
Sophia Antipolis 06902 Oslo 0378 Stuttgart 70174 Berlin 10587 London

WC1E 6BT

Oslo 0371 Erlangen 19058 Freiburg i. Br. Mannheim Bremen
See annexed list of regions Please use ISO country codes as described in annexed notes Codes for the participant roles are as follows: C1 = Co-ordinator; C = Contractor; A = Associate contractor
A.2 - Budget Summary Information
Acronym - Title MECCANO : Multimedia Education & Conferencing Collaboration over ATM Networks & Others
Human Resources Summary (Person-month)
Total Resources of funded1 Contractors Total Resources of funded Associated Contractors Total Resources of funded Subcontractors Subtotal Resources of funded Participants
Total Resources of non-funded2 Contractors Total Resources of non-funded Associated Contractors Total Resources of non-funded Subcontractors Total Resources of Sponsoring Partners

258 36

Cost Summary in KECU

Participants Code3

Personmonth4
1. Personnel 2. Equipment 3. Third Party Assistance (subcontractors) 4. Travel and Subsistenc e 5. Consumables and Computing 6. Other significant Specific Project Cost 7. Overheads
% of EU5 Contribution % FC AC

EU Contribution

C1 A 1.1. Subtotal 1 C2 C3 C4 C5 C6 A 6.1 Subtotal 6 C7 A 7.1 A 7.2 A 7.3 Subtotal 7 C8 A 8.1 Subtotal 8 Total

The interest in network multimedia does not need to be made in this proposal. It is evident from the numerous work items both in many national programmes, and in the three EC Programmes ESPRIT, Telematics and ACTS, that the need has been accepted. Nevertheless, there is a need to discuss why the sort of project proposed here under MECCANO is needed. In the ESPRIT Programme, the whole of Domain 3 addresses multimedia systems; however the main emphasis is on the provision of the systems, with appropriate standards and interfaces. Multimedia pilots in specific environments are envisaged - but mainly as proof that the systems are commercially viable. The services are a major aspect of Area 1 in the ACTS programme; here much very useful work will be done - particularly to develop the services in the context of the BISDN. The same technologies pervades the workplans of the Telematics Programme; most of the sectors have some aspect of multimedia services in them. In this project we will be addressing the user needs as they have already been recognised not only by different sets of users of the Telematics MERCI project, but also by potential groups in the Research and Education & Training areas. The technology has much wider ramifications, but it is only these that we have targeted in the Validation workpackages. Because of the target user groups identified, this proposal addresses the open call for RE 2.1 real-time interactive multimedia collaboration. However wide deployment and good quality collaboration depends vitally on having advanced network access and proper management both of resource and quality of service; for this reason, the proposal addresses also RE 1.2 validation of access methods to advanced communication services and RE 1.3 managing the network as a resource. These items are not being addressed in an official Call at this time, nevertheless they are being addressed here of necessity; good performance multimedia conferencing cannot be addressed separately from the underlying network infrastructure, and the middleware between the network and the multimedia tools. Several current projects e.g. MERCI and MATES address multimedia conferencing. However, in MATES the conferencing technology is secondary. MERCI has been addressing the technology, but many vital areas have not been resolved. Moreover, there have been important developments in standards, networks, applications funded from other bodies which should be incorporated into a full networked multimedia conferencing and seminar system. Other ACTS projects have tackled the same area; however in these the emphasis has been on high speed conferencing using the B-ISDN; they have not tackled the same heterogeneous network environments targeted first by MERCI and now by MECCANO.

2.2 Knowledge of sector and technologies to be used
2.2.1 The International State-of-the-art on Networked Multimedia Conferencing. Packet networks are becoming more suitable for network multimedia. The emerging generation of Internet facilities, in which the backbone services have a lower limit of 34 Mbps, and a higher end limit soon pushing the Gbps range, is fully suitable for wide-area distribution. In the MERCI project we have shown the feasibility of connecting in limited facilities over narrow-band ISDN, supporting good quality facilities at 1.5 Mbps speeds, and distributing the multimedia cheaply over DBS satellites. In ACTS projects like ATHOC, and in commercial services like AT HOME, the potential of two-way multimedia using cable TV plant is being demonstrated. Pilot networks like TEN-34, JAMES, SuperJANET and CAIRN are starting to demonstrate that multicast is a viable technology - as evidenced by the increasing availability of resource reservation in commercial routers. These developments are still in the proofs of concept state; it is only from projects like this one that deployable systems will emerge. Chips for workstations are becoming faster at affordable cost. Recent Codec chipsets and multimedia instruction extensions will ensure very economic multimedia facilities - even current generation PCs and workstations operating in the range of 200 MHz can decode all the algorithms, and encode many, at full motion quality and in real-time. New developments in IR and in smart cards ensure that these two functions will become standard on the PCs deployed later in 1998. In North America, 1-1.5 Mbps transmission speeds are already affordable over the local and wide-area - with higher speed aggregation becoming very attractive into and out of larger sites. Of course, there will continue to be pressure to reduce all costs. For this reason, we expect that many organisations will continue to want to reduce the bandwidth used for videoconferences to less than 300 Kbps for larger meetings and to less than 100 Kbps for desktops in the wide area - even at the cost of video quality. Growth in switched Ethernet hubs, UTP-5 wiring, low cost, higher speed 100baseT and cable TV technologies have made local distribution of multimedia relatively straightforward. Improvement of video projectors, working directly from workstations, has reduced greatly the cost of conference rooms. Even audio problems are being resolved by good quality headsets for workstation operation and affordable echo cancellation in conference rooms. Single channel Basic Rate ISDN for circuit-switched networks has been available for some years; only now are workstations and PCs able to support both channels; reasonable cost equipment for 6 and 30 channel ISDN is available, but the cost of operating many channels is high. With improved codecs, less demanding applications can now be satisfied with two-channel ISDN. The protocols supported on most ISDN boards available (PCs) have not been compatible with those on the packet networks, but this is changing: more PC software now supports IP, and ISDN gateways are becoming available which support the common ISDN protocol structures. The workstation and communications suppliers realise that the H.320 protocols, adopted earlier by the carriers for multimedia working on the ISDN, are incompatible with both the Internet and with Local Area Network distribution; their recent H.323 family is much more appropriate and is well adapted to MBONE packet working. It is no coincidence that Intel and Microsoft are very active in both the IETF and ITU-T committees. There are still significant differences between the MBONE and the ITU-T protocol structures. Early gateways between the two are available from the MERCI project; further development of these gateway facilities is still required - partly because the two communities are still evolving their standards. Video Servers are being developed frantically to meet an expected video-on-demand market. The WGs developing standards for video-conferencing are also addressing the video server standards - enabling the use some of video servers in broader environments. Many such servers have the requisite hardware base needed for this project - but the software facilities are less flexible than we require. We will collaborate in this project with several manufacturers wishing to enter also this market. Many providers of workstations and network components understand the need to incorporate security features. Providing a light level of security is easy, but this may not meet serious demand. Stronger security, using Public Keys and DES, is wanted - but regulatory considerations still impede the introduction of secure products on a world scale - thus constraining the growth of such products. Nevertheless, smart cards will become standard features in some PCs next year; both organisations like Verisign and Nortel in North America, and projects like ICETEL in Europe, are showing that a full security infrastructure could be

Multimedia servers require further development. Some products now provide adequate video-ondemand even compatible with current MBONE standards. The major WWW suppliers and Software companies are collaborating in the IETF MMUSIC Working Group in advancing RTSP; this still needs to be related to the DAVIC initiative. Much work is still needed in the browsing and indexing of the server data. Many products are being integrated with WWW facilities. MBONE multicast facilities are much more flexible that the ITU-T H.320 MCU ones; the newer activities with H323 look very hopeful, and the early interworking gateways have demonstrated proof of concept. Much more work on gatewaying between the two worlds is essential; Many new products are emerging based on the H.323 recommendations; this is further strengthening the need for interworking with the Internet family; Compatibility with the equipment manufacturer Standards is vital. Nevertheless validation for these standards is needed from projects like MERCI and MECCANO - particularly in real demonstrators over the research networks. Problems remain with conference room technology; multiway transmissions and variable delays of the media streams present particular problems. Standards in wide-area conference room control facilities will impact standards for the whole of the conference room equipment.
2.4.4 Relevant References 1. Bolot, et al: Adaptive Error Control for Packet Video in the Internet, Proc. ICIP'96, Lausanne, Switzerland, 96. 2. Bolot, et al.: Control mechanisms for packet audio in the Internet, Proc. IEEE Infocom '96, San Francisco, CA, April 96. 3. Hinsch, et al.: Secure Conferencing User Agent: A Tool to Provide Secure Conferencing with MBONE Multimedia Conferencing Applications, Proc JENC7, Budapest, May 96 4. Unsupported MERCI Software http://ugwww.ucs.ed.ac.uk/mice/archive/ 5. Supported MERCI Software: ftp://ftp.ucs.ed.ac.uk/pub/videoconference/ 6. Kouvelas, et al, Lip Synchronisation for use over the Internet, Analysis and Implementation", in Proceedings of IEEE Globecom'96, November 1996, London, UK. 7. Hardman,.et al " Enhanced Reality Audio in Interactive Networked Environments", in Proceedings of the Framework for Interactive Virtual Environments (FIVE) conference, December 1996, Pisa Italy. 8. Kouvelas, et al.: Overcoming Workstation Scheduling Problems in a Real-Time Audio Tool", in Proceedings of Usenix Annual Technical Conference, January 1997, Anaheim, California 9. Sasse, A. et al: Multimedia Conferencing for Remote Language Teaching over SuperJANET, Computer Assisted Language Learning, Volume 9, Number 2-3, 1996, p.99-105 10. Kirstein, P. et al: Security Requirements and Mechanisms for Multimedia Conferencing, Proc. JENC8, Edinburgh, 1997 11. Kirstein, P. et al: Recent Activities in the MERCI Conferencing Project, Proc. JENC8, Edinburgh, 1997

2.6 Exploitation Plan

2.6.1 The Partners Exploitation by the partners will vary, of course, depending on the nature of the partner. As a very new SME, New Learning AS is already using results from the MERCI project in current products, and expects to learn from many parts of the MECCANO project in a way which will enable them to produce better and more appropriate products. The uniqueness of this multimedia conferencing over wide area European networks will provide valuable experience, and should develop software which will be a
basis for products; we expect to be able to test internally developed software with software developed by other partners of the project, and derive real products. TELES has a straightforward path to commercial application of MECCANO technology into its prudcuts. It is interested in products using conventional PSTN/ISDN equipment (e.g. H.3xx PCs and videophones) to access Mbone/Internet-based services - bypassing ISP bottlenecks. The results of MECCANO (gateways, tools, and operational experience) are going to provide an important part of the foundations for products in the above area - in terms of services as well as equipment. HP is interested in the use of the tools and the associated project outputs across its own enterprise network for personnel support facilities. It is also a major contributor via its philanthropy programme to promote educational facilities at all levels of education; it anticipates that initial exploitation will be most effective in that area. The current project is based on the use of an open environment to achieve wide-scale interoperability. Such a programme is based on the use of tools, many of which have been made available in the public domain. Full commercial exploitation of the outputs from this project will involve the need to resolve the IPR issues arising from this aspect. INRIA derives an appreciable proportion of its income from industrial contracts and from license fees. It will support Dassault Electronique in using the MECCANO tools as a basis for building other training and collaboration tools, and SGS-Thomson in their use of MECCANO shared postscript/pdf viewer as a remote collaboration tool between sites in Crolles (near Grenoble), Italy, and India. That viewer will include reliable multicast transmission, with specific functions like rotate and zoom, etc. - coupled with the MERCI audio tool (FreePhone) and text tool (NTE). INRIA will work closely with the EUTELSAT partner on the DBS activity, who clearly intend to use the MECCANO scenarios in service offerings. We expect that other MECCANO tools will lead to direct commercial licences. CRCs role is slightly different. Its exploitation role is more to promulgate the use of the underlying communications technologies, and encourage wide dissemination to any Canadian industrial partners desiring to provide products; it has no immediate plans to pursue products from MECCANO - merely to encourage the widespread take-up of this important technology in the government and industry. ACCs primary role is to provide advice and services to academia and industry in the Krakow area. Thus its main exploitation route will be to introduce the MECCANO technology into the area, and to encourage its wider take-up both inside Poland and between Poles and other countries. It may decide to commercialise specific tools in conjunction with local industry, but this has not been decided. All the research partners plan to exploit the MECCANO technology for distance learning, seminars and personal collaboration. An important exploitation route for all of them is the direct production of research papers, and the basis the results give for future projects. In this case, the close involvement in MECCANO of the national research networks in Germany, Norway and the UK will ensure that the output is immediately exploited throughout the national academic and research communities; in view of the close European ties of these countries, this means also throughout European academia. Each of the partners have additional routes to exploit the results into products. BU is working directly with TELES, who would provide the exploitation route. RUS is introducing the technology in industrial ACTS and ESPRIT projects, and is working closely with companies such as Aerospatiale, Le and Mureaux to introduce the technology into their sectors. Oslo U started NL as a spin-off; that will provide its product exploitation route. UCL works closely with many companies, including HP. It has started spin-offs in the past, and has also licensed its technology to many companies. It expects its primary exploitation path will be via consulting; some may also be by direct licensing. 2.6.2 The Users This project will have strong impact on the users. First, many users have access to different networks as part of their research or commercial activity; they will be able to use their normal networks for these advanced services. Their organisations normally have a specific procurement policy - be it PCs or UNIX workstations; that the same platform can be used for multimedia conferencing has strong impact on the support requirements and investment decisions needed inside the organisation - and hence on the ease with which the technology can be introduced. At present the ITU-T and Mbone users who do conferencing cannot interwork; the advanced facilities, multi-platform and multi-network environment proposed here will improve the Mbone environment, and remove much of the interworking barrier. There are already many specific conferencing products; most are much more limited in their approach to security, incorporation of servers and control functionality. Without the security aspect, there are many application areas which cannot be addressed. The present approach, which is compatible with that in the Internet research community, supports much more flexible and comprehensive services; moreover the secured products could not be imported into Europe under the present US export laws.

2.6.3 The Suppliers Suppliers are interested in this activity because of its potential impact in many of their products. From workstation manufacturers, we have had considerable support - because of their interest in seeing the technology developed further. The commercial MECCANO partners have made their interest clear above. Many more commercial companies have expressed their interest by working with one of the research or university MECCANO partners. During the MERCI period, this interest has led to contracts, consultancies, donations, sponsoring partnerships in MERCI and licensing. For example HP has moved from a sponsoring partner (with substantial donations to the MECI partners) to full partner in MECCANO, EUTELSAT has moved from interested outsider to sponsoring partner, GPT proposed a full ESPRIT project to develop the MERCI technology further. There is no doubt that the technology is fast moving from prototype to product. MECCANO will not only embrace one product; several projects are proposing to take pieces of the technology developed here and emphasise specific areas. One plans to develop the mobile access, several to exploit the teaching/training environment, yet others specific workstation products. Several are eyeing our network experience closely; intending to incorporate our control strategies into their products. 2.6.4 Business Plan In view of the basic nature of the many technologies incorporated in this project, and the variety of partners, it is inappropriate to formulate a central business plan. This will be pursued by the partners in accordance with their natural commercial alliances. We will not form a single MECCANO company as a result of this work; but do expect to spawn a number of products in associated companies.

2.7 European Added Value

The value of doing the Project on a European Basis Some aspects of the MECCANO work are easier to achieve nationally; e.g. during the MERCI project, we have had significantly better national network connectivity than international. Both technical and political considerations have made connectivity to some countries difficult in the past - but MECCANO is addressing this problem. Moreover, it is very clear from the other European projects in which the partners are involved, that the international benefits are huge: Many applications are pan-European; the benefits are related to the numbers and dispersal of users; The availability of the requisite skills are not found easily in one country; The multinational nature ensures that national constraints do not limit the technological development; The project brings in tools which have been developed under different national and EC initiatives. The Potential Impact on European Economic and Social Policies The availability, and wide deployment, of this technology will have an integrating effect that cannot yet be fully appreciated. This will be in full support of the information society in Europe and of the European Union policies. Moreover, the way that the multimedia technology plans to embrace most of the underlying network technologies will have several important consequences: It is applicable to application sites without the latest, most expensive, communications infrastructures; it will, however, be able to utilities the latest infrastructure as it becomes available (cf. MERCI); It will act as a searching probe to discover weaknesses in the European communications infrastructure even though it will continue to be able to operate at reduced performance. The Contribution to the European Information Society It is difficult to envisage a project which has a greater impact on the Information society, than one which aims to provide: Audio, visual and shared application collaboration with users irrespective of location or application; Capability of working with most current communications technologies and end-user platforms; Addresses applications areas which are well-nigh universal in their impact.

Project ref. Acronym MECCANO Date September 1,1997 Sheet 2 of 9

WP ID 2

Work Package TITLE: Activity with External Groups START END 24 TOTAL KECU DUR 115 24
Objectives: The Objective of this work-package is to ensure that all activities concerned with external groups are adequately staffed, carried out and funded.
Work Description: There are a number of separate external interactions of the Project with the outside world. Under this work-package we include the following: concertation activities, interaction with user groups, annual reviews, dissemination activities, production of information activities, and collaboration with other projects; each will be considered below. We will participate in concertation meetings, at which the project partners will be represented. We will have very strong ties with the ICE-CAR and PROSPECT project, and will extend these to others when the next batch of Telematics projects start. These will include joint meetings with these projects - probably organised around the concertation meetings. The Project Manager of SCIMITAR will be invited also to attend these joint project meetings. We will have a joint in-depth study of what each project has to offer to the others, and will provide documents detailing what products each expects to provide to the others. In the joint meetings we will review progress in these promised products - flagging potential delay or shortfall in specifications. After delivery of the products to other projects, we will expect feedback from them and we will provide feedback to other projects. Of course we will provide the relevant material, and participate in, the annual reviews - whether they are organised directly by the Commission or via the SCIMITAR project. The support by the project partners of the User Groups will be an integral part of WP9. We expect considerable interaction with both our Sponsoring Partners and other User Groups who also will wish access to the MECCANO products. We will organise publicity material, documentation, and limited information and training meetings with such groups. While the initial responsibility for documentation is with the component provider, the production of appropriate external technical documentation will be carried out under this work-package. The MERCI project was particularly strong in presenting its activities at public demonstrations, conferences and in journal articles. We expect to carry on this tradition into the MECCANO project; of course we will strive to present our results at the relevant meetings organised by the Telematics Programme or the SCIMITAR project; we expect also to participate in important other events such as the Joint European Network Conferences, the Internet Society Conferences, and the Telematics Application Conferences and Exhibitions. Finally, while presentations at conferences provide substantial short-term exposure, it does not replace publication in the learned journals; we expect to provide material for conferences to such a standard that the organisers will wish it to be reproduced in the journals which often publish the best conference papers, and will also submit papers independently to the relevant journal editors. It is relatively straightforward to develop products and services to meet specific narrow needs; it is much more complex to develop them in a way that inter-operates with products developed in other projects or by other vendors. We will ensure that our activities align with ITU-T and IETF Standards where feasible. We expect, through this work-package, to retain our participation with the relevant co-ordination and standardisation groups. Deliverables: R2 Publications, publicity material as requested by the Commission or required for conferences, annual reviews, documentation for user groups, IETF and ITU-T submissions, and for other projects.

Work Package TITLE: Network Support START END 24 TOTAL KECU DUR 396 24

Sheet 5 of 9

WP ID 5
WP LEAD C7 TOTAL Person/Month
Objectives: To ensure that the tools operate over a wide range of interconnected, heterogeneous technologies: LAN, B-ISDN, SMDS, packet-switched medium speed networks, ATM (including the JAMES pilot), Direct Broadcast Satellite (DBS), ISDN and mobile - with adequate QoS. In this context, it will also provide tools to measure the QoS, and to manage interconnection resources to achieve adequate performance. Work Description: It is important that the different components work over a variety of network technologies and that QoS can be monitored and maintained over concatenated networks. In MECCANO, IP will be used as an intermediate layer; many of the technologies provide specific considerations. A key problem with multimedia applications is their dependence on the QoS, provided by the underlying infrastructure. We may need to pilot the protocols that ensure that the relevant resource management and routing can be achieved. A5.1 Support for Network Technologies For this we must acquire Drivers for different network technologies, including: packet-switched IP, ISDN, DBS and mobile - both in PCs and workstations under UNIX and with Microsoft Windows/NT support. For each combination of network technology we see a need to: pilot and verify the topology, set up the technology infrastructure, understand how to provide multicast and adequate QoS support. During the lifetime of MECCANO, the new IPv6 will allow new Internet services (provided by QoS allocation schemes in routers). Since this subject was removed from the next Telematics Call, we must provide a reasonable QoS; we will investigate providing this with IPv6, RSVP and CBQ protocols which promise a large payback in the dynamic reservation of network resources. A number of advances are needed to construct managed, high-performance, virtual Mbones able to communicate with average performance public Mbones. We will continue the current RSVP MERCI pilots on a much larger scale than hitherto with the assurance of the active collaboration of the JAMES consortium, the TEN-34 project and of a number of national research networks several of whom are specifically supporting MECCANO. Here our JAMES link to Canada and the UCL CAIRN link to the US ensure that the scope is truly international. Provision of mobile network support is part of several National projects; the technology from these projects will be introduced to MECCANO. The DBS activity requires both active collaboration with EUTELSAT, a sponsoring partner, and work on the relevant protocols. A5.2 Network and Applications Monitoring To achieve high quality multimedia performance, in multicast environments, we will make detailed measurements within applications, gateways, routers, and network switches. Correlation between network behaviour and user acceptance will help achieve required QoS. A detailed measurement and monitoring programme, begun in the MERCI project, in collaboration with both the TEN-34 and JAMES projects, will be continued over the heterogeneous MECCANO systems. We will integrate this activity both with work by the national networks, and with the international activity under the CCIRN working groups. The importance of this work has been recognised by the establishment of relevant IETF working groups, in which we will participate under MECCANO. This work will be co-ordinated also with the work in NICEGlobal, GIBN, MAY and CA*Net II - in each of which at least one MECCANO partner participates. Via WP4 and W6, we will incorporate measurement and monitoring facilities into the components, gateways and relays. The insights gained with the measurements will help determine the correct parameters needed for the design of the following: efficient hierarchical audio and video coding schemes, gateways and relays, the impact of wireless links compared to wireline ones (quite different loss characteristics), the parameters in traffic shaping, in the requests for bandwidths in VPs, and in the way that RSVP reservations are required. Deliverables: R5.1 Support for network technologies in the MECCANO Tools. R5.2 Performance Characteristics of the MECCANO system and their effect on system parameters.

Deliverables D7.1 The Session Announcement and Management Facilities in MECCANO Release 1 D7.2 The Session Announcement and Management Facilities in MECCANO Release 2.
Project ref. Acronym MECCANO Date September 1,1997 Sheet 8 of 9

WP ID 8

Work Package TITLE: Consolidation of Applications START END 24 TOTAL KECU DUR 267 21
WP LEAD C6 TOTAL Person/Month
Objectives: While the majority of the validation and demonstration of our techniques is accomplished in other projects, some must be carried out inside the project. The objective in this workpackage is to consolidate and run a number of validation activities from inside the project. These will be used to validate the quality and acceptability of the technology for different applications and user communities, to assess the relative value of the different tools and to propose changes for subsequent work inside and outside the project. Work Description: A number of specific validation activities will be carried out inside the project; at the suggestion of the Reviewers, these will mainly concern seminars, and will consolidate existing applications. Most of the costs will be met from National or Institutional funding, but some MECCANO funding will be made available by the partner most associated with the pilot groups. The choice of pilots is not arbitrary; it is based on activities with which the participating parties are already associated and which will validate specific aspects of the total MECCANO system. One aim is to validate a component, a second is to validate its applicability in an application area and a third is its dissemination to a user community. The participating national research networks operators, CA*Net II, DFN, SuperJANET and UNINETT want to assess the value of the technology, and its impact on operations. Clearly EUTELSAT has a similar interest on the use of Direct Broadcast Satellite networks in this mode. The different validation activities will adopt different assessment criteria. Some will be subjective, merely that the audience are satisfied, or that the participants have the necessary facilities over the relevant networks; others will be objective, e.g. that the sponsors will proceed to larger scale trials - indicating both.the user acceptance and the cost effectiveness in that application. The applications sites will be mainly in universities, hence the financial commitment to the infrastructure is hard to quantify. Often it is part of the whole research infrastructure, or even, in the DBS case, includes the underwriting of a whole satellite-based system. All MECCANO partners will participate in a regular series of seminars. These will be demonstrating high performance multimedia, by setting up a higher quality Mbone than would be possible over the normal service network using the successor to the JAMES network. This seminar series will include Computer Science, Experimental Cardiology, Health Care, Surgery, Telecommunications and various technological subjects. The common seminar series activity will be supplemented by more specific ones which exercise particular tools and network technologies - which may not have been accepted by all - or even be available at all the sites. Thus some of the partners will be carrying out trials on the ISDN with more than two channels, some will use high speed ATM, or DBS satellites. Some of the seminars will deliberately use secured sessions, which have been announced securely. Some of the partners have conference rooms equipped with specific digital whiteboards. Several of the environments will be heterogeneous, making substantial use of all the types of gateway considered in WP6. At least three versions of media servers will be in routine use by different partners. There are at least four shared workspace tools. All the components will be exercised in these seminars - but not necessarily by each partner. All six countries will be represented in the seminars - but not necessarily all together at any one time; we also expect to include other countries in the seminars including the US (via CAIRN) and the EuroDemo centre in Brussels. During many of the seminars, we expect to make substantial measurements, and record the sessions in a distributed way. Hence we should be able to determine the characteristics required for high performance seminars. Deliverables R8.1 Description of, and conclusions from, the seminars carried out in the first year. R8.2 Description of, and conclusions from, the seminars carried out in the second year.

Project ref. Acronym MECCANO Date September 1,1997 Sheet 9 of 9

WP ID 9

Work Package TITLE: Support for Validation Sites START END 24 TOTAL KECU DUR 158 18
Objectives:. This work-package will ensure that the MECCANO software releases meet the needs of the different validation activities using the packages. This includes both fixing problems in the Releases, and ensuring that the contents of the Releases meet the needs of the validation projects. Work Description: Already in the MERCI project, a number of projects have come to rely on the existence of the MERCI tools. Specific projects, like MANICORAL, PROSPECT and national projects in Germany, Norway, Sweden and the UK continually take the latest releases, and provide strong feedback on their impressions and needs. The project has done its best to respond. By this time, at the start of MECCANO, the situation has changed dramatically. Now the MERCI tools are considered vital to proposals like PROSPECT (ACTS), ICE-CAR (Telematics), NICE (Telematics) and various successors of WWW for groups, MANICORAL and similar national projects. However, some of these projects are now starting to provide tools themselves, which they would like to see integrated into the MECCANO toolset. Thus the support for other validation projects comes in three forms: we must ensure that direct deficiencies in our tools are remedied; we must ensure that the tools meet the needs of these validation and demonstration projects; we must ensure that their tools can be integrated with the tools used by MECCANO. The work implied comes under this workpackage. We cannot provide great detail on the activities - because they are driven by the needs, activities and desires of the other projects. We do allocate specific effort to the liaison and tailoring tasks - but much more effort will be done in the technical workpackages to support these projects. We expect also to set up a User group, which will meet regularly either in person or through the use of MECCANO technology; this will cement the relations between the other projects and the technical groups in MECCANO. This has been discussed already under the auspices of WP2, which is responsible for such external liaison. We will also provide a limited Help Desk facility to provide users of the MECCANO tools with direct help in their use on the various platforms we support and the network environments in which we operate.

5.2 The Profile of the Consortium
With three partners each from industry (two SMEs), research institutes, and universities, the organisational balance is ideal. Most partners are strong in some complementary technology; all the partners are either strong in a relevant technology, or have access to important validation sites. The three university partners have a particularly strong commitment to distance learning, and close links with their research networks and communications carriers; thus the MECCANO partners bring in also the strong desire of their national research networks to provide extensive user trials. This is also one of the reasons for the Associated Partners, who were often put forward by the national research networks. Clearly EUTELSAT as a communication provider, and Shell as a User organisation, complete the profile of a well-rounded consortium.
5.3 The Balance of the Consortium
All the partners except ACC have had several years of collaboration on the MERCI project, and represent complete knowledge of all the relevant technology. There is an excellent geographic balance; Canada. France, Germany, Norway, Poland and the UK are all involved. Each will have high quality access to their research networks, their National pilots, and their ISDN networks. From industry, HP brings in their unrivalled experience in workstations and industrial needs. TELES brings in their familiarity with the ITU equivalent approach, and their extensive experience of ISDN products and services. NL, though a new SME, is actually a spin-off resulting from its founders activity in the MICE/MERCI projects. From the universities, RUS brings in directly its supercomputer centre and contacts with large ACTS trials; these make unique demands on the MECCANO technology. Moreover, its relationship with DFN will bring in many tools from their development activities under DFN sponsorship. The University of Oslo projects with distributed classrooms will provide a unique feedback on the projects needs in this area; UNINETT is probably the leading European exponent of distributed teaching. The UCL broad network and multimedia activities provide the latest technology in audio, security, gateways, server and resource reservation techniques; they are also responsible for national support centres and several validation activities. From the research institutes, ACC has a strong activity in multimedia servers, and a set of equipment, facilities and staff rare in Eastern Europe. CRC has a unique place on the Canadian communications scene; its wide range of skills and its excellent relationships with both CA*Net, provide both much needed adjuncts to the European partners, and a North American partner with the highest leverage. The INRIA skills in video and audio coding are a vital part of the project; they have led to their involvement with DBS technology - and hence also the sponsorship of EUTELSAT. HPLB, INRIA, TELES and UCL all have very strong links with the US - an important ingredient for ensuring international interoperability. All are very active in the IETF - particularly in the relevant working groups. UCLs membership of the DARPA CAIRN project gives it direct, high quality access to the latest resource reservation technology. Also both UCL (to the US) and CRC (from Canada) have direct control of high quality transatlantic links; this ensures firm North American - European validation of the MECCANO technology, and full transatlantic compatibility of procedures. All the partners (with the exception of ACC) have had successful partnerships over many years in other areas - directories (PARADISE), security (PASSWORD and ICETEL) and high speed networks (HIPPARCH, PREPARE). UCL has acted some years ago as a test site for the TELES EUROBRIDGE technology. Thus it is clear that the partnership has been chosen because we all know we work well together, and do not expect the problems endemic in many European projects. It is significant that there were 11 partners in the original MICE project; while all contributed well in the MICE context, and several remain our partners in other activities, only six remained in the original MERCI consortium, and four in MECCANO. Three partners brought into MERCI remain in MECCANO; we are striving to ensure the optimum technical and collaborative balance.

provided by CNS department within HPLB, with a total responsibility for the IT infrastructure within HPLB, and working closely with the CNS teams on HPs other major sites across Europe. Contributions to the Project HPLB's concern that there be a clear and agreed architecture across the project, for use in the development and exploration of real time multi-media applications, persuaded it to lead WP3. It is particular concerned to define the applications with their related performance and the supporting infrastructure, identifying components and interfaces, against current standards and thus identifying potential problem areas and shortfalls in the current tools. The development of new applications, or the use of existing ones, will be part of the proposals which will include coverage of Web-mounted and alternative solutions, including the evaluation of the new operating system options, as they become available. Under WP8, HPLB will implement proposals for use in the Bristol site for collaborative purposes. It will give support to other HP divisions in using the tools, and will set up broadcast and collaborative events with partners and outside organisations - assessing differing contexts and recommending changes Team Leader Sandy Johnstone works for Hewlett-Packard Corporate Development in Europe, with responsibility for leading and co-ordinating all of HP's technical activities within European Collaborative Research. He has worked as Computer Consultant, Service Manager and MIS Manager, firstly in Eastern Europe and the USSR, then in Benelux and Scandinavia. Between 1986 and 1996 he was Training and Development Manager for HP's European Computer Consultancy operation, with special interests in collaborative trans-national co-operation. 5.6.5 INRIA The Organisation INRIA (National Institute for Research in Computer Science and Control) is a French public-sector scientific and technological institute under the responsibility of the Ministry for Research and the Ministry of Industry with over scientists, and a budget of 70 MECUs, 20% of which comes from contracts, royalties and sales. Industrial relations are strategic for INRIA including tenure positions, scholars and trainees, researchers from public laboratories, engineers from industry, and visiting researchers from abroad. The research carried out at INRIA is mainly concerned with software and control engineering, bringing together experts from the fields of applied mathematics, control, signal processing and computer science within the framework of 6 research programs. It has joint contracts, and interchanges staff with, industry; it stimulating the creation of spin-off companies and subsidiaries by former INRIA researchers and engineers. The Contribution to the Project The INRIA team will focus on delivery of higher quality multimedia data over heterogeneous networks - improving performance by combining layered coding schemes, audio and video, with a layered transmission schemes. While this idea is attractive specifying how/when receivers are to join and quit layers has only recently been described and simulated; furthermore, it has not yet been deployed over the Internet. Most of this activity is in WP4, but in WP5, they will consider also the impact of transmission over local wireless and DBS, unidirectional, satellite links - using also IPv6 and resource management services. The Team leader Jean-Crysostome Bolots recent work has focused on designing and evaluating congestion and error control mechanisms for the multicast distribution of audio and video over the Internet. These mechanisms have been included in FreePhone and in the INRIA Videoconference System IVS. In parallel with the work on control mechanisms, he has also been investigating performance characteristics of the Internet. 5.6.6 University of Oslo The Organisation UiO is Norway's largest university with students and a staff of over 4 500. The centre for Information Technology Services (USIT) provides computer network, computer resources and computer services for all parts of the university and has more than 100 full time employees. USIT has played a key role in establishing the national and Nordic academic networks, now organised in UNINETT. The university has Supernet (a national high-speed network for experimental services) ATM with 34 Mbps connection, with plans for upgrading to 155 Mbps. USIT has built an advanced Electronic classroom, which has been used for regular distance learning over the last 6 years, being continually enhanced. There are currently 5 operating classrooms in Norway, and several more being built. The classroom concept is now commercialised, and handled by a USIT spin-off, "New Learning. USIT is responsible for the real time Multimedia National Support Centre funded by UNINETT A/S and participates in a collaborative project nationally funded by the Research Council of Norway (LAVA), introducing advanced broadband video services in application areas as teaching, research, mediation, security and television. The Contribution to the project UiO will bring into the project an existing and fully operating high-end Electronic Classroom, a multimedia server (optical jukebox) and several Multimedia workstations. It will

from the DFN; it is under their funding that we will support other projects in WP9, collaborating with the DFN Multimedia Support Zentrum at Dresden U to support DFN-provided user communities. Team Leader Paul Christ is head of the department Communications Systems and BelWue-Development of RUS, which has pioneered high-speed networking locally, nationally and internationally. He is responsible for BelWues upgrade to 622 Mbps ATM - including the corresponding transitions into the national and international ATM projects. Under the ATHOC project, he participates in a major cable trial which has MECCANO implications. Role and Services of Associated Partners Most of the RUS activities will be carried out directly by RUS. However, three activities will be carried out by partners associated with RUS, whose work has been mainly supported under the DFN initiatives. As part of WP2, Freiburg U. will integrate in and develop further the whiteboard started under the DFN project "Whiteboard for Tele-teaching and Authoring on the fly. In addition, U of Erlangen-Nurenberg will provide a technique to integrate real-time scaleable video services into existing WWW Browsers and Mbone tools. As a validation exercise in WP7, Univ. Mannheim will send real lectures from the University to students' homes via ISDN using scaleable video technology - in a manner compatible with the MERCI/MECCANO Tools. 5.6.8 TELES The Organisation TELES with a 1996 turnover of 32 MECU and 275 employees is a leading-edge supplier of information technology, with a "centre of excellence" in the ISDN/PC area, especially in multimedia technology. TELES is the current ISDN/PC-market leader, shipping up to 50K.month with about 25% for exports, and 50% of its sales in R&D for the PC mass market. It has the broadest and the most innovative range of ISDN products world-wide - PC boards and boxes, highly sophisticated and scaleable PBXs, videoconferencing systems and media servers. In addition to R&D for its own products, TELES also performs contract R&D for major international companies. TELES has had long in working on CEC panEuropean projects and is also active in international industry consortia and in standards bodies such as IMTC, DAVIC, ITU, IETF, EIUF, NIUF. Contribution to the Project In WP4, TELES will support the PCs under Microsoft OSs to support multimedia streams efficiently, and will integrate in Microsoft application developments like Net Meeting. They will put considerable effort in platform management and monitoring - partly in the context of network components of WP5 and partly in the gateways of WP6. They will continue current H323-Mbone gateway activity, including transcoding, announcement and security. Since their components are an integral part of WP8 and outside projects, they will expect to devote a considerable effort on the user support in WP9. Team Leader Hans-Peter Scharf is a manager of Research and Development projects at TELES - both EC and National. He has been responsible for the management of TELES involvement in MERCI and of several other projects. Role and Services of Associated Partners A significant part of the gateway development activity, and some of the validation, will be carried out at the University of Bremen.