|Peter Alfeld||Department of Mathematics||College of Science||University of Utah|
|The Bernstein Bézier Form||Home Page||Examples|
|Spline Spaces and Minimal Determining Sets||User's Guide||Residual Arithmetic|
|Triangulations||How does it work?||Bibliography|
To understand what the applet does you need to understand the Bernstein-Bézier form of a polynomial and the concepts of spline spaces and their minimal determining sets .
The main use of the applet is to analyze minimal determining sets. In the first few incarnations of this code that constituted the only possible use of the software. However, during the Spring Semester of 1999 my numerical graduate class persuaded me to add a variation of the Analysis mode that can be run as a two player game that's quite difficult and sophisticated and that I hope you will enjoy. It's described below at the end of this User's Guide. There is also a drawing mode described below which can be used to label domain points in various ways (without any analysis done by the code).
As an illustration, the Figure nearby shows the Clough-Tocher Split, a set of three triangles that share an interior vertex. The partial minimal determining set shown is for the case that r=1 and d=6. Crosses in circles indicate points in the minimal determining set, filled colored circles indicate points that have been determined, and white circles indicate points whose status has not yet been determined. Boxes indicate points that do not enter any smoothness conditions. Other symbols may be substituted in the drawing mode.
Click in the box on the top of this page (or download the byte code and run it standalone, see below).
Two windows will pop up, the control panel, and a drawing window. The initial triangulation consist of three triangles sharing an interior vertex (the Clough-Tocher split). If for some reason you can't get the applet to work click here for a static image of the control panel and here for an image of the initial drawing window. (The eighth row of the control panel will not show up if you are using the applet rather than a standalone version of the code. This is because Java will not let the applet write on your machine, and I won't let it write on my machine. See below for information on how to save your work.)
If you click on the above applet to make the control panel and drawing windows disappear you can recover them in the state you dismissed them by clicking on the applet again, but only in the same browser section!
You can also download the byte file and run the program standalone. On a Unix system you'd invoke the program with the command java MDS. On my system the program is more responsive in that mode, I can run it with a specified amount of memory, it handles memory problems more gracefully, and I can save my work. .
To quit click on the upper left button (labeled Quit) of the control panel, or type 'x' in any drawing window.
You can change the values of r (the degree of smoothness) and d (the polynomial degree)in the third row of the control panel. There is one red textfield for r and one for d. To edit any text field move the cursor into the textfield and click (always the left mouse button) or highlight part of the text. Then type the insertion or replacement string. A change in any text window becomes effective only after you hit Enter (or Return) on you keyboard. The contents of the textfields can also be incremented or decremented (by 1) by clicking on the ">" and "<" buttons next to the textfield.
Suppose you want to construct a minimal determining set. You do this in stages adding one or more points at a time. Let's refer to the points you have already selected as the current set. The current set is always a subset of a minimal determining set, and eventually it becomes equal to one. To add a point to the current set just click on the domain point. The first time you do this some linear algebra will be initialized and any points that do not enter the smoothness conditions are added. The symbols you see have the following meaning:
Points in the current set can also be taken out, by clicking on them. Any points that are implied by the larger set, but not by the smaller, revert to their outlined status.
The menu in the fifth row of the control panel can be used to determine the effect of clicking on a point, according to the following options:
The current color can be changed using the second menu in the fifth row of the control panel. The default is black.
By default, the drawing window is 601 by 601 pixels. There are three ways to get drawing windows of different sizes:
You can have several drawing windows at once. The control window always corresponds to one particular drawing window. The drawing windows are numbered. You pick which one is currently associated with the control window by changing the number in the text field in the second row of the control panel, the one preceded by the string "T =". You can increase or decrease that number by clicking "> " or "< " on the buttons next to it. You can also edit the contents of the text window. The most convenient way of associating the control panel with a given triangulation is to type "c " or "C" in the relevant drawing window.
A rudimentary editing facility is available. Clicking on the button labeled Edit in the fourth row of the Control Window brings up an Editing Window. At the same time the current triangulation changes into a simple line drawing with the vertices being labeled.
The coordinates of individual points can be changed using the textfields in the second row of the Editing Window.
In the third row the indices of three points can be chosen. Clicking on the button Align will change the coordinates of the third point P to move it close to being in one line with the first two points P1 and P2. The program first moves P to the pixel closest to the projection of P onto the line L through the first two points. It then searches the neighborhood of that pixel for a pixel that is actually on L. It avoids making points coincide. The search may be unsuccessful, for example if P is in between P1 and P2 and the differences of the x and y coordinates of P1 and P2 are two distinct prime numbers. You may be able to make the alignment possible by changing slightly the coordinates of P1 or P2 first. Pairs of parallel edges sharing a vertex are drawn in red.
The Buttons in the top row do the following:
This mode lets you enumerate triangulations with certain attributes and study their properties. It can be invoked from the menu in the fourth row. Much more information can be found here.
This mode allows the design of triangular finite elements. Much more information can be found here.
The following is a list of options available on the control panel. not yet discussed:
During certain time consuming process the drawing window indicates what's happening. The word Initializing is present during the initialization of the linear algebra , and a moving colored bar indicates progress. In particular the bars indicate:
Several Keyboard commands are available in each drawing window. The list below will be extended in the near future. The idea is that essentially one should be able to control each drawing window without using the control panel at all.
|D||increment d by 1|
|d||decrement d by 1|
|R||increment r by 1|
|r||decrement r by 1|
|0||make current color black (the default)|
|1||make current color red|
|2||make current color green|
|3||make current color blue|
|4||make current color cyan|
|5||make current color magenta|
|6||make current color yellow|
|7||make current color White Note: use this color with caution and only for special effects because the background of the drawing is white and the interior of circle and square outlines is also white.|
|RETURN||redraw the net|
|p||Turn position indication during Custom Design OFF|
|P||Turn position indication during Custom Design ON|
|c,C||associate the control panel with this window and put it on top|
|all mode||all mode|
|F1-F12||choose a triangulation (see above)|
|l||label the vertices, toggle between omitting and including boundary vertices|
|S||Enter Super spline mode.|
|I||Initialize MDS computation.|
|m or M||List the current set to standard output.|
|u or U||Undo the previous step in designing a custom triangulation. This can be repeated. Can also be used to undo the last step taken in the drawing mode, but in that case the command can be used only once.|
|z||Toggle the listing in the drawing window of the indices of the domain point that the cursor is currently pointing to. This feature is useful when working with b-nets of very many domains that are close together. The default is off. This is an experimental feature. The display sometimes gets confused, and can be restored by redrawing the net, e.g., by hitting the return key.|
|< and >||Decrease or increase the current symbol Size.|
At present, textual information (to standard output) is very sparse. When a triangulation is completed it is described. The dimensions and rank of the original matrix is stated and a list of the prime numbers used is given.
For example, the default Clough-Tocher split with r=1 and d=3 causes this description:
MDS: Version 3.0, November 1998 run # 1308 New Triangulation 4 Vertices 0: (300,383) 1: (524,525) 2: (300,100) 3: (76,525) 3 Triangles: 0: 3 1 0 1: 3 0 2 2: 0 1 2 3 boundary edges: 0: 1 3 1: 2 3 2: 1 2 3 interior edges: 0: 0 1 --- 3 2 1: 0 3 --- 1 2 2: 0 2 --- 3 1 3 boundary vertices: 1 2 3 1 interior vertices: 0 interior vertex 0 E = 3 e = 3 r = 1 d = 3 lower bound = 12 19 Bezier Points using 1 primes: 0 2147483647 The original matrix is 9 by 19 and has rank 7 The dimension of the spline space = 12
Most of this information is readily understood taking into account the fact that the interior vertex of the Clough-Tocher split is vertex 0. The vertices coincide with specific pixels whose coordinates are integers, with the origin in the upper left corner, x increasing to the right, and y increasing downwards. An interior edge is described by the pair of indices of its vertices, and the indices of the remaining vertices of the attached triangles. For example, "0 1 --- 3 2" means the interior edge is the edge shared by the triangles (0, 1, 3) and (0,1,2).
For each interior vertex v, E is the number of edges attached to v, and e is the number of different slopes these edges have. For example, the four edges emanating from a singular vertex form two parallel pairs, so E=4 and e=2.
The lower bound given is known to equal the exact dimension of the spline space whenever d>3r+1.
Typing "s" (for statistics) in the drawing window causes information like this (obtained after clicking on " complete" in the default setup) to be displayed:
checking ... 7 equations 12 active variables equations OK ... fill = 29/84 (34%) total of 597 Residuals The likelihood of no accidentally zero residuals is 99.999%
This means the reduced system has 7 equations in 23 active variables. 29 entries in that matrix are non-zero. The phrase "equations OK" is a leftover from the debugging days - it means the coefficients in each equation add to zero. They must since the function that equals 1 everywhere is a spline all of whose Bézier coefficients are 1. Please let me know it you ever get a message that the equations are not OK! The "total number of residuals" is the number of times a residual was computed since the last initialization of the linear algebra.
The word "fill" indicates the number of non-zero entries in the matrix compared to the total number of entries.
In the above example a total number of 597 residual has been computed so far. (That number can easily climb into the millions.)
When only one prime number is used the likelihood that none of the computed residuals of non-zero matrix entries is zero is displayed. This is based on the assumption that all residuals are equally likely. The likelihood is usually close to 100% if the default prime of 2 31 -1 is used. You may find it interesting to examine this likelihood for small prime numbers. When several prime numbers are used the likelihood of an accidentally zero residual actually increases, but the likelihood of a correct minimal determining set increases, so the likelihood statement is omitted. For more information check the page on residual arithmetic.
Dimensions and lower bounds on the dimension can be computed by using the Srd Calculator. The calculator does not require analysis of a linear system, saving a potentially large amount of time, and you may find it interesting to compare the lower bound with the actual dimension of your spline space.
It is a separate window that can be invoked by clicking on the button in the upper right corner of the control panel. Essentially it computes a lower bound on the dimension of the current triangulation of the form
dim S <= A V B + B V I C + sigma (*)
which is explained here. The bound equals the true dimension whenever
d > 3r+1
and in many other situations also. It becomes less reliable as the polynomial degree decreases.
When the calculator is brought up it shows the lower bound (*) for the current triangulation and the current values of r and d. The lower bound is displayed in the lower right corner of the calculator window. Usually That expression gets updated automatically whenever the triangulation (or r or d ) changes. However, the values of r , d, V B , and V I can be changed on the calculator panel itself, and the values of A, B and C will change accordingly.
This facility is most useful for examining the dependence of A, B, and C on r and d. It is less useful to change V B and V I since the resulting value of the lower bound does not apply to any particular triangulation.
A little more subtle is the value of e V that can be changed in the right most text field in row 2. If it is white with no text in it it has no effect on the number in the third row of the panel. However, if you enter a number then the number sigma in the third row will equal
You may find it interesting to study the dependence of sigma on r, d, and e V , but the lower bound in the fourth row will have a very arcane meaning.
The Hide button hides the calculator window. (You can recover it by pressing on the Calc. button in the control window.) The Get button synchronizes the calculator with the current triangulation (the one associated with the control panel).
Every update of the calculator also causes an appropriate line of text to be written.
The image nearby shows the domain points for C 1 cubic on a custom designed triangulation. The dimension of this space in general is believed to be 3V B + 2V I + 1 plus the number of singular vertices. The example shows 3 domain points associated with each boundary vertex, 2 with each interior vertex, and one additional point (the lone blue plus sign in the center of one of the interior triangles).
You can design your own triangulation by selecting the three vertices of the first triangle and then adding flaps (new triangles joined to the old triangulation along one edge) and fills (new triangles joined along two edges). Follow these steps:
Pressing the button labeled "import" opens a new window that lets you load a triangulation from a file (only in stand-alone mode) or a URL. The file needs to contain the following data: V and N on the first line, followed by V lines containing the coordinates of the points, one point per line, followed by N lines containing the indices of the vertices of each triangle, one triangle per line. The integers must be separated by blanks, and the lines must not contain other data. For example, the file for the CT split would be:
4 3 302 88 80 514 521 514 301 372 2 0 3 2 3 1 3 0 1The Save Button saves such files with the extension .cmb
The drawing mode is invoked with the menu in the third row. You can first do some analysis in the analysis mode and then switch to the drawing mode to change some of the symbols. However, if you switch from drawing mode to analysis mode then the drawing window gets reinitialized, so beware!
Several symbols can be used. They are selected by the menu in the fourth row and illustrated in the Figure nearby. Everything on the control panel works as in the Analysis mode when it makes sense. (For example, it does not make sense to ask the applet to color all the points in the minimal determining set.)
In the single point mode (selected by the first menu in the fifth row) clicking on a point that has already been labeled with the currently selected symbol causes that symbol to be replaced with a circle. (This is like removing a point.) In the ring, disk, and triangle modes points are marked with the selected symbol regardless of their prior status. In the " all" mode all points as yet unmarked (indicated by single thickness circles) are marked with the currently selected symbol. In the "replace" mode all points marked as the selected point are marked with the selected symbol. Changes made in any but the point mode can be undone by typing "u ".
It is possible to save your work, but for security reasons Java will not let my applet write on your machine (and I won't let you write on my machine). You need to download the byte code as described in the next section. If you run that code (directly rather than via a browser) on your system there will be an eighth row on the control panel (shown on on this static image) which lets you specify a file name and read and write to that filename.
The individual items in the 8-th row do the following:
The individual parts have the following meanings:
The buttons labeled "CODE", "DOUBLE ", and "QUADRUPLE", in the bottom row of the control panel computes data in floating point form and save them to a file s.code where s is the string determined by the other items in this row. Saving the "CODE", information can also be invoked by typing w or W in the drawing window. The bars in the drawing window in turn show progress in setting up the floating point equations, reducing the system to triangular form, and then reducing it to diagonal form. The primary contents of the s.code is the matrix C where
The files s.code differ in subtle ways. Click on the links below to see the file for the cubic C 1 CT scheme.
The buttons "DOUBLE" and "QUADRUPLE" also produce a file s.explicit which contains an exact rational representation of the determined coefficients in terms of those corresponding to the minimal determining set.
Super splines are splines that satisfy additional smoothness conditions. (They thus form a subspace of an ordinary spline space.)
To examine a super spline space do the following:
It is possible to impose additional conditions that force the splines to have a reduced polynomial degree on selected triangles. This option is treated like a superspline condition although it is conceptually different. To reduce the polynomial degree on a certain triangle by 1 enter superspline mode and click close to the center for the triangle. The triangle will be drawn in green, and the (reduced) polynomial degree will be drawn in red, close to the center of the triangle. That red number may be partially obscured by the B-net which is also drawn. The + and - keys work as they do for the superspline conditions, + increase the polynomial degree (up to d ) and - decreases it. Here are are some examples of polynomials with lesser degrees than meets the eye.
Pressing the button labeled Bounds in the sixth row of the control panel turns the computation of bounds on and off. The best available current bounds are displayed at the top of the drawing window. The feature is on by default. This is an active research topic under current investigation.
Alternatively, on a Unix system you can download the single file message , put it into an empty directory, and type source message. This will unbundle the class files and bring up the MDS code. Alternatively, you can download the zip file MDS.zip which has all required class files.
Details of how to run the byte code on your machine depend on your operating system. On my (Unix) machine the command
java -ms128m -mx128m MDS
You can save the image of a triangulation to a postscript file or directly print that image. To do so click on the Print button in the first row of the control panel or type Control-P in the drawing window. This facility works only in the standalone mode. If run from an applet, a security exception occurs.
This facility is currently [June 2012] under development and does not have all the features associated with the regular spline spaces.
Let D denote a directional derivative, and S a spline space being examined by the software. Clicking on the orange button labeled d/de in the main control panel brings up a new drawing window and a new control window that let you examine the space of functions Ds where s is in S. The drawing window shows the coefficients of s as usual, and the coefficients of Ds as triangles. Those triangles are clickable, and their color indicate their status. Dark blue means they can be set, light blue they have been set, and gray they are implied by other coefficients (of s or Ds) that have been set. The control window let's you pick the direction of differentiation. It can be chosen as a linear combination of edges in the triangulation, or as a vector in 2-space. The coefficients and vertices can be labeled, and the original equations can be printed.
Clicking on the orange button All D in the main control window brings up a similar control panel that lets you examine Bézier nets for all derivatives. You can pick two directions, again in terms of Cartesian Coordinates, or as a linear combination of two edges. These directions are designated x and y although they can be in any direction.
On both panels the following buttons have these effects:
Additional buttons on the All Derivatives panel include:
We consider a vector field whose components are two splines P and Q. The divergence and curl of the field are defined by
div ( P, Q ) = P x + Q y and
curl ( P, Q ) = - P y + Q x , respectively.
Clicking on the Button labeled Vector Analysis in the control panel brings up a new vector control panel and a new vector drawing window. They let you analyze the vector field based on the spline defined in the current triangulation, including any supersmoothness conditions. Any change in the current triangulation has no effect on the vector windows once they are produced.
The original definitions of div and curl are with respect to the x and y directions but those can be changed in the first row of the vector control window. The text fields there can be used to enter a new direction which replaces the x direction. The replacement of the y direction is perpendicular to the new x direction. For simplicity we well refer to the new directions also as x and y directions.
The coefficients of the vector components, and those of div and curl, can be set in the vector drawing window. The circular domain points there correspond to the coefficients of P and Q, and the triangles correspond to the coefficients of div and curl. Left clicking on a domain point or a triangle sets P or div, respectively, and right clicking sets Q or curl, respectively. Clicking the middle button has the same effect as first clicking left and then clicking right. P is represented by blue, Q by green, div by red, and curl by yellow. A saturated color indicates that the coefficient is available, a pastel color that it has been assigned, and gray indicates that it has been implied.
The controls in the control window have the following effects:
P: p/D Q: q/D div: s/E curl t/F dim(H) = h
The following table gives an indication of the capabilities of the code. The underlying triangulation is the generic double Clough-Tocher split with d=2r for r=1,2,...,10. The columns in the table have the following meaning:
|generic double-Clough-Tocher split, d = 2r|
To explain the rules we need to distinguish between points you or your opponent add to the current set, and points that count towards your victory. Let's call the latter cookies to avoid confusion.
The rules are as follows:
Please write to meif you encounter any bugs or you like to make suggestions for additional features.