← Back to branch summary

~siretart/ubuntu/utopic/blender/libav10

« back to all changes in this revision

Viewing changes to extern/carve/include/carve/intersection.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/intersection.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
#include <carve/collection_types.hpp>
 
22
#include <carve/iobj.hpp>
 
23
 
 
24
namespace carve {
 
25
  namespace csg {
 
26
 
 
27
    /** 
 
28
     * \class Intersections
 
29
     * \brief Storage for computed intersections between vertices, edges and faces.
 
30
     * 
 
31
     */
 
32
    struct Intersections : public std::unordered_map<IObj, IObjVMapSmall, IObj_hash> {
 
33
      typedef carve::mesh::MeshSet<3>::vertex_t vertex_t;
 
34
      typedef carve::mesh::MeshSet<3>::edge_t   edge_t;
 
35
      typedef carve::mesh::MeshSet<3>::face_t   face_t;
 
36
 
 
37
      typedef std::unordered_map<IObj, IObjVMapSmall, IObj_hash> super;
 
38
 
 
39
      ~Intersections() {
 
40
      }
 
41
 
 
42
      /** 
 
43
       * \brief Record the position of intersection between a pair of intersection objects.
 
44
       * 
 
45
       * @param a The first intersecting object.
 
46
       * @param b The second intersecting object.
 
47
       * @param p The point of intersection.
 
48
       */
 
49
      void record(IObj a, IObj b, vertex_t *p) {
 
50
        if (a > b) std::swap(a, b);
 
51
        (*this)[a][b] = p;
 
52
        (*this)[b][a] = p;
 
53
      }
 
54
 
 
55
      /** 
 
56
       * \brief Test whether vertex \a v intersects face \a f.
 
57
       * 
 
58
       * @param v The vertex to test.
 
59
       * @param f The face to test.
 
60
       * 
 
61
       * @return true, if \a v intersects \a f.
 
62
       */
 
63
      bool intersectsFace(vertex_t *v, face_t *f) const;
 
64
 
 
65
      /** 
 
66
       * \brief Collect sets of vertices, edges and faces that intersect \a obj
 
67
       * 
 
68
       * @param[in] obj The intersection object to search for intersections.
 
69
       * @param[out] collect_v A vector of vertices intersecting \a obj.
 
70
       * @param[out] collect_e A vector of edges intersecting \a obj.
 
71
       * @param[out] collect_f A vector of faces intersecting \a obj.
 
72
       */
 
73
      void collect(const IObj &obj,
 
74
                   std::vector<vertex_t *> *collect_v,
 
75
                   std::vector<edge_t *> *collect_e,
 
76
                   std::vector<face_t *> *collect_f) const;
 
77
 
 
78
 
 
79
      /** 
 
80
       * \brief Determine whether two intersection objects intersect.
 
81
       * 
 
82
       * @param a The first intersection object.
 
83
       * @param b The second intersection object.
 
84
       * 
 
85
       * @return true, if \a a and \a b intersect.
 
86
       */
 
87
      bool intersectsExactly(const IObj &a, const IObj &b) {
 
88
        Intersections::const_iterator i = find(a);
 
89
        if (i == end()) return false;
 
90
        return i->second.find(b) != i->second.end();
 
91
      }
 
92
 
 
93
      /** 
 
94
       * \brief Determine whether an intersection object intersects a vertex.
 
95
       * 
 
96
       * @param a The intersection object.
 
97
       * @param v The vertex.
 
98
       * 
 
99
       * @return true, if \a a and \a v intersect.
 
100
       */
 
101
      bool intersects(const IObj &a, vertex_t *v) {
 
102
        Intersections::const_iterator i = find(a);
 
103
        if (i == end()) return false;
 
104
        if (i->second.find(v) != i->second.end()) return true;
 
105
        return false;
 
106
      }
 
107
 
 
108
      /** 
 
109
       * \brief Determine whether an intersection object intersects an edge.
 
110
       * 
 
111
       * @param a The intersection object.
 
112
       * @param e The edge.
 
113
       * 
 
114
       * @return true, if \a a and \a e intersect (either on the edge,
 
115
       *         or at either endpoint).
 
116
       */
 
117
      bool intersects(const IObj &a, edge_t *e) {
 
118
        Intersections::const_iterator i = find(a);
 
119
        if (i == end()) return false;
 
120
        for (super::data_type::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
 
121
          const IObj &obj = j->first;
 
122
          switch (obj.obtype) {
 
123
          case IObj::OBTYPE_VERTEX:
 
124
            if (obj.vertex == e->v1() || obj.vertex == e->v2()) return true;
 
125
            break;
 
126
          case IObj::OBTYPE_EDGE:
 
127
            if (obj.edge == e) return true;
 
128
            break;
 
129
          default:
 
130
            break;
 
131
          }
 
132
        }
 
133
        return false;
 
134
      }
 
135
 
 
136
      /** 
 
137
       * \brief Determine whether an intersection object intersects a face.
 
138
       * 
 
139
       * @param a The intersection object.
 
140
       * @param f The face.
 
141
       * 
 
142
       * @return true, if \a a and \a f intersect (either on the face,
 
143
       *         or at any associated edge or vertex).
 
144
       */
 
145
      bool intersects(const IObj &a, face_t *f) {
 
146
        Intersections::const_iterator i = find(a);
 
147
        if (i == end()) return false;
 
148
        if (i->second.find(f) != i->second.end()) return true;
 
149
        edge_t *e = f->edge;
 
150
        do {
 
151
          if (i->second.find(e) != i->second.end()) return true;
 
152
          if (i->second.find(e->vert) != i->second.end()) return true;
 
153
          e = e->next;
 
154
        } while (e != f->edge);
 
155
        return false;
 
156
      }
 
157
 
 
158
      /** 
 
159
       * \brief Determine whether an edge intersects another edge.
 
160
       * 
 
161
       * @param e The edge.
 
162
       * @param f The face.
 
163
       * 
 
164
       * @return true, if \a e and \a f intersect.
 
165
       */
 
166
      bool intersects(edge_t *e1, edge_t *e2) {
 
167
        if (intersects(e1->v1(), e2) || intersects(e1->v2(), e2) || intersects(IObj(e1), e2)) return true;
 
168
        return false;
 
169
      }
 
170
 
 
171
      /** 
 
172
       * \brief Determine whether an edge intersects a face.
 
173
       * 
 
174
       * @param e The edge.
 
175
       * @param f The face.
 
176
       * 
 
177
       * @return true, if \a e and \a f intersect.
 
178
       */
 
179
      bool intersects(edge_t *e, face_t *f) {
 
180
        if (intersects(e->v1(), f) || intersects(e->v2(), f) || intersects(IObj(e), f)) return true;
 
181
        return false;
 
182
      }
 
183
 
 
184
      /** 
 
185
       * \brief Determine the faces intersected by an edge.
 
186
       * 
 
187
       * @tparam face_set_t A collection type holding face_t *
 
188
       * @param[in] e The edge.
 
189
       * @param[out] f The resulting set of faces.
 
190
       */
 
191
      template<typename face_set_t>
 
192
      void intersectedFaces(edge_t *e, face_set_t &f) const {
 
193
        std::vector<face_t *> intersected_faces;
 
194
        std::vector<edge_t *> intersected_edges;
 
195
        std::vector<vertex_t *> intersected_vertices;
 
196
 
 
197
        collect(e, &intersected_vertices, &intersected_edges, &intersected_faces);
 
198
 
 
199
        for (unsigned i = 0; i < intersected_vertices.size(); ++i) {
 
200
          facesForVertex(intersected_vertices[i], f);
 
201
        }
 
202
        for (unsigned i = 0; i < intersected_edges.size(); ++i) {
 
203
          facesForEdge(intersected_edges[i], f);
 
204
        }
 
205
        f.insert(intersected_faces.begin(), intersected_faces.end());
 
206
      }
 
207
 
 
208
      /** 
 
209
       * \brief Determine the faces intersected by a vertex.
 
210
       * 
 
211
       * @tparam face_set_t A collection type holding face_t *
 
212
       * @param[in] v The vertex.
 
213
       * @param[out] f The resulting set of faces.
 
214
       */
 
215
      template<typename face_set_t>
 
216
      void intersectedFaces(vertex_t *v, face_set_t &f) const {
 
217
        std::vector<face_t *> intersected_faces;
 
218
        std::vector<edge_t *> intersected_edges;
 
219
        std::vector<vertex_t *> intersected_vertices;
 
220
 
 
221
        collect(v, &intersected_vertices, &intersected_edges, &intersected_faces);
 
222
 
 
223
        for (unsigned i = 0; i < intersected_vertices.size(); ++i) {
 
224
          facesForVertex(intersected_vertices[i], f);
 
225
        }
 
226
        for (unsigned i = 0; i < intersected_edges.size(); ++i) {
 
227
          facesForEdge(intersected_edges[i], f);
 
228
        }
 
229
        f.insert(intersected_faces.begin(), intersected_faces.end());
 
230
      }
 
231
 
 
232
      /** 
 
233
       * \brief Collect the set of faces that contain all vertices in \a verts.
 
234
       * 
 
235
       * @tparam vertex_set_t A collection type holding vertex_t *
 
236
       * @tparam face_set_t A collection type holding face_t *
 
237
       * @param[in] verts A set of vertices.
 
238
       * @param[out] result The resulting set of faces.
 
239
       */
 
240
      template<typename vertex_set_t, typename face_set_t>
 
241
      void commonFaces(const vertex_set_t &verts, face_set_t &result) {
 
242
 
 
243
        std::set<face_t *> ifaces, temp, out;
 
244
        typename vertex_set_t::const_iterator i = verts.begin();
 
245
        if (i == verts.end()) return;
 
246
        intersectedFaces((*i), ifaces);
 
247
        while (++i != verts.end()) {
 
248
          temp.clear();
 
249
          intersectedFaces((*i), temp);
 
250
 
 
251
          out.clear();
 
252
          std::set_intersection(temp.begin(), temp.end(),
 
253
                                ifaces.begin(), ifaces.end(),
 
254
                                set_inserter(out));
 
255
          ifaces.swap(out);
 
256
        }
 
257
        std::copy(ifaces.begin(), ifaces.end(), set_inserter(result));
 
258
      }
 
259
 
 
260
      void clear() {
 
261
        super::clear();
 
262
      }
 
263
 
 
264
    };
 
265
 
 
266
  }
 
267
}