mailleur_delaunay.cpp

Aller à la documentation de ce fichier.

//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//  MAGiC
//####//  Jean Christophe Cuilliere et Vincent FRANCOIS
//####//  Departement de Genie Mecanique - UQTR
//####//------------------------------------------------------------
//####//  MAGIC est un projet de recherche de l equipe ERICCA
//####//  du departement de genie mecanique de l Universite du Quebec a Trois Rivieres
//####//  http://www.uqtr.ca/ericca
//####//  http://www.uqtr.ca/
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//
//####//       mailleur_delaunay.cpp
//####//
//####//------------------------------------------------------------
//####//------------------------------------------------------------
//####//    COPYRIGHT 2000-2024
//####//  jeu 13 jun 2024 11:58:55 EDT
//####//------------------------------------------------------------
//####//------------------------------------------------------------
 
 
#include "gestionversion.h"
#include "mailleur_delaunay.h"
#include "mailleur3d_optimisation.h"
#include "dly_noeud.h"
#include "dly_tetra.h"
#include "dly_triangle.h"
#include "dly_segment.h"
#include "mg_maillage.h"
#include "robustpredicates.hxx"
#include <algorithm>
#include <math.h>
#include "mg_gestionnaire.h"
#include "ot_cpu.h"
#include "m3d_noeud.h"
#include "m3d_tetra.h"
 
 
 
MAILLEUR_DELAUNAY::MAILLEUR_DELAUNAY(MG_MAILLAGE* m,FCT_TAILLE *cartetmp,double crit_arret,class OT_CPU* comp):MAILLEUR(comp),carte(cartetmp),mai(m),critere_arret(crit_arret),niveau_optimisation(2),typemailleur(DELAUNAYCARTE)
{
    robustPredicates::exactinit();
}
 
MAILLEUR_DELAUNAY::MAILLEUR_DELAUNAY(MG_MAILLAGE* m,BOITE_3D boiteext,class OT_CPU* comp):MAILLEUR(comp),boiteexterieur(boiteext),mai(m),niveau_optimisation(2),typemailleur(DELAUNAYLISTENOEUD)
{
    robustPredicates::exactinit();
    carte=NULL;
}
 
MAILLEUR_DELAUNAY::~MAILLEUR_DELAUNAY()
{
    for (int i=0;i<tabnoeud.size();i++)
        delete tabnoeud[i];
    for (int i=0;i<tabtri.size();i++)
        delete tabtri[i];
    for (int i=0;i<tabtet.size();i++)
        delete tabtet[i];
}
 
int MAILLEUR_DELAUNAY::maille(class MG_GROUPE_TOPOLOGIQUE* mggt)
{
    affiche((char*)"Initialisation Delaunay");
    initialise_maillage();
    if (compteur!=NULL) compteur->ajouter_etape("Initialisation maillage");
    
    affiche((char*)"Maillage");
    raffine_maillage();
    if (compteur!=NULL) compteur->ajouter_etape("Insertion de points");
    
    affiche((char*)"Création du maillage final");
    transfert_maillage(&tabnoeud,NULL,&tabtet);
    if (compteur!=NULL) compteur->ajouter_etape("Création du maillage");
    
    
    affiche((char*)"Optimisation de maillage");
    MAILLEUR3D_OPTIMISATION opt(mai,niveau_optimisation);
    if (affichageactif) opt.active_affichage(affiche2);
    opt.optimise(NULL);
    if (compteur!=NULL) compteur->ajouter_etape("Optimisation du maillage");
    affiche((char*)"Fin Delaunay");
    return OK;
}
 
void MAILLEUR_DELAUNAY::change_niveau_optimisation(int num)
{
niveau_optimisation=num;
}
 
void MAILLEUR_DELAUNAY::ajouter_noeud(double &x, double &y, double &z,double epsbordure)
{
 
  
xnoeud.push_back(x);
ynoeud.push_back(y);
znoeud.push_back(z);
}
    
