Selection

What Is It?

Currently, VTK supports a wide variety of subsetting (extracting a subset of data based on some criteria) and picking (mapping a set of screen coordinates to zero-or-one result) functionality. This document is concerned with a more general-purpose selection capability, one that maps a region in screen space to a first-class selection set object that references an arbitrary collection of data, and is usable in a wide variety of applications and user interfaces.

Because selection is a broad topic, this discussion makes a distinction between selection policy, selection interface, and selection implementation.

Terminology

• Subsetting - extraction of an arbitrary subset of available data, for further processing by the pipeline. This is distinct from a selection set because it is copying the source data, not referencing it. Examples include vtkExtractGeometry and vtkSelectVisiblePoints.
• Selection Set - references an arbitrary subset of available data, generated by the user through interaction with the viewport, element inspector, charts, etc. This is distinct from subsetting because it references data, rather than copying it.
• Selection Policy - high-level user-observable behavior that controls interactive selection, such as selection modes, keyboard shortcuts, etc.
• Selection Interface - the abstract interface used to map user input to a selection set, and communicate that selection set to components that will make use of it.
• Selection Implementation - the concrete implementation that processes data and user input to return a selection set.
• Pick Selection - selection of zero-or-one object by clicking the mouse within the viewport. Existing examples include vtkAbstractPicker and its derivatives.
• Rubber-Band Selection - selection of zero-to-many objects that fall within a rectangular region defined by the user in screen space.
• Lasso Selection - selection of zero-to-many objects that fall within an arbitrary-shaped region defined by the user in screen space.

Policy

Requirements

• The selection mechanism should support pick selection of individual data.
• The selection mechanism should support rubber-band selection of data collections.

Open Questions

• Should rubber-band-selection select all of the objects that intersect the volume defined by the rubber-band, or only those objects that are visible? Do we need to provide both?
• Do we need to support selection of edges and points? It's critical for CAD & art applications, does it make any sense for viz?
• Is there any interest in lasso selection, or should it be given the heave-ho?

Interface

Requirements

• It should be possible to select data at all levels of detail, i.e. to select arbitrary sets of assemblies, sub-assemblies, blocks, cells, and points.
• It should be possible to select arbitrary groupings of (filter-defined) data such as blocks, individual isosurfaces in a contour, etc.
• It should be possible to select data at different timesteps, see Time Support.
• It should be possible to represent ranges of data efficiently, i.e. "select all" should be representable without enumerating all possible IDs in a dataset.
• Ideally, it should be possible to use selection-related data structures for more than just interactive on-screen selection, e.g. selecting elements in the element inspector should return the same result structure(s) as selecting them on-screen.

Design

The fundamental challenge in designing the selection interface is to define selection sets in a way that is

• Thorough - selection sets should return as much information about selected objects as the caller requires. In particular, the selection set must contain unique identifiers for the objects that are members of the set.
• Flexible - selection sets should handle different selection modes or pipeline configurations by containing only pertinent data.
• Efficient - selection set size could grow to the size of the input data, so the internal representation of the data must be efficient.

We propose a hierarchical naming scheme whereby each record in a selection set may contain one-or-more of the following tokens:

• Source ID - uniquely identifies the dataset source.
• Timestep ID - uniquely identifies the timestep for a dataset. This ID makes it possible to differentiate among cells when a single dataset is rendered to the screen at multiple timesteps.
• Prop ID - uniquely identifies the visualization network leaf component that rendered a dataset to the screen. This ID makes it possible to differentiate among cells when one dataset is rendered to the screen more-than-once by a split in the network.
• Block ID - uniquely identifies a block (group) of cells within its source dataset.
• Isosurface ID - uniquely identifies an isosurface generated by a contour filter.
• Cell ID - uniquely identifies a cell within its source dataset.
• Point ID - uniquely identifies a point within a cell.
• Other Stuff - data sources and filters may wish to provide additional tag types, e.g. a specific file type may provide additional levels of grouping or organization, a threshold filter may wish to group boundary cells, specialized filters could group together cells that meet some criteria (max temperature), etc.

