Subdivision Schemes Basic idea Start with something coarse and refine it into smaller pieces for rendering 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 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 Terrain clouds generated using procedural textures and Perlin noise http www planetside co uk tool is called Terragen Implementing Subdivision 1 We must represent a polygon mesh Basic operations Split an edge creating a new vertex Split a face creating new edges and new faces based on the old edges and the old and new vertices Questions influencing the data structures Should we store edges explicitly Should faces know about their edges How do we access the required information when performing the basic operations Implementing Subdivision 2 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 Note Everything works from edges Implementing Subdivision 3 Should we explicitly store edges Yes Easy to step through all edges and split them Each edge can store the edges that will replace it Each face can point to its edges so it knows the location of new vertices and edges What does each vertex need to store What does each edge need to store What does each face need to store Answers are in C but converting to C classes is easy Vertex Data Vertices need to know where they are and they will be copied as part of the algorithm For rendering may want Per vertex normals Compute at the end by averaging normals from faces that share the vertex Texture coordinates struct Vertex float x 3 float t 2 float n 3 int num faces Edge Data Need to know endpoints new vertex when split and new edges when split Store pointers as indexes into a list Also want to identify boundary edges which should not have vertices perturbed when split struct Edge int int int int int bool v start Index of start vertex v end Index of end vertex v new Index of new vertex e start Index of one sub edge e end Index of other sub edge boundary Face Data Faces are triangles that need to know Edges in a fixed order for rendering Complication Some edges point forward around the face some point backwards Store this info Normals for rendering or computing vertex normals Compute at the end struct Face int bool float edges 3 forward 3 n 3 Mesh Data Structure Mesh stores Vertices edges and faces The up direction for offsetting vertices struct Mesh int struct Vertex int struct Edge int struct Face float num vertices vertices num edges edges num faces faces up 3 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 General Subdivision Schemes
View Full Document
Unlocking...