fix for carve memory leak, update carve to hg bf36d92ff093
[blender.git] / extern / carve / include / carve / csg.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 <list>
21 #include <vector>
22 #include <algorithm>
23
24 #include <carve/carve.hpp>
25
26 #include <carve/geom3d.hpp>
27
28 #include <carve/mesh.hpp>
29
30 #include <carve/collection_types.hpp>
31 #include <carve/classification.hpp>
32 #include <carve/iobj.hpp>
33 #include <carve/faceloop.hpp>
34 #include <carve/intersection.hpp>
35 #include <carve/rtree.hpp>
36
37 namespace carve {
38   namespace csg {
39
40     class VertexPool {
41       typedef carve::mesh::MeshSet<3>::vertex_t vertex_t;
42
43       const static unsigned blocksize = 1024;
44       typedef std::list<std::vector<vertex_t> > pool_t;
45       pool_t pool;
46     public:
47       void reset();
48       vertex_t *get(const vertex_t::vector_t &v = vertex_t::vector_t::ZERO());
49       bool inPool(vertex_t *v) const;
50
51       VertexPool();
52       ~VertexPool();
53     };
54
55
56
57     namespace detail {
58       struct Data;
59       class LoopEdges;
60     }
61
62     /** 
63      * \class CSG
64      * \brief The class responsible for the computation of CSG operations.
65      * 
66      */
67     class CSG {
68     private:
69
70     public:
71       typedef carve::mesh::MeshSet<3> meshset_t;
72
73       struct Hook {
74         /** 
75          * \class Hook
76          * \brief Provides API access to intermediate steps in CSG calculation.
77          * 
78          */
79         virtual void intersectionVertex(const meshset_t::vertex_t * /* vertex */,
80                                         const IObjPairSet & /* intersections */) {
81         }
82         virtual void processOutputFace(std::vector<meshset_t::face_t *> & /* faces */,
83                                        const meshset_t::face_t * /* orig_face */,
84                                        bool /* flipped */) {
85         }
86         virtual void resultFace(const meshset_t::face_t * /* new_face */,
87                                 const meshset_t::face_t * /* orig_face */,
88                                 bool /* flipped */) {
89         }
90
91         virtual ~Hook() {
92         }
93       };
94
95         /** 
96          * \class Hooks
97          * \brief Management of API hooks.
98          * 
99          */
100       class Hooks {
101       public:
102         enum {
103           RESULT_FACE_HOOK         = 0,
104           PROCESS_OUTPUT_FACE_HOOK = 1,
105           INTERSECTION_VERTEX_HOOK = 2,
106           HOOK_MAX                 = 3,
107
108           RESULT_FACE_BIT          = 0x0001,
109           PROCESS_OUTPUT_FACE_BIT  = 0x0002, 
110           INTERSECTION_VERTEX_BIT  = 0x0004
111        };
112
113         std::vector<std::list<Hook *> > hooks;
114
115         bool hasHook(unsigned hook_num);
116
117         void intersectionVertex(const meshset_t::vertex_t *vertex,
118                                 const IObjPairSet &intersections);
119
120         void processOutputFace(std::vector<meshset_t::face_t *> &faces,
121                                const meshset_t::face_t *orig_face,
122                                bool flipped);
123
124         void resultFace(const meshset_t::face_t *new_face,
125                         const meshset_t::face_t *orig_face,
126                         bool flipped);
127
128         void registerHook(Hook *hook, unsigned hook_bits);
129         void unregisterHook(Hook *hook);
130
131         void reset();
132
133         Hooks();
134         ~Hooks();
135       };
136
137         /** 
138          * \class Collector
139          * \brief Base class for objects responsible for selecting result from which form the result polyhedron.
140          * 
141          */
142       class Collector {
143         Collector(const Collector &);
144         Collector &operator=(const Collector &);
145
146       protected:
147
148       public:
149         virtual void collect(FaceLoopGroup *group, CSG::Hooks &) =0;
150         virtual meshset_t *done(CSG::Hooks &) =0;
151
152         Collector() {}
153         virtual ~Collector() {}
154       };
155
156     private:
157       typedef carve::geom::RTreeNode<3, carve::mesh::Face<3> *> face_rtree_t;
158       typedef std::unordered_map<carve::mesh::Face<3> *, std::vector<carve::mesh::Face<3> *> > face_pairs_t;
159
160       /// The computed intersection data.
161       Intersections intersections;
162
163       /// A map from intersection point to a set of intersections
164       /// represented by pairs of intersection objects.
165       VertexIntersections vertex_intersections;
166
167       /// A pool from which temporary vertices are allocated. Also
168       /// provides testing for pool membership.
169       VertexPool vertex_pool;
170
171       void init();
172
173       void makeVertexIntersections();
174
175       void groupIntersections();
176
177       void _generateVertexVertexIntersections(meshset_t::vertex_t *va,
178                                               meshset_t::edge_t *eb);
179       void generateVertexVertexIntersections(meshset_t::face_t *a,
180                                              const std::vector<meshset_t::face_t *> &b);
181
182       void _generateVertexEdgeIntersections(meshset_t::vertex_t *va,
183                                             meshset_t::edge_t *eb);
184       void generateVertexEdgeIntersections(meshset_t::face_t *a,
185                                            const std::vector<meshset_t::face_t *> &b);
186
187       void _generateEdgeEdgeIntersections(meshset_t::edge_t *ea,
188                                           meshset_t::edge_t *eb);
189       void generateEdgeEdgeIntersections(meshset_t::face_t *a,
190                                          const std::vector<meshset_t::face_t *> &b);
191
192       void _generateVertexFaceIntersections(meshset_t::face_t *fa,
193                                             meshset_t::edge_t *eb);
194       void generateVertexFaceIntersections(meshset_t::face_t *a,
195                                            const std::vector<meshset_t::face_t *> &b);
196
197       void _generateEdgeFaceIntersections(meshset_t::face_t *fa,
198                                           meshset_t::edge_t *eb);
199       void generateEdgeFaceIntersections(meshset_t::face_t *a,
200                                          const std::vector<meshset_t::face_t *> &b);
201
202       void generateIntersectionCandidates(meshset_t *a,
203                                           const face_rtree_t *a_node,
204                                           meshset_t *b,
205                                           const face_rtree_t *b_node,
206                                           face_pairs_t &face_pairs,
207                                           bool descend_a = true);
208       /** 
209        * \brief Compute all points of intersection between poly \a a and poly \a b
210        * 
211        * @param a Polyhedron a.
212        * @param b Polyhedron b.
213        */
214       void generateIntersections(meshset_t *a,
215                                  const face_rtree_t *a_node,
216                                  meshset_t *b,
217                                  const face_rtree_t *b_node,
218                                  detail::Data &data);
219
220       /** 
221        * \brief Generate tables of intersecting pairs of faces.
222        *
223        * @param[out] data Internal data-structure holding intersection info.
224        */
225       void intersectingFacePairs(detail::Data &data);
226
227       /** 
228        * \brief Divide edges in \a edges that are intersected by polyhedron \a poly
229        * 
230        * @param edges The edges to divide.
231        * @param[in] poly The polyhedron to divide against.
232        * @param[in,out] data Intersection information.
233        */
234       void divideEdges(
235         const std::vector<meshset_t::edge_t> &edges,
236         meshset_t *poly,
237         detail::Data &data);
238
239       void divideIntersectedEdges(detail::Data &data);
240
241       /** 
242        * \brief From the intersection points of pairs of intersecting faces, compute intersection edges.
243        * 
244        * @param[out] eclass Classification information about created edges.
245        * @param[in,out] data Intersection information.
246        */
247       void makeFaceEdges(
248         EdgeClassification &eclass,
249         detail::Data &data);
250
251       friend void classifyEasyFaces(
252         FaceLoopList &face_loops,
253         VertexClassification &vclass,
254         meshset_t *other_poly,
255         int other_poly_num,
256         CSG &csg,
257         CSG::Collector &collector);
258
259       size_t generateFaceLoops(
260         meshset_t *poly,
261         const detail::Data &data,
262         FaceLoopList &face_loops_out);
263
264
265
266       // intersect_group.cpp
267
268       /** 
269        * \brief Build a loop edge mapping from a list of face loops.
270        * 
271        * @param[in] loops A list of face loops.
272        * @param[in] edge_count A hint as to the number of edges in \a loops.
273        * @param[out] edge_map The calculated map of edges to loops.
274        */
275       void makeEdgeMap(
276         const FaceLoopList &loops,
277         size_t edge_count,
278         detail::LoopEdges &edge_map);
279
280       /** 
281        * \brief Divide a list of face loops into groups that are connected by at least one edge not present in \a no_cross.
282        * 
283        * @param[in] src The source mesh from which these loops derive.
284        * @param[in,out] face_loops The list of loops (will be emptied as a side effect)
285        * @param[in] loop_edges A loop edge map used for traversing connected loops.
286        * @param[in] no_cross A set of edges not to cross.
287        * @param[out] out_loops A list of grouped face loops.
288        */
289       void groupFaceLoops(
290         meshset_t *src,
291         FaceLoopList &face_loops,
292         const detail::LoopEdges &loop_edges,
293         const V2Set &no_cross,
294         FLGroupList &out_loops);
295
296       /** 
297        * \brief Find the set of edges shared between two edge maps.
298        * 
299        * @param[in] edge_map_a The first edge map.
300        * @param[in] edge_map_b The second edge map.
301        * @param[out] shared_edges The resulting set of common edges.
302        */
303       void findSharedEdges(
304         const detail::LoopEdges &edge_map_a,
305         const detail::LoopEdges &edge_map_b,
306         V2Set &shared_edges);
307
308
309       // intersect_classify_edge.cpp
310
311       /** 
312        * 
313        * 
314        * @param shared_edges 
315        * @param vclass 
316        * @param poly_a 
317        * @param a_loops_grouped 
318        * @param a_edge_map 
319        * @param poly_b 
320        * @param b_loops_grouped 
321        * @param b_edge_map 
322        * @param collector 
323        */
324       void classifyFaceGroupsEdge(
325         const V2Set &shared_edges,
326         VertexClassification &vclass,
327         meshset_t *poly_a,
328         const face_rtree_t *poly_a_rtree,
329         FLGroupList &a_loops_grouped,
330         const detail::LoopEdges &a_edge_map,
331         meshset_t *poly_b,
332         const face_rtree_t *poly_b_rtree,
333         FLGroupList &b_loops_grouped,
334         const detail::LoopEdges &b_edge_map,
335         CSG::Collector &collector);
336
337       // intersect_classify_group.cpp
338
339       /** 
340        * 
341        * 
342        * @param shared_edges 
343        * @param vclass 
344        * @param poly_a 
345        * @param a_loops_grouped 
346        * @param a_edge_map 
347        * @param poly_b 
348        * @param b_loops_grouped 
349        * @param b_edge_map 
350        * @param collector 
351        */
352       void classifyFaceGroups(
353         const V2Set &shared_edges,
354         VertexClassification &vclass,
355         meshset_t *poly_a, 
356         const face_rtree_t *poly_a_rtree,
357         FLGroupList &a_loops_grouped,
358         const detail::LoopEdges &a_edge_map,
359         meshset_t *poly_b,
360         const face_rtree_t *poly_b_rtree,
361         FLGroupList &b_loops_grouped,
362         const detail::LoopEdges &b_edge_map,
363         CSG::Collector &collector);
364
365       // intersect_half_classify_group.cpp
366
367       /** 
368        * 
369        * 
370        * @param shared_edges 
371        * @param vclass 
372        * @param poly_a 
373        * @param a_loops_grouped 
374        * @param a_edge_map 
375        * @param poly_b 
376        * @param b_loops_grouped 
377        * @param b_edge_map 
378        * @param FaceClass 
379        * @param b_out 
380        */
381       void halfClassifyFaceGroups(
382         const V2Set &shared_edges,
383         VertexClassification &vclass,
384         meshset_t *poly_a, 
385         const face_rtree_t *poly_a_rtree,
386         FLGroupList &a_loops_grouped,
387         const detail::LoopEdges &a_edge_map,
388         meshset_t *poly_b,
389         const face_rtree_t *poly_b_rtree,
390         FLGroupList &b_loops_grouped,
391         const detail::LoopEdges &b_edge_map,
392         std::list<std::pair<FaceClass, meshset_t  *> > &b_out);
393
394       // intersect.cpp
395
396       /** 
397        * \brief The main calculation method for CSG.
398        * 
399        * @param[in] a Polyhedron a
400        * @param[in] b Polyhedron b
401        * @param[out] vclass 
402        * @param[out] eclass 
403        * @param[out] a_face_loops 
404        * @param[out] b_face_loops 
405        * @param[out] a_edge_count 
406        * @param[out] b_edge_count 
407        */
408       void calc(
409         meshset_t  *a,
410         const face_rtree_t *a_rtree,
411         meshset_t  *b,
412         const face_rtree_t *b_rtree,
413         VertexClassification &vclass,
414         EdgeClassification &eclass,
415         FaceLoopList &a_face_loops,
416         FaceLoopList &b_face_loops,
417         size_t &a_edge_count,
418         size_t &b_edge_count);
419
420     public:
421       /**
422        * \enum OP
423        * \brief Enumeration of the supported CSG operations.
424        */
425       enum OP {
426         UNION,                  /**< in a or b. */
427         INTERSECTION,           /**< in a and b. */
428         A_MINUS_B,              /**< in a, but not b. */
429         B_MINUS_A,              /**< in b, but not a. */
430         SYMMETRIC_DIFFERENCE,   /**< in a or b, but not both. */
431         ALL                     /**< all split faces from a and b */
432       };
433
434       /**
435        * \enum CLASSIFY_TYPE
436        * \brief The type of classification algorithm to use.
437        */
438       enum CLASSIFY_TYPE {
439         CLASSIFY_NORMAL,        /**< Normal (group) classifier. */
440         CLASSIFY_EDGE           /**< Edge classifier. */
441       };
442
443       CSG::Hooks hooks;         /**< The manager for calculation hooks. */
444
445       CSG();
446       ~CSG();
447
448       /** 
449        * \brief Compute a CSG operation between two polyhedra, \a a and \a b.
450        * 
451        * @param a Polyhedron a
452        * @param b Polyhedron b
453        * @param collector The collector (determines the CSG operation performed)
454        * @param shared_edges A pointer to a set that will be populated with shared edges (if not NULL).
455        * @param classify_type The type of classifier to use.
456        * 
457        * @return 
458        */
459       meshset_t *compute(
460         meshset_t *a,
461         meshset_t *b,
462         CSG::Collector &collector,
463         V2Set *shared_edges = NULL,
464         CLASSIFY_TYPE classify_type = CLASSIFY_NORMAL);
465
466       /** 
467        * \brief Compute a CSG operation between two closed polyhedra, \a a and \a b.
468        * 
469        * @param a Polyhedron a
470        * @param b Polyhedron b
471        * @param op The CSG operation (A collector is created automatically).
472        * @param shared_edges A pointer to a set that will be populated with shared edges (if not NULL).
473        * @param classify_type The type of classifier to use.
474        * 
475        * @return 
476        */
477       meshset_t *compute(
478         meshset_t *a,
479         meshset_t *b,
480         OP op,
481         V2Set *shared_edges = NULL,
482         CLASSIFY_TYPE classify_type = CLASSIFY_NORMAL);
483
484       void slice(
485         meshset_t *a,
486         meshset_t *b,
487         std::list<meshset_t  *> &a_sliced,
488         std::list<meshset_t  *> &b_sliced,
489         V2Set *shared_edges = NULL);
490
491       bool sliceAndClassify(
492         meshset_t *closed,
493         meshset_t *open,
494         std::list<std::pair<FaceClass, meshset_t *> > &result,
495         V2Set *shared_edges = NULL);
496     };
497   }
498 }