lib/creaVtk/vtkPolyDataBooleanFilter.h

   1 /*
   2 Copyright 2012-2022 Ronald Römer
   3
   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
   7
   8     http://www.apache.org/licenses/LICENSE-2.0
   9
  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.
  15 */
  16
  17 #ifndef __vtkPolyDataBooleanFilter_h
  18 #define __vtkPolyDataBooleanFilter_h
  19
  20 #include <vector>
  21 #include <deque>
  22 #include <map>
  23 #include <set>
  24 #include <utility>
  25 #include <iostream>
  26
  27 #include <vtkPolyDataAlgorithm.h>
  28 #include <vtkKdTree.h>
  29 #include <vtkModifiedBSPTree.h>
  30
  31 #include "Utilities.h"
  32
  33 #define OPER_NONE 0
  34 #define OPER_UNION 1
  35 #define OPER_INTERSECTION 2
  36 #define OPER_DIFFERENCE 3
  37 #define OPER_DIFFERENCE2 4
  38
  39 enum class Capt {
  40     NOT,
  41     EDGE,
  42     A,
  43     B
  44 };
  45
  46 enum class Side {
  47     NONE,
  48     START,
  49     END
  50 };
  51
  52 enum class Loc {
  53     NONE,
  54     INSIDE,
  55     OUTSIDE
  56 };
  57
  58 class StripPt {
  59 public:
  60     StripPt () : t(0), capt(Capt::NOT), catched(true) {
  61         edge[0] = NOTSET;
  62         edge[1] = NOTSET;
  63     }
  64
  65     double t;
  66     Capt capt;
  67     double captPt[3];
  68
  69     vtkIdType ind, edge[2];
  70
  71     double pt[3];
  72     double cutPt[3];
  73
  74     friend std::ostream& operator<< (std::ostream &out, const StripPt &s) {
  75         out << "ind " << s.ind
  76             << ", edge [" << s.edge[0] << ", " << s.edge[1] << "]"
  77             << ", t " << s.t
  78             << ", capt " << s.capt
  79             << ", polyId " << s.polyId;
  80         return out;
  81     }
  82
  83     std::vector<Pair> history;
  84
  85     vtkIdType polyId;
  86
  87     bool catched;
  88 };
  89
  90 class StripPtR {
  91 public:
  92     StripPtR () = delete;
  93
  94     StripPtR (vtkIdType ind, std::size_t strip) : ind(ind), strip(strip), ref(NOTSET), side(Side::NONE) {
  95         desc[0] = NOTSET;
  96         desc[1] = NOTSET;
  97     }
  98
  99     vtkIdType ind;
 100     std::size_t strip;
 101     vtkIdType ref, desc[2];
 102     Side side;
 103
 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;
 110         return out;
 111     }
 112 };
 113
 114 typedef std::map<vtkIdType, StripPt> StripPtsType;
 115 typedef std::deque<StripPtR> StripType;
 116 typedef std::vector<StripType> StripsType;
 117
 118 class PStrips {
 119 public:
 120     PStrips (vtkPolyData *pd, vtkIdType cellId) {
 121         const vtkIdType *cell;
 122         vtkIdType numPts;
 123
 124         pd->GetCellPoints(cellId, numPts, cell);
 125
 126         for (vtkIdType i = 0; i < numPts; i++) {
 127             poly.push_back(cell[i]);
 128         }
 129
 130         ComputeNormal(pd->GetPoints(), n, numPts, cell);
 131
 132         base = Base(pd->GetPoints(), numPts, cell);
 133     }
 134
 135     StripPtsType pts;
 136     StripsType strips;
 137
 138     double n[3];
 139     IdsType poly;
 140     Base base;
 141 };
 142
 143 typedef std::map<vtkIdType, PStrips> PolyStripsType;
 144
 145 typedef std::vector<std::reference_wrapper<StripPtR>> RefsType;
 146
 147 // Merger
 148
 149 typedef std::vector<std::size_t> GroupType;
 150
 151 typedef std::map<vtkIdType, std::size_t> SourcesType;
 152
 153 class Conn {
 154 public:
 155     Conn () = delete;
 156     Conn (double d, vtkIdType i, vtkIdType j) : d(d), i(i), j(j) {}
 157
 158     double d;
 159     vtkIdType i, j;
 160
 161     bool operator< (const Conn &other) const {
 162         return d < other.d;
 163     }
 164
 165     friend std::ostream& operator<< (std::ostream &out, const Conn &c) {
 166         out << "Conn(d=" << c.d
 167             << ", i=" << c.i
 168             << ", j=" << c.j
 169             << ")";
 170         return out;
 171     }
 172
 173 };
 174
 175 struct ConnCmp {
 176     bool operator() (const Conn &a, const Conn &b) const {
 177         return std::tie(a.i, a.j) < std::tie(b.i, b.j);
 178     }
 179 };
 180
 181 typedef std::vector<Conn> ConnsType;
 182 typedef std::map<std::size_t, ConnsType> PolyConnsType;
 183
 184 inline std::ostream& operator<< (std::ostream &out, const PolyConnsType& polyConns) {
 185     PolyConnsType::const_iterator itr;
 186
 187     for (itr = polyConns.begin(); itr != polyConns.end(); ++itr) {
 188         out << itr->first << ": [";
 189         for (auto &conn : itr->second) {
 190             out << conn << ", ";
 191         }
 192         out << "]" << std::endl;
 193     }
 194
 195     return out;
 196 }
 197
 198 class Prio {
 199 public:
 200     Prio () = delete;
 201     Prio (const Conn &conn, const std::set<std::size_t> &solvable, double d) : conn(conn), solvable(solvable), d(d) {}
 202
 203     Conn conn;
 204     std::set<std::size_t> solvable;
 205     double d;
 206
 207     friend std::ostream& operator<< (std::ostream &out, const Prio &p) {
 208         out << "Prio(conn=" << p.conn
 209             << ", d=" << p.d
 210             << ")";
 211         return out;
 212     }
 213 };
 214
 215 struct Cmp {
 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);
 220     }
 221 };
 222
 223 typedef std::set<Prio, Cmp> PriosType;
 224
 225 typedef std::map<std::size_t, Prio> PolyPriosType;
 226
 227 class Merger {
 228     vtkPolyData *pd;
 229     const PStrips &pStrips;
 230     vtkIdType origId;
 231
 232     PolysType polys;
 233 public:
 234     Merger (vtkPolyData *pd, const PStrips &pStrips, const StripsType &strips, const IdsType &descIds, vtkIdType origId);
 235     void Run ();
 236
 237 private:
 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);
 240 };
 241
 242 class VTK_EXPORT vtkPolyDataBooleanFilter : public vtkPolyDataAlgorithm {
 243     vtkPolyData *resultA, *resultB, *resultC;
 244
 245     vtkSmartPointer<vtkPolyData> modPdA, modPdB, contLines;
 246
 247     vtkSmartPointer<vtkCellData> cellDataA, cellDataB;
 248     vtkSmartPointer<vtkIdTypeArray> cellIdsA, cellIdsB;
 249
 250     vtkIdTypeArray *contsA, *contsB;
 251
 252     unsigned long timePdA, timePdB;
 253
 254     PolyStripsType polyStripsA, polyStripsB;
 255
 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 ();
 268
 269     int OperMode;
 270
 271 public:
 272     vtkTypeMacro(vtkPolyDataBooleanFilter, vtkPolyDataAlgorithm);
 273     static vtkPolyDataBooleanFilter* New ();
 274
 275     vtkSetClampMacro(OperMode, int, OPER_NONE, OPER_DIFFERENCE2);
 276     vtkGetMacro(OperMode, int);
 277
 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(); }
 283
 284 protected:
 285     vtkPolyDataBooleanFilter ();
 286     ~vtkPolyDataBooleanFilter ();
 287
 288     int ProcessRequest (vtkInformation *request, vtkInformationVector **inputVector, vtkInformationVector *outputVector) override;
 289
 290     void PrintSelf (ostream&, vtkIndent) override {};
 291
 292 private:
 293     vtkPolyDataBooleanFilter (const vtkPolyDataBooleanFilter&) = delete;
 294     void operator= (const vtkPolyDataBooleanFilter&) = delete;
 295
 296 };
 297
 298 #endif