| 1 |
|
5 |
#include <stdio.h>
|
| 2 |
|
|
#include <math.h>
|
| 3 |
|
|
#include "r3d_struct.h"
|
| 4 |
|
|
#include "m3d_const.h"
|
| 5 |
|
|
#include "m3d_hotes.h"
|
| 6 |
|
|
#include "prototype2.h"
|
| 7 |
|
|
extern int debug ;
|
| 8 |
|
|
extern float biais ;
|
| 9 |
|
|
extern GEST_MEM *gest_r ;
|
| 10 |
|
|
int r3d_rech2(FACE *face,NOEUD **nresu,float critere,int *hist,FACE **finter,int *nb_face)
|
| 11 |
|
|
{
|
| 12 |
|
|
|
| 13 |
|
|
/* variables locales */
|
| 14 |
|
|
float *coord ;
|
| 15 |
|
|
NOEUD *noe_p ;
|
| 16 |
|
|
/* tableaux de recherche */
|
| 17 |
|
|
|
| 18 |
|
|
NOEUD *tab_adj[NB_MAX_CONNEC] ;
|
| 19 |
|
|
NOEUD *tab_lie[NB_MAX_CONNEC] ;
|
| 20 |
|
|
NOEUD *lis_possible[NB_MAX_CONNEC] ;
|
| 21 |
|
|
int iordre[NB_MAX_CONNEC] ;
|
| 22 |
|
|
float tab_crit[NB_MAX_CONNEC] ;
|
| 23 |
|
|
int lis_signe[NB_MAX_CONNEC] ;
|
| 24 |
|
|
float tab[NB_MAX_CONNEC] ;
|
| 25 |
|
|
|
| 26 |
|
|
/* parametres de la recherche */
|
| 27 |
|
|
int nb_adj, nb_lie, nb_noe_pos ;
|
| 28 |
|
|
float rayon ;
|
| 29 |
|
|
float xi,yi, zi ;
|
| 30 |
|
|
int ierr ;
|
| 31 |
|
|
float amin, prosca ;
|
| 32 |
|
|
|
| 33 |
|
|
/* utilitaires geometriques */
|
| 34 |
|
|
float vab[3], vac[3], vbc[3], vn[3], norme, pvec[3],vap[3], dist, dab ;
|
| 35 |
|
|
float vip[3], dip, crit ;
|
| 36 |
|
|
/* divers indices */
|
| 37 |
|
|
int i, ind ;
|
| 38 |
|
|
|
| 39 |
|
|
ierr = FAUX ;
|
| 40 |
|
|
amin = 0. ;
|
| 41 |
|
|
*nresu = NULL ;
|
| 42 |
|
|
coord = gest_r->coord ;
|
| 43 |
|
|
/* barycentre */
|
| 44 |
|
|
xi = (coord[x((face->n1)->num)] + coord[x((face->n2)->num)] + coord[x((face->n3)->num)])/3. ;
|
| 45 |
|
|
yi = (coord[y((face->n1)->num)] + coord[y((face->n2)->num)] + coord[y((face->n3)->num)])/3. ;
|
| 46 |
|
|
zi = (coord[z((face->n1)->num)] + coord[z((face->n2)->num)] + coord[z((face->n3)->num)])/3. ;
|
| 47 |
|
|
|
| 48 |
|
|
/* calcul de la normale */
|
| 49 |
|
|
vab[0] = coord[x((face->n2)->num)] - coord[x((face->n1)->num)] ;
|
| 50 |
|
|
vab[1] = coord[y((face->n2)->num)] - coord[y((face->n1)->num)] ;
|
| 51 |
|
|
vab[2] = coord[z((face->n2)->num)] - coord[z((face->n1)->num)] ;
|
| 52 |
|
|
dab = NORME(vab) ;
|
| 53 |
|
|
vac[0] = coord[x((face->n3)->num)] - coord[x((face->n1)->num)] ;
|
| 54 |
|
|
vac[1] = coord[y((face->n3)->num)] - coord[y((face->n1)->num)] ;
|
| 55 |
|
|
vac[2] = coord[z((face->n3)->num)] - coord[z((face->n1)->num)] ;
|
| 56 |
|
|
vbc[0] = coord[x((face->n3)->num)] - coord[x((face->n2)->num)] ;
|
| 57 |
|
|
vbc[1] = coord[y((face->n3)->num)] - coord[y((face->n2)->num)] ;
|
| 58 |
|
|
vbc[2] = coord[z((face->n3)->num)] - coord[z((face->n2)->num)] ;
|
| 59 |
|
|
|
| 60 |
|
|
/* calcul du critere 2 D */
|
| 61 |
|
|
pvec[0] = PVECX(vab,vac) ;
|
| 62 |
|
|
pvec[1] = PVECY(vab,vac) ;
|
| 63 |
|
|
pvec[2] = PVECZ(vab,vac) ;
|
| 64 |
|
|
|
| 65 |
|
|
vn[0] = PVECX(vab,vac) ;
|
| 66 |
|
|
vn[1] = PVECY(vab,vac) ;
|
| 67 |
|
|
vn[2] = PVECZ(vab,vac) ;
|
| 68 |
|
|
|
| 69 |
|
|
norme = NORME(vn) ;
|
| 70 |
|
|
if (norme<EPSILON)
|
| 71 |
|
|
{
|
| 72 |
|
|
if (debug) printf("%s\n"," normale nulle M3D_RECH2 ") ;
|
| 73 |
|
|
return(FAUX) ;
|
| 74 |
|
|
}
|
| 75 |
|
|
for (i=0;i<3;i++) vn[i] = vn[i]/norme ;
|
| 76 |
|
|
rayon = dab ;
|
| 77 |
|
|
|
| 78 |
|
|
/* determination des points adjacents et des points lies a la face courante */
|
| 79 |
|
|
nb_adj = 0 ;
|
| 80 |
|
|
nb_lie = 0 ;
|
| 81 |
|
|
if (!r3d_r_pts(coord,face,tab_adj,&nb_adj,tab_lie,&nb_lie))
|
| 82 |
|
|
{
|
| 83 |
|
|
if (debug) printf("%s\n"," Erreur r3d_r_pts M3D_RECH2 ") ;
|
| 84 |
|
|
return(FAUX) ;
|
| 85 |
|
|
}
|
| 86 |
|
|
nb_lie = 0 ;
|
| 87 |
|
|
/* ******************************************** */
|
| 88 |
|
|
/* traitement des noeuds adjacents PRIORITAIRES */
|
| 89 |
|
|
/* ******************************************** */
|
| 90 |
|
|
/* selection du meilleur point ADJACENT */
|
| 91 |
|
|
/* strategie employee, on choisit le noeud adjacent qui donnera le meilleur tetra */
|
| 92 |
|
|
/* tri des points adjacents par qualite croissante, se definir un seuil au dessous duquel on ne descend pas */
|
| 93 |
|
|
|
| 94 |
|
|
for (i=0;i<nb_adj;i++)
|
| 95 |
|
|
{
|
| 96 |
|
|
noe_p = tab_adj[i] ;
|
| 97 |
|
|
if (noe_p->flag!=(int)face) /* deja traite */
|
| 98 |
|
|
{
|
| 99 |
|
|
crit = m3d_e_qual(coord,(face->n1)->num,(face->n2)->num,(face->n3)->num,noe_p->num) ;
|
| 100 |
|
|
if (crit<critere) crit = CRITERE_ERREUR ;
|
| 101 |
|
|
tab_crit[i] = crit ;
|
| 102 |
|
|
|
| 103 |
|
|
/* calcul du vecteur PA */
|
| 104 |
|
|
vap[0] = coord[x(noe_p->num)] - coord[x((face->n1)->num)] ;
|
| 105 |
|
|
vap[1] = coord[y(noe_p->num)] - coord[y((face->n1)->num)] ;
|
| 106 |
|
|
vap[2] = coord[z(noe_p->num)] - coord[z((face->n1)->num)] ;
|
| 107 |
|
|
dist = PROSCA(vap,vn) ;
|
| 108 |
|
|
if (dist>rayon*EPSILON)
|
| 109 |
|
|
{
|
| 110 |
|
|
vip[0] = coord[x(noe_p->num)] - xi ;
|
| 111 |
|
|
vip[1] = coord[y(noe_p->num)] - yi ;
|
| 112 |
|
|
vip[2] = coord[z(noe_p->num)] - zi ;
|
| 113 |
|
|
dip = NORME(vip) ;
|
| 114 |
|
|
prosca = PROSCA(vip,vn) / dip ;
|
| 115 |
|
|
if (prosca < biais)
|
| 116 |
|
|
{
|
| 117 |
|
|
lis_signe[i] = NEGATIF ;
|
| 118 |
|
|
}
|
| 119 |
|
|
else lis_signe[i] = POSITIF ; /* point au dessus */
|
| 120 |
|
|
}
|
| 121 |
|
|
else lis_signe[i] = NEGATIF ; /* point en dessous */
|
| 122 |
|
|
noe_p->flag = (int)face ;
|
| 123 |
|
|
}
|
| 124 |
|
|
else
|
| 125 |
|
|
{
|
| 126 |
|
|
tab_crit[i] = CRITERE_ERREUR ;
|
| 127 |
|
|
}
|
| 128 |
|
|
}
|
| 129 |
|
|
|
| 130 |
|
|
/* tri par ordre de qualite croissante */
|
| 131 |
|
|
if (nb_adj>0)
|
| 132 |
|
|
{
|
| 133 |
|
|
for (i=0;i<nb_adj;i++) tab[i] = 1./tab_crit[i] ;
|
| 134 |
|
|
for (i=0;i<nb_adj;i++) iordre[i] = i+1 ;/* attention passage c fortran */
|
| 135 |
|
|
trirea(tab,&nb_adj,iordre) ;
|
| 136 |
|
|
|
| 137 |
|
|
/* parcours du vecteur des noeuds adjacents selectes */
|
| 138 |
|
|
i = 0 ;
|
| 139 |
|
|
while (i<nb_adj)
|
| 140 |
|
|
{
|
| 141 |
|
|
ind = iordre[i] -1 ;
|
| 142 |
|
|
noe_p = (NOEUD*)tab_adj[ind] ;
|
| 143 |
|
|
/* flagger le noeud */
|
| 144 |
|
|
noe_p->flag = (int)face ;
|
| 145 |
|
|
/* TEST : LE NOEUD EST-IL SOLUTION ? */
|
| 146 |
|
|
*nb_face = 0 ;
|
| 147 |
|
|
if (r3d_test2(face,amin,ind,tab_adj,lis_signe,tab_crit,coord,finter,nb_face,&ierr))
|
| 148 |
|
|
{
|
| 149 |
|
|
*nresu = tab_adj[ind] ;
|
| 150 |
|
|
/* FONDAMENTAL */
|
| 151 |
|
|
/* ne pas oublier de deflagger les noeuds */
|
| 152 |
|
|
for (i=0;i<nb_adj;i++)
|
| 153 |
|
|
{
|
| 154 |
|
|
noe_p = (NOEUD*)tab_adj[i] ;
|
| 155 |
|
|
noe_p->flag = 0 ;
|
| 156 |
|
|
}
|
| 157 |
|
|
*hist = ADJACENT ;
|
| 158 |
|
|
return(VRAI) ;
|
| 159 |
|
|
}
|
| 160 |
|
|
if (ierr == VRAI)
|
| 161 |
|
|
{
|
| 162 |
|
|
if (debug) printf("%s\n"," Erreur r3d_test2 (adj) M3D_RECH2 ") ;
|
| 163 |
|
|
return(FAUX) ;
|
| 164 |
|
|
}
|
| 165 |
|
|
i++ ;
|
| 166 |
|
|
}
|
| 167 |
|
|
}
|
| 168 |
|
|
|
| 169 |
|
|
/* ******************************************************************* */
|
| 170 |
|
|
/* recherche du meilleur point de la liste */
|
| 171 |
|
|
/* ******************************************************************* */
|
| 172 |
|
|
nb_noe_pos = gest_r->nb_noeud ;
|
| 173 |
|
|
for (i=0;i<nb_noe_pos;i++)
|
| 174 |
|
|
{
|
| 175 |
|
|
ADRESSE(noeud,i,noe_p)
|
| 176 |
|
|
lis_possible[i] = noe_p ;
|
| 177 |
|
|
}
|
| 178 |
|
|
for (i=0;i<nb_noe_pos;i++)
|
| 179 |
|
|
{
|
| 180 |
|
|
noe_p = (NOEUD*)lis_possible[i] ;
|
| 181 |
|
|
if (noe_p->flag!=(int)face) /* deja traite */
|
| 182 |
|
|
{
|
| 183 |
|
|
lis_signe[i] = POSITIF ; /* point au dessus */
|
| 184 |
|
|
crit = m3d_e_qual(coord,(face->n1)->num,(face->n2)->num,(face->n3)->num,noe_p->num) ;
|
| 185 |
|
|
if (crit<critere) crit = CRITERE_ERREUR ;
|
| 186 |
|
|
tab_crit[i] = crit ;
|
| 187 |
|
|
|
| 188 |
|
|
vip[0] = coord[x(noe_p->num)] - xi ;
|
| 189 |
|
|
vip[1] = coord[y(noe_p->num)] - yi ;
|
| 190 |
|
|
vip[2] = coord[z(noe_p->num)] - zi ;
|
| 191 |
|
|
dip = NORME(vip) ;
|
| 192 |
|
|
prosca = PROSCA(vip,vn) / dip ;
|
| 193 |
|
|
if (prosca < biais)
|
| 194 |
|
|
{
|
| 195 |
|
|
lis_signe[i] = NEGATIF ;
|
| 196 |
|
|
}
|
| 197 |
|
|
}
|
| 198 |
|
|
else
|
| 199 |
|
|
{
|
| 200 |
|
|
lis_signe[i] = NEGATIF ; /* point en dessous */
|
| 201 |
|
|
tab_crit[i] = CRITERE_ERREUR ;
|
| 202 |
|
|
}
|
| 203 |
|
|
}
|
| 204 |
|
|
|
| 205 |
|
|
/* a ce stade pour chaque point possible, on dispose du critere en chaque point */
|
| 206 |
|
|
/* FONDAMENTAL */
|
| 207 |
|
|
/* ne pas oublier de deflagger les noeuds */
|
| 208 |
|
|
for (i=0;i<nb_adj;i++)
|
| 209 |
|
|
{
|
| 210 |
|
|
noe_p = (NOEUD*)tab_adj[i] ;
|
| 211 |
|
|
noe_p->flag = 0 ;
|
| 212 |
|
|
}
|
| 213 |
|
|
|
| 214 |
|
|
if (nb_noe_pos>0)
|
| 215 |
|
|
{
|
| 216 |
|
|
for (i=0;i<nb_noe_pos;i++) tab[i] = 1./tab_crit[i] ;
|
| 217 |
|
|
for (i=0;i<nb_noe_pos;i++) iordre[i] = i+1 ; /* attention passage c fortran */
|
| 218 |
|
|
trirea(tab,&nb_noe_pos,iordre) ;
|
| 219 |
|
|
|
| 220 |
|
|
/*
|
| 221 |
|
|
--------------------------------------------------------------------------------
|
| 222 |
|
|
A ce niveau, on a constitue une liste de points ranges par critere croissants
|
| 223 |
|
|
auxquels on va faire subir les tests de selection !
|
| 224 |
|
|
--------------------------------------------------------------------------------
|
| 225 |
|
|
*/
|
| 226 |
|
|
|
| 227 |
|
|
/* parcours du vecteur des noeuds selectes */
|
| 228 |
|
|
i = 0 ;
|
| 229 |
|
|
while (i<nb_noe_pos)
|
| 230 |
|
|
{
|
| 231 |
|
|
ind = iordre[i] -1 ;/* -1 a cause du passage c -->fortran */
|
| 232 |
|
|
noe_p = lis_possible[ind] ;
|
| 233 |
|
|
*nb_face = 0 ;
|
| 234 |
|
|
if (r3d_test2(face,amin,ind,lis_possible,lis_signe,tab_crit,coord,finter,nb_face,&ierr))
|
| 235 |
|
|
{
|
| 236 |
|
|
*nresu = noe_p ;
|
| 237 |
|
|
*hist = PROCHE ;
|
| 238 |
|
|
return(VRAI) ;
|
| 239 |
|
|
}
|
| 240 |
|
|
if (ierr == VRAI)
|
| 241 |
|
|
{
|
| 242 |
|
|
if (debug) printf("%s\n"," Erreur r3d_test2 (proche) R3D_RECH2 ") ;
|
| 243 |
|
|
return(FAUX) ;
|
| 244 |
|
|
}
|
| 245 |
|
|
i++ ;
|
| 246 |
|
|
}
|
| 247 |
|
|
}
|
| 248 |
|
|
*nresu=NULL ;
|
| 249 |
|
|
return(VRAI) ;
|
| 250 |
|
|
}
|
