OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * ***** BEGIN GPL LICENSE BLOCK ***** |
| 3 * |
| 4 * This program is free software; you can redistribute it and/or |
| 5 * modify it under the terms of the GNU General Public License |
| 6 * as published by the Free Software Foundation; either version 2 |
| 7 * of the License, or (at your option) any later version. |
| 8 * |
| 9 * This program is distributed in the hope that it will be useful, |
| 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 12 * GNU General Public License for more details. |
| 13 * |
| 14 * You should have received a copy of the GNU General Public License |
| 15 * along with this program; if not, write to the Free Software Foundation, |
| 16 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
| 17 * |
| 18 * The Original Code is Copyright (C) 2010 Blender Foundation. |
| 19 * All rights reserved. |
| 20 * |
| 21 * The Original Code is: all of this file. |
| 22 * |
| 23 * Contributor(s): none yet. |
| 24 * |
| 25 * ***** END GPL LICENSE BLOCK ***** |
| 26 */ |
| 27 |
| 28 /** \file blender/freestyle/intern/geometry/Grid.cpp |
| 29 * \ingroup freestyle |
| 30 * \brief Base class to define a cell grid surrounding the bounding box of the
scene |
| 31 * \author Stephane Grabli |
| 32 * \date 30/07/2002 |
| 33 */ |
| 34 |
| 35 #include <cassert> |
| 36 #include <stdexcept> |
| 37 |
| 38 #include "BBox.h" |
| 39 #include "Grid.h" |
| 40 |
| 41 // Grid Visitors |
| 42 ///////////////// |
| 43 void allOccludersGridVisitor::examineOccluder(Polygon3r *occ) |
| 44 { |
| 45 occluders_.push_back(occ); |
| 46 } |
| 47 |
| 48 static bool inBox(const Vec3r& inter, const Vec3r& box_min, const Vec3r& box_max
) |
| 49 { |
| 50 if (((inter.x() >= box_min.x()) && (inter.x() < box_max.x())) && |
| 51 ((inter.y() >= box_min.y()) && (inter.y() < box_max.y())) && |
| 52 ((inter.z() >= box_min.z()) && (inter.z() < box_max.z()))) |
| 53 { |
| 54 return true; |
| 55 } |
| 56 return false; |
| 57 } |
| 58 |
| 59 void firstIntersectionGridVisitor::examineOccluder(Polygon3r *occ) |
| 60 { |
| 61 // check whether the edge and the polygon plane are coincident: |
| 62 //------------------------------------------------------------- |
| 63 //first let us compute the plane equation. |
| 64 Vec3r v1(((occ)->getVertices())[0]); |
| 65 Vec3d normal((occ)->getNormal()); |
| 66 //soc unused - double d = -(v1 * normal); |
| 67 |
| 68 double tmp_u, tmp_v, tmp_t; |
| 69 if ((occ)->rayIntersect(ray_org_, ray_dir_, tmp_t, tmp_u, tmp_v)) { |
| 70 if (fabs(ray_dir_ * normal) > 0.0001) { |
| 71 // Check whether the intersection is in the cell: |
| 72 if (inBox(ray_org_ + tmp_t * ray_dir_ / ray_dir_.norm(),
current_cell_->getOrigin(), |
| 73 current_cell_->getOrigin() + cell_size_)) |
| 74 { |
| 75 #if 0 |
| 76 Vec3d bboxdiag(_scene3d->bbox().getMax() - _scen
e3d->bbox().getMin()); |
| 77 if ((t > 1.0e-06 * (min(min(bboxdiag.x(), bboxdi
ag.y()), bboxdiag.z()))) && (t < raylength)) { |
| 78 #else |
| 79 if (tmp_t < t_) { |
| 80 #endif |
| 81 occluder_ = occ; |
| 82 u_ = tmp_u; |
| 83 v_ = tmp_v; |
| 84 t_ = tmp_t; |
| 85 } |
| 86 } |
| 87 else { |
| 88 occ->userdata2 = 0; |
| 89 } |
| 90 } |
| 91 } |
| 92 } |
| 93 |
| 94 bool firstIntersectionGridVisitor::stop() |
| 95 { |
| 96 if (occluder_) |
| 97 return true; |
| 98 return false; |
| 99 } |
| 100 |
| 101 // Grid |
| 102 ///////////////// |
| 103 void Grid::clear() |
| 104 { |
| 105 if (_occluders.size() != 0) { |
| 106 for (OccludersSet::iterator it = _occluders.begin(); it != _occl
uders.end(); it++) { |
| 107 delete (*it); |
| 108 } |
| 109 _occluders.clear(); |
| 110 } |
| 111 |
| 112 _size = Vec3r(0, 0, 0); |
| 113 _cell_size = Vec3r(0, 0, 0); |
| 114 _orig = Vec3r(0, 0, 0); |
| 115 _cells_nb = Vec3u(0, 0, 0); |
| 116 //_ray_occluders.clear(); |
| 117 } |
| 118 |
| 119 void Grid::configure(const Vec3r& orig, const Vec3r& size, unsigned nb) |
| 120 { |
| 121 _orig = orig; |
| 122 Vec3r tmpSize = size; |
| 123 // Compute the volume of the desired grid |
| 124 real grid_vol = size[0] * size[1] * size[2]; |
| 125 |
| 126 if (grid_vol == 0) { |
| 127 double min = DBL_MAX; |
| 128 int index = 0; |
| 129 int nzeros = 0; |
| 130 for (int i = 0; i < 3; ++i) { |
| 131 if (size[i] == 0) { |
| 132 ++nzeros; |
| 133 index = i; |
| 134 } |
| 135 if ((size[i] != 0) && (min > size[i])) { |
| 136 min = size[i]; |
| 137 } |
| 138 } |
| 139 if (nzeros > 1) { |
| 140 throw std::runtime_error("Warning: the 3D grid has more
than one null dimension"); |
| 141 } |
| 142 tmpSize[index] = min; |
| 143 _orig[index] = _orig[index] - min / 2; |
| 144 } |
| 145 // Compute the desired volume of a single cell |
| 146 real cell_vol = grid_vol / nb; |
| 147 // The edge of such a cubic cell is cubic root of cellVolume |
| 148 real edge = pow(cell_vol, 1.0 / 3.0); |
| 149 |
| 150 // We compute the number of cells par edge such as we cover at least the
whole box. |
| 151 unsigned i; |
| 152 for (i = 0; i < 3; i++) |
| 153 _cells_nb[i] = (unsigned)floor(tmpSize[i] / edge) + 1; |
| 154 |
| 155 _size = tmpSize; |
| 156 |
| 157 for (i = 0; i < 3; i++) |
| 158 _cell_size[i] = _size[i] / _cells_nb[i]; |
| 159 } |
| 160 |
| 161 void Grid::insertOccluder(Polygon3r* occluder) |
| 162 { |
| 163 const vector<Vec3r> vertices = occluder->getVertices(); |
| 164 if (vertices.size() == 0) |
| 165 return; |
| 166 |
| 167 // add this occluder to the grid's occluders list |
| 168 addOccluder(occluder); |
| 169 |
| 170 // find the bbox associated to this polygon |
| 171 Vec3r min, max; |
| 172 occluder->getBBox(min, max); |
| 173 |
| 174 // Retrieve the cell x, y, z cordinates associated with these min and ma
x |
| 175 Vec3u imax, imin; |
| 176 getCellCoordinates(max, imax); |
| 177 getCellCoordinates(min, imin); |
| 178 |
| 179 // We are now going to fill in the cells overlapping with the polygon bb
ox. |
| 180 // If the polygon is a triangle (most of cases), we also check for each
of these cells if it is overlapping with |
| 181 // the triangle in order to only fill in the ones really overlapping the
triangle. |
| 182 |
| 183 unsigned i, x, y, z; |
| 184 vector<Vec3r>::const_iterator it; |
| 185 Vec3u coord; |
| 186 |
| 187 if (vertices.size() == 3) { // Triangle case |
| 188 Vec3r triverts[3]; |
| 189 i = 0; |
| 190 for (it = vertices.begin(); it != vertices.end(); it++) { |
| 191 triverts[i] = Vec3r(*it); |
| 192 i++; |
| 193 } |
| 194 |
| 195 Vec3r boxmin, boxmax; |
| 196 |
| 197 for (z = imin[2]; z <= imax[2]; z++) { |
| 198 for (y = imin[1]; y <= imax[1]; y++) { |
| 199 for (x = imin[0]; x <= imax[0]; x++) { |
| 200 coord[0] = x; |
| 201 coord[1] = y; |
| 202 coord[2] = z; |
| 203 // We retrieve the box coordinates of th
e current cell |
| 204 getCellBox(coord, boxmin, boxmax); |
| 205 // We check whether the triangle and the
box ovewrlap: |
| 206 Vec3r boxcenter((boxmin + boxmax) / 2.0)
; |
| 207 Vec3r boxhalfsize(_cell_size / 2.0); |
| 208 if (GeomUtils::overlapTriangleBox(boxcen
ter, boxhalfsize, triverts)) { |
| 209 // We must then create the Cell
and add it to the cells list if it does not exist yet. |
| 210 // We must then add the occluder
to the occluders list of this cell. |
| 211 Cell* cell = getCell(coord); |
| 212 if (!cell) { |
| 213 cell = new Cell(boxmin); |
| 214 fillCell(coord, *cell); |
| 215 } |
| 216 cell->addOccluder(occluder); |
| 217 } |
| 218 } |
| 219 } |
| 220 } |
| 221 } |
| 222 else { // The polygon is not a triangle, we add all the cells overlappin
g the polygon bbox. |
| 223 for (z = imin[2]; z <= imax[2]; z++) { |
| 224 for (y = imin[1]; y <= imax[1]; y++) { |
| 225 for (x = imin[0]; x <= imax[0]; x++) { |
| 226 coord[0] = x; |
| 227 coord[1] = y; |
| 228 coord[2] = z; |
| 229 Cell* cell = getCell(coord); |
| 230 if (!cell) { |
| 231 Vec3r orig; |
| 232 getCellOrigin(coord, orig); |
| 233 cell = new Cell(orig); |
| 234 fillCell(coord, *cell); |
| 235 } |
| 236 cell->addOccluder(occluder); |
| 237 } |
| 238 } |
| 239 } |
| 240 } |
| 241 } |
| 242 |
| 243 bool Grid::nextRayCell(Vec3u& current_cell, Vec3u& next_cell) |
| 244 { |
| 245 next_cell = current_cell; |
| 246 real t_min, t; |
| 247 unsigned i; |
| 248 |
| 249 t_min = FLT_MAX; // init tmin with handle of the case where one or 2
_u[i] = 0.· |
| 250 unsigned coord = 0; // predominant coord(0=x, 1=y, 2=z) |
| 251 |
| 252 |
| 253 // using a parametric equation of a line : B = A + t u, we find the tx,
ty and tz respectively coresponding |
| 254 // to the intersections with the plans: |
| 255 // x = _cell_size[0], y = _cell_size[1], z = _cell_size[2] |
| 256 for (i = 0; i < 3; i++) { |
| 257 if (_ray_dir[i] == 0) |
| 258 continue; |
| 259 if (_ray_dir[i] > 0) |
| 260 t = (_cell_size[i] - _pt[i]) / _ray_dir[i]; |
| 261 else |
| 262 t = -_pt[i] / _ray_dir[i]; |
| 263 if (t < t_min) { |
| 264 t_min = t; |
| 265 coord = i; |
| 266 } |
| 267 } |
| 268 |
| 269 // We use the parametric line equation and the found t (tamx) to compute
the B coordinates: |
| 270 Vec3r pt_tmp(_pt); |
| 271 _pt = pt_tmp + t_min * _ray_dir; |
| 272 |
| 273 // We express B coordinates in the next cell coordinates system. We just
have to |
| 274 // set the coordinate coord of B to 0 of _CellSize[coord] depending on t
he sign of _u[coord] |
| 275 if (_ray_dir[coord] > 0) { |
| 276 next_cell[coord]++; |
| 277 _pt[coord] -= _cell_size[coord]; |
| 278 // if we are out of the grid, we must stop |
| 279 if (next_cell[coord] >= _cells_nb[coord]) |
| 280 return false; |
| 281 } |
| 282 else { |
| 283 int tmp = next_cell[coord] - 1; |
| 284 _pt[coord] = _cell_size[coord]; |
| 285 if (tmp < 0) |
| 286 return false; |
| 287 next_cell[coord]--; |
| 288 } |
| 289 |
| 290 _t += t_min; |
| 291 if (_t >= _t_end) |
| 292 return false; |
| 293 |
| 294 return true; |
| 295 } |
| 296 |
| 297 void Grid::castRay(const Vec3r& orig, const Vec3r& end, OccludersSet& occluders,
unsigned timestamp) |
| 298 { |
| 299 initRay(orig, end, timestamp); |
| 300 allOccludersGridVisitor visitor(occluders); |
| 301 castRayInternal(visitor); |
| 302 } |
| 303 |
| 304 void Grid::castInfiniteRay(const Vec3r& orig, const Vec3r& dir, OccludersSet& oc
cluders, unsigned timestamp) |
| 305 { |
| 306 Vec3r end = Vec3r(orig + FLT_MAX * dir / dir.norm()); |
| 307 bool inter = initInfiniteRay(orig, dir, timestamp); |
| 308 if (!inter) |
| 309 return; |
| 310 allOccludersGridVisitor visitor(occluders); |
| 311 castRayInternal(visitor); |
| 312 } |
| 313 |
| 314 Polygon3r* Grid::castRayToFindFirstIntersection(const Vec3r& orig, const Vec3r&
dir, double& t, |
| 315 double& u, double& v, unsigned t
imestamp) |
| 316 { |
| 317 Polygon3r *occluder = 0; |
| 318 Vec3r end = Vec3r(orig + FLT_MAX * dir / dir.norm()); |
| 319 bool inter = initInfiniteRay(orig, dir, timestamp); |
| 320 if (!inter) { |
| 321 return 0; |
| 322 } |
| 323 firstIntersectionGridVisitor visitor(orig, dir, _cell_size); |
| 324 castRayInternal(visitor); |
| 325 // ARB: This doesn't work, because occluders are unordered within any ce
ll |
| 326 // visitor.occluder() will be an occluder, but we have no guarantee it w
ill be the *first* occluder. |
| 327 // I assume that is the reason this code is not actually used for FindOc
cludee. |
| 328 occluder = visitor.occluder(); |
| 329 t = visitor.t_; |
| 330 u = visitor.u_; |
| 331 v = visitor.v_; |
| 332 return occluder; |
| 333 } |
| 334 |
| 335 void Grid::initRay (const Vec3r &orig, const Vec3r& end, unsigned timestamp) |
| 336 { |
| 337 _ray_dir = end - orig; |
| 338 _t_end = _ray_dir.norm(); |
| 339 _t = 0; |
| 340 _ray_dir.normalize(); |
| 341 _timestamp = timestamp; |
| 342 |
| 343 for (unsigned i = 0; i < 3; i++) { |
| 344 _current_cell[i] = (unsigned)floor((orig[i] - _orig[i]) / _cell_
size[i]); |
| 345 //soc unused - unsigned u = _current_cell[i]; |
| 346 _pt[i] = orig[i] - _orig[i] - _current_cell[i] * _cell_size[i]; |
| 347 } |
| 348 //_ray_occluders.clear(); |
| 349 } |
| 350 |
| 351 bool Grid::initInfiniteRay (const Vec3r &orig, const Vec3r& dir, unsigned timest
amp) { |
| 352 _ray_dir = dir; |
| 353 _t_end = FLT_MAX; |
| 354 _t = 0; |
| 355 _ray_dir.normalize(); |
| 356 _timestamp = timestamp; |
| 357 |
| 358 // check whether the origin is in or out the box: |
| 359 Vec3r boxMin(_orig); |
| 360 Vec3r boxMax(_orig + _size); |
| 361 BBox<Vec3r> box(boxMin, boxMax); |
| 362 if (box.inside(orig)) { |
| 363 for (unsigned int i = 0; i < 3; i++) { |
| 364 _current_cell[i] = (unsigned int)floor((orig[i] - _orig[
i]) / _cell_size[i]); |
| 365 //soc unused - unsigned u = _current_cell[i]; |
| 366 _pt[i] = orig[i] - _orig[i] - _current_cell[i] * _cell_s
ize[i]; |
| 367 } |
| 368 } |
| 369 else { |
| 370 // is the ray intersecting the box? |
| 371 real tmin(-1.0), tmax(-1.0); |
| 372 if (GeomUtils::intersectRayBBox(orig, _ray_dir, boxMin, boxMax,
0, _t_end, tmin, tmax)) { |
| 373 assert(tmin != -1.0); |
| 374 Vec3r newOrig = orig + tmin * _ray_dir; |
| 375 for (unsigned int i = 0; i < 3; i++) { |
| 376 _current_cell[i] = (unsigned)floor((newOrig[i] -
_orig[i]) / _cell_size[i]); |
| 377 if (_current_cell[i] == _cells_nb[i]) |
| 378 _current_cell[i] = _cells_nb[i] - 1; |
| 379 //soc unused - unsigned u = _current_cell[i]; |
| 380 _pt[i] = newOrig[i] - _orig[i] - _current_cell[i
] * _cell_size[i]; |
| 381 } |
| 382 } |
| 383 else { |
| 384 return false; |
| 385 } |
| 386 } |
| 387 //_ray_occluders.clear(); |
| 388 |
| 389 return true; |
| 390 } |
OLD | NEW |