void MAILLEUR_DELAUNAY::insere_noeud_delaunay(DLY_TETRA* tet,double x,double y,double z)
{
DLY_TETRA* tetbase=get_tetra(tet,x,y,z);
            std::vector<DLY_TETRA*> tetdetruit;
            std::vector<DLY_TETRA*> tetcree;
            std::vector<DLY_TRIANGLE*> basetri;
            ajoute_tetra_cavite(tetbase,tetdetruit,basetri);
            for (int i=0;i<tetdetruit.size();i++)
            {
                DLY_TETRA* tettmp=tetdetruit[i];
                if (tettmp->get_voisin1()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin1());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin1()->point_dans_le_tetra(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin1(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin2()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin2());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin2()->point_dans_le_tetra(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin2(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin3()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin3());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin3()->point_dans_le_tetra(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin3(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin4()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin4());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin4()->point_dans_le_tetra(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin4(),tetdetruit,basetri);
                }
            }
            int nbtetrabase=tetdetruit.size();
            for (int i=0;i<tetdetruit.size();i++)
            {
                DLY_TETRA* tettmp=tetdetruit[i];
                if (tettmp->get_voisin1()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin1());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin1()->point_dans_la_sphere(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin1(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin2()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin2());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin2()->point_dans_la_sphere(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin2(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin3()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin3());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin3()->point_dans_la_sphere(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin3(),tetdetruit,basetri);
                }
                if (tettmp->get_voisin4()!=NULL)
                {
                    std::vector<DLY_TETRA*>::iterator itv2=find(tetdetruit.begin(),tetdetruit.end(),tettmp->get_voisin4());
                    if (itv2==tetdetruit.end())
                        if (tettmp->get_voisin4()->point_dans_la_sphere(x,y,z)!=0)
                            ajoute_tetra_cavite(tettmp->get_voisin4(),tetdetruit,basetri);
                }  
            }
               
 
            int res=0;
            do
            {
                res=modifie_cavite(tetdetruit,basetri,nbtetrabase,x,y,z);
            }
            while (res==0);
 
 
 
 
            for (int i=0;i<tetdetruit.size();i++)
            {
                /*std::multimap<double, DLY_TETRA*, std::greater<double> >::iterator it2=front.find(tetdetruit[i]->get_critere_subdivision());
                while ((*it2).second!=tetdetruit[i])
                    it2++;
                front.erase(it2);*/
                retirer_front(tetdetruit[i]->get_segment1());
                retirer_front(tetdetruit[i]->get_segment2());
                retirer_front(tetdetruit[i]->get_segment3());
                retirer_front(tetdetruit[i]->get_segment4());
                retirer_front(tetdetruit[i]->get_segment5());
                retirer_front(tetdetruit[i]->get_segment6());
                    
            }
            DLY_NOEUD* no=new DLY_NOEUD(tabnoeud.size(),x,y,z);
            tabnoeud.push_back(no);
            for (int i=0;i<basetri.size();i++)
            {
                int frontiere=basetri[i]->est_frontiere();
                int coplanaire=basetri[i]->est_coplanaire(no->get_x(),no->get_y(),no->get_z());
                if ((frontiere==0) || ((frontiere==1) && (coplanaire==0)))
                {
                    DLY_TETRA* tetnv=cree_tetra(basetri[i]->get_noeud1(),basetri[i]->get_noeud2(),basetri[i]->get_noeud3(),no);
                    tetcree.push_back(tetnv);
                }
            }
             for (int i=0;i<tetdetruit.size();i++)
                tetdetruit[i]->ajoute_fils(tetcree);
            for (int i=0;i<tetcree.size();i++)
            {
                mise_a_jour_voisin(tetcree[i]);
                if (tetcree[i]->get_voisin1()!=NULL) mise_a_jour_voisin(tetcree[i]->get_voisin1());
                if (tetcree[i]->get_voisin2()!=NULL) mise_a_jour_voisin(tetcree[i]->get_voisin2());
                if (tetcree[i]->get_voisin3()!=NULL) mise_a_jour_voisin(tetcree[i]->get_voisin3());
                if (tetcree[i]->get_voisin4()!=NULL) mise_a_jour_voisin(tetcree[i]->get_voisin4());
            }
}
 
 
void  MAILLEUR_DELAUNAY::raffine_maillage(void)
{
if (typemailleur==DELAUNAYCARTE)
    while ((*(front_trie.begin())).first>critere_arret)
    //for (int jj=0;jj<10000;jj++)
    {
        std::multimap<double, DLY_SEGMENT*, std::greater<double> >::iterator it=front_trie.begin();
        //DLY_TETRA* tet=(*it).second;
        DLY_SEGMENT* seg=(*it).second;
        DLY_TETRA* tet=seg->get_tetra_feuille();
        std::vector<double> lstptdecoup;
        seg->decoupe_noeud(lstptdecoup);
        int nbptdecoup=lstptdecoup.size()/3;
        for (int j=0;j<nbptdecoup;j++)
        {
            double x=lstptdecoup[3*j];
            double y=lstptdecoup[3*j+1];
            double z=lstptdecoup[3*j+2];
            insere_noeud_delaunay(tet,x,y,z);
         
            
            double volold=0.;
            double volnew=0.;
            /*for (int i=0;i<tetdetruit.size();i++)
                volold=volold+tetdetruit[i]->calcul_volume(NULL,0);
            for (int i=0;i<tetcree.size();i++)
                volnew=volnew+tetcree[i]->calcul_volume(NULL,0);
            if (fabs(volold-volnew)>0.000000000001*volold)
                //std::cout << volold << " remplacé par " << volnew << " Étape " << jj << " " << j << std::endl;
*/
           
           /* for (int i=0;i<tabtet.size();i++)
            {
                DLY_TETRA* tet=tabtet[i];
                if (tet->get_feuille()==0) continue;
                if (tet->get_voisin1()!=NULL)
                    if (tet->get_voisin1()->get_feuille()==0)
                    {
                        std::cout << "bug1 " << jj << " "<< j<< std::endl;
                        return;
                    }
                if (tet->get_voisin2()!=NULL)
                    if (tet->get_voisin2()->get_feuille()==0)
                    {
                        std::cout << "bug2 " << jj << " "<< j<< std::endl;
                        return;
                    }
                if (tet->get_voisin3()!=NULL)
                    if (tet->get_voisin3()->get_feuille()==0)
                    {
                        std::cout << "bug3 "<< jj << " "<< j << std::endl;
                        return;
                    }
                if (tet->get_voisin4()!=NULL)
                    if (tet->get_voisin4()->get_feuille()==0)
                    {
                        std::cout << "bug4 "<< jj << " "<< j << std::endl;
                        return;
                    }
              
            }*/
           /* mai=new MG_MAILLAGE(NULL);
            MG_GESTIONNAIRE g;
            g.ajouter_mg_maillage(mai);
            transfert_maillage(&tabnoeud,NULL,&tabtet);
            g.enregistrer("test.magic");*/
            
        }
    }
    
if (typemailleur==DELAUNAYLISTENOEUD)
    for (int i=0;i<xnoeud.size();i++)
      insere_noeud_delaunay(NULL,xnoeud[i],ynoeud[i],znoeud[i]);  
}
 
void MAILLEUR_DELAUNAY::ajouter_front(double crit,DLY_SEGMENT* seg)
{
if (crit>critere_arret)
  {
  std::pair<const unsigned long long,DLY_SEGMENT*> tmp((const unsigned long long)seg,seg);
  std::pair<std::map<const unsigned long long,DLY_SEGMENT*>::iterator,bool> res=front.insert(tmp);
  if (res.second==true)
      {
      seg->change_critere(crit);
      std::pair<double,DLY_SEGMENT*> tmp2(crit,seg);
      front_trie.insert(tmp2);
      }
  }
}
void MAILLEUR_DELAUNAY::retirer_front(DLY_SEGMENT* seg)
{
std::map<const unsigned long long,DLY_SEGMENT*>::iterator it=front.find((const unsigned long long)seg);
if (it==front.end()) return;
front.erase(it);
std::multimap<double,DLY_SEGMENT*,std::greater<double> >::iterator it2=front_trie.find(seg->get_critere());
while ((*it2).second!=seg)
      it2++;
front_trie.erase(it2);
}
int MAILLEUR_DELAUNAY::modifie_cavite(std::vector<DLY_TETRA*> &cavite,std::vector<DLY_TRIANGLE*> &basetri,int nbbase,double x, double y,double z)
{
    std::map<unsigned long long,DLY_TETRA*> tetasupprimercavite;
    for (int i=0;i<basetri.size();i++)
    {
        DLY_TRIANGLE* tri=basetri[i];
        DLY_TETRA* inte=NULL;
        DLY_TETRA* exte=NULL;
        for (int j=0;j<tri->get_nb_tetra();j++)
        {
            DLY_TETRA* tet=tri->get_tetra(j);
            if (tet->get_feuille()==1)
            {
                std::vector<DLY_TETRA*>::iterator it=find(cavite.begin(),cavite.end(),tet);
                if (it==cavite.end()) exte=tet;
                else inte=tet;
            }
        }
        double nor[3];
        int base=0;
        for (int j=0;j<nbbase;j++)
            if (inte==cavite[j]) base=1;
        if (base==1) continue;
        if (inte->get_triangle1()==tri) inte->get_normal1(nor);
        if (inte->get_triangle2()==tri) inte->get_normal2(nor);
        if (inte->get_triangle3()==tri) inte->get_normal3(nor);
        if (inte->get_triangle4()==tri) inte->get_normal4(nor);
        nor[0]=-nor[0];
        nor[1]=-nor[1];
        nor[2]=-nor[2];
        double xyzo[3];
        tri->get_noeud1()->get_coord(xyzo);
        OT_VECTEUR_3D vecdir(x-xyzo[0],y-xyzo[1],z-xyzo[2]);
        OT_VECTEUR_3D normal(nor);
        vecdir.norme();
        double ps=vecdir*normal;
        if (ps<0.000000001)
        {
            tri->est_frontiere();
            //retire_tetra_cavite(inte,cavite,basetri);
            unsigned long long adresse=(unsigned long long)inte;
            tetasupprimercavite.insert(std::pair<unsigned long long,DLY_TETRA*>(adresse,inte));
            
        }
    }
    int nbtetasupprimer=tetasupprimercavite.size();
    if (nbtetasupprimer==0) return 1;
    for (std::map<unsigned long long,DLY_TETRA*>::iterator it=tetasupprimercavite.begin();it!=tetasupprimercavite.end();it++)
      retire_tetra_cavite((*it).second,cavite,basetri);
 
    return 0;
}
 
 
void MAILLEUR_DELAUNAY::retire_tetra_cavite(DLY_TETRA* tet,std::vector<DLY_TETRA*> &cavite,std::vector<DLY_TRIANGLE*> &basetri)
{
    std::vector<DLY_TETRA*>::iterator it=find(cavite.begin(),cavite.end(),tet);
    cavite.erase(it);
    std::vector<DLY_TRIANGLE*>::iterator itv=find(basetri.begin(),basetri.end(),tet->get_triangle1());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle1());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle2());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle2());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle3());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle3());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle4());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle4());
    else basetri.erase(itv);
}
 
