CS-C3100 Assignment 2: Curves and Surfaces

In this assignment, you will be implementing spline curves and mesh subdivision. These are powerful building blocks for animation, 3D modeling and other tasks. The recom-mended extra credit work applies your spline curves to additional ways of modeling 3D objects: swept surfaces and generalized cylinders.




This assignment is considerably more challenging than the intro assignment, and the majority of your time will be spent thinking about the theory rather than how to write code. Start early so you have time for debugging, thinking about the issues that come up, and asking for help.




Requirements (maximum 10 p) on top of which you can do extra credit




Evaluating Bezier curves (2 p)



Evaluating B-spline curves (2 p)



Subdividing a mesh to smaller triangles (2 p)



Computing positions for the new vertices (2 p)



Smoothing the mesh by repositioning old vertices (2 p)






Getting Started






The sample solution example.exe is included in the starter code distribution. Notice that we have added some buttons to the right of the window.




First, load up core.swp by clicking the ’Load SWP’ button on the right. For this assignment, parsing the les is already done for you.




The le core.swp contains four curves. Their control points are shown in yellow, and the resulting curves are shown in white. You can toggle what is drawn with the UI buttons. Click the ’Draw normals’ button to see the local coordinate system at points of a curve.




Subdivision surfaces are loaded with the ’Load OBJ’ button. (Previously loaded curves will stay visible, and can only be hidden by restarting the application.) Press the ’Re ne subdivision’ and ’Coarsen subdivision’ buttons to change the subdivision level. Play with the di erent models to see what happens.

 


The SWP les under the srev and gcyl subdirectories are for extra credit work. In addition to splines, these les contain sweep curves and generalized cylinders based on those splines. example.exe can draw them; click the ’Draw surface’ button to show or hide the generated surface.




Now, build the starter project and launch it. Load the SWP le circles.swp. The starter code is fully functional on this example as-is. If you click the ’Draw normals’ button, you’ll also notice that the coordinate frames are computed for you. The scene can be rotated, panned and zoomed using the mouse and its buttons; try it out.




This assignment reuses old code, and the rendering code is very di erent from the intro assignment. The code you see here is old, "immediate mode" OpenGL. Please note that you don’t have to touch the rendering code in this assignment, and all the remaining assignments will again use modern style OpenGL.







Implementing Curves






Your rst task is to implement piecewise cubic Bezier splines and B-splines. Given an array of control points, you are to generate a set of points that lie on the spline curve (which can then be used to draw the spline by connecting them with line segments). For instance, the control points shown in the picture on the left will result in the piecewise uniform cubic B-spline on the right (in this example, the rst three control points are identical to the last three, which results in a closed curve).




The starter code already renders the control points for you. You will need to evaluate the spline individually and build a list of vertices per each curve.

  







































































Computing points on the spline is su cient if the only goal is to draw it. For other appli-cations of splines, such as animation and surface modeling, you might need to generate additional information (see extra credit section).

 R1 Bezier curves (2 p)




Implement the evaluation of Bezier curve points (function evalBezier). Start by writing the coreBezier function in curve.cpp, which is the basis for evaluating one 4-point bezier curve at small steps, generating sequences of vertices that can then be used for drawing short straight lines on the screen, ultimately making it look like a smooth line.




In the evalBezier function, you generate points along the whole chained-together Bezier curve. Because we chain the individual Beziers together by sharing the last control point of the preceding curve with the rst control point of the next curve, this function must get 3n + 1 vertices as input (n 1). I.e., the rst curve segment is de ned by control points fp1; p2; p3; p4 g, the second by fp4; p5; p6; p7g, etc. You need to loop over the input control points and feed the proper subsets to the coreBezier function. You need to string the results of coreBezier together in the output vector of tessellated points.




The sample function evalCircle shows how to use the CurvePoint and Curve classes. You’ll only need to ll in the V member of the CurvePoints; the normals and others are for extra credit.




See the slides on spline curves for more in-depth information about the underlying math!







R2 B-splines (2 p)




