Programming Assignment 4

Evaluating a Nonuniform B-Spline Surface

General

The idea is to extend the previous assignment to perform knot-insertion. The main objectives are to gain a better understanding of a knot-insertion algorithm (you may use any algorithm for this) and to see an example of subdivision which will make the lecture about subdivision much more enlightening.

Your program should accomplish the following:

  • Given an initial control polygon as in the previous assignment insert knots until the control polyhedron approaches the actual spline surface.

  • To do this you will need to determine when and where you insert a new knot. One idea is as follows:
    • For a B-Spline curve with control point A, B, C, D
    • When the length of AD is about the same as the length of AB + length of BC + length of CD, you are done.
  • Keep the output resolution (u, v step sizes) as 1.0 and generate different levels of subdivision.
  • Hand-in a description of the knot insertion algorithm you used, and how you determine whether and where to insert a knot.

Code

  • You may program in any language, although Matlab is recommended. If your program is in a language other than Matlab, Mathematica,  C/C++, or Java, I may ask you to demonstrate it. 

  • Any package can be used for the viewing purpose. You should not use build-in functions in Matlab, Mathematica, or other packages for generating B-Spline surfaces and knot-insertion.

  • Your code should be readable. The first part of every function should contain a block of comments that give a detailed description of the code's purpose, usage, and its input and output variables.

  • Your code should return warning and error messages for invalid input data.

Input/Output

All values in the following descriptions are floating point, unless preceded by int.

The input will consist of a file in the following form:

(int) Number of Surfaces       u step size           v step size


(int) Number of control points along each row in first surface
(int) Number of control points along each column in first surface

first control point in first row x
first control point in first row y
first control point in first row z
second control point in first row x
second control point in first row y
second control point in first row z
...
last control point in first row x
last control point in first row y
last control point in first row z
...
first control point in second row x
first control point in second row y
first control point in second row z
...
last control point in last row x
last control point in last row y
last control point in last row z

 

(int) Number of control points along each row in second surface
(int) Number of control points along each column in second surface

first control point in first row x
first control point in first row y
first control point in first row z
second control point in first row x
second control point in first row y
second control point in first row z
...
last control point in first row x
last control point in first row y
last control point in first row z
...
first control point in second row x
first control point in second row y
first control point in second row z
...
last control point in last row x
last control point in last row y
last control point in last row z

...    ...   ...
...   ...   ...

(int) Number of control points along each row in last surface
(int) Number of control points along each column in last surface

first control point in first row x
first control point in first row y
first control point in first row z
second control point in first row x
second control point in first row y
second control point in first row z
...
last control point in first row x
last control point in first row y
last control point in first row z
...
first control point in second row x
first control point in second row y
first control point in second row z
...
last control point in last row x
last control point in last row y
last control point in last row z


The output will be a file of triangles in the following form:

(int) Number of triangles

x00     y00      z00

x01     y01    z01

x02     y02     z02


x10     y10     
z10

x11     y11    z11

x12     y12     z12


...         ...         ...


xn0     yn0      zn0

xn1     yn1    zn1

xn2     yn2     zn2


Where "xij    yij    zij" means ith triangle's jth vertex.


A simple example of the output file format with four triangles arranged in a rough tetrahedron:

4
-1 -1 1
1 -1 1
0 1 0
0 -1 -1
-1 -1 1
0 1 0
1 -1 1
0 -1 -1
0 1 0
-1 -1 1
0 -1 -1
1 -1 1



The output should be generated by evaluating each surface patch at parameter values incremented by u step size in u and v step size in v. The triangles should connect these points. For example a uniform cubic B-spline surface with four control points in each row and five control points in each column is defined over parameter values [3,4]x[3,5]. If the u step size was 0.1 and the v-step size was 0.2, then you would evaluate the surface at parameter values:

(3.0,3.0)
(3.1,3.0)
...
(4.0,3.0)
(3.0,3.2)
(3.1,3.2)
...
...
(4.0,5.0)

and the triangles to output would be as follows, where Q(u,v) is the surface evaluated at (u,v). (Actually you can pick a different way to triangulate the points if you want.)

Q(3.0,3.0) Q(3.1,3.0) Q(3.1,3.2)
Q(3.0,3.0) Q(3.1,3.2) Q(3.0,3.2)
Q(3.1,3.0) Q(3.2,3.0) Q(3.2,3.2)
Q(3.1,3.0) Q(3.2,3.2) Q(3.1,3.2)
...


Viewer

A viewer with a crystal ball interface written in C++, using glut and openGL, is provided. It can read in files of triangles in the format described above. You might simply add code to it to do your assignment. It is documented.

Download Viewer (9k, tar-zip file)

Note you don't have to use this viewer, it is easy to write out your triangles to some other format, vrml for example and use a vrml browser to examine your results (other options like IV, OBJ, STL, etc.)

What you should hand-in

Please hand in

  • All of your source code

  • A brief description of how to compile and run your code

  • A description of the knot insertion algorithm you used, and how you determine whether and where to insert a knot.