void MAILLEUR_DELAUNAY::ajoute_tetra_cavite(DLY_TETRA* tet,std::vector<DLY_TETRA*> &cavite,std::vector<DLY_TRIANGLE*> &basetri)
{
    cavite.push_back(tet);
    std::vector<DLY_TRIANGLE*>::iterator itv=find(basetri.begin(),basetri.end(),tet->get_triangle1());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle1());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle2());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle2());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle3());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle3());
    else basetri.erase(itv);
    itv=find(basetri.begin(),basetri.end(),tet->get_triangle4());
    if (itv==basetri.end()) basetri.push_back(tet->get_triangle4());
    else basetri.erase(itv);
}
 
void  MAILLEUR_DELAUNAY::initialise_maillage(void)
{
    BOITE_3D boite;
    if (typemailleur==DELAUNAYCARTE)
      {
      boite=carte->get_boite_3D();
      boite.change_grosseur(0.9999999999999);
      }
    if (typemailleur==DELAUNAYLISTENOEUD)
      {
      boite=boiteexterieur;
      }
    double xmin=boite.get_xmin();
    double ymin=boite.get_ymin();
    double zmin=boite.get_zmin();
    double xmax=boite.get_xmax();
    double ymax=boite.get_ymax();
    double zmax=boite.get_zmax();
    DLY_NOEUD* no1=new DLY_NOEUD(tabnoeud.size(),xmin,ymin,zmin);
    tabnoeud.push_back(no1);
    DLY_NOEUD* no2=new DLY_NOEUD(tabnoeud.size(),xmin,ymax,zmin);
    tabnoeud.push_back(no2);
    DLY_NOEUD* no3=new DLY_NOEUD(tabnoeud.size(),xmax,ymax,zmin);
    tabnoeud.push_back(no3);
    DLY_NOEUD* no4=new DLY_NOEUD(tabnoeud.size(),xmax,ymin,zmin);
    tabnoeud.push_back(no4);
    DLY_NOEUD* no5=new DLY_NOEUD(tabnoeud.size(),xmin,ymin,zmax);
    tabnoeud.push_back(no5);
    DLY_NOEUD* no6=new DLY_NOEUD(tabnoeud.size(),xmin,ymax,zmax);
    tabnoeud.push_back(no6);
    DLY_NOEUD* no7=new DLY_NOEUD(tabnoeud.size(),xmax,ymax,zmax);
    tabnoeud.push_back(no7);
    DLY_NOEUD* no8=new DLY_NOEUD(tabnoeud.size(),xmax,ymin,zmax);
    tabnoeud.push_back(no8);
    DLY_TETRA* tet1=cree_tetra(no2,no1,no3,no6);
    DLY_TETRA* tet2=cree_tetra(no3,no1,no4,no5);
    DLY_TETRA* tet3=cree_tetra(no3,no1,no5,no6);
    DLY_TETRA* tet4=cree_tetra(no8,no5,no7,no4);
    DLY_TETRA* tet5=cree_tetra(no7,no5,no6,no3);
    DLY_TETRA* tet6=cree_tetra(no4,no3,no5,no7);
    mise_a_jour_voisin(tet1);
    mise_a_jour_voisin(tet2);
    mise_a_jour_voisin(tet3);
    mise_a_jour_voisin(tet4);
    mise_a_jour_voisin(tet5);
    mise_a_jour_voisin(tet6);
    char message[255];
    sprintf(message,"     Volume espace : %lf",(xmax-xmin)*(ymax-ymin)*(zmax-zmin));
    if (affichageactif) affiche(message);
}
void  MAILLEUR_DELAUNAY::mise_a_jour_voisin(DLY_TETRA* tet)
{
    int nb=tet->get_triangle1()->get_nb_tetra();
    for (int i=0;i<nb;i++)
    {
        DLY_TETRA* tetmp=tet->get_triangle1()->get_tetra(i);
        if (tetmp->get_feuille()==1)
            if (tetmp!=tet) tet->change_voisin1(tetmp);
    }
    nb=tet->get_triangle2()->get_nb_tetra();
    for (int i=0;i<nb;i++)
    {
        DLY_TETRA* tetmp=tet->get_triangle2()->get_tetra(i);
        if (tetmp->get_feuille()==1)
            if (tetmp!=tet) tet->change_voisin2(tetmp);
    }
    nb=tet->get_triangle3()->get_nb_tetra();
    for (int i=0;i<nb;i++)
    {
        DLY_TETRA* tetmp=tet->get_triangle3()->get_tetra(i);
        if (tetmp->get_feuille()==1)
            if (tetmp!=tet) tet->change_voisin3(tetmp);
    }
    nb=tet->get_triangle4()->get_nb_tetra();
    for (int i=0;i<nb;i++)
    {
        DLY_TETRA* tetmp=tet->get_triangle4()->get_tetra(i);
        if (tetmp->get_feuille()==1)
            if (tetmp!=tet) tet->change_voisin4(tetmp);
    }
}
 
 
DLY_TETRA* MAILLEUR_DELAUNAY::cree_tetra(DLY_NOEUD* n1,DLY_NOEUD* n2,DLY_NOEUD* n3,DLY_NOEUD* n4)
{
    double xyz1[3],xyz2[3],xyz3[3],xyz4[3];
    n1->get_coord(xyz1);
    n2->get_coord(xyz2);
    n3->get_coord(xyz3);
    n4->get_coord(xyz4);
    double qual=OPERATEUR::qualite_tetra(xyz1,xyz2,xyz3,xyz4);
    DLY_TETRA* tet;
    if (!(qual>0.))
          {
          DLY_NOEUD* ntmp=n1;
          n1=n2;
          n2=ntmp;
          }
    tet=new DLY_TETRA(n1,n2,n3,n4,fabs(qual));
    tabtet.push_back(tet);
    tet->change_triangle1(get_triangle(n1,n2,n3));
    tet->change_triangle2(get_triangle(n1,n2,n4));
    tet->change_triangle3(get_triangle(n1,n3,n4));
    tet->change_triangle4(get_triangle(n2,n3,n4));
    tet->change_segment1(get_segment(n1,n2));
    tet->change_segment2(get_segment(n1,n3));
    tet->change_segment3(get_segment(n1,n4));
    tet->change_segment4(get_segment(n2,n3));
    tet->change_segment5(get_segment(n2,n4));
    tet->change_segment6(get_segment(n3,n4));
    //    std::pair<double,DLY_TETRA*> tmp(tet->get_critere_subdivision(),tet);
    if (typemailleur==DELAUNAYCARTE)
    {
    ajouter_front(tet->get_segment1()->calcul_longueur(carte,pas,1),tet->get_segment1());
    ajouter_front(tet->get_segment2()->calcul_longueur(carte,pas,1),tet->get_segment2());
    ajouter_front(tet->get_segment3()->calcul_longueur(carte,pas,1),tet->get_segment3());
    ajouter_front(tet->get_segment4()->calcul_longueur(carte,pas,1),tet->get_segment4());
    ajouter_front(tet->get_segment5()->calcul_longueur(carte,pas,1),tet->get_segment5());
    ajouter_front(tet->get_segment6()->calcul_longueur(carte,pas,1),tet->get_segment6());
    }
    return tet;
}
DLY_SEGMENT* MAILLEUR_DELAUNAY::get_segment(DLY_NOEUD* n1,DLY_NOEUD* n2)
{
    
    DLY_NOEUD* no;
    if (n1->get_num()<n2->get_num()) no=n1;
    else no=n2;
    DLY_SEGMENT* seg=no->get_lien_segment(n1,n2);
    if (seg==NULL)
    {
        seg=new DLY_SEGMENT(n1,n2);
        tabseg.push_back(seg);
        no->insere_lien_segment(seg);
    }
    return seg;
}
 
