Selection Implementation in VTK and ParaView III
Overview
We have added support for selecting an arbitrary list of points or cells as well as the capability of performing rubber band selection to VTK. Traditionally, VTK's only selection mechanism has been single cell or prop selection through picking. This new feature allows creation of selections consisting of an arbitrarily complex list of cell or points. Furthermore, it allows developers to support rubber band selection with the mouse. The result of the selection is a collection of cell or point ids corresponding to what is included in the rubber band area. This selection can then be applied to the original dataset to perform an extraction for further analysis.
Three different algorithms have been implemented. The AreaPicker allows selection of objects at the vtkProp level. The selection is made using software bounding box tests with an additional optional pass in rendering hardware (aka OpenGL selection). The next two selection algorithms select primarily at the vtkCell level. The frustum extraction algorithm (aka Pure Geometry) allows the selection of 3D cells behind the selection rectangle. The color buffer selection algorithm (aka G Buffer) allows the selection of only the front or visible 2D polygonal cells.
New classes added to VTK
vtkSelection - vtkSelection is a tree data structure storing selection results. Each node of the tree contains a vtkDataArray that can be used to store an id list, an id range, attribute values etc. Furthermore, it is possible to attach arbitrary meta-data with each node using a vtkInformation object. Commonly used meta-data items are CONTENT_TYPE (for example POINT_IDS, POINT_ID_RANGE, CELL_IDS etc.), SOURCE (a pointer to the dataset the selection came from) and PROP (a pointer to the 3D scene prop that selection came from)
vtkInteractorStyleRubberBandPick - This new interactor style draws a selection rectangle on the screen. It acts like the TrackballCamera interactor style, until the 'r' key is pressed. Once this happens, and until 'r' is pressed again, it creates a rubber band with each left button drag operation. On each drag release, it passes the screen start and end positions to a vtkPicker. The pre-existing vtkPicker classes get only the center of the selection area to maintain backward compatibility.
vtkAreaPicker - This new vtkPicker class takes a screen rectangle and does a software bounding box intersection test with the pickable vtkProps in the scene. Internally the vtkAreaPicker uses the new vtkFrustumExtractor test to do a fast intersection test on each vtkProp's boundaries.
vtkRenderedAreaPicker - This is a child of the vtkAreaPicker class. It is more selective than its parent because in addition to the bounding box test above it also determines if the vtkProp has some visible contents within the selection area. vtkRenderedAreaPicker, like vtkPropPicker does uses OpenGL's GL_SELECT mode, aka hardware picking.
vtkFrustumExtractor - This vtkDataSetAlgorithm runs a software frustum intersection algorithm to determine which cells of its input vtkDataSet lie within a frustum defined by a rectangular region of the screen.
vtkFrustumExtractor contains two intersection algorithms, the first produces a conservative estimate of insidedness which can be incorrect with a thin selection area, the second algorithm is inclusive producing all cells that at least partially intersect the frustum. The ExactTest flag controls which is run. With ExactTest off, each point is simply evaluated against the six plane equations that define the frustum. Cells are inside if all of their points are inside. If the ExactTest flag is on, a fast cell frustum intersection algorithm is used instead (see Ned Greene, Graphics Gems IV, 1994, p 74-82). The algorithm can quickly accept or reject most cells by testing only the two points that are nearest to and farthest from each of the six plane equations. Only those few cells that are neither trivially accepted nor rejected are then run though a full polygon clipping algorithm.
The PassThrough flag controls whether the output of the algorithm is a shallow copy of the input vtkDataSet with two new "vtkInsidedness" field data arrays, or is an entirely new vtkUnstructuredGrid output that contains only the inside cells and points.
vtkVisibleCellSelector - Rather than operating in world space, this class operates in screen space using the rendering hardware. This class operates by putting vtkRenderer into new selection modes and telling it to render. When the render happens, each visible cell or data set is rendered with the color of each cell chosen to encode a unique identifier. After one or more selection render passes, the contents of the color buffer are read back, and each pixel is examined to identify which cell was frontmost in the scene behind it. Because color buffer resolution in VTK is limited to 24 bits, up to five passes may be required to obtain a complete result. Up to three passes are used to find the visible cells within the rendered datasets. One pass selects between actors, and another pass is used in parallel composite rendering to determine which processor is responsible for each visible cell.
vtkIdentColoredPainter - This class is a new vtkPainter that the vtkRender uses to render each cell in the color coded mode. This Painter temporarily turns off lighting and shading and sets the background to black to do its job. In selection mode, vtkRendered tries to swap in a vtkIdentColoredPainter for each prop. If the Prop is not rendering polygons or is not pickable, the prop is ignored (not drawn.)
vtkExtractSelection and vtkPolyDataExtractSelection - Given a single-node vtkSelection, extracts all cells in the selection list. vtkExtractSelection works on all vtkDataSets and generates a vtkUnstructuredGrid, whereas vtkPolyDataExtractSelection works only on vtkPolyData and generates a vtkPolyData.
Comparison of vtkFrustumExtractor and vtkVisibleCellSelector
vtkFrustumExtractor.
Advantages:
- Exactness - no cell that partially covers the selection area can be missed.
- Ability to pick through the front layer of cells.
- Data type insensitive - can operate on and produce and vtkDataSet type.
Disadvantages:
- Slow: it must iterate over (at least) every cell and examine it in the CPU.
- Can not pick only the front layer of cells.
vtkVisibleCellSelector.
Advantages:
- Fast - uses the rendering hardware. Selection time is roughly 1 to 5x render time.
- Picks front layer of polygons only.
Disadvantages:
- Will omit cells when sub pixel sized polygons are drawn.
- Like compositing it will not work properly when GPU antialising is on.
- Limited to operating on opaque polygonal data only.
- Can not pick cells behind the front shell.
The last two disadvantages are mitigated by the new passthrough feature of vtkDataSetSurfaceFilter and its kin. This preserves the input cell id of all of cells that produce surface polygons in the output. Using this feature, one can recover the front layer of any cell type that constitutes a dataset.
Test case and example
The new VTK level ctest located at VTK/Rendering/Testing/Cxx/TestAreaSelections.cxx demonstrates the use of both the vtkFrustumExtractor and the vtkVisibleCellSelector. In the test two datasets are drawn, one a vtkStructuredGrid, the other a vtkPolyData. When a rubber band selection happens, the portions of the two datasets that lie behind the screen rectangle are extracted and reproduced offset to the right (+X) of the original input datasets.
New classes added to ParaView server
vtkPVSelectionInformation - This sub-class of vtkPVInformation is used to gather selections generated in parallel and deliver the result to the client.
vtkSelectionConverter - This class is used to convert from one selection type to another. For example, it can convert a selection made on the rendered geometry (output of vtkPVGeometryFilter), to a selection on the source of that geometry (input of vtkPVGeometryFilter). This is done by using the vtkOriginalCellIds array generated by the geometry filter. vtkOriginalCellIds is a pedigree id that stores the id of the cell each geometry cell originated from.
vtkSelectionSerializer - This class serializes/unserializes to/from XML vtkSelection. It is usally used to transfer vtkSelection over network (by vtkPVSelectionInformation for example) but it can also be used to store a selection in a file or to print it.
vtkMultiBlockExtractSelection - Given a vtkSelection, extracts cells. This class is a vtkMultiBlockDataSet source. It uses the SOURCE_ID key in the selection properties to get a pointer of the dataset. SOURCE_ID is the client/server streams id assigned during selection mechanism. It applies vtkExtractSelection to each selection node.
vtkExtractBlockFromSelection - Given a SOURCE_ID, extracts it's selected dataset from the output of vtkMultiBlockExtractSelection. It does this by checking the SOURCE_ID key in the Information of the output assigned by vtkMultiBlockExtractSelection. This can be used whenever a multi-block dataset is not convenient (for example when delivering the selection result to the client).
vtkVolumeSelector - This class is a wrapper around vtkFrustrumExtractor. It applies vtkFrustrumExtractor to a list of vtkDataSets (it also stores pointers to associated vtkProps). It then converts the output (vtkInsidedness array) of vtkFrustrumExtractor to a vtkSelection. It also adds the client/server streams id of the selection source to the selection as SOURCE_ID.
vtkPVVisibileCellSelector - Equivalent of vtkVolumeSelector for surface selection (G Buffer). This is a sub-class of vtkVisibleSelector that is capable of generating a vtkSelection containing cells ids (implemented in superclass) as client/server ids for the sources. This class is used by vtkSMRenderModuleProxy to implement vtkSMRenderModuleProxy::SelectVisibleCells
New classes added to ParaView III client
pqSelectionManager - pqSelectionManager is responsible of bringing all of the above classes to support selection on the client. The first time rubber band/pick selection is enabled, it initializes it's internal data structures and creates appropriate selection, extraction and delivery objects on the client and server. Once the selection is done, it either performs a surface selection (vtkPVVisibleCellSelector) or frustrum selection (vtkVolumeSelector). It then redistributes the resuting vtkSelection to the appropriate server/nodes and extracts from datasets using it. The result is passed through a display and rendered on the viewport.
