Hierarchical B-Splines

Overview

For my project I implemented a Hierarchical B-Spline editor as outlined in the SIGGRAPH paper "Hierarchical B-Spline Refinement" by Forsey and Bartels.
The intention of the paper is to introduce a method of editing a B-spline suface while only affecting a local area of the surface. Under normal conditions, moving a control point in a B-spline control mesh affects a large area of the surface. However, by using overlays (which are hierarchically controlled subdivisions) Forsey and Bartels are able to gain finer control over the spline surface

The Initial Surface

The project was coded in C (openGL) and uses a Tcl/TK interface. When the editor is started, an initial surface is loaded from file into the program.

The initial surface consists of 4x4, 8x8, or 12x12 control points (depending on the file loaded) where each point is uniformly spaced and lies on a plane.

The surface is rendered in patches as a bi-cubic B-spline surface using the gluNurbs function provided in OpenGl. Each patch consists of 16 control points (a 4x4 section).

A 25 patch Surface with 8x8 (64) Control Points

Surface Editing

In order to edit the surface, the control points may be clicked and dragged using the left mouse button while in manipulation mode.

While using edit points on the surface (instead of control points) would have made for a more user friendly interface, time did not permit me to implement this feature.

Moving a control point affects the surface

Adding an Overlay

In order to add an overlay into the control mesh we must first switch the system into overlay mode. The system then displays the control mesh in a wireframe view.	The initial 8x8 control mesh in Overlay Mode
We select the area where the overlay is to be added by clicking a control point.	The red area indicates where the overlay will be inserted
We insert the overlay by pressing the "i" button. Note: Since I used overlays consisting of 7x7 control points, only the center overlay control point may be moved during editing. (Moving any another overlay point would result in a tearing of the surface)	The overlay has been inserted

Local Refinement

As we add overlays on top of each other, the degree of locality in our editing process increases.

In this image no overlays have been used and a single control point has been moved up and away from the plane to create a mound in the surface. We can see that moving this single control point affects a large area of the surface.	Moving 1 control point affects a large area
In this image a single overlays has been added and a single control point has again been moved up and away from the plane to create a mound in the surface. We can see that moving this single control point affects a smaller area of the surface.	Moving 1 control point affects a smaller area
In this image a 2nd overlay has been added over the initial overlay and a single control point has again been moved up and away from the plane to create a mound in the surface. We can see that moving this single control point affects an even smaller area of the surface.	Moving 1 control point affects a very small area

Offset Rendering

Since the overlays are really hierarchical subdivisions, when a control point above an overlay is moved it will affect the location of all the overlay points. (and affect the shape of the surface)

In order to facilitate this feature, the overlay control points are stored in a two part fashion. When an overlay is created, the coordinates resulting from the subdivision are stored along with an offset which is set to 0. When an overlay point is moved, the movement is stored as the new offset.

Then later when a control point above the overlay is moved, the subdivision is recalculated and stored without affecting the offset.

In this image the inital mesh has had 2 overlays added to it and some of the overlay control points have been moved resulting in a new surface.	An edited patch with 2 overlays
In this image we see the same mesh with same 2 overlays but some of the base control points have been moved to illustrate the offset rendering. (Note: None of the overlay control points were moved to make this image.	The edited patch after moving some base control points

References

D. Forsey and R. Bartels, Hierarchical B-Spline Refinement. Proceedings of SIGGRAPH '88, p.205.
D. Forsey, Motion Control and Surface Modeling of Articulated Figures in Computer Animation. Doctoral Thesis presented to the University of Waterloo, 1990.
CS 679 Course Notes.

Special Thanks

Patrick Gilhuly - For allowing me to continue to work on my project even after I crashed Leucas 3 times in one afternoon.
Selina Siu - For pointing out that I was using a different size field of view in my picking code than in my drawing code.