Sketchy

Sketchy is a simple drawing program that draws strokes in response to mouse or touch events. As each new input event is processed, a path is fit to the input, and used to generate a triangle mesh for the stroke. The wobbly stroke outlines are animated by a vertex shader.

Stroke fitting

The path of a stroke is represented by a sequence of cubic Bezier curves. The stroke-fitting algorithm begins by fitting a Bezier curve to the list of input points, and measuring the error of the resulting curve (i.e. how far the input points are from the approximating curve.

If the error metric is below a threshold, then the stroke path consists of a single cubic Bezier curve.

More commonly, a stroke cannot be adequately represented by a single Bezier curve, and so the procedure above is modified slightly so that it can be applied recursively: instead of fitting a Bezier curve to the entire list, it is fit to a sub-list defined by a start and end index:

• The initial start and end indices use the entire list of input points.
• Recursively:
  • Fit a Bezier curve to the range indicated by the current start/end index
  • If the error of the curve is acceptable, return a list consisting of a single Bezier curve.
  • Otherwise, choose an index to split the input points, apply this procedure to the two input sub-lists, resulting in two lists of Bezier curves; return the concatenation of these two lists.

Mesh generation

A stroke is rendered by generating a triangle mesh from the Bezier path that was fit to the stroke's input points. This mesh can be reused to render multiple frames if the stroke has not changed since the last frame.

The mesh is generated by:

• For each Bezier segment in the path.
  • Compute a list of parameter values at which to evaluate the segment; the approach used is described below.
  • Evaluate the segment at these parameter values to obtain a list of 2D positions and normals for this segment.
  • Each position/normal pair is used to generate two mesh vertices. An offset vector is computed by multiplying the normal by a per-stroke width. The position of the first vertex is obtained by adding this offset to the evaluated Bezier position, and the position of the second vertex is obtained by subtracting the same offset instead of adding it. Thus, the outline of the stroke is offset from the central “spine” of the stroke.

In order to choose the parameter values at which to evaluate each Bezier segment, and arc-length reparameterization is first computed for the segment. This allows parameters to be chosen such that adjacent vertices are approximately equidistant.

The wobbly outlines of a Sketchy stroke are computed each frame in the vertex shader (discussed below). In addition to the vertex positions computed above, this shader requires other vertex attributes to be baked into the mesh. To support this, the mesh has the following attributes:

• MeshAttribute::kPosition2D
• MeshAttribute::kPositionOffset
• MeshAttribute::kPerimeterPos

Stroke rendering

The “wobbly outline” effect is hard-coded into Escher and is specified by adding a ModifierWobble to the Shape that encapsulates the stroke mesh. This is used to select the Vulkan pipeline object that is used to render the stroke (see escher/impl/model_pipeline_cache.cc), and to provide per-stroke parameters for that pipeline.

The effect is implemented by moving each vertex by some multiple of the vector specified by its kPositionOffset attribute. To compute this multiple, the vertex shader uses the ModiferWobble::SineParams associated with the stroke, as well as the kPerimeterPos attribute of the vertex.

Future Work

Stroke fitting

The stroke-fitting algorithm is applied naively; as each new input point arrives, the entire path is refit. This has two negative consequences:

• The amount of work required to fit the stroke grows linearly (or is it N-log(N)?) with the number of input points.
• When the error threshold is chosen to result in a smoother path, the path “jitters around” as the stroke is extended, since there are many possible paths that satisfy the error threshold.

The obvious solution is to not refit the entire list of input points, but instead to reuse some of the Bezier segments that were computed the last time that the stroke was extended. When the stroke is next extended, the recursive stroke-fitting procedure is initiated with a start-index that skips input points corresponding to the reused Bezier segments.

Use compute shader for stroke tessellation

Stroke vertices are currently generated on the CPU. An alternative would be to generate them on the GPU, as seen in strokeBezierTesslate() in https://github.com/schwa423/Sketchy/blob/qi/qi/pen/port_ios/pen.metal.

Mozart integration

sketchy_demo is currently a standalone application that renders strokes directly into a framebuffer, including shadows cast by each stroke. This is undesirable; Mozart clients should not directly render their own shadows due to “double-shadowing” artifacts when the Mozart SceneManager generates its own shadows based on the geometry of shapes in the global scene-graph.

Instead, Sketchy should provide meshes that are rendered by the SceneManager. This allows strokes to cast shadows onto other SceneManager geometry, and also to have shadows cast onto them. Depending on the elevations of each stroke, another SceneManager client might add a Shape that casts a shadow on one stroke, and is shadowed by another!!

One obstacle is that the SceneManager will not expose ShapeModifier::kWobble as part of its public API (see mozart/services/scene/*); it not generally useful to non-Sketchy clients.

Sketchy can overcome this obstacle by using the GPU to generate new vertices each frame. The SceneManager supports this use-case via the Buffer and MeshShape resources (see resources.fidl and shapes.fidl). This could be done by using the vertex shader to write new vertices into an output buffer instead of passing them along to the rasterizer, or even by completely re-tessellating the stroke each frame; the latter approach would allow the entire stroke path to be animated, not just the stroke outline.