source: subversion/applications/rendering/gosmore/jni/openglespolygon.cpp @ 29350

Last change on this file since 29350 was 27325, checked in by nic, 8 years ago

Fix link errors with gcc-4.6 / Ubuntu-11.10.
Fix HEADLESS compile
Provide for larger planet

  • Property svn:executable set to *
File size: 18.0 KB
Line 
1/* Copyright (C) 2011 Nic Roets as detailed in the README file. */
2#ifndef HEADLESS
3#include <assert.h>
4#include <string.h>
5#include <malloc.h>
6#ifdef ANDROID_NDK
7#include <jni.h>
8#include <GLES/gl.h>
9#include <GLES/glext.h>
10#include <android/log.h>
11#else
12#include <gtk/gtk.h>
13#include <gdk/gdk.h>
14#include <gdk/gdkx.h>
15#endif
16#include "openglespolygon.h"
17#define LG  //__android_log_print (ANDROID_LOG_WARN, "Gosmore", "%d", __LINE__);
18
19using namespace std;
20
21typedef long long calcType; // Used to prevent overflows when
22                            // multiplying two GdkPoint fields
23
24int edgeCmp /*::operator()*/(const PolygonEdge *a, const PolygonEdge *b)
25{
26  const FixedPoint *ap = a->pt, *bp = b->pt,
27    *st = a->prev.y < b->prev.y ? &a->prev : &b->prev;
28  calcType cross;
29  if (a->pt == &a->prev) return a->prev.x < 0; // left and right borders
30  if (b->pt == &b->prev) return b->prev.x > 0;
31  while ((cross = (ap->x - st->x) * (calcType)(bp->y - st->y) -
32                  (ap->y - st->y) * (calcType)(bp->x - st->x)) == 0) {
33    if (ap->y < bp->y) {
34      st = ap;
35      ap += a->delta;
36      if (ap - a->pt >= a->cnt || ap - a->pt + a->cnt <= 0) {
37        if (!a->continues) return !b->isLeft; // Edges are the same
38        a++;
39        ap = a->pt;
40      }
41    }
42    else {
43      st = bp;
44      bp += b->delta;
45      if (bp - b->pt >= b->cnt || bp - b->pt + b->cnt <= 0) {
46        if (!b->continues) return !b->isLeft; // Edges are the same
47        b++;
48        bp = b->pt;
49      }
50    }
51  }
52  return cross < 0;
53}
54
55//-------------------[ Start of AA tree code ]---------------------------
56#define AATREE_NOREBALANCE 1
57
58struct PolygonEdge *First (struct PolygonEdge *root)
59{
60  if (!root->left) return NULL;
61  while (root->left) root = root->left;
62  return root;
63}
64
65struct PolygonEdge *Next (struct PolygonEdge *n)
66{
67  if (n->right) {
68    n = n->right;
69    while (n->left) n = n->left;
70  }
71  else {
72    while (n->parent && n->parent->right == n) n = n->parent;
73    // Follow the parent link while it's pointing to the left.
74    n = n->parent; // Follow one parent link pointing to the right
75
76    if (!n->parent) return NULL;
77    // The last PolygonEdge is the root, because it has nothing to it's right
78  }
79  return n;
80}
81
82struct PolygonEdge *Prev (struct PolygonEdge *n)
83{
84  if (n->left) {
85    n = n->left;
86    while (n->right) n = n->right;
87  }
88  else {
89    while (n->parent && n->parent->left == n) n = n->parent;
90    // Follow the parent link while it's pointing to the left.
91    if (!n->parent) return NULL;
92    // The last PolygonEdge is the root, because it has nothing to it's right
93    n = n->parent; // Follow one parent link pointing to the right
94  }
95  return n;
96}
97
98void Skew (struct PolygonEdge *oldparent)
99{
100  struct PolygonEdge *newp = oldparent->left;
101 
102  if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
103  else oldparent->parent->right = newp;
104  newp->parent = oldparent->parent;
105  oldparent->parent = newp;
106 
107  oldparent->left = newp->right;
108  if (oldparent->left) oldparent->left->parent = oldparent;
109  newp->right = oldparent;
110 
111  oldparent->level = oldparent->left ? oldparent->left->level + 1 : 1;
112}
113
114int Split (struct PolygonEdge *oldparent)
115{
116  struct PolygonEdge *newp = oldparent->right;
117 
118  if (newp && newp->right && newp->right->level == oldparent->level) { 
119    if (oldparent->parent->left == oldparent) oldparent->parent->left = newp;
120    else oldparent->parent->right = newp;
121    newp->parent = oldparent->parent;
122    oldparent->parent = newp;
123   
124    oldparent->right = newp->left;
125    if (oldparent->right) oldparent->right->parent = oldparent;
126    newp->left = oldparent;
127    newp->level = oldparent->level + 1;
128    return 1;
129  }
130  return 0;
131}
132
133#if 0
134static struct PolygonEdge root;
135// A static variable to make things easy.
136
137void RebalanceAfterLeafAdd (struct PolygonEdge *n)
138{ // n is a PolygonEdge that has just been inserted and is now a leaf PolygonEdge.
139  n->level = 1;
140  n->left = NULL;
141  n->right = NULL;
142  for (n = n->parent; n != &root; n = n->parent) {
143    // At this point n->parent->level == n->level
144    if (n->level != (n->left ? n->left->level + 1 : 1)) {
145      // At this point the tree is correct, except (AA2) for n->parent
146      Skew (n);
147      // We handle it (a left add) by changing it into a right add using Skew
148      // If the original add was to the left side of a PolygonEdge that is on the
149      // right side of a horisontal link, n now points to the rights side
150      // of the second horisontal link, which is correct.
151     
152      // However if the original add was to the left of PolygonEdge with a horisontal
153      // link, we must get to the right side of the second link.
154      if (!n->right || n->level != n->right->level) n = n->parent;
155    }
156    if (!Split (n->parent)) break;
157  }
158}
159#endif
160
161void Delete (struct PolygonEdge *n)
162{ // If n is not a leaf, we first swap it out with the leaf PolygonEdge that just
163  // precedes it.
164  struct PolygonEdge *leaf = n, *tmp;
165 
166  if (n->left) {
167    for (leaf = n->left; leaf->right; leaf = leaf->right) {}
168    // When we stop, left has no 'right' child so it cannot have a left one
169    #ifdef AATREE_NOREBALANCE
170    // Remove leaf:
171    if (leaf->parent->left == leaf) leaf->parent->left = leaf->left;
172    else leaf->parent->right = leaf->left;
173    if (leaf->left) leaf->left->parent = leaf->parent;
174    // Replace n with leaf:
175    leaf->parent = n->parent;
176    leaf->left = n->left;
177    leaf->right = n->right;
178    if (n->parent->left == n) n->parent->left = leaf;
179    else n->parent->right = leaf;
180    if (leaf->left) leaf->left->parent = leaf;
181    if (leaf->right) leaf->right->parent = leaf;
182    return;
183    #endif
184  }
185  #ifdef AATREE_NOREBALANCE
186  else {
187    if (n->parent->left == n) n->parent->left = n->right;
188    else n->parent->right = n->right;
189    if (n->right) n->right->parent = n->parent;
190    return;
191  }
192  #else
193  else if (n->right) leaf = n->right;
194  #endif
195
196  tmp = leaf->parent == n ? leaf : leaf->parent;
197  if (leaf->parent->left == leaf) leaf->parent->left = NULL;
198  else leaf->parent->right = NULL;
199 
200  if (n != leaf) {
201    if (n->parent->left == n) n->parent->left = leaf;
202    else n->parent->right = leaf;
203    leaf->parent = n->parent;
204    if (n->left) n->left->parent = leaf;
205    leaf->left = n->left;
206    if (n->right) n->right->parent = leaf;
207    leaf->right = n->right;
208    leaf->level = n->level;
209  }
210  #ifndef AATREE_NOREBALANCE
211  // free (n);
212  while (tmp != &root) {
213    // One of tmp's childern had it's level reduced
214    if (tmp->level > (tmp->left ? tmp->left->level + 1 : 1)) { // AA2 failed
215      tmp->level--;
216      if (Split (tmp)) {
217        if (Split (tmp)) Skew (tmp->parent->parent);
218        break;
219      }
220      tmp = tmp->parent;
221    }
222    else if (tmp->level <= (tmp->right ? tmp->right->level + 1 : 1)) break;
223    else { // AA3 failed
224      Skew (tmp);
225      //if (tmp->right) tmp->right->level = tmp->right->left ? tmp->right->left->level + 1 : 1;
226      if (tmp->level > tmp->parent->level) {
227        Skew (tmp);
228        Split (tmp->parent->parent);
229        break;
230      }
231      tmp = tmp->parent->parent;
232    }
233  }
234  #endif
235}
236
237void Check (struct PolygonEdge *n)
238{
239  assert (!n->left || n->left->parent == n);
240  assert (!n->right || n->right->parent == n);
241//  assert (!Next (n) || n->data <= Next (n)->data);
242  assert (!n->parent || n->parent->level >= n->level);
243  assert (n->level == (n->left == NULL ? 1 : n->left->level + 1));
244  assert (n->level <= 1 || n->right && n->level - n->right->level <= 1);
245  assert (!n->parent || !n->parent->parent ||
246          n->parent->parent->level > n->level);
247}
248
249void Add (struct PolygonEdge *n, struct PolygonEdge *root)
250{
251  struct PolygonEdge *s = root;
252  int lessThan = 1;
253  while (lessThan ? s->left : s->right) {
254    s = lessThan ? s->left : s->right;
255    lessThan = edgeCmp(n, s); //c.operator<(n, s);
256  }
257  if (lessThan) s->left = n;
258  else s->right = n;
259  n->parent = s;
260  #ifdef AATREE_NOREBALANCE
261  n->level = 1;
262  n->left = NULL;
263  n->right = NULL;
264  #else
265  RebalanceAfterLeafAdd (n);
266  #endif
267}
268//----------------------------[ End of AA tree ]----------------------------
269
270int ptSize = 0;
271void AddPolygon (vector<PolygonEdge> &d, FixedPoint *p, int cnt)
272{
273  int i, j, k, firstd = d.size();
274  ptSize = cnt;
275  for (j = cnt - 1; j > 0 && (p[j - 1].y == p[j].y || // p[j..cnt-1] becomes
276    (p[j - 1].y < p[j].y) == (p[j].y < p[0].y)); j--) {} // monotone
277  //if (j == 0) return; // Polygon has no height but it does not cause infinite loop
278  for (i = 0; i < j && (p[i].y == p[i + 1].y ||
279    (p[i].y < p[i + 1].y) == (p[j].y < p[0].y)); i++) {}
280  // Now p[cn-1],p[0..i] is the longest monotone sequence
281  d.resize (firstd + 2);
282  memset (&d[firstd], 0, sizeof (d[0]) * 2); // TODO: remove
283  d[firstd].delta = p[j].y < p[0].y ? 1 : -1;
284  d[firstd].continues = 1;
285  d[firstd + 1].delta = p[j].y < p[0].y ? 1 : -1;
286  d[firstd + 1].continues = 0;
287  d[firstd + !(p[j].y < p[0].y)].cnt = cnt - j;
288  d[firstd + (p[j].y < p[0].y)].cnt = i + 1;
289  d[firstd + !(p[j].y < p[0].y)].pt = p + (p[j].y < p[0].y ? j : cnt - 1);
290  d[firstd + (p[j].y < p[0].y)].pt = p + (p[j].y < p[0].y ? 0 : i);
291  //int lowest = j;
292  for (; i < j ; i = k) {
293    //if (p[lowest].y > p[i].y) lowest = i;
294    for (k = i + 1; k < j && (p[k].y == p[k + 1].y || // p[i..k] becomes
295        (p[k].y < p[k + 1].y) == (p[i].y < p[k].y)); k++) {} // monotone
296    d.push_back(PolygonEdge());
297    memset (&d.back(), 0, sizeof (d[0])); // TODO: remove
298    d[d.size() - 1].pt = p + (p[i].y < p[k].y ? i : k);
299    d[d.size() - 1].delta = p[i].y < p[k].y ? 1 : -1;
300    d[d.size() - 1].continues = 0;
301    d[d.size() - 1].cnt = k - i + 1;
302  }
303/*  GdkPoint *ll = &p[lowest], *lr = &p[lowest];
304  do {
305    if (--ll < p) ll = p + cnt - 1;
306  } while (ll->y <= p[lowest].y);
307  do {
308    if (++lr >= p + cnt) lr = p;
309  } while (lr->y <= p[lowest].y);*/
310  calcType area = p[cnt-1].x * (calcType) p[0].y - p[0].x * (calcType) p[cnt-1].y;
311  for (i = 0; i < cnt - 1; i++) area += p[i].x*(calcType)p[i+1].y-
312    p[i+1].x * (calcType) p[i].y;
313  for (i = firstd; i < d.size(); i++) {
314    // This ll/lr inequality is a cross product that is true if the polygon
315    // was clockwise. AddInnerPoly() will just negate isLeft.
316    d[i].isLeft = (area < 0) == (d[i].delta == 1);
317  }
318}
319
320void AddClockwise (vector<PolygonEdge> &d, FixedPoint *p, int cnt)
321{
322  int i, j;
323  #if 0
324  for (i = 0; i < cnt; i++) __android_log_print (ANDROID_LOG_WARN, "Gosmore",
325    "pt[ptCnt].x = %d; pt[ptCnt++].y=%d;", p[i].x, p[i].y);
326  __android_log_print (ANDROID_LOG_WARN, "Gosmore", "AddClockwise(d,pt,ptCnt); ptCnt = 0;");
327  #endif
328  for (i = 0; i < cnt - 1 && p[i].y == p[0].y; i++) {}
329  int up = p[i].y > p[0].y;
330  for (i = 0; i < cnt - 1; i = j) {
331    d.push_back(PolygonEdge());
332    memset (&d.back(), 0, sizeof (d[0])); //TODO: remove
333    for (j = i; j + 1 < cnt &&
334      (up ? p[j + 1].y >= p[j].y : p[j + 1].y <= p[j].y); j++) {}
335    d[d.size() - 1].pt = up ? p + i : p + j;
336    d[d.size() - 1].delta = up ? 1 : -1;
337    d[d.size() - 1].isLeft = up;
338    d[d.size() - 1].cnt = j - i + 1;
339    d[d.size() - 1].continues = 0;
340    up = !up;
341  }
342}
343
344#ifdef ANDROID_NDK
345void Fill (vector<PolygonEdge> &d,int isSea)
346#else
347void Fill (vector<PolygonEdge> &d,int isSea, GdkWindow *w, GdkGC *gc)
348#endif
349{
350  //PolygonEdge **heap = (PolygonEdge **) malloc ((d.size() + 1) * sizeof (*heap));
351  vector<PolygonEdge*> heap;
352  heap.resize (d.size() + 1);
353  memset (&heap[0], 0, sizeof (heap[0]) * (d.size()+1)); // TODO: remove
354  // leave heap[0] open to make indexing easier
355  int i, h = 1, j, sea = 0, start = 1;
356  PolygonEdge dummy, left, right, root;
357 
358  root.left = NULL;
359  root.right = NULL;
360  root.level = 1000000;
361  root.parent = NULL;
362 
363/*  for (i = 0; i < d.size(); i++) {
364    for (j = 0; j + 1 < d[i].cnt; j++) assert (d[i].pt[j*d[i].delta].y <= d[i].pt[(j+1)*d[i].delta].y);
365    if (d[i].continues)                assert (d[i].pt[j*d[i].delta].y <= d[i+1].pt->y);
366  } // Make sure AddPolygon() and variants are correct */
367  dummy.opp = &dummy;
368  for (i = 0; i < d.size(); i++) {
369    for (j = h++; j > 1 && heap[j / 2]->pt->y > d[i].pt->y; j /= 2) {
370      heap[j] = heap[j/2];
371    }
372    heap[j] = &d[i];
373    d[i].opp = NULL;
374    memcpy (&d[i].prev, d[i].pt, sizeof (d[i].prev)); // This is only
375    // to make the compare work.
376    if (d[i].continues) ++i; // Don't add the second part to the heap
377  }
378  //for (i = 2; i < h; i++) assert (heap[i]->pt->y >= heap[i/2]->pt->y);
379  left.prev.x = -6000*65536;
380  left.prev.y = 0;
381  left.opp = &dummy;
382  //h < 3 || edgeCmp (heap[1],
383  //                heap[h == 3 || heap[2]->pt->y < heap[3]->pt->y ? 2 : 3])
384  //          != !heap[1]->isLeft ? &dummy : &right;
385  left.pt = &left.prev;
386  left.isLeft = 1;
387  Add (&left, &root);
388  right.prev.x = 6000*65536;
389  right.prev.y = 0;
390  right.opp = &dummy; //left.opp == &dummy ? &dummy : &left;
391  right.pt = &right.prev;
392  right.isLeft = 0;
393  Add (&right, &root);
394  while (h > 1) {
395    PolygonEdge *head = heap[1];
396    //printf ("%p %3d\n", head->opp, head->pt->y);
397    if (!head->opp) { // Insert it
398      Add (head, &root);
399      head->opp = head->isLeft ? Next (head) : Prev (head);
400      if (head->opp == NULL || head->opp->isLeft == head->isLeft) {
401        head->opp = &dummy;
402      }
403    }
404    PolygonEdge *o = head->opp;
405    /* Now we render the trapezium between head->opp and head->opp->opp up
406       to head->pt->y */
407    if (o != &dummy && o->opp != &dummy) {
408      GdkPoint q[6];
409      #define CLAMPX(x) (short)((x) >= (1<<29) ? 8191 : (x) < -(1<<29) ? -8191 : (x) >> 16)
410      q[2].x = CLAMPX (o->opp->prev.x);
411      q[2].y = CLAMPX (o->opp->prev.y);
412      q[3].x = CLAMPX (o->prev.x);
413      q[3].y = CLAMPX (o->prev.y);
414      o->prev.x = o->pt->y <= o->prev.y ? o->pt->x
415        : o->prev.x + (o->pt->x - o->prev.x) *
416            calcType (head->pt->y - o->prev.y) / (o->pt->y - o->prev.y);
417      q[0].x = CLAMPX(o->prev.x);
418      o->prev.y = head->pt->y;
419      q[0].y = CLAMPX(o->prev.y);
420      o->opp->prev.x = o->opp->pt->y <= o->opp->prev.y ? o->opp->pt->x
421        : o->opp->prev.x + (o->opp->pt->x - o->opp->prev.x) *
422      calcType (head->pt->y - o->opp->prev.y) / (o->opp->pt->y - o->opp->prev.y);
423      q[1].x = CLAMPX (o->opp->prev.x);
424      o->opp->prev.y = head->pt->y;
425      q[1].y = q[0].y;
426    //if (o->opp->prev.y != o->prev.y && o->opp->prev.x < 30000 &&
427    //  o->opp->prev.x > -30000 && o->prev.x < 30000 && o->prev.x > -30000)
428    //  __android_log_print (ANDROID_LOG_WARN, "Gosmore", "Prev dif");
429      if ((isSea || (o->pt != &o->prev && o->opp->pt != &o->opp->prev)) &&
430          q[o->pt == &o->prev ? 2 : 3].y < q[0].y) {
431      // Frequently it happens that one of the triangles has 0 area because
432      // two of the points are equal. TODO: Filter them out.
433        #ifdef ANDROID_NDK
434        memcpy (&q[4], &q[0], sizeof (q[4]));
435        memcpy (&q[5], &q[2], sizeof (q[5]));
436        glVertexPointer (2, GL_SHORT, 0, q);
437        glDrawArrays (GL_TRIANGLES, 0, 6);
438        #else
439        //memcpy (&q[2], &o->prev, sizeof (q[2]));
440        //memcpy (&q[3], &o->opp->prev, sizeof (q[3]));
441        gdk_draw_polygon (w, gc, TRUE, q, 4);
442        #endif
443        if (q[0].x > 100 && q[1].x <= 100) sea = o->opp == &left;
444        if (q[0].x <= 100 && q[1].x < 100) sea = o->opp == &right;
445        if (q[1].x > 100 && q[0].x <= 100) sea = o == &left;
446        if (q[1].x <= 100 && q[0].x < 100) sea = o == &right;
447       
448        if (start) {
449          start = 0;
450          if (sea) {
451            q[2].x = -6000;
452            q[3].x = 6000;
453            q[4].x = 0;
454            q[4].y = -6000;
455            #ifdef ANDROID_NDK
456            glVertexPointer (2, GL_SHORT, 0, q + 2);
457            glDrawArrays (GL_TRIANGLES, 0, 3);
458            #else
459            //memcpy (&q[2], &o->prev, sizeof (q[2]));
460            //memcpy (&q[3], &o->opp->prev, sizeof (q[3]));
461            gdk_draw_polygon (w, gc, TRUE, q + 2, 3);
462            #endif
463          }
464        }
465      } // If the trapezium has a non-zero height
466    }
467    if (o != &dummy && o->opp != head) {
468      o->opp->opp = &dummy; // Complete the 'Add'
469      o->opp = head;
470    }
471
472    if (--head->cnt) head->pt += head->delta;
473    else if (head->continues) {
474      head->continues = head[1].continues;
475      head->cnt = head[1].cnt;
476      head->pt = head[1].pt;
477    }
478    else { // Remove it
479      head->opp->opp = &dummy;
480      PolygonEdge *n = head->isLeft ? Prev (head) : Next (head);
481      if (n && n->opp == &dummy) {
482        if (head->isLeft == n->isLeft && 
483          (head->opp->pt != &head->opp->prev || n->pt != &n->prev || sea)) {
484          n->opp = head->opp;
485          head->opp->opp = n;
486          n->prev.x += n->pt->y <= n->prev.y ? n->pt->x - n->prev.x :
487            (n->pt->x - n->prev.x) *
488            calcType(head->prev.y - n->prev.y) / (n->pt->y - n->prev.y);
489          n->prev.y = head->prev.y;
490        }
491        else {
492          // Either n is not a replacement for head because one of them is
493          // a left side and the other right side
494          // OR
495          // heap->opp is either left or right and n is either left or right.
496          // and we recently drew all the way to the left or right ("sea").
497          n->opp = &dummy;
498          head->opp->opp = &dummy;
499        }
500      }
501      Delete (head);
502      head = heap[--h];
503    }
504   
505    for (j = 2; j < h; j *= 2) {
506      if (j + 1 < h && heap[j + 1]->pt->y < heap[j]->pt->y) j++;
507      if (heap[j]->pt->y >= head->pt->y) break;
508      heap[j / 2] = heap[j];
509    }
510    heap[j / 2] = head;
511    for (i = 2; i < h; i++) assert (heap[i]->pt->y >= heap[i/2]->pt->y);
512  } // While going through the edges
513  if (sea) { //left.opp == &right) {
514    GdkPoint end[3];
515    end[0].x = -6000;
516    end[0].y = max (left.prev.y, right.prev.y) >> 16;
517    end[1].x = 6000;
518    end[1].y = end[0].y;
519    end[2].x = 0; 
520    end[2].y = 6000;
521    #ifdef ANDROID_NDK
522    glVertexPointer (2, GL_SHORT, 0, end);
523    glDrawArrays (GL_TRIANGLES, 0, 3);
524    #else
525    gdk_draw_polygon (w, gc, TRUE, end, 3);
526    #endif
527  }
528  //free (heap);
529}
530#endif
Note: See TracBrowser for help on using the repository browser.