P Veron{

J C Leon

SHAPE PRESERVING POLYHEDRAL SIMPLIFICATION WITH BOUNDED ERROR

Keywords: polyhedron simpli®cation, conformity, node removal, error inheritance, gaussian curvature approximation, meshing techniques, shape preservation

AbstractÐA new approach is introduced to reduce the number of nodes of a polyhedral model according to several conditions which allow to produce high quality simpli®ed geometries. The simpli®ed polyhedron must satisfy everywhere a geometric restoration criterion based on an error zone assigned to each node of its initial model. These error zones can be speci®ed by the user or automatically set up using the accuracy characteristics of the digitizing device. Moreover, speci®c criteria are used to preserve the shape of the object during the simpli®cation process both from geometric and topologic points of view. Indeed, the uses of such polyhedra require a good geometric quality without topologic and geometric singularities. The simpli®cation process is based on a node removal method. A new strategy is developed to produce the simpli®ed polyhedron using front propagations and multiple remeshing schemes which take into account the discrete curvature characteristics of the object. Such an approach allows to increase the node reduction of the initial polyhedron and produces a smoothing eect on the simpli®ed geometry. The front propagation technique also leads to a better preservation of the shape of the object. Examples illustrate the behaviour of the simpli®cation algorithm in terms of data reduction, quality of the simpli®ed geometry and shape preservation of objects.

INTRODUCTION

Geometric models of objects are widely used in many areas of the industry. The recent advances of digitizing techniques has opened new ways to generate geometric data from existing objects. Such processes produce a set of 3D points often characterized by its large number of points which can range from several thousands to hundreds of thousands. This set of points can be used to build various geometric models of the real object which can range through three kinds. The ®rst one uses an implicit representation of the surfaces [1±3] and the second one is based on a parametric representation of the surfaces [4±7]. These techniques are useful for many applications like design, redesign, visualization and so on. Nevertheless, the surface reconstruction process used to produce such models stays a dicult task. In fact, the surface decomposition into patches and the speci®cation of the continuity conditions between them are still not entirely automatic processes. The third kind of geometric model is based on a polyhedral representation of the surface of an object produced from the digitized points through a triangulation process [8±12]. The main advantages of such models stand in their abilities to represent general object shapes and to be computationally ecient and robust. Moreover, the triangulation process used to produce the polyhedra is often more ecient and less tedious than a surface reconstruction process.

Polyhedral models are well suited for many applications such as computer animation, visualization, robotics, tool path generation for numerically controlled machine tools and even for speci®c applications like the calculation of ray trajectories for non destructive testing processes. Another application stands in their use as geometric model for structural analysis of digitized parts.

However, the polyhedron generated from the digitized set of points often exhibits a large number of nodes and faces and its direct use for any of the previous applications generates lengthy computations and leads to inecient manipulations. Therefore, a simpli®cation process is required to reduce the number of nodes of the polyhedral model in order to improve the eciency of the subsequent processings and to produce a polyhedron adapted to the desired application. Computer animations often require several levels of representation (i.e. or detail) of an object in accordance with the location of the user's point of view, calculations of tool path, ray trajectories and so on, for all these processes the computation time required increases like the number of nodes and faces of the polyhedron. This last remark motivates the use of a simpli®ed polyhedron for such applications though the accuracy of the previous calculations is strongly linked to the quality of the restoration of the geometry of the initial polyhedron. In the ®eld of structural analysis, several geometric adaptions (i.e. they consist mainly in detail removals) or idealizations (i.e. large geometric modi®cations often involving changes in the topology of an object) are often required to generate the adequate geometry for a given analysis. For example, a cylindrical surface may be idealized into a line corresponding to its axis thus allowing the use of a beam model.

Various simpli®cation approaches [START_REF] Erikson | Polygonal simpli®cation: an overview TR 96-016[END_REF][START_REF] Heckbert | Multiresolution modeling for fast redering[END_REF] have been developed recently. Basically, two dierent concepts of simpli®cation process can be distinguished.

The ®rst one consists in ®nding a simpli®ed polyhedron which has a prescribed number of nodes and which preserves as much as possible the initial geometry of the object [8, 15±23].

The other basic concept of simpli®cation processes consists in ®nding a minimal polyhedron, i.e.: a polyhedron with a minimum number of nodes and faces, with respect to some geometric criterion.

Here, the number of nodes and faces of the simpli-®ed polyhedron is unknown and depends on the criterion used. Among the existing methods, one of them cannot simplify arbitrary polyhedra [START_REF] Dehaemer | Simpli®cation of objects rendered by polygonal approximations[END_REF]. Other ones are well suited for polyhedra with low curvature distribution [START_REF] Hinker | Geometric optimization[END_REF][START_REF] Kalvin | Superfaces: polyhedral approximation with bounded error[END_REF]. Other methods need to compute parallel polyhedra [START_REF] Varshney | Hierarchical geometric approximations[END_REF][START_REF] Cohen | Simpli®cation Envelopes Computer Graphics[END_REF], or envelopes [START_REF] Gueâ Ziec | Surface simpli®cation inside a tolerance volume Technical Report RC 20440[END_REF], a dicult task because they must not possess self-intersections.

Previous works have also led us to develop an approach for the simpli®cation of polyhedral models [START_REF] Veâ Ron | Static polyhedron simpli®cation using error measurements[END_REF]. The geometric criterion employed to control the restoration of the geometry is based on an error zone assigned to each node. This tolerance may result either from the error measurement of the digitizing device or it can be set by the user in accordance with the subsequent use of the polyhedral model. Such an approach allows the simpli®cation of an initial polyhedron using a criterion which can be easily understood and monitored by the user.

The main interest of the approaches based on the second basic concept stands in their abilities to control the restoration of the initial geometry through various criteria. This control is eectively necessary when the simpli®ed geometry is used for calculations of tool path, ray trajectories and so on. In the ®eld of computer animation and visualization the approaches based on the ®rst basic concept are widely used mainly because of their short execution time. Nevertheless, quick progress in this ®eld needs the use of high quality surfaces for the simpli®ed geometry in order to satisfy realistic and aesthetic criteria for the animation and the rendering of complex scenes. The smoothness of the simpli®ed surface is one among the most important criterion. The shape preservation of the initial model is also an important aspect either for animation and rendering or for many other applications. Any of the existing approaches give satisfactory solutions with respect to these requirements. Few of them use basic criteria to preserve the topology of the object but they are limited either to local approaches which do not produce satisfying results or global ones which are time consuming and therefore not suited for ecient simpli®cation processes.

The approach initially developed [START_REF] Veâ Ron | Static polyhedron simpli®cation using error measurements[END_REF] does not provide more robustness about the restoration of the shape of the object. The fundamental aspects of the new approach proposed in this paper are:

. the shape preservation of the object. This task is very complex and time consuming if the coherence checking of the object topology and geometry is carried out on a global basis. On the other hand, a local veri®cation cannot produce satisfactory results. The strategy proposed here can be quali®ed as semi-global veri®cation. The coherence checking of the object shape is gained through speci®c criteria which allow to detect possible topologic modi®cations as well as generation of geometric singularities. In addition, a new frontal concept is used to give to the simpli®cation process a semi-global aspect. The propagation of fronts over the surface during the simpli®cation process also increases the eciency and the robustness of processing, . the inheritance concept of the error zones introduced in [START_REF] Veâ Ron | Static polyhedron simpli®cation using error measurements[END_REF] proved to be a good way to control the restoration of the geometry. Nevertheless, this concept generates an algorithm of non linear complexity. At each node removal, the list of error zones assigned to each new face increases thus lengthening the overall simpli®cation process. The processing of large sets of data and the reduction of the execution time of the simpli®cation algorithm have led us to develop a new inheritance concept which allows the simpli®cation process to be of linear complexity with respect to the number of nodes of the initial model, . the last important aspect is the combination of several meshing techniques based on speci®c criteria in order to produce remeshed areas adapted to the local features of the surface. The criteria used range from aspect ratios of triangles to criteria which take into account the principal directions of curvature of the surface. Thus, the quality of the simpli®ed surface and the faces/ nodes reduction is improved. In addition, during the simpli®cation process a new remeshing strategy based on the combination of dierent remeshing schemes is developed.

GENERAL DESCRIPTION OF THE SIMPLIFICATION ALGORITHM

The simpli®cation algorithm is based on a node removal process. All the nodes of the simpli®ed polyhedron produced by the simpli®cation process already exists in the initial data. Several preliminary processing are executed before the main simpli®cation loop starts.

Classi®cation of the edges and nodes of the initial polyhedron

A classi®cation process of the edges and nodes of the polyhedron is required to apply speci®c criteria to each category. The edges of the polyhedron are classi®ed using the following rules: an edge connected to one face only is a boundary edge, an edge connected to two faces is a surface edge, otherwise the edge is assigned the status unknown. The nodes are classi®ed using the following rules: a node connected to two boundary edges is a boundary node, a node connected to surface edges only is a surface node, otherwise the node is assigned the status unknown.

Correction of the non-conformities of the initial polyhedron

The robustness of the simpli®cation process requires that the initial polyhedron is solely made up from nodes and edges either classi®ed on a boundary or on a surface in order to satisfy the manifold conditions. Others geometric conditions are necessary to produce a conform initial polyhedron which ensures the robustness and the eciency of the simpli®cation process. Such requirements are justi®ed because the shape preserving capabilities of the approach developed cannot take place when the initial polyhedron contains geometric and topologic singularities. Simpli®cation tests on industrial data sets have demonstrated the existence of non-conformities described below which must be removed using both automatic and interactive processes.

When the polyhedron does not satisfy the manifold conditions, the non-conformity areas are designated by the unknown classi®cation status of some edges and nodes. The possible non-conformities identi®ed can be divided into two categories. The ®rst one is characterized by all the non-conformities that can be removed through automatic processing:

. double faces identi®ed when two dierent faces have the same list of nodes (eventually in a dierent order), . degenerated faces identi®ed when at least two nodes describing the face are either identical (null area of the face) or located with respect to each other within a distance less than the tolerance of position used to monitor the simpli®cation process.

The second one is characterized by the multiple solutions available to correct them. Therefore, the non-conformities identi®ed are displayed and interactive tools are oered to the user to correct them:

. a node is connected either to one boundary edge only or to more than two boundary edges, . an edge is connected to more than two faces, i.e.: the manifold condition is not veri®ed.

Figure 1 illustrates these ambiguous cases which require interactive processing.

Initialization of the simpli®cation problem

The ®rst part of this last preliminary processing assigns to each node a spherical error zone. The value (i.e. the radius) of each error zone can be set up through two dierent ways. The ®rst one assigns to all the error zones a unique value chosen by the user. The second one assigns to each node an error measurement value related to the measuring system previously used for the digitalization. In this case the value assigned to each node can vary in relation to the shape of the digitized object and the space distribution of the accuracy of the measuring system.

The second part of the initialization associates to each face of the polyhedron a dependency list of error zones de®ned by all the error zones which participate to the local restoration of the surface of the object. Similarly, a dependency list of error zones is also associated to each boundary edge to control the restoration of the boundaries of the object. These dependency lists form the basis of the inheritance concept used to control the overall restoration of the object geometry. Their creation and the associated inheritance concept used are developed in Section 4.

The simpli®cation loop

When the previous preliminary processing have taken place, the simpli®cation process can start. It consists in an iterative node removal process applied until no more candidate node can be removed. An iteration starts with the selection of the best candidate node using selection criteria described in Section 3. The candidate node selected initiates a front which is then propagated according to the approach developed in Section 5. The front propagation stops when no more node of the front can be removed. The propagation of a front also uses the selection criteria to sort its nodes and select the best one for removal. Each candidate node selected is processed as follows:

. a list of the error zones which participate to the restoration of the geometry around the candidate node is created. This step is described in Section 4, . the contour polygon de®ned by the nodes surrounding the candidate node is extracted, . this 3D contour polygon is remeshed using dierent meshing techniques in accordance with the strategy developed in Section 7, . the shape preserving control described in Section 6 is applied to the mesh locally created. This geometric and topologic coherence checking allows to determine whether the candidate node can be removed or not, . if the candidate node is removed a last step is necessary to replace the new mesh into the current polyhedron and to update the dependency list of the newly created faces and boundary edges (see Section 2).

CRITERIA USED TO SELECT THE CANDIDATE NODES

One among the main tasks of the simpli®cation process is the selection of the best candidate node. This selection process becomes increasingly important during the simpli®cation process when the quality of the simpli®ed geometry gets improved, i.e.: if the initial polyhedron has been generated from noisy data, the noise reduction characterizes a geometry improvement.

Two categories of criteria are used in accordance with the two status of node classi®cation. Figure 2 illustrates these criteria.

Selection of the boundary nodes

The selection criterion used for the boundary nodes is based on the evaluation of the angle de®ned by the two boundary edges connected to this node. This evaluation produces an angle ranging from 0 to 1808. Then, all the boundary nodes can be sorted from the largest angle to the smallest one. Such an order allows to try to remove ®rst the nodes located on straight lines or distributed along curved boundaries owning small curvatures. Afterwards, the boundary nodes located on highly curved zones are processed but their probability of removal is much smaller.

Selection of the surface nodes

The selection criterion used for the surface nodes is based on a discrete approximation of the gaussian curvature of the polyhedron around a node.

Several approximations of this curvature are possible:

. the most basic curvature approximation [START_REF] Boix | Approximation line aire des surfaces de R 3 et applications[END_REF] of a polyhedral surface at node I is given by:

K 1 2p À i a i , 1
where the a i are the angles of the faces meeting at node I,

. the second approximation proposed by Calladine [START_REF] Calladine | Gaussian Curvature and Shell Structures The Mathematics of Surfaces[END_REF] takes into account the areas a i of the faces meeting at the node I. The curvature at this node is given by: .

K 2 K 1 1 3 i a i , 2
Boix [START_REF] Boix | Approximation line aire des surfaces de R 3 et applications[END_REF] has developed a third approximation of the gaussian curvature which takes into account the shape dierences of the faces meeting at a node. He has demonstrated that this discrete approximation of the gaussian curvature converges towards that of the equivalent smooth surface. The same property does not hold for Equation [START_REF] Pratt | Direct least squares ®tting of algebraic surfaces Computer Graphics[END_REF]. The curvature at node I is given by:

K 3 K 1 i a i 1 2 i a i À 1 8 i cotga i l 2 i X 3
All the surface nodes are sorted from the smallest absolute value of the gaussian curvature up to the highest. This allows to remove in the ®rst place the nodes located on zero or nearly zero gaussian curvature zones like planes or approximately plane areas or approximations of cylinders. The nodes associated to high positive or negative gaussian curvature values are treated later on and thus have a smaller probability of removal.

The use of such selection criteria allows to preserve the signi®cant areas during the restoration of the shape of the object and forms an aspect of the shape preserving approach developed.

THE REDUCED INHERITANCE CONCEPT OF THE ERROR ZONES

Every time a node is removed, an inheritance process is used to update the list of error zones participating to the restoration of the geometry. This inheritance process is a fundamental aspect of the shape preserving control. The ®rst part of this process takes place in the preliminary processing of the simpli®cation algorithm (see Section 2.3). It assigns to each face and boundary edge of the initial polyhedron a dependency list of error zones which are signi®cant for the local restoration of the geometry of the object. The initial dependency list of a boundary edge contains the two error zones associated to its extremity nodes. Similarly, the initial dependency list of a face contains the three error zones associated to its three nodes (i.e. all the faces are triangular). Figure 3 illustrates these dependency initializations.

The second phase of this process takes place during the simpli®cation loop (see Section 2.4). It creates the list of error zones participating to the geometry preservation around the candidate node to be removed. When this node is of surface type, the list is made up from the set of error zones assigned to each face adjacent to that node. If the node is a boundary one, two lists are created. The ®rst one is similar to a list attached to a surface node and the second one is made up from the set of error zones assigned to the two boundary edges meeting at the candidate node. The ®rst list is used to control the restoration of the surface of the object and the second one (i.e. when it exists) controls the restoration of the boundary of the object through appropriated criteria.

Finally, the third part of the inheritance process takes place when a node is removed (i.e. when the shape preserving criteria are satis®ed) (see Section 2.4). Its goal is to update the dependency lists of the new faces created after remeshing. This update is gained from the lists of error zones previously created which participate locally to the shape restoration of the object. All the error zones of the list set up during the second phase which intersect each new face, are assigned to this face. If the node removed is a boundary one, the update of the new face dependencies is completed by an update of the dependency list of the newly created boundary edge using a similar intersection criterion. This last part of the inheritance process is described in Fig. 4.

During the simpli®cation loop, every time a node is removed, the new faces created become larger and, consequently, the number of error zones in their dependency lists increases. When the initial polyhedron owns a large number of nodes and faces such a behaviour leads to non linear timedependent simpli®cation processes. Indeed, when the number of error zones participating to a node removal increases, the shape control process becomes more time consuming. To overcome this behaviour and give to the simpli®cation process a linear behaviour in relation with the number of nodes of the initial polyhedron, a new reduced inheritance concept is proposed. To this end, a criterion is used during the above updating process to select among all the error zones associated to a node removal, the most signi®cant ones from a shape restoration point of view. The previous remark forms the basis of the criterion proposed to select the signi®cant error zones: for each face F i meeting at node I, the geometric modi®cations involved by the removal of the node I can be interpreted, when new faces F H i are created by the remeshing process, as a rotation a i of the face F i around the edge J i K i located at the opposite of the node I. Similarly, the removal of the nodes J and K involves rotations respectively around the edges IK and IJ. Figure 5 illustrates this remark.

To get a constant time for each node removal, the number of error zones associated to a face must be ®xed. The criterion developed to select the sig-ni®cant error zones allows to limit this number to nine. As long as the number of error zones associated to a face is less than nine, all of them are kept. Then, when this number becomes greater than nine the reduced inheritance concept is applied. Among the nine error zones, the three ones associated to the nodes of the face are retained. Then, the criterion described below allows to retain two signi®cant error zones for each possible rotation of the face around each of its edges, thus producing the six other error zones. From a shape restoration point of view and for a given edge of a face (i.e. or possible rotation around it), an error zone is signi®cant when the location of its centre is far from the plane de®ned by this face and far from the edge considered. The criterion used to select the most signi®cant error zones for a face is illustrated in Fig. 6 and can be stated as follows: for each possible rotation of a face around an edge, a weight W is computed for each error zone using the following rule:

W d  h, 4
where d is the distance (A,P) and h the distance (C,P). C is the center of the sphere de®ning the error zone, P the projection of C on the plane de®ned by the face (I,J,K), and A is the projection of P on the edge JK as shown in Fig. 6. One of the most signi®cant error zones is identi®ed by the maximum positive value of W and the second one by the maximum negative value of W. When several error zones have the same maximum positive or negative value of W, the most signi®cant error zone is identi®ed by the maximum value of h. In fact, the two error zones thus selected correspond to the error zones which have the highest probability to lose their intersection with the face when the node I is removed.

THE FRONTAL APPROACH

A frontal approach is part of the simpli®cation loop of the polyhedron. It is based on the propagation of fronts over the polyhedron. When the simpli®cation loop starts, all the nodes of the polyhedron are candidates to removal. The frontal approach described here is applied to surface nodes only. The simpli®cation loop is an iterative process where each iteration starts with an initialization of a front. Then, a propagation process is applied until a stopping criterion is reached. Figure 7 illustrates the main steps of the simpli®cation loop.

Initialization of a front

This step is based on the use of the surface node selection criterion previously described in Section 3. For each candidate node (i.e. all the surface nodes are candidate at the ®rst iteration) an evaluation of the approximation of the gaussian curvature is computed. The node which owns the minimum absolute gaussian curvature value is selected as the ®rst node of the front. Such a selection allows to start fronts primarily into planar areas, then into the low curvature areas and ®nally into the high curvature areas. The fronts initialized into planar or low curvature areas have a high probability to be subjected to a large propagation at the opposite of those initialized into high curvature areas.

Propagation of a front

This step is carried out through an iterative process applied to all the candidate nodes of the front (i.e. a front is described as a list of nodes). For each node, its contour polygon is extracted and remeshed (see Section 7, the remeshing processes). Then, the shape restoration control takes place and de®nes whether the node can be removed or not (see Section 6, the shape preserving control):

. if the node is removed, the front is updated as follows: the node removed is deleted from the front and all the nodes of its contour polygon which were not into the front are now added to it. Their status is also updated and they become candidate nodes,

. else, if the node cannot be removed (i.e. the shape restoration criteria are not satis®ed), the list of nodes of the front is unchanged but the status of the candidate node is no longer a candidate to the removal process until one, at least, of its surrounding faces has not changed.

The front is thus propagated until no more candidate node exists in its list of nodes. During the propagation process, the best candidate node is also selected in accordance with the surface selection criterion (see Section 3). The nodes with low absolute gaussian curvature values are processed ®rst. Afterwards, those with high absolute gaussian curvature values which have a small probability of removal are processed. This selection leads the process to propagate the front into directions of low curvature. For example, when a front is initialized on a cylinder area it is propagated along its axis. This propagation process is illustrated in Fig. 8.

To sum up, such an approach takes into account dierent feature areas of the initial polyhedron and simpli®es them with a speci®c strategy which contributes to restore as well as possible the shape of the object. The propagation strategy used for each front (i.e. or feature area) leads to a good restoration of the regions of the object with particular shapes (i.e. with signi®cant principal curvature directions). The fronts produced to simplify a simple test example are shown in Fig. 9. The feature areas of the object are eectively well identi®ed. No front has been produced on the round corner of the object because the error zone values speci®ed for this simpli®cation does not allow any node removal in this area.

THE SHAPE PRESERVING CONTROL

This process takes place during the simpli®cation loop, each time the 3D contour polygon of a candidate node is remeshed (see Section 2.4 to locate this process). Its goal is to verify if the shape of the initial polyhedron is adequately restored by the newly created mesh. To preserve the shape of the initial object, such a process must take into account both geometric and topologic criteria.

First of all, the geometric restoration of the initial polyhedron by the new mesh is controlled with a simpli®cation criterion described in the following section. It relies both on the error zones and on the inheritance concept previously de®ned (Section 4). Then, if the mesh produced satis®es the simpli®cation criterion, its topologic and geometric compat-ibilities with respect to the current polyhedron must be checked to detect possible singularities which can occur when the new mesh is inserted into the current polyhedron. The criterion used to check this compatibility is described in Section 6.2.

The use of a frontal approach (see Section 5), which allows to propagate gradually the simpli®cation process, reduces the probability to produce singularities and leads to a better restoration of the shape of the object.

The simpli®cation criterion

The simpli®cation criterion ensures that the mesh created from the 3D contour polygon of the candidate node is entirely enclosed into the envelope de®ned by all the error zones participating to its removal (see Section 4, the construction of this list of error zones).

When the candidate node is a surface one, the local restoration of the geometry around it is expressed as follows: every error zone involved in the removal of the candidate node must intersect at least one of the faces of the 3D contour polygon remeshed. Figure 10 illustrates this criterion with a simple example. Two possible solutions exist to remesh the contour polygon of node J. In Fig. 10b, the two faces created intersect the error zone associated to the node J. Conversely, no face intersects the error zone associated to J in Fig. 10c thus the criterion is violated.

When the candidate node is a boundary one, another test is added to the previous one to check the correctness of the restoration provided by the boundary edge created. This test uses the same envelope concept and can be stated as follows: all the error zones associated to the two boundary edges meeting at the candidate node must intersect the new boundary edge. Figure 11 illustrates this criterion with a planar surface example which ensures that the surface restoration criterion is satis-®ed. Indeed, in this case the error zone associated to node I intersects the face F1 newly created. Nevertheless, Fig. 11a shows that the new boundary edge does not intersect the error zone associated to node I. This con®guration violates the simpli®cation criterion of the boundary. Another con®guration, Fig. 11b, shows that the same test is now satis®ed and the boundary is adequately simpli®ed.

Topologic and geometric coherence checking

This step is achieved only when the geometric criterion is satis®ed and it checks the topologic and the geometric coherence of the polyhedron when the mesh created is inserted into the current polyhedron. The topologic analysis ensures that the polyhedron stays a geometric manifold of dimension two. However, a unique topologic analysis is not sucient to ensure a correct restoration of the shape because of the in¯uence of the geometric con-®guration of the polyhedron (i.e. the location of its nodes).

Two dierent criteria are used to control the restoration of the shape of an object to be able to cope with the surface point of view (i.e. when a surface node is removed) and the boundary point of view (i.e. when a boundary node is removed).

6.2.1. Surface shape restoration criterion. A sucient criterion to determine if a surface node removal may produce non-conformities needs to verify if the contour polygon around the candidate surface node is already partially or eventually entirely meshed by some other faces of the current polyhedron. This veri®cation is carried out through the construction of the list of faces which possess all their nodes on this contour polygon. If no face is found, the contour polygon is not already meshed. If the number of faces found is equal to the number of nodes of the contour polygon minus two, the extracted contour is already entirely meshed. Otherwise, it is partially meshed. Figure 12 illustrates such situations.

When the contour polygon is not already meshed, all the new meshes produced using the dierent meshing techniques described in Section 7 always preserve the coherence of the shape of the object. At the opposite, when the contour polygon is already partially or entirely meshed, the correct restoration of the shape of the object depends on the behaviour of the meshing technique used.

Figure 13 shows a ®rst example of a contour polygon extracted from a surface node I (Fig. 13b) which is already partially meshed by a face F1 of the initial polyhedron. A ®rst meshing solution of this contour, illustrated in Fig. 13c, generates a non-conformity which can be characterized through two dierent ways:

. the existence of two identical edges connecting the nodes J and K. In this case, every edge is still connected to two faces but a geometric singularity exists, . if the creation of two identical edges is forbidden, the edge E is then connected to more than two faces. In this case, there exists a topologic nonconformity because the object has become a nonmanifold one. Both geometric and topologic singularities lead to a bad restoration of the shape of the object. However, the solution in Fig. 13d does not generate any non-conformity but it illustrates the in¯uence of the meshing process over the shape preservation of an object.

Another example of a contour polygon already partially meshed is shown in Fig. 14. In this case, all the nodes of the contour are located into the plane P. The node I located above this plane is candidate for removal. The node J is located below P. Such a situation illustrates that all the possible remeshing con®gurations of the contour polygon lead to a geometric non-conformity characterized by overlapping areas. The correct restoration of the shape of the polyhedron depends of the geometric location of its nodes. The geometry described in Fig. 14 is a particular case (i.e. all the nodes of the contour are located in P) but the general case with arbitrary locations of nodes can lead to more complex non-conformities characterized by self-intersections of the polyhedron.

When the contour polygon is already entirely meshed the probability to generate non-conformities is even higher. All the previous remarks are valid and there exists particular cases where the shape restoration of the object is impossible (see Fig. 15). Indeed, in such cases a change of the topology of the object cannot be avoided and leads to transform a closed surface into an open one.

When the extracted contour polygon is already partially or entirely meshed, the above statements show that the criterion used to validate the remeshed area must take into account both topologic and geometric aspects. From a geometric point of view, the tests required lead to tedious computations which are not acceptable for the eciency of the simpli®cation process. Hence, the shape restoration of the polyhedron is carried out using the following rule: if the extracted contour polygon is already partially or entirely meshed, the removal of the candidate node is forbidden because both topologic and geometric singularities could be produced. 6.2.2. Boundary shape restoration criterion. The criterion used to preserve the shape of the boundaries of an object (i.e. the object is necessarily an open surface) possesses two dierent aspects. Like the surface shape restoration, topologic and geo- metric requirements must be satis®ed to preserve the shape of the object. The ®rst part of the criterion preserves the topology of the object and checks that the number of nodes or edges of each contour polygon of a closed boundary (i.e. these two numbers are equal in this case) is greater or equal to three. Indeed, both from a topologic and a geometric point of view the minimal acceptable representation of the contour polygon of a closed boundary is a triangle. Figure 16 illustrates this aspect with a cylinder. If this criterion is not satis®ed, the topology of the object gets modi®ed and its shape cannot be preserved. Figure 17 shows two examples of topologic modi®cations which can occur when the boundaries are simpli®ed while the previous criterion is violated. An open surface can become a closed one (Fig. 17a) or an open surface can be degenerated into a line (Fig. 17b). To apply this criterion, the simpli®cation of the boundaries of the polyhedron is carried out on a closed contour basis. Each closed contour polygon of the object is described as a list of boundary nodes (i.e. and eventually a list of boundary edges) which allows an easy evaluation of the above criterion. Such a criterion is not sucient from a geometric point of view because of the speci®c con®gurations which may exist into a polyhedron. To avoid the creation of geometric singularities when a boundary node is removed the following control must take place. It determines if there exists surface nodes into the area de®ned by the two boundary edges meeting at the candidate node when the contour polygon of this node was extracted and the boundary edge newly created. If surface nodes are found in this area, the boundary node cannot be removed because it generates a geometric non-conformity. Figure 18 illustrates on a planar surface various geometric con®gurations which generate geometric singularities when the boundary node I is removed. The criterion used to detect such con®gurations is illustrated in Fig. 19 and can be stated as follows:

. determine the interior surface direction d de®ned by:

d n v1 Ĩn v k n v1 Ĩn v k 5
where n is the number of nodes of the contour polygon of I and n v the coordinates of the surface nodes of this contour, . compute Ñedge the normal vector to the edge JK newly created de®ned by: . Ñedge Ñt  JK, with Ñedge Á d b 0 6

. where Ñt is the normal vector to the plane de®ned by (I,J,K), then, determine the location of each node of the extracted contour (excepted J and K), with: If test>0 for all the nodes, the contour polygon is conform and does not generate any singularity.

Conversely, if one of the nodes produces a test0, the contour polygon generates a non-conformity and the boundary node I cannot be removed.

MESHING TECHNIQUES APPLIED TO A 3D CONTOUR POLYGON

During the simpli®cation loop, every time a candidate node is processed, its contour polygon must be remeshed before the shape preserving tests determine whether the node can be removed or not (see Section 2). It has been demonstrated in Section 6.2 that the con®guration of the remeshed area produced in¯uences the shape restoration of the object. Indeed, dierent solutions can generate topologic and/or geometric non-conformities. Thus, ecient meshing processes of 3D contour polygons is one among the most important tasks of a node removal algorithm to preserve as much as possible the shape of the initial model. Two meshing techniques characterized by their abilities to create satisfying contour polygon meshes are used during the simpli-®cation.

Meshing with an equilaterality criterion

The starting point of the meshing process is a 3D contour polygon de®ned by a list of nodes and edges sorted in accordance with their edge connections to produce an ordered closed contour. Then, an average normal Ñ to this contour is computed as follows:

Ñ m i1 ñi k m i1 ñi k , 8
where ñi is the unit normal to the ith face surrounding the candidate node and m is the number of faces meeting at this node.

Afterwards, to avoid the creation of badly meshed areas the second step of the process ident-i®es speci®c contour polygon con®gurations to de-®ne priority nodes. The priority nodes are characterized through topologic and geometric criteria using the following rules:

. a contour node connected to one face only which does not own the candidate node in its list of nodes has a topologic priority (see Fig. 20a), . a contour node aligned with its two neighbour nodes (i.e. the previous one and the next one) has a geometric priority (see Fig. 20b).

Such priority nodes are used in the following step to process them ®rst and the others afterwards using a speci®c selection criterion.

The last step of the process meshes the contour polygon using an iterative processing which creates new faces between three consecutive nodes of the contour polygon. Every time a new face is created, the 3D contour polygon is updated and the process stops when no node is left in the contour.

An iteration starts with the selection of three consecutive nodes of the contour polygon as follows:

. while there exists a priority node Np, the three consecutive nodes selected are (Np, Np n , Np nn ) or (Np, Np p , Np pp ). Figure 21a illustrates this selection. The topologic priority nodes are processed before the geometric ones, . then, the remaining nodes are selected in accordance with the angle de®ned by the two contour edges meeting at each of them. They are processed from the smallest angle to the largest one. If Ns is the current node, the three consecutive nodes are (Ns p , Ns, Ns n ) where Ns p is the node before Ns and Ns n is the next one. Figure 21b illustrates this selection. Such a criterion creates triangles as equilateral as possible and avoids the creation of edges which divide the smallest angles of the contour polygon. Another topologic criterion based on the optimization of the number of edges or faces meeting at each node can also be used but the results produced by the criterion proposed here are better from a shape restoration point of view.

When three nodes of the contour polygon are selected, two criteria are used to verify that a new face can be created with respect to the geometric conformity conditions. The ®rst criterion characterizes the local con®guration of the 3D contour polygon around the three selected nodes. It allows to verify if the new face created from these nodes is eectively located into the interior of the contour polygon. The second one ensures that the new face does not overlap or intersect any of its neighbouring faces. These two criteria are already used and described in a previous work [START_REF] Veâ Ron | Static polyhedron simpli®cation using error measurements[END_REF].

Meshing with a height criterion

The starting point of this meshing process is also an ordered closed contour polygon. The height criterion used here has found its basis in the remeshing problem of a simple contour polygon with four nodes as described in Fig. 22a, as shown in Fig. 22b and c, such a contour polygon has only two acceptable solutions for its remeshing.

In this case, one edge only is created when the contour is remeshed. The solution which has the highest probability to satisfy the simpli®cation criterion (i.e. one of the two faces created must intersect the error zone associated to the candidate node I) is characterized by the minimal distance, or height, h between the newly created edge and the node I removed.

More generally, to remesh an arbitrary 3D contour polygon this criterion allows to create edges which own small values of heights h. To this end, the meshing process is divided into two main steps. The ®rst one de®nes all the acceptable edge con-®gurations for the contour polygon. Then, the second one produces the new mesh of the contour polygon using an iterative process.

7.2.1. Identi®cation of the acceptable edge con-®gurations. This step de®nes the list of all the acceptable edges connecting two dierent nodes of the contour polygon separated by one intermediate node at least (i.e. an edge which connect two consecutive nodes of the contour cannot be acceptable because its does not participate to the remeshing process. Moreover, it already exists). All the acceptable edges identi®ed must not exist in the current polyhedron. Figure 23 illustrates the dierence between possible edges and acceptable ones. An edge is acceptable if its creation during the remeshing process does not produce any topologic and geometric non-conformity. Each acceptable edge divides the contour polygon into two new complementary ones.

The criterion used to determine the validity of an edge JK is based on the property of the candidate node I which should be always visible from each of its contour nodes. The criterion is described in Fig. 24 and it can be stated as follows:

. determination of an average normal Ñ to the contour polygon like the previous meshing technique (see Section 7.1 Equation ( 8)), . construction of the plane P de®ned by the node J and the normal ÑP given by: . identi®cation of the two ordered open contour polygons C 1 and C 2 de®ned from the initial contour and the edge JK, . determination of the status of each polygon C 1 and C 2 which may take the value: . same side status if all the nodes of the polygon are located on the same side of the plane P than the candidate node I, . opposite side status if all the nodes of the polygon are located on the opposite side of the plane P than the candidate node I, . unknown side status if there exists nodes located on both sides of the plane P. . comparison of the status of each polygon C 1 and C 2 to assess the validity of the edge JK: . if C 1 has a same side status and C 2 an opposite side one or conversely, the edge JK is acceptable, . if both C 1 and C 2 have a same side or an opposite side status, the edge JK is not acceptable, . if one of the contour polygons C 1 or C 2 has an unknown side status, a complementary test must take place to determine the validity of the edge JK.

The complementary test required to determine the validity of an edge when C 1 or C 2 has an unknown side status can be stated as follows (i.e. C 1 and C 2 cannot have both an unknown side status because of the property of the candidate node I which is always visible from all the nodes of its contour polygon):

. select the reference polygon C 1 or C 2 which has not an unknown side status, . for each edge E(Ne 1 , Ne 2 ) of the reference polygon, construct the lane P E de®ned by one of the nodes Ne 1 or Ne 2 of edge E and the normal ÑPE given by:

ÑPE Ne 1 Ne 2 À 4 Â Ñ, 10
. then, select all the nodes of the unknown side status polygon which own the same status than the reference polygon, . verify the location of these nodes with respect to the 3D area de®ned by all the planes previously computed. If one of the selected nodes is located into this 3D area, the edge JK cannot be accepted. Otherwise, its validity is acceptable.

Figure 26 illustrates this complementary test. In Fig. 26a the criterion is violated because the node L is located into the 3D area de®ned by P 1 , P 2 , P 3 and P. In Fig. 26b the node L has the same status that the reference contour polygon but the criterion is satis®ed and the edge JK can be accepted.

7.2.2. The iterative process producing the new mesh. An iterative process is used to generate the new mesh of the contour polygon. Each iteration subdivides a current contour polygon into two new ones. The process stops when the list of contour polygons thus produced only owns contours de®ned by three nodes. This list de®nes the new triangles of the mesh of the initial contour polygon.

Each iteration can be stated as follows:

. select in the list of the acceptable edges de®ned, the edge which owns the smallest height value h (i.e. as de®ned previously), Figure 27 illustrates this iterative process on a simple contour polygon.

Simpli®cation strategy and mixed method

The meshing technique based on an equilaterality criterion is well suited when the contour polygon extracted is located on planar areas or in areas which do not own signi®cantly distinct principal curvatures (i.e. such areas can be assimilated to spherical ones). The triangles created in these areas are as equilateral as possible and they correspond to a solution which has a high probability to satisfy the geometric restoration criterion. Moreover, their good aspect ratio (i.e. in the classical sense of this term) decreases the probability to generate geometric non-conformities.

Unfortunately, when this technique is used to remesh contour polygons located in areas which own signi®cantly dierent principal curvatures (i.e. they can be assimilated to cylindrical areas), the mesh con®guration created is not satisfying from a shape restoration point of view. Indeed, the equilaterality criterion tends to create edges perpendicular to the low principal curvature direction. Hence, the successive meshes of contour polygons along a low curvature direction generate waves which are not satisfying for a smooth restoration of the geometry (see Fig. 28b).

The second meshing technique based on a height criterion has been developed to produce well suited meshes when there exists signi®cantly distinct principal curvatures. When a contour polygon is remeshed the new edges are created along the direction of low curvature. Such a technique generates a smoother restoration of the polyhedron thus increasing the quality of the simpli®ed geometry produced (see Fig. 28c). Moreover, with the height criterion the probability for a new mesh to respect the geometric simpli®cation criterion is higher than when the equilaterality criterion is used. Therefore, this meshing technique also leads to a larger reduction of the number of nodes and faces of the polyhedron with respect to the size of the error zone than the result produced by the equilateral meshing technique.

A good strategy to remesh the contour polygon of a candidate node to removal may be guided by the knowledge of the local characteristics of the shape of the contour polygon. Indeed, such an information can be used to easily select one of the two meshing techniques proposed in accordance with their abilities described previously. Unfortunately, the criteria which can be developed to provide such information about the nature of the object shape are not ecient and robust enough to justify their use into the simpli®cation process of polyhedra. Moreover, they can lead to tedious computations which are not acceptable to preserve the eciency of the simpli®cation process. Thus, the meshing strategy used during the simpli®cation is based on a mixed use of the two meshing techniques and can be stated as follows: when a contour polygon is extracted, it is meshed using the method based on an equilaterality criterion. If the geometry is accurately restored the new mesh is kept. Otherwise, if the geometry is not correctly restored the contour polygon is remeshed using the height based method. The newly created mesh is evaluated using the simpli®cation criterion to determine whether the candidate node can be removed or not.

Such a strategy remeshes a contour polygon with triangles as equilateral as possible every time the geometric restoration criterion allows it. An acceptable global geometric con®guration of the simpli-®ed polyhedron is thus preserved. When the candidate node cannot be removed because the con-®guration of the mesh created does not satisfy the simpli®cation criterion, the height based method which generates new edges as closed to the candidate node as possible often produces a satisfying solution from a shape restoration point of view. Due to the bad aspect ratio of the triangles created with the height based method, the mixed one leads to use the equilaterality based method as much as possible. The height based one is employed only when it is necessary and ecient during a node removal. When the vertices of the initial polyhedron incorporates noise, the mixed meshing technique plus the front propagation approach produces a smoothing eect and creates an ecient noise reduction eect. Though the node selection criterion is based on curvature concepts and thus seems inadequate for noisy data, this criterion is ecient with noisy data. It gets ecient progressively, in accordance with the smoothing eect attached to the strategy set up. Figure 29 shows the smoothing eect on a test example produced from the results of a marching cubes algorithm [START_REF] Lorensen | Marching cubes: a high resolution 3D surface construction algorithm Computer Graphics[END_REF]. The size of the error zones are equal to the amplitude of the noise introduced by the measuring device and the marching cubes algorithm.

The next section illustrates the in¯uence of the meshing techniques and the smoothing eect on the quality of the simpli®ed geometry produced and on their associated number of nodes and faces.

RESULTS

The ®rst example illustrates the in¯uence of the dierent meshing techniques both from the quality of the simpli®ed geometry and from the data reduction point of views (i.e. number of nodes and faces removed from the initial polyhedron). This example is a polyhedral model of a part of a ski boot mould digitized with a 3D mechanical measuring device (i.e. in this case the measuring error is ranging from 0.01 to 0.05 mm). The main dimensions of the object are 108 Â 104 Â 21 mm. Figure 30 shows several simpli®ed geometries produced from the initial polyhedron which owns 11 730 nodes and 23 379 faces (Fig. 30a). A map of the discrete gaussian curvature is associated to each polyhedron. The discrete gaussian curvature map of the initial polyhedron illustrates the wiggles of the geometry (i.e. mainly over the blending areas) characterized by alternate negative (i.e. red color on the map) and positive gaussian curvature areas (i.e. green to black colors on the map). These wiggles were generated during the digitizing process by the mechanical sensor.

All the simpli®ed geometries (Fig. 30b±d) are produced with a tolerance value equal to 0.05 mm for every node of the initial model. The front propagation process is always used to carry out the simpli®cations.

Figure 30b shows the simpli®ed geometry produced using the equilaterality based meshing technique. The simpli®ed polyhedron owns 1624 nodes and 3167 faces. The percentage of node reduction reached is equal to 86.15%. The wiggles existing in the initial polyhedron are attenuated but the discrete gaussian curvature map shows that such wiggles still exist over the blending areas because of the meshing technique used.

Figure 30c shows the simpli®ed geometry produced using the height based meshing technique. The simpli®ed polyhedron owns 1344 nodes and 2607 faces. The percentage of node reduction reached (88.54%) is higher than with the equilaterality criterion. Nevertheless, the associated discrete gaussian curvature map shows that the quality of the simpli®ed geometry produced is not as good as the one obtained previously. The use of the height based meshing technique only for the simpli®cation of polyhedra has not appeared as an acceptable solution because of the large number of degenerated triangles in areas of low values of discrete gaussian curvature.

Such a remark leads to the use of the mixed method which produces better results both for the faces/nodes reduction and for the quality of the simpli®ed geometry. Figure 30d shows the simpli®ed geometry produced by this method. The simpli®ed Figure 31 illustrates the mixed method behaviour in accordance with the local shape con®guration of the object. The three following examples illustrates the eciency of the shape preserving approach developed. The ®rst one is a cube with a hole (Fig. 32a). It has been simpli®ed with a tolerance value higher than the radius of the cylinder part (Fig. 32b). From a geometric simpli®cation point of view, such a tolerance value allows to remove all the nodes de®ning the hole (i.e. the geometric simpli®cation criterion is not violated). Nevertheless, the simpli®ed geometry produced still includes the hole because of the use of the topologic and geometric coherence criteria developed. Therefore, the shape of the object is preserved.

Figure 33 also illustrates these coherence criteria on a closed polyhedral surface (Fig. 33a) succes-sively simpli®ed using increasing tolerance values (Fig. 33b±e). Figure 33e shows the minimal representation of the object with respect to the topologic and geometric conditions required to preserve a closed surface. Such a process is useful to generate multiple level of details of an object. It avoids degenerated con®gurations which are not interesting for computer animation and visualization purposes.

The last example (Fig. 34a) illustrates the shape preserving process on an open surface which owns boundary lines. Figure 34a shows the initial polyhedron. The simpli®ed geometry produced with a tolerance value higher than the radius of the circle is shown in Fig. 34b. The simpli®cation of the boundaries of the polyhedron satis®es the geometric and topologic criteria which allow to preserve the shape of the object. The hole de®ned on the initial model is kept despite of the fact that the tolerance value chosen allows the simpli®cation (i.e. the geometric simpli®cation criterion is veri®ed) of all the boundary nodes describing this hole.

CONCLUSION AND FUTURE WORK

The simpli®cation process developed here produces adequate simpli®ed geometries in terms of surface quality and data reduction. The shape of the object is preserved during its simpli®cation thus avoiding the creation of geometric singularities and topologic changes of the nature of the object. Meshing techniques adapted to the surface curvature produce smoother surfaces and increase the data reduction. The reduced inheritance concept developed linearizes the simpli®cation algorithm thus allowing simpli®cations of polyhedra which possess a large number of nodes and faces within acceptable times. It has been highlighted that the technique set up produces a smoothing eect which reduces the noise of input data. New developments focus on the simpli®cation of polyhedral models for structural analysis requirements. Indeed, structural analysis of parts described using polyhedra often requires geometric adaptations such as details removal or idealizations of the geometry to allow the construction of speci®c ®nite element models for example. To this end, the simpli®cation approach must be able to control the topologic modi®cations of the object. For example, a mechanical analysis of a polyhedral model of a pipe using a beam ®nite element model requires to idealize the polyhedron as a line (i.e. connected set of edges).

Other developments are planned in the ®eld of parametric surface reconstruction process. Indeed, in such case, one among the most dicult task stands into the identi®cation of an appropriate decomposition of the surface into patches. To this

Fig. 1 .

 1 Fig. 1. Non-manifold con®gurations: (a) node I cannot be classi®ed because of its connection to 4 boundary edges, (b) edge J-K cannot be classi®ed because of its connection to 3 faces.

Fig. 2 .

 2 Fig. 2. The criteria used to select the best candidate node: (a) boundary node criterion, (b) surface node criterion.

Fig. 3 .

 3 Fig. 3. Initialization of the dependency lists: (a) for the boundary edges, (b) for the faces.

Fig. 4 .

 4 Fig. 4. Update of the dependency lists: (a) for the boundary edges, (b) for the faces.

Fig. 5 .

 5 Fig. 5. Geometric rotation involved by a node removal.

Fig. 6 .

 6 Fig. 6. De®nition of the criterion used to select the signi®cant error zones.

Fig. 7 .

 7 Fig. 7. The ¯ow diagram of the simpli®cation loop.

Fig. 8 .Fig. 9 .

 89 Fig. 8. Process of a front: (a) initialization, (b) updated front after the removal of node I, (c) new front after the removal of node J.

Fig. 10 .Fig. 11 .Fig. 12 .

 101112 Fig. 10. Geometric criterion used to check the restoration of the surface: (a) the initial polyhedron with the error zones participating to the removal of node J, (b) simpli®ed polyhedron at node J in accordance with the criterion, (c) simpli®ed polyhedron at node J with violation of the criterion.

Fig. 13 .Fig. 14 .

 1314 Fig. 13. In¯uence of the meshing con®guration on the shape preservation of an object: (a) initial polyhedron, (b) extracted contour polygon already partially meshed, (c) meshing con®guration which leads to a non-conformity, (d) new meshing con®guration which preserves the shape of the object.

Fig. 15 .Fig. 16 .

 1516 Fig. 15. Particular cases involving an impossible shape restoration of the object: (a) plane contour polygon already entirely meshed, (b) the most degenerated case: a tetrahedron.

Fig. 17 .

 17 Fig. 17. Simpli®cations of polyhedron boundaries with violation of the criterion. Topologic modi®cations occur: (a) an open surface is simpli®ed into a closed one, (b) an open surface is simpli®ed into a line.

Fig. 18 .Fig. 19 .

 1819 Fig. 18. Examples of speci®c con®gurations which generate geometric singularities when the contour polygon of the boundary node I is extracted.

Fig. 20 .Fig. 21 .

 2021 Fig. 20. Identi®cation of priority nodes on the contour polygon: (a) topologic priority nodes, (b) geometric priority nodes.

Figure 25 illustrates

 25 Figure 25 illustrates these con®gurations,

Fig. 22 .

 22 Fig. 22. Meshing solutions of a simple contour polygon: (a) initial con®guration, (b) ®rst meshing solution, (c) second meshing solution which minimizes the distance between the newly created edge and the candidate node I.

Fig. 23 .

 23 Fig. 23. Dierences between possible and acceptable edges.

Fig. 24 .Fig. 25 .

 2425 Fig. 24. Parameters involved in the criterion used to determine the validity of an edge.

Fig. 26 .Fig. 27 .

 2627 Fig. 26. Complementary test used if necessary to determine the validity of an edge: (a) de®nition of the 3D area which should be empty of nodes. Here the node L violates the criterion, (b) new contour con-®guration which satis®es the criterion.

Fig. 28 .

 28 Fig. 28. In¯uence of the meshing technique on the smoothness of the simpli®ed geometry: (a) initial polyhedron, (b) simpli®ed geometry with the equilaterality based method, (c) simpli®ed geometry produced with the height based method and the same tolerance values.

Fig. 29 .

 29 Fig. 29. Smoothing eect produced on noisy data: (a) initial polyhedron, (b) simpli®ed geometry produced using the mixed meshing technique and the front propagation process. The error zone assigned to each node is equal to the size of the stairs (20.7 mm).

Fig. 30 .

 30 Fig. 30. Simpli®ed geometry of a part of a ski boot mould using the dierent meshing techniques and their associated discrete gaussian curvature maps. The tolerance value is equal to 0.05 mm and the front propagation process has been applied: (a) the initial polyhedron with 11 730 nodes and 23 379 faces, (b) simpli®ed one using the equilaterality based meshing technique (1624 nodes, 3167 faces, 86.15% reduced), (c) simpli®ed polyhedron produced with the height based meshing technique (1344 nodes, 2607 faces, 88.54% reduced), (d) simpli®ed polyhedron produced with the mixed meshing technique (949 nodes, 1817 faces, 91.9% reduced).

Fig. 31 .Fig. 32 .

 3132 Fig. 31. Detail views of the part of a ski boot mould sim-pli®ed using the mixed meshing technique. The shape of the triangles produced are adapted to the shape of the object.

Fig. 33 .

 33 Fig. 33. Topology and geometry coherence checking during the simpli®cation of a closed surface: (a) initial polyhedron, (b) simpli®ed one with a tolerance value equal to 0.15 mm, (c) simpli®cation with a tolerance value equal to 1.0 mm, (d) rough simpli®ed geometry, (e) minimal simpli®ed geometry (i.e. a tetrahedron) produced with a tolerance value larger than the size of the initial object.

Fig. 34 .

 34 Fig. 34. Topology and geometry preservation of boundaries during the simpli®cation of a simple planar open surface within a hole: (a) initial polyhedron, (b) simpli®ed polyhedron with a tolerance value higher than the radius of the circle. The shape of the object is preserved.

end, the fronts produced during the simpli®cation of a polyhedron may form the basis to automatically ®nd an adequate set of patch boundaries.


Ultrabroadband spectroscopy is a promising novel approach to overcome two major hurdles which have so far limited the application of THz spectroscopy for security applications: the increased bandwidth enables to record several characteristic spectroscopic features and the technique allows for remote detection. However, for real applications several parameters still have to be optimized. A comprehensive evaluation of the potential of this technique includes for example a detailed study of the generation process in an air plasma. We present some aspects of our joint theoretical and experimental evaluation of the technique for defense and civil security applications.

I. INTRODUCTION

ERAHERTZ spectroscopy has proven to be a versatile tool for the detection of illicit substances like explosives [START_REF] Federici | THz imaging and sensing for security applications -explosives, weapons and drugs[END_REF], drugs [START_REF] Kawase | Non-destructive terahertz imaging of illicit drugs using spectral fingerprints[END_REF] or counterfeit medicines [3]. Especially the detection of explosives has attracted much interest in the security and defense sector due to the major advantages THz technology has to offer, like penetration of non-conducting materials, minimal health-risk for operators and characteristic fingerprints of many security relevant materials at THz frequencies. However, typical THz systems offer just a limited bandwidth of up to 4 THz. For a non-ambiguous identification of dangerous materials, this limited bandwidth can be a serious problem, since, at least in explosives, many characteristic lines tend to show up at frequencies above 2 THz. Hence, in such systems just a small number of lines can be used for the identification of a material. However, since chirped-phase amplified laser systems nowadays deliver high intensities within femtosecond time scales, new mechanisms for creating THz radiation have become accessible, offering a strongly enhanced bandwidth [START_REF] Babushkin | Tailoring terahertz radiation by controlling tunnel photoionization events in gases[END_REF]. Recent reports on two-color laser plasma THz generation and air biased coherent detection have attracted significant interest [START_REF] Cook | Intense terahertz pulses by fourwave rectification in air[END_REF] [START_REF] Dai | Detection of broadband terahertz waves with a laser-induced plasma in gases[END_REF]. Such systems offer typically a bandwidth exceeding 40 THz, making it especially useful for the characterization and identification of different materials, including explosives [START_REF] Dai | Terahertz Air Photonics for Standoff Explosive Detection[END_REF]. First reports have thus sparked once again the interest in THz techniques for security applications. A detailed evaluation of the technique considering several parameters could thus help to confirm this potential.

II. RESULTS

In a first step, we have updated our extensive data base of the spectra of a large variety of explosives, including new formulations of home-made explosives, by adding novel broadband spectroscopy data. Figure 1 shows the absorption coefficient of TNB as an example. The blue line gives the results obtained in the plasma based system, while the green line is obtained in a conventional THz TDS system based on photoconductive antennas as emitter and detector. For better visibility a small offset has been introduced for the green line. The effects of several laser and gas parameters on the generation efficiency and spectral performances will be evaluated theoretically in view of further experimental validation. Preliminary results based on theoretical estimates and past numerical computations will be recalled. They mostly concern intense and broadband THz pulses generated by twocolor laser pulses, e.g., a fundamental pulse and its second harmonic created in a frequency doubling crystal. We will discuss the possibility of increasing the energy yield in the spectral range between 1 and 100 THz for two optical pulse components co-progapating either in tightly focused geometry [START_REF] Babushkin | Ultrafast spatiotemporal dynamics of Terahertz generation by ionizing two-color femtosecond pulses in gases[END_REF][START_REF] Kim | Coherent control of terahertz supercontinuum generation in ultrafast laser-gas interactions[END_REF] or in filamentation regime in a noble gas and air [START_REF] Bergé | 3D Numerical simulations of THz generation by two-color laser filaments[END_REF]. Prior use of a noble gas (argon) is justified by the simplicity of the gas response compared to that of air components. Particular attention will be paid to pump pulses operating in the near infrared, i. e., at 800 nm. Our theoretical analysis emphasizes the importance of tunneling ionization [START_REF] Babushkin | Tailoring terahertz radiation by controlling tunnel photoionization events in gases[END_REF][START_REF] Babushkin | Ultrafast spatiotemporal dynamics of Terahertz generation by ionizing two-color femtosecond pulses in gases[END_REF][START_REF] Kim | Coherent control of terahertz supercontinuum generation in ultrafast laser-gas interactions[END_REF], promoting a steplike increase in the electron density and asymmetric ionization instants favoring the creation of nonzero low-frequency charged currents responsible for broadband THz emission. Figure 2 gives a schematic overview on this two-color photocurrent mechanism. We will also discuss alternative potential mechanisms for Thz generation such as longitudinal ponderomotive forces produced at high laser intensities [START_REF] Sprangle | Ultrashort laser pulses and electromagnetic pulse generation in air and on dielectric surfaces[END_REF]. We shall present semi-analytical evaluations of laser-driven THz spectra based on the so-called local current model in order to optimize and design the THz spectrum and fields through ionization-induced photocurrents.

S. Engelbrecht1 , Luc Bergé2 , Stefan Skupin3 , T.Wang4 , P. U. Jepsen 4

and B. M. Fischer 1

The growth in the THz yield caused by an increase of the pump laser wavelength will be discussed [START_REF] Bergé | 3D Numerical simulations of THz generation by two-color laser filaments[END_REF]. The extreme sensitivity of THz radiation spectrum on the configuration of the femtosecond laser pulses can finally be exploited to tailor specific sources to the application. We numerically examine multi-colored pulse configurations extended to three and more optical frequencies, as these can be produced nowadays by optical parametric amplifiers. Since the relative phases of all frequencies and their respective energies can be in principle controlled, these degrees of freedom will be used to increase substantially the THz pulse energy by shaping the laser pulses in optimal waveforms, such as, e.g. sawtooth shapes [START_REF] Gonzalez De Alaiza Martinez | Boosting Terahertz generation in laser-field ionized gases using a sawtooth wave shape[END_REF].

III. SUMMARY

In summary, we have measured the THz response of several explosives including TNT, TNB, RDX, HMX and ANTA, using a broadband plasma based THz spectroscopic system. The gereration efficiency has been evaluated theoretically by varying laser-gas parameters in order to confirm the potential of the technique for increased performances for safety and security applications. , showing the step-wise increase of the free electron density (filled green curve) by ionization events located at times t n with extremal electric field E(t) (red curve). Free electrons produced in the various ionization events are then accelerated and produce the current J(t) (blue curve). (e) Zoom into the THz range of (c), explaining the spectral structure of the radiation E J emitted by the current J. Each ionization event at time t n induces broadband radiation E J n with comparable amplitudes but different phases (blue curves). The sum of all partial contributions in yields the resulting spectrum E J (filled red curve). The spectral structure of E J is solely determined by spectral interference of different E J n .

Figure 1

 1 Figure 1 Absorption coefficient of TNB (blue curves with error bars). For comparison the green line shows the result of a conventional THz TDS System.

Figure 2

 2 Figure 2 Mechanism and spectral properties of radiation generated by ionizing two-color pulses. (a) Schematic setup, (b) twocolor pump field E(t) (red curve) consisting of fundamental and second harmonic frequency, and current J(t) (blue curve) induced by tunneling-ionization. (c) Spectrum of the generated radiation vs. frequency on a large frequency scale from THz to VUV. (d) Zoom into (b), showing the step-wise increase of the free electron density (filled green curve) by ionization events located at times t n with extremal electric field E(t) (red curve). Free electrons produced in the various ionization events are then accelerated and produce the current J(t) (blue curve). (e) Zoom into the THz range of (c), explaining the spectral structure of the radiation E J emitted by the current J. Each ionization event at time t n induces broadband radiation E J n with comparable amplitudes but different phases (blue curves). The sum of all partial contributions in yields the resulting spectrum E J (filled red curve). The spectral structure of E J is solely determined by spectral interference of different E J n .

French-German Research Institute of Saint Louis, 68301 Saint Louis, France

CEA / DAM Ile De France, Bruyères-le-Châtel, 91297 Arpajon Cedex, France

Univ. Bordeaux -CNRS -CEA, Centre Lasers Intenses et Applications, UMR 5107, 33405 Talence, France

Department of Photonics Engineering, Technical University of Denmark, Kgs. Lyngby 2800, DenmarkUltrabroadband spectroscopy for security applications