Project Octant 10: Marching

By Shamus Posted Monday May 21, 2012

Filed under: Programming 99 comments

Back when I was talking about making beveled edges, some people asked why I didn’t just lift up the corners of cubes to make slopes instead of mucking around with the soft / solid geometry business. At the time, I wanted to avoid a system where I would attempt to build a cube:

octant10_1.png

And wind up with this:

octant10_2.png

I actually had the program doing this when I was working on beveled edges, and it was messy and frustrating. After a while I got used to it, but that wasn’t really the same as having it be intuitive in the first place. To do this right, you’d have to move away from cube-based building and adopt some sort of point-based system. To the end user the difference is purely semantic, but internally a point-based system would have a big impact on how you generate geometry.

That sounds really interesting, but I can’t let myself be distracted from my important goals of… of… What was the point of this project again? Oh, right: Screwing around and working on whatever I find interesting, and damn having a plan. That goal is 100% compatible with tearing the guts out of the engine and starting over with a different system. So let’s do that.

It looks like marching cubes is the go-to solution for this kind of thing. There’s even some raw example code I could drop in and have it working. But it’s no fun to just use some other code without knowing how it works. I don’t just want to use it, I want to understand it.

Marching cubes is a system for taking a 3D point cloud of data and turning it into polygons. By “point cloud” I mean all you have is a 3D grid that says whether or not each space is occupied. I decide to start by implementing marching squares, which is the same idea, but implemented in only 2 dimensions.

octant10_3.png

(If the image doesn’t make it clear, if you’ve got two points off on the same side then you just cut the square in half.)

With four on / off points, there are a total of sixteen possible configurations for each square. You sort them out by assigning a power-of-two number to each corner. Say we make the upper-left point 1. Upper-right will be 2. Lower right is 4. Lower left is 8. Now add up all the active corners. In the example image above, this would result in 1 + 4 + 8 = 13. If all corners were off the number would be zero. (All empty space.) With all corners on you get 15, which is just a solid green square.

You can arrange the numbering any way you like. The point of this numbering system is that you can just make each and every one of your 16 combinations (although zero and fifteen are the easy ones) and then just have it draw the appropriate pre-made shape out of the 16.

I implement this in my program. Note that we’re using squares to make 3D volumes, which doesn’t really work. I knew this wouldn’t work when I started, I just wanted a quick way to teach myself how it worked, and see how it looked. I’m taking squares and extruding them into 3D, so these “cubes” don’t have tops or bottoms.

octant10_4.jpg

Hm. Kind of interesting. I did have to break everything to do this. Texturing, lighting, everything is screwed up. (Also note that the purple cross in the middle of the screen is supposed to be a plus sign. Yes, I even managed to break the crosshair.)

octant10_5.jpg

It’s not the most exciting thing in the world, but it has a certain charm. It’s interesting enough that I’m willing to take what I’ve learned and implement the 3D version of this. This is going to take a while, during which time everything will be hilariously broken. I mean even more broken than it is now.

octant10_6.jpg

The trick with marching cubes is that instead of the 4 corners of a square, you’ve got the 8 corners of a cube. Which means there are 256 possible combinations. 256 different ways to cut up a single section of cube-space to represent all of the different point patterns. Once you understand how it works the whole thing is trivially easy to implement, but it is very, very time-consuming. I get a few dozen configurations into it before I go nosing around for some code. Now that I get the idea, everything from here on is drudge work.

Luckily, someone has indeed done the painstaking part and put the result up online. Even better: It’s old-school ANSI C code. C++ has a lot of advantages when you’re building a large project and you need some way to manage complexity, but when you need a simple bit of code that does a simple thing, nothing beats C for clarity. Far too many programmers would have made this into some convoluted class interface that spans several modules and header files, but the stuff on the linked page is pretty much ready for copy & paste.

So how does it look?

octant10_7.jpg

Er. Yeah. Without lighting it’s pretty dang hard to see anything. I’ve got it painting some facets different colors, and I can make out the contour of the geometry when I’m moving the camera around, but without shading it’s pretty much impossible to make sense of a still image.

The problem is that I can’t light this thing properly. To do lighting, you need surface normals. Surface normals are numbers attached to your 3D geometry that tells you which way it’s pointing. Remember that 3D graphics are made of triangle, and triangles are made of points, and points are just dots in space. A dot doesn’t have a direction. Is this dot facing the light? Or away? Without normals, you don’t know.

octant10_8.png

Hm. I’ve got some code here that will analyze groups of triangles create normals for them. Mathematically, it’s pretty hairy and it’s one of those code snippets that I have to re-learn every time I need to do something with it. (If you’ve got the source for Project Frontier, look for CalculateNormals or CalculateNormalsSeamless in the Mesh module.) It’s crazy slow, but it should let me add lighting to the scene so I can see what I’m looking at.

octant10_12.jpg

