<\/td><\/tr><\/table><\/p>\nThe reason for this is that early in a project, you can often find yourself in a situation where you’re looking at a blank scene and you don’t know why. I start up the program and I’m looking at a solid color. Did I accidentally type a wrong number and move all the scenery 1,000Km to the right, instead of one meter? Or maybe the scenery is where it’s supposed to be, but the camera has been placed far off? Did I mistakenly apply a transparent texture to the scene, thus making everything invisible? Is it even drawing the world at all? Or is everything fine, I’m just looking straight up at the sky? Actually, is the camera moving? Maybe the scenery is just off to one side but I’ve broken the controls so that I can’t move?<\/em> After a few minutes of waving the mouse around and staring at a blank screen, the wise programmer will see the value of having a handy marker nearby. If something goes wrong, the checkerboard can help me know where to look for the problem.<\/p>\n (If I wasn’t lazy, I would have drawn this checkerboard so that the four corners were all different colors, or done something else to ruin the symmetry. Several times while working I’d get disoriented because I couldn’t tell which way was north, south, east, or west. Instead of paying the time up-front to do it right, I spent it in many small doses as I fumbled around, looking at the wrong bit of scenery because I’d lost my bearings. Live and learn. Or don’t, in my case.)<\/p>\n So my basic Qt application is working. I won’t do my full write-up on Qt now. I will say that after a few hours with the platform, I am not a huge fan. It has distinct advantages, but some non-trivial costs. (Not talking about money, mind you.) I’ll get into this more later, but for now let’s just move on and work on this octree stuff.<\/p>\n Octree is named for “Oct” + “tree”, meaning a tree with eight branches. Yes, most sensible people can see that it’s shaped like a cube and not a tree. It’s called a “tree” because programmers tend to name things after how they behave in memory, not how they look in 3D space. In the code, an Octree is conceptually tree-like in that each cube can be divided into smaller cubes, each of which can be divided into eight smaller cubes, each of which… you get the idea. <\/p>\n Let’s start with a cube:<\/p>\n Pretend this is a section of a cubist quasi-Minecraft world. This area is sixteen meters on a side. Now, the brute-force solution is to represent this as a 16x16x16 grid. <\/p>\n That is a LOT of cubes. 4,096, actually. Perhaps a frame of reference would help. In Minecraft, at maximum settings you can see 256m in every direction. When you look to the horizon, the most distant visible block is only 256 meters away. <\/p>\n That means there are also 256 blocks behind you that you’re not seeing right now. Which means the area around you is 512×512 meters. It’s also 256 meters from the top of the world to the bottom. Which means that at any given time, the game has 512x512x256 cubes in memory. That’s 67,108,864 cubes. This is do-able on modern hardware, but horribly inefficient. That’s a great big rolling sea of data. Just passing over it to do calculations would be murder. Moreover, if we’re talking about something Minecraft-y then we’re dealing with a situation where a vast majority of the data is either solid stone or empty air. <\/p>\n In this case, an octree can help.<\/p>\n So back to our 16x16x16 cube. If this is solid stone, then we can just have this one cube that represents 16x16x16 meters of solid stone. If the game says, “what is the block in-such-and-such a place?” we don’t need to go fishing in a big soup of data. We see the coords fall inside of our cube here, so we just say, “stone”. It’s all stone. <\/p>\n But what if it’s NOT all stone? What if one little block at the very bottom is different from all the others? Well, that means we subdivide our cube into eight smaller cubes by cutting once along each axis:<\/p>\n It’s a bit like the Rubik’s Cube from yesterday. <\/p>\n Our cube is now broken up into eight sub-cubes. Each of these sub cubes is 8x8x8 meters. Most of them are still solid stone, but the one at the bottom front needs to be divided again:<\/p>\n Now these new cubes are 4x4x4 meters each. We keep dividing until we get down to the level where we have just 1x1x1 cubes, and we can at last set our one lone cube at the bottom to be different from the others.<\/p>\n Note that originally this entire block of stuff would have taken up 4,096 worth of cubes in memory. Using an octree, we now have:<\/p>\n 1 cube of 16x16x16, which contains: So we have 33 cubes instead of 4,096. Even better, if we need to do a lot of processing looking for particular blocks (perhaps we’re looking for blocks of air so we can make polygons and do lighting calculations) then we have a super-fast way of eliminating huge areas in our search. In a brute-force system, if I was looking for air blocks I’d have to pass over each and every one of these 4.096 cubes and ask, “Is this air? No? Okay, moving on.” But here I won’t need to make more than 25 moves.<\/p>\n There is a slight cost to doing things this way. In a brute system, if I want to look at a specific<\/em> block I can do so directly. If the player destroys the block in row 4, column 2, layer 7, then I can go to 4,2,7 and change it to air. In an Octree, I have to start at the top level and step down. If I want to find Jimmy, I have to ask his great-grandfather, who will tell me where I can find Jimmy’s grandpa, who will tell me where Jimmy’s dad is, who can point me to Jimmy. <\/p>\n The upshot is that when I need a particular<\/em> block it can take me a few hops to get there, but when I need to see every<\/em> block it can save me orders of magnitude of time. <\/p>\n If I throw in some basic “hills”, here is what it looks like:<\/p>\n And here is how that same scene looks on the octree:<\/p>\n The huge white cubes are blocks of air. You can see how the top and bottom of the image have lots of big, consolidated cubes, while the center has lots of tiny little cubes where the air and ground meet. This is how it works: Lots of detail around areas with diversity, and lots of simplification in homogeneous areas. <\/p>\n So that was relatively painless. Next time we’ll be talking about things that are less not painful.<\/p>\n Also: I’ll be releasing the source to Project Frontier at some point this week. What is the go-to place for doing that sort of thing these days? Github? Google Code? Facebook? Geocities? Anything else to say about it before I make the source public?<\/p>\n","protected":false},"excerpt":{"rendered":" Step one of this project is to bootstrap myself up to the point where I can start doing some 3D programming. If I was working in my familiar environment this would be about ten minutes, but now that I’m using Qt it takes me a couple of hours to get a sense of what I […]<\/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-15751","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\/15751","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=15751"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15751\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15751"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15751"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15751"}],"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
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n
\n8 cubes of 8x8x8, one of which is divided into:
\n8 cubes of 4x4x4, one of which is divided into:
\n8 cubes of 2x2x2, one of which is divided into:
\n8 one-meter cubes.<\/p>\n
<\/td><\/tr><\/table><\/p>\n
<\/td><\/tr><\/table><\/p>\n