Chapter 8: Kinetic Data Structures

Overview

In the previous chapters, we discussed hierarchical geometric data structures that are mainly of a static nature. However, in computer graphics (and many other fields), objects move constantly. So, how can we design data structures that allow efficient updating in the presence of an input set, the location of which in space changes continuously?

We can make two observations that help with designing such data structures:

  • When an object (i.e., a line, a point, a polygon, etc.) moves by just image from book , then a conventional, static data structure usually remains valid;

  • If an object moves farther than some image from book and the data structure has to be updated, then this update is (usually) local, i.e., the data structures over the old configuration and over the new one, respectively, differ only by a small amount.

From these observations arise the following questions.

  • How can we determine when the data structure has to be updated?

  • How can we update it efficiently ?

Both of these questions must be answered with less effort than just rebuilding the static data structure every time an object has moved and a query occurs.

The solution is a very generic algorithm technique called kinetic data structure (KDS). It makes a few fairly mild assumptions about the objects it can deal with:

  • All objects (points, lines, line segments, polygons, etc.) follow a known (often called published ) flight path ;

  • The flight path is an algebraic function in t (i.e., it is a function containing only the four basic operators plus square root; the reason for this is that we want to exclude flight paths that can go back and forth arbitrarily often within a time period image from book );

  • Flight paths can be changed at discrete times, i.e., they must not change arbitrarily often. Usually, the application wants to change the flight path, if, for instance, two objects collide. As you will see in this chapter, such a change incurs additional work.

The main loop for virtually all KDSs looks basically as shown in Algorithm 8.1.

Algorithm 8.1: Basic main loop of most kinetic data structures.
image from book
 initialize DS (often like static algorithm) initialize certificates compute failure time of all certificates init priority queue over failure times  loop  retrieve earliest certificate from queue           update KDS (if its an external event, then this will result in a new attribute)           compute new certificates and/or remove some           compute failure time of new certificates           update queue  end loop  
image from book
 


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