CS 779, Winter 2020 Project: T-Splines

Overview

This project is an implementation of T-spline. T-spline was originally introduced in 2003 by Sederberg et.al as a generalization of the widely used NURBS surface. [1] Unlike traditional tensor-product surfaces such as B-splines and NURBS, T-spline allows the existence of a “T-junction”, allowing for more a flexible and efficient representation of models. The vertices of a T-spline surface are managed by a common structure called T-mesh (See Fig. 1 from [2]).

A T-spline surface can be expressed by the following formula. Note that here I use the weighted variant presented in [2].

Features

The base project implements the following features:

Basic T-spline structure with common parametric coordinate system
T-spline evaluation and tessellation
Display T-spline surface
Edit vertices and knot vectors via file
Save and load models from file

Serveral improvements have been made and the following features are added:

Rewrite T-spline data structure using half-edges and local surfaces

Each vertex now has its own local parametric coordinate system. This is meant to provide better support for unstructured T-spline with extraordinary points, which is attempted but not finished.
Algorithms to traverse half-edge while maintaining local coordinate system
Local knot vectors are inferred, not specified
Support more topology than planes (pipe, doughnut, …)
Face-based evaluation of T-spline surface
A new WebGL based editor that supports mouse and keyboard controls
- Rotate, move, and zoom camera using mouse controls
- Click to select and modify vertices/edges

Implementation

The final impelmentation of T-spline is largely based on Sederberg et.al’s original paper on T-splines [1] and a recent paper that addresses unstructured T-splines [2]. The proposed data structure to implement T-splines in [2] ultilizes the concept of half edges.

Each edge in the T-spline model consists of at most two directional half edges, pointing in opposite directions. Each half edge belongs to a surface. Here I adopt the convention that all the half edges on a surface go in counter-clockwise direction. A random half edge on the surface is then selected to be the “direction” of the surface, marking its local knot coordinate system. Similarly, for each vertex, a half edge is set to determine the local knot coordinate system of the vertex. In the example below, the yellow half edge “HE” is the direction of the face, and determins the local knot coordinate system for the surface.

To obtain a particular vertex’s knot vectors with respect to a (possibly different) local knot coordinate system, one simply needs to traverse the directional graph formed by the vertices and half edges. This, however, is easier said than done in the case of T-spline due to the large number of configurations and edge cases. In fact, in this project, most of the time is spent on debugging algorithms and improving robustness.

Finally, the T-spline surface is evaluated face by face. First, all the vertices that have an influence on the face (support of the face) are selected followed by a change of coordinate operation to determine their knot vectors in the face’s local coordinate system. Then for each face, the surface is evaluated and tessellated.

This construction is very flexible and agnostic to changes in knot coordinates. Furthermore, it makes implementing closed surface much easier. An example is shown below:

It does, however, introduces both time and structural complexity. Traversing the graph often involves breadth-first search where visited vertices/edges need to be marked, and changes in the directions of local coordinate systems need to be stored and updated along the way. Debugging and maintaining such a complex data structure is quite a challenge.

WebGL Editor

To display and modify T-spline surfaces, I created a WebGL-based viewer (cgse.js). It currently supports the following basic functionalities

camera movement (rotation, displacement, zoom, etc.),
surface display in multiple modes (control polygon, surface, triangulation, boundary),
vertex selection using mouse and keyboard shortcuts,
vertex/edge/surface manipulation (set x/y/z/w/k, move, scale, rotate) using keyboard shortcuts.

To try out the editor, click here

Note

Phong shader adapted from Prof. Alec Jacobson’s demo
Mouse selection adapted from this tutorial

Limitations and Future Work

Evaluating the surface face by face naively might result in small but visible gaps between the faces. This is because the faces around a T-junction have different sizes in parametric space and therefore the tessellated triangles along the boundaries might not align properly.
Although partially implemented, surface splitting and subdivision via the WebGL editor is still very buggy and thus is disabled and not mentioned above. I have determined the bug is due to an error in graph traversal (BFS) which cause the algorithm to go into an infinite loop. This is not relevant to T-spline surface construction and has little impact on this project but fixing it would allow better modeling experience.
The incentive of implementing T-splines using the approach in [2] is to add support for extraordinary points and thus allowing operations like surface extrusion that are commonly seen in modeling softwares. This feature is never realized as I was overwhelmed with bugs and edge cases.
As I was not aware that half edge is a standard data structure in computer graphics when developing this project, a lot of the half-edge-related algorithms were constructed from scratch and thus are verly like buggy and inefficient.
In the current implementation, to manipulate a knot interval, one needs to select the corresponding edge in control polygon. A separate knot editor that displays it in a planar fashion would be easier and clearer. This however can be tricky when the T-spline surface is unstructured and has many extraordinary points, which may lead to a non-planar graph.

What I Learned

Half edge (doubly connected edge list) is a flexible and common tool that people use to model mesh.
The algorithms related to half edge data structure.
The basics of T-spline such as local knot vectors and face support.
WebGL interface, computer graphics pipeline.