1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
// SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
// SPDX-License-Identifier: BSD-3-Clause
// clang-format off
/**
* @class vtkPConnectivityFilter
* @brief Parallel version of vtkConnectivityFilter
*
* This class computes connectivity of a distributed data set in parallel.
*
* Problem
* =======
*
* Datasets are distributed among ranks in a distributed process (Figure 1).
* vtkConnectivityFilter already runs in parallel on each piece in a typical
* VTK application run with MPI, but it does not produce correct results. As
* Figure 2 shows, distributed pieces of each connected component may end up
* with different labels.
*
* 
*
* 
*
* The part missing from a fully parallel connectivity filter implementation is
* the identification of which pieces on different ranks are actually connected.
* This parallel filter provides that missing piece.
*
* Approach
* ========
*
* Run vtkConnectivityFilter on each rank’s piece and resolve the connected
* pieces afterwards. The implementation uses vtkMPIProcessController to
* communicate among processes.
*
* Steps in the vtkPConnectivityFilter
* -----------------------------------
*
* ### High-level steps
*
* + Run local connectivity algorithm.
*
* + Identify region connections across ranks and create a graph of these links.
*
* + Run a connected components algorithm on the graph created in the previous
* step to unify the regions across ranks.
*
* + Relabel cells and points with their “global” RegionIds.
*
* ### Low-level steps
*
* + In GenerateData(), invoke the superclass’s GenerateData() method. Make
* temporary changes to extract all connected regions - we’ll handle the
* different extraction modes at the end. Example results on 3 ranks are shown
* in Figure 3 where color indicates RegionId computed by vtkConnectivityFilter.
*
* + Check for errors in superclass GenerateData() on any rank and exit the
* algorithm if any encountered an error-indicating return code.
*
* 
*
* + AllGatherv the number of connected RegionIds from each rank and AllGatherv
* the RegionIds themselves.
*
* + Gather all axis-aligned bounding boxes from all other ranks. This is used
* to compute potential neighbors with which each rank should exchange points and
* RegionIds.
*
* 
*
* + Each rank gathers up points potentially coincident with points on neighboring
* ranks and sends them to their neighbors as well
* as the RegionId assigned to each point.
*
* + Each rank runs through the received points and determines which points it owns
* using a locator object. If a point is found on the local rank, add the
* RegionId from the remote point to a set associated with the local
* RegionId. This signifies that the local RegionId is connected to the remote
* RegionId associated with the point.
*
* + Each rank gathers the local-RegionId-to-remote-RegionId links from all
* other ranks.
*
* + From these links, each rank generates a graph structure of the global
* links. The graph structure is identical on all ranks. (Optimization
* opportunity: To reduce communication, this link exchange could be avoided and
* the graph could be made distributed. This is just more complicated to
* program, however).
*
* 
*
* + Run a connected components algorithm that relabels the RegionIds, yielding
* the full connectivity graph across ranks. Figure 6 shows an example result.
*
* + Relabel the remaining RegionIds by a contiguous set of RegionIds (e.g., go
* from [0, 5, 8, 9] to [0, 1, 2, 3]).
*
* 
*
* + From the RegionId graph, relabel points and cells in the output. The result
* is shown in Figure 7.
*
* 
*
* + Handle ScalarConnectivy option and ExtractionMode after full region
* connectivity is determined by identifying the correct RegionId and extracting
* it by thresholding.
*
* Caveats
* =======
*
* This parallel implementation does not support a number of features that the
* vtkConnectivityFilter class supports, including:
*
* - ScalarConnectivity
* - VTK_EXTRACT_POINT_SEEDED_REGIONS extraction mode
* - VTK_EXTRACT_CELL_SEEDED_REGIONS extraction mode
* - VTK_EXTRACT_SPECIFIED_REGIONS extraction mode
*/
// clang-format on
#ifndef vtkPConnectivityFilter_h
#define vtkPConnectivityFilter_h
#include "vtkConnectivityFilter.h"
#include "vtkFiltersParallelGeometryModule.h" // For export macro
VTK_ABI_NAMESPACE_BEGIN
class VTKFILTERSPARALLELGEOMETRY_EXPORT vtkPConnectivityFilter : public vtkConnectivityFilter
{
public:
vtkTypeMacro(vtkPConnectivityFilter, vtkConnectivityFilter);
void PrintSelf(ostream& os, vtkIndent indent) override;
static vtkPConnectivityFilter* New();
protected:
vtkPConnectivityFilter();
~vtkPConnectivityFilter() override;
int RequestData(vtkInformation*, vtkInformationVector**, vtkInformationVector*) override;
private:
vtkPConnectivityFilter(const vtkPConnectivityFilter&) = delete;
void operator=(const vtkPConnectivityFilter&) = delete;
};
VTK_ABI_NAMESPACE_END
#endif
|