In general, we assume that the set of tokens within a single record will vary depending on selection mode (if the user is only selecting props, there is no reason to record and transport cell IDs), data sources (if a source doesn't have or support blocks, the block token won't appear), pipeline configuration (if there isn't a contour filter in the network, there won't be any isosurface tokens), etc. Thus, the selection record will contain arbitrary collections of tokens, and calling code must be written accordingly.

How Can it be Used?

Assuming the above definition of a selection set that is returned by interactive selection mechanisms, it could be used by:

• The UI layer directly, to display information about the selection itself - how many cells were picked, how many blocks, etc.
• The UI layer, to display information about the objects selected - cell types, individual cell data, overall dimensions, min/max values, etc. This assumes corresponding ClientSideData mechanisms that allow the UI layer to lookup cell or other data based on the selection IDs.
• Visualization network filters - the effects of a majority of filters could reasonably be limited to data that matches a selection. This assumes mechanisms that allow the UI layer to push a selection set to a server-side object.
• Mappers - to render data differently based on whether it is selected or not - alternatively, a branch in the pipeline could send selected data to a separate mapper where it would be rendered in a different style (e.g. wireframe) to display the selection.

Specifics

With this in mind, a hypothetical interface for selection (class declarations simplified for clarity):

Note: because selection sets are potentially huge, it makes sense to keep the objects as-lightweight-as-possible, which is why they don't derive from vtkObject.

enum vtkSelectionType
{
  SOURCE_ID_TAG,
  TIMESTEP_ID_TAG,
  PROP_ID_TAG,
  BLOCK_ID_TAG,
  ISOSURFACE_ID_TAG,
  CELL_ID_TAG,
  POINT_ID_TAG,
  USER1_ID_TAG,
  USER2_ID_TAG
  /* ... */
};

/// Stores a single selection "token" which combines a range of identifiers with an enumerated type
struct vtkSelectionToken
{
  vtkSelectionType Type;
  vtkIdType Begin;
  vtkIdType End;
};

/// Stores a collection of selection tokens 
struct vtkSelectionTokenCollection
{
  /* STL-like collection interface here */
};

/// Stores a collection of tokens that describe a single intersection with the selection region
struct vtkSelectionRecord
{
  /// Stores the minimum Z value of the intersection
  double MinZ;
  vtkSelectionTokenCollection Tokens;
};

/// Stores a set of intersections with the selection region
struct vtkSelection
{
  /* STL-like collection interface here */
};

Open Questions

• Prop ID seems to be the correct way to differentiate between multiple renders of one source dataset at the VTK level, but does it make any sense at the ParaView Server Manager level?
• Can a cell be a member of more-than-one block?
• What is the impact on Isosurface ID if there is more-than-one contour filter in a pipeline, e.g. if you rendered contour lines on an isosurface?
• What is the impact on Cell ID for a filter that increases the size of a dataset?
• What is the impact on Cell ID for a filter that merges multiple source datasets?

Implementation

Assuming the above interface, the server-side implementation must be able to deliver the required results. Following are different approaches that have been proposed:

OpenGL Selection

With this approach, geometry is rendered off-screen using an OpenGL render mode of "GL_SELECT". A special camera frustum is used to limit rendering to a rectangular (in screen space) area-of-interest. For each fragment, application-defined "names" are passed to OpenGL by bracketing the OpenGL drawing commands with glPushName() and glPopName(). More than one identifier can be specified for a given fragment, allowing IDs of arbitrary size and/or hierarchical naming schemes. Once rendering is complete, OpenGL returns a "selection buffer" containing zero-to-many "selection records", one for each fragment that intersected the camera frustum. Each selection record includes the minimum Z, maximum Z, and the name(s) that were specified with glPushName().

Existing Examples

• vtkPropPicker

Pros

• Takes advantage of graphics hardware.
• Allows arbitrary application-defined naming schemes for geometry (including hierarchical names).
• Returns all geometry that intersects the selection region regardless of depth.

Cons

