Last Time B splines Recall a property of B spline surfaces the control point grid must be rectangular Project 3 was made available Today Subdivision schemes Homework 6 available B splines as Approximation B splines were developed as approximation functions Given a set of points the control points the B spline approximates them with a smooth curve or surface Ideally we would like to be able to provide a polygonal mesh and then smooth it out with a B spline surface The 3D equivalent of smoothing a 2D poly line with a B spline But we can t do this in general because B spline control meshes must be rectangular Can t even to simple cases like a sphere Subdivision Schemes Basic idea Start with something coarse and refine it into smaller pieces smoothing along the way We have seen how subdivision may be used to render parametric curves and Bezier surfaces We will see how it can be used for modeling specific objects and as a modeling scheme in itself In this lecture Subdivision for tessellating a sphere and implementation details Subdivision for fractal surfaces Subdivision for B spline patches General subdivision surfaces Tessellating a Sphere Spheres are best parameterized in polar coordinates x cos cos y sin cos z sin 0 2 2 2 Note the singularity at the poles Tessellation The process of approximating a surface with a polygon mesh One option for tessellating a sphere Step around and up the sphere in constant steps of and Problem Polygons are of wildly different sizes and some vertices have very high degree Subdivision Method Begin with a course approximation to the sphere that uses only triangles Two good candidates are platonic solids with triangular faces Octahedron Isosahedron They have uniformly sized faces and uniform vertex degree Octahedron Repeat the following process Insert a new vertex in the middle of each edge Push the vertices out to the surface of the sphere Break each triangular face into 4 triangles using the new vertices Isosahedron The First Stage Each face gets split into 4 Each new vertex is degree 6 original vertices are degree 4 Sphere Subdivision Advantages All the triangles at any given level are the same size Relies on the initial mesh having equal sized faces and properties of the sphere The new vertices all have the same degree Mesh is uniform in newly generated areas This is a property we will see later in subdivision surfaces Makes it easier to analyze what happens to the surface The location and degree of existing vertices does not change The only extraordinary points lie on the initial mesh Extraordinary points are those with degree different to the uniform areas Fractal Surfaces Fractals are objects that show self similarity The word is overloaded it can also mean other things Landscapes and coastlines are considered fractal in nature Mountains have hills on them that have rocks on them and so on Continents have gulfs that have harbors that have bays and so on Subdivision is the natural way of building fractal surfaces Start with coarse features Subdivide to finer features Different types of fractals come from different subdivision schemes and different parameters to those schemes Fractal Terrain 1 Start with a coarse mesh Vertices on this mesh won t move so they can be used to set mountain peaks and valleys Also defines the boundary Mesh must not have dangling edges or vertices Every edge and every vertex must be part of a face Also define an up direction Then repeatedly Add new vertices at the midpoint of each edge and randomly push them up or down Split each face into four as for the sphere Fractal Terrain Example A mountainside Fractal Terrain Details There are options for choosing where to move the new vertices Uniform random offset Normally distributed offset small motions more likely Procedural rule eg Perlin noise Scaling the offset of new points according to the subdivision level is essential For the subdivision to converge to a smooth surface the offset must be reduced for each level Colors are frequently chosen based on altitude Fractal Terrains http members aol com maksoy vistfrac sunset htm Terrain clouds generated using procedural textures and Perlin noise http www planetside co uk tool is called Terragen Terrain clouds generated using procedural textures and Perlin noise http www planetside co uk tool is called Terragen Fractal Terrain Algorithm The hard part is keeping track of all the indices and other data Same algorithm works for subdividing sphere Split One Level struct Mesh terrain Copy old vertices for all edges Create and store new vertex Create and store new edges for all faces Create new edges interior to face Create new faces Replace old vertices edges and faces Subdivision Operations Split an edge create a new vertex and two new edges Each edge must be split exactly once Need to know endpoints of edge to create new vertex Split a face creating new edges and new faces based on the old edges and the old and new vertices Require knowledge of which new edges to use Require knowledge of new vertex locations Data Structure Issues We must represent a polygon mesh so that the subdivision operations are easy to perform Questions influencing the data structures What information about faces edges and vertices must we have and how do we get at it Should we store edges explicitly Should faces know about their edges Edge Data iteration 1 The mesh must store all the edges because we need to loop over them to split them The edge must store its endpoints because we need them to split the edge A flag to turn off vertex perturbation is useful for boundary edges struct Edge int int bool v start Index of start vertex v end Index of end vertex no perturb Face Data Faces are triangles To split a face must know its vertices or edges Which To split the face needs to know where the new vertices and new edges are stored They were created when each edge was split Where do we store them so that the face can find them Face Data iteration 1 When an edge is split it makes sense to store the new vertex and new edges as part of the existing edge Faces can then store their edges and access the information for splitting from the edges Each edge is stored once so neighboring faces see the same information Edges may point forwards or backwards around a face and we must store this struct Face int edges 3 bool forward 3 Face Data When an edge is split it makes sense to store the new vertex and new edges as part of the existing edge Faces can then store their edges
View Full Document
Unlocking...