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