Last Time More modeling 11 30 04 Hierarchical modeling Instancing and Parametric Instancing Constructive Solid Geometry Sweep Objects Octrees University of Wisconsin CS559 Fall 2004 Today Subdivision schemes Implicit surfaces Homework 6 due in class Project 3 ongoing 11 30 04 University of Wisconsin CS559 Fall 2004 Smooth versus General Polygon meshes are very general but hard to model with In a production context film game creating a dense accurate mesh requires lots of work Biggest problem is smoothness We desire a way to smooth out a polygonal mesh We can model at a coarse level and automatically fill in the smooth parts Subdivision surfaces are part of the answer 11 30 04 University of Wisconsin CS559 Fall 2004 Subdivision Schemes Basic idea Start with something coarse and refine it into smaller pieces smoothing along the way 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 Subdivision for fractal surfaces General subdivision surfaces 11 30 04 University of Wisconsin CS559 Fall 2004 Tessellating a Sphere Spheres are frequently 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 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 Isosahedron The First Stage Each face gets split into 4 11 30 04 Each new vertex is degree 6 original vertices are degree 4 University of Wisconsin CS559 Fall 2004 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 regular or 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 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 Fractal Terrain Example A mountainside 11 30 04 University of Wisconsin CS559 Fall 2004 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 Reducing the offset of new points according to the subdivision level is essential Define a scale s and a ratio k and at each level si 1 ksi Colors are frequently chosen based on altitude 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 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 11 30 04 University of Wisconsin CS559 Fall 2004 General Subdivision Schemes Subdivision schemes can also be used where there is no target surface They aim to replace a polygonal mesh with a smooth surface that approximates the coarse mesh There are many schemes 11 30 04 Butterfly scheme for triangular meshes Catmull Clark subdivision for mostly rectangular meshes Loop s scheme for triangular meshes Modified butterfly scheme for triangular meshes Many more University of Wisconsin CS559 Fall 2004 Modified Butterfly Scheme Subdivides the same way we have been discussing Each edge is split Each face is split into four Rules are defined for computing the splitting vertex of each edge Basic rule for a uniform region Splitting an edge with endpoints that have degree 6 As before all new interior vertices will have degree 6 Take a weighted sum of the neighboring vertices Weights define rules http www gamasutra com features 20000411 sharp 01 htm 11 30 04 University of Wisconsin CS559 Fall 2004
View Full Document
Unlocking...