← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/lib/octree.cpp

  • Committer: Package Import Robot
  • Author(s): Matteo F. Vescovi
  • Date: 2012-07-23 08:54:18 UTC
  • mfrom: (14.2.16 sid)
  • mto: (14.2.19 sid)
  • mto: This revision was merged to the branch mainline in revision 42.
  • Revision ID: package-import@ubuntu.com-20120723085418-9foz30v6afaf5ffs
Tags: 2.63a-2
http://bugs.debian.org/658075
* debian/: Cycles support added (Closes: #658075)
  For now, this top feature has been enabled only
  on [any-amd64 any-i386] architectures because
  of OpenImageIO failing on all others
* debian/: scripts installation path changed
  from /usr/lib to /usr/share:
  + debian/patches/: patchset re-worked for path changing
  + debian/control: "Breaks" field added on yafaray-exporter

Show diffs side-by-side

added added

removed removed

Lines of Context:
extern/carve/lib/octree.cpp
 
1
// Begin License:
 
2
// Copyright (C) 2006-2011 Tobias Sargeant (tobias.sargeant@gmail.com).
 
3
// All rights reserved.
 
4
//
 
5
// This file is part of the Carve CSG Library (http://carve-csg.com/)
 
6
//
 
7
// This file may be used under the terms of the GNU General Public
 
8
// License version 2.0 as published by the Free Software Foundation
 
9
// and appearing in the file LICENSE.GPL2 included in the packaging of
 
10
// this file.
 
11
//
 
12
// This file is provided "AS IS" with NO WARRANTY OF ANY KIND,
 
13
// INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR
 
14
// A PARTICULAR PURPOSE.
 
15
// End:
 
16
 
 
17
 
 
18
#if defined(HAVE_CONFIG_H)
 
19
#  include <carve_config.h>
 
20
#endif
 
21
 
 
22
#include <carve/octree_decl.hpp>
 
23
#include <carve/octree_impl.hpp>
 
24
 
 
25
#include <carve/poly_decl.hpp>
 
26
 
 
27
namespace carve {
 
28
  namespace csg {
 
29
 
 
30
    Octree::Node::Node(const carve::geom3d::Vector &newMin, const carve::geom3d::Vector &newMax) :
 
31
      parent(NULL), is_leaf(true), min(newMin), max(newMax) {
 
32
      for (int i = 0; i < 8; ++i) children[i] = NULL;
 
33
      aabb = Octree::makeAABB(this);
 
34
    }
 
35
 
 
36
    Octree::Node::Node(Node *p, double x1, double y1, double z1, double x2, double y2, double z2) :
 
37
      parent(p), is_leaf(true), min(carve::geom::VECTOR(x1, y1, z1)), max(carve::geom::VECTOR(x2, y2, z2)) {
 
38
      for (int i = 0; i < 8; ++i) children[i] = NULL;
 
39
      aabb = Octree::makeAABB(this);
 
40
    }
 
41
 
 
42
    Octree::Node::~Node() {
 
43
      for (int i = 0; i < 8; ++i) {
 
44
        if (children[i] != NULL) {
 
45
          (*children[i]).~Node();
 
46
        }
 
47
      }
 
48
      if (children[0] != NULL) {
 
49
        char *ptr = (char*)children[0];
 
50
        delete[] ptr;
 
51
      }
 
52
    }
 
53
 
 
54
    bool Octree::Node::mightContain(const carve::poly::Face<3> &face) {
 
55
      if (face.nVertices() == 3) {
 
56
        return aabb.intersects(carve::geom::tri<3>(face.vertex(0)->v, face.vertex(1)->v, face.vertex(2)->v));
 
57
      } else {
 
58
        return aabb.intersects(face.aabb) && aabb.intersects(face.plane_eqn);
 
59
      }
 
60
    }
 
61
 
 
62
    bool Octree::Node::mightContain(const carve::poly::Edge<3> &edge) {
 
63
      return aabb.intersectsLineSegment(edge.v1->v, edge.v2->v);
 
64
    }
 
65
 
 
66
    bool Octree::Node::mightContain(const carve::poly::Vertex<3> &p) {
 
67
      return aabb.containsPoint(p.v);
 
68
    }
 
69
 
 
70
    bool Octree::Node::hasChildren() {
 
71
      return !is_leaf;
 
72
    }
 
73
 
 
74
    bool Octree::Node::split() {
 
75
      if (is_leaf && hasGeometry()) {
 
76
 
 
77
        carve::geom3d::Vector mid = 0.5 * (min + max);
 
78
        char *ptr = new char[sizeof(Node)*8];
 
79
        children[0] = new (ptr + sizeof(Node) * 0) Node(this, min.x, min.y, min.z, mid.x, mid.y, mid.z);
 
80
        children[1] = new (ptr + sizeof(Node) * 1) Node(this, mid.x, min.y, min.z, max.x, mid.y, mid.z);
 
81
        children[2] = new (ptr + sizeof(Node) * 2) Node(this, min.x, mid.y, min.z, mid.x, max.y, mid.z);
 
82
        children[3] = new (ptr + sizeof(Node) * 3) Node(this, mid.x, mid.y, min.z, max.x, max.y, mid.z);
 
83
        children[4] = new (ptr + sizeof(Node) * 4) Node(this, min.x, min.y, mid.z, mid.x, mid.y, max.z);
 
84
        children[5] = new (ptr + sizeof(Node) * 5) Node(this, mid.x, min.y, mid.z, max.x, mid.y, max.z);
 
85
        children[6] = new (ptr + sizeof(Node) * 6) Node(this, min.x, mid.y, mid.z, mid.x, max.y, max.z);
 
86
        children[7] = new (ptr + sizeof(Node) * 7) Node(this, mid.x, mid.y, mid.z, max.x, max.y, max.z);
 
87
 
 
88
        for (int i = 0; i < 8; ++i) {
 
89
          putInside(faces, children[i], children[i]->faces);
 
90
          putInside(edges, children[i], children[i]->edges);
 
91
          putInside(vertices, children[i], children[i]->vertices);
 
92
        }
 
93
 
 
94
        faces.clear();
 
95
        edges.clear();
 
96
        vertices.clear();
 
97
        is_leaf = false;
 
98
      }
 
99
      return is_leaf;
 
100
    }
 
101
 
 
102
    template <class T>
 
103
    void Octree::Node::putInside(const T &input, Node *child, T &output) {
 
104
      for (typename T::const_iterator it = input.begin(), e = input.end(); it != e; ++it) {
 
105
        if (child->mightContain(**it)) {
 
106
          output.push_back(*it);
 
107
        }
 
108
      }
 
109
    }
 
110
 
 
111
    bool Octree::Node::hasGeometry() {
 
112
      return faces.size() > 0 || edges.size() > 0 || vertices.size() > 0;
 
113
    }
 
114
 
 
115
    Octree::Octree() {
 
116
      root = NULL;
 
117
    }
 
118
 
 
119
    Octree::~Octree() {
 
120
      if (root) delete root;
 
121
    }
 
122
 
 
123
    void Octree::setBounds(const carve::geom3d::Vector &min, const carve::geom3d::Vector &max) {
 
124
      if (root) delete root;
 
125
      root = new Node(min, max);
 
126
    }
 
127
 
 
128
    void Octree::setBounds(carve::geom3d::AABB aabb) {
 
129
      if (root) delete root;
 
130
      aabb.extent = 1.1 * aabb.extent;
 
131
      root = new Node(aabb.min(), aabb.max());
 
132
    }
 
133
 
 
134
    void Octree::addEdges(const std::vector<carve::poly::Edge<3> > &e) {
 
135
      root->edges.reserve(root->edges.size() + e.size());
 
136
      for (size_t i = 0; i < e.size(); ++i) {
 
137
        root->edges.push_back(&e[i]);
 
138
      }
 
139
    }
 
140
 
 
141
    void Octree::addFaces(const std::vector<carve::poly::Face<3> > &f) {
 
142
      root->faces.reserve(root->faces.size() + f.size());
 
143
      for (size_t i = 0; i < f.size(); ++i) {
 
144
        root->faces.push_back(&f[i]);
 
145
      } 
 
146
    }
 
147
    
 
148
    void Octree::addVertices(const std::vector<const carve::poly::Vertex<3> *> &p) {
 
149
      root->vertices.insert(root->vertices.end(), p.begin(), p.end());
 
150
    }
 
151
 
 
152
    carve::geom3d::AABB Octree::makeAABB(const Node *node) {
 
153
      carve::geom3d::Vector centre = 0.5 * (node->min + node->max);
 
154
      carve::geom3d::Vector size = SLACK_FACTOR * 0.5 * (node->max - node->min);
 
155
      return carve::geom3d::AABB(centre, size);
 
156
    }
 
157
 
 
158
    void Octree::doFindEdges(const carve::geom::aabb<3> &aabb,
 
159
                             Node *node,
 
160
                             std::vector<const carve::poly::Edge<3> *> &out,
 
161
                             unsigned depth) const {
 
162
      if (node == NULL) {
 
163
        return;
 
164
      }
 
165
 
 
166
      if (node->aabb.intersects(aabb)) {
 
167
        if (node->hasChildren()) {
 
168
          for (int i = 0; i < 8; ++i) {
 
169
            doFindEdges(aabb, node->children[i], out, depth + 1);
 
170
          }
 
171
        } else {
 
172
          if (depth < MAX_SPLIT_DEPTH && node->edges.size() > EDGE_SPLIT_THRESHOLD) {
 
173
            if (!node->split()) {
 
174
              for (int i = 0; i < 8; ++i) {
 
175
                doFindEdges(aabb, node->children[i], out, depth + 1);
 
176
              }
 
177
              return;
 
178
            }
 
179
          }
 
180
          for (std::vector<const carve::poly::Edge<3>*>::const_iterator it = node->edges.begin(), e = node->edges.end(); it != e; ++it) {
 
181
            if ((*it)->tag_once()) {
 
182
              out.push_back(*it);
 
183
            }
 
184
          }
 
185
        }
 
186
      }
 
187
    }
 
188
 
 
189
    void Octree::doFindEdges(const carve::geom3d::LineSegment &l,
 
190
                             Node *node,
 
191
                             std::vector<const carve::poly::Edge<3> *> &out,
 
192
                             unsigned depth) const {
 
193
      if (node == NULL) {
 
194
        return;
 
195
      }
 
196
 
 
197
      if (node->aabb.intersectsLineSegment(l.v1, l.v2)) {
 
198
        if (node->hasChildren()) {
 
199
          for (int i = 0; i < 8; ++i) {
 
200
            doFindEdges(l, node->children[i], out, depth + 1);
 
201
          }
 
202
        } else {
 
203
          if (depth < MAX_SPLIT_DEPTH && node->edges.size() > EDGE_SPLIT_THRESHOLD) {
 
204
            if (!node->split()) {
 
205
              for (int i = 0; i < 8; ++i) {
 
206
                doFindEdges(l, node->children[i], out, depth + 1);
 
207
              }
 
208
              return;
 
209
            }
 
210
          }
 
211
          for (std::vector<const carve::poly::Edge<3>*>::const_iterator it = node->edges.begin(), e = node->edges.end(); it != e; ++it) {
 
212
            if ((*it)->tag_once()) {
 
213
              out.push_back(*it);
 
214
            }
 
215
          }
 
216
        }
 
217
      }
 
218
    }
 
219
 
 
220
    void Octree::doFindEdges(const carve::geom3d::Vector &v,
 
221
                             Node *node,
 
222
                             std::vector<const carve::poly::Edge<3> *> &out,
 
223
                             unsigned depth) const {
 
224
      if (node == NULL) {
 
225
        return;
 
226
      }
 
227
 
 
228
      if (node->aabb.containsPoint(v)) {
 
229
        if (node->hasChildren()) {
 
230
          for (int i = 0; i < 8; ++i) {
 
231
            doFindEdges(v, node->children[i], out, depth + 1);
 
232
          }
 
233
        } else {
 
234
          if (depth < MAX_SPLIT_DEPTH && node->edges.size() > EDGE_SPLIT_THRESHOLD) {
 
235
            if (!node->split()) {
 
236
              for (int i = 0; i < 8; ++i) {
 
237
                doFindEdges(v, node->children[i], out, depth + 1);
 
238
              }
 
239
              return;
 
240
            }
 
241
          }
 
242
          for (std::vector<const carve::poly::Edge<3>*>::const_iterator
 
243
                 it = node->edges.begin(), e = node->edges.end(); it != e; ++it) {
 
244
            if ((*it)->tag_once()) {
 
245
              out.push_back(*it);
 
246
            }
 
247
          }
 
248
        }
 
249
      }
 
250
    }
 
251
 
 
252
    void Octree::doFindFaces(const carve::geom::aabb<3> &aabb,
 
253
                             Node *node,
 
254
                             std::vector<const carve::poly::Face<3>*> &out,
 
255
                             unsigned depth) const {
 
256
      if (node == NULL) {
 
257
        return;
 
258
      }
 
259
 
 
260
      if (node->aabb.intersects(aabb)) {
 
261
        if (node->hasChildren()) {
 
262
          for (int i = 0; i < 8; ++i) {
 
263
            doFindFaces(aabb, node->children[i], out, depth + 1);
 
264
          }
 
265
        } else {
 
266
          if (depth < MAX_SPLIT_DEPTH && node->faces.size() > FACE_SPLIT_THRESHOLD) {
 
267
            if (!node->split()) {
 
268
              for (int i = 0; i < 8; ++i) {
 
269
                doFindFaces(aabb, node->children[i], out, depth + 1);
 
270
              }
 
271
              return;
 
272
            }
 
273
          }
 
274
          for (std::vector<const carve::poly::Face<3>*>::const_iterator it = node->faces.begin(), e = node->faces.end(); it != e; ++it) {
 
275
            if ((*it)->tag_once()) {
 
276
              out.push_back(*it);
 
277
            }
 
278
          }
 
279
        }
 
280
      }
 
281
    }
 
282
 
 
283
    void Octree::doFindFaces(const carve::geom3d::LineSegment &l,
 
284
                             Node *node,
 
285
                             std::vector<const carve::poly::Face<3>*> &out,
 
286
                             unsigned depth) const {
 
287
      if (node == NULL) {
 
288
        return;
 
289
      }
 
290
 
 
291
      if (node->aabb.intersectsLineSegment(l.v1, l.v2)) {
 
292
        if (node->hasChildren()) {
 
293
          for (int i = 0; i < 8; ++i) {
 
294
            doFindFaces(l, node->children[i], out, depth + 1);
 
295
          }
 
296
        } else {
 
297
          if (depth < MAX_SPLIT_DEPTH && node->faces.size() > FACE_SPLIT_THRESHOLD) {
 
298
            if (!node->split()) {
 
299
              for (int i = 0; i < 8; ++i) {
 
300
                doFindFaces(l, node->children[i], out, depth + 1);
 
301
              }
 
302
              return;
 
303
            }
 
304
          }
 
305
          for (std::vector<const carve::poly::Face<3>*>::const_iterator it = node->faces.begin(), e = node->faces.end(); it != e; ++it) {
 
306
            if ((*it)->tag_once()) {
 
307
              out.push_back(*it);
 
308
            }
 
309
          }
 
310
        }
 
311
      }
 
312
    }
 
313
 
 
314
    void Octree::doFindVerticesAllowDupes(const carve::geom3d::Vector &v, Node *node, std::vector<const carve::poly::Vertex<3> *> &out, unsigned depth) const {
 
315
      if (node == NULL) {
 
316
        return;
 
317
      }
 
318
 
 
319
      if (node->aabb.containsPoint(v)) {
 
320
        if (node->hasChildren()) {
 
321
          for (int i = 0; i < 8; ++i) {
 
322
            doFindVerticesAllowDupes(v, node->children[i], out, depth + 1);
 
323
          }
 
324
        } else {
 
325
          if (depth < MAX_SPLIT_DEPTH && node->vertices.size() > POINT_SPLIT_THRESHOLD) {
 
326
            if (!node->split()) {
 
327
              for (int i = 0; i < 8; ++i) {
 
328
                doFindVerticesAllowDupes(v, node->children[i], out, depth + 1);
 
329
              }
 
330
              return;
 
331
            }
 
332
          }
 
333
          for (std::vector<const carve::poly::Vertex<3> *>::const_iterator it = node->vertices.begin(), e = node->vertices.end(); it != e; ++it) {
 
334
            out.push_back(*it);
 
335
          }
 
336
        }
 
337
      }
 
338
    }
 
339
 
 
340
    void Octree::findEdgesNear(const carve::geom::aabb<3> &aabb, std::vector<const carve::poly::Edge<3>*> &out) const {
 
341
      tagable::tag_begin();
 
342
      doFindEdges(aabb, root, out, 0);
 
343
    }
 
344
 
 
345
    void Octree::findEdgesNear(const carve::geom3d::LineSegment &l, std::vector<const carve::poly::Edge<3>*> &out) const {
 
346
      tagable::tag_begin();
 
347
      doFindEdges(l, root, out, 0);
 
348
    }
 
349
 
 
350
    void Octree::findEdgesNear(const carve::poly::Edge<3> &e, std::vector<const carve::poly::Edge<3>*> &out) const {
 
351
      tagable::tag_begin();
 
352
      doFindEdges(carve::geom3d::LineSegment(e.v1->v, e.v2->v), root, out, 0);
 
353
    }
 
354
 
 
355
    void Octree::findEdgesNear(const carve::geom3d::Vector &v, std::vector<const carve::poly::Edge<3>*> &out) const {
 
356
      tagable::tag_begin();
 
357
      doFindEdges(v, root, out, 0);
 
358
    }
 
359
 
 
360
    void Octree::findFacesNear(const carve::geom::aabb<3> &aabb, std::vector<const carve::poly::Face<3>*> &out) const {
 
361
      tagable::tag_begin();
 
362
      doFindFaces(aabb, root, out, 0);
 
363
    }
 
364
 
 
365
    void Octree::findFacesNear(const carve::geom3d::LineSegment &l, std::vector<const carve::poly::Face<3>*> &out) const {
 
366
      tagable::tag_begin();
 
367
      doFindFaces(l, root, out, 0);
 
368
    }
 
369
 
 
370
    void Octree::findFacesNear(const carve::poly::Edge<3> &e, std::vector<const carve::poly::Face<3>*> &out) const {
 
371
      tagable::tag_begin();
 
372
      doFindFaces(carve::geom3d::LineSegment(e.v1->v, e.v2->v), root, out, 0);
 
373
    }
 
374
 
 
375
    void Octree::findVerticesNearAllowDupes(const carve::geom3d::Vector &v, std::vector<const carve::poly::Vertex<3> *> &out) const {
 
376
      tagable::tag_begin();
 
377
      doFindVerticesAllowDupes(v, root, out, 0);
 
378
    }
 
379
 
 
380
    void Octree::doSplit(int maxSplit, Node *node) {
 
381
      // Don't split down any further than 4 levels.
 
382
      if (maxSplit <= 0 || (node->edges.size() < 5 && node->faces.size() < 5)) {
 
383
        return;
 
384
      }
 
385
 
 
386
      if (!node->split()) {
 
387
        for (int i = 0; i < 8; ++i) {
 
388
          doSplit(maxSplit - 1, node->children[i]);
 
389
        }
 
390
      }
 
391
    }
 
392
 
 
393
    void Octree::splitTree() {
 
394
      // initially split 4 levels
 
395
      doSplit(0, root);
 
396
    }
 
397
 
 
398
  }
 
399
}