Bundle latest version of Carve library which shall resolve compilation issues with...
[blender.git] / extern / carve / include / carve / polyhedron_impl.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/timing.hpp>
21
22 #include <assert.h>
23 #include <list>
24
25 namespace carve {
26   namespace poly {
27
28
29
30     template<typename order_t>
31     struct VPtrSort {
32       order_t order;
33
34       VPtrSort(const order_t &_order) : order(_order) {}
35       bool operator()(carve::poly::Polyhedron::vertex_t const *a,
36                       carve::poly::Polyhedron::vertex_t const *b) const {
37         return order(a->v, b->v);
38       }
39     };
40
41     template<typename order_t>
42     bool Geometry<3>::orderVertices(order_t order) {
43       static carve::TimingName FUNC_NAME("Geometry<3>::orderVertices()");
44       carve::TimingBlock block(FUNC_NAME);
45
46       std::vector<vertex_t *> vptr;
47       std::vector<vertex_t *> vmap;
48       std::vector<vertex_t> vout;
49       const size_t N = vertices.size();
50
51       vptr.reserve(N);
52       vout.reserve(N);
53       vmap.resize(N);
54
55       for (size_t i = 0; i != N; ++i) {
56         vptr.push_back(&vertices[i]);
57       }
58       std::sort(vptr.begin(), vptr.end(), VPtrSort<order_t>(order));
59
60       for (size_t i = 0; i != N; ++i) {
61         vout.push_back(*vptr[i]);
62         vmap[vertexToIndex_fast(vptr[i])] = &vout[i];
63       }
64
65       for (size_t i = 0; i < faces.size(); ++i) {
66         face_t &f = faces[i];
67         for (size_t j = 0; j < f.nVertices(); ++j) {
68           f.vertex(j) = vmap[vertexToIndex_fast(f.vertex(j))];
69         }
70       }
71       for (size_t i = 0; i < edges.size(); ++i) {
72         edges[i].v1 = vmap[vertexToIndex_fast(edges[i].v1)];
73         edges[i].v2 = vmap[vertexToIndex_fast(edges[i].v2)];
74       }
75
76       vout.swap(vertices);
77
78       return true;
79     }
80
81
82
83     template<typename T>
84     int Geometry<3>::_faceNeighbourhood(const face_t *f, int depth, T *result) const {
85       if (depth < 0 || f->is_tagged()) return 0;
86
87       f->tag();
88       *(*result)++ = f;
89
90       int r = 1;
91       for (size_t i = 0; i < f->nEdges(); ++i) {
92         const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(f->edge(i))];
93         const face_t *f2 = connectedFace(f, f->edge(i));
94         if (f2) {
95           r += _faceNeighbourhood(f2, depth - 1, (*result));
96         }
97       }
98       return r;
99     }
100
101
102
103     template<typename T>
104     int Geometry<3>::faceNeighbourhood(const face_t *f, int depth, T result) const {
105       tagable::tag_begin();
106
107       return _faceNeighbourhood(f, depth, &result);
108     }
109
110
111
112     template<typename T>
113     int Geometry<3>::faceNeighbourhood(const edge_t *e, int m_id, int depth, T result) const {
114       tagable::tag_begin();
115
116       int r = 0;
117       const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)];
118       for (size_t i = 0; i < edge_faces.size(); ++i) {
119         const face_t *f = edge_faces[i];
120         if (f && f->manifold_id == m_id) { r += _faceNeighbourhood(f, depth, &result); }
121       }
122       return r;
123     }
124
125
126
127     template<typename T>
128     int Geometry<3>::faceNeighbourhood(const vertex_t *v, int m_id, int depth, T result) const {
129       tagable::tag_begin();
130
131       int r = 0;
132       const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[vertexToIndex_fast(v)];
133       for (size_t i = 0; i < vertex_faces.size(); ++i) {
134         const face_t *f = vertex_faces[i];
135         if (f && f->manifold_id == m_id) { r += _faceNeighbourhood(f, depth, &result); }
136       }
137       return r;
138     }
139
140
141
142     // accessing connectivity information.
143     template<typename T>
144     int Geometry<3>::vertexToEdges(const vertex_t *v, T result) const {
145       const std::vector<const edge_t *> &e = connectivity.vertex_to_edge[vertexToIndex_fast(v)];
146       std::copy(e.begin(), e.end(), result);
147       return e.size();
148     }
149
150
151
152     template<typename T>
153     int Geometry<3>::vertexToFaces(const vertex_t *v, T result) const {
154       const std::vector<const face_t *> &vertex_faces = connectivity.vertex_to_face[vertexToIndex_fast(v)];
155       int c = 0;
156       for (size_t i = 0; i < vertex_faces.size(); ++i) {
157         *result++ = vertex_faces[i]; ++c;
158       }
159       return c;
160     }
161
162
163
164     template<typename T>
165     int Geometry<3>::edgeToFaces(const edge_t *e, T result) const {
166       const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)];
167       int c = 0;
168       for (size_t i = 0; i < edge_faces.size(); ++i) {
169         if (edge_faces[i] != NULL) { *result++ = edge_faces[i]; ++c; }
170       }
171       return c;
172     }
173
174
175
176     inline const Geometry<3>::face_t *Geometry<3>::connectedFace(const face_t *f, const edge_t *e) const {
177       const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)];
178       for (size_t i = 0; i < (edge_faces.size() & ~1U); i++) {
179         if (edge_faces[i] == f) return edge_faces[i^1];
180       }
181       return NULL;
182     }
183
184
185
186     inline void Polyhedron::invert(int m_id) {
187       std::vector<bool> selected_manifolds(manifold_is_closed.size(), false);
188       if (m_id >=0 && (unsigned)m_id < selected_manifolds.size()) selected_manifolds[m_id] = true;
189       invert(selected_manifolds);
190     }
191
192
193     
194     inline void Polyhedron::invert() {
195       invertAll();
196     }
197
198
199
200     inline bool Polyhedron::edgeOnManifold(const edge_t *e, int m_id) const {
201       const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)];
202
203       for (size_t i = 0; i < edge_faces.size(); ++i) {
204         if (edge_faces[i] && edge_faces[i]->manifold_id == m_id) return true;
205       }
206       return false;
207     }
208
209     inline bool Polyhedron::vertexOnManifold(const vertex_t *v, int m_id) const {
210       const std::vector<const face_t *> &f = connectivity.vertex_to_face[vertexToIndex_fast(v)];
211
212       for (size_t i = 0; i < f.size(); ++i) {
213         if (f[i]->manifold_id == m_id) return true;
214       }
215       return false;
216     }
217
218
219
220     template<typename T>
221     int Polyhedron::edgeManifolds(const edge_t *e, T result) const {
222       const std::vector<const face_t *> &edge_faces = connectivity.edge_to_face[edgeToIndex_fast(e)];
223
224       for (size_t i = 0; i < (edge_faces.size() & ~1U); i += 2) {
225         const face_t *f1 = edge_faces[i];
226         const face_t *f2 = edge_faces[i+1];
227         assert (f1 || f2);
228         if (f1)
229           *result++ = f1->manifold_id;
230         else if (f2)
231           *result++ = f2->manifold_id;
232       }
233       return edge_faces.size() >> 1;
234     }
235
236
237
238     template<typename T>
239     int Polyhedron::vertexManifolds(const vertex_t *v, T result) const {
240       const std::vector<const face_t *> &f = connectivity.vertex_to_face[vertexToIndex_fast(v)];
241       std::set<int> em;
242
243       for (size_t i = 0; i < f.size(); ++i) {
244         em.insert(f[i]->manifold_id);
245       }
246
247       std::copy(em.begin(), em.end(), result);
248       return em.size();
249     }
250
251
252
253     template<typename T>
254     void Polyhedron::transform(const T &xform) {
255       for (size_t i = 0; i < vertices.size(); i++) {
256         vertices[i].v = xform(vertices[i].v);
257       }
258       faceRecalc();
259       init();
260     }
261
262
263
264     inline size_t Polyhedron::manifoldCount() const {
265       return manifold_is_closed.size();
266     }
267
268
269
270     inline bool Polyhedron::hasOpenManifolds() const {
271       for (size_t i = 0; i < manifold_is_closed.size(); ++i) {
272         if (!manifold_is_closed[i]) return true;
273       }
274       return false;
275     }
276
277
278
279     inline std::ostream &operator<<(std::ostream &o, const Polyhedron &p) {
280       p.print(o);
281       return o;
282     }
283
284
285
286   }
287 }