← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty-proposed

« back to all changes in this revision

Viewing changes to source/blender/freestyle/intern/geometry/Grid.cpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2013-08-14 10:43:49 UTC
  • mfrom: (14.2.19 sid)
  • Revision ID: package-import@ubuntu.com-20130814104349-t1d5mtwkphp12dyj
Tags: 2.68a-3
* Upload to unstable
* debian/: python3.3 Depends simplified
  - debian/control: python3.3 Depends dropped
    for blender-data package
  - 0001-blender_thumbnailer.patch refreshed
* debian/control: libavcodec b-dep versioning dropped

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/freestyle/intern/geometry/Grid.cpp
 
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
 * ***** END GPL LICENSE BLOCK *****
 
19
 */
 
20
 
 
21
/** \file blender/freestyle/intern/geometry/Grid.cpp
 
22
 *  \ingroup freestyle
 
23
 *  \brief Base class to define a cell grid surrounding the bounding box of the scene
 
24
 *  \author Stephane Grabli
 
25
 *  \date 30/07/2002
 
26
 */
 
27
 
 
28
#include <cassert>
 
29
#include <stdexcept>
 
30
 
 
31
#include "BBox.h"
 
32
#include "Grid.h"
 
33
 
 
34
namespace Freestyle {
 
35
 
 
36
// Grid Visitors
 
37
/////////////////
 
38
void allOccludersGridVisitor::examineOccluder(Polygon3r *occ)
 
39
{
 
40
        occluders_.push_back(occ);
 
41
}
 
42
 
 
43
static bool inBox(const Vec3r& inter, const Vec3r& box_min, const Vec3r& box_max)
 
44
{
 
45
        if (((inter.x() >= box_min.x()) && (inter.x() < box_max.x())) &&
 
46
            ((inter.y() >= box_min.y()) && (inter.y() < box_max.y())) &&
 
47
            ((inter.z() >= box_min.z()) && (inter.z() < box_max.z())))
 
48
        {
 
49
                return true;
 
50
        }
 
51
        return false;
 
52
}
 
53
 
 
54
void firstIntersectionGridVisitor::examineOccluder(Polygon3r *occ)
 
55
{
 
56
        // check whether the edge and the polygon plane are coincident:
 
57
        //-------------------------------------------------------------
 
58
        //first let us compute the plane equation.
 
59
        Vec3r v1(((occ)->getVertices())[0]);
 
60
        Vec3d normal((occ)->getNormal());
 
61
        //soc unused - double d = -(v1 * normal);
 
62
 
 
63
        double tmp_u, tmp_v, tmp_t;
 
64
        if ((occ)->rayIntersect(ray_org_, ray_dir_, tmp_t, tmp_u, tmp_v)) {
 
65
                if (fabs(ray_dir_ * normal) > 0.0001) {
 
66
                        // Check whether the intersection is in the cell:
 
67
                        if (inBox(ray_org_ + tmp_t * ray_dir_ / ray_dir_.norm(), current_cell_->getOrigin(),
 
68
                                  current_cell_->getOrigin() + cell_size_))
 
69
                        {
 
70
#if 0
 
71
                                Vec3d bboxdiag(_scene3d->bbox().getMax() - _scene3d->bbox().getMin());
 
72
                                if ((t > 1.0e-06 * (min(min(bboxdiag.x(), bboxdiag.y()), bboxdiag.z()))) && (t < raylength)) {
 
73
#else
 
74
                                if (tmp_t < t_) {
 
75
#endif
 
76
                                        occluder_ = occ;
 
77
                                        u_ = tmp_u;
 
78
                                        v_ = tmp_v;
 
79
                                        t_ = tmp_t;
 
80
                                }
 
81
                        }
 
82
                        else {
 
83
                                occ->userdata2 = 0;
 
84
                        }
 
85
                }
 
86
        }
 
87
}
 
88
 
 
89
bool firstIntersectionGridVisitor::stop()
 
90
{
 
91
        if (occluder_)
 
92
                return true;
 
93
        return false;
 
94
}
 
95
 
 
96
// Grid
 
97
/////////////////
 
98
void Grid::clear()
 
99
{
 
100
        if (_occluders.size() != 0) {
 
101
                for (OccludersSet::iterator it = _occluders.begin(); it != _occluders.end(); it++) {
 
102
                        delete (*it);
 
103
                }
 
104
                _occluders.clear();
 
105
        }
 
106
 
 
107
        _size = Vec3r(0, 0, 0);
 
108
        _cell_size = Vec3r(0, 0, 0);
 
109
        _orig = Vec3r(0, 0, 0);
 
110
        _cells_nb = Vec3u(0, 0, 0);
 
111
        //_ray_occluders.clear();
 
112
}
 
113
 
 
114
void Grid::configure(const Vec3r& orig, const Vec3r& size, unsigned nb)
 
115
{
 
116
        _orig = orig;
 
117
        Vec3r tmpSize = size;
 
118
        // Compute the volume of the desired grid
 
119
        real grid_vol = size[0] * size[1] * size[2];
 
120
 
 
121
        if (grid_vol == 0) {
 
122
                double min = DBL_MAX;
 
123
                int index = 0;
 
124
                int nzeros = 0;
 
125
                for (int i = 0; i < 3; ++i) {
 
126
                        if (size[i] == 0) {
 
127
                                ++nzeros;
 
128
                                index = i;
 
129
                        }
 
130
                        if ((size[i] != 0) && (min > size[i])) {
 
131
                                min = size[i];
 
132
                        }
 
133
                }
 
134
                if (nzeros > 1) {
 
135
                        throw std::runtime_error("Warning: the 3D grid has more than one null dimension");
 
136
                }
 
137
                tmpSize[index] = min;
 
138
                _orig[index] = _orig[index] - min / 2;
 
139
        }
 
140
        // Compute the desired volume of a single cell
 
141
        real cell_vol = grid_vol / nb;
 
142
        // The edge of such a cubic cell is cubic root of cellVolume
 
143
        real edge = pow(cell_vol, 1.0 / 3.0);
 
144
 
 
145
        // We compute the number of cells par edge such as we cover at least the whole box.
 
146
        unsigned i;
 
147
        for (i = 0; i < 3; i++)
 
148
                _cells_nb[i] = (unsigned)floor(tmpSize[i] / edge) + 1;
 
149
 
 
150
        _size = tmpSize;
 
151
 
 
152
        for (i = 0; i < 3; i++)
 
153
                _cell_size[i] = _size[i] / _cells_nb[i];
 
154
}
 
155
 
 
156
void Grid::insertOccluder(Polygon3r *occluder)
 
157
{
 
158
        const vector<Vec3r> vertices = occluder->getVertices();
 
159
        if (vertices.size() == 0)
 
160
                return;
 
161
 
 
162
        // add this occluder to the grid's occluders list
 
163
        addOccluder(occluder);
 
164
 
 
165
        // find the bbox associated to this polygon
 
166
        Vec3r min, max;
 
167
        occluder->getBBox(min, max);
 
168
 
 
169
        // Retrieve the cell x, y, z cordinates associated with these min and max
 
170
        Vec3u imax, imin;
 
171
        getCellCoordinates(max, imax);
 
172
        getCellCoordinates(min, imin);
 
173
 
 
174
        // We are now going to fill in the cells overlapping with the polygon bbox.
 
175
        // If the polygon is a triangle (most of cases), we also check for each of these cells if it is overlapping with
 
176
        // the triangle in order to only fill in the ones really overlapping the 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
 
 
248
        // using a parametric equation of a line : B = A + t u, we find the tx, ty and tz respectively coresponding
 
249
        // to the intersections with the plans:
 
250
        //     x = _cell_size[0], y = _cell_size[1], z = _cell_size[2]
 
251
        for (i = 0; i < 3; i++) {
 
252
                if (_ray_dir[i] == 0)
 
253
                        continue;
 
254
                if (_ray_dir[i] > 0)
 
255
                        t = (_cell_size[i] - _pt[i]) / _ray_dir[i];
 
256
                else
 
257
                        t = -_pt[i] / _ray_dir[i];
 
258
                if (t < t_min) {
 
259
                        t_min = t;
 
260
                        coord = i;
 
261
                }
 
262
        }
 
263
 
 
264
        // We use the parametric line equation and the found t (tamx) to compute the B coordinates:
 
265
        Vec3r pt_tmp(_pt);
 
266
        _pt = pt_tmp + t_min * _ray_dir;
 
267
 
 
268
        // We express B coordinates in the next cell coordinates system. We just have to
 
269
        // set the coordinate coord of B to 0 of _CellSize[coord] depending on the sign of _u[coord]
 
270
        if (_ray_dir[coord] > 0) {
 
271
                next_cell[coord]++;
 
272
                _pt[coord] -= _cell_size[coord];
 
273
                // if we are out of the grid, we must stop
 
274
                if (next_cell[coord] >= _cells_nb[coord])
 
275
                        return false;
 
276
        }
 
277
        else {
 
278
                int tmp = next_cell[coord] - 1;
 
279
                _pt[coord] = _cell_size[coord];
 
280
                if (tmp < 0)
 
281
                        return false;
 
282
                next_cell[coord]--;
 
283
        }
 
284
 
 
285
        _t += t_min;
 
286
        if (_t >= _t_end)
 
287
                return false;
 
288
 
 
289
        return true;
 
290
}
 
291
 
 
292
void Grid::castRay(const Vec3r& orig, const Vec3r& end, OccludersSet& occluders, unsigned timestamp)
 
293
{
 
294
        initRay(orig, end, timestamp);
 
295
        allOccludersGridVisitor visitor(occluders);
 
296
        castRayInternal(visitor);
 
297
}
 
298
 
 
299
void Grid::castInfiniteRay(const Vec3r& orig, const Vec3r& dir, OccludersSet& occluders, unsigned timestamp)
 
300
{
 
301
        Vec3r end = Vec3r(orig + FLT_MAX * dir / dir.norm());
 
302
        bool inter = initInfiniteRay(orig, dir, timestamp);
 
303
        if (!inter)
 
304
                return;
 
305
        allOccludersGridVisitor visitor(occluders);
 
306
        castRayInternal(visitor);
 
307
}
 
308
 
 
309
Polygon3r *Grid::castRayToFindFirstIntersection(const Vec3r& orig, const Vec3r& dir, double& t,
 
310
                                                double& u, double& v, unsigned timestamp)
 
311
{
 
312
        Polygon3r *occluder = 0;
 
313
        Vec3r end = Vec3r(orig + FLT_MAX * dir / dir.norm());
 
314
        bool inter = initInfiniteRay(orig, dir, timestamp);
 
315
        if (!inter) {
 
316
                return 0;
 
317
        }
 
318
        firstIntersectionGridVisitor visitor(orig, dir, _cell_size);
 
319
        castRayInternal(visitor);
 
320
        // ARB: This doesn't work, because occluders are unordered within any cell
 
321
        // visitor.occluder() will be an occluder, but we have no guarantee it will be the *first* occluder.
 
322
        // I assume that is the reason this code is not actually used for FindOccludee.
 
323
        occluder = visitor.occluder();
 
324
        t = visitor.t_;
 
325
        u = visitor.u_;
 
326
        v = visitor.v_;
 
327
        return occluder;
 
328
}
 
329
 
 
330
void Grid::initRay (const Vec3r &orig, const Vec3r& end, unsigned timestamp)
 
331
{
 
332
        _ray_dir = end - orig;
 
333
        _t_end = _ray_dir.norm();
 
334
        _t = 0;
 
335
        _ray_dir.normalize();
 
336
        _timestamp = timestamp;
 
337
 
 
338
        for (unsigned i = 0; i < 3; i++) {
 
339
                _current_cell[i] = (unsigned)floor((orig[i] - _orig[i]) / _cell_size[i]);
 
340
                //soc unused - unsigned u = _current_cell[i];
 
341
                _pt[i] = orig[i] - _orig[i] - _current_cell[i] * _cell_size[i];
 
342
        }
 
343
        //_ray_occluders.clear();
 
344
}
 
345
 
 
346
bool Grid::initInfiniteRay (const Vec3r &orig, const Vec3r& dir, unsigned timestamp)
 
347
{
 
348
        _ray_dir = dir;
 
349
        _t_end = FLT_MAX;
 
350
        _t = 0;
 
351
        _ray_dir.normalize();
 
352
        _timestamp = timestamp;
 
353
 
 
354
        // check whether the origin is in or out the box:
 
355
        Vec3r boxMin(_orig);
 
356
        Vec3r boxMax(_orig + _size);
 
357
        BBox<Vec3r> box(boxMin, boxMax);
 
358
        if (box.inside(orig)) {
 
359
                for (unsigned int i = 0; i < 3; i++) {
 
360
                        _current_cell[i] = (unsigned int)floor((orig[i] - _orig[i]) / _cell_size[i]);
 
361
                        //soc unused - unsigned u = _current_cell[i];
 
362
                        _pt[i] = orig[i] - _orig[i] - _current_cell[i] * _cell_size[i];
 
363
                }
 
364
        }
 
365
        else {
 
366
                // is the ray intersecting the box?
 
367
                real tmin(-1.0), tmax(-1.0);
 
368
                if (GeomUtils::intersectRayBBox(orig, _ray_dir, boxMin, boxMax, 0, _t_end, tmin, tmax)) {
 
369
                        assert(tmin != -1.0);
 
370
                        Vec3r newOrig = orig + tmin * _ray_dir;
 
371
                        for (unsigned int i = 0; i < 3; i++) {
 
372
                                _current_cell[i] = (unsigned)floor((newOrig[i] - _orig[i]) / _cell_size[i]);
 
373
                                if (_current_cell[i] == _cells_nb[i])
 
374
                                        _current_cell[i] = _cells_nb[i] - 1;
 
375
                                //soc unused - unsigned u = _current_cell[i];
 
376
                                _pt[i] = newOrig[i] - _orig[i] - _current_cell[i] * _cell_size[i];
 
377
                        }
 
378
                }
 
379
                else {
 
380
                        return false;
 
381
                }
 
382
        }
 
383
        //_ray_occluders.clear();
 
384
 
 
385
        return true;
 
386
}
 
387
 
 
388
} /* namespace Freestyle */