/*************************************/
/* Auteur : Rémi Synave */
/* Date de création : 15/05/08 */
/* Date de modification : 15/03/15 */
/* Version : 0.4 */
/*************************************/
/*************************************/
/* Auteur : Romain Leguay */
/* Nguyen Haiduong */
/* Solange Houeto */
/* Marianne Fichoux */
/* Date de modification : 08/06/09 */
/* Version : 0.2 */
/*************************************/
/***************************************************************************/
/* This file is part of a2ri. */
/* */
/* a2ri is free software: you can redistribute it and/or modify it */
/* under the terms of the GNU Lesser General Public License as published */
/* by the Free Software Foundation, either version 3 of the License, or */
/* (at your option) any later version. */
/* */
/* a2ri is distributed in the hope that it will be useful, */
/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
/* GNU Lesser General Public License for more details. */
/* */
/* You should have received a copy of the GNU Lesser General Public */
/* License along with a2ri. */
/* If not, see . */
/***************************************************************************/
#include "triangulation.h"
/********** INTERMEDIATE TYPES AND FUNCTIONS **********/
/* Les fonctions intermédiaires sont préfixées de IF */
/* et les types intermédiaires de IT */
typedef struct
{
point3d *liste_centre1,
*liste_centre2;
double *liste_rayon1,
*liste_rayon2;
double sensibility;
int nbtest1deb,
nbtest1fin,
nbtest2;
int **asupprimer,
*nbelt;
} ITnettoyage_thread_argument;
typedef struct
{
int *list;
int nbelt;
} IT_bpa_liste;
void *
IFthread_process_nettoyage (
void *argu)
{
ITnettoyage_thread_argument *arg =
(ITnettoyage_thread_argument *) argu;
*(arg->asupprimer) = NULL;
*(arg->nbelt) = 0;
for (int i = arg->nbtest1deb; i <= arg->nbtest1fin; i++)
{
if (!intersection_bounding_ball_with_bounding_ball_list
(&(arg->liste_centre1[i]), arg->liste_rayon1[i], arg->liste_centre2,
arg->liste_rayon2, arg->nbtest2, arg->sensibility))
list_int_add (arg->asupprimer, arg->nbelt, i, WITH_REDUNDANCE);
}
pthread_exit (0);
}
//on cherche les aretes qui ne partagent qu'une seule face et on ajoute leur sommet dans une liste
//résultat : la liste des sommets appartenant au bord du maillage
void
IF_bpa_look_for_border (
int key,
vf_edge * value,
void *user_data)
{
IT_bpa_liste *list = user_data;
if (value->nbsharedfaces == 1)
{
list_int_add (&(list->list), &(list->nbelt), value->ve1,
WITH_REDUNDANCE);
list_int_add (&(list->list), &(list->nbelt), value->ve2,
WITH_REDUNDANCE);
}
}
//on cherche à retrouver un cycle dans la liste des sommets appartenant au bord du maillage
void
IF_bpa_cycle (
IT_bpa_liste * list,
IT_bpa_liste * cycle)
{
int trouve = 1;
int next = (*list).list[1];
//on ajoute le premier et le second sommet
list_int_add (&(cycle->list), &(cycle->nbelt), (*list).list[0],
WITH_REDUNDANCE);
list_int_add (&(cycle->list), &(cycle->nbelt), (*list).list[1],
WITH_REDUNDANCE);
while (next != (*list).list[0] && trouve)
{
trouve = 0;
//dans le reste de la liste, on cherche le couple dont le premier element correspond au dernier element ajouté
for (int i = 0; i < (*list).nbelt / 2; i++)
{
if ((*list).list[i * 2] == cycle->list[(cycle->nbelt) - 1])
{
//on a correspondance entre le premier element du couple et le dernier element ajouté
if ((*list).list[i * 2 + 1] != (*list).list[0])
{
//l'element trouvé ne correpond pas au premier element
//on ajoute donc le sommet suivant
list_int_add (&(cycle->list), &(cycle->nbelt),
(*list).list[i * 2 + 1], WITH_REDUNDANCE);
next = (*list).list[i * 2 + 1];
list_int_remove (&((*list).list), &((*list).nbelt),
i * 2 + 1);
list_int_remove (&((*list).list), &((*list).nbelt), i * 2);
}
else
{
//on a correpondance entre l'element à ajouter et le premier élément donc nous avons trouvé un cycle
next = (*list).list[0];
list_int_add (&(cycle->list), &(cycle->nbelt),
-1, WITH_REDUNDANCE);
//on termine l'algorithme en mettant next à la valeur du premier element
list_int_remove (&((*list).list), &((*list).nbelt),
i * 2 + 1);
list_int_remove (&((*list).list), &((*list).nbelt), i * 2);
}
trouve = 1;
}
}
}
list_int_remove (&((*list).list), &((*list).nbelt), 1);
list_int_remove (&((*list).list), &((*list).nbelt), 0);
}
//recherche de cycle dans les arêtes du bord du modèle
int IF_bpa_vf_hole (vf_model * m, IT_bpa_liste *lescycles)
{
int nbtrou = 0;
IT_bpa_liste lescouples;
lescouples.list = NULL;
lescouples.nbelt = 0;
lescycles->list = NULL;
lescycles->nbelt = 0;
hashtable *table = a2ri_vf_construction_edge_table (m, NULL, 0);
hashtable_foreach (table, IF_bpa_look_for_border, &lescouples);
//si on ne trouve aucun sommet sur le bord du maillage
if (lescouples.nbelt == 0)
{
hashtable_free (table);
free (table);
free (lescouples.list);
//il n'y a pas de trou
return nbtrou;
}
//sinon tant qu'on a des elements dans la liste, on cherche un nouveau cycle
while (lescouples.nbelt != 0)
{
IF_bpa_cycle (&lescouples, lescycles);
//le nombre de cycle correspond au nombre de trou
nbtrou++;
}
hashtable_free (table);
free (table);
free (lescouples.list);
return nbtrou;
}
/********** MAIN FUNCTIONS **********/
/**
Nettoyage par suppression des faces dans la zone de recouvrement
@param base,m 2 vf_model
@return aucun
**/
void
nettoyage_delete_face (
vf_model * base,
vf_model * m,
double sensibility)
{
hashtable *table = NULL;
int recouvrement = 1;
int tour = -1;
int *candidat_m = NULL,
size_candidat_m = 0,
*candidat_base = NULL,
size_candidat_base = 0;
double *listrayonmodelm = NULL,
*listrayonbase = NULL;
point3d *listcentrebase = NULL,
*listcentremodelm = NULL;
a2ri_time deptotal,
fintotal,
depinter,
fininter,
depMAJ,
finMAJ,
depBB,
finBB;
double totalinter = 0,
totalMAJ = 0;
deptotal = a2ri_get_time ();
pthread_t th[A2RI_NB_THREAD];
ITnettoyage_thread_argument argument[A2RI_NB_THREAD];
void *ret[A2RI_NB_THREAD];
int *liste_a_supprimer[A2RI_NB_THREAD],
size_liste_a_supprimer[A2RI_NB_THREAD];
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
//on va demander les bounding ball de toutes les faces des deux modèles
candidat_m = (int *) malloc (m->nbface * sizeof (int));
a2ri_erreur_critique_si (candidat_m == NULL,
"erreur allocation memoire pour candidat_m\nnettoyage_delete_face");
candidat_base = (int *) malloc (base->nbface * sizeof (int));
a2ri_erreur_critique_si (candidat_base == NULL,
"erreur allocation memoire pour candidat_base\nnettoyage_delete_face");
for (int i = 0; i < m->nbface; i++)
candidat_m[i] = i;
size_candidat_m = m->nbface;
for (int i = 0; i < base->nbface; i++)
candidat_base[i] = i;
size_candidat_base = base->nbface;
//récupère toutes les bounding sphere de toutes les faces des modeles base et m
depBB = a2ri_get_time ();
a2ri_vf_bounding_ball_minimale (base,
candidat_base,
size_candidat_base,
&listcentrebase,
&listrayonbase);
a2ri_vf_bounding_ball_minimale (m,
candidat_m,
size_candidat_m,
&listcentremodelm,
&listrayonmodelm);
finBB = a2ri_get_time ();
while (recouvrement)
{
tour++;
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
free (liste_a_supprimer[i]);
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
/*mettre le numero des faces dans la zone de recouvrement de
2 vf_model dans 2 listes */
if (tour == 0)
{
depinter = a2ri_get_time ();
for (int i = 0; i < A2RI_NB_THREAD - 1; i++)
{
argument[i].liste_centre2 = listcentrebase;
argument[i].liste_rayon2 = listrayonbase;
argument[i].nbtest2 = size_candidat_base;
argument[i].nbtest1deb = (size_candidat_m / A2RI_NB_THREAD) * i;
argument[i].nbtest1fin =
(size_candidat_m / A2RI_NB_THREAD) * (i + 1) - 1;
argument[i].liste_centre1 = listcentremodelm;
argument[i].liste_rayon1 = listrayonmodelm;
argument[i].sensibility = sensibility;
argument[i].asupprimer = &liste_a_supprimer[i];
argument[i].nbelt = &size_liste_a_supprimer[i];
}
argument[A2RI_NB_THREAD - 1].liste_centre2 = listcentrebase;
argument[A2RI_NB_THREAD - 1].liste_rayon2 = listrayonbase;
argument[A2RI_NB_THREAD - 1].nbtest2 = size_candidat_base;
argument[A2RI_NB_THREAD - 1].nbtest1deb =
(size_candidat_m / A2RI_NB_THREAD) * (A2RI_NB_THREAD - 1);
argument[A2RI_NB_THREAD - 1].nbtest1fin = size_candidat_m - 1;
argument[A2RI_NB_THREAD - 1].liste_centre1 = listcentremodelm;
argument[A2RI_NB_THREAD - 1].liste_rayon1 = listrayonmodelm;
argument[A2RI_NB_THREAD - 1].sensibility = sensibility;
argument[A2RI_NB_THREAD - 1].asupprimer =
&liste_a_supprimer[A2RI_NB_THREAD - 1];
argument[A2RI_NB_THREAD - 1].nbelt =
&size_liste_a_supprimer[A2RI_NB_THREAD - 1];
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
if (pthread_create
(th + i, NULL, IFthread_process_nettoyage, argument + i) < 0)
exit (1);
}
for (int i = 0; i < A2RI_NB_THREAD; i++)
(void) pthread_join (th[i], &ret[i]);
for (int i = A2RI_NB_THREAD - 1; i >= 0; i--)
{
for (int j = size_liste_a_supprimer[i] - 1; j >= 0; j--)
{
list_int_remove (&candidat_m, &size_candidat_m,
liste_a_supprimer[i][j]);
size_candidat_m++;
list_double_remove (&listrayonmodelm, &size_candidat_m,
liste_a_supprimer[i][j]);
size_candidat_m++;
list_point3d_remove (&listcentremodelm, &size_candidat_m,
liste_a_supprimer[i][j]);
}
free (liste_a_supprimer[i]);
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
for (int i = 0; i < A2RI_NB_THREAD - 1; i++)
{
argument[i].liste_centre2 = listcentremodelm;
argument[i].liste_rayon2 = listrayonmodelm;
argument[i].nbtest2 = size_candidat_m;
argument[i].nbtest1deb =
(size_candidat_base / A2RI_NB_THREAD) * i;
argument[i].nbtest1fin =
(size_candidat_base / A2RI_NB_THREAD) * (i + 1) - 1;
argument[i].liste_centre1 = listcentrebase;
argument[i].liste_rayon1 = listrayonbase;
argument[i].sensibility = sensibility;
argument[i].asupprimer = &liste_a_supprimer[i];
argument[i].nbelt = &size_liste_a_supprimer[i];
}
argument[A2RI_NB_THREAD - 1].liste_centre2 = listcentremodelm;
argument[A2RI_NB_THREAD - 1].liste_rayon2 = listrayonmodelm;
argument[A2RI_NB_THREAD - 1].nbtest2 = size_candidat_m;
argument[A2RI_NB_THREAD - 1].nbtest1deb =
(size_candidat_base / A2RI_NB_THREAD) * (A2RI_NB_THREAD - 1);
argument[A2RI_NB_THREAD - 1].nbtest1fin = size_candidat_base - 1;
argument[A2RI_NB_THREAD - 1].liste_centre1 = listcentrebase;
argument[A2RI_NB_THREAD - 1].liste_rayon1 = listrayonbase;
argument[A2RI_NB_THREAD - 1].sensibility = sensibility;
argument[A2RI_NB_THREAD - 1].asupprimer =
&liste_a_supprimer[A2RI_NB_THREAD - 1];
argument[A2RI_NB_THREAD - 1].nbelt =
&size_liste_a_supprimer[A2RI_NB_THREAD - 1];
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
if (pthread_create
(th + i, NULL, IFthread_process_nettoyage, argument + i) < 0)
exit (1);
}
for (int i = 0; i < A2RI_NB_THREAD; i++)
(void) pthread_join (th[i], &ret[i]);
for (int i = A2RI_NB_THREAD - 1; i >= 0; i--)
{
for (int j = size_liste_a_supprimer[i] - 1; j >= 0; j--)
{
list_int_remove (&candidat_base, &size_candidat_base,
liste_a_supprimer[i][j]);
size_candidat_base++;
list_double_remove (&listrayonbase, &size_candidat_base,
liste_a_supprimer[i][j]);
size_candidat_base++;
list_point3d_remove (&listcentrebase, &size_candidat_base,
liste_a_supprimer[i][j]);
}
free (liste_a_supprimer[i]);
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
fininter = a2ri_get_time ();
totalinter += a2ri_time_interval_to_double (depinter, fininter);
}
else
{
if (tour % 2 == 0)
{
depinter = a2ri_get_time ();
for (int i = 0; i < A2RI_NB_THREAD - 1; i++)
{
argument[i].liste_centre2 = listcentrebase;
argument[i].liste_rayon2 = listrayonbase;
argument[i].nbtest2 = size_candidat_base;
argument[i].nbtest1deb =
(size_candidat_m / A2RI_NB_THREAD) * i;
argument[i].nbtest1fin =
(size_candidat_m / A2RI_NB_THREAD) * (i + 1) - 1;
argument[i].liste_centre1 = listcentremodelm;
argument[i].liste_rayon1 = listrayonmodelm;
argument[i].sensibility = sensibility;
argument[i].asupprimer = &liste_a_supprimer[i];
argument[i].nbelt = &size_liste_a_supprimer[i];
}
argument[A2RI_NB_THREAD - 1].liste_centre2 = listcentrebase;
argument[A2RI_NB_THREAD - 1].liste_rayon2 = listrayonbase;
argument[A2RI_NB_THREAD - 1].nbtest2 = size_candidat_base;
argument[A2RI_NB_THREAD - 1].nbtest1deb =
(size_candidat_m / A2RI_NB_THREAD) * (A2RI_NB_THREAD - 1);
argument[A2RI_NB_THREAD - 1].nbtest1fin = size_candidat_m - 1;
argument[A2RI_NB_THREAD - 1].liste_centre1 = listcentremodelm;
argument[A2RI_NB_THREAD - 1].liste_rayon1 = listrayonmodelm;
argument[A2RI_NB_THREAD - 1].sensibility = sensibility;
argument[A2RI_NB_THREAD - 1].asupprimer =
&liste_a_supprimer[A2RI_NB_THREAD - 1];
argument[A2RI_NB_THREAD - 1].nbelt =
&size_liste_a_supprimer[A2RI_NB_THREAD - 1];
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
if (pthread_create
(th + i, NULL, IFthread_process_nettoyage,
argument + i) < 0)
exit (1);
}
for (int i = 0; i < A2RI_NB_THREAD; i++)
(void) pthread_join (th[i], &ret[i]);
for (int i = A2RI_NB_THREAD - 1; i >= 0; i--)
{
for (int j = size_liste_a_supprimer[i] - 1; j >= 0; j--)
{
list_int_remove (&candidat_m, &size_candidat_m,
liste_a_supprimer[i][j]);
size_candidat_m++;
list_double_remove (&listrayonmodelm, &size_candidat_m,
liste_a_supprimer[i][j]);
size_candidat_m++;
list_point3d_remove (&listcentremodelm,
&size_candidat_m,
liste_a_supprimer[i][j]);
}
free (liste_a_supprimer[i]);
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
fininter = a2ri_get_time ();
totalinter += a2ri_time_interval_to_double (depinter, fininter);
}
if (tour % 2 == 1)
{
depinter = a2ri_get_time ();
for (int i = 0; i < A2RI_NB_THREAD - 1; i++)
{
argument[i].liste_centre2 = listcentremodelm;
argument[i].liste_rayon2 = listrayonmodelm;
argument[i].nbtest2 = size_candidat_m;
argument[i].nbtest1deb =
(size_candidat_base / A2RI_NB_THREAD) * i;
argument[i].nbtest1fin =
(size_candidat_base / A2RI_NB_THREAD) * (i + 1) - 1;
argument[i].liste_centre1 = listcentrebase;
argument[i].liste_rayon1 = listrayonbase;
argument[i].sensibility = sensibility;
argument[i].asupprimer = &liste_a_supprimer[i];
argument[i].nbelt = &size_liste_a_supprimer[i];
}
argument[A2RI_NB_THREAD - 1].liste_centre2 = listcentremodelm;
argument[A2RI_NB_THREAD - 1].liste_rayon2 = listrayonmodelm;
argument[A2RI_NB_THREAD - 1].nbtest2 = size_candidat_m;
argument[A2RI_NB_THREAD - 1].nbtest1deb =
(size_candidat_base / A2RI_NB_THREAD) * (A2RI_NB_THREAD - 1);
argument[A2RI_NB_THREAD - 1].nbtest1fin =
size_candidat_base - 1;
argument[A2RI_NB_THREAD - 1].liste_centre1 = listcentrebase;
argument[A2RI_NB_THREAD - 1].liste_rayon1 = listrayonbase;
argument[A2RI_NB_THREAD - 1].sensibility = sensibility;
argument[A2RI_NB_THREAD - 1].asupprimer =
&liste_a_supprimer[A2RI_NB_THREAD - 1];
argument[A2RI_NB_THREAD - 1].nbelt =
&size_liste_a_supprimer[A2RI_NB_THREAD - 1];
for (int i = 0; i < A2RI_NB_THREAD; i++)
{
if (pthread_create
(th + i, NULL, IFthread_process_nettoyage,
argument + i) < 0)
exit (1);
}
for (int i = 0; i < A2RI_NB_THREAD; i++)
(void) pthread_join (th[i], &ret[i]);
for (int i = A2RI_NB_THREAD - 1; i >= 0; i--)
{
for (int j = size_liste_a_supprimer[i] - 1; j >= 0; j--)
{
list_int_remove (&candidat_base, &size_candidat_base,
liste_a_supprimer[i][j]);
size_candidat_base++;
list_double_remove (&listrayonbase, &size_candidat_base,
liste_a_supprimer[i][j]);
size_candidat_base++;
list_point3d_remove (&listcentrebase,
&size_candidat_base,
liste_a_supprimer[i][j]);
}
free (liste_a_supprimer[i]);
liste_a_supprimer[i] = NULL;
size_liste_a_supprimer[i] = 0;
}
fininter = a2ri_get_time ();
totalinter += a2ri_time_interval_to_double (depinter, fininter);
}
}
if ((size_candidat_m == 0) || (size_candidat_base == 0))
recouvrement = 0;
else
{
if (tour % 2 == 0)
{
//supprimer les faces se trouvant sur les bords du maillage
//pour m
depMAJ = a2ri_get_time ();
table = a2ri_vf_construction_edge_table (m, NULL, 0);
for (int i = 0; i < size_candidat_m; i++)
{
vf_edge *edgetemp1 =
hashtable_look_for (table, m->fa[candidat_m[i]].ve1,
m->fa[candidat_m[i]].ve2);
vf_edge *edgetemp2 =
hashtable_look_for (table, m->fa[candidat_m[i]].ve1,
m->fa[candidat_m[i]].ve3);
vf_edge *edgetemp3 =
hashtable_look_for (table, m->fa[candidat_m[i]].ve2,
m->fa[candidat_m[i]].ve3);
if (edgetemp1->nbsharedfaces == 1
|| edgetemp2->nbsharedfaces == 1
|| edgetemp3->nbsharedfaces == 1)
list_int_add (&liste_a_supprimer[0],
&size_liste_a_supprimer[0], candidat_m[i],
WITH_REDUNDANCE);
}
a2ri_vf_remove_list_of_face (m, liste_a_supprimer[0],
size_liste_a_supprimer[0]);
for (int i = 0; i < size_liste_a_supprimer[0]; i++)
{
int index;
list_int_remove (&candidat_m, &size_candidat_m, index =
list_int_contains (candidat_m,
size_candidat_m,
liste_a_supprimer[0]
[i]));
for (int j = index; j < size_candidat_m; j++)
candidat_m[j] = candidat_m[j] - 1;
size_candidat_m++;
list_double_remove (&listrayonmodelm, &size_candidat_m,
index);
size_candidat_m++;
list_point3d_remove (&listcentremodelm, &size_candidat_m,
index);
}
if (size_liste_a_supprimer[0] == 0)
recouvrement = 0;
else
recouvrement = 1;
free (liste_a_supprimer[0]);
liste_a_supprimer[0] = NULL;
size_liste_a_supprimer[0] = 0;
hashtable_free (table);
table = NULL;
finMAJ = a2ri_get_time ();
totalMAJ += a2ri_time_interval_to_double (depMAJ, finMAJ);
}
if (tour % 2 == 1)
{
//pour base
depMAJ = a2ri_get_time ();
table = a2ri_vf_construction_edge_table (base, NULL, 0);
for (int i = 0; i < size_candidat_base; i++)
{
vf_edge *edgetemp1 =
hashtable_look_for (table, base->fa[candidat_base[i]].ve1,
base->fa[candidat_base[i]].ve2);
vf_edge *edgetemp2 =
hashtable_look_for (table, base->fa[candidat_base[i]].ve1,
base->fa[candidat_base[i]].ve3);
vf_edge *edgetemp3 =
hashtable_look_for (table, base->fa[candidat_base[i]].ve2,
base->fa[candidat_base[i]].ve3);
if (edgetemp1->nbsharedfaces == 1
|| edgetemp2->nbsharedfaces == 1
|| edgetemp3->nbsharedfaces == 1)
list_int_add (&liste_a_supprimer[0],
&size_liste_a_supprimer[0],
candidat_base[i], WITH_REDUNDANCE);
}
a2ri_vf_remove_list_of_face (base, liste_a_supprimer[0],
size_liste_a_supprimer[0]);
for (int i = 0; i < size_liste_a_supprimer[0]; i++)
{
int index;
list_int_remove (&candidat_base, &size_candidat_base,
index =
list_int_contains (candidat_base,
size_candidat_base,
liste_a_supprimer[0]
[i]));
for (int j = index; j < size_candidat_base; j++)
candidat_base[j] = candidat_base[j] - 1;
size_candidat_base++;
list_double_remove (&listrayonbase, &size_candidat_base,
index);
size_candidat_base++;
list_point3d_remove (&listcentrebase, &size_candidat_base,
index);
}
if (size_liste_a_supprimer[0] == 0 && !recouvrement)
recouvrement = 0;
else
recouvrement = 1;
free (liste_a_supprimer[0]);
liste_a_supprimer[0] = NULL;
size_liste_a_supprimer[0] = 0;
hashtable_free (table);
table = NULL;
finMAJ = a2ri_get_time ();
totalMAJ += a2ri_time_interval_to_double (depMAJ, finMAJ);
}
}
}
tour++;
fintotal = a2ri_get_time ();
a2ri_display_interval_time ("temps TOTAL nettoyage : ", deptotal, fintotal);
printf ("\ttemps calcul BB : %lf -> %lf %c\n",
a2ri_time_interval_to_double (depBB, finBB),
a2ri_time_interval_to_double (depBB,
finBB) /
a2ri_time_interval_to_double (deptotal, fintotal) * 100, 37);
printf ("\ttemps calcul intersection : %lf -> %lf %c\n", totalinter,
totalinter / a2ri_time_interval_to_double (deptotal,
fintotal) * 100, 37);
printf ("\ttemps MAJ : %lf -> %lf %c\n", totalMAJ,
totalMAJ / a2ri_time_interval_to_double (deptotal, fintotal) * 100,
37);
}
/**
Création d'un vf_model avec une triangulation de delaunay
@param list liste de point
@param nbpoint nombre de points
@return aucun
*/
vf_model *
a2ri_vf_delaunay_triangulation (
const point3d * const list,
int nbpoint)
{
/*TODO*/
vf_model *m = (vf_model *) malloc (sizeof (vf_model));
a2ri_erreur_critique_si (m == NULL,
"erreur allocation memoire pour m\na2ri_vf_delaunay_triangulation");
a2ri_vf_init (m);
return m;
}
/**
Création d'un vef_model avec une triangulation de delaunay
@param list liste de point
@param nbpoint nombre de points
@return aucun
*/
vef_model *
a2ri_vef_delaunay_triangulation (
const point3d * const list,
int nbpoint)
{
/*TODO*/
vef_model *m = (vef_model *) malloc (sizeof (vef_model));
a2ri_erreur_critique_si (m == NULL,
"erreur allocation memoire pour m\na2ri_vef_delaunay_triangulation");
a2ri_vef_init (m);
return m;
}
/*********************/
/*algorithme BPA 2010*/
/*********************/
void a2ri_bpa_insert_edge(bpa_edge *front, bpa_edge e)
{
bpa_edge *newedge=(bpa_edge*)malloc(sizeof(bpa_edge));
a2ri_erreur_critique_si (newedge == NULL,
"erreur allocation memoire pour newedge\na2ri_bpa_insert_edge");
newedge->sigma_i=e.sigma_i;
newedge->sigma_j=e.sigma_j;
newedge->sigma_o=e.sigma_o;
newedge->cijo=e.cijo;
newedge->state=e.state;
newedge->prev=front->prev;
newedge->next=front;
newedge->front=front->prev->front;
front->prev->next=newedge;
front->prev=newedge;
front->front->front=newedge;
}
void a2ri_bpa_delete_edge(bpa_edge **front)
{
a2ri_erreur_critique_si ((*front)->prev == NULL,
"Erreur algorithmique. Arete impossible a supprimer car non boucle 1.\na2ri_bpa_delete_edge");
a2ri_erreur_critique_si ((*front)->next == NULL,
"Erreur algorithmique. Arete impossible a supprimer car non boucle 2.\na2ri_bpa_delete_edge");
(*front)->front->front=(*front)->prev;
(*front)->prev->next=(*front)->next;
(*front)->next->prev=(*front)->prev;
free((*front));
}
void a2ri_bpa_free_front(bpa_edge **front)
{
bpa_edge *courant=*front,*suivant=NULL;
if((*front)==NULL)
return;
if(courant->prev!=NULL)
courant->prev->next=NULL;
suivant=courant->next;
while(courant!=NULL)
{
a2ri_erreur_critique_si (courant->state == ACTIVE,
"Erreur algorithmique. Arete active impossible a liberer.\na2ri_bpa_free_front");
free(courant);
courant=suivant;
if(suivant!=NULL)
suivant=suivant->next;
}
}
void a2ri_bpa_free_fronts(bpa_fronts **fronts)
{
bpa_fronts *courant=*fronts,*suivant=NULL;
if((*fronts)==NULL)
return;
suivant=courant->next;
while(courant!=NULL)
{
a2ri_bpa_free_front(&(courant->front));
courant->front=NULL;
free(courant);
courant=suivant;
if(suivant!=NULL)
suivant=suivant->next;
}
}
void a2ri_bpa_new_front(bpa_fronts **fronts, int sigma_i, int sigma_j, int sigma_k, point3d centre)
{
bpa_edge *parc;
(*fronts)=(bpa_fronts*)malloc(sizeof(bpa_fronts));
a2ri_erreur_critique_si (*fronts == NULL,
"erreur allocation memoire pour fronts\na2ri_bpa_new_front");
(*fronts)->next=NULL;
(*fronts)->front=(bpa_edge*)malloc(sizeof(bpa_edge));
a2ri_erreur_critique_si ((*fronts)->front == NULL,
"erreur allocation memoire pour *fronts->front - 1ere arete\na2ri_bpa_insert_edge");
parc=(*fronts)->front;
/*premiere arete du front*/
parc->sigma_i=sigma_i;parc->sigma_j=sigma_j;parc->sigma_o=sigma_k;parc->cijo=centre;parc->state=ACTIVE;parc->front=(*fronts);
parc->next=(bpa_edge*)malloc(sizeof(bpa_edge));
a2ri_erreur_critique_si (parc->next == NULL,
"erreur allocation memoire pour parc->next - 2eme arete\na2ri_bpa_new_front");
parc->next->prev=parc;
parc=parc->next;
/*seconde arete du front*/
parc->sigma_i=sigma_j;parc->sigma_j=sigma_k;parc->sigma_o=sigma_i;parc->cijo=centre;parc->state=ACTIVE;parc->front=(*fronts);
parc->next=(bpa_edge*)malloc(sizeof(bpa_edge));
a2ri_erreur_critique_si (parc->next == NULL,
"erreur allocation memoire pour parc->next - 3eme arete\na2ri_bpa_new_front");
parc->next->prev=parc;
parc=parc->next;
/*troisieme arete du front*/
parc->sigma_i=sigma_k;parc->sigma_j=sigma_i;parc->sigma_o=sigma_j;parc->cijo=centre;parc->state=ACTIVE;parc->front=(*fronts);
parc->next=(*fronts)->front;
parc->next->prev=parc;
}
bpa_edge* a2ri_bpa_get_active_edge_in_front(bpa_edge *front)
{
//printf("recherche d'arete active dans un front\n");
int tour=0;
while(tour<2)
{
if(front==front->front->front)
tour++;
if(front->state==ACTIVE)
return front;
else
front=front->next;
}
return NULL;
}
bpa_edge* a2ri_bpa_get_active_edge_in_fronts(bpa_fronts *fronts)
{
bpa_edge *temp;
//printf("recherche d'arete active dans les fronts\n");
while(fronts!=NULL)
if((temp=a2ri_bpa_get_active_edge_in_front(fronts->front))!=NULL)
return temp;
else
fronts=fronts->next;
return NULL;
}
char a2ri_bpa_front_contains_point_in_front(bpa_edge *front, int sigma_k)
{
int tour=0;
while(tour<2)
{
if(front==front->front->front)
tour++;
if(front->sigma_i==sigma_k || front->sigma_j==sigma_k)
return 1;
else
front=front->next;
}
return 0;
}
char a2ri_bpa_front_contains_point_in_fronts(bpa_fronts *fronts, int sigma_k)
{
while(fronts!=NULL)
if(a2ri_bpa_front_contains_point_in_front(fronts->front,sigma_k))
return 1;
else
fronts=fronts->next;
return 0;
}
bpa_edge* a2ri_bpa_front_contains_edge_in_front(bpa_edge *front, bpa_edge e)
{
int tour=0;
while(tour<2)
{
if(front==front->front->front)
tour++;
if(front->sigma_i==e.sigma_i && front->sigma_j==e.sigma_j)
return front;
else
front=front->next;
}
return NULL;
}
bpa_edge* a2ri_bpa_front_contains_edge_in_fronts(bpa_fronts *fronts, bpa_edge e)
{
bpa_edge *temp;
while(fronts!=NULL)
{
temp=a2ri_bpa_front_contains_edge_in_front(fronts->front,e);
if(temp!=NULL)
return temp;
else
fronts=fronts->next;
}
return NULL;
}
void a2ri_bpa_display_front(bpa_edge *front)
{
int tour=0;
while(tour==0 || front!=front->front->front)
{
tour=1;
//printf("\tarete : (%d %d) - point oppose : %d - centre : (%lf %lf %lf) - etat : ",front->sigma_i,front->sigma_j,front->sigma_o,front->cijo.x,front->cijo.y,front->cijo.z);
printf("\tarete : (%4d %4d) - point oppose : %4d - ",front->sigma_i,front->sigma_j,front->sigma_o);
if(front->state==ACTIVE)
printf("ACTIVE\n");
if(front->state==BOUNDARY)
printf("BOUNDARY\n");
//printf("\tfront : %p - front->front : %p - front->front->front : %p\n",front,front->front,front->front->front);
front=front->next;
}
}
void a2ri_bpa_display_fronts(bpa_fronts *fronts)
{
int index=0;
while(fronts!=NULL)
{
printf("front %d :\n",index++);
a2ri_bpa_display_front(fronts->front);
fronts=fronts->next;
}
}
int a2ri_bpa_front_distance(bpa_edge *front, int index)
{
if(!a2ri_bpa_front_contains_point_in_front(front, index))
return -1;
int tour=0,taille=-1,distance=0,trouve=0;
while(tour<2)
{
taille++;
if(front==front->front->front)
tour++;
if(front->sigma_i==index || front->sigma_j==index)
trouve=1;
if(!trouve)
distance++;
front=front->next;
}
if((distance*1.0)>=(taille/2.0))
distance=taille-distance-1;
return distance;
}
void a2ri_bpa_join(bpa_edge **e, int sigma_k, point3d centre)
{
bpa_edge temp;
temp.prev=NULL;
temp.next=NULL;
temp.sigma_i=(*e)->sigma_i;
temp.sigma_j=sigma_k;
temp.sigma_o=(*e)->sigma_j;
temp.cijo=centre;
temp.state=ACTIVE;
a2ri_bpa_insert_edge(*e,temp);
temp.sigma_i=sigma_k;
temp.sigma_j=(*e)->sigma_j;
temp.sigma_o=(*e)->sigma_i;
a2ri_bpa_insert_edge(*e,temp);
a2ri_bpa_delete_edge(e);
}
void a2ri_bpa_glue(bpa_fronts **fronts, bpa_edge *ed1, bpa_edge *ed2)
{
bpa_edge *temp;
bpa_fronts *parc=*fronts,*todelete;
//printf("GLUE - arete %d %d - arete %d %d\n",ed1->sigma_i,ed1->sigma_j,ed2->sigma_i,ed2->sigma_j);
//a2ri_bpa_display_fronts(*fronts);
if(ed1->next==ed2 || ed1->prev==ed2)
{
/*SONT ADJACENTS*/
if(ed1->next==ed2 && ed1->prev==ed2)
{
/*FORMENT UNE BOUCLE A EUX DEUX*/
/*SURPPRIMER LE FRONT*/
//printf("deux aretes adjacentes qui forment une boucle ");
if(ed1->front==*fronts)
{
//printf("cas 1\n");
/*L'ARETE APPARTIENT AU PREMIER FRONT*/
*fronts=(*fronts)->next;
parc->front->state=BOUNDARY;
parc->front->next->state=BOUNDARY;
a2ri_bpa_free_front(&(parc->front));
parc->front=NULL;
free(parc);
}
else
{
/*ON RECHERCHE LE FRONT POUR LE SUPPRIMER*/
//printf("cas 2\n");
while(parc->next!=ed1->front)
parc=parc->next;
todelete=parc->next;
parc->next=todelete->next;
todelete->front->state=BOUNDARY;
todelete->front->next->state=BOUNDARY;
a2ri_bpa_free_front(&(todelete->front));
todelete->front=NULL;
free(todelete);
}
}
else
{
//printf("deux aretes adjacentes\n");
/*NE FORMENT PAS UNE BOUCLE A EUX DEUX*/
a2ri_bpa_delete_edge(&ed1);
a2ri_bpa_delete_edge(&ed2);
}
}
else
{
/*NE SONT PAS ADJACENTS*/
if(ed1->front==ed2->front)
{
//printf("deux arete non adjacentes appartenant au meme front\n");
//a2ri_bpa_display_fronts(*fronts);
/*APPARTIENNENT AU MEME FRONT*/
/*SPLIT DU FRONT EN DEUX*/
ed1->front->front=ed1->prev;
ed2->next->prev=ed1->prev;
ed1->prev->next=ed2->next;
ed1->next->prev=ed2->prev;
ed2->prev->next=ed1->next;
while(parc->next!=NULL)
parc=parc->next;
parc->next=(bpa_fronts*)malloc(sizeof(bpa_fronts));
parc=parc->next;
parc->next=NULL;
parc->front=ed2->prev;
temp=parc->front->next;
parc->front->front=parc;
while(temp!=parc->front)
{
temp->front=parc;
temp=temp->next;
}
//printf("\n\n");
//a2ri_bpa_display_fronts(*fronts);
}
else
{
//a2ri_bpa_display_fronts(*fronts);
//printf("deux aretes non adjacentes qui n'appartiennent pas au meme front\n");
/*N'APPARTIENNENT PAS AU MEME FRONT*/
/*FUSION DES DEUX FRONTS*/
if(ed1->front!=*fronts)
todelete=ed1->front;
else
todelete=ed2->front;
ed1->front->front=ed1->prev;
ed2->front->front=ed2->prev;
while(parc->next!=todelete)
parc=parc->next;
parc->next=todelete->next;
ed1->prev->next=ed2->next;
ed2->next->prev=ed1->prev;
ed1->next->prev=ed2->prev;
ed2->prev->next=ed1->next;
if(todelete==ed1->front)
{
temp=ed2->front->front;
temp->front=ed2->front;
temp=temp->next;
while(temp!=ed2->front->front)
{
temp->front=ed2->front;
temp=temp->next;
}
}
else
{
temp=ed1->front->front;
temp->front=ed1->front;
temp=temp->next;
while(temp!=ed1->front->front)
{
temp->front=ed1->front;
temp=temp->next;
}
}
free(todelete);
}
free(ed1);
free(ed2);
}
return;
}
void a2ri_bpa_regularization(bpa_fronts **fronts, int sigma_i, int sigma_j, int sigma_k)
{
bpa_edge *ed1,*ed2,temp;
/*IK KI*/
temp.sigma_i=sigma_i;
temp.sigma_j=sigma_k;
//printf("arete recherche : %d %d\n",temp.sigma_i,temp.sigma_j);
//a2ri_bpa_display_fronts(*fronts);
ed1=a2ri_bpa_front_contains_edge_in_fronts(*fronts,temp);
a2ri_erreur_critique_si (ed1 == NULL,
"Erreur algorithmique. L'arete vient d''etre creee. IK KI ed1 ne peut etre NULL.\na2ri_bpa_regularization");
temp.sigma_i=sigma_k;
temp.sigma_j=sigma_i;
ed2=a2ri_bpa_front_contains_edge_in_fronts(*fronts,temp);
if(ed2!=NULL)
a2ri_bpa_glue(fronts,ed1,ed2);
/*KJ JK*/
temp.sigma_i=sigma_k;
temp.sigma_j=sigma_j;
ed1=a2ri_bpa_front_contains_edge_in_fronts(*fronts,temp);
a2ri_erreur_critique_si (ed1 == NULL,
"Erreur algorithmique. L'arete vient d''etre cree. KJ JK ed1 ne peut etre NULL.\na2ri_bpa_regularization");
temp.sigma_i=sigma_j;
temp.sigma_j=sigma_k;
ed2=a2ri_bpa_front_contains_edge_in_fronts(*fronts,temp);
if(ed2!=NULL)
a2ri_bpa_glue(fronts,ed1,ed2);
}
char a2ri_bpa_compute_ball(point3d p1, point3d p2, point3d p3, vector3d normaleface, double radius, point3d *centre)
{
double longueur;
*centre=circumcircle_center(&p1,&p2,&p3);
longueur=point3d_length(centre,&p1);
if(longueurx=centre->x+normaleface.dx;
centre->y=centre->y+normaleface.dy;
centre->z=centre->z+normaleface.dz;
return 1;
}
else
return 0;
}
char a2ri_bpa_verif_contraintes(pt_point3d *listpoint, int sizelistpoint, point3d p1, point3d p2, point3d p3, vector3d normalp1, vector3d normalp2, vector3d normalp3, double radius, point3d *centre)
{
vector3d AB,AC,normaleface;
double prodscal1,prodscal2,prodscal3,distance;
int index,trouve;
/*printf("----DEBUT A2RI BPA VERIF CONTAINTES\n");
printf("points :\n");
point3d_display(p1);point3d_display(p2);point3d_display(p3);
printf("normales aux trois points :\n");
vector3d_display(normalp1);
vector3d_display(normalp2);
vector3d_display(normalp3);*/
vector3d_init (&AB, p2.x - p1.x,p2.y - p1.y,p2.z - p1.z);
vector3d_init (&AC, p3.x - p1.x,p3.y - p1.y,p3.z - p1.z);
normaleface=vector3d_vectorialproduct (&AB, &AC);
vector3d_normalize(&normaleface);
/*printf("normale au triangle candidat :\n");
vector3d_display(normaleface);*/
prodscal1=vector3d_scalarproduct(&normaleface,&normalp1);
prodscal2=vector3d_scalarproduct(&normaleface,&normalp2);
prodscal3=vector3d_scalarproduct(&normaleface,&normalp3);
if(prodscal1>0 && prodscal2>0 && prodscal3>0)
{
/*printf("test des normales OK\n");*/
/*VERIFIER QUE LA BOULE PASSANT PAR LES TROIS POINTS NE CONTIENNENT PAS D'AUTRE POINT DE LA LISTE*/
/*CALCUL DU CENTRE DE LA BOULE*/
/*SI ON ARRIVE A TROUVER UNE BOULE TOUCHANT LES TROIS POINTS*/
if(a2ri_bpa_compute_ball(p1,p2,p3,normaleface,radius,centre))
{
/*printf("calcul de la boule OK\ncentre :\n");*/
/*point3d_display(*centre);*/
/*VERIFICATION DE NON PRESENCE D'AUTRE POINT DANS LA BOULE*/
index=0;
trouve=0;
/*printf("recherche de points se trouvant dans cette sphere\n");*/
while(!trouve && indexnbvertex;i++)
{
if(list_int_contains(listused,sizeused,i)==-1)
{
*sigma_i=i;
point3d_init(&p1,m->ve[i].x,m->ve[i].y,m->ve[i].z);
free(listcellule);
listcellule=NULL;
sizelistcellule=0;
sizelistpoint=0;
space_partition_get_neighbour(sp,&p1,1,&listcellule,&sizelistcellule);
for(int j=0;jnb_point;
free(listpoint);
listpoint=NULL;
listpoint=(pt_point3d*)malloc(sizelistpoint*sizeof(pt_point3d));
index=0;
/*CREATION DE LA LISTE DE POINT SE TROUVANT DANS LES CASES ADJACENTES AU POINT D'INDEX I*/
for(int j=0;jnb_point;k++)
listpoint[index++]=&(listcellule[j]->list_point[k]);
/*PRISE DES PAIRES DE POINTS DISCTINCTES*/
//printf("nombre de point : %d\n",sizelistpoint);
for(int j=0;jnbface,i,listpoint[j]->att_int,listpoint[k]->att_int);*/
index=list_int_contains(listused,sizeused,listpoint[j]->att_int);
index2=list_int_contains(listused,sizeused,listpoint[k]->att_int);
if(i!=listpoint[j]->att_int && i!=listpoint[k]->att_int && listpoint[j]->att_int!=listpoint[k]->att_int && index==-1 && index2==-1)
{
/*VERIFIER SI LES TROIS POINTS VERIFIENT LES CONTRAINTES BPA*/
/*VERIFIER L'ORIENTATION DE LA NORMALE*/
point3d_init(&p2,
m->ve[listpoint[j]->att_int].x,
m->ve[listpoint[j]->att_int].y,
m->ve[listpoint[j]->att_int].z);
point3d_init(&p3,
m->ve[listpoint[k]->att_int].x,
m->ve[listpoint[k]->att_int].y,
m->ve[listpoint[k]->att_int].z);
if(a2ri_bpa_verif_contraintes(listpoint,
sizelistpoint,
p1,p2,p3,
normal[i],
normal[listpoint[j]->att_int],
normal[listpoint[k]->att_int],
radius,centre))
{
//printf("triangle OK\n");
*sigma_i=i;
*sigma_j=listpoint[j]->att_int;
*sigma_k=listpoint[k]->att_int;
//printf("----FIN A2RI BPA FIND SEED TRIANGLE\n");
return 1;
}
/*else
printf("le triangle ne respecte pas les contraintes bpa\n");*/
}
/*else
printf("triangle degenere ou un point est deja utilise\n");*/
}
}
}
free(listpoint);
free(listcellule);
*sigma_i=-1;
*sigma_j=-1;
*sigma_k=-1;
//printf("pas de triangle trouve\n----FIN A2RI BPA FIND SEED TRIANGLE\n");
return 0;
}
void a2ri_bpa_ball_pivot(vf_model *m, space_partition *sp, vector3d *normal, double radius, bpa_edge *e, int *listused, int sizeused, bpa_fronts *fronts, int *sigma_k, point3d *centre)
{
point3d milieu,p1,p2,p3;
pt_sp_depth *listcellule=NULL;
int sizelistcellule=0;
pt_point3d *listpoint=NULL;
int sizelistpoint=0;
int index=0,index2=0;
pt_point3d *listcentre=NULL;
double prodscal,max;
vector3d AB,AC;
//printf("----DEBUT A2RI BPA BALL PIVOT\n");
//printf("pivot sur l'arete %d %d - point oppose : %d\n",e->sigma_i,e->sigma_j,e->sigma_o);
//printf("centre : ");point3d_display(e->cijo);
point3d_init(&p1,m->ve[e->sigma_i].x,m->ve[e->sigma_i].y,m->ve[e->sigma_i].z);
point3d_init(&p3,m->ve[e->sigma_j].x,m->ve[e->sigma_j].y,m->ve[e->sigma_j].z);
point3d_init(&milieu,(p1.x+p3.x)/2.0,(p1.y+p3.y)/2.0,(p1.z+p3.z)/2.0);
listcellule=NULL;
sizelistcellule=0;
space_partition_get_neighbour(sp,&milieu,1,&listcellule,&sizelistcellule);
for(int j=0;jnb_point;
listpoint=(pt_point3d*)malloc(sizelistpoint*sizeof(pt_point3d));
a2ri_erreur_critique_si(listpoint==NULL,
"erreur allocation memoire pour listpoint\na2ri_bpa_ball_pivot");
listcentre=(pt_point3d*)malloc(sizelistpoint*sizeof(pt_point3d));
a2ri_erreur_critique_si(listcentre==NULL,
"erreur allocation memoire pour listcentre\na2ri_bpa_ball_pivot");
index=0;
/*CREATION DE LA LISTE DE POINT SE TROUVANT DANS LES CASES ADJACENTES AU POINT D'INDEX I*/
for(int j=0;jnb_point;k++)
listpoint[index++]=&(listcellule[j]->list_point[k]);
/*CONSTRUCTION DES BOULES CANDIDATES*/
//int nbcandidat=0;
for(int i=0;iatt_int!=e->sigma_i && listpoint[i]->att_int!=e->sigma_j && listpoint[i]->att_int!=e->sigma_o)
{
//printf("test triangle %d %d %d\n",e->sigma_i,listpoint[i]->att_int,e->sigma_j);
point3d_init(&p2,
m->ve[listpoint[i]->att_int].x,
m->ve[listpoint[i]->att_int].y,
m->ve[listpoint[i]->att_int].z);
if(a2ri_bpa_verif_contraintes(listpoint,
sizelistpoint,
p1,p2,p3,
normal[e->sigma_i],
normal[listpoint[i]->att_int],
normal[e->sigma_j],
radius,centre))
{
listcentre[i]=(point3d*)malloc(sizeof(point3d));
point3d_init(listcentre[i],centre->x,centre->y,centre->z);
//nbcandidat++;
//printf("centre OK, %d candidat\n",nbcandidat);
}
else
{
//printf("centre pas ok\n");
listcentre[i]=NULL;
}
}
else
listcentre[i]=NULL;
}
//printf("%d candidats sur %d\n",nbcandidat,sizelistpoint);
/*REGARDER LES BOULES ET CHOISIR LA BONNE*/
vector3d_init(&AB,e->cijo.x-milieu.x,e->cijo.y-milieu.y,e->cijo.z-milieu.z);
vector3d_normalize(&AB);
index=-1;
max=-1;
for(int i=0;ix-milieu.x,listcentre[i]->y-milieu.y,listcentre[i]->z-milieu.z);
vector3d_normalize(&AC);
prodscal=vector3d_scalarproduct(&AB,&AC);
/*DANS LE CAS OU NOUS N'AVONS PAS ENCORE DE CANDIDAT*/
if(index==-1)
{
index=listpoint[i]->att_int;
max=prodscal;
index2=i;
}
else
/*DANS LE CAS OU LA BOULE TESTEE EST MEILLEURE QUE LA PRECEDENTE RETENUE*/
if(prodscal>max)
{
index2=i;
index=listpoint[i]->att_int;
max=prodscal;
}
else
{
/*DANS LE CAS OU LA BOULE TESTEE EST AUSSI BONNE QUE LA PRECEDENTE RETENUE*/
if(prodscal==max)
{
//printf("ATTENTION, NOUS AVONS UNE EGALITE entre les points :\n%d de distance %d\n%d de distance %d\n",index,a2ri_bpa_front_distance(e,index),listpoint[i]->att_int,a2ri_bpa_front_distance(e,listpoint[i]->att_int));
if(a2ri_bpa_front_distance(e,index)>a2ri_bpa_front_distance(e,listpoint[i]->att_int))
index=listpoint[i]->att_int;
}
}
}
if(index!=-1)
{
*centre=*(listcentre[index2]);
point3d_init(&p2,m->ve[index].x,m->ve[index].y,m->ve[index].z);
/*printf("longueurs : %lf %lf %lf\n",
point3d_length(p1,*centre),
point3d_length(p2,*centre),
point3d_length(p3,*centre));*/
a2ri_erreur_critique_si(!egalite(point3d_length(&p1,centre),radius),
"la boule n'est pas bien definie\na2ri_bpa_ball_pivot\n");
a2ri_erreur_critique_si(!egalite(point3d_length(&p2,centre),radius),
"la boule n'est pas bien definie\na2ri_bpa_ball_pivot\n");
a2ri_erreur_critique_si(!egalite(point3d_length(&p3,centre),radius),
"la boule n'est pas bien definie\na2ri_bpa_ball_pivot\n");
}
free(listpoint);
free(listcellule);
free(listcentre);
*sigma_k=index;
if(list_int_contains(listused,sizeused,*sigma_k)!=-1 && !a2ri_bpa_front_contains_point_in_fronts(fronts,*sigma_k))
*sigma_k=-1;
//printf("-- FIN A2RI BPA BALL PIVOT\n");
}
void a2ri_vf_bpa(vf_model *m, vector3d *normal, double radius)
{
bpa_edge *e;
int sigma_k,sigma_i,sigma_j,*listused=NULL,sizeused=0;
bpa_fronts *fronts=NULL;
point3d centre;
int imin=0;
point3d pmin,pmax;
int nbpartX,nbpartY,nbpartZ;
space_partition *sp=(space_partition*)malloc(sizeof(space_partition));
/*INITIALISATION DE L'ALGORITHME*/
/*CREATION DE LA SPACE PARTITION POUR OPTIMISATION DES RECHERCHES*/
a2ri_erreur_critique_si(sp==NULL,
"Erreur allocation memoire pour sp\na2ri_bpa_find_seed_triangle\n");
point3d_init(&pmin,m->xmin,m->ymin,m->zmin);
point3d_init(&pmax,m->xmax,m->ymax,m->zmax);
nbpartX=(int)((m->xmax-m->xmin)/(2*radius));
if(nbpartX==0)
nbpartX++;
nbpartY=(int)((m->ymax-m->ymin)/(2*radius));
if(nbpartY==0)
nbpartY++;
nbpartZ=(int)((m->zmax-m->zmin)/(2*radius));
if(nbpartZ==0)
nbpartZ++;
space_partition_new(sp,&pmin,&pmax,nbpartX,nbpartY,nbpartZ);
a2ri_vf_space_partition(m,sp);
/*REVOIR L'ALGO*/
while(1)
{
while((e=a2ri_bpa_get_active_edge_in_fronts(fronts))!=NULL)
{
a2ri_bpa_ball_pivot(m,sp,normal,radius,e,listused,sizeused,fronts,&sigma_k,¢re);
if(sigma_k!=-1)
{
list_int_add(&listused,&sizeused,sigma_k,WITHOUT_REDUNDANCE);
#ifdef _DEBUG
printf("%c%c%c%c%c%c%c%c%c%c%c%c%lf%c",8,8,8,8,8,8,8,8,8,8,8,8,sizeused*100.0/(m->nbvertex*1.0),37);
#endif
//printf("Ajout triangle %d : %d %d %d par pivot\n",m->nbface,e->sigma_i,sigma_k,e->sigma_j);
a2ri_vf_add_face(m,e->sigma_i,sigma_k,e->sigma_j);
sigma_i=e->sigma_i;sigma_j=e->sigma_j;
//a2ri_bpa_display_fronts(fronts);
a2ri_bpa_join(&e,sigma_k,centre);
//a2ri_bpa_display_fronts(fronts);
a2ri_bpa_regularization(&fronts,sigma_i,sigma_j,sigma_k);
//a2ri_bpa_display_fronts(fronts);
}
else
{
//printf("arete frontiere\n");
e->state=BOUNDARY;
}
//a2ri_bpa_display_fronts(fronts);
}
if(a2ri_bpa_find_seed_triangle(m,sp,normal,radius,listused,sizeused,&sigma_i,&sigma_j,&sigma_k,¢re,imin))
{
#ifdef _DEBUG
printf("%c%c%c%c%c%c%c%c%c%c%c%c%lf%c",8,8,8,8,8,8,8,8,8,8,8,8,sizeused*100.0/(m->nbvertex*1.0),37);
#endif
//printf("Ajout triangle %d : %d %d %d par seed triangle\n",m->nbface,sigma_i,sigma_j,sigma_k);
imin=sigma_i;
a2ri_vf_add_face(m,sigma_i,sigma_j,sigma_k);
a2ri_bpa_free_fronts(&fronts);
fronts=NULL;
a2ri_bpa_new_front(&fronts,sigma_i,sigma_j,sigma_k,centre);
//a2ri_bpa_display_fronts(fronts);
list_int_add(&listused,&sizeused,sigma_i,WITH_REDUNDANCE);
list_int_add(&listused,&sizeused,sigma_j,WITH_REDUNDANCE);
list_int_add(&listused,&sizeused,sigma_k,WITH_REDUNDANCE);
}
else
{
printf("\nBPA termine...\n");
return;
}
}
return;
}
/*
void a2ri_vf_bpa_multipass(vf_model *m, vector3d *normal, double *listradius, int listsize)
{
return;
}*/
void a2ri_vf_bpa_without_normal(vf_model *m, double radius)
{
vector3d *list=NULL;
list=(vector3d*)malloc(m->nbvertex*sizeof(vector3d));
a2ri_erreur_critique_si(list==NULL,
"erreur allocation memoire pour list\na2ri_vf_bpa_without_normal\n");
for(int i=0;inbvertex;i++)
{
vector3d_init(&(list[i]),m->ve[i].x-((m->xmin+m->xmax)/2.0),m->ve[i].y-((m->ymin+m->ymax)/2.0),m->ve[i].z-((m->zmin+m->zmax)/2.0));
vector3d_normalize(&(list[i]));
}
a2ri_vf_bpa(m,list,radius);
free(list);
}
void a2ri_bpa_average_radius_suggestion(vf_model *m, double *min, double *max, double *average, double *sd)
{
/*TODO optimisation multi thread*/
space_partition sp;
point3d ptmin,ptmax;
double *listelongueur;
listelongueur=(double*)malloc(sizeof(double)*m->nbvertex);
a2ri_erreur_critique_si(listelongueur==NULL,"erreur allocation memoire a2ri_bpa_average_radius_suggestion pour listelongueur\n");
ptmin.x=m->xmin;ptmin.y=m->ymin;ptmin.z=m->zmin;
ptmax.x=m->xmax;ptmax.y=m->ymax;ptmax.z=m->zmax;
if(m->nbvertex>=24)
space_partition_new(&sp,&ptmin,&ptmax,
(int)(pow((m->nbvertex/24.0),1.0/3.0)),
(int)(pow((m->nbvertex/24.0),1.0/3.0)),
((int)pow((m->nbvertex/24.0),1.0/3.0)));
else
space_partition_new(&sp,&ptmin,&ptmax,1,1,1);
a2ri_vf_space_partition(m,&sp);
for(int i=0;inbvertex;i++)
{
point3d p1,p2;
double longueur;
point3d_init(&p1,m->ve[i].x,m->ve[i].y,m->ve[i].z);
space_partition_nearest_point(&sp,&p1,&p2,&longueur,REJECT_ZERO_LENGTH);
listelongueur[i]=longueur;
}
*min=list_double_min(listelongueur,m->nbvertex);
*max=list_double_max(listelongueur,m->nbvertex);
*average=list_double_average(listelongueur,m->nbvertex);
*sd=sqrt(list_double_variance(listelongueur,m->nbvertex));
space_partition_free(&sp);
}
void a2ri_bpa_initialisation(vf_model *m, bpa_fronts **fronts, int **listused, int *sizelistused)
{
IT_bpa_liste temp;
int nbtrou=IF_bpa_vf_hole(m,&temp);
//printf("\n\n%d trous\n",nbtrou);
//list_int_display(temp.list,temp.nbelt);
IT_bpa_liste *cycle;
cycle=(IT_bpa_liste*)malloc(nbtrou*sizeof(IT_bpa_liste));
int index=0;
for(int i=0;i1)
{
int i=0,j,commun=-1;
while(i