gte628v
CS4451 - Computer Graphics
Project 1
|
Jesse Shieh gte628v CS4451 - Computer Graphics Project 1 |
This page requires Macromedia Flash Player 6.
|
Program
Curve and surface refinement techniquesI implemented two refinement techniques described by Prof. Rossignac in CS4451. Both take as input a control polygon P with n vertices and produce another “smoother” control polygon S with 2n vertices. Both approaches start by inserting a new vertex in the middle of each edge of P (This is the “split” operation). Then the “Split&Tweak” technique pulls each original vertex half-way towards the average of its two new neighbors (See Figure 1). The “4-point” approach on the other hand pushes the newly inserted midpoints by 1/4 away from the average of their neighboring mid-points on the left and on the right (See Figure 2). 
If you apply these smoothing operations repeatedly, the Split&Tweak will converge to a uniform cubic B-spline curve that is typically smooth but does not interpolate the vertices of P. The 4-point approach always interpolates the vertices of P but may exhibit sharper turns, as shown in Figure 3, which compares the two approaches for a complex P. Because both approaches converge quickly, 3 levels of subdivision are usually sufficient to produce a smooth-looking curve. 
To force a the B-spline curve to pass through a given point Q, you can put another point directly on top of the given point as shown in Figure 4. To force a sharp angle in the B-sline curve you can place three of the control points very close to colinear as shown Figure 5. To force a sharp angle in the 4-point curve you can place a control point very far to the left or right of it's neighbors as shown Figure 6.   
ImplementationThe input control polygon is given in an two arrays Vx and Vy of n values representing the x coordinate and y coordinate of the vertices, respectively. I implemented methods that run on only one of these arrays (Vx or Vy). This is sufficient, because the x and y values can be treated separately AND identically.Split&TweakThe simple and intuitive way of implementing the Split&Tweak method is to create an auxiliary array M of edge midpoints and then another array A in which to store the tweaked original vertices. This, however, requires two passes through the array passed in. I implemented the Split&Tweak method using a single pass calculating the midpoint and moving the original vertex in 1/4. This can be done, because the results are stored in a separate array, thus preserving the original vertex values for the next run. It would be difficult to do this in place, that is to manipulate the values of the array, because to calculate the next midpoint, you need to original vertex which restricts you from tweaking it until after all midpoints are calculated, forcing two separate passes. This is then a classic example of space vs time. By using two passes, the algorithm will take more time, but is possible to reduce the amount of memory required. By using only one pass, the algorithm is forced to create a new array, but may run a bit faster than the previous. Because Professor Rossignac specified that conciseness was key to this assignment, I chose the single pass algorithm b/c it requires only half as many lines as the alternative. To compute the bspline on a point you must call the method twice, once on each coordinate axis.i.e. show(bspline_helper(bspline_helper(bspline_helper(Vx))), bspline_helper(bspline_helper(bspline_helper(Vy)))); All the other functions work similarly. The code is shown below.
Line 4 simply computes the midpoint of the line produced by the current vertex (i) and the next vertex (i + 1). It is a bit more complicated, however, because of the case of the last vertex. In this case, the (i + 1)th vertex does not exist, so we will use the first vertex instead, because these vertices represent a closed polygon and thus loop around. By running the modulo operator on (i + 1) with the length of the array (V.length), we can accomplish the loop-around concisely and efficiently. We take the result of this and place it in position i * 2 % (V.length * 2) of the new array because the new array will be twice as large as the original array and on each pass of the loop, we are adding two points to the new array. We add the % (V.length * 2) to take care of the last case where i = V.length. In this case, we are actually operating on the first element of the array because there is no V.length element and V.length % V.length is just 0, hence the first element of the array. If we do not mod V.length * 2, then we will be operating on the first element of the array, but adding to the end of the array, thus we need to do this to ensure that the second, longer array also loops around like the first one does. It is possible to get rid of this, but then extra code will need to be added to consider the first and last points in the array. This way is much more concise and ELEGANT. Line 5 looks very confusing and complicated, but it is actually not. If you break it up and extract some variables, you get the following, which is tested to be the same:
c is the current vertex n is the next vertex p is the previous vertex From this we can see very clearly that lines 5-7 in the first example is equivalent to line 8 in the second example. And that we are just computing the "tweak" of the original vertex by moving it 1/4 closer to its neighbors using the equation given in class. Although the second example is much clearer than the first, the first was used because it has 3 extra instructions, specifically those of assigning c, n, and p which the first does not need. It is possible to say and I might agree in another situation that the second example is actually more "concise" than the first. In terms of the character count, the second is shorts, but in terms of lines of code or more clearly the # of semicolons, the first is shorter. It is hard to say which one is more "concise". This is why that are both included here. 4-point subdivisionThe 4-point subdivision method works very similarly to the Split&Tweak method explained above. I implemented the method, again, using only one pass calculating midpoints and tweaking along the way. The difference here, is that it is the calculated midpoints which are tweaked instead of the original vertices. This allows the smooth curve to interpolate the original vertices, which may be useful. Following this, we push the midpoints out by 1/4 instead of in.The code is shown below.
You should note on line 3 that the for-loop iterates from V.length - 1 to V.length * 2 instead. This is because the 4-point algorithm requires 2 points previous from the current point. If we run this on the first point, 0, we will be asking for the -1th and -2th elements in the array. We cannot or really I am just unsure as to what the modulo of a negative number is, so intead, I start i as V.length - 1 and end with V.length * 2 - 1, so no negative numbers are encountered. This is possible because of all the modulos within the code that make the array sort of circular. Again, if we extract some expressions and use variables instead, we come up with a much simpler, verified version shown below.
And it is easy to see, that the midpoints are pushed out rather than pushed in due to the change in sign in line 8 (curr-... instead of curr+...). Also, that the tweaked vertex is actually the midpoint. I'd like to note that this implementation actually works for cases where V.length = 1 and when V.length = 2, but not when V.length = 0. In this case, the for loop will execute once and possibly try to access information that doesn't exist causing an error. Displaying the polygonsTo render the polygons I used Macromedia Flash's built in line drawing tools. The code shown below.
line 4 specifies the width of the lines to be 1 pixel, the color to be the color passed in. The last parameter refers to the depth, which is unimportant here. line 5, moves the current position to the last point in the polygon. This is so, when the lines are drawn they will close up into a closed polygon. lines 6-7 simply iterate through the points and draw lines from the previous point to the current point. SurfacesI have used the above polygon subdivision procedures to create surfaces as follows. I start with a two-dimensional array P[n,m] of control points. I treat each row as a separate control polygon and subdivide it 4 times. I end up with an array Q[n,m * (2 ^ 3)] of points. Then I transpose this "matrix" and repeat the above creating a "matrix" S[n * (2 ^ 3),m * (2 ^ 3)] of points.This portion of the code is included below
Note that on lines 3, 4, 6, and 7 we introduce this temporary array T that seems to be unnecessary. The reason for this is because 'smooth' returns an array of two arrays. If it were possible to say something like the following:
Then we could save 4 lines of code in both loops totaling 7 lines. But b/c there is no construct like the above, we have to use this temporary variable. There is a disadvantage to this code, in that it is very specific to this program and not very abstract in terms of simply taking a matrix, computing the surface and returning the new matrix. Instead it uses the included method to smooth the points and these methods go ahead and run several iterations. It also goes ahead and displays them within the loops which is program dependent and does not return a value. This can be easily added, but was not done for the sake of an extra unnecessary instruction. I have included the .fla file as prj1-3.fla I have included samples of surfaces constructed using the Flash Program below as Figure 7 through 13. 
|
_root.createEmptyMovieClip("shape", 1); /* create object that will do the drawing */
colors = new Array(); /* the different colors to use for each iteration */
colors[0] = 0xFFFF00;
colors[1] = 0x999999;
colors[2] = 0x00FFFF;
colors[3] = 0x000000;
colors[4] = 0xFF00FF;
iterations = 4; /* the default number of iterations to run */
delta = 8; /* how far to move the points i.e. 8=1/4 */
numPoints = 3; /* current number of points on the screen */
autoRedraw = true; /* whether or not to automatically redraw each time a pt is moved */
smoothingFunc = bspline_helper; /* current smoothing function */
smoothingFunc2 = fourpts_helper; /* secondary smoothing function for surfaces */
surfacingFunc = true; /* whether or not we are drawing surfaces */
surfacePolygonSize = 3; /* used by surface to determine the polygon type */
point0.label = 0; /* initialize the default 3 point's labels */
point1.label = 1;
point2.label = 2;
drawTorus();
redraw(); /* go ahead and draw the smoothed polygon for the 3 pts */
stop();
/*
* smooths a set of points given the using the function f
* and displays and returns the result.
*
function smooth(Vx, Vy, f) {
show(Vx = f(f(f(f(Vx)))), Vy = f(f(f(f(Vy))))); /* run f 4 times and show the result *
return new Array(Vx, Vy); /* return the result *
}*/
/*
* same as above
*/
function smooth(Vx, Vy, f) {
//this version of smooth is longer, but allows the user
//to change the number of iterations. It also selectively
//displays the intermediate steps.
for(var j = 0; j < iterations; j ++) {
Vy = f(Vy);
Vx = f(Vx);
if(!surfacingFunc) {
show(Vx, Vy, colors[j]);
}
}
return new Array(Vx, Vy);
}
/*
* runs the bspline algorithm on a set of numbers
* and return the result.
*/
function bspline_helper(V) {
M = new Array();
for(var i = 0; i <= V.length; i ++) { /* cycle through the numbers */
M[i * 2 % (V.length * 2)] = (V[i % V.length] + V[(i + 1) % (V.length)]) / 2; /* find the midpoint */
M[(i * 2 - 1) % (V.length * 2)] = V[i % V.length] + ( /* move the vertex in 1/4 */
(V[(i + 1) % V.length] - V[i % V.length]) +
(V[(i - 1 + V.length) % V.length] - V[i % V.length])) / 8;
}
return M;
}
/*
* runs the four point algorithm on a set of numbers
* and returns the result.
*/
function fourpts_helper(V) {
M = new Array();
for(var i = V.length - 1; i < V.length * 2; i ++) { /* cycle through the numbers */
M[(i - V.length) * 2] = V[i - V.length]; /* keep the vertex the same */
M[(i - V.length) * 2 + 1] = ((V[i % V.length] + V[(i + 1) % (V.length)]) / 2)
- ((((V[(i + 1) % V.length] + V[(i + 1 + 1) % (V.length)]) / 2)
- ((V[i % V.length] + V[(i + 1) % (V.length)]) / 2))
+ (((V[(i - 1) % V.length] + V[(i - 1 + 1) % (V.length)]) / 2)
- ((V[i % V.length] + V[(i + 1) % (V.length)]) / 2))) / delta; /* move the midpoint out 1/4 */
}
return M;
}
/*
* takes in a set of points and a color and displays them
* as a closed polygon on the screen
*/
function show(Vx, Vy, color) {
with(_root.shape) {
lineStyle(1, color, 100); /* set the line width=1, color=color, depth=100 */
moveTo(Vx[Vx.length - 1], Vy[Vy.length - 1]); /* move to the last point, necessary for the polygon to be closed */
for(var i = 0; i < Vx.length; i ++) { /* go through all the points */
lineTo(Vx[i], Vy[i]); /* draw a line to the current point */
}
}
}
/*
* takes in a matrix of points and creates a torus
* based on the set of polygons described by the
* matrix. It also displays it on the screen.
*/
function surface(Vx, Vy) {
for(var i = 0; i < Vx.length; i ++) { /* go through all the polygons */
T = new Array();
show(Vx[i], Vy[i], 0xFF00FF); /* show the original polygon */
T = smooth(Vx[i], Vy[i], smoothingFunc); /* smooth it */
Vx[i] = T[0]; /* put the results back in the matrix */
Vy[i] = T[1];
show(Vx[i], Vy[i], 0x000000); /* show the result */
}
Vx = transpose(Vx); /* transpose the matrices */
Vy = transpose(Vy);
for(var i = 0; i < Vx.length; i ++) { /* repeat the above... */
T = new Array();
T = smooth(Vx[i], Vy[i], smoothingFunc2); /* ...except with fourpts */
Vx[i] = T[0];
Vy[i] = T[1];
show(Vx[i], Vy[i], 0x000000);
}
}
/*
* takes in a matrix V and returns its transpose.
*/
function transpose(V) {
M = new Array();
for(var i = 0; i < V[0].length; i ++) {
M[i] = new Array(); /* initialize the return matrix */
}
for(var i = 0; i < V.length; i ++) {
for(var j = 0; j < V[i].length; j ++) {
M[j][i] = V[i][j]; /* transpose operation */
}
}
return M;
}
/*
* clears the drawing area.
*/
function cls() {
_root.shape.clear();
_root.errormsg = "";
}
/*
* removes all but three of the points.
*/
function clearPoints() {
for(var i = 3; i < numPoints; i ++) {
t = eval("point" + i);
t.removeMovieClip();
}
numPoints = 3;
}
/*
* sets the current mode to draw the bspline.
*/
function drawBspline() {
smoothingFunc = bspline_helper;
if(autoRedraw) {
redraw();
}
}
/*
* sets the secondary smoothing func for surfaces
* mode to draw the four points.
*/
function drawFourpts2() {
smoothingFunc2 = fourpts_helper;
if(autoRedraw) {
redraw();
}
}
/*
* sets the secondary smoothing func for surfaces
* mode to draw the bspline.
*/
function drawBspline2() {
smoothingFunc2 = bspline_helper;
if(autoRedraw) {
redraw();
}
}
/*
* sets the current mode to draw the four points.
*/
function drawFourpts() {
smoothingFunc = fourpts_helper;
if(autoRedraw) {
redraw();
}
}
/*
* sets the current mode to draw the bspline AND four points.
*/
function drawBsplineAndFourpts() {
smoothingFunc = "both";
if(autoRedraw) {
redraw();
}
}
/*
* sets the current mode to draw the torus.
*/
function drawTorus() {
surfacingFunc = not surfacingFunc;
if(!surfacingFunc) {
showSurfaceOptions(false);
}
else {
showSurfaceOptions(true);
}
if(autoRedraw) {
redraw();
}
}
/*
* shows or hides the options that only pertain to surfacing
*/
function showSurfaceOptions(yes) {
ps1._visible = yes;
ps2._visible = yes;
ps3._visible = yes;
dbs2._visible = yes;
dfp2._visible = yes;
}
/*
* toggles whether or not to automatically
* redraw everytime the user changes an option.
*/
function toggleAutoRedraw() {
autoRedraw = not autoRedraw;
if(autoRedraw) {
redraw();
}
}
/*
* draws the shape(s) and smoothed polygon or surface.
*/
function redraw() {
_root.cls();
if(surfacingFunc) {
_root.surfacePoints();
} else {
_root.smoothPoints();
}
}
/*
* add another point into the drawing area.
*/
function addPoint() {
_root.attachMovie("point", "point" + numPoints, numPoints);
t = eval("point" + numPoints);
t._x = 100;
t._y = 100;
t.label = numPoints;
numPoints ++;
if(autoRedraw) {
redraw();
}
}
/*
* take the points on the screen and smooth them.
*/
function smoothPoints() {
Vx = new Array();
Vy = new Array();
for(var i = 0; i < numPoints; i ++) {
Vx[i] = eval("_root.point" + i + "._x"); /* place point coordinates into the arrays */
Vy[i] = eval("_root.point" + i + "._y");
}
show(Vx, Vy, 0xFF00FF); /* show the original polygon */
if(smoothingFunc == "both") {
smooth(Vx, Vy, bspline_helper);
smooth(Vx, Vy, fourpts_helper);
}
else {
V = smooth(Vx, Vy, smoothingFunc); /* smooth the points */
}
}
/*
* take the points on the screen and create a surface
* from them.
*/
function surfacePoints() {
if(numPoints % surfacePolygonSize != 0) { /* check to make sure the # of pts is acceptable */
_root.errormsg = "ERROR: The number of points required to \ndraw a torus must be a multiple of the \npolygon size.";
} else {
Vx = new Array();
Vy = new Array();
for(var i = 0; i < numPoints / surfacePolygonSize; i ++) {
Vx[i] = new Array();
Vy[i] = new Array();
}
for(var i = 0; i < numPoints / surfacePolygonSize; i ++) {
for(var j = 0; j < surfacePolygonSize; j ++) {
Vx[i][j] = eval("point" + (i * surfacePolygonSize + j) + "._x"); /* put the coordinates of ... */
Vy[i][j] = eval("point" + (i * surfacePolygonSize + j) + "._y"); /* ...the points into the matrices */
}
}
surface(Vx, Vy);
}
}
|
_root.cls(); _root.clearPoints(); stop(); |
on(release) {
gotoAndStop(2);
}
|
on(release) {
gotoAndStop(1);
}
|
on(press) {
if(hitTest(_root._xmouse, _root._ymouse, true)) {
_parent.startDrag();
}
}
on(release) {
_parent.stopDrag();
if(_root.autoRedraw) {
_root.redraw();
}
}
|