Savor this image, because I’m not making more of them. It took the thing over a minute of chugging to come up with this scene because of the extreme expense of the normal-calculation code. Well, one more:

octant10_10.jpg

For comparison, here is the same location rendered with the old cube system.

octant10_11.jpg

I add some texture maps. These just use my old brain-dead mapping logic from part 6. Of course, the system breaks down now that I’m no longer using cubes. The situations where I used to have mirroring I now have a big ugly smear as a single column of pixels is stretched over several meters worth of geometry.

octant10_13.jpg

octant10_14.jpg

It’s sort of amazing how organic this looks. This is the same sort of data-set I’ve been using since part 5. Remember that these are just one-meter cubes with the corners knocked off, even though it looks like we’re dealing with high-polygon lumps.

I add some simple vertex coloring to the mix and have it generate a simple “maze”.

octant10_15.jpg

(That white thing in the middle of my screen is my edit icon. That’s where blocks appear or vanish when I hit the appropriate button.)

Building in this stuff is very, very strange. It’s not dealing with “blocks” anymore. Instead I’m building with… blobs. A single point in the air is shaped like a diamond. But once you get a few of them next to each other it feels more like building with clay.

I find I want to dig wider like this. Previously I was content to travel through tunnels that were 1 block wide and 2 tall, but with the beveled shapes the tunnel is sort of cramped like that. So I need to excavate 2 or 3 wide to be comfortable. But then I get impatient and start spamming the destroy button to clear the way. The result is a very lumpy tunnel.

Well, the project is now well and truly broken. I migrated from Qt back to Visual Studio, as I discussed in part 8. Now I’ve re-written the core of the program. The result is that I have pages and pages of disabled code and a dozen or so things that no longer work. Collision, texture mapping, lighting, building, the movement controls… almost every system has something annoying wrong with it. I’m going to clean up this mess and get everything working right again. After that I’ll come back and decide if I want to go back to cubes or keep working with blobs.

octant10_16.jpg

 


From The Archives:
 