Evaluate a B-spline curve in evalBspline. As you already have the code for evaluating points on a Bezier curve from R1, it’s best to just change the basis from B-spline to Bezier, and use the code you already wrote. This is the bene t of generality we’ve talked about in class!




Similar to evalBezier, you should loop over the input control points. Remember that B-splines build the curve with a sliding window that only increases by one at each round; the rst segment is built from control points fp1; p2; p3; p4g, but di ering from the above, the second uses control points fp2; p3; p4; p5g, etc.




For each such subset, put the four control points in a 4x4 matrix and apply the B-spline-to-Bezier conversion matrix (that you know how to build). Then read o the new control points, now in the Bernstein basis, o the columns of the resulting matrix, and pass them on to evalBezier.




After completing this part, the camera animation system (example in swp/campath/sponza.swp) works partially { the position is correctly animated, but the camera looks in a constant direction. Fixing this is an extra credit assignment.

 Loop Subdivision Surfaces






In this part of the assignment, you are to implement triangle mesh subdivision using the Loop scheme. Algorithms like this are the core building blocks of all modern modeling systems!




The basic idea is to subdivide each triangle in the input mesh into four new triangles, and to carefully compute positions for the new vertices and the old vertices in a way that results in a smooth surface when we keep subdividing. In the limit, we get a surface that is actually mathematically smooth almost everywhere. Choosing the appropriate ways of computing the positions is deep and fascinating, but fortunately, implementing a subdivision scheme does not require one to understand why. (Phew.) While you should be able to ful ll the requirements using this document only, we heartily recommend you check out Denis Zorin and his colleagues’ SIGGRAPH course notes on subdivision to nd out more. You’ll nd that Loop’s algorithm is a popular, but by no means only choice of subdivision algoritm, for instance.




You will nd the code you need to complete in Subdiv.cpp. The class MeshWith-Connectivity is the one where the heavy lifting happens.







3.1 Debug tools




If you run into problems with for example indexing the triangles when generating the one-ring (see R5 description,) it might help to use the provided debug highlight functionality to see what your code does. If you press alt while you have a model loaded, the debug code rst nds the vertex your mouse is currently pointing at, then runs the one-ring generation code only for that one vertex. When LoopSubdivision is running in this debug mode, the debugPass boolean will be set to true. You can then push vertex indices into the highlightIndices vector to highlight those vertices as large red points in the GL view. The solution executable demonstrates this by highlighting the one-ring around the chosen vertex. You can naturally customize what happens in the debug pass if you want to debug some other aspect of the subdivision algorithm.







3.2 Warmup: Connectivity Information




In subdivision algorithms, it is important that vertices are shared between adjacent triangles. This is easiest if the position for each vertex (as well as its color, nor-mal, etc.) are only stored once, and the triangles refer to these tables by indices. In MeshWithConnectivity, the positions, normals, and colors are stored in the member vectors positions, normals, and colors.




Now, we specify each triangle as a sequence of three indices into a vertex table, which would look something like shown in Figure 2, left. We store the index information in the indices member of MeshWithConnectivity, de ned as std::vector<Vec3i> indices. So, each triangle has a 3-component vector of indices that describes the vertices. The posi-

 


tions of the three vertices of the ith triangle are then simply positions[indices[i][0]], positions[indices[i][1]], and positions[indices[i][2]].




Furthermore, we will need to know which triangles are connected to which other triangles. This is called connectivity information or mesh topology. In order to ful ll the require-ments, you need to understand and use the simple data structure described below, but its complete implementation is given to you in the starter code.




First, we de ne the three edges of a triangle as follows. For each triangle,




The rst edge e0 runs between vertices i0 and i1,



The second edge e1 runs between vertices i1 and i2,



The third edge e2 runs between vertices i2 and i0.



Note that since we always specify the vertices of triangles in consistent (either clockwise or counterclockwise, but not mixed) order, these edges are directed.




Now, with this de nition in hand, information about neighboring triangles can be stored in another table of three integers per triangle, as shown in Figure 2, middle. In our starter code, this is the neighborTris vector. The table simply says, for each triangle, what is the index of the triangle on the other side of each of the edges, which are numbered as above. Take a moment to convince yourself that the indexing of the vertices, triangles, edges, and neighbors you see in the two gures indeed makes sense. If a triangle does not have a neighbor on the other side of some edge, we denote it with a 1. You will not have to worry about it to ful ll requirements, though.




This is not quite enough information yet. In addition to the index of the neighboring triangle, we encode, for each edge of each triangle, what is the index of the corresponding edge of the neighboring triangle. For instance, the rst edge of triangle 1 consists of vertices 4; 6. (Verify this in the index table!) But in the neighboring triangle 7 { verify that the rst entry for triangle 1 in the neighbor table is indeed 7 { the corresponding edge 6; 4 is not the rst, but the third edge! Verify also this from the index table. In general, there is no way to be sure what these correspondences are except by looking at the actual data, so we encode this in a third array of three integers per triangle called neighbor edges, and we put a 2 in the rst position for triangle 1. This table encodes the information \for each edge in the mesh, what is the index of the corresponding edge in the neighboring triangle." In the starter code, this is the neighborEdges vector. Together, neighbor triangle and neighbor edge indices encode all we need to know about connectivity on the mesh.




Figure 3 shows a simple triangle mesh. The rst step of the Loop algorithm is to insert a new vertex in the middle of each edge in the input mesh.







3.3 Starter code




The starter code has all the structure you need; you just have to ll in the proper handling of a few things, all in the LoopSubdivision function. The code already lls in all the

    







    









                                   















































































































































































































      











      





      





    







    

















        





































































      













    



    



 


into new vertices so that we keep track of its index properly (and don’t try to insert it another time). You can use the array index operator [] for doing this. This is super easy, and just introduces you to what is happening.







With the new vertex data at hand, build the new triangle list at the bottom of the le. For each old triangle, you create four new ones, according to the gure. The old indices are given in the triplet even. Build the similar vector of 3 ints odd using the information from new vertices. For this, you will need to query new vertices to get the index of each new vertex added to the middle of each edge of the old triangle. You can use make pair, similar to the construction of edge earlier in the same method, to build the corresponding pairs of ints (i.e. edges) for each edge, and query the map with the array index operator [], as you know you are always going to nd the right values. When you’ve fetched the indices of the odd (new) vertices, remove the last line of the loop from the starter code (which just outputs a single triangle with the old vertices), and replace it with four push back()s that properly build the new triangles out of the odd and even indices you now have at hand.










R4 Positions for odd (new) vertices (2 p)




Now that you can see the results of the planar subdivision, let’s actually do it using Loop’s method! The idea is to weigh the nodes such that the surface gets smoother and smoother as the level of subdivision increases. Figure 4 illustrates what the weights are. For each new vertex, there is exactly four surrounding vertices to take into account.




In the rst nested loops in MeshWithConnectivity::LoopSubdivision(), you are going to compute the proper weighted average of the four relevant input vertices instead of merely placing the new vertices into the middle of the original edge like the starter code does. To do this, you are going to need the connectivity information.




Again, the nested loops iterate over each edge of each triangle. At each iteration, the variables v0 and v1 are the endpoints of the edge we are looking at. We merely need two more vertices: the ones on the opposite sides of the triangles on both sides of the edge. Getting the rst one is easy: we are at triangle i and the edge that starts from its jth vertex; you know perfectly well how to get the one thats two steps ahead of the start vertex (look at the beginning of the inner loop). Getting the one on the other side of the edge is almost as simple. Use the connectivity structure to get the index of the triangle on the other side and the index of the edge that corresponds to the current one; then you can just walk around the other triangle two steps like you just did in this current triangle.




Once you’ve found the indices of all the relevant vertices, compute new positions, normals, and colors using the weights from the gure instead of the simple midpoint given in the starter code. Careful thinking with pen and paper helps here; draw lots of arrows. Use the weights 3=8 for v0 and v1.




Handling mesh boundaries is not needed for the requirement, but your code must not crash when encountering a boundary. Simply checking neighbor indices against -1, and setting the fourth vertex position to 0 will be enough. Doing boundary handling properly

 


is an extra, and can be found in the recommended section.







R5 Repositioning the even (old) vertices (2 p)




After implementing R3 and R4, the supplied icosahedron looks like a spikeball. The old vertices must also be repositioned, again as in the gure 4. You have to loop through the neighbors of the vertex in question. By looking at the neighbor information illustrated in gure 1, this is surprisingly easy. You have to use the neighbor triangle and edge information to walk to the next vertex.




The second loop given in the starter code in MeshWithConnectivity::LoopSubdivision() (after the nested ones) will nd you a vertex v0 and an edge emanating from that vertex




the jth edge of triangle i. Clearly, indices[i][(j+1)%3], the other end of the jth edge, will get you a vertex that’s connected to v0. Great, you’ve found one already!



The mental model that will lead you to the goal is simple. The idea, now, is to loop around all the other edges that emanate from the vertex v0 by jumping from triangle to triangle until you hit the one you started at. It turns out that this is really simple to do using the connectivity information we have stored; when you’ve done this properly, you have a simple loop that starts from triangle i and edge j, updates the current triangle and edge by walking the connectivity, and keeps doing this until the current triangle loops back to i. If you nd your code containing conditionals or other complex logic, you’ve gone astray! The end result is a really simple while loop.




Be careful with indexing! You will need a pen and lots of paper, but in the end, this is just one loop in about ten lines of code, and a few lines for the original position. It might also help to utilize the provided debug highlighting functionality. See the debug tools section above and code comments for more details.




Again, handling mesh boundaries properly is not needed for this requirement, but your code must not crash on triangle edges. It’s enough to simply check neighbor triangle indices against -1, and leave the vertex at its original position at this stage. If you want to do proper handling for mesh boundaries, you can nd an extra credit for it in the recommended section.

 Extra Credit






As always, you are free to do other extra credit work than what’s listed here. We’ll be fair with points, but if you want to attempt something grand, better talk to us beforehand.







4.1 Recommended




Proper handling of boundaries for Loop subdivision (3p). You can nd information on how to do this in Denis Zorin’s SIGGRAPH course notes and Matt Fisher’s simple Loop tutorial You can use the provided patch.obj for trying this out. We will update the solution exe to do the right thing as well.




Local coordinate frames on the curve (1 p). Compute local coordinate frames along the curve (as described towards the end of this document) and display them. You should render the curve in white, and the N, B, and T vectors in red, green, and blue, respectively. See more about this in the appendix.




The camera animation system (example in sponza.swp) uses the local frame as its orientation so instead of looking in a constant direction, the camera now looks forward along its path. Note that you need to toggle the camera path orientation mode on your UI to see this.




Surfaces of revolution (see appendix) (3 p). Generate and display surfaces of rev-olution (of a curve on the xy-plane around the y-axis) and compute the surface normals correctly. The starter code includes support for this, it’s the ’Draw curve’ button. The solution implements this, so you can check how the results should look like.




To get you motivated, here is an image that was generated using Maya from one of the swept surfaces that your program will create.

  




































































Generalized cylinders (appendix) (3 p). Sweep the spline as the outline of a cylinder along another curve. You are not required to precisely match the results of the

 


sample solution, as it includes a somewhat arbitrary choice of the initial coordinate frame. Again, this is included in the model solution, and some SWPs include generalized cylinders.




Other subdivision schemes (? p). Catmull-Clark, Doo-Sabin, etc. Make it pos-sible to change the scheme on the y, and maybe also to draw the di erent ones simultaneously to compare them.







4.2 Easy




While subdividing, assign new colors to the vertices based on how old they are to visualize how the smoothness develops. (1p)







4.3 Medium




Bezier interpolation for orientations (4p). Use Bezier splines to interpolate between orientation control points in the camera animation mode. The given sponza.swp contains a camera path with orientations encoded as quaternions. Since only two orientations can be combined in a sensible manner at a time, you’ll need to im-plement De Casteljau’s algorithm to interpolate the control points using spherical linear interpolation (slerp) and convert the resulting quaternion to an orientation matrix.




Implement another type of spline curve, and extend the SWP format and parser to accommodate it (3 p). We recommend Catmull-Rom splines, as they are C1-continuous and interpolate all the control points, but feel free to try others (Bessel-Overhauser, Tension-Continuity-Bias). If you implement this extension, please make sure that your code can still read standard SWP les, since that’s how we’re going to grade it. Additionally, provide some SWP les that demonstrate that they work as they’re supposed to.




-curves (4 p). Implement -curves, that are an alternative to Catmull-Rom splines, from Yan et al. (https://dl.acm.org/doi/pdf/10.1145/3072959.3073692). This method is used, e.g., in the Adobe Illustrator’s curvature tool that enables drawing curves without unintuitive loops and cusps. For full points it su ces that you implement the variant of -curves that assumes closed curves. A useful link to solving a cubic equation is: https://en.wikipedia.org/wiki/Cubic equation.




Isosurface extraction (5 p). Convert volume data to a triangle mesh using e.g. marching cubes: http://www.cs.toronto.edu/ jacobson/seminar/lorenson-and-cline-




1987.pdf. You can nd volumetric density data sets that you can use here: https://graphics.stanford.edu/data/voldata/




Implement another kind of primitive curve that is not a spline (? p). Preferably, pick something that’ll result in interesting surfaces. For instance, you might try a corkscrew shape or a Trefoil Knot. Both of these shapes would work great as sweep




 


curves for generalized cylinders. Again, you’ll probably want to extend the SWP format to support these sorts of primitives. We’ll be fair and give you points based on how elaborate your primitive is.




Adaptive step size (4 p). In this assignment, the suggested strategy for discretizing splines involves making uniform steps along the parametric curve. However, it is di cult to choose the appropriate number of steps, since the curvature of splines can vary quite a bit. In fact, any choice of a uniform step size will result in either too few steps at the sharpest turns, or too many in the straight regions. To remedy this situation, implement a recursive subdivision technique to adaptively control the discretization so that more samples are taken when needed. You will need to analyze the derivatives of the curve to get tight bounds.

  





















































Comparison on the wineglass object. Uniform step size (33120 faces) on the left, adaptive step size (18540 faces) on the right.







Render your surfaces (either subdivision surface or surfaces of revolution and gen-eralized cylinders) more interestingly (? p). Change the materials, or even better, change the material as some function of the surface. You might, for instance, have the color depend on the sharpness of the curvature. Or jump ahead of what we are covering in class and read about texture mapping, bump mapping, and dis-placement mapping. If you visualize curvature properly, you’ll get at least 3 extra points.







4.4 Hard




Implement piecewise Bezier and B-spline surfaces (3 p), i.e. surfaces with gaps in between. The description (and the sample code) only supports swept surfaces with C1-continuous sweep curves. This is all that is required, but it may be desirable to sweep curves with sharp corners as well. Extend your code to handle this function-ality for piecewise Bezier curves. If you do this extension, you should also extend the SWP format so that control points can be speci ed. Additionally, you should provide some sample SWP les to demonstrate that your technique will work.

 


Cylinder curve scaling (4 p). We can extend the generality of generalized cylinders by allowing the pro le curve to be controlled by other curves as well. For instance, you may wish to not only control the orientation of the pro le curve using a sweep curve, but the relative scale (\thickness" of the cylinder) of the pro le curve using a scale curve. This is more challenging than it may sound at rst, since you must worry about the fact that the sweep curve may not have the same number of control points as the scale curve.




Implement a user interface so that it is easy for users to specify curves using mouse control (5 p). A user should be able to interactively add, remove, and move con-trol points to curves, and those curves should be displayed interactively. This application may be implemented as an extension to your assignment code, or as a standalone executable. Either way, it should be able to export SWP les. You may choose to implement a purely two-dimensional version, or, for additional credit, a three-dimensional curve editor. If you choose the latter, you should provide an intu-itive way of adding and moving control points using mouse input (this is somewhat challenging, since you will be trying to specify and move three-dimensional points using a two-dimensional input device). See how the CommonControls object is used in the starter code to get an idea of how to add new UI-components. Provide a few sample SWP models and screenshots that you created with this UI. We might show the best ones in the lectures!




Terrain rendering on GPU (6 p). Check the blog post about Fast Terrain Rendering with Continuous Detail on a Modern GPU by Morgan McGuire. Implement the geometry part explained in the post. Generate a heightmap procedurally or with third party software such as World Machine. Setup a shader that uses the gener-ated heightmap to displace the geometry. Notice how the highest level of detail part of the geometry always stays below the camera. For full points, demonstrate the multiresolution approach taken in the geometry generation and rendering. Demon-strate that the geometry translates as the camera moves. You’ll probably have to implement a free moving camera as well. At this point you can leave the shad-ing/visual parts out. The shading/visual parts described in the post leave a lot of potential for extra credit later on.







4.5 Very hard




Subdivision surface tting (10 p). See e.g. papers Loop Subdivision Surface Fitting by Geometric Algorithms and Fitting Subdivision Surfaces.




Multiresolution editing of the subdivided surfaces (10 p). E.g. Mudbox and ZBrush work about like this. See Interactive Multiresolution Mesh Editing for ideas.







4.6 Tangential




The sample code will export your surfaces to OBJ format. Files in this format can be imported into a variety of 3D modeling and rendering packages, such as Maya.

 


This software has been used for a number of video games, feature lms (including The Lord of the Rings), and television shows (including, believe it or not, South Park). You may wish to make your artifact more interesting by rendering it in this software, or other 3D-modeling software. Since the course isn’t about learning software tools, you won’t receive extra credit for this. However, your artifact will look amazing when we post the images on the web for everyone to see. The image at the beginning of this document was generated using this software.







4.7 Research-grade extra




Filtering and lling in 3D laser scans 3D laser scanning devices such as LIDAR produce clouds of 3D points that represent the shape of the space being scanned. There are no triangles, just points! As they shoot laser pulses out from a central location, it’s simple to see why the density of the points drops with increasing distance from the scanner; furthermore, the locations of the points is not exact and some noise remains. And clearly, locations that are not visible to the scanner don’t get any points. (This is why large locations require multiple scans that are aligned and fused into one.)




In this assignment, download complex 3D scans from a suitable repository, such as this, write code for visualizing the point clouds interactively, and see what you can do in order to 1) remove noise and 2) ll in more points in areas of low density. You’re free (and are encouraged!) to consult research literature on nding potential approaches to try. You can also try to implement techniques for generating triangle meshes from the point clouds.




This assignment is vague and open-ended on purpose. Be sure to explain your approach, rationale, and references along with your results! Due to the open-ended nature of this assignment, you can turn your solution along with a future assignment round | you do not have to submit with Round 2. Preferably, write a description of your solution up in a separate PDF le that contains text and images detailing your solution.

 Submission



Make sure your code compiles and runs both in Release and Debug modes on Visual Studio 2019, preferably in the VDI environment. Comment out any func-tionality that is so buggy it would prevent us seeing the good parts. Check that your README.txt (which you hopefully have been updating throughout your work) accurately describes the nal state of your code.




Fill in whatever else is missing, including any feedback you want to share. We were not kidding when we said we prefer brutally honest feedback.




Package all your code, project and solution les required to build your submission, README.txt and any screenshots, logs or other les you want to share into a ZIP archive. Note: the solution le itself does not contain any code, make sure the contents of src/ are present in the nal submission.




Sanity check: look inside your ZIP archive. Are the les there? (Better yet, unpack the archive into another folder, and see if you can still open the solution, compile the code and run.)







Submit your archive in MyCourses folder "Assignment 2: Curves and Sur-faces".

 Appendix: Curve normals






Computing points on the spline is su cient if the only goal is to draw it. For other applications of splines, such as animation and surface modeling, it is necessary to generate more information.




We’ll go over these details rst in two dimensions and then go up to three.







A.1 Two Dimensions




Consider a simple example. Suppose we wanted to animate a car driving around a curve q(t) on the xy-plane. Evaluating q(t) tells us where the car should be at any given time, but not which direction the car should be pointing. A natural way to choose this direction is with the rst derivative of curve: q0(t).




To determine the appropriate transformation at some t, we introduce some shorthand notation. First, we de ne the position V as:







V = q(t)




We de ne the unit tangent vector T as:







= q0(t)=jjq0(t)jj



Then we de ne the normal vector N as a unit vector that is orthogonal to T. One such vector that will satisfy this property is:







= T0=jjT0jj



Then, if we assume that the car is pointed up its positive y-axis, the appropriate homo-geneous transformation can computed as:



























































































N T V

M= 0 0 1




Unfortunately, there is a problem with this formulation. Speci cally, if q has an in ection point, the direction of the normal will ip. In other words, the car will instantaneously change orientation by 180 degrees. Furthermore, if the car is traveling along a straight line, N is zero, and the coordinate system is lost. This is clearly undesirable behavior, so we adopt a di erent approach to nding an N that is orthogonal to T.




We introduce a new vector orthogonal to T that we’ll call B. This is known as the binormal, and we’ll arbitrarily select it to be in pointing in the positive z-direction. Given B, we can compute the appropriate normal as:

 


N=B T




Note that N will be unit and orthogonal to both B and T, because B and T are orthogonal unit vectors. This may not seem like the most intuitive method to compute the desired local coordinate frames in two dimensions, but we have described it because it generalizes quite nicely to three.







A.2 Three Dimensions




To nd appropriate coordinate systems along three dimensions, we can’t just use the old trick of selecting a xed binormal B. One reason is that the curve might turn in the direction of the binormal (i.e., it may happen that T = B). In this case, the normal N becomes unde ned, and we lose our coordinate system. So here is the solution that we suggest.




We will rely on the fact that we will be stepping along q(t) to generate discrete points along the curve. In other words, we might step along q(t) at t1 = 0, t2 = 0:1, and so on. At step i, we can compute the following values (just as in the two-dimensional case):










Vi = q(ti)




Ti = q0(ti).normalized()




To select Ni and Bi, we use the following recursive update equations:










Ni = (Bi 1 Ti).normalized()

Bi = (Ti Ni).normalized()










In these equations, normalized() is a method of Vector3f that returns a unit-length copy of the instance (i.e., v.normalized() returns v=jjvjj). We can initialize the recursion by selecting an arbitrary B0 (well, almost arbitrary; it can’t be parallel to T1). This can then be plugged into the update equations to choose N1 and B1. Intuitively, this recursive update allows the the normal vector at ti to be as close as possible to the normal vector at ti 1, while still retaining the necessary property that the normal is orthogonal to the tangent.




with the two-dimensional case, we can use these three vectors to de ne a local coordi-nate system at each point along the curve. So, let’s say that we wanted to animate this airplane:
   

































































And let’s say that we wanted to align the z-axis of the airplane with the tangent T, the x-axis with the normal N, the y-direction with the binormal B, and have the plane at position V. This can be achieved with the following transformation matrix:




 

NBTV

M= 0 0 0 1




And that summarizes one way to compute local coordinate systems along a piecewise spline. Although the recursive update method that we proposed works fairly well, it has its share of problems. For one, it’s an incremental technique, and so it doesn’t really give you an analytical solution for any value of t that you provide. Another problem with this technique is that there’s no guarantee that closed curves will have matching coordinate systems at the beginning and end. While this is perfectly acceptable for animating an airplane, it is undesirable when implementing closed generalized cylinders.







Appendix: Implementing Surfaces






Use the curves that you generated to create swept surfaces. Speci cally, the type of surfaces you are to handle are surfaces of revolution and generalized cylinders.




The following images show an example of a surface of revolution. On the left is the pro le curve on the xy-plane, and on the right is the result of sweeping the surface about the




-axis.
   
























































The images below show an example of a generalized cylinder. On the left is what we’ll call the sweep curve, and the surface is de ned by sweeping a pro le curve along the sweep curve. Here, the pro le curve is chosen to be a circle, but your implementation should also support arbitrary two-dimensional curves.

  







































































B.1 Surfaces of Revolution




For this assignment, we de ne a surface of revolution as the product of sweeping a curve on the xy-plane counterclockwise around the positive y-axis. The speci c direction of the revolution will be important, as you will soon see.




Suppose that you have already evaluated the control points along the pro le curve. Then, you can generate the vertices of the surface by simply duplicating the evaluated curve points at evenly sampled values of rotation. This should be your rst task during the implementation process.




However, vertices alone do not de ne a surface. As we saw from the previous assignment, we also need to de ne normals and faces. This is where things get a little more chal-lenging. First, let’s discuss the normals. Well, we already have normal vectors N from

 


the evaluation of the curve. So, we can just rotate these normal vectors using the same transformation as we used for the vertices, right? Yes, and no. It turns out that, if we transform a vertex by a homogeneous transformation matrix M, its normal should be transformed by the inverse transpose of the top-left 3 3 submatrix of M. A discussion of why this is the case appears in the Red Book. You can take comfort in the fact that the inverse transpose of a rotation matrix is itself (since rotation is a rigid transformation).




Another thing that you’ll need to worry about is the orientation of the normals. For OpenGL to perform proper lighting calculations, the normals need to be facing out of the surface. So, you can’t just blindly rotate the normals of any curve and expect things to work.




To appreciate this issue, observe the following Bezier curves. The di erence between them is that the normals (the red lines) are reversed. This is the result of just reversing the order of the control points. In other words, even though the curves are the same, the normals depend on the direction of travel.

  





















































In this assignment, we will assume that, for two-dimensional curves, the normals will always point to the left of the direction of travel (the direction of travel is indicated by the blue lines). In other words, the image on the left is correct. This is to be consistent with the fact that, when you’re drawing a circle in a counterclockwise direction, the analytical normals will always point at the origin. With this convention, you will actually want to reverse the orientation of the curve normals when you are applying them to the surface of revolution. Note that, if you implement two-dimensional curves as we described previously, you will automatically get this behavior.




We must also keep in mind that translating the curve may disrupt our convention. Con-sider what happens if we just take the curve on the left side, and translate it so that it is on the other side of the y-axis. This is shown below (the y-axis is the thick green line).

   












































Here, the normals that were once facing towards the y-axis are now facing away! Rather than try to handle both cases, we will assume for this assignment that the pro le curve is always on the left of the y-axis (that is, all points on the curve will have a negative x-coordinate).




So far, we have ignored the faces. Your task will be to generate triangles that connect each repetition of the pro le curve, as shown in the following image. The basic strategy is to zigzag back and forth between adjacent repetitions to build the triangles.

  



















































































In OpenGL, you are required to specify the vertices in a speci c order. They must form a triangle in counterclockwise order (assuming that you are looking at the front of the triangle). If you generate your triangle faces backwards, your triangles will have incorrect lighting calculations, or even worse, not appear at all. So, when you are generating these triangle meshes, keep this in mind. In particular, this is where our assumption of counterclockwise rotation about the y-axis comes in handy.

 B.2 Generalized Cylinders




By now, you should be ready to implement generalized cylinders. They are very much like surfaces of revolution; they are formed by repeating a pro le curve and connecting each copy of the pro le curve with triangles. The di erence is that, rather than sweeping the two-dimensional pro le curve around the y-axis, you’ll be sweeping it along a three-dimensional sweep curve.




Just as with surfaces of revolution, each copy of the pro le curve is independently trans-formed. With surfaces of revolution, we used a rotation. With generalized cylinders, we will use the coordinate system de ned by the N, B, T, and V vectors of the sweep curve. To put it in the context of a previous discussion, imagine dragging a copy of the pro le curve behind an airplane that’s ying along the sweep curve, thus leaving a trail of surface.




The process of selecting the correct normals and faces is very similar to how it is done for surfaces of revolution. We recommend that you write your triangle meshing code as a separate function so that it may be reused.




Here is a neat example of a generalized cylinder. First, let’s see the pro le curve and the sweep curve. Both of these are shown with local coordinate systems at points along the curves. Speci cally, the blue lines are the Ts, the red lines are the Ns, and the green lines are the Bs.

  

























































































The small curve is chosen to be the pro le curve, and the large one is chosen to be the sweep curve. The resulting generalized cylinder is shown below.

   











































































































































































































24