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
34
Brush_makeHollow(const Brush & brush,brush_vector_t & out,float offset)35 void Brush_makeHollow(const Brush& brush, brush_vector_t& out, float offset)
36 {
37 for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
38 {
39 if((*i)->contributes())
40 {
41 out.push_back(new Brush(brush));
42 Face* newFace = out.back()->addFace(*(*i));
43 if(newFace != 0)
44 {
45 newFace->flipWinding();
46 newFace->getPlane().offset(offset);
47 newFace->planeChanged();
48 }
49 }
50 }
51 }
52
53 class BrushHollowSelectedWalker : public scene::Graph::Walker
54 {
55 float m_offset;
56 public:
BrushHollowSelectedWalker(float offset)57 BrushHollowSelectedWalker(float offset)
58 : m_offset(offset)
59 {
60 }
pre(const scene::Path & path,scene::Instance & instance) const61 bool pre(const scene::Path& path, scene::Instance& instance) const
62 {
63 if(path.top().get().visible())
64 {
65 Brush* brush = Node_getBrush(path.top());
66 if(brush != 0
67 && Instance_getSelectable(instance)->isSelected()
68 && path.size() > 1)
69 {
70 brush_vector_t out;
71 Brush_makeHollow(*brush, out, m_offset);
72 for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
73 {
74 NodeSmartReference node((new BrushNode())->node());
75 (*i)->removeEmptyFaces();
76 Node_getBrush(node)->copy(*(*i));
77 delete (*i);
78 Node_getTraversable(path.parent())->insert(node);
79 }
80 }
81 }
82 return true;
83 }
84 };
85
86 typedef std::list<Brush*> brushlist_t;
87
88 class BrushGatherSelected : public scene::Graph::Walker
89 {
90 brush_vector_t& m_brushlist;
91 public:
BrushGatherSelected(brush_vector_t & brushlist)92 BrushGatherSelected(brush_vector_t& brushlist)
93 : m_brushlist(brushlist)
94 {
95 }
pre(const scene::Path & path,scene::Instance & instance) const96 bool pre(const scene::Path& path, scene::Instance& instance) const
97 {
98 if(path.top().get().visible())
99 {
100 Brush* brush = Node_getBrush(path.top());
101 if(brush != 0
102 && Instance_getSelectable(instance)->isSelected())
103 {
104 m_brushlist.push_back(brush);
105 }
106 }
107 return true;
108 }
109 };
110
111 class BrushDeleteSelected : public scene::Graph::Walker
112 {
113 public:
pre(const scene::Path & path,scene::Instance & instance) const114 bool pre(const scene::Path& path, scene::Instance& instance) const
115 {
116 return true;
117 }
post(const scene::Path & path,scene::Instance & instance) const118 void post(const scene::Path& path, scene::Instance& instance) const
119 {
120 if(path.top().get().visible())
121 {
122 Brush* brush = Node_getBrush(path.top());
123 if(brush != 0
124 && Instance_getSelectable(instance)->isSelected()
125 && path.size() > 1)
126 {
127 Path_deleteTop(path);
128 }
129 }
130 }
131 };
132
Scene_BrushMakeHollow_Selected(scene::Graph & graph)133 void Scene_BrushMakeHollow_Selected(scene::Graph& graph)
134 {
135 GlobalSceneGraph().traverse(BrushHollowSelectedWalker(GetGridSize()));
136 GlobalSceneGraph().traverse(BrushDeleteSelected());
137 }
138
139 /*
140 =============
141 CSG_MakeHollow
142 =============
143 */
144
CSG_MakeHollow(void)145 void CSG_MakeHollow (void)
146 {
147 UndoableCommand undo("brushHollow");
148
149 Scene_BrushMakeHollow_Selected(GlobalSceneGraph());
150
151 SceneChangeNotify();
152 }
153
154
155 /// \brief Returns true if
156 /// \li !flipped && brush is BACK or ON
157 /// \li flipped && brush is FRONT or ON
Brush_testPlane(const Brush & brush,const Plane3 & plane,bool flipped)158 bool Brush_testPlane(const Brush& brush, const Plane3& plane, bool flipped)
159 {
160 brush.evaluateBRep();
161 for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
162 {
163 if((*i)->contributes() && !Winding_TestPlane((*i)->getWinding(), plane, flipped))
164 {
165 return false;
166 }
167 }
168 return true;
169 }
170
Brush_classifyPlane(const Brush & brush,const Plane3 & plane)171 brushsplit_t Brush_classifyPlane(const Brush& brush, const Plane3& plane)
172 {
173 brush.evaluateBRep();
174 brushsplit_t split;
175 for(Brush::const_iterator i(brush.begin()); i != brush.end(); ++i)
176 {
177 if((*i)->contributes())
178 {
179 split += Winding_ClassifyPlane((*i)->getWinding(), plane);
180 }
181 }
182 return split;
183 }
184
Brush_subtract(const Brush & brush,const Brush & other,brush_vector_t & ret_fragments)185 bool Brush_subtract(const Brush& brush, const Brush& other, brush_vector_t& ret_fragments)
186 {
187 if(aabb_intersects_aabb(brush.localAABB(), other.localAABB()))
188 {
189 brush_vector_t fragments;
190 fragments.reserve(other.size());
191 Brush back(brush);
192
193 for(Brush::const_iterator i(other.begin()); i != other.end(); ++i)
194 {
195 if((*i)->contributes())
196 {
197 brushsplit_t split = Brush_classifyPlane(back, (*i)->plane3());
198 if(split.counts[ePlaneFront] != 0
199 && split.counts[ePlaneBack] != 0)
200 {
201 fragments.push_back(new Brush(back));
202 Face* newFace = fragments.back()->addFace(*(*i));
203 if(newFace != 0)
204 {
205 newFace->flipWinding();
206 }
207 back.addFace(*(*i));
208 }
209 else if(split.counts[ePlaneBack] == 0)
210 {
211 for(brush_vector_t::iterator i = fragments.begin(); i != fragments.end(); ++i)
212 {
213 delete(*i);
214 }
215 return false;
216 }
217 }
218 }
219 ret_fragments.insert(ret_fragments.end(), fragments.begin(), fragments.end());
220 return true;
221 }
222 return false;
223 }
224
225 class SubtractBrushesFromUnselected : public scene::Graph::Walker
226 {
227 const brush_vector_t& m_brushlist;
228 std::size_t& m_before;
229 std::size_t& m_after;
230 public:
SubtractBrushesFromUnselected(const brush_vector_t & brushlist,std::size_t & before,std::size_t & after)231 SubtractBrushesFromUnselected(const brush_vector_t& brushlist, std::size_t& before, std::size_t& after)
232 : m_brushlist(brushlist), m_before(before), m_after(after)
233 {
234 }
pre(const scene::Path & path,scene::Instance & instance) const235 bool pre(const scene::Path& path, scene::Instance& instance) const
236 {
237 return true;
238 }
post(const scene::Path & path,scene::Instance & instance) const239 void post(const scene::Path& path, scene::Instance& instance) const
240 {
241 if(path.top().get().visible())
242 {
243 Brush* brush = Node_getBrush(path.top());
244 if(brush != 0
245 && !Instance_getSelectable(instance)->isSelected())
246 {
247 brush_vector_t buffer[2];
248 bool swap = false;
249 Brush* original = new Brush(*brush);
250 buffer[static_cast<std::size_t>(swap)].push_back(original);
251
252 {
253 for(brush_vector_t::const_iterator i(m_brushlist.begin()); i != m_brushlist.end(); ++i)
254 {
255 for(brush_vector_t::iterator j(buffer[static_cast<std::size_t>(swap)].begin()); j != buffer[static_cast<std::size_t>(swap)].end(); ++j)
256 {
257 if(Brush_subtract(*(*j), *(*i), buffer[static_cast<std::size_t>(!swap)]))
258 {
259 delete (*j);
260 }
261 else
262 {
263 buffer[static_cast<std::size_t>(!swap)].push_back((*j));
264 }
265 }
266 buffer[static_cast<std::size_t>(swap)].clear();
267 swap = !swap;
268 }
269 }
270
271 brush_vector_t& out = buffer[static_cast<std::size_t>(swap)];
272
273 if(out.size() == 1 && out.back() == original)
274 {
275 delete original;
276 }
277 else
278 {
279 ++m_before;
280 for(brush_vector_t::const_iterator i = out.begin(); i != out.end(); ++i)
281 {
282 ++m_after;
283 NodeSmartReference node((new BrushNode())->node());
284 (*i)->removeEmptyFaces();
285 ASSERT_MESSAGE(!(*i)->empty(), "brush left with no faces after subtract");
286 Node_getBrush(node)->copy(*(*i));
287 delete (*i);
288 Node_getTraversable(path.parent())->insert(node);
289 }
290 Path_deleteTop(path);
291 }
292 }
293 }
294 }
295 };
296
CSG_Subtract()297 void CSG_Subtract()
298 {
299 brush_vector_t selected_brushes;
300 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
301
302 if (selected_brushes.empty())
303 {
304 globalOutputStream() << "CSG Subtract: No brushes selected.\n";
305 }
306 else
307 {
308 globalOutputStream() << "CSG Subtract: Subtracting " << Unsigned(selected_brushes.size()) << " brushes.\n";
309
310 UndoableCommand undo("brushSubtract");
311
312 // subtract selected from unselected
313 std::size_t before = 0;
314 std::size_t after = 0;
315 GlobalSceneGraph().traverse(SubtractBrushesFromUnselected(selected_brushes, before, after));
316 globalOutputStream() << "CSG Subtract: Result: "
317 << Unsigned(after) << " fragment" << (after == 1 ? "" : "s")
318 << " from " << Unsigned(before) << " brush" << (before == 1? "" : "es") << ".\n";
319
320 SceneChangeNotify();
321 }
322 }
323
324 class BrushSplitByPlaneSelected : public scene::Graph::Walker
325 {
326 const Vector3& m_p0;
327 const Vector3& m_p1;
328 const Vector3& m_p2;
329 const char* m_shader;
330 const TextureProjection& m_projection;
331 EBrushSplit m_split;
332 public:
BrushSplitByPlaneSelected(const Vector3 & p0,const Vector3 & p1,const Vector3 & p2,const char * shader,const TextureProjection & projection,EBrushSplit split)333 BrushSplitByPlaneSelected(const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, const TextureProjection& projection, EBrushSplit split)
334 : m_p0(p0), m_p1(p1), m_p2(p2), m_shader(shader), m_projection(projection), m_split(split)
335 {
336 }
pre(const scene::Path & path,scene::Instance & instance) const337 bool pre(const scene::Path& path, scene::Instance& instance) const
338 {
339 return true;
340 }
post(const scene::Path & path,scene::Instance & instance) const341 void post(const scene::Path& path, scene::Instance& instance) const
342 {
343 if(path.top().get().visible())
344 {
345 Brush* brush = Node_getBrush(path.top());
346 if(brush != 0
347 && Instance_getSelectable(instance)->isSelected())
348 {
349 Plane3 plane(plane3_for_points(m_p0, m_p1, m_p2));
350 if(plane3_valid(plane))
351 {
352 brushsplit_t split = Brush_classifyPlane(*brush, m_split == eFront ? plane3_flipped(plane) : plane);
353 if(split.counts[ePlaneBack] && split.counts[ePlaneFront])
354 {
355 // the plane intersects this brush
356 if(m_split == eFrontAndBack)
357 {
358 NodeSmartReference node((new BrushNode())->node());
359 Brush* fragment = Node_getBrush(node);
360 fragment->copy(*brush);
361 Face* newFace = fragment->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
362 if(newFace != 0 && m_split != eFront)
363 {
364 newFace->flipWinding();
365 }
366 fragment->removeEmptyFaces();
367 ASSERT_MESSAGE(!fragment->empty(), "brush left with no faces after split");
368
369 Node_getTraversable(path.parent())->insert(node);
370 {
371 scene::Path fragmentPath = path;
372 fragmentPath.top() = makeReference(node.get());
373 selectPath(fragmentPath, true);
374 }
375 }
376
377 Face* newFace = brush->addPlane(m_p0, m_p1, m_p2, m_shader, m_projection);
378 if(newFace != 0 && m_split == eFront)
379 {
380 newFace->flipWinding();
381 }
382 brush->removeEmptyFaces();
383 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after split");
384 }
385 else
386 // the plane does not intersect this brush
387 if(m_split != eFrontAndBack && split.counts[ePlaneBack] != 0)
388 {
389 // the brush is "behind" the plane
390 Path_deleteTop(path);
391 }
392 }
393 }
394 }
395 }
396 };
397
Scene_BrushSplitByPlane(scene::Graph & graph,const Vector3 & p0,const Vector3 & p1,const Vector3 & p2,const char * shader,EBrushSplit split)398 void Scene_BrushSplitByPlane(scene::Graph& graph, const Vector3& p0, const Vector3& p1, const Vector3& p2, const char* shader, EBrushSplit split)
399 {
400 TextureProjection projection;
401 TexDef_Construct_Default(projection);
402 graph.traverse(BrushSplitByPlaneSelected(p0, p1, p2, shader, projection, split));
403 SceneChangeNotify();
404 }
405
406
407 class BrushInstanceSetClipPlane : public scene::Graph::Walker
408 {
409 Plane3 m_plane;
410 public:
BrushInstanceSetClipPlane(const Plane3 & plane)411 BrushInstanceSetClipPlane(const Plane3& plane)
412 : m_plane(plane)
413 {
414 }
pre(const scene::Path & path,scene::Instance & instance) const415 bool pre(const scene::Path& path, scene::Instance& instance) const
416 {
417 BrushInstance* brush = Instance_getBrush(instance);
418 if(brush != 0
419 && path.top().get().visible()
420 && brush->isSelected())
421 {
422 BrushInstance& brushInstance = *brush;
423 brushInstance.setClipPlane(m_plane);
424 }
425 return true;
426 }
427 };
428
Scene_BrushSetClipPlane(scene::Graph & graph,const Plane3 & plane)429 void Scene_BrushSetClipPlane(scene::Graph& graph, const Plane3& plane)
430 {
431 graph.traverse(BrushInstanceSetClipPlane(plane));
432 }
433
434 /*
435 =============
436 CSG_Merge
437 =============
438 */
Brush_merge(Brush & brush,const brush_vector_t & in,bool onlyshape)439 bool Brush_merge(Brush& brush, const brush_vector_t& in, bool onlyshape)
440 {
441 // gather potential outer faces
442
443 {
444 typedef std::vector<const Face*> Faces;
445 Faces faces;
446 for(brush_vector_t::const_iterator i(in.begin()); i != in.end(); ++i)
447 {
448 (*i)->evaluateBRep();
449 for(Brush::const_iterator j((*i)->begin()); j != (*i)->end(); ++j)
450 {
451 if(!(*j)->contributes())
452 {
453 continue;
454 }
455
456 const Face& face1 = *(*j);
457
458 bool skip = false;
459 // test faces of all input brushes
460 //!\todo SPEEDUP: Flag already-skip faces and only test brushes from i+1 upwards.
461 for(brush_vector_t::const_iterator k(in.begin()); !skip && k != in.end(); ++k)
462 {
463 if(k != i) // don't test a brush against itself
464 {
465 for(Brush::const_iterator l((*k)->begin()); !skip && l != (*k)->end(); ++l)
466 {
467 const Face& face2 = *(*l);
468
469 // face opposes another face
470 if(plane3_opposing(face1.plane3(), face2.plane3()))
471 {
472 // skip opposing planes
473 skip = true;
474 break;
475 }
476 }
477 }
478 }
479
480 // check faces already stored
481 for(Faces::const_iterator m = faces.begin(); !skip && m != faces.end(); ++m)
482 {
483 const Face& face2 = *(*m);
484
485 // face equals another face
486 if (plane3_equal(face1.plane3(), face2.plane3()))
487 {
488 //if the texture/shader references should be the same but are not
489 if (!onlyshape && !shader_equal(face1.getShader().getShader(), face2.getShader().getShader()))
490 {
491 return false;
492 }
493 // skip duplicate planes
494 skip = true;
495 break;
496 }
497
498 // face1 plane intersects face2 winding or vice versa
499 if (Winding_PlanesConcave(face1.getWinding(), face2.getWinding(), face1.plane3(), face2.plane3()))
500 {
501 // result would not be convex
502 return false;
503 }
504 }
505
506 if(!skip)
507 {
508 faces.push_back(&face1);
509 }
510 }
511 }
512 for(Faces::const_iterator i = faces.begin(); i != faces.end(); ++i)
513 {
514 if(!brush.addFace(*(*i)))
515 {
516 // result would have too many sides
517 return false;
518 }
519 }
520 }
521
522 brush.removeEmptyFaces();
523
524 return true;
525 }
526
CSG_Merge(void)527 void CSG_Merge(void)
528 {
529 brush_vector_t selected_brushes;
530
531 // remove selected
532 GlobalSceneGraph().traverse(BrushGatherSelected(selected_brushes));
533
534 if (selected_brushes.empty())
535 {
536 globalOutputStream() << "CSG Merge: No brushes selected.\n";
537 return;
538 }
539
540 if (selected_brushes.size() < 2)
541 {
542 globalOutputStream() << "CSG Merge: At least two brushes have to be selected.\n";
543 return;
544 }
545
546 globalOutputStream() << "CSG Merge: Merging " << Unsigned(selected_brushes.size()) << " brushes.\n";
547
548 UndoableCommand undo("brushMerge");
549
550 scene::Path merged_path = GlobalSelectionSystem().ultimateSelected().path();
551
552 NodeSmartReference node((new BrushNode())->node());
553 Brush* brush = Node_getBrush(node);
554 // if the new brush would not be convex
555 if(!Brush_merge(*brush, selected_brushes, true))
556 {
557 globalOutputStream() << "CSG Merge: Failed - result would not be convex.\n";
558 }
559 else
560 {
561 ASSERT_MESSAGE(!brush->empty(), "brush left with no faces after merge");
562
563 // free the original brushes
564 GlobalSceneGraph().traverse(BrushDeleteSelected());
565
566 merged_path.pop();
567 Node_getTraversable(merged_path.top())->insert(node);
568 merged_path.push(makeReference(node.get()));
569
570 selectPath(merged_path, true);
571
572 globalOutputStream() << "CSG Merge: Succeeded.\n";
573 SceneChangeNotify();
574 }
575 }
576