DLY_TRIANGLE* MAILLEUR_DELAUNAY::get_triangle(DLY_NOEUD* n1,DLY_NOEUD* n2,DLY_NOEUD* n3)
{
    DLY_NOEUD* no;
    if (n1->get_num()<n2->get_num()) no=n1;
    else no=n2;
    if (n3->get_num()<no->get_num()) no=n3;
    DLY_TRIANGLE* tri=no->get_lien_triangle(n1,n2,n3);
    if (tri==NULL)
    {
        tri=new DLY_TRIANGLE(n1,n2,n3);
        tabtri.push_back(tri);
        no->insere_lien_triangle(tri);
    }
    return tri;
}
 
 
DLY_TETRA* MAILLEUR_DELAUNAY::get_tetra(double x,double y,double z)
{
    DLY_TETRA* tet;
    tet=get_tetra(tabtet[0],x,y,z);
    if (tet!=NULL) return tet;
    tet=get_tetra(tabtet[1],x,y,z);
    if (tet!=NULL) return tet;
    tet=get_tetra(tabtet[2],x,y,z);
    if (tet!=NULL) return tet;
    tet=get_tetra(tabtet[3],x,y,z);
    if (tet!=NULL) return tet;
    tet=get_tetra(tabtet[4],x,y,z);
    if (tet!=NULL) return tet;
    tet=get_tetra(tabtet[5],x,y,z);
    if (tet!=NULL) return tet;
    return NULL;
}
 
