Yet Another Iteration Over Selections

This page summarizes a new design for changing the selection implementation in VTK and ParaView. This design proposes a replacement for vtkSelection and vtkExtractSelected* classes in VTK.

Drawbacks of the Current Design

The fundamental drawback of the current design is that it's not possible to combine multiple selection criteria together easily. The problem is two fold, not only is it not possible in vtkSelection to define such a selection-object, it's complicated to combine multiple extract-selection filters to extract such a combined selection.

Another issue is that it's not easy to add new selection types no the fly. Code in VTK needs to be changed everytime a new selection ContentType is added.

Implementation wise, vtkSelection uses overloaded SelectionList which is prone to errors and requires redundant checks and validations time and again.

Selection 3.0

This proposal, proposes three main classes:

• vtkSelection2 - this is the vtkDataObject subclass that will eventually replace the deprecated vtkSelection.
• vtkSelectionPredicate - this is superclass for a "criteria". This roughly corresponds to vtkSelectionNode in VTK 5.6.
• vtkBlockSelectionPredicate - same as vtkSelectionPredicate with the exception that it's used only to determine if a block in a composite dataset is selected.
• vtkGenericExtractSelection - this is the only extract selection filter that's needed in this new design unlike VTK 5.6 that has several filters e.g. vtkExtractSelectedIds, vtkExtractSelectedFrustum, vtkExtractSelectedRows etc.

vtkSelection2

The important API for vtkSelection2 is as follows:

class VTK_FILTERING_EXPORT vtkSelection2 : public vtkDataObject
{
public:

  ...

  // Description:
  // FieldType is used to determine the field association for the selection e.g.
  // cells, points, rows etc. It identifies what elements are being selected.
  // Accepted values are defined in vtkDataObject::FieldAssociations enum.
  vtkSetMacro(FieldType, int);
  vtkGetMacro(FieldType, int);

  // Description:
  // Get/Set the block-predicate. BlockPredicate is the predicate used to test
  // if a block in a composite dataset is selected or not.
  void SetBlockPredicate(vtkBlockSelectionPredicate*);
  vtkGetObjectMacro(BlockPredicate, vtkBlockSelectionPredicate);

  // Description:
  // Get/Set the predicate. This predicate defines what items are being
  // selected.
  void SetPredicate(vtkSelectionPredicate*);
  vtkGetObjectMacro(Predicate, vtkSelectionPredicate);

  ...

};

vtkSelectionPredicate

class VTK_FILTERING_EXPORT vtkSelectionPredicate : public vtkObject
{
public:
  ...

  // Description:
  // Returns true if the Initialize/Finalize methods must be called once for
  // composite datasets, or for every leaf node in the composite dataset.
  vtkGetMacro(HandlesCompositeDatasets, bool);
  vtkSetMacro(HandlesCompositeDatasets, bool);
  vtkBooleanMacro(HandlesCompositeDatasets, bool);

  // Description:
  // Called to initialize the predicate. If
  // GetHandlesCompositeDatasets() returns true, this method will once with the
  // argument being the composite dataset, else it's called for every leaf node
  // in the composite dataset.
  virtual bool Initialize(vtkSelection2* selection, vtkDataObject* dataObject);

  // Description:
  // Called for every element to test if the element is 'in' or 'out'.
  virtual bool Test(vtkSelection2* selection, vtkDataObject* dataObject,
    vtkIdType elementId);

  // Description:
  // Called to cleanup. If
  // GetHandlesCompositeDatasets() returns true, this method will once with the
  // argument being the composite dataset, else it's called for every leaf node
  // in the composite dataset.
  virtual void Finalize(vtkSelection2* selection);

  ...

};

vtkBlockSelectionPredicate

class VTK_FILTERING_EXPORT vtkBlockSelectionPredicate : public vtkObject
{
public:
  ...

  // Description:
  // Called to initialize the predicate. 
  virtual bool Initialize(vtkSelection2* selection, vtkCompositeDataSet* dataObject);

  // Description:
  // Called for every block to test if the block is 'in' or 'out'.
  virtual bool Test(vtkSelection2* selection, vtkCompositeDataIterator* iter);

  // Description:
  // Called to cleanup.
  virtual void Finalize(vtkSelection2* selection);

  ...

};

Issues/Rationales

Why not merely extend vtkSelection for backwards compatibility?

The APIs for vtkSelection and vtkSelection2 are going to be remarkably different. We are even changing the place of some attributes e.g. FieldAssociation. That'd make it confusing for users if we merged the two. Hence we keep them separate.

Are we really calling the class vtkSelection2?

No. It's just a place holder for now. Once the team comes up with a better name, we'll update the documentation. The implementation will indeed have the chosen "better" name and not vtkSelection2.

Why does vtkSelection2 have a FieldAssociation iVar?

With vtkSelection, when we moved the FieldAssociation iVar was moved from vtkSelection to vtkSelectionNode, the rationale was that we should be able to specify queries such as "in a graph, select all vertices that satisfy (A) , and select all edges that satisfy (B)". But selecting edges implies selection of corresponding vertices! So how do we deal with vertices not selected by (A) but get selected due to (B)? There's no toolkit level logic that can address such issues correctly. It's application specific. Applications should construct such heterogeneous element type queries as separate selections and then combine the results as they deem fit.

Implementation-wise, combining such multi-element-type queries into one gives no performance benefit in general since we'd iterate over each element type individually anyways.

Hence, in this new design, a selection defintion specifies the one and only one type of elements to be selected.

Why is there a separate vtkBlockSelectionPredicate?

For non-composite datasets, when extracting the selection, the vtkGenericExtractSelection filter will simply iterate over every element and test if the element is in or out using the vtkSelectionPredicate. That works well and we avoid repeated iteration over elements gracefully. Now consider the same for composite datasets. With composite datasets, it's possible to have a predicate that accepts or discards entire block. Now, if such a predicate was mixed in with the regular "element-based" predicates, we'd still loop over all elements in every node in the composite dataset even if the entire block is to be discarded. Thus performance issue can be easily avoided by keeping the predicates that select blocks separate from the predicates that select elements.

How is this design extensible when compared with previous implementation?

Developers can create vtkSelectionPredicate or vtkBlockSelectionPredicate subclasses on the fly. So long as the instantiators know how to create these new subclasses, the vtkSelection2 object will be serializable/de-serializable. Also, since the predicates encapsulate the logic to evaluate the criteria to test if the element/block is in or out, vtkGenericExtractSelection will be able to handle extracting such selections with ease.

vtkSelection (VTK 5.6), on the other hand, required every new ContentType to be added to the vtkSelectionNode header. Also vtkExtractSelection filter needed to be changed to know how to handle the newly added ContentType. Serialization/Deserialization was not possible for vtkSelection in general. ParaView uses custom code (vtkSelectionSerializer) to handle serialization of known keys.

How are combination selections supported?

We'll implement subclasses of vtkSelectionPredicate e.g. vtkBooleanSelectionPredicate that takes the boolean operation as an iVar. These can be used to combine multiple vtkSelectionPredicate subclasses.

Subclassing vtkSelectionPredicate to support different types e.g. frustum, id-based etc. makes it possible for these subclasses to provide explicit API for setting attributes unlike the current implementation where all simply override the SelectionList to mean different things.