poly_clip.cpp revision 54b6cfa9a9e5b861a9930af873580d6dc20f773c 
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
36namespace 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
59void 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
107int 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