sys/src/games/timmy/poly.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <thread.h>
   4 #include <draw.h>
   5 #include <mouse.h>
   6 #include "dat.h"
   7 #include "fns.h"
   8
   9 Poly *
  10 mkpoly(int n, ...)
  11 {
  12         Poly *p;
  13         int i;
  14         va_list va;
  15
  16         p = emalloc(sizeof(Poly));
  17         p->nvert = n;
  18         p->vert = emalloc((n + 1) * sizeof(Vec));
  19         va_start(va, n);
  20         for(i = 0; i < n; i++){
  21                 p->vert[i].x = va_arg(va, double);
  22                 p->vert[i].y = va_arg(va, double);
  23         }
  24         p->vert[n] = p->vert[0];
  25         va_end(va);
  26         polyfix(p);
  27         return p;
  28 }
  29
  30 void
  31 polyfix(Poly *o)
  32 {
  33         double I, A, x, y, t;
  34         Vec *p, *q;
  35         int i;
  36
  37         I = 0;
  38         A = 0;
  39         x = 0;
  40         y = 0;
  41         for(i = 0; i < o->nvert; i++){
  42                 p = &o->vert[i];
  43                 q = p + 1;
  44                 t = p->x * q->y - p->y * q->x;
  45                 A += t;
  46                 x += (p->x + q->x) * t / 3;
  47                 y += (p->y + q->y) * t / 3;
  48         }
  49         x /= A;
  50         y /= A;
  51         for(i = 0; i <= o->nvert; i++){
  52                 o->vert[i].x -= x;
  53                 o->vert[i].y -= y;
  54         }
  55         for(i = 0; i < o->nvert; i++){
  56                 p = &o->vert[i];
  57                 q = p + 1;
  58                 t = p->x * q->y - p->y * q->x;
  59                 I += (p->x * (p->x + q->x) + q->x * q->x + p->y * (p->y + q->y) + q->y * q->y) * t / 6;
  60         }
  61         o->invI = A / I;
  62 }
  63
  64 Poly *
  65 polydup(Poly *p)
  66 {
  67         Poly *q;
  68         int i;
  69
  70         q = emalloc(sizeof(Poly));
  71         q->nvert = p->nvert;
  72         q->vert = emalloc((p->nvert + 1) * sizeof(Vec));
  73         for(i = 0; i <= p->nvert; i++)
  74                 q->vert[i] = p->vert[i];
  75         q->invI = p->invI;
  76         return q;
  77 }
  78
  79 void
  80 polytrans(Poly *sp, Poly *dp, double x0, double y0, double θ)
  81 {
  82         int i;
  83         double c, s, x, y;
  84
  85         assert(sp->nvert == dp->nvert);
  86         c = cos(θ * DEG);
  87         s = sin(θ * DEG);
  88         for(i = 0; i <= sp->nvert; i++){
  89                 x = sp->vert[i].x;
  90                 y = sp->vert[i].y;
  91                 dp->vert[i].x = x0 + x * c - y * s;
  92                 dp->vert[i].y = y0 + x * s + y * c;
  93         }
  94         dp->invI = sp->invI;
  95 }
  96
  97 void
  98 polybbox(Poly *sp, Rectangle *t)
  99 {
 100         int fx, fy, cx, cy, i;
 101
 102         t->min.x = floor(sp->vert[0].x - Slop);
 103         t->max.x = ceil(sp->vert[0].x + Slop) + 1;
 104         t->min.y = floor(sp->vert[0].y - Slop);
 105         t->max.y = ceil(sp->vert[0].y + Slop) + 1;
 106         for(i = 1; i < sp->nvert; i++){
 107                 fx = sp->vert[i].x;
 108                 cx = ceil(fx + Slop); fx = floor(fx - Slop);
 109                 fy = sp->vert[i].y + 1;
 110                 cy = ceil(fy + Slop); fy = floor(fy - Slop);
 111                 if(fx < t->min.x) t->min.x = fx;
 112                 if(cx > t->max.x) t->max.x = cx;
 113                 if(fy < t->min.y) t->min.y = fy;
 114                 if(cy > t->max.y) t->max.y = cy;
 115         }
 116 }
 117
 118 void
 119 polydraw(Poly *p, Image *d, Image *fill, Image *line)
 120 {
 121         int i;
 122         static int maxp;
 123         static Point *buf;
 124
 125         if(p->nvert + 1 > maxp){
 126                 maxp = p->nvert + 1;
 127                 free(buf);
 128                 buf = emalloc((p->nvert + 1) * sizeof(Point));
 129         }
 130         for(i = 0; i <= p->nvert; i++){
 131                 buf[i].x = d->r.min.x + (int)(p->vert[i].x + 0.5);
 132                 buf[i].y = d->r.min.y + (int)(p->vert[i].y + 0.5);
 133         }
 134         if(fill != nil) fillpoly(d, buf, p->nvert + 1, 0, fill, ZP);
 135         if(line != nil) poly(d, buf, p->nvert + 1, 0, 0, 0, line, ZP);
 136 }
 137
 138 void
 139 freepoly(Poly *p)
 140 {
 141         if(p == nil) return;
 142         free(p->vert);
 143         free(p);
 144 }
 145
 146 Hinge *
 147 hingedup(Hinge *h, Obj *o)
 148 {
 149         Hinge *p, **hp, *r;
 150
 151         r = nil;
 152         hp = &r;
 153         for(; h != nil; h = h->onext){
 154                 p = emalloc(sizeof(Hinge));
 155                 p->p = h->p;
 156                 p->p0 = h->p0;
 157                 p->o = o;
 158                 p->cnext = p->cprev = p;
 159                 *hp = p;
 160                 hp = &p->onext;
 161         }
 162         return r;
 163 }
 164
 165 Obj *
 166 mkobj(ObjT *t)
 167 {
 168         Obj *o;
 169
 170         o = emalloc(sizeof(Obj));
 171         o->tab = t;
 172         o->hinge = hingedup(t->hinge, o);
 173         o->tab->init(o);
 174         o->next = o->prev = o;
 175         return o;
 176 }
 177
 178 Obj *
 179 objdup(Obj *o)
 180 {
 181         Obj *p;
 182
 183         p = emalloc(sizeof(Obj));
 184         *p = *o;
 185         p->poly = polydup(o->poly);
 186         p->next = p->prev = p;
 187         p->hinge = hingedup(p->hinge, p);
 188         return p;
 189 }
 190
 191 void
 192 objcat(Obj *l, Obj *o)
 193 {
 194         o->prev = l->prev;
 195         o->next = l;
 196         o->prev->next = o;
 197         o->next->prev = o;
 198 }
 199
 200 static int
 201 polycheck(Poly *a, Poly *b)
 202 {
 203         int i, j;
 204         Vec *x, *y, *z;
 205         double d, m;
 206
 207         for(i = 0; i < a->nvert; i++){
 208                 z = &a->vert[i];
 209                 m = Inf(1);
 210                 for(j = 0; j < b->nvert; j++){
 211                         x = &b->vert[j];
 212                         y = x + 1;
 213                         d = (z->y - x->y) * (y->x - x->x) - (z->x - x->x) * (y->y - x->y);
 214                         d /= vecdist(*x, *y);
 215                         if(d < -Slop) goto next;
 216                         if(d < m){
 217                                 if(m < 0) goto next;
 218                                 m = d;
 219                         }else if(d < 0) goto next;
 220                 }
 221                 return 1;
 222         next:;
 223         }
 224         return 0;
 225 }
 226
 227 int
 228 objcoll(Obj *a, Obj *b)
 229 {
 230         if(!rectXrect(a->bbox, b->bbox)) return 0;
 231         if(a->poly == nil || b->poly == nil) return 0;
 232         return polycheck(a->poly, b->poly) || polycheck(b->poly, a->poly);
 233 }
 234
 235 void
 236 objexcise(Obj *o)
 237 {
 238         Hinge *h;
 239
 240         o->next->prev = o->prev;
 241         o->prev->next = o->next;
 242         o->next = o;
 243         o->prev = o;
 244         for(h = o->hinge; h != nil; h = h->onext){
 245                 h->cprev->cnext = h->cnext;
 246                 h->cnext->cprev = h->cprev;
 247                 h->cprev = h;
 248                 h->cnext = h;
 249         }
 250 }
 251
 252 void
 253 freeobj(Obj *o)
 254 {
 255         if(o == nil) return;
 256         objexcise(o);
 257         freepoly(o->poly);
 258         free(o);
 259 }
 260
 261 int
 262 hinged(Obj *a, Obj *b)
 263 {
 264         Hinge *k, *l, *m;
 265
 266         if(b->hinge == nil) return 0;
 267         for(k = a->hinge; k != nil; k = k->onext)
 268                 for(l = k->cnext; l != k; l = l->cnext)
 269                         for(m = b->hinge; m != nil; m = m->onext)
 270                                 if(m == l)
 271                                         return 1;
 272         return 0;
 273 }
 274
 275 Hinge *hinges;
 276
 277 void
 278 hingepairs(Obj *l)
 279 {
 280         Obj *o;
 281         Hinge *h, *hh;
 282         Hinge **p;
 283
 284         hinges = nil;
 285         p = &hinges;
 286         for(o = l->next; o != l; o = o->next)
 287                 for(h = o->hinge; h != nil; h = h->onext){
 288                         for(hh = h->cnext; hh != h; hh = hh->cnext)
 289                                 if(hh < h)
 290                                         break;
 291                         if(hh == h) continue;
 292                         *p = h;
 293                         p = &h->anext;
 294                 }
 295 }
 296
 297 void
 298 copyhinges(Obj *sl, Obj *dl)
 299 {
 300         Obj *o, *p, **ol;
 301         Hinge *h, *k, *l;
 302         int n;
 303
 304         for(n = 0, o = sl->next; o != sl; o = o->next)
 305                 o->idx = n++;
 306         ol = emalloc(sizeof(Obj *) * n);
 307         for(n = 0, o = dl->next; o != dl; o = o->next)
 308                 ol[n++] = o;
 309         for(o = sl->next, p = dl->next; o != sl; o = o->next, p = p->next){
 310                 for(h = o->hinge, k = p->hinge; h != nil; h = h->onext, k = k->onext){
 311                         if(h->cnext == h) continue;
 312                         for(l = h->cnext->o->hinge, n = 0; l != h->cnext; l = l->onext)
 313                                 n++;
 314                         for(l = ol[h->cnext->o->idx]->hinge; n != 0; n--)
 315                                 l = l->onext;
 316                         l->cprev->cnext = k->cnext;
 317                         k->cnext->cprev = l->cprev;
 318                         k->cnext = l;
 319                         l->cprev = k;
 320                 }
 321         }
 322         hingepairs(dl);
 323 }