# Compression using Hierarchical B-splines

The storage savings of the hierarchical form in the surfaces described is considerable: up to two orders of magnitude over an equivalent Bezier surface representation.

## Traditional B-spline and Bezier surfaces

Plate 1 below, shows the worst case scenario for a B-spline surface. Each of the diagonal bumps causes the creation of a maximal number of spurious patches.

Plate 2 shows the patches used in a hierarchical representation of the same surface. The cost of an equivalent B-spline surface is calculated by enumerating the knot lines introduced by local refinement, extending them to the boundaries of the surface, and counting the resulting control vertices. In a traditional tensor-product spline, which shall be referred to as a flat spline representation, these knots would extend to the surface boundaries, producing a tensor-product surface defined by 1225 control vertices. The hierarchical version uses 24.

Thus, a traditional tensor-product, bi-cubic B-spline surface defining the surface in Plate 3 uses approximately 29000 control vertices. Counting the root-level surface, and those control nodes with non-zero offsets, the hierarchical form uses only 790 data points to fully represent the same surface.

Refinement using the hierarchical form requires storage proportional to the number of edited control nodes, because only the non-zero offsets are required to define the surface.

The economical representation of the hierarchical form even improves upon the representation produced by using one polygon per spline patch (i.e. 4012 polygons in Plate 3 above). If the vertices of the polygons are arranged as a rectangular mesh, the ordering of the polygon vertices is implicit. Twelve bytes (3 floating point numbers) are needed for the position of each vertex. Thus, 48144 bytes of data (4012x12bytes) are required to store all the information needed to describe the surface in Plate 3. This is a lower bound since few polygonal models are arranged in a regular rectangular mesh and, consequently, require more information to describe the ordering of the vertices.

Storage for the hierarchical form requires two short integers (4 bytes) for the indices of each non-zero offset and three floating point numbers for the coordinate values of the offset (12 bytes) - a total of 16 bytes. (This estimate is not a lower bound since non-zero offsets tend to group together allowing the positioning of a larger number of offsets within a single rectangular parametric range. This grouping would reduce the per-node storage cost while incurring a number of additional zero entries within the region.) Four bytes per level of overlay record the level number and the number of offsets per level, giving a total of 12676 bytes ((790x16)+(9x4)) - about 26% of the cost of the polygonal database.

The surface for the dragon in Plate 4 requires about 20,000 control vertices - the hierarchical form has only 505 non-zero offsets in 7 levels. 8104 bytes are required for storage as compared with 37056 bytes for 3088 polygons.

Furthermore, the hierarchical representation is, in this case, more economical than the equivalent Bezier surface. The lower bound on the number of control vertices required to represent N^2 bicubic Bezier patches is 9N^2. For the dragon head N is 50, giving a lower bound of 27225 control vertices - 53 times the number required for the minimum hierarchical representation.

The estimated storage cost for the head in Plate 4 is slightly higher than the minimum required for a simple static representation because the figure is fully articulated, able to move not only the head, neck and jaw, but also nostrils, ear flaps and eyebrows. This model has been used successfully in a short animation shown in the Electronic Theatre during SIGGRAPH'90.

You can download a copy of the file defining this surface (11208bytes compressed). This contains the definition for the entire animated figure: the skeleton definition, plus the surface which moves as the skeleton moves.

Here are a few more sample surfaces using in the table below.

The table below compares the storage cost of the hierarchical form for the surfaces shown in the colour images above. The storage estimates are calculated as above, and the estimates for the traditional bi-cubic B-spline, the polygonal and the Bezier representations are lower bounds.

```+-----------------------------------------------------------+
|Cost Comparison of Various Surface Representations         |
+-------+------+--------------------+--------+------+-------+
|       |Num-  |    Hierarchical    |        |      |       |
| Plate |ber   |  Bicubic B-spline  |Flat    |      |       |
|       |of    +--------+-----------+Bicubic |Poly- |Bicubic|
|       |Patch-| Minimal|   Fast    |B-Spline|gons  |Bezier |
|       |es    |        |           |        |      |       |
+-------+------+--------+-----------+--------+------+-------+
|   1   | 256  |   24   |    773    |  1225  |  256 |  2304 |
|   3   |4012  |  790   |   9713    | 29718  | 4012 | 36108 |
|   4   |3088  |  505   |   7484    | 21168  | 3088 | 27792 |
|   5   |2164  |  178   |   6168    | 16524  | 2164 | 19476 |
|   6   | 216  |  177   |    413    |   400  |  216 |  1944 |
|   7   | 876  |  315   |   1569    |   853  |  876 |  7883 |
+-------+------+--------+-----------+-----------------------+
```

Storage cost comparison using number of control vertices

```+-------------------------------------------------------+
|Cost Comparison of Various Surface Representations     |
+------+------+-----------------+-------+-----+---------+
|      |Num-  |   Hierarchical  |       |     |         |
| Plate|ber   | Bicubic B-spline|Flat   |     |Composite|
|      |of    +---------+-------+Bicubic|Poly-|Bicubic  |
|      |Patch-| Minimal | Fast  |Spline |gons |Bezier   |
|      |es    |         |       |       |     |         |
+------+------+---------+-------+-------+-----+---------+
|   1  |  256 |    404  | 12388 |  14700| 3072|  27648  |
|   3  | 4012 |  12676  |155450 | 356616|48144| 433296  |
|   4  | 3088 |   8108  |119772 | 254016|37056| 333504  |
|   5  | 2164 |   2900  | 98732 | 198288|25968| 233712  |
|   6  |  216 |   2832  |  6608 |   4800| 2592|  23328  |
|   7  |  876 |   5040  | 25104 |  10236|10512|  94607  |
+------+------+---------+---------------+---------------+
```

Storage cost comparison using byte count. The cost per control vertex is 16 bytes for the hierarchical formulation and 12 bytes for all the others.

Last updated by David Forsey on 1 Feb. 95.