Project Octant Part 2: Octree

By Shamus Posted Wednesday May 2, 2012

Filed under: Programming 85 comments

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 need and how I get it working. (Incidentally, Qt is pronounced “cute”, if you’re one of those people who likes to read my blog aloud.) There are example programs, but they’re usually demos of “OpenGL and some other concepts” and it’s not clear what parts of the code are the demo, what parts are infrastructure, and what parts are cruft.

Eventually I get a bare-bones application working that creates a simple scene with a checkerboard ground. Something like this is always step 1 for me. I learned a long time ago that you should have a simple, reliable, non-textured, orient-able object in the scene at all times.

octant1_1.jpg

The 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? 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.

(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.)

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.

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.

Let’s start with a cube:

octant1_2.jpg

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.

octant1_3.jpg

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.

minecraft_view_distance.jpg

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.

In this case, an octree can help.

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.

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:

octant1_4.jpg

It’s a bit like the Rubik’s Cube from yesterday.

2x2cube.jpg

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:

octant1_5.jpg

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.

octant1_6.jpg

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:

1 cube of 16x16x16, which contains:
8 cubes of 8x8x8, one of which is divided into:
8 cubes of 4x4x4, one of which is divided into:
8 cubes of 2x2x2, one of which is divided into:
8 one-meter cubes.

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.

There is a slight cost to doing things this way. In a brute system, if I want to look at a specific 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.

The upshot is that when I need a particular block it can take me a few hops to get there, but when I need to see every block it can save me orders of magnitude of time.

If I throw in some basic “hills”, here is what it looks like:

octant1_7.jpg

And here is how that same scene looks on the octree:

octant1_8.jpg

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.

So that was relatively painless. Next time we’ll be talking about things that are less not painful.

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?

 


From The Archives:
 

