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 156
