1. 2D Hull [25 + 8 = 33]
(a) Initialization:  There are 2 initialization modes:
- The default is “r” (random). The user may have entered a number N on the command line with your program, or perhaps a right-click menu option. Generate N unique random vertices (if they forgot N, just generate a default of 100). Alternatively, they may select a menu item, which adds 100 more random points each time selected.
- The user can type “m” and then interactively enter points with the mouse and cursor. “m” quits the input mode. Be sure to check that the vertices given by the user are unique (ignore any that are not).
When drawing the points from any input mode, use glPointSize so that they are large enough to see. (b) Convex hull:  Implement any one of the convex hull algorithms discussed in class on the vertices in part (a). A command “c” will begin the convex hull computation and rendering. Save the hull edges in a data structure (necessary for question 2).
(c) Hull peel:  Repeatedly apply the convex hull routine to the set of points to create a peel, which is as follows. Find the hull for the points and draw it. Remove these hull points from the set, and iterate on the remaining points. Continue until less than 3 points remain.
(d) Peels on point clusters. Select K random points in your set of points. K is supplied by user, and should be much less than the number of points total. For example, for 100 points, perhaps K=5. Then divide all the points in the set into 5 sets, where the points in each set is closest in distance to one of the 5 random points. Perform a hull peel on each of the 5 sets, and colour the peels on each of the K sets a different colour.
2. 2D Triangulation [25 + 8 = 33]
- Initialization:  See 1(a) above.
- 2D Triangulation: [10(trisection)+8(cleanup)=18] Implement the trisection/cleanup triangulation algorithms discussed in class. The command line should be: “triangulate N”, where N is the number of random points to use (OR, use a right-click GLUT menu selection). Draw the result. Save the triangles in a data structure. Count and print the number of random vertices and triangles created. In the case of the trisection, draw the progress of the cleanup algorithm as it runs. Count the number of times triangles were restructured, and print this number at the end.
- Lattice:  Apply the above to an N-by-N lattice of points. You might wish to have a special command to set up this data.
(d)Surface of a 3D function: Letting the user select random points (a) and lattice (b) from the main question, let the 2D triangulated polygons define the polygonal mesh of the surface of a 3D function: y = f(x, z). (Note: we will treat the 2D version as vertices on the X-Z plane — more explanation of this in class!) Let the user select between 3 different 3D functions that you supply. For example:
y = sin(x)*cos(y)*x*y
The coordinate system should be centered around (0,0,0), and X and Z should be permitted to be positive and negative. Then perform a 2D triangulation on the points, by applying it only to the (X,Z) coordinates (the triangulation in the main question does this). The resulting triangulation will take the form of polygons on the surface of the function. Insert the computed Y values into the vertex coordinates, and plot the 3D surface in OpenGL. The other 2 functions you supply should similarly be centered on the origin, with positive/negative X and Z values. Note that you should compute the Y values just once, and save the (X,Y,Z) coordinates in a table for efficient rendering in 3D. Use the code in “rotate2.c” to spin the surface in 3D, under user control.
3. 3D Convex Hull [25 + 8 = 33]
- Initialization:  K unique random points in 3-space are generated (K is a command-line parameter; default 100). You should set in X, Y, and Z directions.
- Centre of gravity:  Find the centre of gravity (avg coordinate) of the points in (a), and draw it as a large red dot or polygon.
- Convex hull:  Implement the greedy convex hull algorithm for 3 dimensions. Note that, instead of finding the distances between points and lines, you’ll find distances between points and planes. You should store the hull in a data structure of polygons. A simplification is that you can assume that there will never be more than 3 co-planar points on a hull polygon. If you find more than 3 (i.e. fast distance of point to plane is zero for 4+ points), delete the extra points so that you have 3 distinct points on the plane that are not collinear).
- Rendering:  Draw the 3D hull from (c) by defining an appropriately sized volume with glOrtho. The hull should be centered in the middle of the volume, and the volume should be centered on the origin (0,0,0), with equal ranges positive and negative on the 3 axes. You will also need to use the Zbuffer. One command key will draw the hull using flat-shaded randomly coloured polygons. Another key will display the hull as a wire frame. Use the scheme in the file “rotate2.c” to spin your 3D hull interactively.
(e)3D spherical hull peel. Define a loop that creates a new set of random points a distance d from the origin (0,0,0), computes and renders its hull, and then repeats the process a given number of times for smaller and smaller d values. The result should be a set of concentric hulls. They will tend to look like spheres if you use many points. Render the result using transparent surfaces (OpenGL’s alpha channel). You may also want to spin your object in 3D (see (d) above). This object is also easy to apply OpenGL lighting onto, because vertex normals are identical to vertex coordinates on a unit sphere centered at (0, 0, 0).
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx