 <\/td><\/tr><\/table><\/p>\nThat seems like a ton of terrain data, and it is. Yet from the center to the edge is only 416 meters. Not even half a kilometer! Yeah. Filling in the world out to the horizon is tough<\/em>. It takes a lot of data. Most games don’t even go this far. I think Minecraft lets you see about 256 meters. I think Oblivion, Fallout 3, and New Vegas stop well short of half a kilometer. (Okay, FUEL had a massive view distance, but that was made by a real team of guys, so sue me.) <\/p>\nNow, my graphics card can handle this. In fact, it’s not even really trying. But throwing polygons at the graphics card like this is wasteful. Horribly, horribly wasteful. It’s not affecting my machine, but if this was a low-end machine, I’d really be slowing down. <\/p>\n I don’t actually want to work on this right now. The real bottleneck is on the CPU side, where my machine struggles to churn out the pages of data needed to fill<\/em> this terrain. By contrast, actually rendering<\/em> it is no big deal. That’s all handled by the GPU, which, as far as I can tell, is bored right now. Having said that, I can’t leave things like this. I need to make sure the terrain system works right before I move on, which means taking some basic steps to reduce polygon count. I don’t want to be one of those developers who writes inefficient engines and expects you to buy new graphics hardware to make up for it. <\/p>\nThis step is going to mean mucking about in the guts of my terrain engine, and it’s easier to do that now than later. Now the thing is fresh in my mind. Later I will be foggy on the details, and I’ll have a bunch of other systems built on top of it. <\/p>\n For polygon optimization, I’m going to go back to Peter Lindstrom and his magic method of polygon reduction, which I used way back in 2006, during my original terrain project<\/a>. Rather than make you go back and re-read that series, I’ll reprint the relevant steps here:<\/p>\n \n\n\nTo use a quad tree, our grid must<\/i> be a perfect square. It has to have the same width and height, and they must be a power of 2. In the terrain I’ve been using, the width and height is 32, which is 25<\/sup>. For our example here, let’s assume we’re working with an 8×8 grid, which is 23<\/sup>.\n<\/td>\n <\/td>\n<\/tr>\n | \n| \nThe main grid is divided into 4 quadrants. So, we have this sub-grid of 2 x 2. Then…\n<\/td>\n |  <\/td>\n<\/tr>\n | \n| \n…each of those squares is, in turn, divided into 4 quadrants. This yields a sub-grid of 4 x 4, which in turn can be divided further, and so on. <\/p>\n Anyway, this gives us a way to look at the grid at different levels of detail.\n<\/td>\n |  <\/td>\n<\/tr>\n | \n| \nMy program starts at the largest blocks on the 2 x 2 grid. Let’s say it examines the four blocks in question and determines that the lower-left one is a bit hilly, and needs to be divided further. The other three quadrants are flat enough that they can be left alone. So, we divide the lower-left block. <\/p>\n<\/td>\n |  <\/td>\n<\/tr>\n | \n| \nWithin that<\/i> block, we have 4 smaller blocks, and of those 4, we determine that the upper-right has some detail that needs to be preserved, but the other 3 are again simple enough that they can be left alone. Once again, we divide the one block into 4 smaller ones.\n<\/td>\n |  <\/td>\n<\/tr>\n | \n| \nAs you mark individual squares for use, you’re actually flagging points on the grid for use. When you do so, there’s this chain of other points you mark as used. You step up to the next largest spot on the grid, and flag a point as in-use. That point, in turn, reaches up to the NEXT larger square on the quad tree and flags a point for use, and so on, until you’re talking about the corners of the entire grid itself. <\/p>\n<\/td>\n |  <\/td>\n<\/tr>\n<\/table>\nThis is a really complicated system. The math behind it is trivial, but the rules controlling the points are confusing. Then turning those points into triangles is even worse. It took me a couple of days to figure it out the first time, and I don’t remember any of it five years later.<\/p>\n But!<\/p>\n In my least entry on project Hex, I mentioned the importance of comments<\/a>. Check out the comments I left in my old terrain project:<\/p>\n\/*-----------------------------------------------------------------------------\r\n North N \r\n *-------* *---+---* *---*---* *---+---*\r\n |\\ | |\\ \/| |\\Nl|Nr\/| | | |\r\n | \\ Sup | | \\ \/ | | \\ | \/ | | A | B |\r\n | \\ | | \\ \/ | |Wr\\|\/El| | | |\r\n | \\ | West+ * +East W*---*---*E *---+---* \r\n | \\ | | \/ \\ | |Wl\/|\\Er| | | |\r\n | Inf \\ | | \/ \\ | | \/ | \\ | | C | D |\r\n | \\| |\/ \\| |\/Sr|Sl\\| | | |\r\n *-------* *---+---* *---*---* *---*---*\r\n South S \r\n\r\n Figure a Figure b Figure c Figure d\r\n\r\nThis takes a single quadtree block and decides how to divide it for rendering. \r\nIf the center point in not included in the mesh (or if there IS no center \r\nbecause we are at the lowest level of the tree), then the block is simply \r\ncut into two triangles. (Figure a)\r\n\r\nIf the center point is active, but none of the edges, the block is cut into\r\nfour triangles. (Fig. b) If the edges are active, then the block is cut \r\ninto a combination of smaller triangles (Fig. c) and sub-blocks (Fig. d). \r\n\r\n-----------------------------------------------------------------------------*\/<\/pre>\nThank you, thank you, Shamus of 2006. Your ten minutes writing those comments just saved me a day and a half. There were a lot of wonderful notes in that thing, which allowed me to take the Lindstrom system and drop it into this Frontier project in just a couple of hours.<\/p>\n Note to self: You should be putting more comments in THIS project.<\/p>\n So the polygon reduction is gone, and we are left with a NEW problem. This problem:<\/p>\n  <\/td><\/tr><\/table><\/p>\nGaps. Removing polygons naturally changes the shape of the terrain. These changes cause the squares to no longer line up with each other. There are now gaps, where you can see between the blocks of terrain. Here is an example:<\/p>\n  <\/td><\/tr><\/table><\/p>\nThere’s a terrain right under us. (Pink) And other in front of us. (Yellow) At A, you can see that Pink needed a point that yellow didn’t, and at B you can see there was a point that yellow needed, but not pink. The way to reconcile this is to “stitch” them together. <\/p>\n Sigh. And this is why I didn’t want to have to do this step. I HATE stitching. It’s not hard or complex, but it feels… inelegant. See, programmers talk about encapsulation<\/em>. That’s the idea that you make a bit of code that does one thing, it does it well, and once it’s done you can treat it like a black box and not worry about how the insides work. The overall structure of the program should be as simple as possible, even if the individual parts are dauntingly complex. Each system should be connected to as few other systems as possible. <\/p>\nUp until now, terrains have been a lovely black box. I just make a terrain, tell it where it goes, and give it a few milliseconds between frames. The terrain block handles everything else. Now my terrain blocks have to interact with each other. Each one has to know about its four neighbors (if they exist!) and be able to negotiate with them to make sure their edges match. Which edge points is it using? Is that neighbor actually done building? Has it changed its edges recently, perhaps in response to some OTHER terrain block? Terrains are no longer just something you can create and forget about. Now you have to create them, and then help them find each other. <\/p>\n Now, this isn’t a horrible thing. It’s actually kind of trivial and not worth the two paragraphs I’m spending complaining about it. But when I have to add inter-connected stuff like this it makes me uneasy. It usually<\/em> means I need to re-think my design. Not always, though. Some problems are hard, and there’s nothing you can do but suck it up and deal with the complexity. <\/p>\n <\/td><\/tr><\/table><\/p>\n118,353 polygons. Less than a tenth of what it was before. And it looks exactly the same. <\/p>\n Well, we fixed something that wasn’t a problem and added a bit of complexity that I dislike, but the important thing is that it’s built right<\/em>. Somewhere there is a crappy laptop that will really appreciate the effort.<\/p>\nNext time we’ll add something cool.<\/p>\n","protected":false},"excerpt":{"rendered":" My project. Looking nice enough so far. But it has a problem. The problem is this: Those are triangles. A LOT of triangles.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-11991","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/11991","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11991"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/11991\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11991"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11991"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} |
|
|
| | |
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n