When working with Ink a useful property of a stroke is the ability to know where the stroke may have intersected with itself. Ink strokes are represented internally as a simple array of N discrete points. Calculating self-intersection points, in a naïve manner, would lead to intersecting N-1 line segments with each other. This leads to a runtime of O(N²). Intersecting two line segments involves enough arithmetic that this runtime is unacceptable for real-time interaction. We are using Paul Bourke’s technique for the intersection of two line segments.

We are able to improve this runtime by utilizing spatial partitioning techniques. Spatial partitioning typically involves subdividing areas of space into a tree structure such that each node of the tree holds the data for a certain area of space. Finkel & Bentley’s Quadtrees (Bentley, 1974) are a classic example of spatial partitioning.

The following properties of our self-intersection problem influenced the design of our algorithm:

• The self-intersection routine will only be called once.
• The points in our space are linearly related as they represent a polyline.
• All points lie in a 2D plane.

Working from these properties our strategy is to use a 2D spatial partitioning scheme whose underlying tree is optimized for fast insertion at the cost of not guaranteeing balance or optimal spatial partitions. This is acceptable because we are performing N intersection tests and N insertions. If the number of intersection tests performed were orders of magnitude greater than the number of insertions, i.e. as one would expect in a ray tracer, this would not be an ideal strategy.

The self-intersection algorithm goes as follows:

• For each line segment:
  • Compute line segment L’s bounding box B.
  • Intersect B with tree.
    • If leaf nodes exist whose bounds intersect with B
      • If leaf node’s line segment and L intersect at point I
        • Store self-intersection point I
  • Insert new tree leaf containing L and B.
  • On traversal back to root node we compute intermediate nodes’ bounding boxes

Pseudo-code can be found in the following PDF: Self-Intersection Pseudo-Code

SurfPad is an exploration of Microsoft’s Silverlight technology with a special emphasis on Inking in the browser.  Details on the project itself will emerge as they formalize.  The premise is to prototype a rich, fluid searching experience driven primarily by a pen.  SurfPad is a project of the Microsoft Center for Research on Pen-Centric Computing at Brown University’s Computer Science Department being driven by Kris Jordan (me) as part of my Master’s Thesis.  This blog will follow the progress made along the course of my semester.