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