DLY_TETRA* MAILLEUR_DELAUNAY::get_tetra(DLY_TETRA* tet,double x,double y,double z)
{
    if (tet==NULL) return get_tetra(x,y,z);
    if (tet->point_dans_le_tetra(x,y,z))
    {
        if (tet->get_feuille()==1) return tet;
        int nb=tet->get_nb_fils();
        for (int i=0;i<nb;i++)
        {
            DLY_TETRA* tetrep=get_tetra(tet->get_fils(i),x,y,z);
            if (tetrep!=NULL) return tetrep;
        }
    }
    return NULL;
}
 
 
void MAILLEUR_DELAUNAY::transfert_maillage(std::vector<DLY_NOEUD*> *tabn,std::vector<DLY_TRIANGLE*> *tabe2d,std::vector<DLY_TETRA*> *tabe3d)
{
    for (int i=0;i<tabn->size();i++)
    {
        DLY_NOEUD *no=(*tabn)[i];
        M3D_NOEUD* noeud=new M3D_NOEUD(NULL,no->get_x(),no->get_y(),no->get_z(),MAGIC::ORIGINE::MAILLEUR_AUTO);
        mai->ajouter_mg_noeud(noeud);
        no->change_noeud(noeud);
        noeud->etat_actif();
    }
    if (tabe2d!=NULL)
    {
        for (int i=0;i<tabe2d->size();i++)
        {
            DLY_TRIANGLE* tri=(*tabe2d)[i];
            if (tri->est_frontiere())
                MG_TRIANGLE *mgtri=mai->ajouter_mg_triangle(NULL,tri->get_noeud1()->get_noeud(),tri->get_noeud2()->get_noeud(),tri->get_noeud3()->get_noeud(),MAGIC::ORIGINE::MAILLEUR_AUTO);
        }
    }
    else
    {
        double vol=0.;
        double nbmaitheo=0;
        for (int i=0;i<tabe3d->size();i++)
        {
            DLY_TETRA* tet=(*tabe3d)[i];
            if (tet->get_feuille()==1)
            {
                MG_TRIANGLE* mgtriangle1=mai->get_mg_triangle(tet->get_noeud1()->get_noeud()->get_id(),tet->get_noeud3()->get_noeud()->get_id(),tet->get_noeud2()->get_noeud()->get_id());
                MG_TRIANGLE* mgtriangle2=mai->get_mg_triangle(tet->get_noeud1()->get_noeud()->get_id(),tet->get_noeud2()->get_noeud()->get_id(),tet->get_noeud4()->get_noeud()->get_id());
                MG_TRIANGLE* mgtriangle3=mai->get_mg_triangle(tet->get_noeud2()->get_noeud()->get_id(),tet->get_noeud3()->get_noeud()->get_id(),tet->get_noeud4()->get_noeud()->get_id());
                MG_TRIANGLE* mgtriangle4=mai->get_mg_triangle(tet->get_noeud1()->get_noeud()->get_id(),tet->get_noeud4()->get_noeud()->get_id(),tet->get_noeud3()->get_noeud()->get_id());
                if (mgtriangle1==NULL) mgtriangle1=mai->ajouter_mg_triangle(NULL,tet->get_noeud1()->get_noeud(),tet->get_noeud3()->get_noeud(),tet->get_noeud2()->get_noeud(),MAGIC::ORIGINE::MAILLEUR_AUTO);
                if (mgtriangle2==NULL) mgtriangle2=mai->ajouter_mg_triangle(NULL,tet->get_noeud1()->get_noeud(),tet->get_noeud2()->get_noeud(),tet->get_noeud4()->get_noeud(),MAGIC::ORIGINE::MAILLEUR_AUTO);
                if (mgtriangle3==NULL) mgtriangle3=mai->ajouter_mg_triangle(NULL,tet->get_noeud2()->get_noeud(),tet->get_noeud3()->get_noeud(),tet->get_noeud4()->get_noeud(),MAGIC::ORIGINE::MAILLEUR_AUTO);
                if (mgtriangle4==NULL) mgtriangle4=mai->ajouter_mg_triangle(NULL,tet->get_noeud1()->get_noeud(),tet->get_noeud4()->get_noeud(),tet->get_noeud3()->get_noeud(),MAGIC::ORIGINE::MAILLEUR_AUTO);
                M3D_TETRA* mgtet=mgtet=new M3D_TETRA(NULL,tet->get_noeud1()->get_noeud(),tet->get_noeud2()->get_noeud(),tet->get_noeud3()->get_noeud(),tet->get_noeud4()->get_noeud(),mgtriangle1,mgtriangle2,mgtriangle3,mgtriangle4,MAGIC::ORIGINE::MAILLEUR_AUTO);
                mai->ajouter_mg_tetra(mgtet);
                int tabnoeud[4]={0,0,0,0};
                if (tet->get_triangle1()->est_frontiere()) {tabnoeud[0]=1;tabnoeud[1]=1;tabnoeud[2]=1;}
                if (tet->get_triangle2()->est_frontiere()) {tabnoeud[0]=1;tabnoeud[1]=1;tabnoeud[3]=1;}
                if (tet->get_triangle3()->est_frontiere()) {tabnoeud[0]=1;tabnoeud[2]=1;tabnoeud[3]=1;}
                if (tet->get_triangle4()->est_frontiere()) {tabnoeud[1]=1;tabnoeud[2]=1;tabnoeud[3]=1;}
                if (tabnoeud[0]==1) ((M3D_NOEUD*)mgtet->get_noeud1())->etat_inactif();
                if (tabnoeud[1]==1) ((M3D_NOEUD*)mgtet->get_noeud2())->etat_inactif();
                if (tabnoeud[2]==1) ((M3D_NOEUD*)mgtet->get_noeud3())->etat_inactif();
                if (tabnoeud[3]==1) ((M3D_NOEUD*)mgtet->get_noeud4())->etat_inactif();
                
                vol=vol+tet->calcul_volume(NULL,0);
                nbmaitheo=nbmaitheo+tet->calcul_volume(carte,0);
            }
        }
        LISTE_MG_SEGMENT::iterator it;
        for (MG_SEGMENT *seg=mai->get_premier_segment(it);seg;seg=mai->get_suivant_segment(it))
            {
            M3D_NOEUD* no1=(M3D_NOEUD*)seg->get_noeud1();
            M3D_NOEUD* no2=(M3D_NOEUD*)seg->get_noeud2();
            seg->change_dimension_topo_null(3);
            if (no1->get_etat()==MAGIC::MAILLEURFRONTALETAT::INACTIF)
              if (no2->get_etat()==MAGIC::MAILLEURFRONTALETAT::INACTIF)
                {
                OT_VECTEUR_3D vec(no1->get_coord(),no2->get_coord());
                vec.norme();
                OT_VECTEUR_3D vecx(1.,0.,0.);
                OT_VECTEUR_3D vecy(0.,1.,0.);
                OT_VECTEUR_3D vecz(0.,0.,1.);
                if (fabs(vecx*vec)<1e-10) seg->change_dimension_topo_null(2);
                else if (fabs(vecy*vec)<1e-10) seg->change_dimension_topo_null(2);
                else if (fabs(vecz*vec)<1e-10) seg->change_dimension_topo_null(2);
                }
              
            }
        char message[255];
        sprintf(message,"     Volume maille : %lf",vol);
        if (affichageactif) affiche(message);
        nbmaitheo=12.*nbmaitheo/sqrt(2);
        double erreur=nbmaitheo-mai->get_nb_mg_tetra();
        erreur=erreur/mai->get_nb_mg_tetra();
        sprintf(message,"     Nombre de maille theorique  : %d, Nombre de maille pratique %d, erreur %.2lf%%",(int)nbmaitheo,mai->get_nb_mg_tetra(),erreur);
        if (affichageactif) affiche(message);
    }
 
}
 
 
int MAILLEUR_DELAUNAY::est_de_delaunay(void)
{
    for (int i=0;i<tabtet.size();i++)
    {
        DLY_TETRA* tet=tabtet[i];
        for (int j=0;j<tabnoeud.size();j++)
        {
            DLY_NOEUD* no=tabnoeud[j];
            if (no!=tet->get_noeud1())
                if (no!=tet->get_noeud2())
                    if (no!=tet->get_noeud3())
                        if (no!=tet->get_noeud4())
                        {
                            int num=tet->point_dans_la_sphere(no->get_x(),no->get_y(),no->get_z()>1);
                            if (num>1)
                                return 0;
 
                        }
        }
    }
    return 1;
}