{"id":15843,"date":"2012-05-09T04:16:42","date_gmt":"2012-05-09T09:16:42","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=15843"},"modified":"2012-05-09T05:40:37","modified_gmt":"2012-05-09T10:40:37","slug":"project-octant-part-5the-rainbow-collection","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=15843","title":{"rendered":"Project Octant Part 5:The Rainbow Collection"},"content":{"rendered":"

Today we’re finally going to start adding some features to make this thing look a bit more… What? You say you want another digression on noise filtering and interpolation techniques? You sure? Okay then! <\/p>\n

(Nerd!)<\/p>\n

If you remember from last time, we’re taking tables of random white noise and expanding them to create “interesting” patterns. Stuff like this:<\/p>\n

octant5_1.png<\/td><\/tr><\/table><\/p>\n

Now, I really don’t want to have the next bunch of images be black & white scramble squares. That’s boring and it’s actually hard to see the effect I’m talking about. So I’ve altered my program to output example images that will use color-blending to make the gradients more clear. So the above image now looks like this:<\/p>\n

octant5_2.png<\/td><\/tr><\/table><\/p>\n

Just remember we’re not really<\/em> dealing with color data right now. We’re actually just generating heaps of numbers between zero (dark blue) and one (red) and this color-fade makes it easier to see what we’re doing. Okay? Great. <\/p>\n

In the image above we’re looking at around 16×16 pixels, give or take the partials on the edges. We need to be able to expand this data and come up with values between these points. <\/p>\n

In the previous entry<\/a>, I put in a system based on cutting a quad (rectangle) into a pair of triangles and blending across it. Doing so yields this:<\/p>\n

octant5_3.png<\/td><\/tr><\/table><\/p>\n

(Am I the only one who thinks that circle with a tail in the middle of the image looks kind of like the Mandelbrot set<\/a>?)<\/p>\n

I’ve been using this snippet of code for years. It wasn’t until I posted the last entry that I even questioned it. Someone asked why I wasn’t using bilinear filtering<\/a> and I realized I didn’t have a good reason. There might be<\/em> a good reason, but I hadn’t even considered the question. I’ve been using the quad-fade code for so long I just sort of take it for granted. <\/p>\n

See, the quad code has two important features:<\/p>\n

    \n
  1. It is fast. This is probably the fastest possible method that won’t create nasty seams.\n<\/li>\n
  2. It breaks things into triangles.<\/li>\n<\/ol>\n

    The triangles thing is important in certain cases. Like, in collision detection. It’s handy if the player is standing on a square of terrain and I want to see if they’re ankle-deep, or floating above it, so that I can nudge them up or drop them down according to the long-understood rules of gravity and… walking up hills. If they’re walking on a triangle (and you are always walking on triangles in a 3D game) then I don’t want to treat the surface like it’s rounded. That will not look right. <\/p>\n

    So I used this code out of habit. I saw a blend-four-values problem and pulled out the hammer I always use on four-value problems. But is that the right choice to make here?<\/p>\n

    The quad blending begins with four values. Say you’ve got four pixels you want to blend together:<\/p>\n

    octant5_6.png<\/td><\/tr><\/table><\/p>\n

    We take this square and divide it into a pair of triangles. We can do this by cutting from upper-right to lower-left, or from upper-left to lower-right. Whatever. It’s best to alternate your cuts in a checkerboard pattern to avoid ugly artifacts. (Alternating our cuts will lead to the “diamond” pattern you see in the earlier image.)<\/p>\n

    octant5_7.png<\/td><\/tr><\/table><\/p>\n

    If the point we’re trying to generate falls in the lower triangle, then we blend between those three points. If it falls in the upper triangle, we use the corners of the other triangle. If I’m generating point X on the image above, then I create a value that is 1\/4 cyan (upper left) and 3\/4 orange (lower left) because we’re about 3\/4 of the way down the image. Then I take that blended value and mix it half and half with dark blue (lower right) because we’re halfway across the image. It might sound confusing, but the code to accomplish this is actually a good bit smaller than this paragraph and only slightly less readable.<\/p>\n

    octant5_8.png<\/td><\/tr><\/table><\/p>\n

    The downside of this is that the points aren’t given equal weight. The two points that form the right angles can’t effect the middle. The exact center is a blend of the two blues, without any weighting from the orange or green. (Please don’t correct me and explain that these are peach and avocado or whatever artists call these colors. I’m making polygons, not a salad. I’m an engineer, and the only color names I know are the ones from the Crayola 8-box. Doghouse Diaries<\/a> and XKCD<\/a> have already slain this horse and gave it a good pummeling afterward. (Insert “pummel horse” joke here.) Let’s move on.)<\/p>\n

    Instead, let’s try bilinear filetering. (“bi” meaning two-way. Yes, just like the sex thing, you complete<\/em> juvenile. “linear” meaning in a straight line. So, a couple of lines? Let’s try it.)<\/p>\n

    octant5_10.png<\/td><\/tr><\/table><\/p>\n

    Bilinear filtering gives the values a more equitable distribution. To solve for the same x as before, we would blend halfway between the top two pixels for point A. Then we blend halfway between the bottom two for point B. Then we blend 75% of the way from A to B for x. Clear? I hope so, because I want to move on.<\/p>\n

    Oh, the same square with biliner filering looks like this:<\/p>\n

    octant5_9.png<\/td><\/tr><\/table><\/p>\n

    Note that we needed to do three blending operations to get this value, as opposed to two blends for the cheapo blend I’ve been using. Now, a single blend is nothing. A few math operations. But remember what we’re doing with this data. We need to do three blends per pixel. But we’re doing this in three dimensions, so we need to generate two<\/em> pixels and blend those<\/em> together for a single octave of noise. And we generally want to combine about 8 octaves to make our noise interesting. So… <\/p>\n

    (3 blends * 2 pixels + 1 blend) * 8 octaves = 56 blend operations<\/code><\/center><\/p>\n

    That’s per cube. Oh, and most cubes need 2 bits of noise. (One to shape hills and one to dig caves, for example.) And a single 16-meter block of the world needs 4,096 cubes. And in a scene, even at the lowest possible<\/strong> visibility settings you’ve probably got around 400 such blocks rolling around in memory. (I think Notch calls them chunks. I’ve taken to calling them nodes.) <\/p>\n

    So even a crappy low-visibility scene needs to perform 183,500,800 blend operations. Also keep in mind that a single blend operation is…<\/p>\n

    \r\ninline float Lerp (float n1, float n2, float delta)\r\n{\r\n  return n1 * (1.0f - delta) + n2 * delta;\r\n}\r\n<\/pre>\n
    Looks like a subtract, a couple of multiply operations, and an add. We need to do that, one hundred and eighty-three million times. That will wipe the smug off the face of your quad-core 4Ghz processor in a hurry. Your machine is going to work<\/em> for this scenery, kiddo. So no, increasing the number of blends we need to do by 50% is not something to be done lightly. We need a really good reason before we start dumping more CPU juice on the problem. We need something important, like marginally better graphics or something.<\/p>\n
    Anyway. So this is what we have now:<\/p>\n
    octant5_3.png<\/td><\/tr><\/table><\/p>\n
    And here is the same thing generated with bilinear filtering:<\/p>\n
    octant5_4.png<\/td><\/tr><\/table><\/p>\n
    So… is it worth it? It’s hard to tell.  Obviously it looks better in RAINBOW VIEW, but that’s not what the data is used for.  In our program, the data is used to make caves.  Does it make better caves? <\/p>\n
    True story bro: As of writing this paragraph, I have yet to try it.  I honestly don’t know, 1,200 words into this post, if this is a complete waste of time or not.  Let’s find out.<\/p>\n
    octant_brb.jpg<\/td><\/tr><\/table><\/p>\n
    That didn’t take long. Okay, so I made a huge volume of noise caves with the threshold set at 0.5. (In English, it should be a roughly even 50-50 mix of air and solid… block stuff.) First, I take a screenshot of a nice bit of cave using the discount triangle-interpolation blending:<\/p>\n
    octant5_old_busted.jpg<\/td><\/tr><\/table><\/p>\n
    And now the exact same location, but generated with bilinear whatsits:<\/p>\n
    octant5_new_hotness.jpg<\/td><\/tr><\/table><\/p>\n
    Is one of these really better than the other? It’s hard to say. What’s “better”? More visually interesting? More fun to explore? More realistic? Is the slow one really 50% slower? <\/p>\n
    This sounds like a decision to make later, when one of these variables matters. I’ve got both systems sitting side-by-side and can flip between them as I need. I guess for testing it makes sense to stick with the faster system anyway. If I stick with this project then eventually I’ll have to add a bunch of timers to keep track of where all the CPU is going, and that would be a good time to come back to this.<\/p>\n
    Also, in the process of writing the new filter, I managed to mess up and make this:<\/p>\n
    octant5_5.png<\/td><\/tr><\/table><\/p>\n
    (I was blending between the wrong corners.) It’s useless, but kind of pretty in a strange way.  I like it because it looks like one of those shuffle puzzles. I suppose it would be considered evil to present this as a shuffle puzzle and let someone drive themselves insane trying to get things to match up?<\/p>\n
    So that’s what we accomplished today… nothing! This riveting series will continue in the next entry unless there isn’t one.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Today we’re finally going to start adding some features to make this thing look a bit more… What? You say you want another digression on noise filtering and interpolation techniques? You sure? Okay then! (Nerd!) If you remember from last time, we’re taking tables of random white noise and expanding them to create “interesting” patterns. […]<\/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":[233],"class_list":["post-15843","post","type-post","status-publish","format-standard","hentry","category-programming","tag-octant"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15843","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=15843"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15843\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}