http://www.jwz.org/xscreensaver/xscreensaver-5.10.tar.gz
[xscreensaver] / 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   int i;
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   i=0;
728   while (pattern_next_unfilled_couple(p, &first_edge, &first_direction)) {
729     /* start a new loop */
730     s=spline_new(random()%(p->ncolors-2)+2);
731     array_add_element(p->splines, s);
732
733     current_edge=first_edge;
734     current_node=first_node=current_edge->node1;
735     current_direction=first_direction;
736
737     do {
738       pattern_edge_couple_set(p, current_edge, current_direction, 1);
739       next_edge = graph_next_edge_around(p->graph,current_node,current_edge,current_direction);
740
741       /* add the spline segment to the spline */
742       pattern_draw_spline_direction(p,s,current_node,
743                                     current_edge,next_edge,current_direction);
744       
745       /* cross the edge */
746       current_edge = next_edge;
747       current_node = edge_other_node(next_edge, current_node);
748       current_direction=1-current_direction;
749
750     } while (current_node!=first_node || current_edge!=first_edge || current_direction!=first_direction);
751
752     if (s->segments->nb_elements==2) /* spline is just one point: remove it */
753       p->splines->elements[p->splines->nb_elements-1]=NULL;
754       
755   }
756 }
757
758 static void pattern_animate(struct state *st)
759 {
760   Pattern p = st->pattern;
761   double t = st->t;
762   double t2;
763   double x,y,x2,y2,x3,y3,x4,y4;
764   int i,segment,unused;
765   int ticks;
766   double step=0.0001; /* TODO: set the step (or the delay) as a
767                         * function of the spline length, so that
768                         * drawing speed is constant
769                         */
770   Spline s;
771
772   XSetLineAttributes(st->dpy,st->gc,st->params.curve_width,LineSolid,CapRound,JoinRound);
773   XSetLineAttributes(st->dpy,st->shadow_gc,st->params.shadow_width,LineSolid,CapRound,JoinRound);
774
775   for (ticks=0;ticks<100 && t<1;ticks++) {
776     for (i=0;i<p->splines->nb_elements;i++) 
777       if ((s=p->splines->elements[i])) { /* skip if one-point spline */
778         spline_value_at(s, &x, &y, fmod(t,1.0),&segment);
779         spline_value_at(s, &x2, &y2, fmod(t+step,1.0),&unused);
780         
781         /* look ahead for the shadow segment */
782         t2=t+step;
783         if (t2<=1.0) {
784           spline_value_at(s, &x3, &y3, fmod(t2,1.0),&unused);
785           while (t2+step<1.0 && (x3-x2)*(x3-x2)+(y3-y2)*(y3-y2) < st->params.shadow_width*st->params.shadow_width) {
786             t2+=step;
787             spline_value_at(s, &x3, &y3, fmod(t2,1.0),&unused);
788           }
789           
790           spline_value_at(s, &x4, &y4, fmod(t2+step,1.0),&unused);
791           
792           /* draw shadow line */
793           XDrawLine(st->dpy,st->window,st->shadow_gc, 
794                     (int)rint(x3),(int)rint(y3), 
795                     (int)rint(x4),(int)rint(y4));
796         } 
797         /* draw line segment */
798         if (p->splines->nb_elements==1)
799           XSetForeground(st->dpy, st->gc, st->colors[segment%(p->ncolors-3)+2].pixel);
800         else
801           XSetForeground(st->dpy, st->gc, st->colors[s->color].pixel);
802         XDrawLine(st->dpy,st->window,st->gc,
803                   (int)rint(x),(int)rint(y),
804                   (int)rint(x2),(int)rint(y2));
805       }
806     t+=step;
807   }
808   st->t=t;
809
810   if (t>=1) {
811     st->reset=1;
812
813     /* at the end we redraw back to remove shadow spillage */
814     for (i=0;i<p->splines->nb_elements;i++) {
815       if ((s=p->splines->elements[i])) {
816         double offset=step;
817         XSetForeground(st->dpy, st->gc, st->colors[s->color].pixel);
818         spline_value_at(s, &x, &y, fmod(t,1.0),&unused);
819
820         spline_value_at(s, &x2, &y2, fmod(t-offset,1.0),&unused);
821       
822         while ((x2-x)*(x2-x)+(y2-y)*(y2-y) < st->params.shadow_width*st->params.shadow_width) {
823           offset+=step;
824           spline_value_at(s, &x2, &y2, fmod(t-offset,1.0),&unused);
825         }
826       
827         XDrawLine(st->dpy,st->window,st->gc, (int)rint(x),(int)rint(y), (int)rint(x2),(int)rint(y2));
828       }
829     }
830   }
831 }
832
833 /*======================================================================*/
834
835 static const char *celtic_defaults[] = {
836     ".background: black",
837     ".foreground: #333333",
838     "*fpsSolid: true",
839     "*ncolors: 20",
840     "*delay: 10000",
841     "*delay2: 5",
842     "*showGraph: False",
843     0
844 };
845
846 static XrmOptionDescRec celtic_options[] = {
847     {"-background", ".background", XrmoptionSepArg, 0},
848     {"-foreground", ".foreground", XrmoptionSepArg, 0},
849     {"-ncolors", ".ncolors", XrmoptionSepArg, 0},
850     {"-delay", ".delay", XrmoptionSepArg, 0},
851     {"-delay2", ".delay2", XrmoptionSepArg, 0},
852     {"-graph", ".showGraph", XrmoptionNoArg, "True"},
853     {0, 0, 0, 0}
854 };
855
856 #if 0
857 static void params_to_s(FILE *f)
858 {
859   switch (st->params.type) {
860   case polar: fprintf(f,"type: polar\n"); 
861     fprintf(f,"nb_orbits: %ld\n",st->params.nb_orbits);
862     fprintf(f,"nb_nodes_per_orbit: %ld\n",st->params.nb_nodes_per_orbit);
863     break;
864   case tgrid: fprintf(f,"type: grid\n"); 
865     fprintf(f,"edge_size: %ld\n",st->params.edge_size);
866     break;
867   case triangle: fprintf(f,"type: triangle\n"); 
868     fprintf(f,"edge_size: %ld\n",st->params.edge_size);
869     break;
870   case kennicott: 
871     fprintf(f,"type: kennicott\n"); 
872     fprintf(f,"edge_size: %ld\n",st->params.edge_size);
873     fprintf(f,"cluster_size: %ld\n",st->params.cluster_size);
874     break;
875   }
876
877   fprintf(f,"curve width: %ld\n",st->params.curve_width);
878   fprintf(f,"shadow width: %ld\n",st->params.shadow_width);
879   fprintf(f,"shape1: %g\n",st->params.shape1);
880   fprintf(f,"shape2: %g\n",st->params.shape2);
881   fprintf(f,"margin: %ld\n",st->params.margin);
882   fprintf(f,"angle: %g\n",st->params.angle);
883   fprintf(f,"delay: %ld\n",st->params.delay);
884 }
885 #endif
886
887 #if 0
888 static void colormap_to_s(int ncolors, XColor *colors)
889 {
890   int i;
891   printf("-- colormap (%d colors):\n",st->ncolors);
892   for (i=0;i<st->ncolors;i++)
893     printf("%d: %d %d %d\n", i, st->colors[i].red, st->colors[i].green, st->colors[i].blue);
894   printf("----\n");
895 }
896 #endif
897
898
899 static void *
900 celtic_init (Display *d_arg, Window w_arg)
901 {
902   struct state *st = (struct state *) calloc (1, sizeof(*st));
903   XGCValues gcv;
904
905   st->dpy=d_arg; st->window=w_arg;
906   st->showGraph=get_boolean_resource (st->dpy, "showGraph", "Boolean");
907
908   st->ncolors = get_integer_resource (st->dpy, "ncolors", "Integer");
909
910
911   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
912   assert(st->colors = (XColor *) calloc (st->ncolors,sizeof(XColor)));
913
914   if (get_boolean_resource(st->dpy, "mono", "Boolean"))
915     {
916     MONO:
917       st->ncolors = 1;
918       st->colors[0].pixel = get_pixel_resource(st->dpy, st->xgwa.colormap,
919                                            "foreground", "Foreground");
920     }
921   else
922     {
923 #if 0
924       make_random_colormap (st->dpy, st->xgwa.visual, st->xgwa.colormap,
925                             st->colors, &st->ncolors, True, True, 0, True);
926 #else
927       make_smooth_colormap (st->dpy, st->xgwa.visual, st->xgwa.colormap,
928                             st->colors, &st->ncolors, True, 0, True);
929 #endif
930       if (st->ncolors < 2)
931         goto MONO;
932       else {
933         st->colors[0].pixel = get_pixel_resource(st->dpy, st->xgwa.colormap,
934                                              "foreground", "Foreground");
935         st->colors[1].pixel = get_pixel_resource(st->dpy, st->xgwa.colormap,
936                                              "background", "Background");
937       }
938     }
939   
940   
941   /* graphic context for curves */
942   gcv.foreground = st->colors[0].pixel;
943   gcv.background = st->colors[1].pixel;
944   gcv.line_width = st->params.curve_width;
945   gcv.cap_style=CapRound;
946   st->gc = XCreateGC (st->dpy, st->window, GCForeground|GCBackground|GCLineWidth|GCCapStyle, &gcv);
947   
948   /* graphic context for graphs */
949   gcv.foreground = st->colors[0].pixel;
950   gcv.background = st->colors[1].pixel;
951   st->gc_graph = XCreateGC (st->dpy, st->window, GCForeground|GCBackground, &gcv);
952   
953   /* graphic context for shadows */
954   gcv.foreground = st->colors[1].pixel;
955   gcv.line_width = st->params.shadow_width;
956   gcv.cap_style=CapRound;
957   st->shadow_gc = XCreateGC(st->dpy, st->window, GCForeground|GCLineWidth|GCCapStyle, &gcv);
958
959   st->delay2 = 1000000 * get_integer_resource(st->dpy, "delay2", "Delay2");
960
961   return st;
962 }
963
964 static unsigned long
965 celtic_draw (Display *dpy, Window window, void *closure)
966 {
967   struct state *st = (struct state *) closure;
968
969   if (st->eraser) {
970     st->eraser = erase_window (st->dpy, st->window, st->eraser);
971     return 10000;
972   }
973
974   if (st->reset) {
975     st->reset = 0;
976
977     pattern_del(st->pattern);
978     st->pattern = NULL;
979     graph_del(st->graph);
980
981     /* recolor each time */
982     st->ncolors = get_integer_resource (st->dpy, "ncolors", "Integer");
983     if (st->ncolors > 2)
984       make_smooth_colormap (st->dpy, st->xgwa.visual, st->xgwa.colormap,
985                             st->colors, &st->ncolors, True, 0, True);
986
987     st->eraser = erase_window (st->dpy, st->window, st->eraser);
988     return st->delay2;
989   }
990
991   if (st->pattern == NULL) {
992     st->params.curve_width=random()%5+4;
993     st->params.shadow_width=st->params.curve_width+4;
994     st->params.shape1=(15+random()%15)/10.0 -1.0;
995     st->params.shape2=(15+random()%15)/10.0 -1.0;
996     st->params.edge_size=10*(random()%5)+20;
997     st->params.delay=get_integer_resource(st->dpy, "delay", "Delay");
998     st->params.angle=random()%360*2*M_PI/360;
999     st->params.margin=(random()%8)*100-600;
1000
1001     switch (random()%4) {
1002     case 0:
1003       st->params.type=tgrid;
1004       st->params.shape1=(random()%1*2-1.0)*(random()%10+3)/10.0;
1005       st->params.shape2=(random()%1*2-1.0)*(random()%10+3)/10.0;
1006       st->params.edge_size=10*(random()%5)+50;
1007       break;
1008     case 1:
1009       st->params.type=kennicott;
1010       st->params.shape1=(random()%20)/10.0 -1.0;
1011       st->params.shape2=(random()%20)/10.0 -1.0;
1012       st->params.edge_size=10*(random()%3)+70;
1013       st->params.cluster_size=st->params.edge_size/(3.0+random()%10)-1;
1014       break;
1015     case 2:
1016       st->params.type=triangle;
1017       st->params.edge_size=10*(random()%5)+60;
1018       st->params.margin=(random()%10)*100-900;
1019       break;
1020     case 3:
1021       st->params.type=polar;
1022       st->params.nb_orbits=2+random()%10;
1023       st->params.nb_nodes_per_orbit=4+random()%10;
1024       break;
1025     }
1026
1027
1028 /*     st->params.type= polar; */
1029 /*   st->params.nb_orbits= 5; */
1030 /*   st->params.nb_nodes_per_orbit= 19; */
1031 /*   st->params.curve_width= 4; */
1032 /*   st->params.shadow_width= 8; */
1033 /*   st->params.shape1= 0.5; */
1034 /*   st->params.shape2= 1.3; */
1035 /*   st->params.margin= 30; */
1036 /*   st->params.angle= 5.21853; */
1037 /*   st->params.delay= 10000; */
1038
1039     
1040 /*     params_to_s(stdout); */
1041     
1042   /*=======================================================*/
1043     
1044     
1045     switch (st->params.type) {
1046     case tgrid:
1047       st->graph=make_grid_graph(st, st->params.margin,st->params.margin,
1048                         st->xgwa.width-2*st->params.margin, 
1049                         st->xgwa.height-2*st->params.margin, 
1050                         st->params.edge_size);
1051       break;
1052     case kennicott:
1053       st->graph=make_kennicott_graph(st, st->params.margin,st->params.margin,
1054                              st->xgwa.width-2*st->params.margin, 
1055                              st->xgwa.height-2*st->params.margin, 
1056                              st->params.edge_size,
1057                              st->params.cluster_size);
1058       break;
1059     case triangle:
1060       st->graph=make_triangle_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       break;
1065     case polar:
1066       st->graph=make_polar_graph(st, st->params.margin,st->params.margin,
1067                          st->xgwa.width-2*st->params.margin, 
1068                          st->xgwa.height-2*st->params.margin, 
1069                          st->params.nb_nodes_per_orbit, 
1070                          st->params.nb_orbits);
1071       break;
1072     default:
1073       st->graph=make_grid_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.edge_size);
1077       break;
1078     }
1079
1080     graph_rotate(st->graph,st->params.angle,st->xgwa.width/2,st->xgwa.height/2);
1081     
1082     if (st->showGraph)
1083       graph_draw(st, st->graph);
1084     
1085     st->pattern=pattern_new(st, st->graph, st->params.shape1, st->params.shape2);
1086     pattern_make_curves(st->pattern);
1087     st->t = 0.0;
1088   }
1089
1090   pattern_animate(st);
1091
1092   return st->params.delay;
1093 }
1094
1095
1096 static void
1097 celtic_reshape (Display *dpy, Window window, void *closure, 
1098                  unsigned int w, unsigned int h)
1099 {
1100   struct state *st = (struct state *) closure;
1101   XGetWindowAttributes (st->dpy, st->window, &st->xgwa);
1102 }
1103
1104 static Bool
1105 celtic_event (Display *dpy, Window window, void *closure, XEvent *event)
1106 {
1107   return False;
1108 }
1109
1110 static void
1111 celtic_free (Display *dpy, Window window, void *closure)
1112 {
1113   struct state *st = (struct state *) closure;
1114   free (st);
1115 }
1116
1117
1118 XSCREENSAVER_MODULE ("Celtic", celtic)