The Android Open Source Project | 9066cfe | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | |
Chih-Hung Hsieh | cef190d | 2016-05-19 15:25:50 -0700 | [diff] [blame] | 38 | #define SWAP(a, b, temp) {(temp) = a; (a) = b; (b) = temp;} |
The Android Open Source Project | 9066cfe | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 39 | #define COORD(vert, i) ((float *)(vert))[i] |
| 40 | |
| 41 | #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \ |
Chih-Hung Hsieh | cef190d | 2016-05-19 15:25:50 -0700 | [diff] [blame] | 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;} \ |
The Android Open Source Project | 9066cfe | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 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 | { |
The Android Open Source Project | 9066cfe | 2009-03-03 19:31:44 -0800 | [diff] [blame] | 61 | float *up, *vp, *wp; |
| 62 | Poly_vert *v; |
| 63 | int i; |
| 64 | Poly_vert *u; |
| 65 | float t, tu, tv; |
| 66 | |
| 67 | q->n = 0; |
| 68 | |
| 69 | /* start with u=vert[n-1], v=vert[0] */ |
| 70 | u = &p->vert[p->n-1]; |
| 71 | tu = sign*COORD(u, index) - u->sw*k; |
| 72 | for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) { |
| 73 | /* on old polygon (p), u is previous vertex, v is current vertex */ |
| 74 | /* tv is negative if vertex v is in */ |
| 75 | tv = sign*COORD(v, index) - v->sw*k; |
| 76 | if ((tu <= 0.0f) ^ (tv <= 0.0f)) { |
| 77 | /* edge crosses plane; add intersection point to q */ |
| 78 | t = tu/(tu-tv); |
| 79 | up = (float *)u; |
| 80 | vp = (float *)v; |
| 81 | wp = (float *)&q->vert[q->n].sx; |
| 82 | for(int i = 0; i < 4; i++, wp++, up++, vp++) { |
| 83 | *wp = *up+t*(*vp-*up); |
| 84 | } |
| 85 | q->n++; |
| 86 | } |
| 87 | if (tv<=0.0f) /* vertex v is in, copy it to q */ |
| 88 | q->vert[q->n++] = *v; |
| 89 | } |
| 90 | } |
| 91 | |
| 92 | /* |
| 93 | * poly_clip_to_frustum: Clip the convex polygon p1 to the screen space frustum |
| 94 | * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex, |
| 95 | * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1, |
| 96 | * and similar tests for y and z, for each vertex v of the polygon. |
| 97 | * If polygon is entirely inside box, then POLY_CLIP_IN is returned. |
| 98 | * If polygon is entirely outside box, then POLY_CLIP_OUT is returned. |
| 99 | * Otherwise, if the polygon is cut by the box, p1 is modified and |
| 100 | * POLY_CLIP_PARTIAL is returned. |
| 101 | * |
| 102 | * Given an n-gon as input, clipping against 6 planes could generate an |
| 103 | * (n+6)gon, so POLY_NMAX in poly.h must be big enough to allow that. |
| 104 | */ |
| 105 | |
| 106 | int poly_clip_to_frustum(Poly *p1) |
| 107 | { |
| 108 | int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0; |
| 109 | int i; |
| 110 | Poly_vert *v; |
| 111 | Poly p2, *p, *q, *r; |
| 112 | |
| 113 | /* count vertices "outside" with respect to each of the six planes */ |
| 114 | for (v=p1->vert, i=p1->n; i>0; i--, v++) { |
| 115 | float sw = v->sw; |
| 116 | if (v->sx < -sw) x0out++; /* out on left */ |
| 117 | if (v->sx > sw) x1out++; /* out on right */ |
| 118 | if (v->sy < -sw) y0out++; /* out on top */ |
| 119 | if (v->sy > sw) y1out++; /* out on bottom */ |
| 120 | if (v->sz < -sw) z0out++; /* out on near */ |
| 121 | if (v->sz > sw) z1out++; /* out on far */ |
| 122 | } |
| 123 | |
| 124 | /* check if all vertices inside */ |
| 125 | if (x0out+x1out+y0out+y1out+z0out+z1out == 0) |
| 126 | return POLY_CLIP_IN; |
| 127 | |
| 128 | /* check if all vertices are "outside" any of the six planes */ |
| 129 | if (x0out==p1->n || x1out==p1->n || y0out==p1->n || |
| 130 | y1out==p1->n || z0out==p1->n || z1out==p1->n) { |
| 131 | p1->n = 0; |
| 132 | return POLY_CLIP_OUT; |
| 133 | } |
| 134 | |
| 135 | /* |
| 136 | * now clip against each of the planes that might cut the polygon, |
| 137 | * at each step toggling between polygons p1 and p2 |
| 138 | */ |
| 139 | p = p1; |
| 140 | q = &p2; |
| 141 | if (x0out) CLIP_AND_SWAP(sx, -1.0f, -1.0f, p, q, r); |
| 142 | if (x1out) CLIP_AND_SWAP(sx, 1.0f, 1.0f, p, q, r); |
| 143 | if (y0out) CLIP_AND_SWAP(sy, -1.0f, -1.0f, p, q, r); |
| 144 | if (y1out) CLIP_AND_SWAP(sy, 1.0f, 1.0f, p, q, r); |
| 145 | if (z0out) CLIP_AND_SWAP(sz, -1.0f, -1.0f, p, q, r); |
| 146 | if (z1out) CLIP_AND_SWAP(sz, 1.0f, 1.0f, p, q, r); |
| 147 | |
| 148 | /* if result ended up in p2 then copy it to p1 */ |
| 149 | if (p==&p2) |
| 150 | memcpy(p1, &p2, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert)); |
| 151 | return POLY_CLIP_PARTIAL; |
| 152 | } |
| 153 | |
| 154 | } // namespace android |