Integrating Interactive Selection

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 arrays of user-defined data which are equivalent to variables in ParaView. 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 in some areas - a typical 3D character model using subdivision surfaces or NURBS will number points and elements in the thousands to tens-of-thousands range.

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. Because selection is a critical part of the process, it has received a lot of attention. 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 - whether a filter creates a selection outright or modifies the selection in its outputs, the user should be able to manually "override" the selection without discarding it entirely, and with a minimum of effort.

Data Structures

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 (points, edges, polygons, etc). 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 list of records, where each record stores a hierarchical list of IDs for gprims that are contained within the set. See the k3d::selection namespace for details on this data, which is strongly-coupled to the OpenGL selection mechanism. A simple example:
  • Selection set containing a single point: [MESH 0 POLYHEDRON 0 FACE 201 POINT 1]
  • Selection set containing multiple points: [MESH 0 POLYHEDRON 1 FACE 10 POINT 1] [MESH 0 POLYHEDRON 1 FACE 10 POINT 2] ...
• A selection operation represents a change between two selection states. It encapsulates the change as a collection of three-element tuples, where each tuple contains a half-open range of IDs and the selection state to be applied to the range. The use of ranges makes it possible to represent "select all" and "deselect all" compactly. Ranges correspond to explicit changes in state, while gaps between ranges represent IDs that will not be changed. See the k3d::mesh_selection class for details. Some examples:
  • Select point 3, leaving all other points unchanged: [3, 4, 1]
  • Deselect point 3, leaving all other points unchanged: [3, 4, 0]
  • Select point 3 and deselect point 5, leaving all other points unchanged: [3, 4, 1], [5, 6, 0]
  • Select point 3, deselecting all other points: [0, 3, 0] [3, 4, 1], [4, MAX_INT, 0]
  • Select all: [0, MAX_INT, 1]
  • Deselect all: [0, MAX_INT, 0]

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.

Implementation

Because selection state passes through the pipeline like any other variable, it should be clear that selection filters can be created that modify or replace the selection state in the obvious way. The key question to ask is "where does interactive selection data reside, and how does it interact with filter-based selections?" In K-3D, interactive user selections are stored as selection operation structures in the individual filters and actors. In detail:

• Assume a simple pipeline that consists only of a source:

             Do Nothing
                |
PolyCube -> Actor/Mapper

• By default, the actor selection operation is set to "do nothing", so the input data (which is unselected by default) is rendered normally.
• The user picks a point by clicking the mouse in the render window. The render window returns a selection set containing a single point ID, which is converted into an "add" selection operation, one that explicitly ignores the selection state of all gprims, except for the single point which is explicitly selected.
• Key point: The selection operation is stored as a property of the actor:

            Select Point N
                |
PolyCube -> Actor/Mapper

• Within the actor, the selection operation is used to modify the selection state of the input data. When the input data is rendered, its appearance will reflect the modified selection state.

• If the user were to pick another point in the render window, a new selection operation would be generated and combined with the operation already stored in the actor. This would cause pipeline execution and a display update.

• Thus, the selection that is rendered is always the combination of the "upstream" selection state that moves through the pipeline, and the "interactive" selection that is stored in the actor.

Most filters are "selection-aware", meaning that they refer to the selection state of individual gprims and alter their operation accordingly. Selection-aware filters by-definition have a selection operation ivar, just like the actor. When a selection-aware filter is inserted into the pipeline, the "current" interactive selection (the one that is stored in the actor) is copied to the new filter's selection property, and the actor's selection property is reset to "do nothing":

          Select Point N   Do Nothing
                |              |
PolyCube -> ScalePoints -> Actor/Mapper

When the selection aware filter executes, it applies the contents of its selection operator to its input, then uses the modified selection state to perform its calculations. Depending on the nature of the filter, the modified input selection might be passed downstream unchanged, or might be modified as a convenience to the user. A typical example would be a filter that creates new gprims, altering the output selection state so that the new gprims are selected by default.

Storing selection operation data in individual filters increases the burden slightly on filter authors, since they have to explicitly apply the operation to the incoming data before processing it - one might imagine having a standalone "Selection" filter whose sole purpose would be to act as a container for selection operation data, and in fact early designs worked just that way. After gaining some experience, selections were moved into individual filters to give filter authors the flexibility to specify explicitly whether their filter is selection-aware or not. It is also possible for a filter to have more than one selection operation as an input. An example is the super-experimental QuadrilateralRemeshing filter, which takes two selections as input: the user designates one point as a "starting point" for the algorithm, then specifies one-to-many "end points". Using per-filter storage allows the filter author direct access to the selection data so that they can interpret it in their own way if needed.

K-3D provides automatic serialization and undo/redo for properties, so storing selection as a property has the beneficial side-effects of making it serializable and undo/redo enabled.

Samples

Some sample selection filters:

• GrowSelection
• SelectEdgeLoops
• SelectEdgeRings

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

• SubdivideEdges
• ConnectVertices