frameworks/base/core/jni/android/opengl/poly_clip.cpp

   1 /*
   2 **
   3 ** Copyright 2007, The Android Open Source Project
   4 **
   5 ** Licensed under the Apache License, Version 2.0 (the "License");
   6 ** you may not use this file except in compliance with the License.
   7 ** You may obtain a copy of the License at
   8 **
   9 **     http://www.apache.org/licenses/LICENSE-2.0
  10 **
  11 ** Unless required by applicable law or agreed to in writing, software
  12 ** distributed under the License is distributed on an "AS IS" BASIS,
  13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 ** See the License for the specific language governing permissions and
  15 ** limitations under the License.
  16 */
  17
  18 /*
  19  * Generic Convex Polygon Scan Conversion and Clipping
  20  * by Paul Heckbert
  21  * from "Graphics Gems", Academic Press, 1990
  22  */
  23
  24 /* Based on the public domain code:
  25  * poly_clip.c: homogeneous 3-D convex polygon clipper
  26  *
  27  * Paul Heckbert        1985, Dec 1989
  28  */
  29
  30 #include "poly.h"
  31 #include "string.h"
  32
  33 #define LOG_TAG "StreetView"
  34 #include <utils/Log.h>
  35
  36 namespace android {
  37
  38 #define SWAP(a, b, temp)        {temp = a; a = b; b = temp;}
  39 #define COORD(vert, i) ((float *)(vert))[i]
  40
  41 #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  42     poly_clip_to_halfspace(p, q, &v->elem-(float *)v, sign, sign*k); \
  43     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  44     SWAP(p, q, r); \
  45 }
  46
  47 /*
  48  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  49  * copying the portion satisfying sign*s[index] < k*sw into q,
  50  * where s is a Poly_vert* cast as a float*.
  51  * index is an index into the array of floats at each vertex, such that
  52  * s[index] is sx, sy, or sz (screen space x, y, or z).
  53  * Thus, to clip against xmin, use
  54  *      poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  55  * and to clip against xmax, use
  56  *      poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  57  */
  58
  59 void poly_clip_to_halfspace(Poly* p, Poly* q, int index, float sign, float k)
  60 {
  61     unsigned long m;
  62     float *up, *vp, *wp;
  63     Poly_vert *v;
  64     int i;
  65     Poly_vert *u;
  66     float t, tu, tv;
  67
  68     q->n = 0;
  69
  70     /* start with u=vert[n-1], v=vert[0] */
  71     u = &p->vert[p->n-1];
  72     tu = sign*COORD(u, index) - u->sw*k;
  73     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  74         /* on old polygon (p), u is previous vertex, v is current vertex */
  75         /* tv is negative if vertex v is in */
  76         tv = sign*COORD(v, index) - v->sw*k;
  77         if ((tu <= 0.0f) ^ (tv <= 0.0f)) {
  78             /* edge crosses plane; add intersection point to q */
  79             t = tu/(tu-tv);
  80             up = (float *)u;
  81             vp = (float *)v;
  82             wp = (float *)&q->vert[q->n].sx;
  83                 for(int i = 0; i < 4; i++, wp++, up++, vp++) {
  84                         *wp = *up+t*(*vp-*up);
  85                 }
  86             q->n++;
  87         }
  88         if (tv<=0.0f)           /* vertex v is in, copy it to q */
  89             q->vert[q->n++] = *v;
  90     }
  91 }
  92
  93 /*
  94  * poly_clip_to_frustum: Clip the convex polygon p1 to the screen space frustum
  95  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex,
  96  * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1,
  97  * and similar tests for y and z, for each vertex v of the polygon.
  98  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  99  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
 100  * Otherwise, if the polygon is cut by the box, p1 is modified and
 101  * POLY_CLIP_PARTIAL is returned.
 102  *
 103  * Given an n-gon as input, clipping against 6 planes could generate an
 104  * (n+6)gon, so POLY_NMAX in poly.h must be big enough to allow that.
 105  */
 106
 107 int poly_clip_to_frustum(Poly *p1)
 108 {
 109     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0;
 110     int i;
 111     Poly_vert *v;
 112     Poly p2, *p, *q, *r;
 113
 114     /* count vertices "outside" with respect to each of the six planes */
 115     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
 116                 float sw = v->sw;
 117                 if (v->sx < -sw) x0out++;       /* out on left */
 118                 if (v->sx > sw) x1out++;        /* out on right */
 119                 if (v->sy < -sw) y0out++;       /* out on top */
 120                 if (v->sy > sw) y1out++;        /* out on bottom */
 121                 if (v->sz < -sw) z0out++;       /* out on near */
 122                 if (v->sz > sw) z1out++;        /* out on far */
 123     }
 124
 125     /* check if all vertices inside */
 126     if (x0out+x1out+y0out+y1out+z0out+z1out == 0)
 127         return POLY_CLIP_IN;
 128
 129     /* check if all vertices are "outside" any of the six planes */
 130     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
 131         y1out==p1->n || z0out==p1->n || z1out==p1->n) {
 132             p1->n = 0;
 133             return POLY_CLIP_OUT;
 134         }
 135
 136     /*
 137      * now clip against each of the planes that might cut the polygon,
 138      * at each step toggling between polygons p1 and p2
 139      */
 140     p = p1;
 141     q = &p2;
 142     if (x0out) CLIP_AND_SWAP(sx, -1.0f, -1.0f, p, q, r);
 143     if (x1out) CLIP_AND_SWAP(sx,  1.0f, 1.0f, p, q, r);
 144     if (y0out) CLIP_AND_SWAP(sy, -1.0f, -1.0f, p, q, r);
 145     if (y1out) CLIP_AND_SWAP(sy,  1.0f, 1.0f, p, q, r);
 146     if (z0out) CLIP_AND_SWAP(sz, -1.0f, -1.0f, p, q, r);
 147     if (z1out) CLIP_AND_SWAP(sz,  1.0f, 1.0f, p, q, r);
 148
 149     /* if result ended up in p2 then copy it to p1 */
 150     if (p==&p2)
 151         memcpy(p1, &p2, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert));
 152     return POLY_CLIP_PARTIAL;
 153 }
 154
 155 } // namespace android