New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Comp Game Design

by: Ophelia Ritchie

Comp Game Design EECS 494

Ophelia Ritchie
GPA 3.8


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Engineering Computer Science

This 52 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 494 at University of Michigan taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/231549/eecs-494-university-of-michigan in Engineering Computer Science at University of Michigan.

Similar to EECS 494 at UM

Popular in Engineering Computer Science


Reviews for Comp Game Design


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15
EECS 494 Tigrm m WFat m Mt Rainier created by Manel Giuli with Terragen Outline 1 of 2 Possible data representations Tiles Heightmaps Terrain Meshes Mini casestudy Chips Autogeneration Fault Formation Midpoint Displacement Particle Deposition Other methods Outline 2 of 2 Tools L3DT Terragen Optimization methods Delaunay Triangulation ROAM and LCD CatmuIIClark Subdivision Algorithm 2D Representation Tiles 1 Pretty simple you have a set of tiles and a regularlyspaced grid Each grid in the square is occupied by a tile Square grid 45 view square grid same as the square grid Hexagonal grid 2D Representation Tiles 2 The tilebased approach is simple but it potentially suffers from ugliness because the transitions between tiles is much too harsh Many games employ a technique described by David Michael httpwwwgamedevnetreferencearticlesarticle934asp Of Samu Games httpwwwsamugamescomlI blend transitions between tiles 0 Rather than have lots and lots of tiles to implement transitions Michael implemented a precendenceand transparency approach 2D Representation Tiles 3 0 Here we have the eight tiles for Michael39s game39s map Terrains are arranged so that there is a strict precedence As Michael notes Precedence does not reflect the relative elevations of the terrain but is instead based on which terrains looks best when overlapping other terrains 2D Representation Tiles 4 16 possible edge transitions and 16 possible corner transitions 0 We can combine the edge transitions with the corner transitions to create all 256 possible transitions 0 Above are the transition templates Top are edge transitions Bottom are corner transitions Black areas are transparent grey are opaque 2D Representation Tiles 5 Imdim mlWl39 F iiii imi ii mH 0 An artist uses these transitions to create the 32 30 terrain transitions for each tile type 0 Many more extra tiles but not exponentially more 2D Representation Tiles 6 Drawing is a twostep process For each cell in your grid Draw the base terrain Then draw any transition overlays in reverse order of precedence Heightmaps 1 Essentially a 2D array of pixels Normally in the range 0255 Black pixels are the lowest light pixels the highest Generally we use a clouds filter in Photoshop plasma in the Gimp Perlin Noise or some such technique to create a noisy but smooth image 0 We translate each point in a grid by a factor of the corresponding pixel in the image Heightmaps 2 Can you spot the potential problem hint think ofjagged terrains Heightmaps regularlyspaced grids and trianglebased terrains How should we triangulate this quad Heightmaps regularlyspaced grids and trianglebased terrains Two possibilities There are a couple of solutions you could try Allow your terrain editor to switch diagonals for a given quad Constrain all quads to be planar Heightmap limitations What kind of terrain formations can we not represent with a simple heightmap Heightmap m ta ons What kind of terrain formations can we not represent with a simple heightmap Also overhangs Devil39s Tower type landforms etc Heightmap limitations There are a few ways we can solve this problem Only use heightmaps for the initial generation then sculpt terrain as we see fit and be sure not to do anything with the terrain that requires 2D topology Treat these types of formations as nonterrain objects which we place on the terrain grid AFTER formation Apply modifiers to the terrain which nondestructiver transform the geometry late in the terrain pipeline Have a layer of say three heightmaps the bottom one of which is our base the middle one a kind of ceiling heightmap and the top one another base Intersections of the heightmaps are the boundaries at which it changes overhang to underhang and vice versa This won39t work for bridgeunderabridge though Delaunay Triangulation We want to figure out a way to reduce the number of vertices and triangles in our terrain mesh We also want to reduce the number of very thin sliver triangles in our mesh probably we can render the same scene with fewer larger triangles This is where Delaunay Triangulation becomes useful lntuitively Delaunay Triangulation takes a set of points and triangulates them httpwwwcscornelledulnfoPeoplechewDelaunayhtml Delaunay Triangulation The Delaunay Triangulation in a nutshell is one in which every edge has satisfied the Delaunay property That is to say the circumcircle that contains the vertices of the edge and the other one of the first triangle does not contain the opposing vertex and vice versa Delaunay triangulations are unique Delaunay Triangulation Michael Garland and Paul S Heckbert described an algorithm that takes as input a heightmap and creates a Delaunay triangulation for that heightmap It is an iterative refinement algorithm we stop when the error is small enough Greedy algorithm 39 httpwwwbowdoinedutomateachingcsBSOspringO4Handoutsscapepdf Delaunay Triangulation Ummmlt mumo Delaunay Triangulation Delaunay Triangulation quot V WWW4m 1 I A P 1 a 55A VA1 A Chips 0 Has many of the benefits of both tileassembly and heightfield like surfacing Create a set of chips with a heightmap terrain tool These chips don39t have to be square they can be long or Lshaped for example Assemble the chips in another tool Where chips meet add points a la Delaunay or Contrained Delaunay and average heights or better yet smooth across an area Terrain Autogeneration It39s easier and more realistic in many cases to get the computer to create the landscape for us 0 These are often referred to as fractal terrain generation These techniques are especially useful for VERY BIG maps and dynamic maps For big maps we might not have enough resources to pay artists to create big worlds for us For dynamic maps well they39re created at runtime Especially for static maps we can always tweak the map after autogeneration with a 3D tool Terrain Autogeneration Fault Formation First all cells of the heightmapto 0 Draw a line across the cell Raise all cells on one side of the line by a certain amount Continue like this drawing lines and raising one side but with each iteration we decrease the amount by which we raise If we want a smoother terrain no problem just apply a smooth eg blur filter Terrain Autogeneration Fault Formation Terrain Autogen Midpoint Displacement Forthe 2D case take a line segment and find its midpoint Insert a vertex in that midpoint and translate it up or down by some random amount Recursiver apply the same procedure on the two new connected line segments 4gtr 1 Terrain Autogen Midpoint Displacement Continue until you reach a sufficient level of detail Useful for 2D autogeneration Terrain Autogen Midpoint Displacement 3D is the same idea we just operate and recurse on square fragments of the map The Diamondsquare algorithm l l g l 7 3 33 Terrain Autogen Particle Deposition The idea is that we choose a point on the map and deposit particles that is add to the heightmap over and over again Particles will fall to their neighbor which neighbor is randomly determined if they can I J j 39rl39h l LLL Terrain Autogen Particle Deposition We can occasionally move the point of deposition so as to not create one big island or mountain 0 We can also create calderas by treating deposits past a certain threshold as subtractions in height rather than additions These subtractions are applied at the end effectively inverting those areas Terrain Autogen Particle Deposition Terrain Aut ogeneration Hills httpwww robotfrogcom3dhillshillhtml 5 ite rati n n 5 2EIZI iterations Terrain Autogeneration Cellular Automata httpwwwcs ubc cavanGI2005PostersWijayaCaleeGI2005PosterAbstract pdf Terrain Autogeneration Which is best Which method is best Well there is no best Different techniques produce different results Several techniques in concert that is to say in additive sequence can be used to get the best of all worlds Terrain Autogeneration Autotexturing We can get automatically texture terrain based on the features of the terrain One simple example might be Region1Snow 256192 Region2Rock 192128 Region3Grass 12864 Region4Sand 640 At the boundaries we blend between features As we39ll see programs like L3DT do this and we can configure which textures correlate to which heights Terrain Autogeneration Autotexturing L3DT Very sophisticated autogenerator Very large maps possible Start with a design map which you can alter that serve as seeds for the creation of terrain features Lots of realistic terraincreation techniques eg several types of erosion channeling erosion thermal erosion etc water table flooding creation normal creation attribute creation texture creation and more 0 You can export all of these generated tables eg as a BMP httpwwwbundysoftcomL3DT T Texture map Terragen Less sophisticated generation than L3DT for example But intool editing is supported As is a 3D renderer httpwwwpanetsidecoukterragen ROAM Realtime Optimaly Adapting Meshes This is a way of reducing the number of triangles that we send to the rendering pipeline This algorithm belongs to a class of algorithms called Level of Detail LOD algorithms LOD algorithms in a nutshell render small detailed triangles CLOSE to the camera Render large rough triangles far away from the camera All triangles once transformed to projection space should have about the same area r00 ROAM ROAM recursively partitions the landscape into pairs of isosceles right triangles Mimi L I Lml a m I AAAN1 The closer the camera is the deeper we render ROAM sample httpwwwgamasutracomfeatures20000403turner01htm ROAM Notice in the sample we39re sending more triangles to the pipeline than we apparently need eg triangles way outside of the viewing volume Why 3 my d lt9 r ll quot tquot J L U Notice in the sample we39re sending more triangles to the pipeline than we apparently need eg triangles way outside of the viewing volume Why To avoid cracking CatmullClark Subdivision Algorithm Developed by E Catmull of Pixar and J Clark Nondestructive geometry recursive subdivision and smoothing algorithm Iterate until it looks good enough httpsymbolcraftco mgraphicssubdivision CatmullClark Subdivision Algorithm Let the original vertices denote the input vertices for our algorithm or iteration First calculate the center of each face These are called the face points 0 Create new edge points for each edge Each new edge point position is the average of three vertices the position of the midpoint of the original edge and the position of the face point for the two adjacent faces 0 Connect face points to edge points with new edges The positions of the original vertices are then recalculated as the weighted average of the original vertices the midpoints of the edges that shared the old vertex and the face points surrounding the old vertex


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.