I implemented an editor for hierarchical B-splines which were first presented in [1] by Forsey and Bartels. I also referred to [2], Forsey's PhD thesis, as additional detail was presented. Like Forsey, I also used uniform cubic b-spline tensor product patches. Uniform knots allow for a convenient matrix formulation of the b-spline basis functions.
I tesselated the surfaces and drew them with OpenGL's glDrawArrays(). I also used the GLM library, mostly for coordinate transformations, and its vector class. The Eigen library was also used for computing the b-spline surfaces, as it supports matrices of arbitrary dimension, and has convenient block indexing.
A 4x4 patch is created by default, with a 16x16 resolution per patch (eg. number of triangles in a patch is 16x16x2).
The user is free to press new at anytime. They will be prompted (by the console) for new patch dimensions and resolution. This resets the editing session and allows for arbitrary patch sizes >= 4x4.
The user can load a previously saved editing session from file by pressing load and entering the file name in the console. An editing session is saved by pressing save and entering the file name in console.
The user left-clicks a point to select it, turning the point red. The user can then left-click and drag the point. Screen coordinates are converted to model coordinates with help from glm::unProject.
Edit points allow the user to directly interact with the surface. Selection and interaction is done as for control points.
The key feature of the editor. User first selects a point and presses S to add a layer of refinement around that point. An area of refinement can be designated by selecting a second point using LEFT_CONTROL while left clicking.
Grey coloured control points cannot be moved, and are set by the parent surface to maintain continuity with the child surface. The keys PAGE UP and PAGE DOWN can be used to navigate refinement levels. This allows for easier selection of desired control points. In the image below the level is one above the parent level (now the first child).
Of course refinement can be done multiple times on one patch and one layer of refinement can have multiple siblings.
When the control points of a parent are moved the child patch needs to still maintain continuity with the parent. Therefore all control points are exressed in terms of a reference (determined by the parent) and an offset (determined by editing at the respective level). The base surface is edited from the previous figure. As seen below, the child patches move with the parent, while still retaining their own details.
Every patch can be assigned a unique colour using the on-screen menu. Only colours of the currently selected refinement level are shown.
Patches of the same refinement level can be merged. This is necessary when refining the parent would cause one of the inactive (grey) points of a child to become active. Start with two children of the same level. They are independent of each other since three control points serve to enforce a continuous boundary. Note these children have children of their own and have been edited. The editors patch merging is free of any restrictions. The algorithm traverses all child nodes and updates their information.
I switch to the parent's level and select a point that if refined, would cause conflict with the existing children.
I refine that point, and the editor deletes the two children and creates one larger patch that contains all their information. Note that the surface has not changed.
Phong shading. I used the CS688 shader from assignment 3. However I had to calculate the normals (done using the matrix form). The control points are shaded using the basic shader from assignment 1.
Movement. Track ball rotation. I used the CS688 track ball code from assignment 3. Right click + drag allows for translation of the surface. The scroll wheel allows for zooming.
Multi-threading. I saw about a 2x speed up in FPS on a 16 thread CPU. Multiple threads are used for tesselation, and calculating surface points / normals. This is a sub-optimal implementation as it was done near the end of the project. Rewriting the program with multi-threading in mind should reduce the gap between actual and theoretical speed up. Threads are launched between each frame, which introduces overhead and requires full sychronization before displaying the image.
Learned how to implement a type of tensor-product surface as there were no assignments on this.
Learned the useful and easy to compute with matrix representation of b-splines. I also had to derive how to compute normals in this matrix representation (although it was not that hard once I realized it was straightforward).
Beyond CS688 I had little exposure to hierarchical data structures. Of course this project forced me to become quite familiar with tree data structures.
Reinforce basic OpenGL concepts such as object picking, buffers, and coordinate transforms.
Learn how to use spline surfaces to create models (motivation for splines).
I couldn't resist recreating the famous graphics dragon in my editor. See the results below.
You can see the mess of points this creates, thankfully I actively used my method of selecting levels. More importantly, notice the density of points increases around key areas such as the nose and ears. In a regular b-spline editor this density of points would have to be constant requiring extra computation.
References
[1] David R. Forsey, Richard H. Bartels. Hierarchical B-Spline Refinement. SIGGRAPH 1988, Atlanta.
[2] David R. Forsey. Motion control and surface modeling of articulated figures in computer animation. Thesis. University of Waterloo, Department of Computer Science, 1990.