{"id":16,"date":"2016-07-17T19:50:38","date_gmt":"2016-07-17T16:50:38","guid":{"rendered":"http:\/\/icospheric.com\/blog\/?p=16"},"modified":"2018-04-04T15:05:56","modified_gmt":"2018-04-04T12:05:56","slug":"making-terraced-terrain","status":"publish","type":"post","link":"https:\/\/icospheric.com\/blog\/2016\/07\/17\/making-terraced-terrain\/","title":{"rendered":"Making Terraced Terrain"},"content":{"rendered":"<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-81\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/TerracedTerrainFeaturedImage.jpg\" alt=\"TerracedTerrainFeaturedImage\" width=\"720\" height=\"240\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/TerracedTerrainFeaturedImage.jpg 720w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/TerracedTerrainFeaturedImage-300x100.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/p>\n<h1>Introduction<\/h1>\n<p>Say what you want about infamous\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Godus\">Godus<\/a>, but it does have a rather nice visual style, and what I especially liked about it \u2014\u00a0that stylized terraced\u00a0terrain.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-83 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/GodusScreenshot.jpg\" width=\"720\" height=\"406\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/GodusScreenshot.jpg 720w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/GodusScreenshot-300x169.jpg 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/p>\n<p>I managed to somewhat replicate this\u00a0look and even took it a step further, implementing it on a spherical planet.<\/p>\n<blockquote class=\"twitter-tweet\" data-width=\"550\">\n<p lang=\"en\" dir=\"ltr\">Painting layered Godus-like terrain on a spherical planet <a href=\"https:\/\/twitter.com\/hashtag\/madewithunity?src=hash&amp;ref_src=twsrc%5Etfw\">#madewithunity<\/a> <a href=\"https:\/\/twitter.com\/hashtag\/screenshotsaturday?src=hash&amp;ref_src=twsrc%5Etfw\">#screenshotsaturday<\/a> <a href=\"https:\/\/twitter.com\/hashtag\/gamedev?src=hash&amp;ref_src=twsrc%5Etfw\">#gamedev<\/a> <a href=\"https:\/\/t.co\/5GNhsyqonG\">pic.twitter.com\/5GNhsyqonG<\/a><\/p>\n<p>&mdash; Icospheric Planetoid (@icospheric) <a href=\"https:\/\/twitter.com\/icospheric\/status\/703368822057730048?ref_src=twsrc%5Etfw\">February 26, 2016<\/a><\/p><\/blockquote>\n<p><script async src=\"https:\/\/platform.twitter.com\/widgets.js\" charset=\"utf-8\"><\/script><\/p>\n<p>Since then, many people have been asking about its implementation details. Here is how I did it.<\/p>\n<h1>High-Level Overview<\/h1>\n<p>The main idea behind such\u00a0terraced terrain: it is just another representation of a heightmap. Heightmaps are\u00a0probably the easiest and most popular way to generate terrains, so if you&#8217;re already using them, then you most likely\u00a0won&#8217;t need to change anything except mesh generation code.<\/p>\n<p>The high-level algorithm is as follows:<\/p>\n<ol>\n<li>Take heightmap-based surface.<\/li>\n<li>Cut it into slices with horizontal planes.<\/li>\n<li>Fill intersections between the planes and the heightmap.<\/li>\n<li>Connect planes with vertical walls.<\/li>\n<li>PROFIT!<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-44 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/2D_Terrain.png\" alt=\"\" width=\"620\" height=\"560\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/2D_Terrain.png 620w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/2D_Terrain-300x271.png 300w\" sizes=\"auto, (max-width: 620px) 100vw, 620px\" \/><\/p>\n<p>Or in three dimensions:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-35 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain.png\" alt=\"\" width=\"680\" height=\"620\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain.png 680w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain-300x274.png 300w\" sizes=\"auto, (max-width: 680px) 100vw, 680px\" \/><\/p>\n<p>And here is a top-down view:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-36 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain_TopDown.png\" alt=\"\" width=\"325\" height=\"293\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain_TopDown.png 325w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/3D_Terrain_TopDown-300x270.png 300w\" sizes=\"auto, (max-width: 325px) 100vw, 325px\" \/><\/p>\n<p>Notice how the mesh still in some way preserves those triangles of the heightmap.\u00a0What exactly happens here is that each\u00a0triangle of a heightmap surface\u00a0is replaced with a fragment of terraced terrain that consist of one or more &#8220;steps&#8221;.\u00a0The algorithm for converting a triangle to such steps will be as follows:<\/p>\n<ol>\n<li>Iterate through\u00a0all triangles made by heightmap data.<\/li>\n<li>For each triangle, find all planes that are crossed by this triangle, plus one more plane below.\u00a0This can be done by taking this triangle&#8217;s points with minimum and maximum heights and finding all planes whose heights are between those min\/max values.<\/li>\n<li>For each plane that we&#8217;ve just found, add\u00a0polygons to the mesh using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Marching_squares#Meandering_triangles\">meandering triangles<\/a> algorithm (which is similar to more widely known\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Marching_squares\">marching squares<\/a> algorithm, except it works with triangles, not squares); based on which points of the triangle are above or below the plane.<br \/>\nThere can be three fundamentally different cases of polygon configuration: when one, two or all three points of the triangle are above the plane (the picture below shows each one of them).<\/li>\n<li>Additionally, for each plane excluding the bottom one, add a &#8220;wall&#8221; polygon\u00a0connecting this plane\u00a0with the plane below.<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-45 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/Triangle-1.png\" alt=\"\" width=\"720\" height=\"259\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/Triangle-1.png 720w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/05\/Triangle-1-300x108.png 300w\" sizes=\"auto, (max-width: 720px) 100vw, 720px\" \/><\/p>\n<h1>Pseudocode Example<\/h1>\n<p>This is a slightly simplified pseudocode\u00a0implementation of the entire algorithm. It doesn&#8217;t deal with generation of polygon normals (which is quite straightforward) and assumes a flat terrain, rather than a sphere.<\/p>\n<pre>\/\/ This will store total number of the generated vertices, this is needed\r\n\/\/ to generate vertex indices for mesh polygons\r\niv = 0\r\n\r\nfor each triangle in mesh data:\r\n\r\n    \/\/ 3D vector coordinates of each point of the triangle\r\n    v1, v2, v3\r\n\r\n    \/\/ Each point's heights above \"sea level\". For a flat (non-spherical)\r\n    \/\/ terrain it's just the vertical component of the respective vector\r\n    \/\/ (\"y\" in case of Unity engine).\r\n    h1 = v1.y\r\n    h2 = v2.y\r\n    h3 = v3.y\r\n\r\n    \/\/ Min and max heights of the planes that cross the triangle (plus one\r\n    \/\/ plane below). Here we assume that planes are located at discrete\r\n    \/\/ heights, 1 unit apart from each other.\r\n    h_min = floor(min(h1, h2, h3))\r\n    h_max = floor(max(h1, h2, h3))\r\n\r\n    \/\/ Iterate through each plane\r\n    for (h = h_min; h &lt;= h_max; h++):\r\n\r\n        \/\/ This variable indicates, which case of the Meandering Triangles\r\n        \/\/ algorithm we're dealing with: one, two or three points of the\r\n        \/\/ triangle above the plane\r\n        points_above = 0\r\n\r\n        \/\/ Check for all 8 possible combinations of point locations relative\r\n        \/\/ to the plane, and narrow them down to three different mesh\r\n        \/\/ configurations.\r\n        \/\/ Note that in some cases we're swapping values so that points above\r\n        \/\/ the plane would always be in the same variables, this simplifies\r\n        \/\/ the actual generation of mesh polygons.\r\n        \/\/ (This code may probably be further optimized for better readability\r\n        \/\/ and\/or performance, but here is one of the ways to do it.)\r\n        if (h1 &lt; h):\r\n            if (h2 &lt; h):\r\n                if (h3 &lt; h):\r\n                    \/\/ All points are below the plane, no triangles will be\r\n                    \/\/ added to the mesh (should not be possible)\r\n                else:\r\n                    points_above = 1         \/\/ v3 is above\r\n                    \/\/ no need to swap values, they're already fine\r\n            else:\r\n                if (h3 &lt; h):\r\n                    points_above = 1         \/\/ v2 is above\r\n                    v1, v2, v3 = v3, v1, v2  \/\/ make it v3 instead\r\n                else:\r\n                    points_above = 2         \/\/ v2 and v3 are above\r\n                    v1, v2, v3 = v2, v3, v1  \/\/ make them v1 and v2 instead\r\n        else:\r\n            if (h2 &lt; h):\r\n                if (h3 &lt; h):\r\n                    points_above = 1         \/\/ v1 is above\r\n                    v1, v2, v3 = v2, v3, v1  \/\/ make it v3 instead\r\n                else:\r\n                    points_above = 2         \/\/ v1 and v3 are above\r\n                    v1, v2, v3 = v3, v1, v2  \/\/ make them v1 and v2 instead\r\n            else:\r\n                if (h3 &lt; h):\r\n                    points_above = 2         \/\/ v1 and v2 are above\r\n                    \/\/ no need to swap values, they're already fine\r\n                else:\r\n                    points_above = 3         \/\/ all vectors are above\r\n\r\n        \/\/ Since we've swapped values of the points, let's find their heights again\r\n        h1 = v1.y\r\n        h2 = v2.y\r\n        h3 = v3.y\r\n\r\n        \/\/ For each point of the triangle, we will also need its projections\r\n        \/\/ to the current plane and the plane below. Just set its vertical\r\n        \/\/ component to the plane's height\r\n\r\n        \/\/ Current plane:\r\n        v1_c = vector3(v1.x, h, v1.z)\r\n        v2_c = vector3(v2.x, h, v2.z)\r\n        v3_c = vector3(v3.x, h, v3.z)\r\n\r\n        \/\/ The plane below; these vertices will be used to make vertical \"walls\"\r\n        \/\/ between planes\r\n        v1_b = vector3(v1.x, h - 1, v1.z)\r\n        v2_b = vector3(v2.x, h - 1, v2.z)\r\n        v3_b = vector3(v3.x, h - 1, v3.z)\r\n\r\n        \/\/ Now we generate mesh polygons for each of the three cases\r\n        if points_above == 3:\r\n\r\n            \/\/ The simplest case, just one triangle\r\n            add_mesh_vertex(v1_c)\r\n            add_mesh_vertex(v2_c)\r\n            add_mesh_vertex(v3_c)\r\n            add_mesh_triangle(iv, iv + 1, iv + 2)\r\n            iv += 3\r\n\r\n        else:\r\n\r\n            \/\/ Here we need to find locations of new points that are located on\r\n            \/\/ the sides of the triangle's projections.\r\n            \/\/ (See images below for a visual explanation.)\r\n            \/\/ We do that by interpolating between vectors based on their heights.\r\n\r\n            t1 = (h1 - h) \/ (h1 - h3)  \/\/ Interpolation value for v1 and v3\r\n            v1_c_n = vector3.lerp(v1_c, v3_c, t1)\r\n            v1_b_n = vector3.lerp(v1_b, v3_b, t1)\r\n\r\n            t2 = (h2 - h) \/ (h2 - h3)  \/\/ Interpolation value for v2 and v3\r\n          \u00a0 v2_c_n = vector3.lerp(v2_c, v3_c, t2)\r\n            v2_b_n = vector3.lerp(v2_b, v3_b, t2)\r\n\r\n            if points_above == 2:\r\n\r\n                \/\/ Add \"roof\" part of the step\r\n                add_mesh_vertex(v1_c)\r\n                add_mesh_vertex(v2_c)\r\n                add_mesh_vertex(v2_c_n)\r\n                add_mesh_vertex(v1_c_n)\r\n                add_mesh_triangle(iv, iv + 1, iv + 2)\r\n                add_mesh_triangle(iv + 2, iv + 3, iv)\r\n                iv += 4\r\n\r\n                \/\/ Add \"wall\" part of the step\r\n                add_mesh_vertex(v1_c_n)\r\n                add_mesh_vertex(v2_c_n)\r\n                add_mesh_vertex(v2_b_n)\r\n                add_mesh_vertex(v1_b_n)\r\n                add_mesh_triangle(iv, iv + 1, iv + 2)\r\n                add_mesh_triangle(iv, iv + 2, iv + 3)\r\n                iv += 4\r\n\r\n            else if points_above == 1:\r\n\r\n                \/\/ Add \"roof\" part of the step\r\n                add_mesh_vertex(v3_c)\r\n                add_mesh_vertex(v1_c_n)\r\n                add_mesh_vertex(v2_c_n)\r\n                add_mesh_triangle(iv, iv + 1, iv + 2)\r\n                iv += 3\r\n\r\n                \/\/ Add \"wall\" part of the step\r\n                add_mesh_vertex(v2_c_n)\r\n                add_mesh_vertex(v1_c_n)\r\n                add_mesh_vertex(v1_b_n)\r\n                add_mesh_vertex(v2_b_n)\r\n                add_mesh_triangle(iv, iv + 1, iv + 3)\r\n                add_mesh_triangle(iv + 1, iv + 2, iv + 3)\r\n                iv += 4<\/pre>\n<p>&nbsp;<\/p>\n<table>\n<tbody>\n<tr>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-72 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_1_sm.png\" width=\"302\" height=\"406\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_1_sm.png 302w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_1_sm-223x300.png 223w\" sizes=\"auto, (max-width: 302px) 100vw, 302px\" \/><\/td>\n<td><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-73 size-full\" src=\"http:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_2_sm.png\" width=\"302\" height=\"406\" srcset=\"https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_2_sm.png 302w, https:\/\/icospheric.com\/blog\/wp-content\/uploads\/2016\/07\/Triangle_Vectors_2_sm-223x300.png 223w\" sizes=\"auto, (max-width: 302px) 100vw, 302px\" \/><\/td>\n<\/tr>\n<tr>\n<td style=\"text-align: center;\">points_above == 1<\/td>\n<td style=\"text-align: center;\">points_above == 2<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h1>Conclusion<\/h1>\n<p>I hope this will help anyone who wants to implement such terraced terrain. There\u00a0is a lot more you can do with that, like different ways to apply colors to layers, adding baked ambient occlusion, or\u00a0maybe even using\u00a0some textures, it&#8217;s all up to you.<\/p>\n<p>For anyone who just wants to play around with such terrain without writing any code, you can have\u00a0a look at <a href=\"https:\/\/icospheric.itch.io\/planet-painter\">Planet Painter<\/a>, my free tool for editing spherical terrains, which supports both classic heightmaps and terraced terrain. You can even export the planets as 3D models and use in your Unity or other projects.<\/p>\n<p><iframe loading=\"lazy\" src=\"https:\/\/itch.io\/embed\/52245?linkback=true\" width=\"552\" height=\"167\" frameborder=\"0\"><\/iframe><\/p>\n<p>And of course feel free to ask me if you still have any questions, either here in comments, via email (<a href=\"mailto:icospheric@gmail.com\">icospheric@gmail.com<\/a>) or Twitter (<a href=\"https:\/\/twitter.com\/icospheric\">@icospheric<\/a>).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Introduction Say what you want about infamous\u00a0Godus, but it does have a rather nice visual style, and what I especially liked about it \u2014\u00a0that stylized terraced\u00a0terrain. I managed to somewhat replicate this\u00a0look and even took it a step further, implementing it on a spherical planet. Painting layered Godus-like terrain on a spherical planet #madewithunity #screenshotsaturday [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-16","post","type-post","status-publish","format-standard","hentry","category-articles"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/posts\/16","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/comments?post=16"}],"version-history":[{"count":39,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/posts\/16\/revisions"}],"predecessor-version":[{"id":94,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/posts\/16\/revisions\/94"}],"wp:attachment":[{"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/media?parent=16"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/categories?post=16"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icospheric.com\/blog\/wp-json\/wp\/v2\/tags?post=16"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}