← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/include/carve/octree_decl.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/octree_decl.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/geom3d.hpp>
 
23
#include <carve/aabb.hpp>
 
24
 
 
25
#include <carve/polyhedron_base.hpp>
 
26
 
 
27
namespace carve {
 
28
 
 
29
  namespace csg {
 
30
 
 
31
    const double SLACK_FACTOR=1.0009765625;
 
32
    const unsigned FACE_SPLIT_THRESHOLD=50U;
 
33
    const unsigned EDGE_SPLIT_THRESHOLD=50U;
 
34
    const unsigned POINT_SPLIT_THRESHOLD=20U;
 
35
    const unsigned MAX_SPLIT_DEPTH=32;
 
36
 
 
37
    class Octree {
 
38
 
 
39
    public:
 
40
      class Node {
 
41
      private:
 
42
        Node(const Node &node); // undefined.
 
43
        Node &operator=(const Node &node); // undefined.
 
44
 
 
45
      public:
 
46
        Node *parent;
 
47
        Node *children[8];
 
48
        bool is_leaf;
 
49
 
 
50
        carve::geom3d::Vector min;
 
51
        carve::geom3d::Vector max;
 
52
 
 
53
        std::vector<const carve::poly::Geometry<3>::face_t *> faces;
 
54
        std::vector<const carve::poly::Geometry<3>::edge_t *> edges;
 
55
        std::vector<const carve::poly::Geometry<3>::vertex_t *> vertices;
 
56
 
 
57
        carve::geom3d::AABB aabb;
 
58
 
 
59
        Node();
 
60
 
 
61
        Node(const carve::geom3d::Vector &newMin, const carve::geom3d::Vector &newMax);
 
62
        Node(Node *p, double x1, double y1, double z1, double x2, double y2, double z2);
 
63
 
 
64
        ~Node();
 
65
 
 
66
        bool mightContain(const carve::poly::Geometry<3>::face_t &face);
 
67
        bool mightContain(const carve::poly::Geometry<3>::edge_t &edge);
 
68
        bool mightContain(const carve::poly::Geometry<3>::vertex_t &p);
 
69
        bool hasChildren();
 
70
        bool hasGeometry();
 
71
 
 
72
        template <class T>
 
73
        void putInside(const T &input, Node *child, T &output);
 
74
 
 
75
        bool split();
 
76
      };
 
77
 
 
78
 
 
79
 
 
80
      Node *root;
 
81
 
 
82
 
 
83
 
 
84
      struct no_filter {
 
85
        bool operator()(const carve::poly::Geometry<3>::edge_t *) { return true; }
 
86
        bool operator()(const carve::poly::Geometry<3>::face_t *) { return true; }
 
87
      };
 
88
 
 
89
 
 
90
 
 
91
      Octree();
 
92
 
 
93
      ~Octree();
 
94
 
 
95
 
 
96
 
 
97
      void setBounds(const carve::geom3d::Vector &min, const carve::geom3d::Vector &max);
 
98
      void setBounds(carve::geom3d::AABB aabb);
 
99
 
 
100
 
 
101
 
 
102
      void addEdges(const std::vector<carve::poly::Geometry<3>::edge_t > &edges);
 
103
      void addFaces(const std::vector<carve::poly::Geometry<3>::face_t > &faces);
 
104
      void addVertices(const std::vector<const carve::poly::Geometry<3>::vertex_t *> &vertices);
 
105
 
 
106
 
 
107
 
 
108
      static carve::geom3d::AABB makeAABB(const Node *node);
 
109
 
 
110
 
 
111
 
 
112
      void doFindEdges(const carve::geom::aabb<3> &aabb,
 
113
                       Node *node,
 
114
                       std::vector<const carve::poly::Geometry<3>::edge_t *> &out,
 
115
                       unsigned depth) const;
 
116
      void doFindEdges(const carve::geom3d::LineSegment &l,
 
117
                       Node *node,
 
118
                       std::vector<const carve::poly::Geometry<3>::edge_t *> &out,
 
119
                       unsigned depth) const;
 
120
      void doFindEdges(const carve::geom3d::Vector &v,
 
121
                       Node *node,
 
122
                       std::vector<const carve::poly::Geometry<3>::edge_t *> &out,
 
123
                       unsigned depth) const;
 
124
      void doFindFaces(const carve::geom::aabb<3> &aabb,
 
125
                       Node *node,
 
126
                       std::vector<const carve::poly::Geometry<3>::face_t *> &out,
 
127
                       unsigned depth) const;
 
128
      void doFindFaces(const carve::geom3d::LineSegment &l,
 
129
                       Node *node,
 
130
                       std::vector<const carve::poly::Geometry<3>::face_t *> &out,
 
131
                       unsigned depth) const;
 
132
 
 
133
 
 
134
 
 
135
      void doFindVerticesAllowDupes(const carve::geom3d::Vector &v,
 
136
                                    Node *node,
 
137
                                    std::vector<const carve::poly::Geometry<3>::vertex_t *> &out,
 
138
                                    unsigned depth) const;
 
139
 
 
140
      void findVerticesNearAllowDupes(const carve::geom3d::Vector &v,
 
141
                                      std::vector<const carve::poly::Geometry<3>::vertex_t *> &out) const;
 
142
 
 
143
 
 
144
 
 
145
      template<typename filter_t>
 
146
      void doFindEdges(const carve::poly::Geometry<3>::face_t &f, Node *node,
 
147
                       std::vector<const carve::poly::Geometry<3>::edge_t *> &out,
 
148
                       unsigned depth,
 
149
                       filter_t filter) const;
 
150
 
 
151
      template<typename filter_t>
 
152
      void findEdgesNear(const carve::poly::Geometry<3>::face_t &f,
 
153
                         std::vector<const carve::poly::Geometry<3>::edge_t *> &out,
 
154
                         filter_t filter) const;
 
155
 
 
156
      void findEdgesNear(const carve::poly::Geometry<3>::face_t &f,
 
157
                         std::vector<const carve::poly::Geometry<3>::edge_t *> &out) const {
 
158
        return findEdgesNear(f, out, no_filter());
 
159
      }
 
160
 
 
161
 
 
162
 
 
163
      void findEdgesNear(const carve::geom::aabb<3> &aabb, std::vector<const carve::poly::Geometry<3>::edge_t *> &out) const;
 
164
      void findEdgesNear(const carve::geom3d::LineSegment &l, std::vector<const carve::poly::Geometry<3>::edge_t *> &out) const;
 
165
      void findEdgesNear(const carve::poly::Geometry<3>::edge_t &e, std::vector<const carve::poly::Geometry<3>::edge_t *> &out) const;
 
166
      void findEdgesNear(const carve::geom3d::Vector &v, std::vector<const carve::poly::Geometry<3>::edge_t *> &out) const;
 
167
 
 
168
 
 
169
 
 
170
      void findFacesNear(const carve::geom::aabb<3> &aabb, std::vector<const carve::poly::Geometry<3>::face_t *> &out) const;
 
171
      void findFacesNear(const carve::geom3d::LineSegment &l, std::vector<const carve::poly::Geometry<3>::face_t *> &out) const;
 
172
      void findFacesNear(const carve::poly::Geometry<3>::edge_t &e, std::vector<const carve::poly::Geometry<3>::face_t *> &out) const;
 
173
 
 
174
 
 
175
 
 
176
      static void doSplit(int maxSplit, Node *node);
 
177
 
 
178
 
 
179
 
 
180
      template <typename FUNC>
 
181
      void doIterate(int level, Node *node, const FUNC &f) const;
 
182
 
 
183
      template <typename FUNC>
 
184
      void iterateNodes(const FUNC &f) const;
 
185
 
 
186
 
 
187
 
 
188
      void splitTree();
 
189
 
 
190
    };
 
191
 
 
192
  }
 
193
}