| 1 | /* Copyright (c) 2001, Stanford University
|
|---|
| 2 | * All rights reserved
|
|---|
| 3 | *
|
|---|
| 4 | * See the file LICENSE.txt for information on redistributing this software.
|
|---|
| 5 | */
|
|---|
| 6 |
|
|---|
| 7 | #include <float.h>
|
|---|
| 8 | #include "cr_bbox.h"
|
|---|
| 9 |
|
|---|
| 10 | /**
|
|---|
| 11 | * \mainpage Util
|
|---|
| 12 | *
|
|---|
| 13 | * \section UtilIntroduction Introduction
|
|---|
| 14 | *
|
|---|
| 15 | * Chromium consists of all the top-level files in the cr
|
|---|
| 16 | * directory. The util module basically takes care of API dispatch,
|
|---|
| 17 | * and OpenGL state management.
|
|---|
| 18 | *
|
|---|
| 19 | */
|
|---|
| 20 | static float _vmult(const float *m, float x, float y, float z)
|
|---|
| 21 | {
|
|---|
| 22 | return m[0]*x + m[4]*y + m[8]*z + m[12];
|
|---|
| 23 | }
|
|---|
| 24 |
|
|---|
| 25 | void
|
|---|
| 26 | crTransformBBox( float xmin, float ymin, float zmin,
|
|---|
| 27 | float xmax, float ymax, float zmax,
|
|---|
| 28 | const CRmatrix *m,
|
|---|
| 29 | float *out_xmin, float *out_ymin, float *out_zmin,
|
|---|
| 30 | float *out_xmax, float *out_ymax, float *out_zmax )
|
|---|
| 31 | {
|
|---|
| 32 | float x[8], y[8], z[8], w[8];
|
|---|
| 33 | int i,j;
|
|---|
| 34 |
|
|---|
| 35 | /* Here is the arrangement of the bounding box
|
|---|
| 36 | *
|
|---|
| 37 | * 0 --- 1
|
|---|
| 38 | * |\ .\
|
|---|
| 39 | * | 2 --- 3
|
|---|
| 40 | * | | . |
|
|---|
| 41 | * | | . |
|
|---|
| 42 | * 4.|...5 |
|
|---|
| 43 | * \| .|
|
|---|
| 44 | * 6 --- 7
|
|---|
| 45 | *
|
|---|
| 46 | * c array contains the edge connectivitiy list
|
|---|
| 47 | */
|
|---|
| 48 |
|
|---|
| 49 | static const int c[8][3] = {
|
|---|
| 50 | {1, 2, 4},
|
|---|
| 51 | {0, 3, 5},
|
|---|
| 52 | {0, 3, 6},
|
|---|
| 53 | {1, 2, 7},
|
|---|
| 54 | {0, 5, 6},
|
|---|
| 55 | {1, 4, 7},
|
|---|
| 56 | {2, 4, 7},
|
|---|
| 57 | {3, 5, 6}
|
|---|
| 58 | };
|
|---|
| 59 |
|
|---|
| 60 | x[0] = _vmult(&(m->m00), xmin, ymin, zmin);
|
|---|
| 61 | x[1] = _vmult(&(m->m00), xmax, ymin, zmin);
|
|---|
| 62 | x[2] = _vmult(&(m->m00), xmin, ymax, zmin);
|
|---|
| 63 | x[3] = _vmult(&(m->m00), xmax, ymax, zmin);
|
|---|
| 64 | x[4] = _vmult(&(m->m00), xmin, ymin, zmax);
|
|---|
| 65 | x[5] = _vmult(&(m->m00), xmax, ymin, zmax);
|
|---|
| 66 | x[6] = _vmult(&(m->m00), xmin, ymax, zmax);
|
|---|
| 67 | x[7] = _vmult(&(m->m00), xmax, ymax, zmax);
|
|---|
| 68 |
|
|---|
| 69 | y[0] = _vmult(&(m->m01), xmin, ymin, zmin);
|
|---|
| 70 | y[1] = _vmult(&(m->m01), xmax, ymin, zmin);
|
|---|
| 71 | y[2] = _vmult(&(m->m01), xmin, ymax, zmin);
|
|---|
| 72 | y[3] = _vmult(&(m->m01), xmax, ymax, zmin);
|
|---|
| 73 | y[4] = _vmult(&(m->m01), xmin, ymin, zmax);
|
|---|
| 74 | y[5] = _vmult(&(m->m01), xmax, ymin, zmax);
|
|---|
| 75 | y[6] = _vmult(&(m->m01), xmin, ymax, zmax);
|
|---|
| 76 | y[7] = _vmult(&(m->m01), xmax, ymax, zmax);
|
|---|
| 77 |
|
|---|
| 78 | z[0] = _vmult(&(m->m02), xmin, ymin, zmin);
|
|---|
| 79 | z[1] = _vmult(&(m->m02), xmax, ymin, zmin);
|
|---|
| 80 | z[2] = _vmult(&(m->m02), xmin, ymax, zmin);
|
|---|
| 81 | z[3] = _vmult(&(m->m02), xmax, ymax, zmin);
|
|---|
| 82 | z[4] = _vmult(&(m->m02), xmin, ymin, zmax);
|
|---|
| 83 | z[5] = _vmult(&(m->m02), xmax, ymin, zmax);
|
|---|
| 84 | z[6] = _vmult(&(m->m02), xmin, ymax, zmax);
|
|---|
| 85 | z[7] = _vmult(&(m->m02), xmax, ymax, zmax);
|
|---|
| 86 |
|
|---|
| 87 | w[0] = _vmult(&(m->m03), xmin, ymin, zmin);
|
|---|
| 88 | w[1] = _vmult(&(m->m03), xmax, ymin, zmin);
|
|---|
| 89 | w[2] = _vmult(&(m->m03), xmin, ymax, zmin);
|
|---|
| 90 | w[3] = _vmult(&(m->m03), xmax, ymax, zmin);
|
|---|
| 91 | w[4] = _vmult(&(m->m03), xmin, ymin, zmax);
|
|---|
| 92 | w[5] = _vmult(&(m->m03), xmax, ymin, zmax);
|
|---|
| 93 | w[6] = _vmult(&(m->m03), xmin, ymax, zmax);
|
|---|
| 94 | w[7] = _vmult(&(m->m03), xmax, ymax, zmax);
|
|---|
| 95 |
|
|---|
| 96 | /* Now, the object-space bbox has been transformed into
|
|---|
| 97 | * clip-space. */
|
|---|
| 98 |
|
|---|
| 99 | /* Find the 2D bounding box of the 3D bounding box */
|
|---|
| 100 | xmin = ymin = zmin = FLT_MAX;
|
|---|
| 101 | xmax = ymax = zmax = -FLT_MAX;
|
|---|
| 102 |
|
|---|
| 103 | for (i=0; i<8; i++)
|
|---|
| 104 | {
|
|---|
| 105 | float xp = x[i];
|
|---|
| 106 | float yp = y[i];
|
|---|
| 107 | float zp = z[i];
|
|---|
| 108 | float wp = w[i];
|
|---|
| 109 |
|
|---|
| 110 | /* If corner is to be clipped... */
|
|---|
| 111 | if (zp < -wp)
|
|---|
| 112 | {
|
|---|
| 113 |
|
|---|
| 114 | /* Point has three edges */
|
|---|
| 115 | for (j=0; j<3; j++)
|
|---|
| 116 | {
|
|---|
| 117 | /* Handle the clipping... */
|
|---|
| 118 | int k = c[i][j];
|
|---|
| 119 | float xk = x[k];
|
|---|
| 120 | float yk = y[k];
|
|---|
| 121 | float zk = z[k];
|
|---|
| 122 | float wk = w[k];
|
|---|
| 123 | float t;
|
|---|
| 124 |
|
|---|
| 125 | if (zp+wp-zk-wk == 0.0)
|
|---|
| 126 | continue; /* avoid divide by zero */
|
|---|
| 127 | else
|
|---|
| 128 | t = (wp + zp) / (zp+wp-zk-wk);
|
|---|
| 129 |
|
|---|
| 130 | if (t < 0.0f || t > 1.0f)
|
|---|
| 131 | {
|
|---|
| 132 | continue;
|
|---|
| 133 | }
|
|---|
| 134 | wp = wp + (wk-wp) * t;
|
|---|
| 135 | xp = xp + (xk-xp) * t;
|
|---|
| 136 | yp = yp + (yk-yp) * t;
|
|---|
| 137 | zp = -wp;
|
|---|
| 138 |
|
|---|
| 139 | xp /= wp;
|
|---|
| 140 | yp /= wp;
|
|---|
| 141 | zp /= wp;
|
|---|
| 142 |
|
|---|
| 143 | if (xp < xmin) xmin = xp;
|
|---|
| 144 | if (xp > xmax) xmax = xp;
|
|---|
| 145 | if (yp < ymin) ymin = yp;
|
|---|
| 146 | if (yp > ymax) ymax = yp;
|
|---|
| 147 | if (zp < zmin) zmin = zp;
|
|---|
| 148 | if (zp > zmax) zmax = zp;
|
|---|
| 149 | }
|
|---|
| 150 | }
|
|---|
| 151 | else
|
|---|
| 152 | {
|
|---|
| 153 | /* corner was not clipped.. */
|
|---|
| 154 | xp /= wp;
|
|---|
| 155 | yp /= wp;
|
|---|
| 156 | zp /= wp;
|
|---|
| 157 | if (xp < xmin) xmin = xp;
|
|---|
| 158 | if (xp > xmax) xmax = xp;
|
|---|
| 159 | if (yp < ymin) ymin = yp;
|
|---|
| 160 | if (yp > ymax) ymax = yp;
|
|---|
| 161 | if (zp < zmin) zmin = zp;
|
|---|
| 162 | if (zp > zmax) zmax = zp;
|
|---|
| 163 | }
|
|---|
| 164 | }
|
|---|
| 165 |
|
|---|
| 166 | /* Copy for export */
|
|---|
| 167 | if (out_xmin) *out_xmin = xmin;
|
|---|
| 168 | if (out_ymin) *out_ymin = ymin;
|
|---|
| 169 | if (out_zmin) *out_zmin = zmin;
|
|---|
| 170 | if (out_xmax) *out_xmax = xmax;
|
|---|
| 171 | if (out_ymax) *out_ymax = ymax;
|
|---|
| 172 | if (out_zmax) *out_zmax = zmax;
|
|---|
| 173 | }
|
|---|
| 174 |
|
|---|
| 175 | /**
|
|---|
| 176 | * Given the coordinates of the two opposite corners of a bounding box
|
|---|
| 177 | * in object space (x1,y1,z1) and (x2,y2,z2), use the given modelview
|
|---|
| 178 | * and projection matrices to transform the coordinates to NDC space.
|
|---|
| 179 | * Find the 3D bounding bounding box of those eight coordinates and
|
|---|
| 180 | * return the min/max in (x1,y1,x1) and (x2,y2,z2).
|
|---|
| 181 | */
|
|---|
| 182 | void
|
|---|
| 183 | crProjectBBox(const GLfloat modl[16], const GLfloat proj[16],
|
|---|
| 184 | GLfloat *x1, GLfloat *y1, GLfloat *z1,
|
|---|
| 185 | GLfloat *x2, GLfloat *y2, GLfloat *z2)
|
|---|
| 186 | {
|
|---|
| 187 | CRmatrix m;
|
|---|
| 188 |
|
|---|
| 189 | /* compute product of modl and proj matrices */
|
|---|
| 190 | m.m00 = proj[0] * modl[0] + proj[4] * modl[1] + proj[8] * modl[2] + proj[12] * modl[3];
|
|---|
| 191 | m.m01 = proj[1] * modl[0] + proj[5] * modl[1] + proj[9] * modl[2] + proj[13] * modl[3];
|
|---|
| 192 | m.m02 = proj[2] * modl[0] + proj[6] * modl[1] + proj[10] * modl[2] + proj[14] * modl[3];
|
|---|
| 193 | m.m03 = proj[3] * modl[0] + proj[7] * modl[1] + proj[11] * modl[2] + proj[15] * modl[3];
|
|---|
| 194 | m.m10 = proj[0] * modl[4] + proj[4] * modl[5] + proj[8] * modl[6] + proj[12] * modl[7];
|
|---|
| 195 | m.m11 = proj[1] * modl[4] + proj[5] * modl[5] + proj[9] * modl[6] + proj[13] * modl[7];
|
|---|
| 196 | m.m12 = proj[2] * modl[4] + proj[6] * modl[5] + proj[10] * modl[6] + proj[14] * modl[7];
|
|---|
| 197 | m.m13 = proj[3] * modl[4] + proj[7] * modl[5] + proj[11] * modl[6] + proj[15] * modl[7];
|
|---|
| 198 | m.m20 = proj[0] * modl[8] + proj[4] * modl[9] + proj[8] * modl[10] + proj[12] * modl[11];
|
|---|
| 199 | m.m21 = proj[1] * modl[8] + proj[5] * modl[9] + proj[9] * modl[10] + proj[13] * modl[11];
|
|---|
| 200 | m.m22 = proj[2] * modl[8] + proj[6] * modl[9] + proj[10] * modl[10] + proj[14] * modl[11];
|
|---|
| 201 | m.m23 = proj[3] * modl[8] + proj[7] * modl[9] + proj[11] * modl[10] + proj[15] * modl[11];
|
|---|
| 202 | m.m30 = proj[0] * modl[12] + proj[4] * modl[13] + proj[8] * modl[14] + proj[12] * modl[15];
|
|---|
| 203 | m.m31 = proj[1] * modl[12] + proj[5] * modl[13] + proj[9] * modl[14] + proj[13] * modl[15];
|
|---|
| 204 | m.m32 = proj[2] * modl[12] + proj[6] * modl[13] + proj[10] * modl[14] + proj[14] * modl[15];
|
|---|
| 205 | m.m33 = proj[3] * modl[12] + proj[7] * modl[13] + proj[11] * modl[14] + proj[15] * modl[15];
|
|---|
| 206 |
|
|---|
| 207 | crTransformBBox( *x1, *y1, *z1,
|
|---|
| 208 | *x2, *y2, *z2,
|
|---|
| 209 | &m,
|
|---|
| 210 | x1, y1, z1,
|
|---|
| 211 | x2, y2, z2 );
|
|---|
| 212 | }
|
|---|
| 213 |
|
|---|
| 214 |
|
|---|
| 215 | #define MIN(a, b) ((a) < (b) ? (a) : (b))
|
|---|
| 216 | #define MAX(a, b) ((a) > (b) ? (a) : (b))
|
|---|
| 217 |
|
|---|
| 218 |
|
|---|
| 219 | /**
|
|---|
| 220 | * Compute union of a and b and put in result.
|
|---|
| 221 | */
|
|---|
| 222 | void
|
|---|
| 223 | crRectiUnion(CRrecti *result, const CRrecti *a, const CRrecti *b)
|
|---|
| 224 | {
|
|---|
| 225 | result->x1 = MIN(a->x1, b->x1);
|
|---|
| 226 | result->x2 = MAX(a->x2, b->x2);
|
|---|
| 227 | result->y1 = MIN(a->y1, b->y1);
|
|---|
| 228 | result->y2 = MAX(a->y2, b->y2);
|
|---|
| 229 | }
|
|---|
