Integrating Interactive Selection

Work in progress

Case History: K-3D

K-3D (http://www.k-3d.org) is an open-source artists' tool that has some striking similarities to ParaView - in particular, it is based on an implicit, demand-driven pipeline architecture where users make connections between sources, filters, and sinks to manipulate their data. Geometric data moves through the pipeline using a heterogeneous data structure which is roughly comparable to unstructured grids in ParaView. Geometric data can include arbitrary Of course, there are significant differences, too: K-3D isn't client-server, nor is it parallel. The bulk of the functionality revolves around interactive modelling (creation) of 3D datasets, rather than working with existing experimental or simulated data. Data tends to be orders of magnitude smaller - a typical 3D character model using subdivision surfaces or NURBS will number points and elements in the thousands to tens-of-thousands range, although this is offset in other areas - large bitmap textures play important roles in adding visual complexity.

Use Cases

Typically, users tend to go through an iterative process where they begin with a simple geometric source (cube, sphere, cylinder, etc) and add complexity through a set of select/modify/repeat operations. Some use cases:

• The user creates a cube. Nothing is selected. User interactively selects one face of the cube and applies a ExtrudeFaces filter, which extrudes the selected face, leaving the selection unchanged:

PolyCube -> ExtrudeFaces -> Actor/Mapper

• The user creates a cube. Nothing is selected. User interactively selects two points on a face diagonal and applies a ConnectVertices filter, which splits the face into two triangles. The selection is changed so that the newly-created edges are now selected:

PolyCube -> ConnectVertices -> Actor/Mapper

• The user creates a sphere. Nothing is selected. User applies a SelectCube filter, which selects all of the points that fall within a three-dimensional bounding box. The user then applies a TranslatePoints filter, which only modifies the positions of the selected points, leaving the selection unchanged:

PolySphere -> SelectCube -> TranslatePoints ->Actor/Mapper

• The user creates a cylinder. Nothing is selected. User interactively selects an edge on the cylinder, then applies a SelectEdgeRings filter, which expands the selection to include a "ring" of edges around the circumference of the cylinder. The user interactively deselects some of the selected edges and applies a ScalePoints filter, which only modifies the selected edges, leaving the selection unchanged:

PolyCylinder -> SelectEdgeRings -> ScalePoints -> Actor/Mapper

A key requirement in the above use cases is the ability to combine user interaction with filter-generated selection - if a filter changes the selection, the user can manually "override" the selection without discarding it entirely.

Implementation

K-3D makes an explicit distinction between selection state, selection set, and selection operation structures:

• A selection state is the actual state (selected versus not selected) of a collection of gprims. The state is stored in arrays that are part of the geometric data set, and thus move through the pipeline like any other variable. At the end of the pipeline, the selection state is used by mappers to change how gprims are rendered based on their state (i.e. highlighting selected gprims).
• A selection set represents a set membership where gprims (points, edges, polygons, etc) are either inside or outside the set. The selection set stores a hierarchical list of IDs for gprims that are contained within the set.
• A selection operation represents a change between two selection states. It encapsulates the change as a set of explicit modifications to ranges of IDs - for example "select IDs 10 - 20", "deselect IDs 103 - 243", etc. Using lists of ranges makes it possible to represent "select all" and "deselect all" compactly as a single range, instead of the set of all IDs. "Gaps" between ranges represent IDs that will not be modified.

The three types of selection data are used for different parts of the overall selection process:

• When the user performs an interative selection (picking, drawing a rubber-band, etc) in a 3D render window, the render window returns a selection set containing the gprims that were under the mouse pointer, inside the rubber-band, etc.
• The user interface layer converts the selection set into a selection operation, based on any selection policies that happen to be in-effect. Based on keyboard modifiers or other UI controls, the selection set might become a "replace", "add" or "subtract" selection operation.
• The selection operation is stored as a property of a filter, where it is used to modify the selection state of the data moving through the pipeline.

Most filters are "selection aware", meaning that they refer to the selection state of individual gprims and alter their operation accordingly. Filters may also modify the selection state as it passes through the pipeline: broadly speaking, some filters are selection filters, whose sole purpose is to alter / replace the selection state, while other filters modify the selection as a convenient side-effect of their true purpose.

Some sample selection filters:

• GrowSelection
• SelectEdgeLoops
• SelectEdgeRings

Some filters that alter the selection as a side-effect:

• SubdivideEdges
• ConnectVertices