DOC PREVIEW
UW-Madison CS 559 - CS 559 Lecture Notes

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Last TimeTodaySmooth versus GeneralSubdivision SchemesTessellating a SphereSubdivision MethodThe First StageSphere Subdivision AdvantagesFractal SurfacesFractal Terrain (1)Fractal Terrain ExampleFractal Terrain DetailsFractal Terrain AlgorithmSubdivision OperationsData Structure IssuesGeneral Subdivision SchemesButterfly SchemeButterfly Scheme (1)Data StructuresModified Butterfly SchemeSlide 21BoundariesModified Butterfly Example4/15/04 © University of Wisconsin, CS559 Spring 2004Last Time•More modeling:–Hierarchical modeling–Instancing and Parametric Instancing–Constructive Solid Geometry–Sweep Objects–Octrees–Blobs and Metaballs and other such things4/15/04 © University of Wisconsin, CS559 Spring 2004Today•Subdivision schemes•Homework 6 due April 20•No lecture April 224/15/04 © University of Wisconsin, CS559 Spring 2004Smooth 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 answer4/15/04 © University of Wisconsin, CS559 Spring 2004Subdivision 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 surfaces4/15/04 © University of Wisconsin, CS559 Spring 2004Tessellating a Sphere•Spheres are frequently parameterized in polar coordinates:–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 degree22 ,20sin ,cossin ,coscos zyx4/15/04 © University of Wisconsin, CS559 Spring 2004Subdivision 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•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 verticesOctahedronIsosahedron4/15/04 © University of Wisconsin, CS559 Spring 2004The First StageEach face gets split into 4:Each new vertex is degree 6, original vertices are degree 44/15/04 © University of Wisconsin, CS559 Spring 2004Sphere 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 areas4/15/04 © University of Wisconsin, CS559 Spring 2004Fractal 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 schemes4/15/04 © University of Wisconsin, CS559 Spring 2004Fractal 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 sphere4/15/04 © University of Wisconsin, CS559 Spring 2004Fractal Terrain ExampleA mountainside4/15/04 © University of Wisconsin, CS559 Spring 2004Fractal 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”4/15/04 © University of Wisconsin, CS559 Spring 2004Fractal Terrain Algorithm•The hard part is keeping track of all the indices and other data•Same algorithm works for subdividing sphereSplit_One_Level(struct Mesh terrain)Copy old verticesfor all edgesCreate and store new vertexCreate and store new edgesfor all facesCreate new edges interior to faceCreate new facesReplace old vertices, edges and faces4/15/04 © University of Wisconsin, CS559 Spring 2004Subdivision 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 locations4/15/04 © University of Wisconsin, CS559 Spring 2004Data 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?4/15/04 © University of Wisconsin, CS559 Spring 2004General Subdivision Schemes•Subdivision schemes can also be used where there is no “target” surface•They aim to


View Full Document

UW-Madison CS 559 - CS 559 Lecture Notes

Documents in this Course
Filters

Filters

14 pages

Lecture 2

Lecture 2

24 pages

Clipping

Clipping

22 pages

Modeling

Modeling

33 pages

Filters

Filters

26 pages

Dithering

Dithering

33 pages

Lecture 4

Lecture 4

20 pages

Load more
Download CS 559 Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 559 Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 559 Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?