19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** Copyright 2007, The Android Open Source Project 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** Licensed under the Apache License, Version 2.0 (the "License"); 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** you may not use this file except in compliance with the License. 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** You may obtain a copy of the License at 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** http://www.apache.org/licenses/LICENSE-2.0 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** Unless required by applicable law or agreed to in writing, software 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** distributed under the License is distributed on an "AS IS" BASIS, 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** See the License for the specific language governing permissions and 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project** limitations under the License. 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project*/ 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Generic Convex Polygon Scan Conversion and Clipping 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * by Paul Heckbert 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * from "Graphics Gems", Academic Press, 1990 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* Based on the public domain code: 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * poly_clip.c: homogeneous 3-D convex polygon clipper 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Paul Heckbert 1985, Dec 1989 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "poly.h" 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include "string.h" 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define LOG_TAG "StreetView" 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#include <utils/Log.h> 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectnamespace android { 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define SWAP(a, b, temp) {temp = a; a = b; b = temp;} 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define COORD(vert, i) ((float *)(vert))[i] 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project#define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \ 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project poly_clip_to_halfspace(p, q, &v->elem-(float *)v, sign, sign*k); \ 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \ 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project SWAP(p, q, r); \ 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * poly_clip_to_halfspace: clip convex polygon p against a plane, 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * copying the portion satisfying sign*s[index] < k*sw into q, 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * where s is a Poly_vert* cast as a float*. 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * index is an index into the array of floats at each vertex, such that 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * s[index] is sx, sy, or sz (screen space x, y, or z). 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Thus, to clip against xmin, use 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin); 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * and to clip against xmax, use 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * poly_clip_to_halfspace(p, q, XINDEX, 1., xmax); 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectvoid poly_clip_to_halfspace(Poly* p, Poly* q, int index, float sign, float k) 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project float *up, *vp, *wp; 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Poly_vert *v; 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i; 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Poly_vert *u; 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project float t, tu, tv; 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project q->n = 0; 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* start with u=vert[n-1], v=vert[0] */ 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project u = &p->vert[p->n-1]; 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project tu = sign*COORD(u, index) - u->sw*k; 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) { 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* on old polygon (p), u is previous vertex, v is current vertex */ 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* tv is negative if vertex v is in */ 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project tv = sign*COORD(v, index) - v->sw*k; 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if ((tu <= 0.0f) ^ (tv <= 0.0f)) { 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* edge crosses plane; add intersection point to q */ 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project t = tu/(tu-tv); 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project up = (float *)u; 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project vp = (float *)v; 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project wp = (float *)&q->vert[q->n].sx; 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for(int i = 0; i < 4; i++, wp++, up++, vp++) { 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project *wp = *up+t*(*vp-*up); 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project q->n++; 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (tv<=0.0f) /* vertex v is in, copy it to q */ 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project q->vert[q->n++] = *v; 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * poly_clip_to_frustum: Clip the convex polygon p1 to the screen space frustum 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex, 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1, 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * and similar tests for y and z, for each vertex v of the polygon. 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * If polygon is entirely inside box, then POLY_CLIP_IN is returned. 989066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * If polygon is entirely outside box, then POLY_CLIP_OUT is returned. 999066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Otherwise, if the polygon is cut by the box, p1 is modified and 1009066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * POLY_CLIP_PARTIAL is returned. 1019066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 1029066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Given an n-gon as input, clipping against 6 planes could generate an 1039066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * (n+6)gon, so POLY_NMAX in poly.h must be big enough to allow that. 1049066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1059066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1069066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectint poly_clip_to_frustum(Poly *p1) 1079066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project{ 1089066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0; 1099066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int i; 1109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Poly_vert *v; 1119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Poly p2, *p, *q, *r; 1129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* count vertices "outside" with respect to each of the six planes */ 1149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project for (v=p1->vert, i=p1->n; i>0; i--, v++) { 1159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project float sw = v->sw; 1169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sx < -sw) x0out++; /* out on left */ 1179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sx > sw) x1out++; /* out on right */ 1189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sy < -sw) y0out++; /* out on top */ 1199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sy > sw) y1out++; /* out on bottom */ 1209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sz < -sw) z0out++; /* out on near */ 1219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (v->sz > sw) z1out++; /* out on far */ 1229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* check if all vertices inside */ 1259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x0out+x1out+y0out+y1out+z0out+z1out == 0) 1269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return POLY_CLIP_IN; 1279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* check if all vertices are "outside" any of the six planes */ 1299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x0out==p1->n || x1out==p1->n || y0out==p1->n || 1309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project y1out==p1->n || z0out==p1->n || z1out==p1->n) { 1319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p1->n = 0; 1329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return POLY_CLIP_OUT; 1339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 1349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* 1369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * now clip against each of the planes that might cut the polygon, 1379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * at each step toggling between polygons p1 and p2 1389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 1399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project p = p1; 1409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project q = &p2; 1419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x0out) CLIP_AND_SWAP(sx, -1.0f, -1.0f, p, q, r); 1429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (x1out) CLIP_AND_SWAP(sx, 1.0f, 1.0f, p, q, r); 1439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (y0out) CLIP_AND_SWAP(sy, -1.0f, -1.0f, p, q, r); 1449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (y1out) CLIP_AND_SWAP(sy, 1.0f, 1.0f, p, q, r); 1459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (z0out) CLIP_AND_SWAP(sz, -1.0f, -1.0f, p, q, r); 1469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (z1out) CLIP_AND_SWAP(sz, 1.0f, 1.0f, p, q, r); 1479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /* if result ended up in p2 then copy it to p1 */ 1499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (p==&p2) 1509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project memcpy(p1, &p2, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert)); 1519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return POLY_CLIP_PARTIAL; 1529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 1539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 1549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} // namespace android 155