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