float angleX,angleY,bangleX,bangleY,rayon,tempo,tempo1;
		float pose=1.2f;
		int ordre=18;
		Ensemble lensemble;
		Places lesplaces;
		BFont gillesans;
		Couleur couleurs;
		
//*******************************************
//*******************************************
//*******************************************

void setup(){

	gillesans = loadFont("GillSans.vlw.gz");
	rectMode(CENTER_DIAMETER);
	ellipseMode(CENTER_DIAMETER);	
	size(750,500);
	background(175,180,200);
	couleurs=new Couleur();
	initier();
}

void loop(){
	
	clear();
	tempo+=0.02f;
	lesplaces.modifierlespos(tempo);
	if(tempo>tempo1){
		tempo1+=pose;
		lensemble.initialiserarrivee();	
	}
		fill(55,40,90);
		textFont(gillesans,19);
		text(lensemble.chaine,20,490);
		textFont(gillesans,140);
	push();
	modifierparam();
	lesplaces.afficher();
	lensemble.afficher();
	pop();	
}
//*******************************************
//*******************************************
//*******************************************
void initier(){
	

	rayon=300.0f/sin(PI/ordre);
	lesplaces=new Places();
	lensemble=new Ensemble(lesplaces);
	angleX=0;
	angleY=0;
	tempo=0;
	tempo1=pose;
}

 void mousePressed(){
 	tempo1=tempo+pose;
	lensemble.initialiserarrivee();

}
void afficherRepere(float l){
       
	stroke(255,0,0);
       line(0,0,0,l,0,0);
       stroke(0,255,0);    
       line(0,0,0,0,l,0);
       stroke(0,0,255);   
       line(0,0,0,0,0,l);          
  }
   
//*******************************************
//*******************************************
//*******************************************
void modifierparam(){

	bangleX=-0.35f+(-mouseY+100)/500.0f;
	bangleY=tempo+(mouseX-width/2.0f)/100.0f;//	
	angleX+=(bangleX-angleX)/10.0f;
	angleY+=(bangleY-angleY)/10.0f;
	
	translate(200,100,-2800);
	rotateX(angleX);
	rotateY(angleY);
	stroke(255,0,255,100);
	fill(255,190,190,199);
	push();
		rotateX(HALF_PI);
		ellipse(0,0,2*rayon+1800,2*rayon+1800);
	pop();

	
}

