refactored plugin api; refactored callback library; added signals library
[xonotic/netradiant.git] / radiant / csg.cpp
1 /*
2 Copyright (C) 1999-2006 Id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
4
5 This file is part of GtkRadiant.
6
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
20 */
21
22 #include "csg.h"
23
24 #include "debugging/debugging.h"
25
26 #include <list>
27
28 #include "map.h"
29 #include "brushmanip.h"
30 #include "brushnode.h"
31 #include "grid.h"
32
33 void Face_makeBrush(Face& face, const Brush& brush, brush_vector_t& out, float offset)
34 {
35   if(face.contributes())
36   {
37     out.push_back(new Brush(brush));
38     Face* newFace = out.back()->addFace(face);
39     if(newFace != 0)
40     {
41       newFace->flipWinding();
42       newFace->getPlane().offset(offset);
43       newFace->planeChanged();
44     }
45   }
46 }
47
48 class FaceMakeBrush
49 {
50   const Brush& brush;
51   brush_vector_t& out;
52   float offset;
53 public:
54   FaceMakeBrush(const Brush& brush, brush_vector_t& out, float offset)
55     : brush(brush), out(out), offset(offset)
56   {
57   }
58   void operator()(Face& face) const
59   {
60     Face_makeBrush(face, brush, out, offset);
61   }
62 };
63
64 void Brush_makeHollow(const Brush& brush, brush_vector_t& out, float offset)
65 {
66   Brush_forEachFace(brush, FaceMakeBrush(brush, out, offset));
67 }
68
69 class BrushHollowSelectedWalker : public scene::Graph::Walker
70 {
71   float m_offset;
72 public:
73   BrushHollowSelectedWalker(float offset)
74     : m_offset(offset)
75   {
76   }
77   bool pre(const scene::Path& path, scene::Instance& instance) const
78   {
79     if(path.top().get().visible())
80     {
81       Brush* brush = Node_getBrush(path.top());
82       if(brush != 0
83         && Instance_getSelectable(instance)->isSelected()
84         && path.size() > 1)
85       {
86         brush_vector_t out;
87         Brush_makeHollow(*brush, out, m_offset);
88         for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
89         {
90           (*i)->removeEmptyFaces();
91           NodeSmartReference node((new BrushNode())->node());
92           Node_getBrush(node)->copy(*(*i));
93           delete (*i);
94           Node_getTraversable(path.parent())->insert(node);
95         }
96       }
97     }
98     return true;
99   }
100 };
101
102 typedef std::list<Brush*> brushlist_t;
103
104 class BrushGatherSelected : public scene::Graph::Walker
105 {
106   brush_vector_t& m_brushlist;
107 public:
108   BrushGatherSelected(brush_vector_t& brushlist)
109     : m_brushlist(brushlist)
110   {
111   }
112   bool pre(const scene::Path& path, scene::Instance& instance) const
113   {
114     if(path.top().get().visible())
115     {
116       Brush* brush = Node_getBrush(path.top());
117       if(brush != 0
118         && Instance_getSelectable(instance)->isSelected())
119       {
120         m_brushlist.push_back(brush);
121       }
122     }
123     return true;
124   }
125 };
126
127 class BrushDeleteSelected : public scene::Graph::Walker
128 {
129 public:
130   bool pre(const scene::Path& path, scene::Instance& instance) const
131   {
132     return true;
133   }
134   void post(const scene::Path& path, scene::Instance& instance) const
135   {
136     if(path.top().get().visible())
137     {
138       Brush* brush = Node_getBrush(path.top());
139       if(brush != 0
140         && Instance_getSelectable(instance)->isSelected()
141         && path.size() > 1)
142       {
143         Path_deleteTop(path);
144       }
145     }
146   }
147 };
148
149 void Scene_BrushMakeHollow_Selected(scene::Graph& graph)
150 {
151   GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize()));
152   GlobalSceneGraph().traverse(BrushDeleteSelected());
153 }
154
155 /*
156 =============
157 CSG_MakeHollow
158 =============
159 */
160
161 void CSG_MakeHollow (void)
162 {
163   UndoableCommand undo("brushHollow");
164
165   Scene_BrushMakeHollow_Selected(GlobalSceneGraph());
166
167   SceneChangeNotify();
168 }
169
170 template<typename Functor>
171 class Dereference
172 {
173   const Functor& functor;
174 public:
175   typedef typename Functor::first_argument_type first_argument_type;
176   typedef typename Functor::result_type result_type;
177   Dereference(const Functor& functor) : functor(functor)
178   {
179   }
180   result_type operator()(first_argument_type firstArgument) const
181   {
182     return functor(*firstArgument);
183   }
184 };
185
186 template<typename Functor>
187 inline Dereference<Functor> makeDereference(const Functor& functor)
188 {
189   return Dereference<Functor>(functor);
190 }
191
192 template<typename Predicate>
193 Face* Brush_findIf(const Brush& brush, const Predicate& predicate)
194 {
195   Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
196   return i == brush.end() ? 0 : *i;
197 }
198
199 template<typename Caller>
200 class BindArguments1
201 {
202   typedef typename Caller::SecondArgument FirstBound;
203   FirstBound firstBound;
204 public:
205   typedef typename Caller::Return Return;
206   typedef typename Caller::FirstArgument FirstArgument;
207   BindArguments1(FirstBound firstBound)
208     : firstBound(firstBound)
209   {
210   }
211   Return operator()(FirstArgument firstArgument) const
212   {
213     return Caller::call(firstArgument, firstBound);
214   }
215 };
216
217 template<typename Caller>
218 class BindArguments2
219 {
220   typedef typename Caller::SecondArgument FirstBound;
221   typedef typename Caller::ThirdArgument SecondBound;
222   FirstBound firstBound;
223   SecondBound secondBound;
224 public:
225   typedef typename Caller::Return Return;
226   typedef typename Caller::FirstArgument FirstArgument;
227   BindArguments2(FirstBound firstBound, SecondBound secondBound)
228     : firstBound(firstBound), secondBound(secondBound)
229   {
230   }
231   Return operator()(FirstArgument firstArgument) const
232   {
233     return Caller::call(firstArgument, firstBound, secondBound);
234   }
235 };
236
237 template<typename Caller, typename FirstBound, typename SecondBound>
238 BindArguments2<Caller> bindArguments(const Caller& caller, FirstBound firstBound, SecondBound secondBound)
239 {
240   return BindArguments2<Caller>(firstBound, secondBound);
241 }
242
243 inline bool Face_testPlane(const Face& face, const Plane3& plane, bool flipped)
244 {
245   return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
246 }
247 typedef Function3<const Face&, const Plane3&, bool, bool, Face_testPlane> FaceTestPlane;
248
249
250
251 /// \brief Returns true if
252 /// \li !flipped && brush is BACK or ON
253 /// \li flipped && brush is FRONT or ON
254 bool Brush_testPlane(const Brush& brush, const Plane3& plane, bool flipped)
255 {
256   brush.evaluateBRep();
257 #if 1
258   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
259   {
260     if(Face_testPlane(*(*i), plane, flipped))
261     {
262       return false;
263     }
264   }
265   return true;
266 #else
267   return Brush_findIf(brush, bindArguments(FaceTestPlane(), makeReference(plane), flipped)) == 0;
268 #endif
269 }
270
271 brushsplit_t Brush_classifyPlane(const Brush& brush, const Plane3& plane)
272 {
273   brush.evaluateBRep();
274   brushsplit_t split;
275   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
276   {
277     if((*i)->contributes())
278     {
279       split += Winding_ClassifyPlane((*i)->getWinding(), plane);
280     }
281   }
282   return split;
283 }
284
285 bool Brush_subtract(const Brush& brush, const Brush& other, brush_vector_t& ret_fragments)
286 {
287   if(aabb_intersects_aabb(brush.localAABB(), other.localAABB()))
288   {
289     brush_vector_t fragments;
290     fragments.reserve(other.size());
291     Brush back(brush);
292
293     for(Brush::const_iterator i(other.begin()); i != other.end(); ++i)
294     {
295       if((*i)->contributes())
296       {
297         brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
298         if(split.counts[ePlaneFront] != 0
299           && split.counts[ePlaneBack] != 0)
300         {
301           fragments.push_back(new Brush(back));
302           Face* newFace = fragments.back()->addFace(*(*i));
303           if(newFace != 0)
304           {
305             newFace->flipWinding();
306           }
307           back.addFace(*(*i));
308         }
309         else if(split.counts[ePlaneBack] == 0)
310         {
311           for(brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i)
312           {
313             delete(*i);
314           }
315           return false;
316         }
317       }
318     }
319     ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
320     return true;
321   }
322   return false;
323 }
324
325 class SubtractBrushesFromUnselected : public scene::Graph::Walker
326 {
327   const brush_vector_t& m_brushlist;
328   std::size_t& m_before;
329   std::size_t& m_after;
330 public:
331   SubtractBrushesFromUnselected(const brush_vector_t& brushlist, std::size_t& before, std::size_t& after)
332     : m_brushlist(brushlist), m_before(before), m_after(after)
333   {
334   }
335   bool pre(const scene::Path& path, scene::Instance& instance) const
336   {
337     return true;
338   }
339   void post(const scene::Path& path, scene::Instance& instance) const
340   {
341     if(path.top().get().visible())
342     {
343       Brush* brush = Node_getBrush(path.top());
344       if(brush != 0
345         && !Instance_getSelectable(instance)->isSelected())
346       {
347         brush_vector_t buffer[2];
348         bool swap = false;
349         Brush* original = new Brush(*brush);
350         buffer[static_cast<std::size_t>(swap)].push_back(original);
351         
352         {
353           for(brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i)
354           {
355             for(brush_vector_t::iterator j(buffer[static_cast<std::size_t>(swap)].begin()); j != buffer[static_cast<std::size_t>(swap)].end(); ++j)
356             {
357               if(Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>(!swap)]))
358               {
359                 delete (*j);
360               }
361               else
362               {
363                 buffer[static_cast<std::size_t>(!swap)].push_back((*j));
364               }
365             }
366             buffer[static_cast<std::size_t>(swap)].clear();
367             swap = !swap;
368           }
369         }
370
371         brush_vector_t& out = buffer[static_cast<std::size_t>(swap)];
372
373         if(out.size() == 1 && out.back() == original)
374         {
375           delete original;
376         }
377         else
378         {
379           ++m_before;
380           for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
381           {
382             ++m_after;
383             NodeSmartReference node((new BrushNode())->node());
384             (*i)->removeEmptyFaces();
385             ASSERT_MESSAGE(!(*i)->empty(), "brush left with no faces after subtract");
386             Node_getBrush(node)->copy(*(*i));
387             delete (*i);
388             Node_getTraversable(path.parent())->insert(node);
389           }
390           Path_deleteTop(path);
391         }
392       }
393     }
394   }
395 };
396
397 void CSG_Subtract()
398 {
399   brush_vector_t selected_brushes;
400   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
401
402   if (selected_brushes.empty())
403   {
404     globalOutputStream() << "CSG Subtract: No brushes selected.\n";
405   }
406   else
407   {
408     globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
409
410     UndoableCommand undo("brushSubtract");
411
412     // subtract selected from unselected
413     std::size_t before = 0;
414     std::size_t after = 0;
415     GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
416     globalOutputStream() << "CSG Subtract: Result: "
417       << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
418       << " from " << Unsigned(before) << " brush" << (before == 1? "" : "es") << ".\n";
419
420     SceneChangeNotify();
421   }
422 }
423
424 class BrushSplitByPlaneSelected : public scene::Graph::Walker
425 {
426   const Vector3& m_p0;
427   const Vector3& m_p1;
428   const Vector3& m_p2;
429   const char* m_shader;
430   const TextureProjection& m_projection;
431   EBrushSplit m_split;
432 public:
433   BrushSplitByPlaneSelected(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split)
434     : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
435   {
436   }
437   bool pre(const scene::Path& path, scene::Instance& instance) const
438   {
439     return true; 
440   }
441   void post(const scene::Path& path, scene::Instance& instance) const
442   {
443     if(path.top().get().visible())
444     {
445       Brush* brush = Node_getBrush(path.top());
446       if(brush != 0
447         && Instance_getSelectable(instance)->isSelected())
448       {
449         Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
450         if(plane3_valid(plane))
451         {
452           brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
453           if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
454           {
455             // the plane intersects this brush
456             if(m_split == eFrontAndBack)
457             {
458               NodeSmartReference node((new BrushNode())->node());
459               Brush* fragment = Node_getBrush(node);
460               fragment->copy(*brush);
461               Face* newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
462               if(newFace != 0 && m_split != eFront)
463               {
464                 newFace->flipWinding();
465               }
466               fragment->removeEmptyFaces();
467               ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
468
469               Node_getTraversable(path.parent())->insert(node);
470               {
471                 scene::Path fragmentPath = path;
472                 fragmentPath.top() = makeReference(node.get());
473                 selectPath(fragmentPath, true);
474               }
475             }
476
477             Face* newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
478             if(newFace != 0 && m_split == eFront)
479             {
480               newFace->flipWinding();
481             }
482             brush->removeEmptyFaces();
483             ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
484           }
485           else
486             // the plane does not intersect this brush
487           if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
488           {
489             // the brush is "behind" the plane
490             Path_deleteTop(path);
491           }
492         }
493       }
494     }
495   }
496 };
497
498 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
499 {
500   TextureProjection projection;
501   TexDef_Construct_Default(projection);
502   graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
503   SceneChangeNotify();
504 }
505
506
507 class BrushInstanceSetClipPlane : public scene::Graph::Walker
508 {
509   Plane3 m_plane;
510 public:
511   BrushInstanceSetClipPlane(const Plane3& plane)
512     : m_plane(plane)
513   {
514   }
515   bool pre(const scene::Path& path, scene::Instance& instance) const
516   {
517     BrushInstance* brush = Instance_getBrush(instance);
518     if(brush != 0
519       && path.top().get().visible()
520       && brush->isSelected())
521     {
522       BrushInstance& brushInstance = *brush;
523       brushInstance.setClipPlane(m_plane);
524     }
525     return true; 
526   }
527 };
528
529 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
530 {
531   graph.traverse(BrushInstanceSetClipPlane(plane));
532 }
533
534 /*
535 =============
536 CSG_Merge
537 =============
538 */
539 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
540 {
541   // gather potential outer faces 
542
543   {
544     typedef std::vector<const Face*> Faces;
545     Faces faces;
546     for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
547     {
548       (*i)->evaluateBRep();
549       for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
550       {
551         if(!(*j)->contributes())
552         {
553           continue;
554         }
555
556         const Face& face1 = *(*j);
557
558         bool skip = false;
559         // test faces of all input brushes
560         //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
561         for(brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k)
562         {
563           if(k != i) // don't test a brush against itself
564           {
565             for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
566             {
567               const Face& face2 = *(*l);
568
569               // face opposes another face
570               if(plane3_opposing(face1.plane3(), face2.plane3()))
571               {
572                 // skip opposing planes
573                 skip  = true;
574                 break;
575               }
576             }
577           }
578         }
579
580         // check faces already stored
581         for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
582         {
583           const Face& face2 = *(*m);
584
585           // face equals another face
586           if (plane3_equal(face1.plane3(), face2.plane3()))
587           {
588             //if the texture/shader references should be the same but are not
589             if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
590             {
591               return false;
592             }
593             // skip duplicate planes
594             skip = true;
595             break;
596           }
597
598           // face1 plane intersects face2 winding or vice versa
599           if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
600           {
601             // result would not be convex
602             return false;
603           }
604         }
605
606         if(!skip)
607         {
608           faces.push_back(&face1);
609         }
610       }
611     }
612     for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
613     {
614       if(!brush.addFace(*(*i)))
615       {
616         // result would have too many sides
617         return false;
618       }
619     }
620   }
621
622   brush.removeEmptyFaces();
623
624   return true;
625 }
626
627 void CSG_Merge(void)
628 {
629   brush_vector_t selected_brushes;
630
631   // remove selected
632   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
633
634   if (selected_brushes.empty())
635   {
636     globalOutputStream() << "CSG Merge: No brushes selected.\n";
637     return;
638   }
639
640   if (selected_brushes.size() < 2)
641   {
642     globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
643     return;
644   }
645
646   globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
647
648   UndoableCommand undo("brushMerge");
649
650   scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
651
652   NodeSmartReference node((new BrushNode())->node());
653   Brush* brush = Node_getBrush(node);
654   // if the new brush would not be convex
655   if(!Brush_merge(*brush, selected_brushes, true))
656   {
657     globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
658   }
659   else
660   {
661     ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
662
663     // free the original brushes
664     GlobalSceneGraph().traverse(BrushDeleteSelected());
665
666     merged_path.pop();
667     Node_getTraversable(merged_path.top())->insert(node);
668     merged_path.push(makeReference(node.get()));
669
670     selectPath(merged_path, true);
671
672     globalOutputStream() << "CSG Merge: Succeeded.\n";
673     SceneChangeNotify();
674   }
675 }