1 /*
2 Copyright (C) 2010-2014 Kristian Duske
3
4 This file is part of TrenchBroom.
5
6 TrenchBroom is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 TrenchBroom is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with TrenchBroom. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #ifndef Polyhedron_Subtract_h
21 #define Polyhedron_Subtract_h
22
23 template <typename T, typename FP, typename VP>
subtract(const Polyhedron & subtrahend)24 typename Polyhedron<T,FP,VP>::SubtractResult Polyhedron<T,FP,VP>::subtract(const Polyhedron& subtrahend) const {
25 Callback c;
26 return subtract(subtrahend, c);
27 }
28
29 template <typename T, typename FP, typename VP>
subtract(const Polyhedron & subtrahend,const Callback & callback)30 typename Polyhedron<T,FP,VP>::SubtractResult Polyhedron<T,FP,VP>::subtract(const Polyhedron& subtrahend, const Callback& callback) const {
31 Subtract subtract(*this, subtrahend, callback);
32
33 List& result = subtract.result();
34 Merge merge(result, callback);
35 return result;
36 }
37
38 template <typename T, typename FP, typename VP>
39 class Polyhedron<T,FP,VP>::Subtract {
40 private:
41 const Polyhedron& m_minuend;
42 Polyhedron m_subtrahend;
43 const Callback& m_callback;
44 typename Polyhedron::List m_fragments;
45
46 typedef typename V::LexicographicOrder VertexCmp;
47 typedef std::set<V, VertexCmp> PositionSet;
48 typedef std::map<V, V, VertexCmp> ClosestVertices;
49 typedef std::map<V, V, VertexCmp> MoveableVertices;
50
51 class VertexSetCmp {
52 public:
operator()53 bool operator()(const typename V::Set& lhs, const typename V::Set& rhs) const {
54 return compare(lhs, rhs) < 0;
55 }
56 private:
compare(const typename V::Set & lhs,const typename V::Set & rhs)57 int compare(const typename V::Set& lhs, const typename V::Set& rhs) const {
58 if (lhs.size() < rhs.size())
59 return -1;
60 if (lhs.size() > rhs.size())
61 return 1;
62
63 typename V::Set::const_iterator lIt = lhs.begin();
64 typename V::Set::const_iterator rIt = rhs.begin();
65 for (size_t i = 0; i < lhs.size(); ++i) {
66 const V& lPos = *lIt++;
67 const V& rPos = *rIt++;
68
69 const int cmp = lPos.compare(rPos);
70 if (cmp != 0)
71 return cmp;
72 }
73 return 0;
74 }
75 };
76
77 typedef std::set<typename V::Set, VertexSetCmp> FragmentVertexSet;
78 public:
Subtract(const Polyhedron & minuend,const Polyhedron & subtrahend,const Callback & callback)79 Subtract(const Polyhedron& minuend, const Polyhedron& subtrahend, const Callback& callback) :
80 m_minuend(minuend),
81 m_subtrahend(subtrahend),
82 m_callback(callback) {
83 if (clipSubtrahend()) {
84 m_fragments.push_back(m_minuend);
85 chopMinuend();
86 removeSubtrahend();
87 simplify();
88 }
89 }
90 public:
result()91 typename Polyhedron::List& result() {
92 return m_fragments;
93 }
94 private:
clipSubtrahend()95 bool clipSubtrahend() {
96 Face* first = m_minuend.faces().front();
97 Face* current = first;
98 do {
99 const ClipResult result = m_subtrahend.clip(m_callback.plane(current));
100 if (result.empty())
101 return false;
102 current = current->next();
103 } while (current != first);
104 return true;
105 }
106
chopMinuend()107 void chopMinuend() {
108 const Face* firstFace = m_subtrahend.faces().front();
109 const Face* currentFace = firstFace;
110 do {
111 const Plane<T,3> plane = m_callback.plane(currentFace);
112
113 typename Polyhedron::List::iterator it, end;
114 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it) {
115 Polyhedron front = *it;
116 const ClipResult clipResult = front.clip(plane);
117 if (clipResult.success()) {
118 it->clip(plane.flipped());
119 it = m_fragments.insert(it, front);
120 ++it;
121 }
122 }
123
124 currentFace = currentFace->next();
125 } while (currentFace != firstFace);
126 }
127
removeSubtrahend()128 void removeSubtrahend() {
129 const typename V::List vertices = V::asList(m_subtrahend.vertices().begin(), m_subtrahend.vertices().end(), GetVertexPosition());
130
131 typename Polyhedron::List::iterator it, end;
132 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it) {
133 const Polyhedron& fragment = *it;
134 if (fragment.hasVertices(vertices, 0.1)) {
135 m_fragments.erase(it);
136 return;
137 }
138 }
139 assert(false);
140 }
141
simplify()142 void simplify() {
143 FragmentVertexSet newFragments = buildNewFragments();
144 removeDuplicateFragments(newFragments);
145 rebuildFragments(newFragments);
146 }
147
buildNewFragments()148 FragmentVertexSet buildNewFragments() {
149 FragmentVertexSet result;
150
151 const ClosestVertices closest = findClosestVertices();
152 if (closest.empty())
153 return findFragmentVertices();
154
155 typename Polyhedron::List::iterator it, end;
156 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it) {
157 Polyhedron& fragment = *it;
158 typename V::Set newFragmentVertices;
159
160 const Vertex* firstVertex = fragment.vertices().front();
161 const Vertex* currentVertex = firstVertex;
162
163 do {
164 const V& currentPosition = currentVertex->position();
165 typename ClosestVertices::const_iterator clIt = closest.find(currentPosition);
166 if (clIt != closest.end()) {
167 const V& targetPosition = clIt->second;
168 newFragmentVertices.insert(targetPosition);
169 } else {
170 newFragmentVertices.insert(currentPosition);
171 }
172 currentVertex = currentVertex->next();
173 } while (currentVertex != firstVertex);
174
175 result.insert(newFragmentVertices);
176 }
177
178 return result;
179 }
180
findClosestVertices()181 ClosestVertices findClosestVertices() {
182 MoveableVertices moveableVertices = findMoveableVertices();
183 FragmentVertexSet fragmentVertices = findFragmentVertices();
184 return findClosestVertices(moveableVertices, fragmentVertices);
185 }
186
findMoveableVertices()187 MoveableVertices findMoveableVertices() const {
188 const PositionSet exclude = findExcludedVertices();
189 MoveableVertices result(VertexCmp(0.1));
190
191 typename Polyhedron::List::const_iterator it, end;
192 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it) {
193 const Polyhedron& fragment = *it;
194 findMoveableVertices(fragment, exclude, result);
195 }
196
197 return result;
198 }
199
findExcludedVertices()200 PositionSet findExcludedVertices() const {
201 PositionSet result(VertexCmp(0.1));
202 SetUtils::makeSet(V::asList(m_subtrahend.vertices().begin(), m_subtrahend.vertices().end(), GetVertexPosition()), result);
203 SetUtils::makeSet(V::asList(m_minuend.vertices().begin(), m_minuend.vertices().end(), GetVertexPosition()), result);
204 return result;
205 }
206
findMoveableVertices(const Polyhedron & fragment,const PositionSet & exclude,MoveableVertices & result)207 void findMoveableVertices(const Polyhedron& fragment, const PositionSet& exclude, MoveableVertices& result) const {
208 const Vertex* firstVertex = fragment.vertices().front();
209 const Vertex* currentVertex = firstVertex;
210 do {
211 const V& currentPosition = currentVertex->position();
212 if (exclude.count(currentPosition) == 0 && result.count(currentPosition) == 0)
213 result.insert(std::make_pair(currentPosition, m_minuend.findClosestVertex(currentPosition)->position()));
214 currentVertex = currentVertex->next();
215 } while (currentVertex != firstVertex);
216 }
217
findFragmentVertices()218 FragmentVertexSet findFragmentVertices() const {
219 FragmentVertexSet result;
220
221 typename Polyhedron::List::const_iterator it, end;
222 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it) {
223 const Polyhedron& fragment = *it;
224 typename V::Set vertices(VertexCmp(0.1));
225
226 const Vertex* firstVertex = fragment.vertices().front();
227 const Vertex* currentVertex = firstVertex;
228 do {
229 vertices.insert(currentVertex->position());
230 currentVertex = currentVertex->next();
231 } while (currentVertex != firstVertex);
232
233 result.insert(vertices);
234 }
235
236 return result;
237 }
238
findClosestVertices(const MoveableVertices & vertices,FragmentVertexSet & fragments)239 ClosestVertices findClosestVertices(const MoveableVertices& vertices, FragmentVertexSet& fragments) {
240 ClosestVertices result;
241
242 typename MoveableVertices::const_iterator vIt, vEnd;
243 for (vIt = vertices.begin(), vEnd = vertices.end(); vIt != vEnd; ++vIt) {
244 const V& vertexPosition = vIt->first;
245 const V& targetPosition = vIt->second;
246
247 if (applyVertexMove(vertexPosition, targetPosition, fragments))
248 result[vertexPosition] = targetPosition;
249 }
250
251 return result;
252 }
253
applyVertexMove(const V & vertexPosition,const V & targetPosition,FragmentVertexSet & fragments)254 bool applyVertexMove(const V& vertexPosition, const V& targetPosition, FragmentVertexSet& fragments) {
255 FragmentVertexSet newFragments;
256 typename FragmentVertexSet::const_iterator fIt,fEnd;
257 for (fIt = fragments.begin(), fEnd = fragments.end(); fIt != fEnd; ++fIt) {
258 typename V::Set newVertices = *fIt;
259
260 if (newVertices.erase(vertexPosition) > 0) {
261 newVertices.insert(targetPosition);
262
263 Polyhedron newFragment(newVertices);
264 if (newFragment.polyhedron()) {
265 if (newFragment.intersects(m_subtrahend))
266 return false;
267 }
268 }
269 newFragments.insert(newVertices);
270 }
271
272 using std::swap;
273 swap(fragments, newFragments);
274
275 return true;
276 }
277
containsIntersectingFragments(const List & fragments)278 bool containsIntersectingFragments(const List& fragments) const {
279 typename List::const_iterator first, second, end;
280 for (first = fragments.begin(), end = fragments.end(); first != end; ++first) {
281 for (second = first, std::advance(second, 1); second != end; ++second) {
282 if (first->intersects(*second))
283 return true;
284 }
285 }
286 return false;
287 }
288
removeDuplicateFragments(FragmentVertexSet & newFragments)289 void removeDuplicateFragments(FragmentVertexSet& newFragments) const {
290 FragmentVertexSet result;
291 const typename FragmentVertexSet::iterator end = newFragments.end();
292 while (!newFragments.empty()) {
293 typename FragmentVertexSet::iterator lIt = newFragments.begin();
294 typename FragmentVertexSet::iterator rIt = newFragments.begin(); ++rIt;
295 while (lIt != end && rIt != end) {
296 if (SetUtils::subset(*lIt, *rIt)) {
297 newFragments.erase(lIt);
298 lIt = end;
299 } else if (SetUtils::subset(*rIt, *lIt)) {
300 rIt = SetUtils::erase(newFragments, rIt);
301 } else {
302 ++rIt;
303 }
304 }
305 if (lIt != end) {
306 result.insert(*lIt);
307 newFragments.erase(lIt);
308 }
309 }
310
311 using std::swap;
312 swap(newFragments, result);
313 }
314
rebuildFragments(const FragmentVertexSet & newFragments)315 void rebuildFragments(const FragmentVertexSet& newFragments) {
316 m_fragments.clear();
317
318 typename FragmentVertexSet::const_iterator it, end;
319 for (it = newFragments.begin(), end = newFragments.end(); it != end; ++it) {
320 const typename V::Set& vertices = *it;
321 if (vertices.size() > 3) {
322 const Polyhedron fragment(vertices);
323 if (fragment.polyhedron())
324 m_fragments.push_back(fragment);
325 }
326 }
327 }
328 };
329
330 template <typename T, typename FP, typename VP>
331 class Polyhedron<T,FP,VP>::Partition {
332 private:
333 List& m_fragments;
334 public:
Partition(List & fragments)335 Partition(List& fragments) :
336 m_fragments(fragments) {}
337
338 };
339
340 template <typename T, typename FP, typename VP>
341 class Polyhedron<T,FP,VP>::Merge {
342 private:
343 struct NeighbourEntry {
344 size_t neighbour;
345 Face* face;
346 Face* neighbourFace;
347
348 typedef std::set<NeighbourEntry> Set;
349
NeighbourEntryNeighbourEntry350 NeighbourEntry(const size_t i_neighbour, Face* i_face, Face* i_neighbourFace) :
351 neighbour(i_neighbour),
352 face(i_face),
353 neighbourFace(i_neighbourFace) {
354 assert(face != NULL);
355 assert(neighbourFace != NULL);
356 }
357
358 bool operator<(const NeighbourEntry& other) const {
359 return neighbour < other.neighbour;
360 }
361 };
362
363 typedef std::vector<typename Polyhedron::List::iterator> IndexList;
364 typedef std::map<size_t, typename NeighbourEntry::Set> Neighbours;
365
366 typedef std::set<size_t> MergeGroup;
367
368 struct MergeGroupCmp {
369 public:
operatorMergeGroupCmp370 bool operator()(const MergeGroup& lhs, const MergeGroup& rhs) const {
371 return compare(lhs, rhs) < 0;
372 }
373 private:
compareMergeGroupCmp374 int compare(const MergeGroup& lhs, const MergeGroup& rhs) const {
375 if (lhs.size() < rhs.size())
376 return -1;
377 if (lhs.size() > rhs.size())
378 return 1;
379
380 typename MergeGroup::const_iterator lIt, lEnd, rIt;
381 for (lIt = lhs.begin(), rIt = rhs.begin(), lEnd = lhs.end(); lIt != lEnd; ++lIt, ++rIt) {
382 const size_t lIndex = *lIt;
383 const size_t rIndex = *rIt;
384 if (lIndex < rIndex)
385 return -1;
386 if (lIndex > rIndex)
387 return 1;
388 }
389
390 return 0;
391 }
392 };
393
394 typedef std::set<MergeGroup, MergeGroupCmp> MergeGroups;
395
396 typename Polyhedron::List& m_fragments;
397 const Callback& m_callback;
398 IndexList m_indices;
399 Neighbours m_neighbours;
400 MergeGroups m_mergeGroups;
401 public:
Merge(typename Polyhedron::List & fragments,const Callback & callback)402 Merge(typename Polyhedron::List& fragments, const Callback& callback) :
403 m_fragments(fragments),
404 m_callback(callback) {
405 initialize();
406 merge();
407 }
408 private:
initialize()409 void initialize() {
410 typename Polyhedron::List::iterator it, end;
411 for (it = m_fragments.begin(), end = m_fragments.end(); it != end; ++it)
412 m_indices.push_back(it);
413 }
414
merge()415 void merge() {
416 findMergeableNeighbours();
417 findMergeGroups();
418 partitionMergeGroups();
419 applyMergeGroups();
420 }
421
422 class FaceKey {
423 private:
424 typename V::Set m_vertices;
425 public:
FaceKey(const Face * face)426 FaceKey(const Face* face) {
427 const HalfEdge* first = face->boundary().front();
428 const HalfEdge* current = first;
429 do {
430 m_vertices.insert(current->origin()->position());
431 current = current->next();
432 } while (current != first);
433 }
434
435 bool operator<(const FaceKey& other) const {
436 return compare(other) < 0;
437 }
438 private:
compare(const FaceKey & other)439 int compare(const FaceKey& other) const {
440 typename V::Set::const_iterator myIt = m_vertices.begin();
441 typename V::Set::const_iterator otIt = other.m_vertices.begin();
442
443 for (size_t i = 0; i < m_vertices.size(); ++i) {
444 const V& myVertex = *myIt++;
445 const V& otVertex = *otIt++;
446 const int vertexCmp = myVertex.compare(otVertex);
447 if (vertexCmp != 0)
448 return vertexCmp;
449 }
450
451 return 0;
452 }
453 };
454
455
456 typedef std::pair<size_t, Face*> NeighbourFace;
457 typedef std::vector<NeighbourFace> NeighbourFaceList;
458 typedef std::map<FaceKey, NeighbourFaceList> NeighbourMap;
459
findMergeableNeighbours()460 void findMergeableNeighbours() {
461 const NeighbourMap neighbourMap = findNeighbours();
462 typename NeighbourMap::const_iterator nIt, nEnd;
463 for (nIt = neighbourMap.begin(), nEnd = neighbourMap.end(); nIt != nEnd; ++nIt) {
464 const NeighbourFaceList& neighbourFaces = nIt->second;
465 assert(neighbourFaces.size() <= 2);
466
467 if (neighbourFaces.size() == 2) {
468 const NeighbourFace& first = neighbourFaces[0];
469 const NeighbourFace& second = neighbourFaces[1];
470
471 const size_t firstIndex = first.first;
472 const size_t secondIndex = second.first;
473 Face* firstFace = first.second;
474 Face* secondFace = second.second;
475
476 if (mergeableNeighbours(secondFace, *m_indices[firstIndex])) {
477 m_neighbours[ firstIndex].insert(NeighbourEntry(secondIndex, firstFace, secondFace));
478 m_neighbours[secondIndex].insert(NeighbourEntry( firstIndex, secondFace, firstFace));
479 }
480 }
481 }
482 }
483
findNeighbours()484 NeighbourMap findNeighbours() {
485 NeighbourMap result;
486
487 for (size_t index = 0; index < m_indices.size(); ++index) {
488 const typename Polyhedron::List::iterator fIt = m_indices[index];
489 const Polyhedron& fragment = *fIt;
490 Face* firstFace = fragment.faces().front();
491 Face* currentFace = firstFace;
492 do {
493 const FaceKey key(currentFace);
494 NeighbourFaceList& neighbours = result[key];
495 assert(neighbours.size() < 2);
496 neighbours.push_back(std::make_pair(index, currentFace));
497 currentFace = currentFace->next();
498 } while (currentFace != firstFace);
499 }
500
501 return result;
502 }
503
mergeableNeighbours(const Face * sharedFace,const Polyhedron & neighbour)504 bool mergeableNeighbours(const Face* sharedFace, const Polyhedron& neighbour) const {
505 // The two polyhedra which share the given faces can be merged if no vertex of one polyhedron is visible by any
506 // other face of the other polyhedron other than the shared face.
507
508 const Vertex* firstVertex = neighbour.vertices().front();
509
510 const Face* currentFace = sharedFace->next(); // skip the shared face
511 do {
512 const Vertex* currentVertex = firstVertex;
513 do {
514 if (currentFace->visibleFrom(currentVertex->position()))
515 return false;
516 currentVertex = currentVertex->next();
517 } while (currentVertex != firstVertex);
518 currentFace = currentFace->next();
519 } while (currentFace != sharedFace);
520 return true;
521 }
522
findMergeGroups()523 void findMergeGroups() {
524 typename Neighbours::const_iterator nIt, nEnd;
525 for (nIt = m_neighbours.begin(), nEnd = m_neighbours.end(); nIt != nEnd; ++nIt) {
526 const size_t index1 = nIt->first;
527 const typename NeighbourEntry::Set& entries = nIt->second;
528
529 typename NeighbourEntry::Set::const_iterator eIt, eEnd;
530 for (eIt = entries.begin(), eEnd = entries.end(); eIt != eEnd; ++eIt) {
531 const NeighbourEntry& entry = *eIt;
532 const size_t index2 = entry.neighbour;
533
534 MergeGroup group;
535 group.insert(index1);
536 group.insert(index2);
537
538 const Polyhedron polyhedron = mergeGroup(group);
539
540 if (m_mergeGroups.count(group) == 0 &&
541 !expandMergeGroup(group, polyhedron, index1) &&
542 !expandMergeGroup(group, polyhedron, index2))
543 m_mergeGroups.insert(group);
544 }
545 }
546 }
547
expandMergeGroup(const MergeGroup & group,const Polyhedron & polyhedron,const size_t index1)548 bool expandMergeGroup(const MergeGroup& group, const Polyhedron& polyhedron, const size_t index1) {
549 const typename Neighbours::const_iterator nIt = m_neighbours.find(index1);
550 if (nIt == m_neighbours.end())
551 return false;
552
553 bool didExpand = false;
554 const typename NeighbourEntry::Set& entries = nIt->second;
555 typename NeighbourEntry::Set::const_iterator eIt, eEnd;
556 for (eIt = entries.begin(), eEnd = entries.end(); eIt != eEnd; ++eIt) {
557 MergeGroup newGroup = group;
558
559 const NeighbourEntry& entry = *eIt;
560 const size_t index2 = entry.neighbour;
561 const Face* neighbourFace = entry.neighbourFace;
562
563 if (mergeableNeighbours(neighbourFace, polyhedron) && newGroup.insert(index2).second) {
564 Polyhedron newPolyhedron = polyhedron;
565 newPolyhedron.merge(*m_indices[index2]);
566
567 if (m_mergeGroups.count(newGroup) == 0 &&
568 !expandMergeGroup(newGroup, newPolyhedron, index2)) {
569 m_mergeGroups.insert(newGroup);
570 didExpand = true;
571 }
572 }
573 }
574 return didExpand;
575 }
576
mergeGroup(const MergeGroup & group)577 Polyhedron mergeGroup(const MergeGroup& group) const {
578 MergeGroup::const_iterator it = group.begin();
579 MergeGroup::const_iterator end = group.end();
580
581 Polyhedron result = *m_indices[*it];
582 ++it;
583 while (it != end) {
584 result.merge(*m_indices[*it]);
585 ++it;
586 }
587
588 return result;
589 }
590
partitionMergeGroups()591 void partitionMergeGroups() {
592 MergeGroups newMergeGroups;
593 typename MergeGroups::iterator mFirst, mSecond;
594 while (!m_mergeGroups.empty()) {
595 mFirst = m_mergeGroups.begin();
596 mSecond = mFirst; ++mSecond;
597
598 const MergeGroup& first = *mFirst;
599 bool firstIsDisjoint = true;
600
601 while (mSecond != m_mergeGroups.end()) {
602 const MergeGroup& second = *mSecond;
603 MergeGroup intersection;
604
605 SetUtils::intersection(first, second, intersection);
606 if (!intersection.empty()) {
607 firstIsDisjoint = false;
608 if (first.size() == intersection.size()) {
609 // both sets are identical or first is a subset of second, erase first and break
610 m_mergeGroups.erase(mFirst);
611 } else if (second.size() == intersection.size()) {
612 // second is a subset of first, erase second and break
613 m_mergeGroups.erase(mSecond);
614 } else {
615 // the groups must be partitioned properly
616 MergeGroup firstMinusSecond;
617 MergeGroup secondMinusFirst;
618 SetUtils::minus(first, intersection, firstMinusSecond);
619 SetUtils::minus(second, intersection, secondMinusFirst);
620
621 // erase both first and second
622 m_mergeGroups.erase(mFirst);
623 m_mergeGroups.erase(mSecond);
624
625 // insert the new merge groups and break
626 m_mergeGroups.insert(intersection);
627 m_mergeGroups.insert(firstMinusSecond);
628 m_mergeGroups.insert(secondMinusFirst);
629 }
630 break;
631 } else {
632 ++mSecond;
633 }
634 }
635
636 if (firstIsDisjoint) {
637 newMergeGroups.insert(first);
638 m_mergeGroups.erase(mFirst);
639 }
640 }
641
642 using std::swap;
643 std::swap(m_mergeGroups, newMergeGroups);
644 }
645
applyMergeGroups()646 void applyMergeGroups() {
647 typename MergeGroups::const_iterator mIt, mEnd;
648 typename MergeGroup::const_iterator gIt, gEnd;
649 typename Polyhedron::List::iterator fIt;
650
651 for (mIt = m_mergeGroups.begin(), mEnd = m_mergeGroups.end(); mIt != mEnd; ++mIt) {
652 const MergeGroup& group = *mIt;
653 if (group.size() > 1) {
654 gIt = group.begin();
655 gEnd = group.end();
656
657 Polyhedron& master = *m_indices[*gIt++];
658 while (gIt != gEnd) {
659 fIt = m_indices[*gIt++];
660 master.merge(*fIt);
661 m_fragments.erase(fIt);
662 }
663 }
664 }
665 }
666 };
667
668 #endif /* Polyhedron_Subtract_h */
669