////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
static class Place{
	Vecteur pos;
	Quat qua;
	int num;
public Place(Place pl){
			pos=pl.pos;
			qua=pl.qua;
			num=pl.num;	
}
public Place(int n,Vecteur p,Quat q){
	pos=p;
	qua=q;
	num=	n;	
	}
public void set(Place pl){
		pos.set(pl.pos);
		qua.set(pl.qua);
		num=pl.num;		
		}
public static Place interpolate(Place pdepart,Place parrivee,float t,float haut){
		Vecteur vinter=Vecteur.comb(1-t,pdepart.pos,t,parrivee.pos);
		vinter.y-=haut*(float)Math.sin(t*PI);
		Quat qinter=Quat.slerp2(pdepart.qua,parrivee.qua,t);		
	return new Place(0,vinter,qinter);			
}
					
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
class Places{
	Place[] table;
	
	
public Places(){

	table=new Place[ordre];
	initier();	
	}
	
void initier(){
	for(int i=0;i<ordre;i++){
		float a=TWO_PI*i/ordre;
		Vecteur p=new Vecteur(rayon*cos(a),0,rayon*sin(a));
		Quat q=new Quat(new Vecteur(0,1,0),-a,1.0f);
		table[i]=new Place(i,p,q);
		 }			
	}

public void afficher(){
	push();
		for(int i=0;i<ordre;i++){
		push();
			translate(table[i].pos.x,180+table[i].pos.y,table[i].pos.z);
			rotateY(-i*TWO_PI/ordre);	
			fill(couleurs.table[i][0],couleurs.table[i][1],couleurs.table[i][2]);
			stroke(180);
			box(200);
			fill(255);
			
			rotateY(HALF_PI);
			translate(0,0,102);
			text(i,-30,30);
		pop();
		push();
			translate(table[i].pos.x,-180-table[i].pos.y,table[i].pos.z);
			rotateY(-i*TWO_PI/ordre);	
			fill(couleurs.table[i][0],couleurs.table[i][1],couleurs.table[i][2],20);
			stroke(180);
			box(200);
			rotateY(HALF_PI);
			
			
			translate(0,0,50);
			rotateX(PI);
			fill(255,240);
			text(i,-40,0);
			noStroke();	
		pop();
		}
	pop();
	}
void	modifierlespos(float t)
	{
	for(int i=0;i<ordre;i++){table[i].pos.y=-380-100*cos(16*tempo+2*TWO_PI*i/ordre);}
}
}
//+200+200*cos(5*tempo*TWO_PI*i/ordre)
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
class Element{
		int num,depart, arrivee;
		Place placeinter;
		float temps,haut;
public Element(int n,int depart,int arrivee)
{		
		num=n;	
		this.depart= depart;
		this.arrivee=arrivee;
		haut=500+random(0,400);
}

void interpoler(){		
		temps+=0.025;
		Place placedepart	=lesplaces.table[depart];
		Place placearrivee=lesplaces.table[arrivee];			
		if(temps<1){			
			placeinter=Place.interpolate(placedepart,placearrivee,temps,haut);	
		}else{
			temps=1;
			placeinter=new Place(placearrivee);			
		}	
		push();
			translate(placeinter.pos.x,placeinter.pos.y,placeinter.pos.z);
			appliqueQuat(placeinter.qua);
			fill(couleurs.table[num][0],couleurs.table[num][1],couleurs.table[num][2]);
			stroke(200);
			box(158);
			rotateY(PI/2);
			translate(-50,130,80);
			fill(255);
			text(num,0,-100);
		pop();
		push();
			translate(placeinter.pos.x,-placeinter.pos.y,placeinter.pos.z);
			appliqueQuat(placeinter.qua);
	fill(couleurs.table[num][0],couleurs.table[num][1],couleurs.table[num][2],20);
			noStroke();
			box(158);
			rotateY(PI/2);
			translate(-50,-30,80);
			rotateX(PI);
			fill(255,210);
			text(num,0,0);			
		pop();
}	
	
void appliqueQuat(Quat q){
	     float[] ro=q.getValue();
	     rotate(ro[0],ro[1],ro[2],ro[3]);
	  }

}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
class Ensemble{
		Element[] elements;
		int n;
		float r;
		Substitution subst;
		String[] str;
		String chaine;
		
public Ensemble(Places plass){
		n=ordre;
		r=rayon;
		str=new String[ordre];
		chaine="";
		elements=new Element[n];
		subst=new Substitution();
		lesplaces=plass;
		for(int i=0;i<n;i++)	{
			elements[i]=new Element(i,i,subst.table[i]);
		}
	}
	
void initialiserarrivee(){
	 
	for(int i=0;i<n;i++){		
		elements[i].temps=0;
		int d=elements[i].depart;	
		int a=elements[i].arrivee;
		int aa=subst.table[a];
		
		elements[i].depart=a;	
		elements[i].arrivee=aa;
		elements[i].haut=200+abs(aa-a)*(900/ordre);
		str[aa]=" ("+aa+","+i+") ";	
	}
	chaine="";
	for(int i=0;i<n;i++){
	chaine=chaine+str[i];
	}	
}

void afficher()
{
	for(int i=0;i<n;i++)
	{	push();
		elements[i].interpoler();
		pop();
	}
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
class Couleur{
	int[][] table;
public Couleur(){
	table=new int[ordre][3];
	initier();
}
 void initier(){
 	int c;	
	for(int i=0;i<ordre;i++){
		table[i][0]=90+(int)(30*Math.sin(4*PI/ordre*i));
		table[i][1]= 100-(int)(30*Math.cos(2*PI/ordre*i));
		table[i][2]=120-(int)(40*Math.cos(2*PI/ordre*i));
	}
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
class Substitution
{
	int[] table;
	
public Substitution()
{
		table=new int[ordre];
		initier();
}
public void initier0()
{			for(int i=0;i<ordre;i++)	table[i]=i;
			
			table[0]=1;
			table[1]=2;
			table[2]=0;
			table[3]=3;
}		
public void initier()
{
		for(int i=0;i<ordre;i++)	table[i]=i;
		for(int i=0;i<ordre;i++)	{
			int j=Math.round(random(0,ordre-1));
			int k=Math.round(random(0,ordre-1));
			int pr=table[j];
			table[j]=table[k];
			table[k]=pr;	
		}
	
}

}
//------------------------------------------------------------
// Quat class
//------------------------------------------------------------
public static class Quat
{
  float w, x, y, z;

 public Quat()
  {
    reset();
  }

 public  Quat(float w, float x, float y, float z)
  {
    this.w = w;
    this.x = x;
    this.y = y;
    this.z = z;
  }
   public Quat(float w, Vecteur v)
  {
    this.w = w;
    this.x =v. x;
    this.y = v.y;
    this.z = v.z;
  }
public  Quat(Quat q)
  {
    set(q);
  }

 public  void reset()
  {
    w = 1.0f;
    x = 0.0f;
    y = 0.0f;
    z = 0.0f;
  }

  public void set(float w, Vecteur v)
  {
    this.w = w;
    x = v.x;
    y = v.y;
    z = v.z;
  }

  public void set(Quat q)
  {
    w = q.w;
    x = q.x;
    y = q.y;
    z = q.z;
  }
  public Quat(Vecteur v,float angle,float rapport){
   v.normalize(rapport);
   float sinus=(float)Math.sin(angle/2);	
   this.w = rapport*(float)Math.cos(angle/2);
     this.x =v.x*sinus;
     this.y = v.y*sinus;
     this.z = v.z*sinus;
   }
public float norme(){
	return (float)Math.sqrt(x * x + y * y + z * z + w * w);
}

 public  Quat normalize()
  {
    float square = x * x + y * y + z * z + w * w;
    float dist = (square > 0.0f) ? (1.0f / (float) Math.sqrt(square)) : 1.0f;

    x *= dist;
    y *= dist;
    z *= dist;
    w *= dist;
    return this;
  }
  public  Quat normalize(float c)
   {
     float square = x * x + y * y + z * z + w * w;
     float dist = (square > 0.0f) ? (c / (float) Math.sqrt(square)) : c;
	
     x *= dist;
     y *= dist;
     z *= dist;
     w *= dist;
     return this;
   }
 public static Quat mul(Quat q1, Quat q2)
  {
    Quat res = new Quat();
    res.w = q1.w * q2.w - q1.x * q2.x - q1.y * q2.y - q1.z * q2.z;
    res.x = q1.w * q2.x + q1.x * q2.w + q1.y * q2.z - q1.z * q2.y;
    res.y = q1.w * q2.y + q1.y * q2.w + q1.z * q2.x - q1.x * q2.z;
    res.z = q1.w * q2.z + q1.z * q2.w + q1.x * q2.y - q1.y * q2.x;
    return res;
  }
 public static Quat comb(Quat q1,float r1, Quat q2,float r2)
   {
     Quat res = new Quat();
     res.w = q1.w *r1 +  q2.w*r2;
     res.x = q1.x * r1+  q2.x * r2;
     res.y = q1.y * r1+  q2.y * r2;
     res.z = q1.z * r1+  q2.z * r2;
     return res;
   }
   public Quat ajouter(Quat q1,float r1)
     {
       Quat res = new Quat();
       res.w = q1.w *r1;
       res.x = q1.x * r1;
       res.y = q1.y * r1;
       res.z = q1.z * r1;
       return res;
     } 
      
     public   float Angle()
  {	
   
    float nq=norme();
	return (float) Math.acos(w/nq)* 2.0f;
 }  
     public   float[] getValue()
 {	
   float[] res = new float[4];
   float nq=norme();
	 res[0] = (float) Math.acos(w/nq)* 2.0f;
  	 
	 float nV= (float) Math.sqrt(x*x+y*y+z*z);
  if ( nV< 0.00001f*nq)
   {
	res[1] = x ;
	res[2] = y;
	res[3] = z ;   
   }else{
	 res[1] = x /nV;
	 res[2] = y/nV ;
	 res[3] = z/nV;  }
   return res;
 }
 
 public   Quat conjugue(){
	return new Quat(w,-x,-y,-z);
}
public  Quat oppose(){
	return new Quat(-w,-x,-y,-z);
}
public Quat copie(){
	return new Quat(w,x,y,z);
	}
	public Quat copieNorme(){
		Quat res=new Quat(w,x,y,z);
		res.normalize();
		return res;
		}	
	public Vecteur tourner(Vecteur v){
	Quat qv=new Quat(0.0f,v.x,v.y,v.z);
	Quat qc=this.conjugue();
	Quat q1=Quat.mul(qv,qc);	
	Quat q= Quat.mul(this,q1);
	return new Vecteur(q.x,q.y,q.z);	
	
}
public static Quat slerp(Quat d, Quat a,float t){
	Quat res;
	d.normalize();
	a.normalize();
	float costheta=d.x*a.x+d.y*a.y+d.z*a.z;
	
	if(costheta<0.99f){
		float theta=(float)Math.acos(costheta);
		float sintheta=(float)Math.sin(theta);
		float rd=(float)Math.sin(theta*(1-t))/sintheta;
		float ra=(float)Math.sin(theta*t)/sintheta;
		 res= Quat.comb(d,rd,a,ra);}
	else{
		res=Quat.comb(d,1-t,a,t);
	}
	return res;

}
public static Quat slerp1(Quat d, Quat a,float tt){
	
	d.normalize();
	a.normalize();
	float t=(tt-1)*(tt-1)*(tt-1)+1;
	float angle=(float)Math.acos(d.x*a.x+d.y*a.y+d.z*a.z);
	if(angle>0.05f){	
	float sina=(float)Math.sin(angle);
	float rd=(float)Math.sin(angle*(1-t))/sina;
	float ra=(float)Math.sin(angle*t)/sina;
	return Quat.comb(d,rd,a,ra);}
	else{return Quat.comb(d,1-t,a,t);
	}
}
public Vecteur axe(){
return new Vecteur(x,y,z);	
}
public static Quat slerp2(Quat d, Quat a,float tt){
	Quat res;
	d.normalize();
	a.normalize();
	float costheta=d.x*a.x+d.y*a.y+d.z*a.z;
	float t=(tt-1)*(tt-1)+1;
	if(costheta<0.9999f){
		float theta=(float)Math.acos(costheta);
		float sintheta=(float)Math.sin(theta);
		float rd=(float)Math.sin(theta*(1-t))/sintheta;
		float ra=(float)Math.sin(theta*t)/sintheta;
		 res= Quat.comb(d,rd,a,ra);
		}
	else{
		res=Quat.comb(d,1-t,a,t);
	}
	return  Quat.mul(res,new Quat((float)Math.cos(t*6.2832f),(float)Math.sin(t*6.2832f),(float)Math.sin(t*6.2832f),0));

}

public static Quat euler2quat(float psi,float theta,float phi){
	/* psi      :angle de la rotation autour de 0z    :precession
	 * theta   :angle de la rotation autour de 0x1  :nutation
	 * phi      :angle de la rotation autoue de 0z2  : rotation propre
	 */
		float w,x,y,z,th,psiMphi,psiPphi;
		th=theta/2;
		psiMphi=(psi-phi)/2;
		psiPphi=(psi+phi)/2;		
		w=(float)Math.cos(th)*(float)Math.cos(psiPphi);
		x=(float)Math.sin(th)*(float)Math.cos(psiMphi);
		y=(float)Math.sin(th)*(float)Math.sin(psiMphi);
		z=(float)Math.cos(th)*(float)Math.sin(psiPphi);		
	return new Quat(w,x,y,z);
}

}
//-------------------------------------------------------
//-------------------------------------------------------
public static class Vecteur
{
public  float x, y, z;
 
public  Vecteur()
  {
  }

public  Vecteur(float x, float y, float z)
  {
    this.x = x;
    this.y = y;
    this.z = z;
 
  }
  
public  Vecteur(float x, float y, float z,float lon)
  { float no=(float) Math.sqrt(x * x + y * y + z * z);
  	no=lon/no;
    this.x = x*no;
    this.y = y*no;
    this.z = z*no;
 
  } 
  public void place(float xx, float yy, float zz)
  {
    this.x = xx;
    this.y = yy;
    this.z = zz;
  }
  public void set(Vecteur v)
   {
     this.x = v.x;
     this.y =v.y;
     this.z = v.z;
 
   }
 public Vecteur normalize()
  {
    float length = length();
    x /= length;
    y /= length;
    z /= length;
    return this;
  }
  public  Vecteur normalize(float k)
   {
     float length = length();
     x=x/ length*k;
     y =y/ length*k;
     z =z/ length*k;
     return this;
   }
   public  float length()
  {
    return (float) Math.sqrt(x * x + y * y + z * z);
  }

  public  Vecteur cross(Vecteur v2)
  {
    Vecteur res = new Vecteur();
    res.x = y * v2.z - z * v2.y;
    res.y =z * v2.x - x * v2.z;
    res.z = x * v2.y - y * v2.x;
    return res;
  }

  public  static float dot(Vecteur v1, Vecteur v2)
  {
    return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z;
  }
  public float dot(Vecteur v1)
  {
    return v1.x * x + v1.y *y + v1.z *z;
  }
  public Vecteur mul( float d)
  {
    Vecteur res = new Vecteur();
    res.x =x * d;
    res.y = y * d;
    res.z = z * d;
    return res;
  }
  public static Vecteur comb(float a,Vecteur v1,float b, Vecteur v2)
  {
   float  rx =a* v1.x + b*v2.x;
   float ry =a* v1.y + b*v2.y;
    float rz =a* v1.z + b*v2.z;
    return new Vecteur(rx,ry,rz);
  }
  public static Vecteur barycentre(float a,Vecteur v1,float b, Vecteur v2)
   {
   Vecteur res=comb(a,v1,b,v2);
   res=res.mul(1/(a+b));
     return res;
   }
  public  Vecteur ajouter(Vecteur v,float m){
		Vecteur res=new Vecteur(x+v.x*m, y+v.y*m,z+v.z*m);
    return res;
  }
  public  Vecteur ajouter(float ax,float ay,float az){
		 Vecteur res=new Vecteur(x+ax, y+ay,z+az);
     return res;
   }
  
  public  void afficher(String tex,BApplet ba){
  	ba.println(tex+"x= "+x+" y= "+y+" z= "+z);
  }
  public  Vecteur projete(Vecteur laxe){
  	laxe.normalize();
  	Vecteur res=laxe.mul(this.dot(laxe));
  	return res;
  }
  public Vecteur projeteSurAxe(Vecteur laxe){
	 laxe.normalize();
	 Vecteur res=laxe.mul(this.dot(laxe));
	 return res;
   }
   public  Vecteur projeteSurPlan(Vecteur laxe){
	  laxe.normalize();
	  Vecteur res=projeteSurAxe(laxe);
	  res=this.ajouter(res,-1);
	  return res;
    } 
    public  Vecteur symetrique(Vecteur laxe){
	    laxe.normalize();
	    Vecteur res=projeteSurAxe(laxe);
	    res=this.ajouter(res,-2.0f);
	    return res;
      }
     public float distancePointDroite(Vecteur d, Vecteur v){
		v.normalize();
	     	Vecteur pd=d.ajouter(this,-1);
	      	Vecteur hd=v.mul(v.dot(pd));
	    	 Vecteur ph=pd.ajouter(hd,-1);
	     	 return ph.length();
      } 
    /*projection sur le plan vectoriel de normale "laxe"
    public   Vecteur projeteSurPlan(Vecteur laxe,Vecteur unpoint){
	    laxe.normalize();
	    Vecteur res=projeteSurPlan(laxe);	   
	return  res.ajouter(unpoint.projeteSurAxe(res),1);
	   
      }*/
        
      public  float donneAngle(Vecteur vc){
	 return (float) Math.acos(this.dot(vc)/(length()*vc.length()));
  }
  
  public  Vecteur tourner(Vecteur axe,float angle){//axe est normé et orthogonal à this
  	Vecteur vaxe=axe.mul(this.dot(axe));
  	Vecteur vx=this.ajouter(vaxe,-1);
  	Vecteur ygrec=axe.cross(this);
  	return vaxe.ajouter(Vecteur.comb((float)Math.cos(angle),this,(float)Math.sin(angle),ygrec),1);
  }
  public Vecteur cloner()
    {
      Vecteur res = new Vecteur();
      res.x =x ;
      res.y = y ;
      res.z = z ;
      return res;
    } 
    public  Vecteur tourner(float a,Vecteur ax){
	    Quat qv=new Quat(0.0f,x,y,z);
	    Quat q0=new Quat((float)Math.cos(a/2),ax.mul((float)Math.sin(a/2)));
	    Quat qc=q0.conjugue();
	    Quat q1=Quat.mul(qv,qc);	
	    Quat q= Quat.mul(q0,q1);
	    return new Vecteur(q.x,q.y,q.z);	
	
    } 
    public  Vecteur coorabs(BApplet ba) {
	    float xa = ba.objectX(x,y,z);
	    float ya = ba.objectY(x,y,z);
	    float za = ba.objectZ(x,y,z);
	    return new Vecteur(xa, ya, za);
    }
//  *******************************************
//  *******************************************
//  *******************************************
    public static  void afficherRepere(BApplet ba,float lon){
       
	     ba.stroke(255,0,0);
	    ba.line(0,0,0,lon,0,0);
	    ba.stroke(0,255,0);    
	    ba.line(0,0,0,0,lon,0);
	    ba.stroke(0,0,255);   
	    ba.line(0,0,0,0,0,lon);          
       } 
public static  void afficherRepere(BApplet ba){
       
	 ba.stroke(255,0,0);
	ba.line(0,0,0,500,0,0);
	ba.stroke(0,255,0);    
	ba.line(0,0,0,0,500,0);
	ba.stroke(0,0,255);   
	ba.line(0,0,0,0,0,500);          
   } 
 
//  *******************************************
//  *******************************************
//  *******************************************
    public  void afficherLigne(float k,BApplet ba){
    	ba.line(x*k,y*k,z*k,-x*k,-y*k,-z*k);
}

    }