Fix T39608: Blender 2.70 crashes when performing union
[blender.git] / extern / carve / carve-util.h
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2014 Blender Foundation.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation,
22  *                 Sergey Sharybin
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 #ifndef __CARVE_UTIL_H__
28 #define __CARVE_UTIL_H__
29
30 #include <carve/csg.hpp>
31 #include <carve/geom3d.hpp>
32 #include <carve/interpolator.hpp>
33 #include <carve/mesh.hpp>
34 #include <carve/triangulator.hpp>
35
36 #include "carve-capi.h"
37
38 struct TriIdxCompare {
39         bool operator() (const carve::triangulate::tri_idx &left,
40                          const carve::triangulate::tri_idx &right) const {
41                 if (left.a < right.a) {
42                         return true;
43                 }
44                 else if (left.a > right.a) {
45                         return false;
46                 }
47
48                 if (left.b < right.b) {
49                         return true;
50                 }
51                 else if (left.b > right.b) {
52                         return false;
53                 }
54
55                 if (left.c < right.c) {
56                         return true;
57                 }
58                 else if (left.c > right.c) {
59                         return false;
60                 }
61
62                 return false;
63         }
64 };
65
66 typedef std::set<carve::triangulate::tri_idx, TriIdxCompare> TrianglesStorage;
67
68 void carve_getRescaleMinMax(const carve::mesh::MeshSet<3> *left,
69                             const carve::mesh::MeshSet<3> *right,
70                             carve::geom3d::Vector *min,
71                             carve::geom3d::Vector *max);
72
73 bool carve_unionIntersections(carve::csg::CSG *csg,
74                               carve::mesh::MeshSet<3> **left_r,
75                               carve::mesh::MeshSet<3> **right_r);
76
77 bool carve_checkPolyPlanarAndGetNormal(const std::vector<carve::geom3d::Vector> &vertices,
78                                        const int verts_per_poly,
79                                        const int *verts_of_poly,
80                                        carve::math::Matrix3 *axis_matrix_r);
81
82 int carve_triangulatePoly(struct ImportMeshData *import_data,
83                           CarveMeshImporter *mesh_importer,
84                           const std::vector<carve::geom3d::Vector> &vertices,
85                           const int verts_per_poly,
86                           const int *verts_of_poly,
87                           const carve::math::Matrix3 &axis_matrix,
88                           std::vector<int> *face_indices,
89                           TrianglesStorage *triangles_storage);
90
91 namespace carve {
92         namespace interpolate {
93
94                 template<typename attr_t>
95                 class VertexAttr : public Interpolator {
96                 public:
97                         typedef const meshset_t::vertex_t *key_t;
98
99                 protected:
100                         typedef std::unordered_map<key_t, attr_t> attrmap_t;
101
102                         attrmap_t attrs;
103
104                         virtual void resultFace(const carve::csg::CSG &csg,
105                                                 const meshset_t::face_t *new_face,
106                                                 const meshset_t::face_t *orig_face,
107                                                 bool flipped)
108                         {
109                                 typedef meshset_t::face_t::const_edge_iter_t const_edge_iter_t;
110                                 for (const_edge_iter_t new_edge_iter = new_face->begin();
111                                          new_edge_iter != new_face->end();
112                                          ++new_edge_iter)
113                                 {
114                                         typename attrmap_t::const_iterator found =
115                                                 attrs.find(new_edge_iter->vert);
116                                         if (found == attrs.end()) {
117                                                 for (const_edge_iter_t orig_edge_iter = orig_face->begin();
118                                                      orig_edge_iter != orig_face->end();
119                                                      ++orig_edge_iter)
120                                                 {
121                                                         if ((orig_edge_iter->vert->v - new_edge_iter->vert->v).length2() < 1e-5) {
122                                                                 attrs[new_edge_iter->vert] = attrs[orig_edge_iter->vert];
123                                                         }
124                                                 }
125                                         }
126                                 }
127                         }
128
129                 public:
130                         bool hasAttribute(const meshset_t::vertex_t *v) {
131                                 return attrs.find(v) != attrs.end();
132                         }
133
134                         const attr_t &getAttribute(const meshset_t::vertex_t *v, const attr_t &def = attr_t()) {
135                                 typename attrmap_t::const_iterator found = attrs.find(v);
136                                 if (found != attrs.end()) {
137                                         return found->second;
138                                 }
139                                 return def;
140                         }
141
142                         void setAttribute(const meshset_t::vertex_t *v, const attr_t &attr) {
143                                 attrs[v] = attr;
144                         }
145                 };
146
147                 template<typename attr_t>
148                 class SimpleFaceEdgeAttr : public Interpolator {
149                 public:
150                         typedef std::pair<const meshset_t::face_t *, unsigned> key_t;
151
152                 protected:
153                         typedef std::pair<const meshset_t::vertex_t *, const meshset_t::vertex_t *> vpair_t;
154
155                         struct key_hash {
156                                 size_t operator()(const key_t &v) const {
157                                         return size_t(v.first) ^ size_t(v.second);
158                                 }
159                         };
160                         struct vpair_hash {
161                                 size_t operator()(const vpair_t &v) const {
162                                         return size_t(v.first) ^ size_t(v.second);
163                                 }
164                         };
165
166                         typedef std::unordered_map<key_t, attr_t, key_hash> attrmap_t;
167                         typedef std::unordered_map<vpair_t, key_t, vpair_hash> edgedivmap_t;
168
169                         attrmap_t attrs;
170
171                         struct Hook : public Interpolator::Hook {
172                         public:
173                                 virtual unsigned hookBits() const {
174                                         return carve::csg::CSG::Hooks::PROCESS_OUTPUT_FACE_BIT;
175                                 }
176                                 Hook(Interpolator *_interpolator, const carve::csg::CSG &_csg) : Interpolator::Hook(_interpolator, _csg) {
177                                 }
178                                 virtual ~Hook() {
179                                 }
180                         };
181
182                         virtual Interpolator::Hook *makeHook(carve::csg::CSG &csg) {
183                                 return new Hook(this, csg);
184                         }
185
186                         virtual void processOutputFace(const carve::csg::CSG &csg,
187                                                        std::vector<carve::mesh::MeshSet<3>::face_t *> &new_faces,
188                                                        const meshset_t::face_t *orig_face,
189                                                        bool flipped) {
190                                 edgedivmap_t undiv;
191
192                                 for (meshset_t::face_t::const_edge_iter_t e = orig_face->begin(); e != orig_face->end(); ++e) {
193                                         key_t k(orig_face, e.idx());
194                                         typename attrmap_t::const_iterator attr_i = attrs.find(k);
195                                         if (attr_i == attrs.end()) {
196                                                 continue;
197                                         } else {
198                                                 undiv[vpair_t(e->v1(), e->v2())] = k;
199                                         }
200                                 }
201
202                                 for (size_t fnum = 0; fnum < new_faces.size(); ++fnum) {
203                                         const carve::mesh::MeshSet<3>::face_t *new_face = new_faces[fnum];
204                                         for (meshset_t::face_t::const_edge_iter_t e = new_face->begin(); e != new_face->end(); ++e) {
205                                                 key_t k(new_face, e.idx());
206
207                                                 vpair_t vp;
208                                                 if (!flipped) {
209                                                         vp = vpair_t(e->v1(), e->v2());
210                                                 } else {
211                                                         vp = vpair_t(e->v2(), e->v1());
212                                                 }
213                                                 typename edgedivmap_t::const_iterator vp_i;
214                                                 if ((vp_i = undiv.find(vp)) != undiv.end()) {
215                                                         attrs[k] = attrs[vp_i->second];
216                                                 }
217                                         }
218                                 }
219                         }
220
221                 public:
222
223                         bool hasAttribute(const meshset_t::face_t *f, unsigned e) {
224                                 return attrs.find(std::make_pair(f, e)) != attrs.end();
225                         }
226
227                         attr_t getAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &def = attr_t()) {
228                                 typename attrmap_t::const_iterator fv = attrs.find(std::make_pair(f, e));
229                                 if (fv != attrs.end()) {
230                                         return (*fv).second;
231                                 }
232                                 return def;
233                         }
234
235                         void setAttribute(const meshset_t::face_t *f, unsigned e, const attr_t &attr) {
236                                 attrs[std::make_pair(f, e)] = attr;
237                         }
238
239                         void copyAttribute(const meshset_t::face_t *face,
240                                            unsigned edge,
241                                            SimpleFaceEdgeAttr<attr_t> *interpolator) {
242                                 key_t key(face, edge);
243                                 typename attrmap_t::const_iterator fv = interpolator->attrs.find(key);
244                                 if (fv != interpolator->attrs.end()) {
245                                         attrs[key] = (*fv).second;
246                                 }
247                         }
248
249                         void swapAttributes(SimpleFaceEdgeAttr<attr_t> *interpolator) {
250                                 attrs.swap(interpolator->attrs);
251                         }
252
253                         SimpleFaceEdgeAttr() : Interpolator() {
254                         }
255
256                         virtual ~SimpleFaceEdgeAttr() {
257                         }
258                 };
259
260                 template<typename attr_t>
261                 class SwapableFaceEdgeAttr : public FaceEdgeAttr<attr_t> {
262                 public:
263                         typedef carve::mesh::MeshSet<3> meshset_t;
264
265                         void copyAttribute(const meshset_t::face_t *face,
266                                            unsigned edge,
267                                            SwapableFaceEdgeAttr<attr_t> *interpolator) {
268                                 typename FaceEdgeAttr<attr_t>::key_t key(face, edge);
269                                 typename FaceEdgeAttr<attr_t>::attrmap_t::const_iterator fv = interpolator->attrs.find(key);
270                                 if (fv != interpolator->attrs.end()) {
271                                         this->attrs[key] = (*fv).second;
272                                 }
273                         }
274
275                         void swapAttributes(SwapableFaceEdgeAttr<attr_t> *interpolator) {
276                                 this->attrs.swap(interpolator->attrs);
277                         }
278                 };
279         }  // namespace interpolate
280 }  // namespace carve
281
282 #endif  // __CARVE_UTIL_H__