git.hungrycats.org Git - xscreensaver/blob - hacks/celtic.c

   1 /* celtic, Copyright (c) 2006 Max Froumentin <max@lapin-bleu.net>
   2  *
   3  * Permission to use, copy, modify, distribute, and sell this software and its
   4  * documentation for any purpose is hereby granted without fee, provided that
   5  * the above copyright notice appear in all copies and that both that
   6  * copyright notice and this permission notice appear in supporting
   7  * documentation.  No representations are made about the suitability of this
   8  * software for any purpose.  It is provided "as is" without express or
   9  * implied warranty.
  10  *
  11  * A celtic pattern programme inspired by "Les Entrelacs Celtes", by
  12  * Christian Mercat, Dossier Pour La Science, no. 47, april/june 2005.
  13  * See <http://www.entrelacs.net/>
  14  */
  15
  16 #include <math.h>
  17 #include <assert.h>
  18 #include "screenhack.h"
  19 #include "erase.h"
  20
  21 #define SQRT_3 1.73205080756887729352
  22
  23 /*-----------------------------------------*/
  24 Display *dpy;
  25 Window window;
  26 int ncolors;
  27 XColor *colors;
  28 GC gc,shadow_gc,gc_graph;
  29
  30 struct params {
  31   unsigned long curve_width, shadow_width;
  32   double shape1, shape2;
  33   unsigned long margin;
  34
  35   enum graph_type { polar, grid, kennicott, triangle } type;
  36   unsigned long edge_size;
  37   unsigned long cluster_size; /* only used if type is kennicott */
  38   unsigned long delay;        /* controls curve drawing speed (step delay
  39                                * in microsecs) */
  40   unsigned long nsteps; /* only if triangle: number of subdivisions along the side */
  41   unsigned long nb_orbits;          /* only used if type is polar */
  42   unsigned long nb_nodes_per_orbit; /* only used if type is polar */
  43
  44   double angle; /* angle of rotation of the graph around the centre */
  45 } params;
  46
  47
  48 /*-----------------------------------------*/
  49 typedef enum direction {
  50   CLOCKWISE=0, ANTICLOCKWISE=1
  51 } Direction;
  52
  53
  54 /*-----------------------------------------*/
  55 typedef struct array {
  56   int nb_elements;
  57   int nb_allocated_elements;
  58   int increment;
  59   void **elements;
  60 } *Array;
  61
  62 static Array array_new(int increment)
  63 {
  64   Array new;
  65   assert(new=(Array)calloc(1,sizeof(struct array)));
  66   new->nb_elements=0;
  67   new->nb_allocated_elements=0;
  68   new->increment=increment;
  69   return new;
  70 }
  71
  72 static void array_del(Array a, void (*free_element)(void*))
  73 {
  74   int i;
  75   if (free_element)
  76     for (i=0;i<a->nb_elements;i++)
  77       free_element(a->elements[i]);
  78   free(a->elements);
  79   free(a);
  80 }
  81
  82 static void array_add_element(Array a, void *element)
  83 {
  84   if (a->nb_elements == a->nb_allocated_elements) {
  85     /* we must allocate more */
  86     a->nb_allocated_elements+=a->increment;
  87     a->elements=realloc(a->elements,a->nb_allocated_elements*sizeof(void *));
  88   }
  89   a->elements[a->nb_elements++]=element;
  90 }
  91 /*-----------------------------------------*/
  92
  93 typedef struct node {
  94   double x,y;
  95   Array edges;
  96 } *Node;
  97
  98 typedef struct edge {
  99   Node node1, node2;
 100   double angle1, angle2;
 101 } *Edge;
 102
 103 /*-----------------------------------------*/
 104 /* Node functions */
 105
 106 static Node node_new(double x, double y)
 107 {
 108   Node new;
 109   assert(new = (Node)calloc(1,sizeof(struct node)));
 110   new->x=x;
 111   new->y=y;
 112   new->edges = array_new(10);
 113   return new;
 114 }
 115
 116 static void node_del(void *n)
 117 { /* not Node * because the function is passed to array_del */
 118   array_del(((Node)n)->edges,NULL);
 119   free(n);
 120 }
 121
 122 #if 0
 123 static void node_to_s(Node n, FILE *f)
 124 {
 125   fprintf(f,"Node: %g %g\n",n->x,n->y);
 126 }
 127 #endif
 128
 129 static void node_draw(Node n)
 130 {
 131   XDrawArc(dpy,window,gc_graph,(int)rint(n->x)-5,(int)rint(n->y)-5,10,10,0,360*64);
 132 }
 133
 134 static void node_add_edge(Node n, Edge e)
 135 {
 136   array_add_element(n->edges,e);
 137 }
 138
 139
 140 /*-----------------------------------------*/
 141 /* Edge functions */
 142
 143 static Edge edge_new(Node n1, Node n2)
 144 {
 145   Edge new;
 146   assert(new = (Edge)calloc(1,sizeof(struct edge)));
 147   new->node1=n1;
 148   new->node2=n2;
 149   new->angle1=atan2(new->node2->y - new->node1->y, new->node2->x - new->node1->x);
 150   if (new->angle1 < 0) new->angle1+=6.28;
 151
 152   new->angle2=atan2(new->node1->y - new->node2->y, new->node1->x - new->node2->x);
 153   if (new->angle2 < 0) new->angle2+=6.28;
 154   return new;
 155 }
 156
 157 static void edge_del(void *e) /* not Edge * because the function is passed to array_del */
 158 {
 159   free(e);
 160 }
 161
 162 #if 0
 163 static void edge_to_s(Edge e, FILE *f)
 164 {
 165   fprintf(f,"Edge: (%g, %g), (%g, %g) angles: %g, %g\n",
 166           e->node1->x, e->node1->y, e->node2->x, e->node2->y,
 167           e->angle1, e->angle2);
 168 }
 169 #endif
 170
 171 static void edge_draw(Edge e)
 172 {
 173   XDrawLine(dpy,window,gc_graph, e->node1->x, e->node1->y, e->node2->x, e->node2->y);
 174 }
 175
 176 static double edge_angle(Edge e, Node n)
 177 {
 178   /* returns the angle of the edge at Node n */
 179   assert(n==e->node1 || n==e->node2);
 180   if (n==e->node1) return e->angle1; else return e->angle2;
 181 }
 182
 183 static Node edge_other_node(Edge e, Node n)
 184 {
 185   assert(n==e->node1 || n==e->node2);
 186   if (n==e->node1) return e->node2; else return e->node1;
 187 }
 188
 189 static double edge_angle_to(Edge e, Edge e2, Node node, Direction direction)
 190 {
 191   /* returns the absolute angle from this edge to "edge2" around
 192      "node" following "direction" */
 193   double a;
 194
 195   if (direction==CLOCKWISE)
 196     a=edge_angle(e,node) - edge_angle(e2,node);
 197   else
 198     a=edge_angle(e2,node) - edge_angle(e,node);
 199
 200   if (a<0) return a+2*M_PI; else return a;
 201 }
 202
 203 /*-----------------------------------------*/
 204
 205 typedef struct graph {
 206   Array nodes;
 207   Array edges;
 208 } *Graph;
 209
 210 static Graph graph_new(void)
 211 {
 212   Graph new;
 213   assert(new = (Graph)calloc(1,sizeof(struct graph)));
 214   new->nodes = array_new(100);
 215   new->edges = array_new(100);
 216   return new;
 217 }
 218
 219 static void graph_del(Graph g)
 220 {
 221   array_del(g->nodes, &node_del);
 222   array_del(g->edges, &edge_del);
 223   free(g);
 224 }
 225
 226
 227 static void graph_add_node(Graph g, Node n)
 228 {
 229   array_add_element(g->nodes, n);
 230 }
 231
 232 static void graph_add_edge(Graph g, Edge e)
 233 {
 234   array_add_element(g->edges, e);
 235
 236   /* for each node n of e, add n to pointer e */
 237   node_add_edge(e->node1, e);
 238   node_add_edge(e->node2, e);
 239 }
 240
 241 static Edge graph_next_edge_around(Graph g, Node n, Edge e, Direction direction)
 242 {
 243   /* return the next edge after e around node n clockwise */
 244   double angle, minangle=20;
 245   Edge next_edge = e, edge;
 246   int i;
 247
 248   for (i=0;i<n->edges->nb_elements;i++) {
 249     edge=n->edges->elements[i];
 250     if (edge != e) {
 251       angle = edge_angle_to(e,edge,n,direction);
 252       if (angle < minangle) {
 253         next_edge=edge;
 254         minangle=angle;
 255       }
 256     }
 257   }
 258   return next_edge;
 259 }
 260
 261 #if 0
 262 static void graph_to_s(Graph g, FILE *f)
 263 {
 264   int i;
 265   for (i=0;i<g->nodes->nb_elements;i++)
 266     node_to_s(g->nodes->elements[i],f);
 267   for (i=0;i<g->edges->nb_elements;i++)
 268     edge_to_s(g->edges->elements[i],f);
 269 }
 270 #endif
 271
 272 static void graph_draw(Graph g)
 273 {
 274   int i;
 275
 276   for (i=0;i<g->nodes->nb_elements;i++)
 277     node_draw(g->nodes->elements[i]);
 278   for (i=0;i<g->edges->nb_elements;i++)
 279     edge_draw(g->edges->elements[i]);
 280   XSync(dpy,False);
 281 }
 282
 283 static void graph_rotate(Graph g, double angle, int cx, int cy)
 284 {
 285   /* rotate all the nodes of the graph around the centre */
 286   int i;
 287   float c=cos(angle),s=sin(angle),x,y;
 288   Node n;
 289   for (i=0;i<g->nodes->nb_elements;i++) {
 290     n=g->nodes->elements[i];
 291     x=n->x; y=n->y;
 292     n->x = (x-cx)*c-(y-cy)*s + cx;
 293     n->y = (x-cx)*s+(y-cy)*c + cy;
 294   }
 295 }
 296
 297
 298 /*---------------------------*/
 299
 300 static Graph make_polar_graph(int xmin, int ymin, int width, int height,
 301                        int nbp, /* number of points on each orbit */
 302                        int nbo /* number of orbits */)
 303      /* make a simple grid graph, with edges present or absent randomly */
 304 {
 305   int cx = width/2+xmin, cy=height/2+ymin; /* centre */
 306   int os = (width<height?width:height)/(2*nbo); /* orbit height */
 307   Graph g;
 308   Node *grid;
 309   int o,p;
 310
 311   /* generate nodes */
 312   assert(grid=(Node*)calloc(1+nbp*nbo,sizeof(Node)));
 313   assert(g=graph_new());
 314
 315   graph_add_node(g, grid[0]=node_new((double)cx,(double)cy));
 316
 317   for (o=0;o<nbo;o++)
 318     for (p=0;p<nbp;p++)
 319       graph_add_node(g,
 320                      grid[1+o*nbp+p]=node_new(cx+(o+1)*os*sin(p*2*M_PI/nbp),
 321                                               cy+(o+1)*os*cos(p*2*M_PI/nbp)));
 322
 323
 324   /* generate edges */
 325   for (o=0;o<nbo;o++)
 326     for (p=0;p<nbp;p++) {
 327       if (o==0) /* link first orbit nodes with centre */
 328         graph_add_edge(g,edge_new(grid[1+o*nbp+p],grid[0]));
 329       else /* liink orbit nodes with lower orbit */
 330         graph_add_edge(g,edge_new(grid[1+o*nbp+p],grid[1+(o-1)*nbp+p]));
 331       /* link along orbit */
 332       graph_add_edge(g,edge_new(grid[1+o*nbp+p],
 333                                 grid[1+o*nbp+(p+1)%nbp]));
 334     }
 335
 336   free(grid);
 337   return g;
 338 }
 339
 340
 341 static Graph make_grid_graph(int xmin, int ymin, int width, int height, int step)
 342      /* make a simple grid graph */
 343 {
 344   Graph g;
 345   int row,col,x,y;
 346   int size=(width<height?height:width);
 347
 348   /* empirically, it seems there are 2 curves only if both
 349      nbcol and nbrow are even, so we round them to even */
 350   int nbcol=(2+size/step)/2*2, nbrow=(2+size/step)/2*2;
 351
 352   Node *grid;
 353   assert(grid=(Node*)calloc(nbrow*nbcol,sizeof(Node)));
 354   assert(g=graph_new());
 355
 356
 357   /* adjust xmin and xmax so that the grid is centered */
 358   xmin+=(width-(nbcol-1)*step)/2;
 359   ymin+=(height-(nbrow-1)*step)/2;
 360
 361   /* create node grid */
 362   for (row=0;row<nbrow;row++)
 363     for (col=0;col<nbcol;col++) {
 364       x=col*step+xmin;
 365       y=row*step+ymin;
 366       grid[row+col*nbrow]=node_new((double)x, (double)y);
 367       graph_add_node(g, grid[row+col*nbrow]);
 368     }
 369
 370   /* create edges */
 371   for (row=0;row<nbrow;row++)
 372     for (col=0;col<nbcol;col++) {
 373       if (col!=nbcol-1)
 374         graph_add_edge(g,edge_new(grid[row+col*nbrow],
 375                                   grid[row+(col+1)*nbrow]));
 376       if (row!=nbrow-1)
 377         graph_add_edge(g,edge_new(grid[row+col*nbrow],grid[row+1+col*nbrow]));
 378       if (col!=nbcol-1 && row!=nbrow-1) {
 379           graph_add_edge(g,edge_new(grid[row+col*nbrow],
 380                                     grid[row+1+(col+1)*nbrow]));
 381           graph_add_edge(g,edge_new(grid[row+1+col*nbrow],
 382                                     grid[row+(col+1)*nbrow]));
 383       }
 384     }
 385
 386   free(grid);
 387
 388   return g;
 389 }
 390
 391
 392 static Graph make_triangle_graph(int xmin, int ymin, int width, int height, int edge_size)
 393 {
 394   Graph g;
 395   Node *grid;
 396   int row,col;
 397   double L=(width<height?width:height)/2.0; /* circumradius of the triangle */
 398   double cx=xmin+width/2.0, cy=ymin+height/2.0; /* centre of the triangle */
 399   double p2x=cx-L*SQRT_3/2.0, p2y=cy+L/2.0; /* p2 is the bottom left vertex */
 400   double x,y;
 401   int nsteps=3*L/(SQRT_3*edge_size);
 402
 403   assert(grid=(Node*)calloc((nsteps+1)*(nsteps+1),sizeof(Node)));
 404   assert(g=graph_new());
 405
 406   /* create node grid */
 407   for (row=0;row<=nsteps;row++)
 408     for (col=0;col<=nsteps;col++)
 409       if (row+col<=nsteps) {
 410         x=p2x+col*L*SQRT_3/nsteps + row*L*SQRT_3/(2*nsteps);
 411         y=p2y-row*3*L/(2*nsteps);
 412         grid[col+row*(nsteps+1)]=node_new((double)x, (double)y);
 413         graph_add_node(g, grid[col+row*(nsteps+1)]);
 414       }
 415
 416   /* create edges */
 417   for (row=0;row<nsteps;row++)
 418     for (col=0;col<nsteps;col++)
 419       if (row+col<nsteps) {
 420           /* horizontal edges */
 421           graph_add_edge(g,edge_new(grid[row+col*(nsteps+1)],grid[row+(col+1)*(nsteps+1)]));
 422           /* vertical edges */
 423           graph_add_edge(g,edge_new(grid[row+col*(nsteps+1)],grid[row+1+col*(nsteps+1)]));
 424           /* diagonal edges */
 425           graph_add_edge(g,edge_new(grid[row+1+col*(nsteps+1)],grid[row+(col+1)*(nsteps+1)]));
 426       }
 427
 428   free(grid);
 429   return g;
 430
 431 }
 432
 433
 434 static Graph make_kennicott_graph(int xmin, int ymin, int width, int height, int step,
 435                            int cluster_size)
 436      /* make a graph inspired by one of the motifs from the Kennicott bible */
 437      /* square grid of clusters of the shape  /|\
 438       *                                       ---
 439       *                                       \|/
 440       * cluster_size is the length of an edge of a cluster
 441       */
 442 {
 443   Graph g;
 444   int row,col,x,y;
 445   int size=width<height?height:width;
 446   int nbcol=(1+size/step)/2*2, nbrow=(1+size/step)/2*2;
 447   Node *grid;
 448
 449   /* there are 5 nodes by for each cluster */
 450   assert(grid=(Node*)calloc(5*nbrow*nbcol,sizeof(Node)));
 451   assert(g=graph_new());
 452
 453   /* adjust xmin and xmax so that the grid is centered */
 454   xmin+=(width-(nbcol-1)*step)/2;
 455   ymin+=(height-(nbrow-1)*step)/2;
 456
 457   /* create node grid */
 458   for (row=0;row<nbrow;row++)
 459     for (col=0;col<nbcol;col++) {
 460       int ci=5*(row+col*nbrow);
 461       x=col*step+xmin;
 462       y=row*step+ymin;
 463
 464       /* create a cluster centred on x,y */
 465       grid[ci  ]=node_new((double)x, (double)y);
 466       grid[ci+1]=node_new((double)(x+cluster_size), (double)y);
 467       grid[ci+2]=node_new((double)x, (double)(y-cluster_size));
 468       grid[ci+3]=node_new((double)(x-cluster_size), (double)y);
 469       grid[ci+4]=node_new((double)x, (double)(y+cluster_size));
 470
 471       graph_add_node(g, grid[ci]);
 472       graph_add_node(g, grid[ci+1]);
 473       graph_add_node(g, grid[ci+2]);
 474       graph_add_node(g, grid[ci+3]);
 475       graph_add_node(g, grid[ci+4]);
 476
 477       /* internal edges */
 478       graph_add_edge(g,edge_new(grid[ci], grid[ci+1]));
 479       graph_add_edge(g,edge_new(grid[ci], grid[ci+2]));
 480       graph_add_edge(g,edge_new(grid[ci], grid[ci+3]));
 481       graph_add_edge(g,edge_new(grid[ci], grid[ci+4]));
 482       graph_add_edge(g,edge_new(grid[ci+1], grid[ci+2]));
 483       graph_add_edge(g,edge_new(grid[ci+2], grid[ci+3]));
 484       graph_add_edge(g,edge_new(grid[ci+3], grid[ci+4]));
 485       graph_add_edge(g,edge_new(grid[ci+4], grid[ci+1]));
 486
 487     }
 488
 489   /* create inter-cluster edges */
 490   for (row=0;row<nbrow;row++)
 491     for (col=0;col<nbcol;col++) {
 492       if (col!=nbcol-1)
 493         /* horizontal edge from edge 1 of cluster (row, col) to edge 3
 494          * of cluster (row,col+1) */
 495         graph_add_edge(g,edge_new(grid[5*(row+col*nbrow)+1],grid[5*(row+(col+1)*nbrow)+3]));
 496       if (row!=nbrow-1)
 497         /* vertical edge from edge 4 of cluster (row, col) to edge 2
 498          * of cluster (row+1,col) */
 499         graph_add_edge(g,edge_new(grid[5*(row+col*nbrow)+4],
 500                                   grid[5*(row+1+col*nbrow)+2]));
 501     }
 502   free(grid);
 503   return g;
 504 }
 505
 506 /*---------------------------*/
 507 typedef struct spline_segment {
 508   double x1,y1,x2,y2,x3,y3,x4,y4;
 509 } *SplineSegment;
 510
 511 typedef struct spline {
 512   Array segments; /* array of SplineSegment */
 513   int color;
 514 } *Spline;
 515
 516 static Spline spline_new(int color)
 517 {
 518   Spline new=(Spline)calloc(1,sizeof(struct spline));
 519   new->segments=array_new(30);
 520   new->color=color;
 521   return new;
 522 }
 523
 524 static void spline_del(void *s)
 525 {
 526   array_del(((Spline)s)->segments,&free);
 527   free(s);
 528 }
 529
 530 static void spline_add_segment(Spline s,
 531                         double x1, double y1, double x2, double y2,
 532                         double x3, double y3, double x4, double y4)
 533 {
 534   SplineSegment ss=(SplineSegment)calloc(1,sizeof(struct spline_segment));
 535   ss->x1=x1;  ss->x2=x2;  ss->x3=x3;  ss->x4=x4;
 536   ss->y1=y1;  ss->y2=y2;  ss->y3=y3;  ss->y4=y4;
 537   array_add_element(s->segments,ss);
 538 }
 539
 540 #if 0
 541 static void spline_to_s(Spline s, FILE *f)
 542 {
 543   int i;
 544   SplineSegment ss;
 545   fprintf(f,"Spline: \n");
 546   for (i=0;i<s->segments->nb_elements;i++) {
 547     ss=s->segments->elements[i];
 548     fprintf(f," - segment %d: (%g, %g),(%g, %g),(%g, %g),(%g, %g)\n",
 549             i,ss->x1,ss->y1,ss->x2,ss->y2,ss->x3,ss->y3,ss->x4,ss->y4);
 550   }
 551 }
 552 #endif
 553
 554 static void spline_value_at(Spline s, double *x, double *y, double t, int *segment)
 555 {
 556   int si;
 557   double tt;
 558   SplineSegment ss;
 559   si = floor(t*s->segments->nb_elements);
 560   tt = t*s->segments->nb_elements - si;
 561   assert(tt>=0 && tt<1);
 562   ss=s->segments->elements[si];
 563
 564   *x = ss->x1*(1-tt)*(1-tt)*(1-tt)+3*ss->x2*tt*(1-tt)*(1-tt)+3*ss->x3*tt*tt*(1-tt)+ss->x4*tt*tt*tt;
 565   *y = ss->y1*(1-tt)*(1-tt)*(1-tt)+3*ss->y2*tt*(1-tt)*(1-tt)+3*ss->y3*tt*tt*(1-tt)+ss->y4*tt*tt*tt;
 566
 567   *segment=si;
 568 }
 569
 570 /*---------------------------*/
 571 typedef struct edge_couple {
 572   int **array;
 573   int size;
 574 } *EdgeCouple;
 575
 576 static EdgeCouple edge_couple_new(int nb_edges) {
 577   int i;
 578   EdgeCouple new = (EdgeCouple)calloc(1,sizeof(struct edge_couple));
 579   new->array = (int **)calloc(nb_edges, sizeof(int*));
 580   new->size = nb_edges;
 581
 582   for (i=0;i<nb_edges;i++) {
 583     new->array[i]=(int *)calloc(2,sizeof(int));
 584     new->array[i][CLOCKWISE]=0;
 585     new->array[i][ANTICLOCKWISE]=0;
 586   }
 587   return new;
 588 }
 589
 590 static void edge_couple_del(EdgeCouple e)
 591 {
 592   int i;
 593   for (i=0;i<e->size;i++) free(e->array[i]);
 594   free(e->array);
 595   free(e);
 596 }
 597
 598 /*---------------------------*/
 599
 600 typedef struct pattern {
 601   double shape1, shape2;
 602   EdgeCouple ec;
 603   Graph graph;
 604   Array splines;
 605   int ncolors;
 606 } *Pattern;
 607
 608 static Pattern pattern_new(Graph g, int ncolors, double shape1, double shape2)
 609 {
 610   Pattern new;
 611   assert(new=(Pattern)calloc(1,sizeof(struct pattern)));
 612   new->shape1=shape1;
 613   new->shape2=shape2;
 614   new->graph=g;
 615   new->ec=edge_couple_new(g->edges->nb_elements);
 616   new->splines=array_new(10);
 617   new->ncolors=ncolors;
 618   return new;
 619 }
 620
 621 static void pattern_del(Pattern p)
 622 {
 623   edge_couple_del(p->ec);
 624   array_del(p->splines,&spline_del);
 625   free(p);
 626 }
 627
 628 static void pattern_edge_couple_set(Pattern p, Edge e, Direction d, int value)
 629 {
 630   int i;
 631   for (i=0;i<p->graph->edges->nb_elements;i++)
 632     if (p->graph->edges->elements[i]==e) {
 633       p->ec->array[i][d]=value;
 634       return;
 635     }
 636 }
 637
 638 static void pattern_draw_spline_direction(Pattern p, Spline s,
 639                                    Node node, Edge edge1, Edge edge2,
 640                                    Direction direction)
 641 {
 642   double x1=(edge1->node1->x+edge1->node2->x)/2.0;
 643   double y1=(edge1->node1->y+edge1->node2->y)/2.0;
 644
 645   /* P2 (x2,y2) is the middle point of edge1 */
 646   double x4=(edge2->node1->x+edge2->node2->x)/2.0;
 647   double y4=(edge2->node1->y+edge2->node2->y)/2.0;
 648
 649   double alpha=edge_angle_to(edge1,edge2,node,direction)*p->shape1;
 650   double beta=p->shape2;
 651
 652   double i1x,i1y,i2x,i2y,x2,y2,x3,y3;
 653
 654   if (direction == ANTICLOCKWISE) {
 655     /* I1 must stick out to the left of NP1 and I2 to the right of NP4 */
 656     i1x =  alpha*(node->y-y1)+x1;
 657     i1y = -alpha*(node->x-x1)+y1;
 658     i2x = -alpha*(node->y-y4)+x4;
 659     i2y =  alpha*(node->x-x4)+y4;
 660     x2 =  beta*(y1-i1y) + i1x;
 661     y2 = -beta*(x1-i1x) + i1y;
 662     x3 = -beta*(y4-i2y) + i2x;
 663     y3 =  beta*(x4-i2x) + i2y;
 664   }
 665   else {
 666     /* I1 must stick out to the left of NP1 and I2 to the right of NP4 */
 667     i1x = -alpha*(node->y-y1)+x1;
 668     i1y =  alpha*(node->x-x1)+y1;
 669     i2x =  alpha*(node->y-y4)+x4;
 670     i2y = -alpha*(node->x-x4)+y4;
 671     x2 = -beta*(y1-i1y) + i1x;
 672     y2 =  beta*(x1-i1x) + i1y;
 673     x3 =  beta*(y4-i2y) + i2x;
 674     y3 = -beta*(x4-i2x) + i2y;
 675   }
 676
 677   spline_add_segment(s,x1,y1,x2,y2,x3,y3,x4,y4);
 678 }
 679
 680 static int pattern_next_unfilled_couple(Pattern p, Edge *e, Direction *d)
 681 {
 682   int i;
 683   for (i=0;i<p->ec->size;i++) {
 684     if (p->ec->array[i][CLOCKWISE]==0) {
 685       *e=p->graph->edges->elements[i];
 686       *d=CLOCKWISE;
 687       return 1;
 688     }
 689     else if (p->ec->array[i][ANTICLOCKWISE]==0) {
 690       *e=p->graph->edges->elements[i];
 691       *d=ANTICLOCKWISE;
 692       return 1;
 693     }
 694   }
 695   return 0;
 696 }
 697
 698 static void pattern_make_curves(Pattern p)
 699 {
 700   int i;
 701   Edge current_edge, first_edge, next_edge;
 702   Node current_node, first_node;
 703   Direction current_direction, first_direction;
 704   Spline s;
 705
 706   i=0;
 707   while (pattern_next_unfilled_couple(p, &first_edge, &first_direction)) {
 708     /* start a new loop */
 709     s=spline_new(random()%(p->ncolors-2)+2);
 710     array_add_element(p->splines, s);
 711
 712     current_edge=first_edge;
 713     current_node=first_node=current_edge->node1;
 714     current_direction=first_direction;
 715
 716     do {
 717       pattern_edge_couple_set(p, current_edge, current_direction, 1);
 718       next_edge = graph_next_edge_around(p->graph,current_node,current_edge,current_direction);
 719
 720       /* add the spline segment to the spline */
 721       pattern_draw_spline_direction(p,s,current_node,
 722                                     current_edge,next_edge,current_direction);
 723
 724       /* cross the edge */
 725       current_edge = next_edge;
 726       current_node = edge_other_node(next_edge, current_node);
 727       current_direction=1-current_direction;
 728
 729     } while (current_node!=first_node || current_edge!=first_edge || current_direction!=first_direction);
 730
 731     if (s->segments->nb_elements==2) /* spline is just one point: remove it */
 732       p->splines->elements[p->splines->nb_elements-1]=NULL;
 733
 734   }
 735 }
 736
 737 static void pattern_animate(Pattern p, unsigned long delay)
 738 {
 739   double t,t2;
 740   double x,y,x2,y2,x3,y3,x4,y4;
 741   int i,segment,unused;
 742   int ticks = 0;
 743   double step=0.0001; /* TODO: set the step (or the delay) as a
 744                         * function of the spline length, so that
 745                         * drawing speed is constant
 746                         */
 747   Spline s;
 748
 749   XSetLineAttributes(dpy,gc,params.curve_width,LineSolid,CapRound,JoinRound);
 750   XSetLineAttributes(dpy,shadow_gc,params.shadow_width,LineSolid,CapRound,JoinRound);
 751
 752   for (t=0.0;t<1;t+=step) {
 753     for (i=0;i<p->splines->nb_elements;i++)
 754       if ((s=p->splines->elements[i])) { /* skip if one-point spline */
 755         spline_value_at(s, &x, &y, fmod(t,1.0),&segment);
 756         spline_value_at(s, &x2, &y2, fmod(t+step,1.0),&unused);
 757
 758         /* look ahead for the shadow segment */
 759         t2=t+step;
 760         if (t2<=1.0) {
 761           spline_value_at(s, &x3, &y3, fmod(t2,1.0),&unused);
 762           while (t2+step<1.0 && (x3-x2)*(x3-x2)+(y3-y2)*(y3-y2) < params.shadow_width*params.shadow_width) {
 763             t2+=step;
 764             spline_value_at(s, &x3, &y3, fmod(t2,1.0),&unused);
 765           }
 766
 767           spline_value_at(s, &x4, &y4, fmod(t2+step,1.0),&unused);
 768
 769           /* draw shadow line */
 770           XDrawLine(dpy,window,shadow_gc,
 771                     (int)rint(x3),(int)rint(y3),
 772                     (int)rint(x4),(int)rint(y4));
 773         }
 774         /* draw line segment */
 775         if (p->splines->nb_elements==1)
 776           XSetForeground(dpy, gc, colors[segment%(p->ncolors-3)+2].pixel);
 777         else
 778           XSetForeground(dpy, gc, colors[s->color].pixel);
 779         XDrawLine(dpy,window,gc,
 780                   (int)rint(x),(int)rint(y),
 781                   (int)rint(x2),(int)rint(y2));
 782       }
 783
 784     if (++ticks > 100) {
 785       XSync(dpy,False);
 786       usleep(delay);
 787       screenhack_handle_events (dpy);
 788       ticks = 0;
 789     }
 790   }
 791
 792   /* at the end we redraw back to remove shadow spillage */
 793   for (i=0;i<p->splines->nb_elements;i++) {
 794     if ((s=p->splines->elements[i])) {
 795       double offset=step;
 796       XSetForeground(dpy, gc, colors[s->color].pixel);
 797       spline_value_at(s, &x, &y, fmod(t,1.0),&unused);
 798
 799       spline_value_at(s, &x2, &y2, fmod(t-offset,1.0),&unused);
 800
 801       while ((x2-x)*(x2-x)+(y2-y)*(y2-y) < params.shadow_width*params.shadow_width) {
 802         offset+=step;
 803         spline_value_at(s, &x2, &y2, fmod(t-offset,1.0),&unused);
 804       }
 805
 806       XDrawLine(dpy,window,gc, (int)rint(x),(int)rint(y), (int)rint(x2),(int)rint(y2));
 807     }
 808   }
 809   XSync(dpy,False);
 810 }
 811
 812 /*======================================================================*/
 813
 814 char *progclass = "Celtic";
 815
 816 char *defaults[] = {
 817     ".background: black",
 818     ".foreground: grey20",
 819     "*ncolors: 20",
 820     "*delay: 10000",
 821     "*delay2: 5",
 822     "*showGraph: False",
 823     0
 824 };
 825
 826 XrmOptionDescRec options[] = {
 827     {"-background", ".background", XrmoptionSepArg, 0},
 828     {"-foreground", ".foreground", XrmoptionSepArg, 0},
 829     {"-ncolors", ".ncolors", XrmoptionSepArg, 0},
 830     {"-delay", ".delay", XrmoptionSepArg, 0},
 831     {"-delay2", ".delay2", XrmoptionSepArg, 0},
 832     {"-graph", ".showGraph", XrmoptionNoArg, "True"},
 833     {0, 0, 0, 0}
 834 };
 835
 836 #if 0
 837 static void params_to_s(FILE *f)
 838 {
 839   switch (params.type) {
 840   case polar: fprintf(f,"type: polar\n");
 841     fprintf(f,"nb_orbits: %ld\n",params.nb_orbits);
 842     fprintf(f,"nb_nodes_per_orbit: %ld\n",params.nb_nodes_per_orbit);
 843     break;
 844   case grid: fprintf(f,"type: grid\n");
 845     fprintf(f,"edge_size: %ld\n",params.edge_size);
 846     break;
 847   case triangle: fprintf(f,"type: triangle\n");
 848     fprintf(f,"edge_size: %ld\n",params.edge_size);
 849     break;
 850   case kennicott:
 851     fprintf(f,"type: kennicott\n");
 852     fprintf(f,"edge_size: %ld\n",params.edge_size);
 853     fprintf(f,"cluster_size: %ld\n",params.cluster_size);
 854     break;
 855   }
 856
 857   fprintf(f,"curve width: %ld\n",params.curve_width);
 858   fprintf(f,"shadow width: %ld\n",params.shadow_width);
 859   fprintf(f,"shape1: %g\n",params.shape1);
 860   fprintf(f,"shape2: %g\n",params.shape2);
 861   fprintf(f,"margin: %ld\n",params.margin);
 862   fprintf(f,"angle: %g\n",params.angle);
 863   fprintf(f,"delay: %ld\n",params.delay);
 864 }
 865 #endif
 866
 867 #if 0
 868 static void colormap_to_s(int ncolors, XColor *colors)
 869 {
 870   int i;
 871   printf("-- colormap (%d colors):\n",ncolors);
 872   for (i=0;i<ncolors;i++)
 873     printf("%d: %d %d %d\n", i, colors[i].red, colors[i].green, colors[i].blue);
 874   printf("----\n");
 875 }
 876 #endif
 877
 878
 879
 880 void screenhack(Display * d, Window w)
 881 {
 882   XGCValues gcv;
 883   XWindowAttributes xgwa;
 884   Bool showGraph=get_boolean_resource ("showGraph", "Boolean");
 885   Pattern p;
 886   Graph g;
 887
 888   dpy=d; window=w;
 889   ncolors = get_integer_resource ("ncolors", "Integer");
 890
 891
 892   XGetWindowAttributes (dpy, window, &xgwa);
 893   assert(colors = (XColor *) calloc (ncolors,sizeof(XColor)));
 894
 895   if (get_boolean_resource("mono", "Boolean"))
 896     {
 897     MONO:
 898       ncolors = 1;
 899       colors[0].pixel = get_pixel_resource("foreground", "Foreground",
 900                                            dpy, xgwa.colormap);
 901     }
 902   else
 903     {
 904 #if 0
 905       make_random_colormap (dpy, xgwa.visual, xgwa.colormap,
 906                             colors, &ncolors, True, True, 0, True);
 907 #else
 908       make_smooth_colormap (dpy, xgwa.visual, xgwa.colormap,
 909                             colors, &ncolors, True, 0, True);
 910 #endif
 911       if (ncolors < 2)
 912         goto MONO;
 913       else {
 914         colors[0].pixel = get_pixel_resource("foreground", "Foreground",
 915                                              dpy, xgwa.colormap);
 916         colors[1].pixel = get_pixel_resource("background", "Background",
 917                                              dpy, xgwa.colormap);
 918       }
 919     }
 920
 921   /* graphic context for curves */
 922   gcv.foreground = colors[0].pixel;
 923   gcv.background = colors[1].pixel;
 924   gcv.line_width = params.curve_width;
 925   gcv.cap_style=CapRound;
 926   gc = XCreateGC (dpy, window, GCForeground|GCBackground|GCLineWidth|GCCapStyle, &gcv);
 927
 928   /* graphic context for graphs */
 929   gcv.foreground = colors[0].pixel;
 930   gcv.background = colors[1].pixel;
 931   gc_graph = XCreateGC (dpy, window, GCForeground|GCBackground, &gcv);
 932
 933   /* graphic context for shadows */
 934   gcv.foreground = colors[1].pixel;
 935   gcv.line_width = params.shadow_width;
 936   gcv.cap_style=CapRound;
 937   shadow_gc = XCreateGC(dpy, window, GCForeground|GCLineWidth|GCCapStyle, &gcv);
 938
 939   /*=======================================================*/
 940
 941   for (;;) {
 942     params.curve_width=random()%5+4;
 943     params.shadow_width=params.curve_width+4;
 944     params.shape1=(15+random()%15)/10.0 -1.0;
 945     params.shape2=(15+random()%15)/10.0 -1.0;
 946     params.edge_size=10*(random()%5)+20;
 947     params.delay=get_integer_resource("delay", "Delay");
 948     params.angle=random()%360*2*M_PI/360;
 949     params.margin=(random()%8)*100-600;
 950
 951     switch (random()%4) {
 952     case 0:
 953       params.type=grid;
 954       params.shape1=(random()%1*2-1.0)*(random()%10+3)/10.0;
 955       params.shape2=(random()%1*2-1.0)*(random()%10+3)/10.0;
 956       params.edge_size=10*(random()%5)+50;
 957       break;
 958     case 1:
 959       params.type=kennicott;
 960       params.shape1=(random()%20)/10.0 -1.0;
 961       params.shape2=(random()%20)/10.0 -1.0;
 962       params.edge_size=10*(random()%3)+70;
 963       params.cluster_size=params.edge_size/(3.0+random()%10)-1;
 964       break;
 965     case 2:
 966       params.type=triangle;
 967       params.edge_size=10*(random()%5)+60;
 968       params.margin=(random()%10)*100-900;
 969       break;
 970     case 3:
 971       params.type=polar;
 972       params.nb_orbits=2+random()%10;
 973       params.nb_nodes_per_orbit=4+random()%10;
 974       break;
 975     }
 976
 977
 978 /*     params.type= polar; */
 979 /*   params.nb_orbits= 5; */
 980 /*   params.nb_nodes_per_orbit= 19; */
 981 /*   params.curve_width= 4; */
 982 /*   params.shadow_width= 8; */
 983 /*   params.shape1= 0.5; */
 984 /*   params.shape2= 1.3; */
 985 /*   params.margin= 30; */
 986 /*   params.angle= 5.21853; */
 987 /*   params.delay= 10000; */
 988
 989
 990 /*     params_to_s(stdout); */
 991
 992     /*=======================================================*/
 993
 994
 995     switch (params.type) {
 996     case grid:
 997       g=make_grid_graph(params.margin,params.margin,
 998                         xgwa.width-2*params.margin,
 999                         xgwa.height-2*params.margin,
1000                         params.edge_size);
1001       break;
1002     case kennicott:
1003       g=make_kennicott_graph(params.margin,params.margin,
1004                              xgwa.width-2*params.margin,
1005                              xgwa.height-2*params.margin,
1006                              params.edge_size,
1007                              params.cluster_size);
1008       break;
1009     case triangle:
1010       g=make_triangle_graph(params.margin,params.margin,
1011                             xgwa.width-2*params.margin,
1012                             xgwa.height-2*params.margin,
1013                             params.edge_size);
1014       break;
1015     case polar:
1016       g=make_polar_graph(params.margin,params.margin,
1017                          xgwa.width-2*params.margin,
1018                          xgwa.height-2*params.margin,
1019                          params.nb_nodes_per_orbit,
1020                          params.nb_orbits);
1021       break;
1022     default:
1023       g=make_grid_graph(params.margin,params.margin,
1024                         xgwa.width-2*params.margin,
1025                         xgwa.height-2*params.margin,
1026                         params.edge_size);
1027       break;
1028     }
1029
1030     graph_rotate(g,params.angle,xgwa.width/2,xgwa.height/2);
1031
1032     if (showGraph)
1033       graph_draw(g);
1034
1035     p=pattern_new(g,ncolors, params.shape1, params.shape2);
1036     pattern_make_curves(p);
1037     pattern_animate(p,params.delay);
1038
1039     {
1040       int d2 = get_integer_resource("delay2", "Delay2");
1041       int i;
1042       for (i = 0; i < d2; i++) {
1043         XSync (dpy, False);
1044         screenhack_handle_events (dpy);
1045         sleep(1);
1046       }
1047     }
1048
1049     pattern_del(p);
1050     graph_del(g);
1051
1052    erase_full_window(dpy,window);
1053
1054    /* recolor each time */
1055    ncolors = get_integer_resource ("ncolors", "Integer");
1056    if (ncolors > 2)
1057      make_smooth_colormap (dpy, xgwa.visual, xgwa.colormap,
1058                            colors, &ncolors, True, 0, True);
1059   }
1060 }