1 //============================================================================
2 //  Copyright (c) Kitware, Inc.
3 //  All rights reserved.
4 //  See LICENSE.txt for details.
5 //
6 //  This software is distributed WITHOUT ANY WARRANTY; without even
7 //  the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
8 //  PURPOSE.  See the above copyright notice for more information.
9 //============================================================================
10 #ifndef vtk_m_rendering_Triangulator_h
11 #define vtk_m_rendering_Triangulator_h
12 
13 #include <typeinfo>
14 #include <vtkm/cont/Algorithm.h>
15 #include <vtkm/cont/ArrayHandleCounting.h>
16 #include <vtkm/cont/CellSetPermutation.h>
17 #include <vtkm/cont/DataSet.h>
18 #include <vtkm/rendering/raytracing/MeshConnectivityBuilder.h>
19 #include <vtkm/worklet/DispatcherMapField.h>
20 #include <vtkm/worklet/DispatcherMapTopology.h>
21 #include <vtkm/worklet/WorkletMapField.h>
22 #include <vtkm/worklet/WorkletMapTopology.h>
23 namespace vtkm
24 {
25 namespace rendering
26 {
27 /// \brief Triangulator creates a minimal set of triangles from a cell set.
28 ///
29 ///  This class creates a array of triangle indices from both 3D and 2D
30 ///  explicit cell sets. This list can serve as input to opengl and the
31 ///  ray tracer scene renderers.
32 ///
33 class Triangulator
34 {
35 public:
36   class CountTriangles : public vtkm::worklet::WorkletVisitCellsWithPoints
37   {
38   public:
39     VTKM_CONT
CountTriangles()40     CountTriangles() {}
41     using ControlSignature = void(CellSetIn cellset, FieldOut);
42     using ExecutionSignature = void(CellShape, _2);
43 
44     VTKM_EXEC
operator()45     void operator()(vtkm::CellShapeTagGeneric shapeType, vtkm::Id& triangles) const
46     {
47       if (shapeType.Id == vtkm::CELL_SHAPE_TRIANGLE)
48         triangles = 1;
49       else if (shapeType.Id == vtkm::CELL_SHAPE_QUAD)
50         triangles = 2;
51       else if (shapeType.Id == vtkm::CELL_SHAPE_TETRA)
52         triangles = 4;
53       else if (shapeType.Id == vtkm::CELL_SHAPE_HEXAHEDRON)
54         triangles = 12;
55       else if (shapeType.Id == vtkm::CELL_SHAPE_WEDGE)
56         triangles = 8;
57       else if (shapeType.Id == vtkm::CELL_SHAPE_PYRAMID)
58         triangles = 6;
59       else
60         triangles = 0;
61     }
62 
63     VTKM_EXEC
operator()64     void operator()(vtkm::CellShapeTagHexahedron vtkmNotUsed(shapeType), vtkm::Id& triangles) const
65     {
66       triangles = 12;
67     }
68 
69     VTKM_EXEC
operator()70     void operator()(vtkm::CellShapeTagQuad vtkmNotUsed(shapeType), vtkm::Id& triangles) const
71     {
72       triangles = 2;
73     }
74     VTKM_EXEC
operator()75     void operator()(vtkm::CellShapeTagWedge vtkmNotUsed(shapeType), vtkm::Id& triangles) const
76     {
77       triangles = 8;
78     }
79   }; //class CountTriangles
80 
81   template <int DIM>
82   class TriangulateStructured : public vtkm::worklet::WorkletVisitCellsWithPoints
83   {
84 
85   public:
86     using ControlSignature = void(CellSetIn cellset, FieldInCell, WholeArrayOut);
87     using ExecutionSignature = void(IncidentElementIndices, _2, _3);
88     VTKM_CONT
TriangulateStructured()89     TriangulateStructured() {}
90 
91 #if defined(VTKM_MSVC)
92 #pragma warning(push)
93 #pragma warning(disable : 4127) //conditional expression is constant
94 #endif
95     template <typename CellNodeVecType, typename OutIndicesPortal>
operator()96     VTKM_EXEC void operator()(const CellNodeVecType& cellIndices,
97                               const vtkm::Id& cellIndex,
98                               OutIndicesPortal& outputIndices) const
99     {
100       vtkm::Id4 triangle;
101       if (DIM == 2)
102       {
103         const vtkm::Id triangleOffset = cellIndex * 2;
104         // 0-1-2
105         triangle[1] = cellIndices[0];
106         triangle[2] = cellIndices[1];
107         triangle[3] = cellIndices[2];
108         triangle[0] = cellIndex;
109         outputIndices.Set(triangleOffset, triangle);
110         // 0-3-2
111         triangle[2] = cellIndices[3];
112         outputIndices.Set(triangleOffset + 1, triangle);
113       }
114       else if (DIM == 3)
115       {
116         const vtkm::Id triangleOffset = cellIndex * 12;
117 
118         triangle[1] = cellIndices[0];
119         triangle[2] = cellIndices[1];
120         triangle[3] = cellIndices[5];
121         triangle[0] = cellIndex;
122         outputIndices.Set(triangleOffset, triangle);
123 
124         triangle[1] = cellIndices[0];
125         triangle[2] = cellIndices[5];
126         triangle[3] = cellIndices[4];
127         outputIndices.Set(triangleOffset + 1, triangle);
128 
129         triangle[1] = cellIndices[1];
130         triangle[2] = cellIndices[2];
131         triangle[3] = cellIndices[6];
132         outputIndices.Set(triangleOffset + 2, triangle);
133 
134         triangle[1] = cellIndices[1];
135         triangle[2] = cellIndices[6];
136         triangle[3] = cellIndices[5];
137         outputIndices.Set(triangleOffset + 3, triangle);
138 
139         triangle[1] = cellIndices[3];
140         triangle[2] = cellIndices[7];
141         triangle[3] = cellIndices[6];
142         outputIndices.Set(triangleOffset + 4, triangle);
143 
144         triangle[1] = cellIndices[3];
145         triangle[2] = cellIndices[6];
146         triangle[3] = cellIndices[2];
147         outputIndices.Set(triangleOffset + 5, triangle);
148 
149         triangle[1] = cellIndices[0];
150         triangle[2] = cellIndices[4];
151         triangle[3] = cellIndices[7];
152         outputIndices.Set(triangleOffset + 6, triangle);
153 
154         triangle[1] = cellIndices[0];
155         triangle[2] = cellIndices[7];
156         triangle[3] = cellIndices[3];
157         outputIndices.Set(triangleOffset + 7, triangle);
158 
159         triangle[1] = cellIndices[0];
160         triangle[2] = cellIndices[3];
161         triangle[3] = cellIndices[2];
162         outputIndices.Set(triangleOffset + 8, triangle);
163 
164         triangle[1] = cellIndices[0];
165         triangle[2] = cellIndices[2];
166         triangle[3] = cellIndices[1];
167         outputIndices.Set(triangleOffset + 9, triangle);
168 
169         triangle[1] = cellIndices[4];
170         triangle[2] = cellIndices[5];
171         triangle[3] = cellIndices[6];
172         outputIndices.Set(triangleOffset + 10, triangle);
173 
174         triangle[1] = cellIndices[4];
175         triangle[2] = cellIndices[6];
176         triangle[3] = cellIndices[7];
177         outputIndices.Set(triangleOffset + 11, triangle);
178       }
179     }
180 #if defined(VTKM_MSVC)
181 #pragma warning(pop)
182 #endif
183   };
184 
185 
186   class IndicesSort : public vtkm::worklet::WorkletMapField
187   {
188   public:
189     VTKM_CONT
IndicesSort()190     IndicesSort() {}
191     using ControlSignature = void(FieldInOut);
192     using ExecutionSignature = void(_1);
193     VTKM_EXEC
operator()194     void operator()(vtkm::Id4& triangleIndices) const
195     {
196       // first field contains the id of the cell the
197       // trianlge belongs to
198       vtkm::Id temp;
199       if (triangleIndices[1] > triangleIndices[3])
200       {
201         temp = triangleIndices[1];
202         triangleIndices[1] = triangleIndices[3];
203         triangleIndices[3] = temp;
204       }
205       if (triangleIndices[1] > triangleIndices[2])
206       {
207         temp = triangleIndices[1];
208         triangleIndices[1] = triangleIndices[2];
209         triangleIndices[2] = temp;
210       }
211       if (triangleIndices[2] > triangleIndices[3])
212       {
213         temp = triangleIndices[2];
214         triangleIndices[2] = triangleIndices[3];
215         triangleIndices[3] = temp;
216       }
217     }
218   }; //class IndicesSort
219 
220   struct IndicesLessThan
221   {
222     VTKM_EXEC_CONT
operatorIndicesLessThan223     bool operator()(const vtkm::Id4& a, const vtkm::Id4& b) const
224     {
225       if (a[1] < b[1])
226         return true;
227       if (a[1] > b[1])
228         return false;
229       if (a[2] < b[2])
230         return true;
231       if (a[2] > b[2])
232         return false;
233       if (a[3] < b[3])
234         return true;
235       return false;
236     }
237   };
238 
239   class UniqueTriangles : public vtkm::worklet::WorkletMapField
240   {
241   public:
242     VTKM_CONT
UniqueTriangles()243     UniqueTriangles() {}
244 
245     using ControlSignature = void(WholeArrayIn, WholeArrayOut);
246     using ExecutionSignature = void(_1, _2, WorkIndex);
247 
248     VTKM_EXEC
IsTwin(const vtkm::Id4 & a,const vtkm::Id4 & b)249     bool IsTwin(const vtkm::Id4& a, const vtkm::Id4& b) const
250     {
251       return (a[1] == b[1] && a[2] == b[2] && a[3] == b[3]);
252     }
253 
254     template <typename IndicesPortalType, typename OutputFlagsPortalType>
operator()255     VTKM_EXEC void operator()(const IndicesPortalType& indices,
256                               OutputFlagsPortalType& outputFlags,
257                               const vtkm::Id& index) const
258     {
259       if (index == 0)
260         return;
261       //if we are a shared face, mark ourself and neighbor for destruction
262       if (IsTwin(indices.Get(index), indices.Get(index - 1)))
263       {
264         outputFlags.Set(index, 0);
265         outputFlags.Set(index - 1, 0);
266       }
267     }
268   }; //class UniqueTriangles
269 
270   class Triangulate : public vtkm::worklet::WorkletVisitCellsWithPoints
271   {
272 
273   public:
274     VTKM_CONT
Triangulate()275     Triangulate() {}
276     using ControlSignature = void(CellSetIn cellset, FieldInCell, WholeArrayOut);
277     using ExecutionSignature = void(_2, CellShape, PointIndices, WorkIndex, _3);
278 
279     template <typename VecType, typename OutputPortal>
operator()280     VTKM_EXEC void operator()(const vtkm::Id& triangleOffset,
281                               vtkm::CellShapeTagWedge vtkmNotUsed(shapeType),
282                               const VecType& cellIndices,
283                               const vtkm::Id& cellId,
284                               OutputPortal& outputIndices) const
285     {
286       vtkm::Id4 triangle;
287 
288       triangle[1] = cellIndices[0];
289       triangle[2] = cellIndices[1];
290       triangle[3] = cellIndices[2];
291       triangle[0] = cellId;
292       outputIndices.Set(triangleOffset, triangle);
293 
294       triangle[1] = cellIndices[3];
295       triangle[2] = cellIndices[5];
296       triangle[3] = cellIndices[4];
297       outputIndices.Set(triangleOffset + 1, triangle);
298 
299       triangle[1] = cellIndices[3];
300       triangle[2] = cellIndices[0];
301       triangle[3] = cellIndices[2];
302       outputIndices.Set(triangleOffset + 2, triangle);
303 
304       triangle[1] = cellIndices[3];
305       triangle[2] = cellIndices[2];
306       triangle[3] = cellIndices[5];
307       outputIndices.Set(triangleOffset + 3, triangle);
308 
309       triangle[1] = cellIndices[1];
310       triangle[2] = cellIndices[4];
311       triangle[3] = cellIndices[5];
312       outputIndices.Set(triangleOffset + 4, triangle);
313 
314       triangle[1] = cellIndices[1];
315       triangle[2] = cellIndices[5];
316       triangle[3] = cellIndices[2];
317       outputIndices.Set(triangleOffset + 5, triangle);
318 
319       triangle[1] = cellIndices[0];
320       triangle[2] = cellIndices[3];
321       triangle[3] = cellIndices[4];
322       outputIndices.Set(triangleOffset + 6, triangle);
323 
324       triangle[1] = cellIndices[0];
325       triangle[2] = cellIndices[4];
326       triangle[3] = cellIndices[1];
327       outputIndices.Set(triangleOffset + 7, triangle);
328     }
329     template <typename VecType, typename OutputPortal>
operator()330     VTKM_EXEC void operator()(const vtkm::Id& triangleOffset,
331                               vtkm::CellShapeTagQuad vtkmNotUsed(shapeType),
332                               const VecType& cellIndices,
333                               const vtkm::Id& cellId,
334                               OutputPortal& outputIndices) const
335     {
336       vtkm::Id4 triangle;
337 
338 
339       triangle[1] = cellIndices[0];
340       triangle[2] = cellIndices[1];
341       triangle[3] = cellIndices[2];
342       triangle[0] = cellId;
343       outputIndices.Set(triangleOffset, triangle);
344 
345       triangle[2] = cellIndices[3];
346       outputIndices.Set(triangleOffset + 1, triangle);
347     }
348 
349     template <typename VecType, typename OutputPortal>
operator()350     VTKM_EXEC void operator()(const vtkm::Id& triangleOffset,
351                               vtkm::CellShapeTagHexahedron vtkmNotUsed(shapeType),
352                               const VecType& cellIndices,
353                               const vtkm::Id& cellId,
354                               OutputPortal& outputIndices) const
355     {
356       vtkm::Id4 triangle;
357 
358       triangle[1] = cellIndices[0];
359       triangle[2] = cellIndices[1];
360       triangle[3] = cellIndices[5];
361       triangle[0] = cellId;
362       outputIndices.Set(triangleOffset, triangle);
363 
364       triangle[1] = cellIndices[0];
365       triangle[2] = cellIndices[5];
366       triangle[3] = cellIndices[4];
367       outputIndices.Set(triangleOffset + 1, triangle);
368 
369       triangle[1] = cellIndices[1];
370       triangle[2] = cellIndices[2];
371       triangle[3] = cellIndices[6];
372       outputIndices.Set(triangleOffset + 2, triangle);
373 
374       triangle[1] = cellIndices[1];
375       triangle[2] = cellIndices[6];
376       triangle[3] = cellIndices[5];
377       outputIndices.Set(triangleOffset + 3, triangle);
378 
379       triangle[1] = cellIndices[3];
380       triangle[2] = cellIndices[7];
381       triangle[3] = cellIndices[6];
382       outputIndices.Set(triangleOffset + 4, triangle);
383 
384       triangle[1] = cellIndices[3];
385       triangle[2] = cellIndices[6];
386       triangle[3] = cellIndices[2];
387       outputIndices.Set(triangleOffset + 5, triangle);
388 
389       triangle[1] = cellIndices[0];
390       triangle[2] = cellIndices[4];
391       triangle[3] = cellIndices[7];
392       outputIndices.Set(triangleOffset + 6, triangle);
393 
394       triangle[1] = cellIndices[0];
395       triangle[2] = cellIndices[7];
396       triangle[3] = cellIndices[3];
397       outputIndices.Set(triangleOffset + 7, triangle);
398 
399       triangle[1] = cellIndices[0];
400       triangle[2] = cellIndices[3];
401       triangle[3] = cellIndices[2];
402       outputIndices.Set(triangleOffset + 8, triangle);
403 
404       triangle[1] = cellIndices[0];
405       triangle[2] = cellIndices[2];
406       triangle[3] = cellIndices[1];
407       outputIndices.Set(triangleOffset + 9, triangle);
408 
409       triangle[1] = cellIndices[4];
410       triangle[2] = cellIndices[5];
411       triangle[3] = cellIndices[6];
412       outputIndices.Set(triangleOffset + 10, triangle);
413 
414       triangle[1] = cellIndices[4];
415       triangle[2] = cellIndices[6];
416       triangle[3] = cellIndices[7];
417       outputIndices.Set(triangleOffset + 11, triangle);
418     }
419 
420     template <typename VecType, typename OutputPortal>
operator()421     VTKM_EXEC void operator()(const vtkm::Id& triangleOffset,
422                               vtkm::CellShapeTagGeneric shapeType,
423                               const VecType& cellIndices,
424                               const vtkm::Id& cellId,
425                               OutputPortal& outputIndices) const
426     {
427       vtkm::Id4 triangle;
428 
429       if (shapeType.Id == vtkm::CELL_SHAPE_TRIANGLE)
430       {
431 
432         triangle[1] = cellIndices[0];
433         triangle[2] = cellIndices[1];
434         triangle[3] = cellIndices[2];
435         triangle[0] = cellId;
436         outputIndices.Set(triangleOffset, triangle);
437       }
438       if (shapeType.Id == vtkm::CELL_SHAPE_QUAD)
439       {
440 
441         triangle[1] = cellIndices[0];
442         triangle[2] = cellIndices[1];
443         triangle[3] = cellIndices[2];
444         triangle[0] = cellId;
445         outputIndices.Set(triangleOffset, triangle);
446 
447         triangle[2] = cellIndices[3];
448         outputIndices.Set(triangleOffset + 1, triangle);
449       }
450       if (shapeType.Id == vtkm::CELL_SHAPE_TETRA)
451       {
452         triangle[1] = cellIndices[0];
453         triangle[2] = cellIndices[3];
454         triangle[3] = cellIndices[1];
455         triangle[0] = cellId;
456         outputIndices.Set(triangleOffset, triangle);
457 
458         triangle[1] = cellIndices[1];
459         triangle[2] = cellIndices[2];
460         triangle[3] = cellIndices[3];
461         outputIndices.Set(triangleOffset + 1, triangle);
462 
463         triangle[1] = cellIndices[0];
464         triangle[2] = cellIndices[2];
465         triangle[3] = cellIndices[3];
466         outputIndices.Set(triangleOffset + 2, triangle);
467 
468         triangle[1] = cellIndices[0];
469         triangle[2] = cellIndices[2];
470         triangle[3] = cellIndices[1];
471         outputIndices.Set(triangleOffset + 3, triangle);
472       }
473       if (shapeType.Id == vtkm::CELL_SHAPE_HEXAHEDRON)
474       {
475         triangle[1] = cellIndices[0];
476         triangle[2] = cellIndices[1];
477         triangle[3] = cellIndices[5];
478         triangle[0] = cellId;
479         outputIndices.Set(triangleOffset, triangle);
480 
481         triangle[1] = cellIndices[0];
482         triangle[2] = cellIndices[5];
483         triangle[3] = cellIndices[4];
484         outputIndices.Set(triangleOffset + 1, triangle);
485 
486         triangle[1] = cellIndices[1];
487         triangle[2] = cellIndices[2];
488         triangle[3] = cellIndices[6];
489         outputIndices.Set(triangleOffset + 2, triangle);
490 
491         triangle[1] = cellIndices[1];
492         triangle[2] = cellIndices[6];
493         triangle[3] = cellIndices[5];
494         outputIndices.Set(triangleOffset + 3, triangle);
495 
496         triangle[1] = cellIndices[3];
497         triangle[2] = cellIndices[7];
498         triangle[3] = cellIndices[6];
499         outputIndices.Set(triangleOffset + 4, triangle);
500 
501         triangle[1] = cellIndices[3];
502         triangle[2] = cellIndices[6];
503         triangle[3] = cellIndices[2];
504         outputIndices.Set(triangleOffset + 5, triangle);
505 
506         triangle[1] = cellIndices[0];
507         triangle[2] = cellIndices[4];
508         triangle[3] = cellIndices[7];
509         outputIndices.Set(triangleOffset + 6, triangle);
510 
511         triangle[1] = cellIndices[0];
512         triangle[2] = cellIndices[7];
513         triangle[3] = cellIndices[3];
514         outputIndices.Set(triangleOffset + 7, triangle);
515 
516         triangle[1] = cellIndices[0];
517         triangle[2] = cellIndices[3];
518         triangle[3] = cellIndices[2];
519         outputIndices.Set(triangleOffset + 8, triangle);
520 
521         triangle[1] = cellIndices[0];
522         triangle[2] = cellIndices[2];
523         triangle[3] = cellIndices[1];
524         outputIndices.Set(triangleOffset + 9, triangle);
525 
526         triangle[1] = cellIndices[4];
527         triangle[2] = cellIndices[5];
528         triangle[3] = cellIndices[6];
529         outputIndices.Set(triangleOffset + 10, triangle);
530 
531         triangle[1] = cellIndices[4];
532         triangle[2] = cellIndices[6];
533         triangle[3] = cellIndices[7];
534         outputIndices.Set(triangleOffset + 11, triangle);
535       }
536       if (shapeType.Id == vtkm::CELL_SHAPE_WEDGE)
537       {
538         triangle[1] = cellIndices[0];
539         triangle[2] = cellIndices[1];
540         triangle[3] = cellIndices[2];
541         triangle[0] = cellId;
542         outputIndices.Set(triangleOffset, triangle);
543 
544         triangle[1] = cellIndices[3];
545         triangle[2] = cellIndices[5];
546         triangle[3] = cellIndices[4];
547         outputIndices.Set(triangleOffset + 1, triangle);
548 
549         triangle[1] = cellIndices[3];
550         triangle[2] = cellIndices[0];
551         triangle[3] = cellIndices[2];
552         outputIndices.Set(triangleOffset + 2, triangle);
553 
554         triangle[1] = cellIndices[3];
555         triangle[2] = cellIndices[2];
556         triangle[3] = cellIndices[5];
557         outputIndices.Set(triangleOffset + 3, triangle);
558 
559         triangle[1] = cellIndices[1];
560         triangle[2] = cellIndices[4];
561         triangle[3] = cellIndices[5];
562         outputIndices.Set(triangleOffset + 4, triangle);
563 
564         triangle[1] = cellIndices[1];
565         triangle[2] = cellIndices[5];
566         triangle[3] = cellIndices[2];
567         outputIndices.Set(triangleOffset + 5, triangle);
568 
569         triangle[1] = cellIndices[0];
570         triangle[2] = cellIndices[3];
571         triangle[3] = cellIndices[4];
572         outputIndices.Set(triangleOffset + 6, triangle);
573 
574         triangle[1] = cellIndices[0];
575         triangle[2] = cellIndices[4];
576         triangle[3] = cellIndices[1];
577         outputIndices.Set(triangleOffset + 7, triangle);
578       }
579       if (shapeType.Id == vtkm::CELL_SHAPE_PYRAMID)
580       {
581         triangle[1] = cellIndices[0];
582         triangle[2] = cellIndices[4];
583         triangle[3] = cellIndices[1];
584         triangle[0] = cellId;
585         outputIndices.Set(triangleOffset, triangle);
586 
587         triangle[1] = cellIndices[1];
588         triangle[2] = cellIndices[2];
589         triangle[3] = cellIndices[4];
590         outputIndices.Set(triangleOffset + 1, triangle);
591 
592         triangle[1] = cellIndices[2];
593         triangle[2] = cellIndices[3];
594         triangle[3] = cellIndices[4];
595         outputIndices.Set(triangleOffset + 2, triangle);
596 
597         triangle[1] = cellIndices[0];
598         triangle[2] = cellIndices[4];
599         triangle[3] = cellIndices[3];
600         outputIndices.Set(triangleOffset + 3, triangle);
601 
602         triangle[1] = cellIndices[3];
603         triangle[2] = cellIndices[2];
604         triangle[3] = cellIndices[1];
605         outputIndices.Set(triangleOffset + 4, triangle);
606 
607         triangle[1] = cellIndices[3];
608         triangle[2] = cellIndices[1];
609         triangle[3] = cellIndices[0];
610         outputIndices.Set(triangleOffset + 5, triangle);
611       }
612     }
613   }; //class Triangulate
614 
615 public:
616   VTKM_CONT
Triangulator()617   Triangulator() {}
618 
619   VTKM_CONT
ExternalTriangles(vtkm::cont::ArrayHandle<vtkm::Id4> & outputIndices,vtkm::Id & outputTriangles)620   void ExternalTriangles(vtkm::cont::ArrayHandle<vtkm::Id4>& outputIndices,
621                          vtkm::Id& outputTriangles)
622   {
623     //Eliminate unseen triangles
624     vtkm::worklet::DispatcherMapField<IndicesSort> sortInvoker;
625     sortInvoker.Invoke(outputIndices);
626 
627     vtkm::cont::Algorithm::Sort(outputIndices, IndicesLessThan());
628     vtkm::cont::ArrayHandle<vtkm::UInt8> flags;
629     flags.Allocate(outputTriangles);
630 
631     vtkm::cont::ArrayHandleConstant<vtkm::Id> one(1, outputTriangles);
632     vtkm::cont::Algorithm::Copy(one, flags);
633     //Unique triangles will have a flag = 1
634     vtkm::worklet::DispatcherMapField<UniqueTriangles>().Invoke(outputIndices, flags);
635 
636     vtkm::cont::ArrayHandle<vtkm::Id4> subset;
637     vtkm::cont::Algorithm::CopyIf(outputIndices, flags, subset);
638     outputIndices = subset;
639     outputTriangles = subset.GetNumberOfValues();
640   }
641 
642   VTKM_CONT
Run(const vtkm::cont::DynamicCellSet & cellset,vtkm::cont::ArrayHandle<vtkm::Id4> & outputIndices,vtkm::Id & outputTriangles)643   void Run(const vtkm::cont::DynamicCellSet& cellset,
644            vtkm::cont::ArrayHandle<vtkm::Id4>& outputIndices,
645            vtkm::Id& outputTriangles)
646   {
647     bool fastPath = false;
648     if (cellset.IsSameType(vtkm::cont::CellSetStructured<3>()))
649     {
650       //vtkm::cont::CellSetStructured<3> cellSetStructured3D =
651       //  cellset.Cast<vtkm::cont::CellSetStructured<3>>();
652 
653       //raytracing::MeshConnectivityBuilder<Device> builder;
654       //outputIndices = builder.ExternalTrianglesStructured(cellSetStructured3D);
655       //outputTriangles = outputIndices.GetNumberOfValues();
656       //fastPath = true;
657       vtkm::cont::CellSetStructured<3> cellSetStructured3D =
658         cellset.Cast<vtkm::cont::CellSetStructured<3>>();
659       const vtkm::Id numCells = cellSetStructured3D.GetNumberOfCells();
660 
661       vtkm::cont::ArrayHandleCounting<vtkm::Id> cellIdxs(0, 1, numCells);
662       outputIndices.Allocate(numCells * 12);
663       vtkm::worklet::DispatcherMapTopology<TriangulateStructured<3>>(TriangulateStructured<3>())
664         .Invoke(cellSetStructured3D, cellIdxs, outputIndices);
665 
666       outputTriangles = numCells * 12;
667     }
668     else if (cellset.IsSameType(vtkm::cont::CellSetStructured<2>()))
669     {
670       vtkm::cont::CellSetStructured<2> cellSetStructured2D =
671         cellset.Cast<vtkm::cont::CellSetStructured<2>>();
672       const vtkm::Id numCells = cellSetStructured2D.GetNumberOfCells();
673 
674       vtkm::cont::ArrayHandleCounting<vtkm::Id> cellIdxs(0, 1, numCells);
675       outputIndices.Allocate(numCells * 2);
676       vtkm::worklet::DispatcherMapTopology<TriangulateStructured<2>>(TriangulateStructured<2>())
677         .Invoke(cellSetStructured2D, cellIdxs, outputIndices);
678 
679       outputTriangles = numCells * 2;
680       // no need to do external faces on 2D cell set
681       fastPath = true;
682     }
683     else
684     {
685       auto cellSetUnstructured =
686         cellset.ResetCellSetList(VTKM_DEFAULT_CELL_SET_LIST_UNSTRUCTURED{});
687       vtkm::cont::ArrayHandle<vtkm::Id> trianglesPerCell;
688       vtkm::worklet::DispatcherMapTopology<CountTriangles>(CountTriangles())
689         .Invoke(cellSetUnstructured, trianglesPerCell);
690 
691       vtkm::Id totalTriangles = 0;
692       totalTriangles = vtkm::cont::Algorithm::Reduce(trianglesPerCell, vtkm::Id(0));
693 
694       vtkm::cont::ArrayHandle<vtkm::Id> cellOffsets;
695       vtkm::cont::Algorithm::ScanExclusive(trianglesPerCell, cellOffsets);
696       outputIndices.Allocate(totalTriangles);
697 
698       vtkm::worklet::DispatcherMapTopology<Triangulate>(Triangulate())
699         .Invoke(cellSetUnstructured, cellOffsets, outputIndices);
700 
701       outputTriangles = totalTriangles;
702     }
703 
704     //get rid of any triagles we cannot see
705     if (!fastPath)
706     {
707       ExternalTriangles(outputIndices, outputTriangles);
708     }
709   }
710 }; // class Triangulator
711 }
712 } //namespace vtkm::rendering
713 #endif //vtk_m_rendering_Triangulator_h
714