• Caller must supply a fixed-size buffer that will receive selection records once drawing is complete - since the number of records returned can't generally be predicted in advance, and is limited only by the size of the dataset to be rendered, the caller has to be prepared to handle selection "failure" if the buffer isn't large enough (e.g. try again with a larger buffer, return a "partial" selection, or fail).
• Doesn't support lasso selection directly (the selection region is limited to a screen rectangle, and per-pixel operations such as the stencil test aren't applied in selection mode).
• Potentially disruptive changes to the render-module interfaces - there must be a way to request a selection operation from the render module, passing arguments (selection mode, etc) and the selection region, and return a selection set. This API must be implemented in many render modules.
• Can be difficult to disambiguate points and lines from polygons when picking - this probably isn't applicable to ParaQ, but the issue is as follows: suppose you are drawing polygons with outlines and vertices. You want to be able to interactively pick a polygon, an edge, or a point. The problem is that when the user picks the region near a point, for example, you will get separate selection records for the point, the incident edges, and the polygon. If you do a naive depth-sort, the polygon will nearly always sort closer than the point or any of the lines. If you ignore depth-sorting, you may accidentally pick a point that is hidden. The solution to handle selection of points and lines is to pick the nearest geometry, and if it is a face, do some distance calculations in screen-space to pick the point or edge that is "closest" to the pointer.

Pure Geometry

With this approach, existing VTK filters are inserted into the pipeline, and are used to clip the dataset against an arbitrary volume. A small frustum can be used for picking, a larger frustum can be used for rubber-band selection, and arbitrary volumes can be used for special cases such as lasso selection.

Exising Examples

vtkPicker does geometric selection by casting rays.

Pros

• Already supports parallel execution.
• Much of the code is already written.
• Supports selection of any arbitrary volume.
• Returns all geometry that intersects the selection region regardless of depth.

Cons

• Doesn't take advantage of graphics hardware - thresholding performance may be poor.
• Managing the "extra" selection filters in the pipeline may be disruptive, and it may not be appropriate for them to be user-visible.

G Buffer

In the geometry-buffer approach, all cells are rendered off-screen with lighting and transparency disabled. The Z-buffer is enabled normally. For each cell, the cell ID is encoded as a color which is used to render the cell. A mask can be used to limit rendering to an "area-of-interest", i.e. a single pixel (picking), a rectangle (rubber-band) or an arbitrary shape (lasso). Once rendering is complete, the buffer will contain an image where each pixel contains the cell ID (color) of the closest cell. After reading the buffer contents for the area-of-interest, the colors are "decoded" back into cell IDs to form the set of selected cells.

Pros

• Memory requirements are constant, and bounded by screen size.
• Takes advantage of graphics hardware.
• Is capable of supporting all selection types.
• Easy implementation of rubber-band selection of a surface, instead of a volume.

Cons

• The number of cell IDs is limited by the depth of the off-screen buffer, possibly as-low-as (2^16)-1 cell IDs, with (2^32)-1 cell IDs more common, depending on hardware.
• Because the buffer can only "store" one ID per pixel, selections always contain only a visible surface, never a volume.

Implementation

Overview

The diagram below summarizes how we are thinking of implementing selection:

In summary:

1. The user inputs a selection. This can be a rubber band selection or a selection on the histogram. ParaView will try to keep the original selection. Where the selection generated by the GUI is not appropriate for the selection system, it will be converted
2. If enabled and applicable, the selection is applied to the list of (pickable) pipeline objects and the generated set of pipeline objects is converted to a server manager model selection. This selection is passed to the GUI and is usually displayed on the pipeline browser.
3. The selection list is applied to the geometry to generate visible, highlighted selection on all applicable views
4. The user can then ask for one of the following:
• Display information about selected cells. The selected cells are extracted, passed to pgraph, sent to client and information is displayed
• Display information about selected cells over time. The selected cells are extracted by pedigree id over time. The results are sent to the client (pgraph) and displayed
• Extract selection. A new dataset is extracting the selected cells. A new source is shown on the pipeline browser. This is a static source. It is no longer attached to the original input.

Selection Datastructure

The current selection datastructure is a tree of vtkDataObjects (vtkHierarchicalDataSet or vtkMultiBlockDataSet). Each data object contains one or more data arrays that contain a list of ids. Usually, each child of the root node corresponds to a selected data object. Information about which dataset/mapper that node belongs to will be attached to the information of the dataset. Similarly, each data array will contain information about which type of selection list they contain.