99 thoughts on “Project Octant 10: Marching

  1. Moewicus says:

    LumpyClayCraft is blowing my sleep deprived mind.

    1. Arvind says:

      This could become something like From Dust (haven’t played it but I heard that’s what you did in it), where you can shape terrain on the fly along with other stuff. Sounds very exciting.

      1. Paul Spooner says:

        From Dust used a height map. Basically, this means you can’t make caves, overhangs, arches, etc. It was a pretty game though.

        1. James says:

          this isn’t related so i apologize, but i need to bring this up and hopefully shamus will see it.

          i have been re-watching the earlier Spoiler Warning series (the ones on viddler, i’m not sure if its my region, but the videos have had issues loading the built in viddler ad’s specifically the MiB3 one and one for GAME. which means often i have to refresh the page like 20 times in the hopes it will run a different ad. just letting you know

          sorry for being off topic

  2. Mersadeon says:

    Hm. I have to say, I do like the whole “building with blobs” idea – it looks kind of nice.

    Also, the drawing explaining the point-stuff reminded me of “Drawn to knowledge”. Are going to make more of those? Because I really liked the one about the origin of the internet. Whenever someone asks me how the internet came to be what it is, I basically explain it just like you in your video.

  3. Zeta Kai says:

    I dub it BlobCraft. You’ll make a mint.

    1. evileeyore says:

      If I had a millions dollars I would pay Shamus to make some sort of game out of BlobCraft.

  4. Pete says:

    I wonder if this is how Lords of Uberdark does its terrain. Or Transport Tycoon, back in the day.

    1. bit says:

      Link is broken, sweets.

      …But, after googling;
      http://www.lordsofuberdark.com/
      Huh. That actually looks pretty neat. I like the heavy outlines, psuedo-cell shaded thing going on there.

    2. Dasick says:

      I think so. That was the first thing I thought of when Shamus said he was building with blobs.

    3. Dragomok says:

      Actually, it uses voxels (it was mentioned in the first video in their YouTube channel and its Kickstarter page is title Lords of Uberdark – 3D Voxel Based Mining / Building Game as of 22nd May). Everything I know about voxels is that “they’re pixels with volume” and, since it’s midnight when I’m writing this, I can’t really do a research, so I can’t really tell if it’s the same idea that Shamus uses or not.

      1. Kdansky says:

        Wikipedia!

        A voxel (volumetric pixel or Volumetric Picture Element) is a volume element, representing a value on a regular grid in three dimensional space.

        So yeah, Minecraft, BlobCraft and Uberdark all use Voxels. I’m guessing Uberdark actually does the exact same thing as BlobCraft, using Marching Cubes.

        1. Mephane says:

          Afaik voxel graphics is not just about managing voxel-like data like Minecraft blocks, but the entire rendering pipeline is different. So in order to truely implement voxel graphics you would need to do more than just a 3D grid as your world data and then turn that into ordinary triangles which you feed your video card.

          (I might however have misread something somewhere and be dead wrong about this, feel free to correct me if I am.)

          1. decius says:

            Voxel rendering doesn’t become triangles. You render voxels instead.

            I don’t understand any more than that, any more than I understand why it’s not trivial to just say “after you render the scene, put this HUD over it” rather than having to put the HUD on a transparent polygon and then render that polygon.

            1. empty_other says:

              Red Alert 2 uses voxels for their vehicle models. I quickly recreated the technique in c++ once and was planning for using them in a game (which i never finished, as usual).

              Anyway, it was really simple as long as it was drawn isometric. You dont even need any fancy 3d card to do it (you can even do it in photoshop).
              1. Get 16 images, each of the 16×16 in size (or bigger, of course). Each of them contain a slice of the tank, from bottom to top.
              2. Rotate every image according to which direction the tank is driving.
              3. Then shrink the image height down to 8 in height (if you are drawing at 45 degrees camera angle).
              4. Then draw each image to the screen, starting with the bottom one. For every image you draw, move it 1px above the previous.
              5. If everything went right now, you should have drawn a voxel tank. It is unshaded, so you probably have to write some shading code yourself, or just add some static shadows to the images.

              How far you offset each image should probably not be 1px but rather based on what angle you see the image. 1 pixel if you look at it from its side, 0 pixels if you look at it from the top, and anything in between when looking at it from the side. But im too lazy to do that.

              I even made a quick example in photoshop to illustrate:
              http://www.onlyhuman.dk/files/voxels-in-photoshop.png

              1. decius says:

                That’s an interesting technique for rotating a unit, but where does it use voxels? It seems like as you go from a straight-down view to a ground-level view, you would see the same image, just shortened. From the top, you should see the top view, and from the side, the side view: The sides of the tires aren’t visible from the top, and the top features aren’t visible from the side. It could work well for a limited set of camera angles- I don’t recall RA2 having an adjustable camera angle.

                1. Mechtroid says:

                  That’s why he said it worked as long as it was isometric. Indeed, it fails if the voxels don’t have a footprint the same size as a pixel, but that’s the main property of an isometric viewpoint.

                  1. decius says:

                    The only characteristic of ‘isometric’ is that every object of equal actual size is projected as an equal size object, regardless of the ‘distance’ from the surface on which it is projected

                    That can be done from any ‘angle’, although in drafting it also has a more specific meaning.

                    Using voxels for a 2d surface would be overkill, especially when you can use rotated sprites as described to get the exact same result.

                2. empty_other says:

                  No, nothing in RA2 was real 3d, so no adjustable camera angle. But the tanks could rotate in 3d space (sideways or around).

                  I didn’t think about ground level and image scaling/color blending: If i were to see it from ground level, the scaling would make those “slices” blend their colors, and i would get a not-so-beautiful color mixup.. I would probably have to make a image-scaling function which give preference to pixels on the bottom (closest to me) to get a realistic view from the ground.

                  1. decius says:

                    Could the units rotate on any arbitrary axis? I can’t recall off the top of my head if a tank going up a hill looked ‘perfect’, or just ‘right’.

                    I’m not even sure if I recall the terrain in RA2 having any hills.

          2. Sumanai says:

            Indeed, voxels are sort of volumetric pixels, not cubes made out of polygons. They can be represented in different ways, but inside a single “cube” there’s no extra data. So a voxel can’t have a texture on it, since it’s the smallest visual object in the engine.

            The only methods I know of drawing voxel graphics use raytracing at various levels of complexity. Usually it’s just a straight beam for every drawn pixel going until it hits a voxel and then reports the colour.

            Ken Silverman has been dabbling with them since he created the build engine and felt that he had dropped out of the loop for polygon graphics.

            http://advsys.net/ken/

            Most games that have used voxels have used a mixed engine that does both voxels and polygons so some parts are the other, while the rest is the other.

            Minecraft uses polygons, Fez uses voxels. They call them “trixels” or something because they use a shading system that doesn’t make the voxels look rounded, but they’re voxels. Unless they changed the engine after I read up on it.

            1. Jamie Pate says:

              pretty sure voxlap is used in this game:
              http://ace-spades.com
              that is an example of a true voxel engine (not sure if the terrain or the characters or both count as ‘true’ voxels, but they’re in there somewhere)

              1. Sumanai says:

                When the arm clips through the ground it looks a bit funny, in a way I don’t think usually happens with voxels, so I’m not certain if it actually uses Voxlap. Do the creators mention it anywhere?

                Regardless it is good for checking what voxel graphics look like generally speaking, since it shares a lot of similarities visually.

            2. Oleyo says:

              Nothing beat hiding in the voxel grass in the original Delta Force.

          3. Mechtroid says:

            Here, let me try to explain the intricacies of voxels versus voxel engines versus voxel rendering versus the rest of your computer.

            In Which Mechtroid Takes a Metaphor To Infinity And Beyond:
            Or: Your PC, Now a Sitcom on Fox!

            Well, let’s pretend you’re this guy, CPU. You work with Ms. GPU. She’s exotic and foreign, and she’s an amazing artist. You and Ms. GPU have a job creating paintings and shipping them to a museum for your employer to look at. Your job is to keep intricate notes and generate sketches. She turns them into beautiful landscapes, filling them with light and color. Then Mrs. GPU ships them off to Museum du Monitore, and you’re off to sketching the next one, changing your notes based off your employer’s feedback.

            And then you read a self-improvement book called “The Cube Solution” by Dr. Jenny Voxel. It’s fast, simple, and it makes so much more sense to your mathematical mind, pretty much everything about it is amazing. In Dr. Voxel’s system all you have to do is sketch clouds of points and a tiny bit about each point, and you can get rid of all these complex notes crap. All of those calculations you have to do to help Ms. GPU are unnecessary. Just fields of points, and changing them in simple mathematical ways, what you do best. Sure, you’ll need a lot more space to store all these notes, but your house has been bigger than you could ever need as of late. The problem is, Ms. GPU doesn’t work that way. She doesn’t understand points, you might as well be talking a different language.

            Your friend Jim suggests painting the entire thing yourself, but you already have a full time job keeping track of notes, and you paint far too methodically to do it quickly anyways. Dammit Jim, you’re a mathematician, not an artist.

            Now, as the average person’s CPU, you could try to render voxels, but Ms. GPU would just give you a deadpan look and go “… What are these? No, don’t answer. You’re not stupid, you know I only work with lines. It’s that Jenny you read about in a book, isn’t it? Jeez, you’re such a pig sometimes. I’m going to pretend these… ‘disgusting little points’ are triangles. Whatever mess that happens in your museum is your fault. Some days I don’t know why I put up with you.”

            At best you get an indecipherable painting, at worst she throws a tantrum. This woman’s tantrums are legendary, if it gets bad enough she just starts shrieking and never stops, something you nicknamed the “Blue Scream of death”.

            So a program that decides to follow the voxel method at some point has to give up and ask his co-worker steve to turn all these points you sketched into triangles for him. But Steve starts using half of the house to do all these calculations about triangles, and you have to start taking turns using the only calculator between the two of you. That gums up all the works, then the employer complains about how “slow” the company is and you blame steve and then the company parties get REALLY strained and awkward between you two.

            tl;dr: Voxels: The perfect setup for an episode from the sitcom starring your computer.

            1. Pete says:

              That is probably the most eloquent way to say “the hardware we have for rendering triangles doesnt exist for voxels yet” Ive seen so far.

            2. Mephane says:

              For many reasons I believe our current graphics hardware is moving towards a dead-end,

              a) because of its inability to natively render voxels,
              b) due to its vast collection of special (though clever) tricks to inexpensively imitate effects of light, shadow, reflection etc. without actually calculating the stuff (in contrast to raytracing where all that is really happening),
              c) because at some point in the foreseeable future raytracing will become the more efficient rendering method, as it scales much better with the increasing number of objects/triangles.

              Don’t get me wrong, I am not claiming scanline rendering is dead, I only say that its death will be inevitable at some point in the future.

  5. Alan says:

    Wow, taking a nearly working system and reinventing the polygon is pretty far reaching.

    I think both of them have their advantages, it just depends on what type of thing you are trying to do with it.

  6. ragnarok_mr4 says:

    This reminds me very much of the blobmesh/metaball geometry tool in 3DSMax. :D

  7. bit says:

    This is strangely pretty, in a surrealist kind of way. I feel like I’m in some strange, beta, slightly glitched-out experimental N64 game.

  8. GM says:

    This look´s better than Kq8 but then that is not difficult,i´ll say it look´s interesting reminds me King quest 5-7 actually.

  9. Lord Honk says:

    Reminds me very much of the way the CryEngine handles caves. When I played around with it I was most fascinated by the 3-dimensional texture coordinates they use, but looking back their approach to creating caves in solid mountains is not unlike what you’ve got going there.

    Just checked, they’re calling it “voxel caves”, or at least that’s what google gives me the most results for. Okay, so it’s not too similar, but you get my point, right?

    Anyways, personally, I find there’s only so much you can do with cubes, and this mathematically organic aesthetic I find most intriguing. Do what you must, Shamus, I recon I’ll keep getting more and more impressed by your work.

    1. Pete says:

      Well technically Shamus Cubepoints(tm) are voxels, so it makes sense the result would look similar.

      1. Zukhramm says:

        Technically technically, being an analogue to pixel, voxel would only mean single colored cubes used to make up a 3D picture.

      2. TMTVL says:

        He totally should try to trademark “Shamus Cubepoints”. Or maybe “Youngian Cubepoints”.

        …Shamusian Cubepoints?

        1. Syal says:

          “Twenty Sided Cubepoints”.

          1. Chargone says:

            … the geometrical implications of that name are kind of scary…

            1. decius says:

              Well, given that it implies a ten-dimensional cube, and that people who understand more about physics/math than I can parse say that reality is 11-dimensional, I can believe it.

  10. Kian says:

    Two things. First, the drawn example for marching squares is missing a triangle. The top left square should have a triangle in the upper right corner. :)

    Second, I imagine the code you downloaded for the shapes accounts for all the possibilities that are really the same shape turned about in different directions? Meaning, the case of a single point in one corner of the cube is really one shape with 8 possible orientations, not 8 different shapes. Do you know how many unique shapes there actually are?

    1. Demo says:

      Counting shapes:

      0 corners:
      1 shape

      1 corner:
      1 shape

      2 corners:
      3 shapes (2.1 adjacent corners, 2.2 two corners diagonally opposite on the same face, 2.3 two corners completely opposite)

      3 corners:
      3 shapes (3.1 all corners on the same face, 3.2 two corners on the same edge and one corner on the diagonally opposite edge, 3.3 three corners adjacent to one corner)

      4 corners:
      6 shapes (4.1 all corners on the same face, 4.2 three corners share a face and the fourth corner is below the corner not on, 4.3 three corners share a face and the forth corner is below one on the ‘outer’ corners of the ‘L’ shape, 4.4 three corners are all adjacent to the fourth, 4.5 two corners share an edge and the other two corners are on the opposite edge, 4.6 no two corners share an edge)

      5, 6, 7 and 8 are the same as 3,2,1 and 0 respectively, so I count 14 shapes. There are some chirality issues however, which may require 3.2 and 4.3 to be counted again, depending on whether you allow reflection.

      1. Zukhramm says:

        How are 5, 6, 7 and 8 the same as 3,2,1 and 0? Wouldn’t they have the same number of configurations, but, of course, reversed? This would give 28 shapes, allowing reflection.

        1. Demo says:

          Because you need exactly the same polygons in both cases. Let’s look at 1/7 since it’s the easiest to see.

          If you have only one corner ‘on’ then everything else is outside so you cut off that one corner with a triangle through the centre of the edges which meet at that corner.

          If you have seven corners ‘on’ then the one corner that is ‘off’ is outside and so again you cut it off with a triangle through the centre of the edges which meet at that corner.

          I believe there is a difference when you want to texture, since I think that then knowing which side is inside and which side is outside matters. In that case we need to count the shapes for 4,5, 6,7 and 8 to get 28 shapes. We count the 4s twice, since if you turn all the ‘on’ corners ‘off’ and all the ‘off’ corners ‘on’ then you still have 4 on corners so nothing new, but now the inside and outside are in a different place.

    2. Paul Spooner says:

      As it turns out, memory is cheaper than Shamus’ programming hours. This means that the brute force method (just generate all 256 permutations) is easier than being clever. Discovering and then coding all the symmetries might be more elegant, but I’ll bet it takes ten times longer to program and gives you an identical result.

  11. skeeto says:

    The result is that I have pages and pages of disabled code and a dozen or so things that no longer work.

    The whole point of using source control is so you don’t need to comment out huge swaths of code, you just delete it. :-) You do experiments on feature branches and merge the working parts back into your main branch when you’re happy with it — or you just throw the whole branch away if it doesn’t work out.

    1. Brandon says:

      For wildly experimental coding projects that are not expected to really amount to anything other than your own satisfaction that something works or doesn’t work, I think version control is massively overkill.

      Not to mention a pain in the ass to set up and remember to use.

      1. Sean says:

        I used to think that way, until on a personal project where I said “Bah, I don’t need revision control!”

        .. 5 hours into backtracking my changes and attempting to recreate what was once working after a failed experimental approach, I changed my mind.

        The < 30 minutes of work to set up revision control, and the change in coding habits to make it part of "finishing" a piece of code is well worth the cost. The freedom to experiment because I'm not afraid I'll lose something, and being able to recover when I eventually do fumble it is extremely valuable to me. I never worry about how my experiments will pan out, and I can just follow my creativity at first.

        1. harborpirate says:

          Agreed, source control seems unnecessary until you realize that you’re well and truly into a dead end.
          It really is quite terrifying to realize that you’ve modified a few thousand lines of code (or more) with no clear idea how to get back to a working project.

          Then operating without source control, EVER, seems like a bad idea.

          At bare minimum, directory copies at every stopping point is something you should never do without. (But really, a few minutes to set up a decent source control system that you can use over and over again is well worth it).

          1. WJS says:

            I think there’s at least some merit to the argument that doing it “properly” with branches etc. is overdoing it on something like this, but you should still be using version control, even if just basically as “Undo/Redo on steroids”.

      2. Kdansky says:

        Sir, you are doing it wrong. Version Control is the one and only thing you must never skip. Creating a mercurial repository is a one-click affair. Since I’m the guy who recommended .hg to Shamus, I’m pretty sure he hasn’t used it to its full potential, or even correctly. It’s a required skill to learn in software development, just like you need to know what “const” and “&” and “*” do in C++.

        1. Mephane says:

          class CrappyClass
          {
          public:
          SetSomething(std::string data);
          std::string GetSomething();
          private:
          std::string somedata;
          }

          It is entirely possible to do C++ without const and &. I have seen it in professional code. That example above is structured exactly like some of the stuff I have seen. The question is whether it is doable without making a bunch of other programmers facepalm all the time. XD

        2. Shamus says:

          For the record, I’m using mercurial on this project. I do check-ins several times a day. Project Octant here is on change #70 already.

          Large blocks of commented-out code are my “to-do” markers. “Either fix this or delete it”.

  12. swimon1 says:

    Marching cubes looks amazing. I’m guessing it is used in a lot of scientific computing? Because the pictures with the grey textures definitely has that 3d MRI/CT-scan or physics model aesthetic (the caves also remind me a lot of Jet Force Gemini in all the right ways ^^). If marching cubes can practically be used then I definitely think you should give it a try because it looks beautiful.

    1. Rick C says:

      If you follow the wikipedia link Shamus gave for marching cubes, you’ll see that it was developed exactly to produce 3D images from MRI slices.

      1. swimon1 says:

        Oh! Well look at that.

        1. Rick C says:

          It was news to me, too.

  13. Blobs. Reminded me about Amit Patel’s blog Blobs in Games. His blogs/pages are good and valuable – he’s written about algorithms and thoughts for games – maps, grids, hexes, pathfinding, maps and map generation.

  14. Anjin says:

    I love this stuff. I was laughing so hard by the time I got to “Well, the project is now well and truly broken.” So I apologize about any schadenfreude that I experienced.

  15. Chris says:

    “Screwing around and working on whatever I find interesting, and damn having a plan”

    Yes! This is more like it. Experiment with fun ideas like this and report back to us. Break some eggs if need be.

    I like where this blob thing is going. Run with it.

  16. Paul Spooner says:

    It seems like you shouldn’t need to calculate normals on the fly. You’ve got a limited set of cubes shapes right? Why not make a script to run through each case and generate a lookup table? That way you only do the calcs once. It’s not like you’re dealing with arbitrary geometry… Maybe I’m missing something here?

    Are you storing aggregated statistics in the tree? Things like “this octant is 80% solid” would be really useful for doing a rough implementation of Ambient Occlusion. plus You wouldn’t need to drill all the way down to the “Tile” scale to do changes to larger groups of blocks.

    Having a tool that removes or places more than one block at a time would be great, no matter if you’re planning on using the “blob” or “cube” visualization. Of course, then you get into the realm of “brushes”, from which many brave souls have never returned.

    1. Shamus says:

      “It seems like you shouldn't need to calculate normals on the fly. You've got a limited set of cubes shapes right? Why not make a script to run through each case and generate a lookup table? That way you only do the calcs once. It's not like you're dealing with arbitrary geometry… Maybe I'm missing something here?”

      Heh. Basically, to answer any of this would be skipping ahead, but you and I had the same idea.

      1. Kdansky says:

        Okay, I’ve looked up what your problem probably is: You have to do some linear algebra. Normals work like this:

        1. Calculating triangle normals: Take all three corners of a triangle, and figure out the normal: CrossProduct(v2-v1, v3-v1). Store those buggers.

        2. For each vertex, figure out your vertex normals by doing a weighted average over the adjacent triangle normals. The weight is decided by the angle. And here’s the tricky part: If you do this naively, you will write a cos() somewhere, and that’s terribly slow. Instead, do some linear algebra and figure out the short cut with a dot product.

        3. (Optional) The slowest thing will be the square root when normalizing, and in this case you can safely substitute that for something from wikipedia without issue.

        4. Tada, blazing fast normals, because you’re only iterating over your triangles and vertices once each, and only doing basic multiplication, bitshifting and additions. If you still suffer issues, I would recommend to rethink how you store vectors, because most likely your caching behaviour is abysmal.

      2. Mephane says:

        I am looking forward to this. This is really exciting, like a good book or movie. Will the lookup-tables be pre-created? Will they be written in code or some self-made file format optimized for that purpose? Will they be calculated when the program is launched, and then reused? Will there be a function with a static local object that it returns a reference too, or will it return a pointer? Or just a global object that is written to at the beginning of main? Is my nerdiness beyond sanity because I am genuinely excited now? XD

  17. HBOrrgg says:

    So do all blocks work like this now or is it still just the “soft” blocks? I was really looking forward the idea of dirt behaving completely differently from stone when you try to build with it.

    1. decius says:

      I can’t imagine there coexisting two different implementations. Previously, blocks were defined as filling a volume, and the previous implementation of slopes was a special case of determining the volume. In this, blocks occupy points, and the volume is determined by which points are filled.

      I could be wrong, as always.

      In either case, I’m looking forward to seeing how texturing is handled when two different types of material meet.

      1. HBOrrgg says:

        It’s still a cubic grid which means you can fit cubes in it. If a particular point was labeled “brick” then instead of following the same rule as dirt you would place a cube surrounding that point 0.5 m in each direction. I could see it taking a lot of work to implement, but if it was then he could play with blobs and cubes at the same time!

        1. decius says:

          It gets rather confusing when I try to figure out what behavior should be, for the general case. One thing I might suggest would be rotating the grid 45 degrees from down, and then making ‘bricky’ blocks always create the same cube that a single point would make using the marching cubes algorithm.

  18. Spammy says:

    I have to say, I’m pretty curious now to see what building and exploring is like in the world of blobs. Since there are only points and not cubes… if this were a Minecraft-like game you’d collect points and not blocks? Or a certain volume of stuff? What would a tree look like if that were the case?

    I’m sure you’re tired of hearing people compare every project you work on to Minecraft, but that’s just because you make things that look interesting to explore and make me wish I had enough programming confidence to try to make them work on my hardware.

    1. HBOrrgg says:

      I think at the moment it’s just placing points, if you put two right next to each other then they magically fill in the space between. I imagine trying to actually deal with volume would be opening up an entirely new can of worms.

      1. WJS says:

        I don’t see why, it’s all just terminology. You could just as easily say that “a block of dirt” in Minecraft is “a cubic meter of dirt”, and you’d be saying exactly the same thing.

  19. SyrusRayne says:

    Okay, this looks pretty damn cool. I love this kind of terrain deformation. Don’t get me wrong, I love Minecraft, but I feel like this has a much different, and in some ways better, style.

    For example, perhaps a shooter type of game on an alien world. You crash land, have to fend for yourself in the environment, avoiding aliens and so forth. Maybe if you do some code to generate weird looking cities you could add stealth mechanics, and (procedurally generated,) alien technology and stuff… I’d play that game.

    What was I talking about again?

  20. Marmakoide says:

    It’s begging for tri-planar texturing, but the “corner-removed cubes + vertex colored blobs + detail texture” looks *awesome*. It’s cute, recognizable and original. Last screenshot feels like there is a lot of potential behind :)

  21. Scott Richmond says:

    Thank christ you used Marching Cubes. I was going to explode if you continued down the path of writing you’re own crazy sudo-marching algorithm.
    I just wanted to point out that if you felt like more of a challenge and a much more unique look, take a look at Dual Contouring. Its a much more complex iso marching algorithm but gets better results.

  22. Cybron says:

    Looking very cool. Would love to see your solution on the lighting issue.

  23. Annie Moose says:

    OK, now that is just plain cool-looking. It’s still got the Minecraft base of blocks to it, but now it looks (and presumably feels) completely different, with the blocks more or less disguised. Even with just rough textures on it, it looks pretty sweet, very very organic.

    How is walking around in it? Do you still have to jump up hills like with blocks or is that not an issue?

    EDIT: Also, should mention that the “maze” tunnel screenshot reminds me of the HL2:E2 antlion tunnels. Which is a pretty cool thing, because I thought those looked awesome.

  24. Steve C says:

    What are you using to make the non-screenshot blog images?
    IE: octant10_3.png octant10_8.png

    1. Shamus says:

      Paint shop pro 8. The poor man’s Photoshop.

      1. Drew says:

        I thought GIMP was the poor man’s photoshop.

        1. X2Eliah says:

          From what I’ve used, GIMP is the dead man’s photoshop… Because only a dead person woudl have the patience to wait until that thing finishes a single fx operation >:|

          1. Paul Spooner says:

            Yeah, and Blender is the dead man’s Maya, because only the dead have enough time to waste learning how to use it.
            I use both by the way. Really nice tools once you conquer the “Matterhorn-like learning curve”.

            1. Kdansky says:

              The Matterhorn isn’t very steep. Use Eiger for your metaphor. :P

        2. harborpirate says:

          GIMP is the homeless man’s photoshop.

          GIMP just recently got around to supporting a “single window” mode; they probably should have added that about a decade ago.

          I actually use it frequently, but ease of use is a foreign concept in that beast.

      2. Anachronist says:

        I love Paint Shop Pro. I’m still on version 5 though, and it suits my needs just fine. I think Windows95 didn’t even exist when that came out.

  25. Bryan says:

    Hmm, re-reading the glMesh.cpp code again (from project frontier), I think I see another bug. (In CalculateNormalsSeamless() only; CalculateNormals() is fine.)

    See, GLvector’s x/y/z coordinates are floats. But floats have problems with rounding: depending on compiler optimization, this:

    float a = 0.1;
    float b = a * 2;
    
    if (a == 0.2) {
      printf("okn");
    } else {
      printf("arrrrgn");
    }

    might print “arrrrg”, instead of the expected “ok”. (Because 0.1 is not exactly representable in any less-than-infinite number of IEEE-754-format bits. Just like 1/3 is not exactly representable in any less-than-infinite number of base-ten digits. So 0.1 * 2 is not necessarily exactly equal to 0.2.)

    Anyway, the issue in CalculateNormalsSeamless is that the GLvectors in _vertex are not necessarily exactly equal, even if they’re close enough that they should be treated as equal for the purposes of merging to calculate a normal. And operator== for two GLvector instances relies on the three pairs of numbers being exactly equal.

    Just pushed a fix to bitbucket, although it uses std::fabs() directly (in all the operator== overloads), and I don’t know if VS has that available. Still:

    https://bitbucket.org/bryankadzban/frontier/changeset/67c40a43552b

  26. Bryan says:

    Hmm, wait. I wonder if you could calculate the normals in a (Cg or GLSL) vertex program, and do the lighting then? You’d have to pass the nearby vertices down to the program for each point being drawn, and it might end up taking too long during rendering (instead of passing a bunch of normals that get calculated once, you recalculate them every time you render anything), but that calculation *seems* to be pretty parallelizable, and GPUs should be good at that kind of thing.

    Not sure what to do about the Seamless() variant though. Something would still have to combine vertices somewhere. Maybe not worth it in that case.

    (Or maybe you can just precalculate the normals for any shape, as you seem to have indicated you’re going to try.)

    Also, IIRC you aren’t using shaders yet in this project anyway, so that would make it a bit hard. :-)

    1. Simon Buchan says:

      Can’t compute normals in a vertex shader, because they only give you a single vertex at a time, and you need to know where the vertices around you are to compute a normal. You *can* do it in a *geometry* shader, though: they give you a vertex and all of the vertices connected to it, *almost* exactly what you need: the problem is in figuring out how to have normals pointing the right way – telling the difference between the inside and outside of a bowl is half of the job of normals, afterall.

  27. ClearWater says:

    Those first screen shots with the marching squares algorithm remind me of M.C. Escher’s Bond of Union: http://www.leninimports.com/m_c_escher_bond_of_union_art_print.jpg

  28. Mephane says:

    Personally, I love the new approach and the blobs. It even makes the tech feel more advanced that mere cubes, even though the underlying idea is still basically the same. :D

  29. TheMich says:

    Look again! The cubes are now diamonds!

    1. Chargone says:

      “I’m on a horse ”
      “moo!”
      *looks down, looks back up*
      “cow.”

    2. decius says:

      Diamonds with all edges of equal length and all angles are right angles…

      The cubes have been rotated! Now I can’t recognize anybody; I can’t tell the staff from the customers.

    3. Paul Spooner says:

      I believe the term is “Octahedron”. I prefer the “Truncated Hexahedron” myself, but that’s adding all kinds of extra polygons.
      Of course, you could go with an arbitrary point cloud instead of a structured cubic spatial framework. You’d end up with arbitrary planar solids, which look a lot like crystals.
      http://www.peripheralarbor.com/gallery/v/CG+Art/scripts/crystal/
      But that’s going a bit far, wouldn’t you say?

  30. Dasick says:

    Is it possible to combine the previous and this approach? Voxels looks pretty darn good for natural terrain, but I recon it’d look mighty queer for geometric, man-made structures.

    How hard would it be to have ‘solid’ blocks that behave as cubes, and have ‘blob’ blocks that behave like this?

  31. BvG says:

    Wow, that’s insane.

    Why didn’t you stay with cubes (internal representation) and then modify the landscape using slopes wherever they’re needed based on cubes being there or not. That way, you’d auto-generate the slopes, based on changes in the landscape, instead of having to change the whole “game” around to use diamonds?

    1. Kian says:

      He tried that first, an update or two ago. It didn’t work the way he wanted it to.

    2. WJS says:

      The internal representation wasn’t cubes, it was voxels, just like this. This is just a different method of converting them to polygons for the GPU.

  32. John Lopez says:

    I quite like the direction this is going. If you can find a compatible texturing model, this could create very realistic looking cave systems with real time deformation.

    As far as the tunneling taking too long, this more organic looking terrain seems amiable to a toolset that includes larger and smaller “picks”. A 2×2 pick may be a good default, with 1×1 being used for detail work.

    1. harborpirate says:

      I agree, this method has some serious promise.

  33. Thom says:

    I was thinking something like this when I started reading about the project. I’ve played a lot of Transport Tycoon, and the landscaping in the game uses something like this to raise and lower land. The world is made out of squares/cubes, but you raise/lower the corners of those squares and the game makes it look sort of nice. It’s impossible to make a cube, but when one point is raised one level, it makes a nice “pyramid” with 4 sloped sides up to the one point.

    I really like the idea and hope this is the direction it’ll be going with your project.

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 decius Cancel reply

Your email address will not be published.