85 thoughts on “Project Octant Part 2: Octree

  1. Suraj says:

    Put source on GitHub (Google Code is also OK) please and do add a licence file. I am awaiting eagerly for the QT related post.

    1. Chris says:

      Yes, GitHub please! And good idea about adding a license file.

  2. Primogenitor says:

    GitHub is where the cool code is at.

    Documentation is also useful, especially UML or similar. And bundling copies of the blog entries with it counts as documenting it.

  3. Nathan says:

    Yeah, you probably want to go with Github.

  4. Mad says:

    gitorious.org is also rather nice if you want to work with git. ( And Qt lives there as well )

  5. Sean Hagen says:

    I’m throwing in my vote for GitHub. HUGE fan of Git in general, and I love how GitHub has made the tool even more usable ( and social, even ).

  6. Chargone says:

    lesson learned in recent times: it doesn’t matter what you’re doing, who your target audience is, or any of that.

    ALWAYS release your files to multiple locations.

    because you Will lose some of them for reasons that don’t make a damn bit of sense.

  7. psivamp says:

    I am also looking forward to your opinion on Qt. I downloaded it for two OS’s, but I don’t really have time during the last two weeks of semester to be messing around with large coding projects.

    Also, yay, Project Frontier source.

    And, now, an actual question/comment. As recently as Project Frontier I believe you said you were still working with the OpenGL fixed pipeline (i.e. OpenGL 2.1) vice the newer programmable pipeline (OpenGL 3+). Is that still the case?

    Edit: You also seem to have some transparent GUI elements already, is that part of Qt?

    1. Shamus says:

      I actually have some shaders in PF. (Note to self: Include those!) I don’t remember if I wrote about them or not, but the trees and grass wave in the wind, the surface of the world appears to curve, and so on. All done with shaders.

      Of course, this project is still fixed function. Heck, it barely even draws anything yet. :)

      1. Exetera says:

        My vote says Github.

        Also: I’m glad to hear you added shaders to Frontier, but… why did you add them at the end of the project, rather than when you were busy sorting out that bizarre hack for coloring the grass and the flowers? I mean… that would be so easy to fix if you were doing your own lighting. And that’s not that hard. (That said, I’m coming from a lot of WebGL experience, where you always need to use shaders.)

        1. Shamus says:

          It’s not that hard… once you have the libraries added. Like I said:

          “If I want a lighting system that incorporates polygon coloring, I'll have to make my own. I can either do that with vertex shaders or by turning off all OpenGL lighting and doing all of the lighting calculations myself. Both of these steps are complex and time-consuming, and might require changes to the low-level bits of my engine. (Including the terrain system, which I just resolved to leave alone for a bit.) Can I use vertex shaders when I'm using OpenGL through SDL? Wait, now I have to read up on what functionality is available with SDL. Oh, there's a beta version of SDL that might offer…

          No. No no no no. I will take this step eventually, but this is NOT the right time for it. I started this project because I want to experiment with my ideas for procedural content, not so I can muck out implementing my own lighting model. That will be a time-consuming distraction, and will lock me in to certain decisions that I'm just not ready to make yet.”

          1. Exetera says:

            But… you did decide to figure out your library issues and get shaders added. You took that step eventually, so… why not take it when you’d get something out of it? (And, for that matter, after you decided to use a nasty hack specifically to get out of implementing shaders… why would you go ahead and use them anyways for some minor visual improvements?)

            I guess my perspective on this is not the best, having used APIs which require shaders for a while…

            Semi-related: When the source is released, I’m totally going to try porting it to WebGL.

            1. Sumanai says:

              From what I’ve understood, it wasn’t the time. The main purpose for Shamus wasn’t related to how it would look but how it would function. If you do the wrong thing at the right time you can lose the wind from your sails before you get to the important bit.

              For instance: I know I need food. I have food in the freezer. It’s impractical to use it frozen, so I have to take it out before I need it. Yesterday I knew I would need meat from the freezer for tomorrow. Why didn’t I take it out yesterday? Because it would’ve been spoiled by tomorrow, when I actually needed it.

              I knew I wasn’t going to cook today, simply because I’ve learned to, roughly, predict when I’m in the mood for making food. Today was simply not going to be that day, so there I would’ve had to force myself and when I do that I’m less inclined to cook another time and my diet goes worse than it already is since I end up eating microwave dinners.

              For you the important bit is the shaders, so to you it would’ve been the right thing at the right time.

            2. Blake says:

              I’d say because coding for yourself is a lot different to coding for work.
              If the shader work wasn’t what he was interested in, there would be a great risk of him just dropping the project before he got to the stuff he wanted to be working on.

              Working on procedural stuff immediately was worth more than having everything done quicker.

              1. Jeramie says:

                Sorry about a year-old reply, but I just gotta agree completely with Blake here. When it’s a personal project, do whatever is fun, efficient, and comfortable for your coding style, and whatever keeps you moving forward with it.

  8. Kdansky says:

    I’m more of a .hg user, which goes to bitbucket. But I guess github will work.

    1. Simon Buchan says:

      I too really like Mercurial, but github is just too ridiculously good. I’ve not been brave enough to try Hg-Git yet, but it might be good enough to split the difference.

    2. Jacob Albano says:

      Yep, I was going to say the same thing. Bitbucket has been very good for me and my team.

  9. Vorp says:

    If you want to speed up the single-block operations, I found an interesting solution. If you map block positions to the range[0, 2^n], with the world origin at (2^n)/2, the bits in the integer index will give you the exact path to the target node. For example a one-dimensional tree 16 wide, if you want the node at position 6, 6 = 0110, so the path would be left-right-right-left.

    1. Mephane says:

      But that does not yet say anything about the memory layout of the octree. Probably the nodes are connected through pointers, which means one would still have to traverse that path from pointer to pointer. So your method tells the program to go left-right-right-left, but as far as I understood the problem mentioned in Shamus’ post, actually going traversing that path is what makes it slower and indexed-array-access.

  10. Jonathan says:

    Your Rubix cube photo is only a 2x2x2 cube…normal cubes are 3x3x3.

    1. Shamus says:

      Correct. I Chose the 2x2x2 because it illustrated the Octree division, not because it was the more common kind of puzzle.

      1. noahpocalypse says:

        Would there be any benefit to a 3×3 tree? (Dodecatree?) My novice coder’s mind can’t comprehend how that would help, or really how that would work, but it sure sounds cool.

        1. Piflik says:

          The tree would be shallower, but wider. Also you’d end up with more small cubes (instead of dividing one cube into 8 smaller ones, you’d divide them into 27 smaller ones). So it would be worse.

          From a 9m³ to a 1m³:

          1x9m³ divided into
          27x3m³, one of which is divided into
          27x1m³

          1. Deoxy says:

            Depends on the final size you want – if you start with a fixed area and need it broken down to a fixed size (or smaller), the 3x3x3 could achieve that with fewer steps, which would result in both fewer cubes and a shorter traverse.

            The problem there is not that you have more or less cubes, it’s that you’ve gone from binary to trinary, and binary has some really, REALLY serious advantages, not the least of which is that it’s native to the hardware.

          2. Abnaxis says:

            I don’t know what the correct answer to the question is, but I’m 99.9% certain it is way more complicated than that. The optimal number of divisions depends on a lot of factors, like how often you have to know what a particular blocks neighbors are vs how often you have to single out a particular pixel. Again, I might be blowing smoke out my rear, but I don’t think eight equal divisions is so much the optimal way of doing things, but rather the convenient way. Using eight divisions keeps stuff in powers of 2, which are way more convenient when programming.

        2. Zukhramm says:

          That’d be, I don’t know, a “viginti-sept-tree”.

        3. hewhosaysfish says:

          To compare with Shamus’s description: “The upshot is that when I need a particular block it can take me a few hops to get there, but when I need to see every block it can save me orders of magnitude of time.”

          With a 3x3x3 tree it would take you less hops to get to a particular block (because with each hop you’re dividing the search space by 27 rather than by 8) but when you need to see everything then it won’t necessarily give you the same time savings (for the same reasons; dividing by 27 will give you more, smaller cubes which will waste memory where you have large areas of the same composition).

          And, of course, a 3x3x3 tree wouldn’t use powers of two – programmers have to do things in powers of two.

          1. AnZsDad says:

            Programmers do it in pairs?

            (I’m so sorry…)

        4. Zak McKracken says:

          A Dodecatree would be a 12-tree … that’s like … 3x2x2?

          If you went for 3x3x3, you might as well take it on step further and use 4x4x4. And … ohh wait, that’s just eight times 2x2x2, except of course that now one subdivision of one leave means 64 new leaves and not just 8. Less memory efficient.

          Also, there are some really cool adressing and storage management tricks for octrees that only work in binary. I’m not far enough into CS to know this properly, but in essence, you can describe the position of one leave in space with just three bits of data per tree level. (three bits is what you need to represent a number up to 8). So if we take the approach to put two of these numbers in one 8-Bit-Byte, then we’ve got two levels in only one Byte! Mind you, that’s just the leave index, but there are some really cool tricks to find this leave in memory extremely quickly and at the same time waste very very little memory storing it.

          I’d love to point at a proper Paper on the topic, but I’ve no idea where to find it and what that method was called. I’m working (as a user) with software that uses more than 30 levels of octrees (which gives a scale factor of 1 (US-)billion, and manages to fill your complete 24GB of RAM with it… There’s a way to save extreme amounts of space, but as I said, I’m not one of the coders, so I’ll just revel in the vast performance improvements we can achieve with some cool tricks and hope that someone else can shed light on how it actually works.

          There are also some very inefficient ways to implement octrees. And I hope Shamus manages to present us with one of the better ones, because I’d like to know this too.

        5. Kdansky says:

          No, because generally speaking, what you save in work for less tiers, you pay again for having way more complex comparisons. Plus power of two means the hardware likes you more, see the other comments.

    2. It’s funny. Part of my brain said “that rubix cube looks weird,” but the rest of it say “move on, not the point of the article.” So it wasn’t until you pointed it out that I realized WHY I thought it looked weird.

      1. Vipermagi says:

        To me the cube picture was weird because I initially interpreted the C as an L.

        1. Sumanai says:

          I’m afraid to think how impractical Rubik’s Lube would be. And what it would do to the user.

  11. nmichaels says:

    If you used mercurial to track your progress, bitbucket is the place to put it. If you used git, github is happier. If you didn’t use source control while working, both are good and provide free stuff for open source projects.

    1. Mark Erikson says:

      If he DIDN’T use source control… shame on him, he should know better :)

      On that note, I’m curious to hear Shamus’s take on version control systems, just on general principle.

    2. GardenNinja says:

      For what it’s worth, Bitbucket has git support now, though I imagine git is better supported on github.

    3. Zak McKracken says:

      I wonder in which case sourceforge is the go-to place. Lots of good projects on there, too. But I’ve no idea why any project would go to one or the other site.

      1. DrMcCoy says:

        SourceForge used to be the go-to place, years ago.
        It’s the MySpace of code repository sites.

        A lot of projects are still there because it’s tedious work to move, it’s not neccesarily gaining them much to do so; and, if done completely, they’d lose information still sitting in SourceForge’s bug/patch trackers.
        And one thing GitHub is still missing that SourceForge provides is mailing lists.

        1. Zak McKracken says:

          Ohh, Mailing lists, those poor poor replacements for proper newsgroups or fora:(
          (except if you actually have to tell something to a number of people, that is)

          Otherwise: I was completely unaware of SF’s status. Thanks for enlightening me. Been getting a bunch of good software from there, though.

        2. WJS says:

          I don’t know if it’s gone to hell over the years, or if it’s just outdated, but I always find it really unpleasant whenever I need to download something hosted on Sourceforge.

  12. Rohit says:

    Can’t wait for the source.

  13. As an artist trying to learn how to code I am really excited to open up the source code…. Then look at it. Not know what it does. Close it. And, finally go back to trying to learn the basics of C++.

    1. MichaelG says:

      Start with something more forgiving. In C or c++, memory errors are the bane of your existence. Learn Javascript and WebGL or Java.

      1. I actually know a bit of python and I really like that language. Before that I learned Action Script 3.0 . C++ is actually a hobby for me and I find that the more I learn about the low level mechanics of a game engine or a rendering pipline the easier it is to make art for those specifications( Z sorting was not explained in any art tutorial but in a brief overview of how a renderer functions). For instance, I don’t want to just learn how to make shaders. In Unity (I use it at work) there is the Strumpy Shader Editor, which is a visual shader creation suite. I can get around it just fine but for me to get full use out of this tool I think that I would prefer to learn the mechanics of “why,” underneath the pretty interface.

        1. Dasick says:

          The way I learn most programming languages is I sit down, make up a simple project to do (low level games are the best I find, because games tend to need almost all of the aspects of programing) and try to implement it. I break down the game into manageable tasks, then go ahead and research each one, build it up the way Shamus describes in the second paragraph and mush it all together.

          The idea is that a project that you’re building up to gives everything you’re coding a sense of purpose, and the fact that it’s a big-ish project means you will run into unexpected errors and problems sooner or later and be forced to solve them using everything you’ve got.

          Like an Octree really. It sounds cool, but you don’t really understand it’s full utility unless you’ve made one and had to use it somewhere.

          P.S.I’ve yet to have a complete game, but in the process of doing that I’ve learnt Turing (text-based galaxy-spanning free-form space-opera RPG) Java (rogue-like platformer… I want to remake it as a Diablo clone), C# (RTS. I don’t want to program in C# any more, but I’ve made so much progress I don’t wanna start from scratch either) and C++ (A top-down path finding program for someone’s game. My most finished project to date).

          1. Yep, that’s my plan for now too. I picked up a “simple” engine to start out with( softpixel) just so that I don’t have to do all of the lower end work. This way I can still come to grips with the language and make something “cool” rather than just a boring console program. Now it’s just a matter of making a, sphere based, twin stick shooter. Hopefully I will learn: Pathfinding, file IO, a little dip into some procedural stuff, and everything else.

            Yay! face to keyboard times await. At least I like puzzles.

            1. MichaelG says:

              Best of luck, and I’m not arguing against getting down in the weeds (see my project blog http://sea-of-memes.com )

              What I’m warning you about is C++ debugging. If you do something as simple as overwrite an array, or continue to use a pointer after you’ve freed it, the program can break in some completely different area, much later. You can go insane trying to find those bugs, and the debugger doesn’t help.

              Any of the interpreted languages would avoid this problem. Graphics programming will be the same with any language that has an OpenGL binding. Most of the work is in the shaders now anyway.

              1. DrMcCoy says:

                “and the debugger doesn't help”

                http://valgrind.org/

                Seriously, if it were physical possible, I’d carry valgrind’s children.

                1. Deadfast says:

                  This so much.

                  Writing beyond an array, reading the value of memory that was previously deallocated and failing to deallocate the array:

                  deadfast@laptop:~/C++$ valgrind –leak-check=full ./a.out
                  ==10731== Memcheck, a memory error detector
                  ==10731== Copyright (C) 2002-2010, and GNU GPL’d, by Julian Seward et al.
                  ==10731== Using Valgrind-3.6.1-Debian and LibVEX; rerun with -h for copyright info
                  ==10731== Command: ./a.out
                  ==10731==
                  ==10731== Invalid write of size 4
                  ==10731== at 0x40074B: main (test.cpp:10)
                  ==10731== Address 0x5971064 is 0 bytes after a block of size 36 alloc’d
                  ==10731== at 0x4C2864B: operator new[](unsigned long) (vg_replace_malloc.c:305)
                  ==10731== by 0x40071C: main (test.cpp:7)
                  ==10731==
                  ==10731== Invalid read of size 4
                  ==10731== at 0x400770: main (test.cpp:12)
                  ==10731== Address 0x59710b0 is 0 bytes inside a block of size 4 free’d
                  ==10731== at 0x4C27FF2: operator delete(void*) (vg_replace_malloc.c:387)
                  ==10731== by 0x40076B: main (test.cpp:11)
                  ==10731==
                  ==10731==
                  ==10731== HEAP SUMMARY:
                  ==10731== in use at exit: 36 bytes in 1 blocks
                  ==10731== total heap usage: 2 allocs, 1 frees, 40 bytes allocated
                  ==10731==
                  ==10731== 36 bytes in 1 blocks are definitely lost in loss record 1 of 1
                  ==10731== at 0x4C2864B: operator new[](unsigned long) (vg_replace_malloc.c:305)
                  ==10731== by 0x40071C: main (test.cpp:7)
                  ==10731==
                  ==10731== LEAK SUMMARY:
                  ==10731== definitely lost: 36 bytes in 1 blocks
                  ==10731== indirectly lost: 0 bytes in 0 blocks
                  ==10731== possibly lost: 0 bytes in 0 blocks
                  ==1 0731== still reachable: 0 bytes in 0 blocks
                  ==10731== suppressed: 0 bytes in 0 blocks
                  ==10731==
                  ==10731== For counts of detected and suppressed errors, rerun with: -v
                  ==10731== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 4 from 4)

                  Such awesomeness comes with a price though. Valgrind is only available for Linux, OS X and Android. There is an alternative called Dr. Memory which is also available on Windows. I haven’t had the chance to try it myself and there doesn’t seem to be really that much info about it out there. Does anyone have any experience with it?

        2. Blake says:

          My progression was ActionScript->Java->C++. ActionScript got me to understand object oriented concepts, Java was where I learnt to write a stand-alone app (and messed around with pathfinding and such), then C++ is what I use for work.
          Java gives really nice error messages, a lot of C++ compiler errors even make no sense at first, and you pretty much just have to learn what they mean (“What do you mean you wanted a semi-colon before this first line of my file!? Oh, the last file I included was missing a semi-colon”).

          If you’re learning C++ on your own, my advice would be to read lots of code. For instance when Shamus releases the source, don’t just go “aaah I don’t understand this!?”, keep following it down to the lowest levels, work out why each part is doing what it’s doing, and as you get to higher levels it’ll start to make sense.

      2. Sumanai says:

        I thought Javascript fell into the same hole as PHP, CSS and HTML in that it brings with it insanity for those trying to learn it.

        1. Blake says:

          My impression was it seems usable on the surface, but the deeper you dig the more you want to poke your own eyes out.

  14. Steve says:

    Github please. It is the easiest to clone (Checkout) from.

  15. ctrees says:

    You should really just tweet that code.

    1. Scott (Duneyrr) says:

      I can see no reason not to do this.

  16. Cybron says:

    Geocities, obviously.

    1. Dave B says:

      No, post it on a BBS!

      1. neolith says:

        Punchcards!

        1. Sord says:

          IBM 5081 format please!

          1. bucaneer says:

            Get one of the novices to transcribe and illuminate it on parchment.

            1. Mephane says:

              Real men carve everything in granite.

              1. Moridin says:

                Written language? Get off my lawn! Real men teach their words to others so that storytellers can keep them alive as oral tradition.

                1. Sumanai says:

                  I just wait for the universe to procedurally generate and then compile the code.

                2. Zak McKracken says:

                  Real programmers…
                  http://xkcd.com/378/

                  I had to do this.

      2. Shamus says:

        Too late. I already uploaded it to my AOL page. It took forever. I mean, it’s almost five megabytes!

        1. Blake says:

          Man, that’s gonna take a lot of 5 and a quarter inch floppies.

  17. Fenix says:

    In Minecraft the max view distance is actually 256(ish (It’s more like 280)) block diameter, not radius. So the world rendered is 256(ish)x256(ish)x256 currently.

  18. Dasick says:

    Funny thing about pronunciation… I thought Qt was pronounced “cutie” or “cootie” (calling someone the former is a symptom of the latter. unless you’re being ironic. because everything is better when it’s ironic. like these brackets).

  19. mneme says:

    Qt is pronounced as “Q, T” (in your local language) a lot more often than the British pronunciation of “cute”. I prefer “cutie” myself (which is how I pronounce Q. T.).

    An yeah, githut is the obvious (although git is easy enough to push from that you could trivially mirror to multiple repos).

  20. BeamSplashX says:

    Shamus, I think you meant for your title to say “Quad Tree”.

    Thank me later.

    1. Alex says:

      Maybe his goal is now to create a horrible fusion of Octopus and Tree?

      An “Octotree”, if you will. Like “The Giving Tree“, but less horrifying.

      1. HiEv says:

        Now I’m reminded of the “Save The Pacific Northwest Tree Octopus” page.

    2. Drew says:

      Perhaps I’m missing something…why would he mean Quad Tree?

      1. BeamSplashX says:

        He mentioned in his previous post on Octant that he’s used to using quad trees, so he often types that instead of octree.

        I’m being a facetious bastard, is what I’m saying.

    3. Jake Albano says:

      That’s incorrect. It’s physically impossible for a quadtree to represent 3D space. Octrees are quadtrees^2.

  21. Alex says:

    Have you tried using Unity? What are your thoughts, if you have? How does it compare to something like Qt?

    1. Shamus says:

      Unity is a great tool for people with the opposite of my skillset: Lots of art, little programming.

      Generally, full-featured game engines do not play well with procedural content. They’re built around loading stuff from disk and displaying it in the world, and some of them don’t even have systems that allow you to create textures and models and scenery in memory.

      1. Piflik says:

        People like me…Yay!…

        I have to agree. Unity is perfect for people with an art background. There still is some programming with C# and/or a Javascript derivative, but that’s more scripting than programming. The framework for rendering, animation, sound, physics, etc is all already there. If you need more exotic stuff (or simply want to), you can of course write your own components to replace the existing ones, but you don’t have to have the ability to write a whole game engine on your own to start working. You can focus on the creative part.

        The one thing that makes it perfect for me is the instant gratification. If I didn’t see progress constantly, I would probably loose interest very quickly. I can’t imagine myself write a codebase for a week or so before I see how well (or if at all) it works.

  22. Brandon says:

    Historically, I’ve done most of my coding on Unix based systems using text editors and compilers rather than any kind of IDE. I’ve been wanting to switch over to coding on my Windows machine because my Unix machine is slowly dying (It’s a really old laptop. I don’t want to put Unix on my desktop), so I’ve been looking into some IDEs. I hadn’t heard of Qt though, very interested to read what you have to say about it.

    I love reading your programming posts by the way. It always inspires me to start coding in my free time again. :)

  23. Tharwen says:

    I’d heard of octrees before, but just sat slack-jawed and nodded my head whenever it came to having them explained to me.

    Now, I’m pretty sure I’ve got it (I expect there’s more to it than just in your description, but I’ve got over the first Hurdle of Understanding (heh, that sounds good. I should make a blog to write all about it so that people can solve forum disputes for years to come by simply linking to it))

    Anyway, yeah. Shamus, you are amazing at explaining complex things simply. Thanks.

    Also:

    “If you can’t explain it simply, you don’t understand it well enough” – Albert Einstein

    1. MatthewH says:

      I would second this. I haven’t the foggiest idea what he’s doing, but I feel more informed at the end of it. Not that I think I could pass a test on the actual procedures.

      Out of curiosity, if most programing is done in an environment like Qt, how is Qt written? Basic command prompt, or is that “burned into the chips” I keep hearing about?

      1. Sumanai says:

        It’s the same thing as with physical tools. Build basic tools out of rocks, sticks and so on, then use those for better tools, go on until you start cursing about the youngsters and their “power drills” and “nail guns” and whatnot.

        Then you can use those tools to make more tools.

      2. WJS says:

        Development of tools doesn’t have to be done at a lower level than the tools operate on. It wouldn’t surprise me in the slightest if the Qt IDE was developed using the Qt IDE. Obviously your first version has to be made with something else, but once you’ve got past that point nothing stops you from writing Qt 1.1 using Qt 1.0.

  24. harborpirate says:

    Another vote for GitHub. Its so easy to use, forking projects is a breeze, and the project repository is stored locally so its extremely fast to work with (no more waiting eons to do checkins/checkouts).

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun. Your email address will not be published. Required fields are marked*

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>

Leave a Reply to DrMcCoy Cancel reply

Your email address will not be published.