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

Last change on this file since 34655 was 29825, checked in by nic, 6 years ago

close #4930
close #4502
Silence compiler warnings about unused and uninitialized variables.
Remove some features that were never completed

  • 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;
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  #ifndef AATREE_NOREBALANCE
197  struct PolygonEdge *tmp = leaf->parent == n ? leaf : leaf->parent;
198  #endif
199  if (leaf->parent->left == leaf) leaf->parent->left = NULL;
200  else leaf->parent->right = NULL;
201 
202  if (n != leaf) {
203    if (n->parent->left == n) n->parent->left = leaf;
204    else n->parent->right = leaf;
205    leaf->parent = n->parent;
206    if (n->left) n->left->parent = leaf;
207    leaf->left = n->left;
208    if (n->right) n->right->parent = leaf;
209    leaf->right = n->right;
210    leaf->level = n->level;
211  }
212  #ifndef AATREE_NOREBALANCE
213  // free (n);
214  while (tmp != &root) {
215    // One of tmp's childern had it's level reduced
216    if (tmp->level > (tmp->left ? tmp->left->level + 1 : 1)) { // AA2 failed
217      tmp->level--;
218      if (Split (tmp)) {
219        if (Split (tmp)) Skew (tmp->parent->parent);
220        break;
221      }
222      tmp = tmp->parent;
223    }
224    else if (tmp->level <= (tmp->right ? tmp->right->level + 1 : 1)) break;
225    else { // AA3 failed
226      Skew (tmp);
227      //if (tmp->right) tmp->right->level = tmp->right->left ? tmp->right->left->level + 1 : 1;
228      if (tmp->level > tmp->parent->level) {
229        Skew (tmp);
230        Split (tmp->parent->parent);
231        break;
232      }
233      tmp = tmp->parent->parent;
234    }
235  }
236  #endif
237}
238
239void Check (struct PolygonEdge *n)
240{
241  assert (!n->left || n->left->parent == n);
242  assert (!n->right || n->right->parent == n);
243//  assert (!Next (n) || n->data <= Next (n)->data);
244  assert (!n->parent || n->parent->level >= n->level);
245  assert (n->level == (n->left == NULL ? 1 : n->left->level + 1));
246  assert (n->level <= 1 || (n->right && n->level - n->right->level <= 1));
247  assert (!n->parent || !n->parent->parent ||
248          n->parent->parent->level > n->level);
249}
250
251void Add (struct PolygonEdge *n, struct PolygonEdge *root)
252{
253  struct PolygonEdge *s = root;
254  int lessThan = 1;
255  while (lessThan ? s->left : s->right) {
256    s = lessThan ? s->left : s->right;
257    lessThan = edgeCmp(n, s); //c.operator<(n, s);
258  }
259  if (lessThan) s->left = n;
260  else s->right = n;
261  n->parent = s;
262  #ifdef AATREE_NOREBALANCE
263  n->level = 1;
264  n->left = NULL;
265  n->right = NULL;
266  #else
267  RebalanceAfterLeafAdd (n);
268  #endif
269}
270//----------------------------[ End of AA tree ]----------------------------
271
272int ptSize = 0;
273void AddPolygon (vector<PolygonEdge> &d, FixedPoint *p, int cnt)
274{
275  int i, j, k, firstd = d.size();
276  ptSize = cnt;
277  for (j = cnt - 1; j > 0 && (p[j - 1].y == p[j].y || // p[j..cnt-1] becomes
278    (p[j - 1].y < p[j].y) == (p[j].y < p[0].y)); j--) {} // monotone
279  //if (j == 0) return; // Polygon has no height but it does not cause infinite loop
280  for (i = 0; i < j && (p[i].y == p[i + 1].y ||
281    (p[i].y < p[i + 1].y) == (p[j].y < p[0].y)); i++) {}
282  // Now p[cn-1],p[0..i] is the longest monotone sequence
283  d.resize (firstd + 2);
284  memset (&d[firstd], 0, sizeof (d[0]) * 2); // TODO: remove
285  d[firstd].delta = p[j].y < p[0].y ? 1 : -1;
286  d[firstd].continues = 1;
287  d[firstd + 1].delta = p[j].y < p[0].y ? 1 : -1;
288  d[firstd + 1].continues = 0;
289  d[firstd + !(p[j].y < p[0].y)].cnt = cnt - j;
290  d[firstd + (p[j].y < p[0].y)].cnt = i + 1;
291  d[firstd + !(p[j].y < p[0].y)].pt = p + (p[j].y < p[0].y ? j : cnt - 1);
292  d[firstd + (p[j].y < p[0].y)].pt = p + (p[j].y < p[0].y ? 0 : i);
293  //int lowest = j;
294  for (; i < j ; i = k) {
295    //if (p[lowest].y > p[i].y) lowest = i;
296    for (k = i + 1; k < j && (p[k].y == p[k + 1].y || // p[i..k] becomes
297        (p[k].y < p[k + 1].y) == (p[i].y < p[k].y)); k++) {} // monotone
298    d.push_back(PolygonEdge());
299    memset (&d.back(), 0, sizeof (d[0])); // TODO: remove
300    d[d.size() - 1].pt = p + (p[i].y < p[k].y ? i : k);
301    d[d.size() - 1].delta = p[i].y < p[k].y ? 1 : -1;
302    d[d.size() - 1].continues = 0;
303    d[d.size() - 1].cnt = k - i + 1;
304  }
305/*  GdkPoint *ll = &p[lowest], *lr = &p[lowest];
306  do {
307    if (--ll < p) ll = p + cnt - 1;
308  } while (ll->y <= p[lowest].y);
309  do {
310    if (++lr >= p + cnt) lr = p;
311  } while (lr->y <= p[lowest].y);*/
312  calcType area = p[cnt-1].x * (calcType) p[0].y - p[0].x * (calcType) p[cnt-1].y;
313  for (i = 0; i < cnt - 1; i++) area += p[i].x*(calcType)p[i+1].y-
314    p[i+1].x * (calcType) p[i].y;
315  for (i = firstd; i < (int) d.size(); i++) {
316    // This ll/lr inequality is a cross product that is true if the polygon
317    // was clockwise. AddInnerPoly() will just negate isLeft.
318    d[i].isLeft = (area < 0) == (d[i].delta == 1);
319  }
320}
321
322void AddClockwise (vector<PolygonEdge> &d, FixedPoint *p, int cnt)
323{
324  int i, j;
325  #if 0
326  for (i = 0; i < cnt; i++) __android_log_print (ANDROID_LOG_WARN, "Gosmore",
327    "pt[ptCnt].x = %d; pt[ptCnt++].y=%d;", p[i].x, p[i].y);
328  __android_log_print (ANDROID_LOG_WARN, "Gosmore", "AddClockwise(d,pt,ptCnt); ptCnt = 0;");
329  #endif
330  for (i = 0; i < cnt - 1 && p[i].y == p[0].y; i++) {}
331  int up = p[i].y > p[0].y;
332  for (i = 0; i < cnt - 1; i = j) {
333    d.push_back(PolygonEdge());
334    memset (&d.back(), 0, sizeof (d[0])); //TODO: remove
335    for (j = i; j + 1 < cnt &&
336      (up ? p[j + 1].y >= p[j].y : p[j + 1].y <= p[j].y); j++) {}
337    d[d.size() - 1].pt = up ? p + i : p + j;
338    d[d.size() - 1].delta = up ? 1 : -1;
339    d[d.size() - 1].isLeft = up;
340    d[d.size() - 1].cnt = j - i + 1;
341    d[d.size() - 1].continues = 0;
342    up = !up;
343  }
344}
345
346#ifdef ANDROID_NDK
347void Fill (vector<PolygonEdge> &d,int isSea)
348#else
349void Fill (vector<PolygonEdge> &d,int isSea, GdkWindow *w, GdkGC *gc)
350#endif
351{
352  //PolygonEdge **heap = (PolygonEdge **) malloc ((d.size() + 1) * sizeof (*heap));
353  vector<PolygonEdge*> heap;
354  heap.resize (d.size() + 1);
355  memset (&heap[0], 0, sizeof (heap[0]) * (d.size()+1)); // TODO: remove
356  // leave heap[0] open to make indexing easier
357  int i, h = 1, j, sea = 0, start = 1;
358  PolygonEdge dummy, left, right, root;
359 
360  root.left = NULL;
361  root.right = NULL;
362  root.level = 1000000;
363  root.parent = NULL;
364 
365/*  for (i = 0; i < d.size(); i++) {
366    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);
367    if (d[i].continues)                assert (d[i].pt[j*d[i].delta].y <= d[i+1].pt->y);
368  } // Make sure AddPolygon() and variants are correct */
369  dummy.opp = &dummy;
370  for (i = 0; i < (int) d.size(); i++) {
371    for (j = h++; j > 1 && heap[j / 2]->pt->y > d[i].pt->y; j /= 2) {
372      heap[j] = heap[j/2];
373    }
374    heap[j] = &d[i];
375    d[i].opp = NULL;
376    memcpy (&d[i].prev, d[i].pt, sizeof (d[i].prev)); // This is only
377    // to make the compare work.
378    if (d[i].continues) ++i; // Don't add the second part to the heap
379  }
380  //for (i = 2; i < h; i++) assert (heap[i]->pt->y >= heap[i/2]->pt->y);
381  left.prev.x = -6000*65536;
382  left.prev.y = 0;
383  left.opp = &dummy;
384  //h < 3 || edgeCmp (heap[1],
385  //                heap[h == 3 || heap[2]->pt->y < heap[3]->pt->y ? 2 : 3])
386  //          != !heap[1]->isLeft ? &dummy : &right;
387  left.pt = &left.prev;
388  left.isLeft = 1;
389  Add (&left, &root);
390  right.prev.x = 6000*65536;
391  right.prev.y = 0;
392  right.opp = &dummy; //left.opp == &dummy ? &dummy : &left;
393  right.pt = &right.prev;
394  right.isLeft = 0;
395  Add (&right, &root);
396  while (h > 1) {
397    PolygonEdge *head = heap[1];
398    //printf ("%p %3d\n", head->opp, head->pt->y);
399    if (!head->opp) { // Insert it
400      Add (head, &root);
401      head->opp = head->isLeft ? Next (head) : Prev (head);
402      if (head->opp == NULL || head->opp->isLeft == head->isLeft) {
403        head->opp = &dummy;
404      }
405    }
406    PolygonEdge *o = head->opp;
407    /* Now we render the trapezium between head->opp and head->opp->opp up
408       to head->pt->y */
409    if (o != &dummy && o->opp != &dummy) {
410      GdkPoint q[6];
411      #define CLAMPX(x) (short)((x) >= (1<<29) ? 8191 : (x) < -(1<<29) ? -8191 : (x) >> 16)
412      q[2].x = CLAMPX (o->opp->prev.x);
413      q[2].y = CLAMPX (o->opp->prev.y);
414      q[3].x = CLAMPX (o->prev.x);
415      q[3].y = CLAMPX (o->prev.y);
416      o->prev.x = o->pt->y <= o->prev.y ? o->pt->x
417        : o->prev.x + (o->pt->x - o->prev.x) *
418            calcType (head->pt->y - o->prev.y) / (o->pt->y - o->prev.y);
419      q[0].x = CLAMPX(o->prev.x);
420      o->prev.y = head->pt->y;
421      q[0].y = CLAMPX(o->prev.y);
422      o->opp->prev.x = o->opp->pt->y <= o->opp->prev.y ? o->opp->pt->x
423        : o->opp->prev.x + (o->opp->pt->x - o->opp->prev.x) *
424      calcType (head->pt->y - o->opp->prev.y) / (o->opp->pt->y - o->opp->prev.y);
425      q[1].x = CLAMPX (o->opp->prev.x);
426      o->opp->prev.y = head->pt->y;
427      q[1].y = q[0].y;
428    //if (o->opp->prev.y != o->prev.y && o->opp->prev.x < 30000 &&
429    //  o->opp->prev.x > -30000 && o->prev.x < 30000 && o->prev.x > -30000)
430    //  __android_log_print (ANDROID_LOG_WARN, "Gosmore", "Prev dif");
431      if ((isSea || (o->pt != &o->prev && o->opp->pt != &o->opp->prev)) &&
432          q[o->pt == &o->prev ? 2 : 3].y < q[0].y) {
433      // Frequently it happens that one of the triangles has 0 area because
434      // two of the points are equal. TODO: Filter them out.
435        #ifdef ANDROID_NDK
436        memcpy (&q[4], &q[0], sizeof (q[4]));
437        memcpy (&q[5], &q[2], sizeof (q[5]));
438        glVertexPointer (2, GL_SHORT, 0, q);
439        glDrawArrays (GL_TRIANGLES, 0, 6);
440        #else
441        //memcpy (&q[2], &o->prev, sizeof (q[2]));
442        //memcpy (&q[3], &o->opp->prev, sizeof (q[3]));
443        gdk_draw_polygon (w, gc, TRUE, q, 4);
444        #endif
445        if (q[0].x > 100 && q[1].x <= 100) sea = o->opp == &left;
446        if (q[0].x <= 100 && q[1].x < 100) sea = o->opp == &right;
447        if (q[1].x > 100 && q[0].x <= 100) sea = o == &left;
448        if (q[1].x <= 100 && q[0].x < 100) sea = o == &right;
449       
450        if (start) {
451          start = 0;
452          if (sea) {
453            q[2].x = -6000;
454            q[3].x = 6000;
455            q[4].x = 0;
456            q[4].y = -6000;
457            #ifdef ANDROID_NDK
458            glVertexPointer (2, GL_SHORT, 0, q + 2);
459            glDrawArrays (GL_TRIANGLES, 0, 3);
460            #else
461            //memcpy (&q[2], &o->prev, sizeof (q[2]));
462            //memcpy (&q[3], &o->opp->prev, sizeof (q[3]));
463            gdk_draw_polygon (w, gc, TRUE, q + 2, 3);
464            #endif
465          }
466        }
467      } // If the trapezium has a non-zero height
468    }
469    if (o != &dummy && o->opp != head) {
470      o->opp->opp = &dummy; // Complete the 'Add'
471      o->opp = head;
472    }
473
474    if (--head->cnt) head->pt += head->delta;
475    else if (head->continues) {
476      head->continues = head[1].continues;
477      head->cnt = head[1].cnt;
478      head->pt = head[1].pt;
479    }
480    else { // Remove it
481      head->opp->opp = &dummy;
482      PolygonEdge *n = head->isLeft ? Prev (head) : Next (head);
483      if (n && n->opp == &dummy) {
484        if (head->isLeft == n->isLeft && 
485          (head->opp->pt != &head->opp->prev || n->pt != &n->prev || sea)) {
486          n->opp = head->opp;
487          head->opp->opp = n;
488          n->prev.x += n->pt->y <= n->prev.y ? n->pt->x - n->prev.x :
489            (n->pt->x - n->prev.x) *
490            calcType(head->prev.y - n->prev.y) / (n->pt->y - n->prev.y);
491          n->prev.y = head->prev.y;
492        }
493        else {
494          // Either n is not a replacement for head because one of them is
495          // a left side and the other right side
496          // OR
497          // heap->opp is either left or right and n is either left or right.
498          // and we recently drew all the way to the left or right ("sea").
499          n->opp = &dummy;
500          head->opp->opp = &dummy;
501        }
502      }
503      Delete (head);
504      head = heap[--h];
505    }
506   
507    for (j = 2; j < h; j *= 2) {
508      if (j + 1 < h && heap[j + 1]->pt->y < heap[j]->pt->y) j++;
509      if (heap[j]->pt->y >= head->pt->y) break;
510      heap[j / 2] = heap[j];
511    }
512    heap[j / 2] = head;
513    for (i = 2; i < h; i++) assert (heap[i]->pt->y >= heap[i/2]->pt->y);
514  } // While going through the edges
515  if (sea) { //left.opp == &right) {
516    GdkPoint end[3];
517    end[0].x = -6000;
518    end[0].y = max (left.prev.y, right.prev.y) >> 16;
519    end[1].x = 6000;
520    end[1].y = end[0].y;
521    end[2].x = 0; 
522    end[2].y = 6000;
523    #ifdef ANDROID_NDK
524    glVertexPointer (2, GL_SHORT, 0, end);
525    glDrawArrays (GL_TRIANGLES, 0, 3);
526    #else
527    gdk_draw_polygon (w, gc, TRUE, end, 3);
528    #endif
529  }
530  //free (heap);
531}
532#endif
Note: See TracBrowser for help on using the repository browser.