]> git.xonotic.org Git - xonotic/netradiant.git/blob - radiant/csg.cpp
if a font was not found, fall back to fixed or courier new - should fix "missing...
[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 Type>
171 class RemoveReference
172 {
173 public:
174   typedef Type type;
175 };
176
177 template<typename Type>
178 class RemoveReference<Type&>
179 {
180 public:
181   typedef Type type;
182 };
183
184 template<typename Functor>
185 class Dereference
186 {
187   const Functor& functor;
188 public:
189   typedef typename RemoveReference<typename Functor::first_argument_type>::type* first_argument_type;
190   typedef typename Functor::result_type result_type;
191   Dereference(const Functor& functor) : functor(functor)
192   {
193   }
194   result_type operator()(first_argument_type firstArgument) const
195   {
196     return functor(*firstArgument);
197   }
198 };
199
200 template<typename Functor>
201 inline Dereference<Functor> makeDereference(const Functor& functor)
202 {
203   return Dereference<Functor>(functor);
204 }
205
206 typedef Face* FacePointer;
207 const FacePointer c_nullFacePointer = 0;
208
209 template<typename Predicate>
210 Face* Brush_findIf(const Brush& brush, const Predicate& predicate)
211 {
212   Brush::const_iterator i = std::find_if(brush.begin(), brush.end(), makeDereference(predicate));
213   return i == brush.end() ? c_nullFacePointer : *i; // uses c_nullFacePointer instead of 0 because otherwise gcc 4.1 attempts conversion to int
214 }
215
216 template<typename Caller>
217 class BindArguments1
218 {
219   typedef typename Caller::second_argument_type FirstBound;
220   FirstBound firstBound;
221 public:
222   typedef typename Caller::result_type result_type;
223   typedef typename Caller::first_argument_type first_argument_type;
224   BindArguments1(FirstBound firstBound)
225     : firstBound(firstBound)
226   {
227   }
228   result_type operator()(first_argument_type firstArgument) const
229   {
230     return Caller::call(firstArgument, firstBound);
231   }
232 };
233
234 template<typename Caller>
235 class BindArguments2
236 {
237   typedef typename Caller::second_argument_type FirstBound;
238   typedef typename Caller::third_argument_type SecondBound;
239   FirstBound firstBound;
240   SecondBound secondBound;
241 public:
242   typedef typename Caller::result_type result_type;
243   typedef typename Caller::first_argument_type first_argument_type;
244   BindArguments2(FirstBound firstBound, SecondBound secondBound)
245     : firstBound(firstBound), secondBound(secondBound)
246   {
247   }
248   result_type operator()(first_argument_type firstArgument) const
249   {
250     return Caller::call(firstArgument, firstBound, secondBound);
251   }
252 };
253
254 template<typename Caller, typename FirstBound, typename SecondBound>
255 BindArguments2<Caller> bindArguments(const Caller& caller, FirstBound firstBound, SecondBound secondBound)
256 {
257   return BindArguments2<Caller>(firstBound, secondBound);
258 }
259
260 inline bool Face_testPlane(const Face& face, const Plane3& plane, bool flipped)
261 {
262   return face.contributes() && !Winding_TestPlane(face.getWinding(), plane, flipped);
263 }
264 typedef Function3<const Face&, const Plane3&, bool, bool, Face_testPlane> FaceTestPlane;
265
266
267
268 /// \brief Returns true if
269 /// \li !flipped && brush is BACK or ON
270 /// \li flipped && brush is FRONT or ON
271 bool Brush_testPlane(const Brush& brush, const Plane3& plane, bool flipped)
272 {
273   brush.evaluateBRep();
274 #if 1
275   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
276   {
277     if(Face_testPlane(*(*i), plane, flipped))
278     {
279       return false;
280     }
281   }
282   return true;
283 #else
284   return Brush_findIf(brush, bindArguments(FaceTestPlane(), makeReference(plane), flipped)) == 0;
285 #endif
286 }
287
288 brushsplit_t Brush_classifyPlane(const Brush& brush, const Plane3& plane)
289 {
290   brush.evaluateBRep();
291   brushsplit_t split;
292   for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
293   {
294     if((*i)->contributes())
295     {
296       split += Winding_ClassifyPlane((*i)->getWinding(), plane);
297     }
298   }
299   return split;
300 }
301
302 bool Brush_subtract(const Brush& brush, const Brush& other, brush_vector_t& ret_fragments)
303 {
304   if(aabb_intersects_aabb(brush.localAABB(), other.localAABB()))
305   {
306     brush_vector_t fragments;
307     fragments.reserve(other.size());
308     Brush back(brush);
309
310     for(Brush::const_iterator i(other.begin()); i != other.end(); ++i)
311     {
312       if((*i)->contributes())
313       {
314         brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
315         if(split.counts[ePlaneFront] != 0
316           && split.counts[ePlaneBack] != 0)
317         {
318           fragments.push_back(new Brush(back));
319           Face* newFace = fragments.back()->addFace(*(*i));
320           if(newFace != 0)
321           {
322             newFace->flipWinding();
323           }
324           back.addFace(*(*i));
325         }
326         else if(split.counts[ePlaneBack] == 0)
327         {
328           for(brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i)
329           {
330             delete(*i);
331           }
332           return false;
333         }
334       }
335     }
336     ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
337     return true;
338   }
339   return false;
340 }
341
342 class SubtractBrushesFromUnselected : public scene::Graph::Walker
343 {
344   const brush_vector_t& m_brushlist;
345   std::size_t& m_before;
346   std::size_t& m_after;
347 public:
348   SubtractBrushesFromUnselected(const brush_vector_t& brushlist, std::size_t& before, std::size_t& after)
349     : m_brushlist(brushlist), m_before(before), m_after(after)
350   {
351   }
352   bool pre(const scene::Path& path, scene::Instance& instance) const
353   {
354     return true;
355   }
356   void post(const scene::Path& path, scene::Instance& instance) const
357   {
358     if(path.top().get().visible())
359     {
360       Brush* brush = Node_getBrush(path.top());
361       if(brush != 0
362         && !Instance_getSelectable(instance)->isSelected())
363       {
364         brush_vector_t buffer[2];
365         bool swap = false;
366         Brush* original = new Brush(*brush);
367         buffer[static_cast<std::size_t>(swap)].push_back(original);
368         
369         {
370           for(brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i)
371           {
372             for(brush_vector_t::iterator j(buffer[static_cast<std::size_t>(swap)].begin()); j != buffer[static_cast<std::size_t>(swap)].end(); ++j)
373             {
374               if(Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>(!swap)]))
375               {
376                 delete (*j);
377               }
378               else
379               {
380                 buffer[static_cast<std::size_t>(!swap)].push_back((*j));
381               }
382             }
383             buffer[static_cast<std::size_t>(swap)].clear();
384             swap = !swap;
385           }
386         }
387
388         brush_vector_t& out = buffer[static_cast<std::size_t>(swap)];
389
390         if(out.size() == 1 && out.back() == original)
391         {
392           delete original;
393         }
394         else
395         {
396           ++m_before;
397           for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
398           {
399             ++m_after;
400             NodeSmartReference node((new BrushNode())->node());
401             (*i)->removeEmptyFaces();
402             ASSERT_MESSAGE(!(*i)->empty(), "brush left with no faces after subtract");
403             Node_getBrush(node)->copy(*(*i));
404             delete (*i);
405             Node_getTraversable(path.parent())->insert(node);
406           }
407           Path_deleteTop(path);
408         }
409       }
410     }
411   }
412 };
413
414 void CSG_Subtract()
415 {
416   brush_vector_t selected_brushes;
417   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
418
419   if (selected_brushes.empty())
420   {
421     globalOutputStream() << "CSG Subtract: No brushes selected.\n";
422   }
423   else
424   {
425     globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
426
427     UndoableCommand undo("brushSubtract");
428
429     // subtract selected from unselected
430     std::size_t before = 0;
431     std::size_t after = 0;
432     GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
433     globalOutputStream() << "CSG Subtract: Result: "
434       << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
435       << " from " << Unsigned(before) << " brush" << (before == 1? "" : "es") << ".\n";
436
437     SceneChangeNotify();
438   }
439 }
440
441 class BrushSplitByPlaneSelected : public scene::Graph::Walker
442 {
443   const Vector3& m_p0;
444   const Vector3& m_p1;
445   const Vector3& m_p2;
446   const char* m_shader;
447   const TextureProjection& m_projection;
448   EBrushSplit m_split;
449 public:
450   BrushSplitByPlaneSelected(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split)
451     : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
452   {
453   }
454   bool pre(const scene::Path& path, scene::Instance& instance) const
455   {
456     return true; 
457   }
458   void post(const scene::Path& path, scene::Instance& instance) const
459   {
460     if(path.top().get().visible())
461     {
462       Brush* brush = Node_getBrush(path.top());
463       if(brush != 0
464         && Instance_getSelectable(instance)->isSelected())
465       {
466         Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
467         if(plane3_valid(plane))
468         {
469           brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
470           if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
471           {
472             // the plane intersects this brush
473             if(m_split == eFrontAndBack)
474             {
475               NodeSmartReference node((new BrushNode())->node());
476               Brush* fragment = Node_getBrush(node);
477               fragment->copy(*brush);
478               Face* newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
479               if(newFace != 0 && m_split != eFront)
480               {
481                 newFace->flipWinding();
482               }
483               fragment->removeEmptyFaces();
484               ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
485
486               Node_getTraversable(path.parent())->insert(node);
487               {
488                 scene::Path fragmentPath = path;
489                 fragmentPath.top() = makeReference(node.get());
490                 selectPath(fragmentPath, true);
491               }
492             }
493
494             Face* newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
495             if(newFace != 0 && m_split == eFront)
496             {
497               newFace->flipWinding();
498             }
499             brush->removeEmptyFaces();
500             ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
501           }
502           else
503             // the plane does not intersect this brush
504           if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
505           {
506             // the brush is "behind" the plane
507             Path_deleteTop(path);
508           }
509         }
510       }
511     }
512   }
513 };
514
515 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
516 {
517   TextureProjection projection;
518   TexDef_Construct_Default(projection);
519   graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
520   SceneChangeNotify();
521 }
522
523
524 class BrushInstanceSetClipPlane : public scene::Graph::Walker
525 {
526   Plane3 m_plane;
527 public:
528   BrushInstanceSetClipPlane(const Plane3& plane)
529     : m_plane(plane)
530   {
531   }
532   bool pre(const scene::Path& path, scene::Instance& instance) const
533   {
534     BrushInstance* brush = Instance_getBrush(instance);
535     if(brush != 0
536       && path.top().get().visible()
537       && brush->isSelected())
538     {
539       BrushInstance& brushInstance = *brush;
540       brushInstance.setClipPlane(m_plane);
541     }
542     return true; 
543   }
544 };
545
546 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
547 {
548   graph.traverse(BrushInstanceSetClipPlane(plane));
549 }
550
551 /*
552 =============
553 CSG_Merge
554 =============
555 */
556 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
557 {
558   // gather potential outer faces 
559
560   {
561     typedef std::vector<const Face*> Faces;
562     Faces faces;
563     for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
564     {
565       (*i)->evaluateBRep();
566       for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
567       {
568         if(!(*j)->contributes())
569         {
570           continue;
571         }
572
573         const Face& face1 = *(*j);
574
575         bool skip = false;
576         // test faces of all input brushes
577         //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
578         for(brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k)
579         {
580           if(k != i) // don't test a brush against itself
581           {
582             for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
583             {
584               const Face& face2 = *(*l);
585
586               // face opposes another face
587               if(plane3_opposing(face1.plane3(), face2.plane3()))
588               {
589                 // skip opposing planes
590                 skip  = true;
591                 break;
592               }
593             }
594           }
595         }
596
597         // check faces already stored
598         for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
599         {
600           const Face& face2 = *(*m);
601
602           // face equals another face
603           if (plane3_equal(face1.plane3(), face2.plane3()))
604           {
605             //if the texture/shader references should be the same but are not
606             if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
607             {
608               return false;
609             }
610             // skip duplicate planes
611             skip = true;
612             break;
613           }
614
615           // face1 plane intersects face2 winding or vice versa
616           if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
617           {
618             // result would not be convex
619             return false;
620           }
621         }
622
623         if(!skip)
624         {
625           faces.push_back(&face1);
626         }
627       }
628     }
629     for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
630     {
631       if(!brush.addFace(*(*i)))
632       {
633         // result would have too many sides
634         return false;
635       }
636     }
637   }
638
639   brush.removeEmptyFaces();
640
641   return true;
642 }
643
644 void CSG_Merge(void)
645 {
646   brush_vector_t selected_brushes;
647
648   // remove selected
649   GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
650
651   if (selected_brushes.empty())
652   {
653     globalOutputStream() << "CSG Merge: No brushes selected.\n";
654     return;
655   }
656
657   if (selected_brushes.size() < 2)
658   {
659     globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
660     return;
661   }
662
663   globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
664
665   UndoableCommand undo("brushMerge");
666
667   scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
668
669   NodeSmartReference node((new BrushNode())->node());
670   Brush* brush = Node_getBrush(node);
671   // if the new brush would not be convex
672   if(!Brush_merge(*brush, selected_brushes, true))
673   {
674     globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
675   }
676   else
677   {
678     ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
679
680     // free the original brushes
681     GlobalSceneGraph().traverse(BrushDeleteSelected());
682
683     merged_path.pop();
684     Node_getTraversable(merged_path.top())->insert(node);
685     merged_path.push(makeReference(node.get()));
686
687     selectPath(merged_path, true);
688
689     globalOutputStream() << "CSG Merge: Succeeded.\n";
690     SceneChangeNotify();
691   }
692 }