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

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