CURVE COMPRESSOR

Generally, the rendering of curves is done in two steps: (1) construction of an approximation of the curve to be rendered by a sequence of position vertices, and (2) drawing of a line-strip (lines connecting consecutive vertex-pairs) based on that sequence.

The naive way to generate a vertex sequence approximating an arbitrary curve is to sample it from beginning to end at regular intervals. However, this approach often generates many redundant vertices, that if were absent from the sequence would have made little to no difference in the way a human viewer perceives the shape of the curve.

In this project, we outline a method by which these vertices can be easily identified and discarded.

Table of contents

Introduction

In this project, we focus on parametric curves in particular, because they tend to be the most receptive towards our proposed optimization.

The most common type of parameteric curve is the one whose equation takes on a single parameter \(t\) from the domain \([0, 1]\). For example, if we are given the following curve:

$$ C(t): \mathbb{R} \rightarrow \mathbb{R}^2 $$

where \(t \in [0, 1]\), a vertex sequence \(A\) approximating \(C\) can be generated by simply sampling \(C\) at \(n \in \mathbb{N}\) regular intervals of a fixed length \(\ell\):

$$ \ell = 1 / n $$ $$ A := (C(0), C(\ell), C(2\ell), \ldots, C((n-1)\ell), C(1)) $$

Figure 1 illustrates this procedure:

Figure 1: A quadratic Bezier curve.
original shape
regularly sampled with \(\ell = 0.1\)

Approach

Our approach towards compressing the strip \(A\) is to try and find sub-sequences of vertices on \(A\) that are roughly collinear, and reduce those to a single pair of vertices approximating the segment.

For example: if in a section of \(A\) the sequence of consecutive vertices \(p\), \(q\), and \(r\) lie roughly on the same line, we may remove \(q\) from \(A\) and it will maintain its general shape (albeit not to the same degree of precision).

We identify the rough collinearity of three such points by comparing the measured angle \(\alpha = \measuredangle pqr\) with a user-chosen tolerance parameter \(\theta \in [0, 1]\). When \(|\alpha| < \theta\pi\), we consider the line-strip generated by \((p, q, r)\) to be visually indistinguishable from the one generated by \((p, r)\).

In figure 2 we illustrate the algorithm's performance on a high-order Bezier curve and with varying value choices for \(\theta\):

Figure 2: Compression on a 7th-order Bezier curve.
original curve,
regularly sampled with \(\ell = 0.001\)
compressed with \(\theta = \)
compression-rate: %
compressed with \(\theta = \)
compression-rate: %
compressed with \(\theta = \)
compression-rate: %
compressed with \(\theta = \)
compression-rate: %
compressed with \(\theta = \)
compression-rate: %
compressed with \(\theta = \)
compression-rate: %

Source code

You can view the source code and documentation of the library on GitHub.

See also