<\/td><\/tr><\/table><\/p>\nAnd wind up with this:<\/p>\n
 <\/td><\/tr><\/table><\/p>\nI 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.<\/p>\n 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<\/em>. 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.<\/p>\n It looks like marching cubes<\/a> 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. <\/p>\n 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<\/a>, which is the same idea, but implemented in only 2 dimensions. <\/p>\n (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.)<\/p>\n 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.<\/p>\n 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. <\/p>\n 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.<\/p>\n Hm. Kind of interesting. I did have to break everything<\/em> 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.)<\/p>\n 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.<\/p>\n 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.<\/p>\n 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. <\/p>\n The problem is that I can’t light this thing properly. To do lighting, you need surface normals<\/a>. 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. <\/p>\n 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. <\/p>\n 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:<\/p>\n For comparison, here is the same location rendered with the old cube system.<\/p>\n I add some texture maps. These just use my old brain-dead mapping logic from part 6<\/a>. 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. <\/p>\n It’s sort of amazing how organic this looks. This is the same sort of data-set I’ve been using since part 5<\/a>. 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. <\/p>\n I add some simple vertex coloring to the mix and have it generate a simple “maze”.<\/p>\n (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.)<\/p>\n 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. <\/p>\n 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.<\/p>\n Well, the project is now well and truly broken. I migrated from Qt back to Visual Studio, as I discussed in part 8<\/a>. 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. <\/p>\n 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: And wind […]<\/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-15945","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\/15945","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=15945"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/15945\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=15945"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=15945"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=15945"}],"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
<\/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","protected":false},"excerpt":{"rendered":"