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