← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/include/carve/spacetree.hpp

  • 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/include/carve/spacetree.hpp
 
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
#pragma once
 
19
 
 
20
#include <carve/carve.hpp>
 
21
 
 
22
#include <carve/geom.hpp>
 
23
#include <carve/aabb.hpp>
 
24
#include <carve/vertex_decl.hpp>
 
25
#include <carve/edge_decl.hpp>
 
26
#include <carve/face_decl.hpp>
 
27
 
 
28
namespace carve {
 
29
 
 
30
  namespace space {
 
31
 
 
32
    static inline bool intersection_test(const carve::geom::aabb<3> &aabb, const carve::poly::Face<3> *face) {
 
33
      if (face->nVertices() == 3) {
 
34
        return aabb.intersects(carve::geom::tri<3>(face->vertex(0)->v, face->vertex(1)->v, face->vertex(2)->v));
 
35
      } else {
 
36
        // partial, conservative SAT.
 
37
        return aabb.intersects(face->aabb) && aabb.intersects(face->plane_eqn);
 
38
      }
 
39
    }
 
40
 
 
41
    static inline bool intersection_test(const carve::geom::aabb<3> &aabb, const carve::poly::Edge<3> *edge) {
 
42
      return aabb.intersectsLineSegment(edge->v1->v, edge->v2->v);
 
43
    }
 
44
 
 
45
    static inline bool intersection_test(const carve::geom::aabb<3> &aabb, const carve::poly::Vertex<3> *vertex) {
 
46
      return aabb.intersects(vertex->v);
 
47
    }
 
48
 
 
49
 
 
50
 
 
51
    struct nodedata_FaceEdge {
 
52
      std::vector<const carve::poly::Face<3> *> faces;
 
53
      std::vector<const carve::poly::Edge<3> *> edges;
 
54
 
 
55
      void add(const carve::poly::Face<3> *face) {
 
56
        faces.push_back(face);
 
57
      }
 
58
 
 
59
      void add(const carve::poly::Edge<3> *edge) {
 
60
        edges.push_back(edge);
 
61
      }
 
62
 
 
63
      template<typename iter_t>
 
64
      void _fetch(iter_t &iter, const carve::poly::Edge<3> *) {
 
65
        std::copy(edges.begin(), edges.end(), iter);
 
66
      }
 
67
 
 
68
      template<typename iter_t>
 
69
      void _fetch(iter_t &iter, const carve::poly::Face<3> *) {
 
70
        std::copy(faces.begin(), faces.end(), iter);
 
71
      }
 
72
 
 
73
      template<typename node_t>
 
74
      void propagate(node_t *node) {
 
75
      }
 
76
 
 
77
      template<typename iter_t>
 
78
      void fetch(iter_t &iter) {
 
79
        return _fetch(iter, std::iterator_traits<iter_t>::value_type);
 
80
      }
 
81
    };
 
82
 
 
83
 
 
84
 
 
85
    const static double SLACK_FACTOR = 1.0009765625;
 
86
    const static unsigned MAX_SPLIT_DEPTH = 32;
 
87
 
 
88
 
 
89
 
 
90
    template<unsigned n_dim, typename nodedata_t>
 
91
    class SpatialSubdivTree {
 
92
 
 
93
      typedef carve::geom::aabb<n_dim> aabb_t;
 
94
      typedef carve::geom::vector<n_dim> vector_t;
 
95
 
 
96
    public:
 
97
 
 
98
      class Node {
 
99
        enum {
 
100
          n_children = 1 << n_dim
 
101
        };
 
102
 
 
103
      public:
 
104
        Node *parent;
 
105
        Node *children;
 
106
 
 
107
        vector_t min;
 
108
        vector_t max;
 
109
 
 
110
        aabb_t aabb;
 
111
 
 
112
        nodedata_t data;
 
113
 
 
114
      private:
 
115
        Node(const Node &node); // undefined.
 
116
        Node &operator=(const Node &node); // undefined.
 
117
 
 
118
        Node() {
 
119
        }
 
120
 
 
121
        inline aabb_t makeAABB() const {
 
122
          vector_t centre = 0.5 * (min + max);
 
123
          vector_t size = SLACK_FACTOR * 0.5 * (max - min);
 
124
          return aabb_t(centre, size);
 
125
        }
 
126
 
 
127
        void setup(Node *_parent, const vector_t &_min, const vector_t &_max) {
 
128
          parent = _parent;
 
129
          min = _min;
 
130
          max = _max;
 
131
          aabb = makeAABB();
 
132
        }
 
133
 
 
134
        void alloc_children() {
 
135
          vector_t mid = 0.5 * (min + max);
 
136
          children = new Node[n_children];
 
137
          for (size_t i = 0; i < (n_children); ++i) {
 
138
            vector_t new_min, new_max;
 
139
            for (size_t c = 0; c < n_dim; ++c) {
 
140
              if (i & (1 << c)) {
 
141
                new_min.v[c] = min.v[c];
 
142
                new_max.v[c] = mid.v[c];
 
143
              } else {
 
144
                new_min.v[c] = mid.v[c];
 
145
                new_max.v[c] = max.v[c];
 
146
              }
 
147
            }
 
148
            children[i].setup(this, new_min, new_max);
 
149
          }
 
150
        }
 
151
 
 
152
        void dealloc_children() {
 
153
          delete [] children;
 
154
        }
 
155
 
 
156
      public:
 
157
 
 
158
        inline bool isLeaf() const { return children == NULL; }
 
159
 
 
160
        Node(Node *_parent, const vector_t &_min, const vector_t &_max) : parent(_parent), children(NULL), min(_min), max(_max) {
 
161
          aabb = makeAABB();
 
162
        }
 
163
 
 
164
        ~Node() {
 
165
          dealloc_children();
 
166
        }
 
167
 
 
168
        bool split() {
 
169
          if (isLeaf()) {
 
170
            alloc_children();
 
171
            data.propagate(this);
 
172
          }
 
173
          return isLeaf();
 
174
        }
 
175
 
 
176
        template<typename obj_t>
 
177
        void insert(const obj_t &object) {
 
178
          if (!isLeaf()) {
 
179
            for (size_t i = 0; i < n_children; ++i) {
 
180
              if (intersection_test(children[i].aabb, object)) {
 
181
                children[i].insert(object);
 
182
              }
 
183
            }
 
184
          } else {
 
185
            data.add(object);
 
186
          }
 
187
        }
 
188
 
 
189
        template<typename obj_t>
 
190
        void insertVector(typename std::vector<obj_t>::iterator beg, typename std::vector<obj_t>::iterator end) {
 
191
          if (isLeaf()) {
 
192
            while (beg != end) {
 
193
              data.add(*beg);
 
194
            }
 
195
          } else {
 
196
            for (size_t i = 0; i < n_children; ++i) {
 
197
              typename std::vector<obj_t>::iterator mid = std::partition(beg, end, std::bind1st(intersection_test, children[i].aabb));
 
198
              children[i].insertVector(beg, mid);
 
199
            }
 
200
          }
 
201
        }
 
202
 
 
203
        template<typename iter_t>
 
204
        void insertMany(iter_t begin, iter_t end) {
 
205
          if (isLeaf()) {
 
206
          }
 
207
        }
 
208
 
 
209
        template<typename obj_t, typename iter_t, typename filter_t>
 
210
        void findObjectsNear(const obj_t &object, iter_t &output, filter_t filter) {
 
211
          if (!isLeaf()) {
 
212
            for (size_t i = 0; i < n_children; ++i) {
 
213
              if (intersection_test(children[i].aabb, object)) {
 
214
                children[i].findObjectsNear(object, output, filter);
 
215
              }
 
216
            }
 
217
            return;
 
218
          }
 
219
          data.fetch(output);
 
220
        }
 
221
 
 
222
        // bool hasGeometry();
 
223
 
 
224
        // template <class T>
 
225
        // void putInside(const T &input, Node *child, T &output);
 
226
 
 
227
      };
 
228
 
 
229
 
 
230
 
 
231
      Node *root;
 
232
 
 
233
      SpatialSubdivTree(const vector_t &_min, const vector_t &_max) : root(new Node(NULL, _min, _max)) {
 
234
      }
 
235
 
 
236
      ~SpatialSubdivTree() {
 
237
        delete root;
 
238
      }
 
239
 
 
240
      struct no_filter {
 
241
        template<typename obj_t>
 
242
        bool operator()(const obj_t &obj) const {
 
243
          return true;
 
244
        }
 
245
      };
 
246
 
 
247
      struct tag_filter {
 
248
        template<typename obj_t>
 
249
        bool operator()(const obj_t &obj) const {
 
250
          return obj.tag_once();
 
251
        }
 
252
      };
 
253
 
 
254
      // in order to be used as an input, aabb_t::intersect(const obj_t &) must exist.
 
255
      template<typename obj_t, typename iter_t, typename filter_t>
 
256
      void findObjectsNear(const obj_t &object, iter_t output, filter_t filter) {
 
257
        if (!intersection_test(root->aabb, object)) return;
 
258
        root->findObjectsNear(root, object, output, filter);
 
259
      }
 
260
 
 
261
    };
 
262
 
 
263
  }
 
264
}