8.4. Kinetic BSP in the Plane

8.4. Kinetic BSP in the Plane

We can now proceed to tackle our goal of designing a kinetic BSP. Here, we will restrict our discussion to the 2D case as presented in [de Berg et al. 01], but there are similar variants for the 3D case [Agarwal et al. 97, Agarwal et al. 98, Comba 99].

We are given a set S of moving segments in the plane, which we want to restrict further in that they never intersect each other. Let us first introduce some notation:

  • Let ( ) denote the region of node in the plane;

  • Let S ( ) := S ˆ ( ) be the set of fragments that must be stored in the subtree rooted at ;

  • We call a segment s long ( with respect to ) iff it intersects both the left and the right border of ( ), or iff the endpoints lie on these borders (you will see in a minute that ( ) does indeed have such borders);

  • The rank of an endpoint is just the rank of its x -coordinate;

  • Let x l ( ) , x r ( ) denote the smallest and largest, respectively, ranks of all endpoints in S ( ) (relative to all other x -coordinates!).

Now, we will describe the construction of the (static) BSP. Basically, this amounts to consider three cases:

  1. S ( ) = ˜: is a leaf;

  2. S ( ) does not contain long segments: split the set of fragments by a vertical splitting line image from book ; such a node is called a vertical node . The line x mid will pass through an endpoint, but not necessarily one of S ( ). In fact, it could happen that all fragments in S ( ) are completely to one side of x mid ; such a node can cause fragmentation;

  3. S ( ) contains l long segments: we can sort these from bottom to top, since there are no intersections. They will be used as splitting lines. We create a multi-way node with l + 1 children, each of which corresponds to a region between two consecutive long segments. Each child gets those fragments assigned that are within such a region. Another name for such a node is a horizontal node ; it does not cause fragmentation.

By construction, the regions have four borders: two vertical (parallel) ones on the left and right side, and two more or less horizontal ones at the top and bottom. This is called a trapezoid . [2] See Figure 8.3 for an illustration of how such a BSP looks.

image from book
Figure 8.3: An example of a kinetic BSP tree. On the left, four segments are shown, together with the vertical splitting lines. At the top of each vertical line is its ID, which happens to also be the endpoints rank in the situation shown. On the right is the corresponding BSP tree; round nodes are vertical splitting nodes, while square nodes are multi-way (i.e., horizontal) nodes. Leaves are small grey nodes.

Before proceeding, we would like to point out the following properties of this tree:

  • The tree without the multi-way nodes can be considered a segment tree over the x -coordinates of all endpoints;

  • The parent of a multi-way node is always a vertical node;

  • Any region ( ) has at most two neighbor regions adjacent to its left side and to its right side, respectively, and one above and below, respectively;

  • As soon as a segment cannot cause fragmentation within a region (because it has become a long segment with respect to that region), it will be used as a splitting line.

In order to obtain a KDS, we must throw in a few more ingredients , most of which we already used for the kinetic segment tree:

  • array R [1 , , 2 n ] : image from book image from book , just as before,

  • a fragment list image from book , as before,

  • for each endpoint, a pointer to the neighbor region,

  • for each leaf, four pointers to the neighbor regions.

Since segments are not allowed to intersect, it is obvious that the combinatorial structure changes only when the x -coordinates of two endpoints swap ranks. This yields the certificates, which are exactly the same as for the kinetic segment tree.

For describing the algorithm, we assume that the rank of the right endpoint of segment s has incremented by 1. This is an event in which s has to augmented by one elementary fragment (EF). All other cases are analogous. The algorithm will proceed in two steps: update leaf and then reestablish the tree properties.

Step 1. Let i p = rank of endpoint p before the event (afterwards it is i p + 1). There are two cases.

In the first case, p is on the left border of the region ( ) of leaf before the event, and after the event it is somewhere in the interior (i.e., x r ( ) > i p + 1). In that case, we just replace by a little subtree, as shown in Figure 8.4.

image from book
Figure 8.4: This is the first case of leaf operations to be performed on a kinetic BSP when an event happens. The leaf is replaced by a small subtree. Its root is a vertical node with a splitting line through p (the endpoint that has swapped ranks with another endpoint).

The second case is when p is on the left border before the event, and on the right border after the event (i.e., x r ( ) = i p + 1). Again, we replace the leaf by something else, but now this depends on whether s parent is a vertical node or a multi-way (horizontal) node. In the first case, this distinction was not necessary because the root of the new subtree was a vertical node. See Figure 8.5 for the exact operations.

image from book
Figure 8.5: This is the second case of leaf operations when an event happens. Again, the leaf is replaced by a small subtree. However, here the exact operation depends on the type of parent node of . If the parent is a vertical node, then the new subtree is straightforward. If the parent is a multi-way (horizontal) node, then we must insert a new splitting line into that parent.

Step 2. After the leaf has been modified in Step 1, we obtain a new BSP that is valid and produces the new partitioning of the plane. However, it does not necessarily possess the properties outlined above. In particular, the horizontal split through segment s (either by a new node, or by an existing one) might have been performed higher up in the tree, if we had constructed the BSP from scratch. To restore this property, we push the new horizontal split up as far as possible. Note that it might end up in a multi-way node that already exists.

Let f = s ˆ ( ), where f' is the new EF, and is the new horizontal node. Let be the left sibling of (if any), and f = s ˆ ( ) (if any). Now, if is a horizontal node, too, and s is being stored there, too, then s is a long segment with respect to ( ) ˆ ( ). Therefore, the horizontal split with s could (and should) have been done higher up in the tree.

In that case, we perform the operation as depicted in Figure 8.6. If the parent of the new horizontal node



Geometric Data Structures for Computer Graphics2006
Geometric Data Structures for Computer Graphics2006
ISBN: N/A
EAN: N/A
Year: 2005
Pages: 69

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net