Hierarchical stream arrows

The stream arrows approach [51] is based on a regular tiling of texture space. This is not well-suited for stream surfaces that spread over regions of high divergence or convergence. The arrows become either too big or too small in certain areas. To eliminate this undesirable effect we present a hierarchical extension to the stream arrows technique.

   
A stack of stream arrows textures

The goal is to develop an algorithm, which is capable of generating stream arrows that are almost equal-sized in the rendered image. As we do not want to loose the ability to represent local divergence or convergence using the stream arrows technique, we decided to construct a hierarchical algorithm instead of a continuous solution. When flow diverges locally, the hierarchical stream arrows method switches discretely to the next detailed level of stream arrows. These stream arrows are smaller in texture space, but since they are used for divergent areas of the stream surface, they are finally almost equal-sized to all other stream arrows in the rendered image. Refer to Fig. 4.7 for an image which demonstrates this situation.

  

Figure 4.7: Hierarchical stream arrows, two examples. [left image] [right image]

The hierarchical stream arrows texture is specified by the shape of one tile, i.e., the outline of an arrow, and two vectors dc and dr (see Fig. 4.8) which define the offsets between adjacent columns and rows of arrows, respectively. Additionally there is a factor a which represents the scale relation between level i and i+1. If a=1/2 the size of stream arrows is doubled, when the algorithm switches to the next coarser level. Finally there is a vector o, which is the offset of the entire texture with respect to the origin of texture space. Offset vector o becomes important, when animation is applied. Due to this specification each stream arrow can be addressed by exactly one identity ID given by three numbers. ID ( $\mathit{level}$, $\mathit{col}$, $\mathit{row}$) identifies one stream arrow as a copy of the base tile, first translated by $\mathbf{o}+\mathit{col}\cdot\mathbf{dc}+\mathit{row}\cdot\mathbf{dr}$

  

Figure 4.8: Hierarchical stream arrows texture, i.e., a stack of stream arrows textures - specification parameters.

The separation algorithm

The hierarchical stream arrows technique is triangle oriented, because we produce the stream surfaces as triangular meshes: the front of the stream surface ($\approx$ time line) is advanced through phase space while the stream surface is integrated. Triangles are smaller in stream surface areas, where curvature is high, flat areas of stream surfaces are triangulated with larger triangles.

During the stream surface algorithm vertices are assigned 2D texture coordinates. One texture coordinate of each vertex (v coordinate) is set to the integration time of a stream line from the seed point to the vertex. The other texture coordinate of each vertex is set in such a way that all vertices connected with one stream line get the same texture value, i.e., the 1D seed parameter of the start-point of the stream line (u coordinate). See Fig. 4.5.

To apply the hierarchical stream arrows texture to the stream surface the hierarchical stream arrows algorithm processes the stream surface triangle by triangle and performs the following separation algorithm:

activeTiles = {}                  // . . .  IDs of active tiles
lockedTiles = {}                  // . . .  IDs of locked tiles
FOR ALL Triangles tri DO:
| level:=findLevelOfTriangle(tri) // get most appropriate level
| tiles:=getMaybeTiles(tri,level) // . .  get overlapping tiles
| FOR ALL Tiles tile IN tiles DO:
| | IF NOT (tile.active OR tile.locked) THEN:
| | | IF overlap(tile,activeTiles) THEN: tile.lock
| | | ELSE:                              tile.activate
| intersect(tri,activeTiles)      // . . . .  do the separation

The algorithm needs two data structures in addition to the triangular mesh of the stream surface: activeTiles stores the IDs of all tiles that actually are instanced within the stream surface, whereas in lockedTiles all IDs of tiles are stored that overlap at least one active tile and thus should not be generated. Both data structures need to be be searched as fast as possible (in overlap() and intersect()) and easy to extend by a new tile. Since tiles are related via their 2D location in texture space and searching is also performed in a `geographical' manner using texture coordinates (IDs), we use a linked data structure that closely represents the spatial relation between tiles.

The algorithm processes the stream surface triangle by triangle. For each triangle tri the corresponding level in the hierarchical stream arrows texture is determined by comparing the size of triangle tri in texture space to its size in phase space coordinates. This ratio is used to find the most appropriate level in the stack of stream arrows textures. Then all tiles in that level, which might intersect triangle tri are determined (getMaybeTiles()). Tiles which are already activated or locked are omitted. All remaining tiles are checked, whether they overlap any active tile (overlap()). Tiles that overlap at least one active tile are locked (added to lockedTiles), and all the others are activated (added to activeTiles). See Fig. 4.9 for an example with two triangles. After all tiles are checked triangle tri is intersected with all active tiles and separated into three sets: parts that belong to the arrows, parts that do not, and the separating outline. All three sets can be individually processed, e.g., assigned a certain level of semi-transparency, after the segmentation algorithm has finished.

  

Figure 4.9: Activating and locking tiles, example with two triangles.

The mechanism of activeTiles and lockedTiles ensures that neighboring triangles of a stream surface are consistently covered by entire tiles of the hierarchical stream arrows texture. If the tile instanced for the currently processed triangle is overlapped by a tile which was already instanced for a previously processed and nearby triangle--this tile is active and of different level than the current tile--the active tile is used for the current triangle. This ensures consistency. The current tile which overlaps the active tile is furthermore locked.

mailto:helwig@cg.tuwien.ac.at.