2 Copyright 2012-2022 Ronald Römer
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
8 http://www.apache.org/licenses/LICENSE-2.0
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
17 #ifndef __vtkPolyDataBooleanFilter_h
18 #define __vtkPolyDataBooleanFilter_h
27 #include <vtkPolyDataAlgorithm.h>
28 #include <vtkKdTree.h>
29 #include <vtkModifiedBSPTree.h>
31 #include "Utilities.h"
35 #define OPER_INTERSECTION 2
36 #define OPER_DIFFERENCE 3
37 #define OPER_DIFFERENCE2 4
60 StripPt () : t(0), capt(Capt::NOT), catched(true) {
69 vtkIdType ind, edge[2];
74 friend std::ostream& operator<< (std::ostream &out, const StripPt &s) {
75 out << "ind " << s.ind
76 << ", edge [" << s.edge[0] << ", " << s.edge[1] << "]"
78 << ", capt " << s.capt
79 << ", polyId " << s.polyId;
83 std::vector<Pair> history;
94 StripPtR (vtkIdType ind, std::size_t strip) : ind(ind), strip(strip), ref(NOTSET), side(Side::NONE) {
101 vtkIdType ref, desc[2];
104 friend std::ostream& operator<< (std::ostream &out, const StripPtR &s) {
105 out << "ind " << s.ind
106 << ", desc [" << s.desc[0] << ", " << s.desc[1] << "]"
107 << ", strip " << s.strip
108 << ", side " << s.side
109 << ", ref " << s.ref;
114 typedef std::map<vtkIdType, StripPt> StripPtsType;
115 typedef std::deque<StripPtR> StripType;
116 typedef std::vector<StripType> StripsType;
120 PStrips (vtkPolyData *pd, vtkIdType cellId) {
121 const vtkIdType *cell;
124 pd->GetCellPoints(cellId, numPts, cell);
126 for (vtkIdType i = 0; i < numPts; i++) {
127 poly.push_back(cell[i]);
130 ComputeNormal(pd->GetPoints(), n, numPts, cell);
132 base = Base(pd->GetPoints(), numPts, cell);
143 typedef std::map<vtkIdType, PStrips> PolyStripsType;
145 typedef std::vector<std::reference_wrapper<StripPtR>> RefsType;
149 typedef std::vector<std::size_t> GroupType;
151 typedef std::map<vtkIdType, std::size_t> SourcesType;
156 Conn (double d, vtkIdType i, vtkIdType j) : d(d), i(i), j(j) {}
161 bool operator< (const Conn &other) const {
165 friend std::ostream& operator<< (std::ostream &out, const Conn &c) {
166 out << "Conn(d=" << c.d
176 bool operator() (const Conn &a, const Conn &b) const {
177 return std::tie(a.i, a.j) < std::tie(b.i, b.j);
181 typedef std::vector<Conn> ConnsType;
182 typedef std::map<std::size_t, ConnsType> PolyConnsType;
184 inline std::ostream& operator<< (std::ostream &out, const PolyConnsType& polyConns) {
185 PolyConnsType::const_iterator itr;
187 for (itr = polyConns.begin(); itr != polyConns.end(); ++itr) {
188 out << itr->first << ": [";
189 for (auto &conn : itr->second) {
192 out << "]" << std::endl;
201 Prio (const Conn &conn, const std::set<std::size_t> &solvable, double d) : conn(conn), solvable(solvable), d(d) {}
204 std::set<std::size_t> solvable;
207 friend std::ostream& operator<< (std::ostream &out, const Prio &p) {
208 out << "Prio(conn=" << p.conn
216 bool operator() (const Prio &a, const Prio &b) const {
217 const auto _a = a.solvable.size(),
218 _b = b.solvable.size();
219 return std::tie(_a, a.d) < std::tie(_b, b.d);
223 typedef std::set<Prio, Cmp> PriosType;
225 typedef std::map<std::size_t, Prio> PolyPriosType;
229 const PStrips &pStrips;
234 Merger (vtkPolyData *pd, const PStrips &pStrips, const StripsType &strips, const IdsType &descIds, vtkIdType origId);
238 void MergeGroup (const GroupType &group, PolysType &merged);
239 bool FindConns (vtkPolyData *lines, vtkSmartPointer<vtkKdTree> kdTree, vtkSmartPointer<vtkModifiedBSPTree> bspTree, PolyConnsType &polyConns, const IndexedPolysType &indexedPolys, const SourcesType &sources, int &n);
242 class VTK_EXPORT vtkPolyDataBooleanFilter : public vtkPolyDataAlgorithm {
243 vtkPolyData *resultA, *resultB, *resultC;
245 vtkSmartPointer<vtkPolyData> modPdA, modPdB, contLines;
247 vtkSmartPointer<vtkCellData> cellDataA, cellDataB;
248 vtkSmartPointer<vtkIdTypeArray> cellIdsA, cellIdsB;
250 vtkIdTypeArray *contsA, *contsB;
252 unsigned long timePdA, timePdB;
254 PolyStripsType polyStripsA, polyStripsB;
256 void GetStripPoints (vtkPolyData *pd, vtkIdTypeArray *sources, PStrips &pStrips, IdsType &lines);
257 bool GetPolyStrips (vtkPolyData *pd, vtkIdTypeArray *conts, vtkIdTypeArray *sources, PolyStripsType &polyStrips);
258 void RemoveDuplicates (IdsType &lines);
259 void CompleteStrips (PStrips &pStrips);
260 bool HasArea (const StripType &strip) const;
261 bool CutCells (vtkPolyData *pd, PolyStripsType &polyStrips);
262 void RestoreOrigPoints (vtkPolyData *pd, PolyStripsType &polyStrips);
263 void DisjoinPolys (vtkPolyData *pd, PolyStripsType &polyStrips);
264 void ResolveOverlaps (vtkPolyData *pd, vtkIdTypeArray *conts, PolyStripsType &polyStrips);
265 void AddAdjacentPoints (vtkPolyData *pd, vtkIdTypeArray *conts, PolyStripsType &polyStrips);
266 void MergePoints (vtkPolyData *pd, PolyStripsType &polyStrips);
267 bool CombineRegions ();
272 vtkTypeMacro(vtkPolyDataBooleanFilter, vtkPolyDataAlgorithm);
273 static vtkPolyDataBooleanFilter* New ();
275 vtkSetClampMacro(OperMode, int, OPER_NONE, OPER_DIFFERENCE2);
276 vtkGetMacro(OperMode, int);
278 void SetOperModeToNone () { OperMode = OPER_NONE; Modified(); }
279 void SetOperModeToUnion () { OperMode = OPER_UNION; Modified(); }
280 void SetOperModeToIntersection () { OperMode = OPER_INTERSECTION; Modified(); }
281 void SetOperModeToDifference () { OperMode = OPER_DIFFERENCE; Modified(); }
282 void SetOperModeToDifference2 () { OperMode = OPER_DIFFERENCE2; Modified(); }
285 vtkPolyDataBooleanFilter ();
286 ~vtkPolyDataBooleanFilter ();
288 int ProcessRequest (vtkInformation *request, vtkInformationVector **inputVector, vtkInformationVector *outputVector) override;
290 void PrintSelf (ostream&, vtkIndent) override {};
293 vtkPolyDataBooleanFilter (const vtkPolyDataBooleanFilter&) = delete;
294 void operator= (const vtkPolyDataBooleanFilter&) = delete;