tag:blogger.com,1999:blog-82282246816598757652024-03-05T16:35:31.935+01:00HexahedraA C++ framework for voxel games.Unknownnoreply@blogger.comBlogger26125tag:blogger.com,1999:blog-8228224681659875765.post-64334425789270028772012-10-02T16:05:00.000+02:002012-10-02T16:22:21.722+02:00User interfaces and flightless birdsThere are several ways to build a graphical user interface.<br />
<div>
<br /></div>
<div>
The oldest one is absolute positioning. For every button, label, etc., you specify the position and the size yourself (usually in pixels). Anybody who has ever used <a href="http://en.wikipedia.org/wiki/Microsoft_Foundation_Class_Library">MFC</a> knows why this is a bad idea. If you want a resizable window, you'll have to catch the window events yourself, and calculate/set the position and size for each widget. Translations usually break the layout; your best bet would be to make separate dialogs for every language.</div>
<div>
<br /></div>
<div>
A very popular method is the box/packing/struts/glue/springs model. It might even have a proper technical name. You define a layout using horizontal and vertical containers, anchor points, springs, fixed spacings, and the toolkit does the layout for you. Much better already!</div>
<div>
<br /></div>
<div>
Another method is the constraints-based layout, and it has been slowly gaining popularity. It is not new; the first Lisp implementations appeared in the early 90s. But for example, it is the recommended way to define user interfaces in <a href="http://kb.applingua.com/2011/07/localization-dream-cocoa-autolayout/">Cocoa since OS X Lion</a>, and Adobe also uses it in their <a href="http://stlab.adobe.com/group__asl__overview.html">Adam and Eve</a> framework. In a constraint, you can say, "okay, I want this button left-aligned with this widget, and somewhere below the title", or "I want this field to be just as wide as that one, and preferably somewhere between 40 and 250". The widgets are then laid out according to your wish list.</div>
<div>
<br /></div>
<h2>
UI requirements for Hexahedra</h2>
<div>
For the readers who just tuned in: in Hexahedra, all mods/plugins run on the server. This means we have the following requirements for the in-game user interface:</div>
<div>
<ul>
<li>Network transparency.</li>
<li>Has to be able to adapt to different resolutions and screen layouts.</li>
<li>Good localization support. Not just translations to other languages, but also adapting to right-to-left languages.</li>
<li>Support for client-side themes.</li>
<li>Must be easy to define.</li>
</ul>
<div>
Given all that, the constraints-based method sounds pretty good.</div>
</div>
<div>
<br /></div>
<div>
The first thing I need is something that eats constraints and poops a widget layout. Turns out such a beast is called a linear constraint solver. There are several, such as Indigo, Ultraviolet, and LP-solve. But the best candidate for the task at hand is <a href="http://www.cs.washington.edu/research/constraints/cassowary/">Cassowary</a>.</div>
<div>
<br /></div>
<div>
Cassowary hasn't been updated in a decade. It doesn't build on my system without tweaking, it has a bug or two, valgrind reports memory leaks, and defining constraints with it is pretty awkward. Besides, I really want to know how it works in detail.</div>
<div>
<br /></div>
<div>
You can guess where this is heading.</div>
<div>
<br /></div>
<h2>
Rhea</h2>
<div>
So yeah. <a href="https://github.com/Nocte-/rhea">Rhea</a>. It still needs to be documented and packaged properly, but it's definitely in a usable state.</div>
<div>
<br /></div>
<div>
The user interface library that is sitting on top of Rhea is still under heavy development, but I can show you where it's headed. Let's set up a frame with three text labels in it, and use Rhea to define and solve the constraints:</div>
<div>
<br /></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> ui::theme t; </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> ui::label <b>a</b> (t, L"AAA"), <b>b</b> (t, L"BBBBBBBBBB"), <b>c</b> (t, L"CCCCC");</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> ui::frame <b>box</b>;</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> rhea::simplex_solver s;</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"></span><br />
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.add_constraints(</span></div>
<span style="font-family: Courier New, Courier, monospace;">
</span>
<div>
<span style="font-family: Courier New, Courier, monospace;"> {</span></div>
<span style="font-family: Courier New, Courier, monospace;">
<div>
box.top == 0, // Keep the frame's corner at 0,0</div>
<div>
box.left == 0,</div>
<div>
<br /></div>
<div>
a.top == box.top, // Align 'a' in the top left corner</div>
<div>
a.left == box.left,</div>
<div>
<br /></div>
<div>
b.top == box.top, // Align 'b' along the top</div>
<div>
b.left >= a.right, // Make sure b is right of a</div>
<div>
<br /></div>
<div>
// Make sure b is horizontally centered, but make it a</div>
<div>
// weak constraint. If there's not enough room, b will</div>
<div>
// be placed as close to the center as possible, but always</div>
<div>
// to the right of a (the stronger constraint).</div>
<div>
//</div>
<div>
// Note that 'h_center' is actually a linear expression;</div>
<div>
// the frame class defines it (quite literally) as</div>
<div>
// "left / 2 + right / 2".</div>
<div>
//</div>
<div>
{b.h_center == box.h_center, rhea::strength::<b>weak</b>()},</div>
<div>
</div>
<div>
b.right <= box.right, // Make sure b still fits</div>
<div>
<br /></div>
<div>
c.top >= a.bottom, // Place 'c' somewhere below 'a'</div>
<div>
c.bottom <= box.bottom, // Make sure it's inside the frame</div>
<div>
c.left == box.left, // Keep it left-aligned</div>
<div>
c.right <= box.right</div>
<div>
});</div>
<div>
<br /></div>
<div>
// And yes that is actually C++.</div>
</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: inherit;">Now that the user interface is defined, the labels will ask the theme for a preferred size (based on the font and the text), and we can tell the solver what we want. In this example, the theme simply assumes every character in a text label is a 20x20 square. Now, let's say we want the frame to be 200 x 150:</span></div>
<div>
<span style="font-family: inherit;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.add_edit_var(box.width).add_edit_var(box.height);</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.begin_edit();</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.suggest_value(box.width, <b>200</b>);</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.suggest_value(box.height, <b>150</b>);</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> s.end_edit();</span></div>
<div>
<br /></div>
<div>
"Edit variables" are special variables in the Cassowary algorithm. A new value can be <i>suggested</i> for them, and the existing constraints are re-solved with a minimum of overhead. Speed is important to keep the UI feel responsive. The widgets now have the following dimensions: (shown <span style="font-family: Courier New, Courier, monospace; font-size: x-small;">[left, top ; right, bottom](width x height)</span> .)</div>
<div>
<br /></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> box : [0,0;220,150](220x150)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> a : [0,0;60,20](60x20)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> b : [60,0;220,20](160x20)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> c : [0,130;100,150](100x20)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEih4qWHgeQIXFKnOCX43wBpBlGOfsURH_iGv6-yBaXR7s3j0PayPgTiFprmCjU5OBmriwkzJlNAcFNXBEZNpEiQb-Td4xvTSsTdKMOL7WUxZ9lmclRv7Px6sRlJYN7dKrFuLDzhEU5QRkzg/s1600/rect2987.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="130" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEih4qWHgeQIXFKnOCX43wBpBlGOfsURH_iGv6-yBaXR7s3j0PayPgTiFprmCjU5OBmriwkzJlNAcFNXBEZNpEiQb-Td4xvTSsTdKMOL7WUxZ9lmclRv7Px6sRlJYN7dKrFuLDzhEU5QRkzg/s200/rect2987.png" width="200" /></a></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: inherit;">We suggested a width of 200; the solver decided to make it 20 wider, so it ended up <b>220</b> x 150 instead. There was one weak constraint it could drop: 'b' is not centered inside the box. But given all the other requirements, the box just couldn't get any smaller than 220. (That's pretty neat: I never actually had to specify this number anywhere, the solver figured it out for me.)</span></div>
<div>
<span style="font-family: inherit;"><br /></span></div>
<div>
<span style="font-family: inherit;">What if we suggest a width of <b>600</b> instead?</span></div>
<div>
<span style="font-family: inherit;"><br /></span></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> box : [0,0;600,150](<b>600</b>x150)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> a : [0,0;60,20](60x20)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> b : [220,0;380,20](160x20)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"> c : [0,20;100,40](100x20)</span></div>
</div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDu9AzojsC6zGtKg5Xj7gWrAnwyMKfj5PuBx5r0mtNUgI6J2-dtuC5MxNY5oNH4pxKzkynxyh63mGczF_Q-RLNB6RxFexiKYao_KEImXrqNebNk4QjRmjagoRG-E9-oXk62J0eA-joa9md/s1600/rect2988.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="100" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDu9AzojsC6zGtKg5Xj7gWrAnwyMKfj5PuBx5r0mtNUgI6J2-dtuC5MxNY5oNH4pxKzkynxyh63mGczF_Q-RLNB6RxFexiKYao_KEImXrqNebNk4QjRmjagoRG-E9-oXk62J0eA-joa9md/s400/rect2988.png" width="400" /></a></div>
<div>
<span style="font-family: Courier New, Courier, monospace;"><br /></span></div>
<div>
<br /></div>
<div>
The 'B' label now has enough breathing space to be centered properly.</div>
<div>
<br /></div>
<div>
So we have a resizable window, where an element is centered, unless it bumps into another. The window has a proper minimum size. The layout will also adjust automatically whenever the labels are translated to another language, or a different theme is used. Not bad for 13 really short lines of c++.</div>
<div>
<br /></div>
<h2>
Up next</h2>
<div>
There have been a few other big changes in Hexahedra, so the next blog post will probably be about <a href="http://enet.bespin.org/">ENet</a> (the new UDP network protocol) or <a href="http://lee.fov120.com/iqm/">IQM</a> (the new model format). But UI Part 2 will look at the behavior side of the widgets, hopefully with some actual video footage.</div>
<div>
<br /></div>
<div>
<br /></div>
Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-8228224681659875765.post-61269019970008548752012-09-03T00:13:00.000+02:002012-09-03T09:17:42.542+02:00User interface : the hotbar<div class="separator" style="clear: both; text-align: justify;">
The hotbar is a staple of game interfaces, and no Minecraft clone can do without it. Players can drag items, blocks, spells, or other actions to one of its slots for easy access.</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
After shamelessly grabbing some graphics from <a href="http://www.minecraftforum.net/topic/513093-32x16x132-dokucraft-the-saga-continues/">Dokucraft</a>, this is what it looks like in Hexahedra:</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigsGgmzdw4mbylHnPa7kcwIqr5Kc3QC2vkNEZapbk3VABL0TZCK8Tfu_XoLgks-hWLPlNrAIUxtYW90ntNITFIMEjPnnaFMwNi447JACMZeUYKdiOsqjC_vTLWKn_s6yxR06yRkkyALJEy/s1600/hotbar.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEigsGgmzdw4mbylHnPa7kcwIqr5Kc3QC2vkNEZapbk3VABL0TZCK8Tfu_XoLgks-hWLPlNrAIUxtYW90ntNITFIMEjPnnaFMwNi447JACMZeUYKdiOsqjC_vTLWKn_s6yxR06yRkkyALJEy/s1600/hotbar.jpeg" /></a></div>
<br />
<div style="text-align: justify;">
In Minecraft, it's a single bitmap. In Hexahedra, you need to cut it into smaller pieces: a left "cap" (the rounded corner), an empty slot, a separator (the grey dot between the slots), something to indicate the active selection (the triangles at the top and bottom), and a right cap.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
It might sound complicated, but it's for a good reason. Everything is controlled server-side, so it needs to be dynamic. Using Lua scripts, the server can at any given moment change the size and layout of the hotbar. The example you see here was generated with:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">on_login(function(plr)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> plr.hotbar_size = 12</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> plr:hotbar_set(0, hotbar_slot(1, "cobblestone"))</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> plr:hotbar_set(1, hotbar_slot(2, "firstaidkit"))</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">...</span></div>
<div>
<span style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> plr:hotbar_set(9, hotbar_slot(1, "snow"))</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> plr:hotbar_set(10, hotbar_slot(1, "glass"))</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">end)</span></div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div style="text-align: justify;">
The function <span style="font-family: Courier New, Courier, monospace;">hotbar_set</span> takes a position, and a slot object. The first parameter of the slot determines its type. The following types are available:</div>
<div>
<ul>
<li>Empty</li>
<li>Showing a material, either as a block turned 30 degrees, or as a custom 3D model (such as the fence post in slot 7 in the image)</li>
<li>Showing an item</li>
<li>Showing a custom icon that represents an action (for example, casting a spell)</li>
<li>A section separator, for splitting the hotbar in two or more sections</li>
</ul>
<div>
Also, a slot can have one or more extras:</div>
</div>
<div>
<ul>
<li>A colored crawl bar (item damage, gun ammo, ...)</li>
<li>A number</li>
<li>A small badge in the lower right corner (powerups, enchantments)</li>
<li>A cooldown timer</li>
<li>A disabled mode</li>
<li>A locked mode (player can't drag it anywhere, or drag another item onto the slot)</li>
<li>An action mode (slot cannot be the current selection, but the player can trigger its action with a keypress)</li>
</ul>
<div style="text-align: justify;">
Sometimes, a material can't be represented by its 3-D model. For example, a door consists of two blocks, each with its own material. In this case, the programmer should provide an item that represents it with a proper icon, and hook up the appropriate callbacks to this item.</div>
</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Being able to control the hotbar from the server is great. Yes, you can make it behave just like in Minecraft. But you could also replace broken tools automatically from the player's inventory. For the infinite blackboard game, I just set it to one icon that shows the player's crayon color. For the tower defense game, the hotbar slowly grows as the player unlocks different tower types. Perhaps you need a RPG setup with separate attacks, spells, and items, with the number of slots depending on the character's level? </div>
<div style="text-align: justify;">
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-45891949428209877542012-08-07T13:03:00.000+02:002012-08-07T13:03:31.691+02:00DIY fencesBehold! A fence!<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgky5jPxq1PR0Qpd_ELhxwhCsdMnoyFfhNOfISbeOmlE4OzLGRWPDKpO2oy4ktPwU4_0SkCr0Rj466Mw_5zgMK45fC2QygZIHaMJg6PrzFQyP9xLew1eeAPmuU_ypmIbqG0ZkmYqpG2xY3m/s1600/screenshot.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="266" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgky5jPxq1PR0Qpd_ELhxwhCsdMnoyFfhNOfISbeOmlE4OzLGRWPDKpO2oy4ktPwU4_0SkCr0Rj466Mw_5zgMK45fC2QygZIHaMJg6PrzFQyP9xLew1eeAPmuU_ypmIbqG0ZkmYqpG2xY3m/s400/screenshot.jpeg" width="400" /></a></div>
<br />
Now, fences aren't all that exciting. Minecraft's had them for almost two years now. No, the cool bit is how they were scripted.<br />
<br />
<h3>
The 3-D model</h3>
<div>
Unlike items and mobs, custom block models cannot be imported from just any Blender or Collada file. To keep things manageable, they are essentially a 16x16x16 chunk scaled down to the size of a block. You define them as a list of boxes, where all coordinates are integers, limited from 0 to 16. Every face of every box can be textured individually, the same way a normal block can.</div>
<div>
<br /></div>
<div>
For example, here's a snippet of the Lua script that defines the materials:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">define_material({ name = "<b>fence.0000</b>",</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> on_place = place_fence, on_remove = remove_fence,</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> <b>custom_model = { { 7, 7, 0, 9, 9, 15, "fence" } }</b> })</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"><br /></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">define_material({ name = "<b>fence.000E</b>",</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> on_remove = remove_fence,</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> <b>custom_model = { { 7, 7, 0, 9, 9, 15, "fence" }, </b></span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"><b> { 10, 8, 10, 15, 8, 12, "bark" } }</b> })</span></div>
</div>
<div>
<br /></div>
<div>
A fence can connect to its neighbors in any combination of the four cardinal directions, so we need 16 different models in total. You're free to pick any name you like, but I've used a naming system here that shows in which directions the fence extends. "Fence.0000" is just a post, a single box with the 'fence' texture. "Fence.000E" extends to the east, and consists of the same post, and another box with the much darker 'bark' texture. We also need "Fence.00W0", "Fence.00WE", "Fence.0N00", and so on.</div>
<div>
<br /></div>
<div>
(Ordering the models by binary counting will come in handy later.)</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVS2vDqLt7EhlzxuckCC9TeMvMMVpPyUtbT4AnEllekBINT5l1ZhaOacKPHwHIZCUSh_Tl-hG5AjPQ5xrhmtX5ns7XD8rpkWb7JKcBekr1jqV3HpHUL3WppXb5x5wxCW_TOZ8tNM5Ro0RX/s1600/screenshot2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="266" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhVS2vDqLt7EhlzxuckCC9TeMvMMVpPyUtbT4AnEllekBINT5l1ZhaOacKPHwHIZCUSh_Tl-hG5AjPQ5xrhmtX5ns7XD8rpkWb7JKcBekr1jqV3HpHUL3WppXb5x5wxCW_TOZ8tNM5Ro0RX/s400/screenshot2.jpeg" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<i>Examples of fence models</i></div>
<div>
<br /></div>
<div>
All this info is sent to the client on login. So if you join a server, there's no need to install anything, you automatically get to see whatever cool custom blocks they designed for their map.</div>
<div>
<br /></div>
<div>
This is nice for static decoration, but if you want to give the player the opportunity to build his or her own fences, there's a little more scripting involved.</div>
<div>
<br /></div>
<div>
(Note: the idea for custom block models isn't quite new, Minetest recently added "<a href="http://minetest.net/forum/viewtopic.php?id=2333">nodeboxes</a>" that can do the same thing.)</div>
<div>
<br /></div>
<h3>
Scripting the behavior</h3>
<div>
Every fence material gets a number. We'll say 'fence.0000' is material number 100, and the others are numbered incrementally. If the player places a fence, the value in the chunk's array gets changed from 0 (air) to 100, and a fence post appears. So far so good, but the second fence placed right next to it also looks like a post. When this happens, we want to connect the two. So the first one should change from 100 to 104 ('fence.0N00'), and the other to 108 ('fence.S000').</div>
<div>
<br /></div>
You might have noticed we had already provided an 'on_place' and 'on_remove' callback for the fence materials. The first one, place_fence, looks like this:<br />
<br />
<br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">local function is_fence(a, b)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> return b >= a and b < (a + 16)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">end</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"><br /></span>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">local function <b>place_fence</b>(p, id)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local e = p + vec(1, 0, 0)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local n = p + vec(0, 1, 0)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local w = p + vec(-1, 0, 0)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local s = p + vec(0, -1, 0)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> </span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(e))) then</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> id = id + 1</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(e, get_block(e) + 2)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(w))) then</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> id = id + 2</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(w, get_block(w) + 1)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end </span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(n))) then</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> id = id + 4</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(n, get_block(n) + 8)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end </span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(s))) then</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> id = id + 8</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(s, get_block(s) + 4) </span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> </span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(p, id)</span><br />
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">end</span><br />
<div>
<br /></div>
<div>
'place_fence' only gets called for "fence.0000". The parameters are the position, and the material ID (in this case, 100). We use this ID to check the four neighbors (<span style="font-family: Courier New, Courier, monospace;">e, w, s</span>, and <span style="font-family: Courier New, Courier, monospace;">n</span>), to see if they are fences as well. This check is rather simple; we've registered 16 materials, so they should be somewhere in the range 100 to 116.</div>
<div>
<br /></div>
<div>
For every fence we find, we adjust the model of that neighbor block so it connects to the one we're about to place. And of course we adjust '<span style="font-family: Courier New, Courier, monospace;">id</span>' as well, we need to connect them both ways.</div>
<div>
<br /></div>
<div>
Removing a fence is very similar, but instead of adding a given value for each direction, we subtract it:</div>
<div>
<br /></div>
<div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">local function <b>remove_fence</b>(p, id)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local e = p + vec(1, 0, 0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local n = p + vec(0, 1, 0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local w = p + vec(-1, 0, 0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> local s = p + vec(0, -1, 0)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(e))) then</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(e, get_block(e) <b>- 2</b>)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(w))) then</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(w, get_block(w) <b>- 1</b>)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(n))) then</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(n, get_block(n) <b>- 8</b>)</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> if (is_fence(id, get_block(s))) then</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(s, get_block(s) <b>- 4</b>) </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> end</span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;"> change_block(p, <b>0</b>) </span></div>
<div>
<span style="font-family: Courier New, Courier, monospace; font-size: x-small;">end</span></div>
</div>
<div>
<br /></div>
<div>
No need to adjust '<span style="font-family: Courier New, Courier, monospace;">id</span>', at the end we're going to place an air block there anyway.</div>
<br />
<br />
<h3>
More to come</h3>
<div>
Of course, you can build much more with this API than just fences. Doors, stairs, window shutters, pipes, ladders, wooden beams, rails, you name it. How about fences that connect to walls as well? With gates? I'll leave all that to your imagination for now, and in the next few posts I'd like to show other parts of the API, such as the user interface and items.</div>
<div>
<br /></div>
<div>
<br /></div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-88531871804135884482012-07-17T23:57:00.002+02:002012-07-17T23:57:43.905+02:00And my axe!<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGV7z9yfGGBzimdB3VMHNKhixn56S7TDJtZFlb9y2wR4jhAbo86N2rU1mXrxac-QCpLPhoMBR28XZqy9PKbU-gy6qpzSBmuiyijv9WjTB3LW1TT8jkclwIlR7czCdtHiToPe8fo2PfK92O/s1600/axe.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="266" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGV7z9yfGGBzimdB3VMHNKhixn56S7TDJtZFlb9y2wR4jhAbo86N2rU1mXrxac-QCpLPhoMBR28XZqy9PKbU-gy6qpzSBmuiyijv9WjTB3LW1TT8jkclwIlR7czCdtHiToPe8fo2PfK92O/s400/axe.jpeg" width="400" /></a></div>
<br />
Got the brilliantly named <a href="http://assimp.sourceforge.net/">Assimp</a> library working, so I can now import every 3D file format known to man. I'm not a big fan of the high poly-count models seen in some other blocky games, but this axe just happened to be one of the example files, so I grabbed that one for testing.<br />
<br />
The standard renderer that comes with the library uses direct calls. The axe model has tens of thousands of triangles, so it's a miracle I'm still getting 30 FPS. So the next step would be to look for/create a proper VBO-based renderer, and get skeletal animations working (for mobs and players).<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-84146544245108497042012-07-03T16:17:00.000+02:002012-07-03T16:17:14.482+02:00More about voxel meshingThe 0FPS blog has a great article about meshing, that ties in nicely with my latest couple of posts here, and explains it better and in more depth than I ever could. <a href="http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/">Go check it out</a>!<br />
<br />
And after recording and posting that video about transparent surfaces, I've ran into cases where the sorting method does not produce the desired results. Back to the drawing board. :)<br />
<br />Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-8228224681659875765.post-28033972781465446292012-06-11T20:04:00.001+02:002012-06-11T20:15:17.539+02:00Polygon mergingHere's a screenshot in wireframe mode to show the merging in action:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGBMsMFu6UG_94_5OgxEzhX87_ex4w-QJhJLRqfUr4uY_S0MLXhtmmq0bQuNlYHeIbE_EsJxvGmPmxDqafw07pG_dsXIhiiGUuWd3HSnPz-jDFgo_mwjbGPzcxMZj9G-4_SXEUhdfF6s0o/s1600/reduce.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="250" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGBMsMFu6UG_94_5OgxEzhX87_ex4w-QJhJLRqfUr4uY_S0MLXhtmmq0bQuNlYHeIbE_EsJxvGmPmxDqafw07pG_dsXIhiiGUuWd3HSnPz-jDFgo_mwjbGPzcxMZj9G-4_SXEUhdfF6s0o/s400/reduce.jpeg" width="400" /></a></div>
<br />
In some of the large flat surfaces (grass and water) everything can be merged, and all that's left are the chunk boundaries. The polygon count is reduced by about 60% on average.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-43919120301252544282012-06-09T01:16:00.001+02:002012-07-03T16:08:58.426+02:00Sorting in depthA while back (too long!) I explained how to draw a bunch of cubes, and made a nonchalant remark about how it is important to draw everything in a front-to-back (or back-to-front, for transparent polys) order. Sorting all voxels by distance every time the camera moves is not an option, so we need to think of something else.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/pA2RsRRuwIA?feature=player_embedded' frameborder='0'></iframe></div>
<br />
<br />
<h3>
At the chunk level</h3>
The first thing we'll do is to sort all the chunks by their <a href="http://en.wikipedia.org/wiki/Taxicab_geometry">Manhattan distance</a>. Instead of calculating the distance using the <a href="http://en.wikipedia.org/wiki/Pythagorean_theorem">Pythagorean theorem</a> (what we usually think of as "distance", also known as Euclidean distance), it is the sum of the differences of all three ordinates. If the camera is in chunk (1,2,3) and we want to measure the distance to chunk (5,7,9), the differences in the x, y and z directions are 4, 5, and 6 respectively, and their sum is 15.<br />
<br />
The nice thing about the Manhattan distance is that, in our voxel world, it is always a whole number. We use this number to group the chunks, one group for each distance. Group 1 has no more than 6 chunks in it, while group 2 has no more than 18. (Try to imagine how this looks in 3D and you'll see why.)<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgHA_msfn-DoL6n_DbxYCbYNPhwhFHzfl1jZCdbSx4BevoY3Zfq0rqmR-_7AgmryGAoeUmjQbbZFJFc_SBsUA2fyK5hiBhQQ-FjawmcxdwkJ8hUSnFHVtCdivdoXutUxZmyTgto_GT7Kn2/s1600/fig1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="141" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjgHA_msfn-DoL6n_DbxYCbYNPhwhFHzfl1jZCdbSx4BevoY3Zfq0rqmR-_7AgmryGAoeUmjQbbZFJFc_SBsUA2fyK5hiBhQQ-FjawmcxdwkJ8hUSnFHVtCdivdoXutUxZmyTgto_GT7Kn2/s400/fig1.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Grouping chunks by Manhattan distance</td></tr>
</tbody></table>
It's kind of a lazy version of a <a href="http://en.wikipedia.org/wiki/Bucket_sort">bucket sort</a>. We only need to do this once. Whenever we want to render the scene, we traverse this data structure in order. The ordering of the individual chunks does not matter; no two chunks with the same distance can never overlap each other from the camera's perspective. This gives us more freedom to pick a suitable data structure, e.g. a hash table.<br />
<br />
The drawback is that every time the camera enters a different chunk, we need to shuffle this data structure. Luckily most of the operations are quite cheap. (For very, very large view ranges and slow CPUs, this can even be done in the background. Nobody will notice if one or two frames still use the previous, almost-correct sorting order.)<br />
<br />
<h3>
At the block level</h3>
<div>
The individual blocks within the chunk must also be sorted. This is trickier, because not only does the sorting order change every time the camera enters a different block, it also changes for some of the surrounding chunks.</div>
<div>
<br /></div>
<div>
We split the surface that needs to be rendered (the set of exposed block faces) into six stacks of 16×16 grid "slices". Six, because there's one stack for each cardinal direction.</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6mcf1vnN9_1rQgCsR1agQdKdZbiZ3Bm-Cz0x5NzIkaYuOBplZNhEnkX2vQlXqmVQapyvQ9YRAoGFkPGdeyRS9Sd-7Hv_hVLIuvm4lKvLJ9NtUSaQiCsEqs8N-LiPZS-kAwhi0qmn4LcZM/s1600/fig2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="181" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6mcf1vnN9_1rQgCsR1agQdKdZbiZ3Bm-Cz0x5NzIkaYuOBplZNhEnkX2vQlXqmVQapyvQ9YRAoGFkPGdeyRS9Sd-7Hv_hVLIuvm4lKvLJ9NtUSaQiCsEqs8N-LiPZS-kAwhi0qmn4LcZM/s400/fig2.png" width="400" /></a></div>
<div>
<br /></div>
<div>
Here we see an example. The stack of slices that corresponds to "up" holds the faces A and B. A is at (1,1) o slice 0, B at (1, 2) on slice 1, one level deeper. So in this case, the z-axis corresponds to the actual z-axis of the game world.</div>
<div>
<br /></div>
<div>
The stack that corresponds to "east" (or "right") holds I and II. Although A and B ended up in different slices, I and II end up in the same slice because the z-axis now runs west-to-east.</div>
<div>
<br /></div>
<div>
All six stacks are then drawn in their z-order. Here's an example of the player looking north, down the slices of an eastward grid:</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEijzFqi0s1KoqOnPHzLYM9PsO9DTYxx0FwgVlQZGVZgdaA3l9lcQK_7Wkpp5byg2NGjLh3qoRszZO99RgoZPmWmYLtKROEuDsKRHN_hzejjXESMWor8gIIIZTW6kF6fpiN90CENcmiR1lph/s1600/fig3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="177" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEijzFqi0s1KoqOnPHzLYM9PsO9DTYxx0FwgVlQZGVZgdaA3l9lcQK_7Wkpp5byg2NGjLh3qoRszZO99RgoZPmWmYLtKROEuDsKRHN_hzejjXESMWor8gIIIZTW6kF6fpiN90CENcmiR1lph/s400/fig3.png" width="400" /></a></div>
<div>
<br /></div>
<div>
The slices are drawn in right-to-left order in this case. Faces J and K are drawn normally. K is closer to the player, and is drawn on top of J. L is drawn even earlier, if it weren't for backface culling. (It would be possible to start drawing a K's slice, based on the camera position, but finding the right index in the vertex buffer is nontrivial. Besides, the GPU can do backface culling so fast it's not even funny. It's likely you'll spend more time on the CPU trying to find the right starting point.)</div>
<div>
<br /></div>
<div>
This is also where identical, adjacent faces are merged in OpenGL 3.x mode. It isn't difficult to detect the two "N" textures can be merged into a rectangle. Determining the optimal way to merge the faces is an <a href="http://en.wikipedia.org/wiki/Set_cover_problem">expensive</a> operation, so Hexahedra uses a simple <a href="http://en.wikipedia.org/wiki/Greedy_algorithm">greedy</a> algorithm. (Start at the top-left texture, and keep expanding a rectangle to the right and to the bottom until you encounter a different texture anywhere. Remove all textures in this rectangle, and repeat until the slice is empty.)</div>
<div>
<br />
<h3>
Für die Lulz</h3>
</div>
<div>
And because boring wall of text is boring, a video!</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/s2RuJom3XV0?feature=player_embedded' frameborder='0'></iframe></div>
<div>
<br /></div>Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-8228224681659875765.post-50480590595957916682012-02-12T22:48:00.000+01:002012-02-22T00:20:25.789+01:00Flying through ModernCity<div class="separator" style="clear: both; text-align: left;">
The whole "send surfaces only instead of whole chunks" bit now works properly, so I thought I'd show you guys a video.</div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/67CHFZW8vc0?feature=player_embedded' frameborder='0'></iframe></div>
<br />
(Omagosh I'm allowed to embed Youtube videos again? yay!)<br />
<br />
It seems the screen recorder didn't only kill the frame rate as per usual, but also messed with the occlusion queries. So you'll see the occasional hole in the terrain. Let's see if I can figure out why this happens...<br />
<br />
Edit: Fixed it by changing the occlusion system. We'll leave that for another blog post. In the meantime:<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/-qn3kwdmoto?feature=player_embedded' frameborder='0'></iframe></div>
<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-29259794427272747182012-02-05T13:07:00.001+01:002012-02-14T19:31:15.465+01:00How to draw a cube<br />
I'm not the only one who tried to draw a couple of cubes after seeing Minecraft, and every now and then I get questions from other programmers about how to structure the data and make it fast. So let's take a look at the basics of cube rendering.<br />
<br />
<div>
<br /></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif; font-size: large;">Structure and storage</span><br />
<br />
<br />
At the bottom level, we have a block, which is nothing more than a 16-bit value. This means we can have over 65,000 block types, although special block types could take up multiple slots. (For example, a staircase that can be placed in four directions would require four ID numbers.) There is a separate table that holds all the info for a given block type, such as the name, durability, transparency, the collision box, Lua hooks, etc.<br />
<br />
<div>
<div>
Then there's the chunk, a group of blocks arranged in a 16×16×16 cube. Or at least, that's the concept. In reality, it is an array of block types, and its size is fixed at 16³ = 4096 elements. (At 16 bits for a block type, that's 8192 bytes). The (x,y,z) position of a block is implicit: it is located in the array at index [x + y * 16 + z * 256].</div>
<div>
<br /></div>
</div>
<div>
<div>
Then, at the highest level, there's the game world. This is a really, really big cube (4.3 billion blocks in every direction: a few times larger than our own sun), and it's sliced up in chunks.</div>
<div>
<br /></div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG284SPpYYPIff2RfrTpx-d2kwr9n-vWEyu1I-oqC8zxV-54qHVU9nWFNENIrQOW1mZxzE53hyagEPqypt-fZc2yK8aNZ7-f7Tl5qgoW7nAdwq5iry3v3cXXE4b1lTk2_Vc0_Um-Z5k_R9/s1600/hexa-datastructures.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="316" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiG284SPpYYPIff2RfrTpx-d2kwr9n-vWEyu1I-oqC8zxV-54qHVU9nWFNENIrQOW1mZxzE53hyagEPqypt-fZc2yK8aNZ7-f7Tl5qgoW7nAdwq5iry3v3cXXE4b1lTk2_Vc0_Um-Z5k_R9/s400/hexa-datastructures.png" width="400" /></a></div>
<div style="font-size: x-large;">
<br /></div>
</div>
<div>
<div>
Unlike blocks, we don't have to keep all 19 septillion chunks in memory at all times. Chunks are positioned explicitly, meaning we store its position as well. This allows us to load and unload small sections of the game world as needed. I store them in a database, where the position is the primary key, and the chunk data is a blob of compressed data. Until recently it used 'deflate' as its compression algorithm. I switched to LZ4, because it is much faster (7 to 10 times) and compression is only a few percent worse on average.</div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif; font-size: large;">Rendering</span></div>
<div>
<br /></div>
<div>
<div>
Drawing the cubes on screen seems simple enough. Load the chunks that are near the player, then go through every block in every chunk. Grab the right texture for that block type, draw a cube at this position (the chunk's own coordinates, plus the implicit position of the block). Ta dah.</div>
</div>
<div>
<br /></div>
<div>
<div>
This is really, really slow. We're drawing a lot of stuff the player can never see, so this is also easy to speed up. The only thing that is interesting for rendering, are the faces at the surface. So we still check every block, but we also look at the six neighbors. If the neighbor is of a different block type, <i>and</i> it is transparent, then we draw the face. Surfaces are stored as a list of a 16-bit chunk array index, plus a byte that indicates which of the six faces are exposed in the lowest 6 bits.</div>
</div>
<div>
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWT4ysimvcpAcQ-Sdfc409u-Bxxzjwy_rTbww9m30lD0GvcgSuu-24JJqIyHZG0HGotz7LTZ_HzVgHT0we8EMQIZIL64rLtBq63bqtFdXAxLdB3AL69qL52ROZH4BzlfJEa2xfhtkpbrBf/s1600/hexa-surface.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="168" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjWT4ysimvcpAcQ-Sdfc409u-Bxxzjwy_rTbww9m30lD0GvcgSuu-24JJqIyHZG0HGotz7LTZ_HzVgHT0we8EMQIZIL64rLtBq63bqtFdXAxLdB3AL69qL52ROZH4BzlfJEa2xfhtkpbrBf/s320/hexa-surface.png" width="320" /></a></div>
<div>
<br /></div>
<div>
<div>
Much better already! Combined with frustum culling and occlusion culling (described in detail in <a href="http://an%20earlier%20post/">an earlier post</a>) performance will be boosted even further.</div>
</div>
<div style="font-size: x-large;">
<br /></div>
<div>
<div>
Opaque and transparent objects need to be drawn separately, so you'll have to generate two surfaces for each chunk. First you draw all opaque surfaces, in near-to-far order. Then you turn off z-buffer writes, and draw all transparent surfaces in reverse order, far-to-near.</div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<span style="font-family: Arial, Helvetica, sans-serif; font-size: large;">Surface extraction</span></div>
<div>
<br /></div>
<div>
<div>
The step that converts a chunk to the visibile surfaces is now our new bottleneck. I know others have experimented with offloading this to the GPU, but this requires a rather modern card, and I'd like to support at least OpenGL 2.1. So for now, we're still CPU bound.</div>
</div>
<div>
<br /></div>
<div>
<div>
Hexahedra always runs in a client-server setup, even for single player. The server also looks for a chunk's surface, even though it doesn't render anything. It uses this for calculating light, and for collision handling. Now why don't we store this information in the database as well, and send only the surfaces to the client?</div>
</div>
<div>
<br /></div>
<div>
<div>
This has several advantages. Clients don't have to go through the same expensive step anymore. Network load will be reduced; a surface is usually smaller than the chunk it was generated from, with only a couple of worst-case scenarios as the rare exception. Cheating will be harder, since clients cannot see ores or other valuables hidden inside the walls.</div>
</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
<div>
Hope you enjoyed this quick peek under the hood!</div>
<div>
<br /></div>
<div>
<br /></div>
<div>
<br /></div>
</div>Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-8228224681659875765.post-60975473812107690402011-09-25T13:25:00.000+02:002011-09-25T13:25:52.753+02:00GLSLMost people have already seen GLSL in action in several Minecraft mods, ranging from bump- and parallax mapping to bending the world into one giant acid trip. Other games, such as <a href="http://www.mythruna.com/">Mythruna</a>, use it out of the box for effects like HDR bloom.<br />
<br />
Personally, I prefer Hexahedra's current look, with the simple textures and the blocky lighting. But there are several other interesting things possible that have nothing to do with aesthetics.<br />
<br />
One of them is the use of texture arrays. An old technique to speed up rendering is to use a texture atlas: a large texture that combines several smaller ones. The drawback is that such textures cannot be tiled, so every cube has to be drawn separately. Minecraft uses (used?) a texture atlas that is exactly one tile wide, so the textures can at least be tiled horizontally. Strips of cube faces can be merged together, which cuts back on the amount of work the GPU needs to do.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhWCcp3mYPpAOHU7C_E8THu3eyryNljQ4It5bGq-sBK3nKUFMFHL859C4zcLLuBIClnu1IHoWjzcPb6pXA7EAjQMpqhN_Lwo_h5sVHCA64B7CX4BioopKGbuEX6R_gWvYC2X8wUIF2zmPd/s1600/hexa3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="286" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhhWCcp3mYPpAOHU7C_E8THu3eyryNljQ4It5bGq-sBK3nKUFMFHL859C4zcLLuBIClnu1IHoWjzcPb6pXA7EAjQMpqhN_Lwo_h5sVHCA64B7CX4BioopKGbuEX6R_gWvYC2X8wUIF2zmPd/s400/hexa3.png" width="400" /></a></div>
<br />
A texture array is a kind of 3-D texture. The individual textures are arranged in a stack. Each slice can now be tiled both horizontally and vertically, so we can merge even more faces. The gains are the most obvious for open water, where 256 cubes with the same texture and lighting can be merged into a single, large square.<br />
<br />
And in one fell swoop, it also solves all problems with textures bleeding into each other at the edges because of mipmapping and rounding errors. <br />
<br />
There's another advantage. Every corner used to be stored as three shorts (x, y, z) for the position, two floats (u, v) for the coordinates in the texture atlas, and three bytes (r, g, b) for the lighting. That's 68 bytes per face.<br />
<br />
Such restrictions no longer exist in GLSL. We can put the coordinates in bytes. (I'd put them in nibbles, but the range is 0-16, not 0-15). Now that we're using texture arrays, we need a short to pick a slice, and two nibbles for the u,v coordinates. Three more nibbles for the lighting: ambient, sunlight, and artificial light. The actual light colors are grabbed from uniforms, global values we need to set only once. So we're down to 32 bytes per face. Nice!<br />
<br />
Hmm... The u,v coordinates now move in lockstep with the vertex positions. It turns out that by storing a normal, we can go from world coordinates to texture coordinates by a simple multiplication. We only have six possible normals, so that's three bits. And we're down to 28 bytes per face. Even better, we can now use the normals for the ambient lighting as well. Dusk and dawn are going to look spectacular if we can give the west (c.q. east) faces a red or pink hue.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9j9rR0fui-lkT5kTHcWKmQVjNMHCRBKSc37KUCBBxGZIDoYSvKGuvXDYroT6gMJBJ2pS7XdEA1wPS56L_4vACCelssqKERtBMJCLtRCssg4h47F-jI0Az8Vp8Tjq5-iQFE4MArzUG3T4g/s1600/hexa4.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="116" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9j9rR0fui-lkT5kTHcWKmQVjNMHCRBKSc37KUCBBxGZIDoYSvKGuvXDYroT6gMJBJ2pS7XdEA1wPS56L_4vACCelssqKERtBMJCLtRCssg4h47F-jI0Az8Vp8Tjq5-iQFE4MArzUG3T4g/s400/hexa4.png" width="400" /></a></div>
<br />
<br />
I look at the top of the screen where it says "20 FPS". Frown. Revert to previous shaders. 60 FPS. The fuck?<br />
<br />
Turns out a simple lookup in a table with six 2x3 matrices is painfully slow in GLSL. It might not be worth the extra 4 bytes per face, but it would be neat to have anisotropic ambient light. Perhaps a lookup in a small 1D texture would solve this? I'll have to spend some more time on this.<br />
<br />
Unknownnoreply@blogger.com9tag:blogger.com,1999:blog-8228224681659875765.post-11894112825500475222011-07-26T17:05:00.000+02:002011-07-26T17:05:47.481+02:00New test dataThere has been a lot of activity recently around <a href="http://www.minecraftforum.net/topic/310298-173robintons-mods/">Cubic Chunks</a>, a Minecraft mod that raises the height limit to 4096. Some of the old yMod maps have been dusted off and converted to this new format. Since it is based on McRegion, it isn't difficult to import in Hexa.<br />
<br />
One of those maps is <a href="http://www.minecraftforum.net/topic/147345-mapmoderncraft-city-v6beta-173height-modhuge-skyscrapers/">ModernCraft</a>. I just wanted to show some screenshots, because it looks awesome.<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOTPKWUT6_aQRgd8_uS8UgFQlDoYchVT9vE9ub2gFbTaFLFRktQhjiRabCRxl6nhb49WNnvnda7z5EqGuOUUBDw4CHicCWvghx1KmRAaIlCIdmgbuNCN5vaQ3DWThUp_eXY_ht5dwGcf-t/s1600/modern16.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjOTPKWUT6_aQRgd8_uS8UgFQlDoYchVT9vE9ub2gFbTaFLFRktQhjiRabCRxl6nhb49WNnvnda7z5EqGuOUUBDw4CHicCWvghx1KmRAaIlCIdmgbuNCN5vaQ3DWThUp_eXY_ht5dwGcf-t/s400/modern16.jpeg" width="400" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiP9Y4bJy1p6zMuKHrXpKPVLDVa94w5jPYNv_zOFmL1m1MrYb_MlM8fyQ4GGzeNjLe3oYF5zOioNBCQJuwX_8GvyYQXz_92L7BoBvQtpg_l_vCfYGFPuuvLcBoAB6ArlvpQ_Lldcyzu8jeM/s1600/modern17.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiP9Y4bJy1p6zMuKHrXpKPVLDVa94w5jPYNv_zOFmL1m1MrYb_MlM8fyQ4GGzeNjLe3oYF5zOioNBCQJuwX_8GvyYQXz_92L7BoBvQtpg_l_vCfYGFPuuvLcBoAB6ArlvpQ_Lldcyzu8jeM/s400/modern17.jpeg" width="400" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhulkGToIXkpV5CZn0_HzJ1AKN1UzrlNICE6kDinTAgW9aPNx-_sic9_u1LYg7vdmSAfnOG3pOc0yBqcB5RAs3rRsce5_u9szBUIE3HO4Py77JzFEaKMlpSRC_pOzMEkiOwLl1ldGEC4acB/s1600/modern11.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhulkGToIXkpV5CZn0_HzJ1AKN1UzrlNICE6kDinTAgW9aPNx-_sic9_u1LYg7vdmSAfnOG3pOc0yBqcB5RAs3rRsce5_u9szBUIE3HO4Py77JzFEaKMlpSRC_pOzMEkiOwLl1ldGEC4acB/s400/modern11.jpeg" width="400" /></a></div>Unknownnoreply@blogger.com5tag:blogger.com,1999:blog-8228224681659875765.post-2305378959144445342011-07-22T20:29:00.000+02:002012-02-13T12:07:18.823+01:00Occlusion culling in action<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<iframe allowfullscreen='allowfullscreen' webkitallowfullscreen='webkitallowfullscreen' mozallowfullscreen='mozallowfullscreen' width='320' height='266' src='https://www.youtube.com/embed/cLBuFFl1Bcw?feature=player_embedded' frameborder='0'></iframe></div>
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-81447325959827375302011-07-19T22:47:00.000+02:002011-07-19T22:47:02.116+02:00Occlusion cullingThe best way to speed things up is to send, load, and draw as little as possible. Hexahedra now uses hardware occlusion culling at the client side to determine which chunks to fetch over the network and show to the player.<br />
<br />
Hardware occlusion checking is done by drawing the scene first, and then <i>pretending</i> to draw a box (or any convenient primitive) around whatever you want to cull. The GPU then tells you if this box would have been visible or not, had it actually been drawn. If it is visible, you can then proceed to load and draw the actual million-triangle object as usual.<br />
<br />
<br />
<b><u>How not to do it</u></b><br />
<br />
It would be nice if we could check if the 16x16x16 bounding box of a chunk is visible, before we grab it from the server, decompress it, make a mesh, and push it to the graphics card.<br />
<br />
We run into a couple of problems right away. First, to make sure the check is useful, the chunks that could potentially occlude it must be drawn first. For a chunk somewhere straight in front of the player, there's only one potential occluder. (For example, the chunk at {2,0,0} is only covered by the one at {1,0,0}.) Most chunks will have 2 or 3 potential occluders, though. And to determine whether to draw them or not, we'll have to check their occluders first...<br />
<br />
Technical complications aside (chunks cannot be turned into meshes until their six neighbors are loaded, both the GPU queries and network queries are asynchronous, etc.) it is easy to see this is tricky to get working. And it doesn't work that well either. Suppose we have a chunk A, and three neighboring chunks B, C, and D that are A's potential occluders. B and C are visible, but they're on the edge of the screen. D is just off the edge of the screen, so we can't do a visibility check just yet. But until it becomes visible, we can't issue the query for A. (Well, we <i>could</i>, but that would result in way too many queries and loads of false positives.) However, if B and C don't cover A completely, we will see an ugly gap until the player turns his head far enough for D to enter the screen.<br />
<br />
So that's where I lost a lot of time last month. :P<br />
<br />
<br />
<b><u>Better occlusion checking</u></b><br />
<br />
The solution is not to check the bounding <i>boxes</i>, but the <i>faces</i> that touch the chunks that are already visible. Here's an illustration of how it is implemented right now:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtQdPHNIJ3wlVRHWL4BimRNe7E3oS-DkJE-_l3MuVxJx0LhXIfZKP6Dt3MXtvdfVWMXd99kReNrUOIDVEn-ukCr7eZywWjWa4Qztkl8vRbsLtPEKrhPPyJVvAs6eymNfD1FDPBHI-w-yne/s1600/occlusion.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgtQdPHNIJ3wlVRHWL4BimRNe7E3oS-DkJE-_l3MuVxJx0LhXIfZKP6Dt3MXtvdfVWMXd99kReNrUOIDVEn-ukCr7eZywWjWa4Qztkl8vRbsLtPEKrhPPyJVvAs6eymNfD1FDPBHI-w-yne/s320/occlusion.png" width="274" /></a></div><br />
Step 1: the player is standing in this chunk, which is of course visible to the player. Six queries are issues, one for every face of this chunk. (In the illustration you see only four). The queries are shown as lines. The dotted lines are outside the player's view, so we can't resolve them yet. The solid lines, however, will be answered by the GPU soon.<br />
<br />
Step 2: The GPU has told us both faces are visible, so we fetch the corresponding chunks from the server, and draw them. For the new visible chunks, we issue new visibility queries. There are now four queries underway, and four are on hold.<br />
<br />
Step 3: Some of the queries of chunk 1 have returned, and two faces are invisible. We mark the chunks as occluded, and we don't load them or issue any further queries for them.<br />
<br />
Step 4: More data comes back, but in the meantime the player turns his head to the right. The face on the right enters the screen, and the query becomes active.<br />
<br />
Step 5: The face is visible, and chunk 2 is loaded and drawn. Three new queries are sent to the GPU, including the one for the face that borders the occluded chunk above it.<br />
<br />
Step 6: That face is visible, so chunk 3 is now marked visible as well. The other two faces were occluded.<br />
<br />
<br />
<b><u>Coming up</u></b><br />
<br />
It appears there is still a problem where I get false negatives back. This is annoying, because the terrain shows a hole at that point. Here's a screenshot with one of such hiccups. The queries are drawn in green, for debugging purposes.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1XvFz1nNfrWrHGEDk1az8MtywqekCS4e57IQwqp7duM6_BGWITNFRiIl_clPfrYt_yebl6kXqiXgJsbwFz-0zqQJw-6LVZl1uxNxNtNt7qTS-v-Zla5Bs1yFcmcJZhrUcfu3xoILF6icW/s1600/screenshot.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj1XvFz1nNfrWrHGEDk1az8MtywqekCS4e57IQwqp7duM6_BGWITNFRiIl_clPfrYt_yebl6kXqiXgJsbwFz-0zqQJw-6LVZl1uxNxNtNt7qTS-v-Zla5Bs1yFcmcJZhrUcfu3xoILF6icW/s400/screenshot.jpeg" width="400" /></a></div><br />
<br />
Usually a shake of the mouse solves it, and the algorithm chugs along as if nothing happened, but it's really annoying and ugly. Also, I need to integrate the heightmap, so I can skip air chunks. (As you can see, there's a lot of unnecessary checking going on up in the sky. This will speed things up tremendously.)<br />
<br />
Once that's taken care of, I hope to be able to post some videos showing all this in action, and also some statistics of just how much memory and triangles this saves under realistic conditions.Unknownnoreply@blogger.com1tag:blogger.com,1999:blog-8228224681659875765.post-23303273540505239242011-05-24T18:01:00.001+02:002011-05-31T00:47:15.075+02:00Scripting<a href="http://www.rasterbar.com/products/luabind.html">Luabind</a> is awesome.<br />
<div><br />
<div>I've spent some time with this library, and it's a really amazing C++ wrapper for <a href="http://lua.org/">Lua</a>. Binding functions, classes, even callbacks and anonymous functions, it's a breeze.</div></div><div><br />
</div><div>Materials were never supposed to be hardcoded, but now the framework finally allows you to specify your own in a Lua script:</div><div><br />
</div><div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">define_material(1, { name = "dirt", texture = { 1 }, hardness = 1.5 })</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">define_material(2, { name = "grass", texture = { 1, 0, 1 } })</span></div></div><div><div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">define_material(3, { name = "water", texture = { 239 }, transparency = 0.5, viscosity = 0.2 })</span></div></div></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span></div><div>...And so on. My first idea was to read this from the world database, or an XML file, but nothing is as convenient and flexible as this.</div><div><br />
</div><div>(The "texture" property is an array with 1 to 6 indices to the texture atlas. If only one value is given, all faces of the cube will use that texture. In the case of grass, texture '1' is used for the sides, '0' for the top, and '1' again for the bottom. An array with 6 values would specify different textures for every face.)</div><div><br />
</div><div>Strictly speaking, this isn't real scripting yet, just configuration. So let's take a look at events:</div><div><br />
</div><div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">function launch (player)</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> player:change_speed(0,0,10)</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"> player:shout("WHEE!")</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">end</span></div></div><div><br />
</div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">on_approach(40, 40, 0, 3, 6, launch)</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;"><br />
</span></div><div>On_approach calls a function whenever a player gets near (40, 40, 0), within 3 blocks distance. (The coordinates are given relative to the center of the world). Any player entering this area will be launched into the air, by adding 10 m/s to their vertical speed. This event won't fire again until the player is further away than 6 blocks.</div><div><br />
</div><div>Similar triggers could be added to materials, items, and mobs. This, for example...</div><div><br />
</div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace; font-size: x-small;">define_material(2, { on_touch = launch })</span></div><div><span class="Apple-style-span" style="font-family: 'Courier New', Courier, monospace;"><br />
</span></div><div><span class="Apple-style-span" style="font-family: inherit;">would be really, really annoying. But it would not overwrite anything from the first definition, it would only add a trigger.</span></div><div><span class="Apple-style-span" style="font-family: inherit;"><br />
</span></div><div>Next thing I'll need to do is look at security. It's very important that the scripts are properly sandboxed. Also, I should study Gary's Mod, to get an idea of how to properly design such an API.<br />
<br />
<br />
Edit: I'm jotting down some ideas <a href="http://sites.google.com/site/hexahedralib/home/lua-api">here</a>.</div><div><br />
</div>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-89108434574249556022011-05-21T00:04:00.001+02:002011-05-21T00:37:52.820+02:00More screeniesSo, people wanted to see more screenshots! Let's take a look at the first two steps of the terrain generator:<br />
<div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEitMYouumQvE0c13K9cw9GYM1wtON4SpCXEJ32mrV6AtTJ8ILGuwfa8EqKuF75OvRx0KzabHuqpog5TWEqCeVdpXqI3MO9xUKqaXh4axEBBYmZSB8JeO4uWFJFewfsSd7zNz6ce0rCUx0W8/s1600/simpleperlin.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEitMYouumQvE0c13K9cw9GYM1wtON4SpCXEJ32mrV6AtTJ8ILGuwfa8EqKuF75OvRx0KzabHuqpog5TWEqCeVdpXqI3MO9xUKqaXh4axEBBYmZSB8JeO4uWFJFewfsSd7zNz6ce0rCUx0W8/s400/simpleperlin.jpeg" width="400" /></a></div><div><br />
</div><div>The first step uses 2-D perlin noise to generate a height map. Nothing fancy.</div><div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiNvpdZhOWiMvbDaB4n5iq8EpJrYmKRP8m0VKxee_9Xrq1Mq3_xrB1olOCTBwzrj4lKGOFQ9M3278j4VL_ZF3Z76FkaazJeBTHSlFK16KfcBcqjE7M-9BGYgVaYLzaQT2zJ9BZfyY0kKEW/s1600/whatthechrist.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhiNvpdZhOWiMvbDaB4n5iq8EpJrYmKRP8m0VKxee_9Xrq1Mq3_xrB1olOCTBwzrj4lKGOFQ9M3278j4VL_ZF3Z76FkaazJeBTHSlFK16KfcBcqjE7M-9BGYgVaYLzaQT2zJ9BZfyY0kKEW/s400/whatthechrist.jpeg" width="400" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: left;">The second step mi-... WHAT.</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: left;">*fixes bug*</div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGlZsO8q2IgwZcGssyuCD634KL-5A4zi4JQTDcPy73TA0xwYoaFmAO_Xu3leaVnT-Yy6dfhqdsf0hGW0vVGZHdDEgkAUBNaR4FUJr7d4uE1x9wgOqXop3yqwnurII8KShgtU7BXXRifcuS/s1600/perlinmix.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjGlZsO8q2IgwZcGssyuCD634KL-5A4zi4JQTDcPy73TA0xwYoaFmAO_Xu3leaVnT-Yy6dfhqdsf0hGW0vVGZHdDEgkAUBNaR4FUJr7d4uE1x9wgOqXop3yqwnurII8KShgtU7BXXRifcuS/s400/perlinmix.jpeg" width="400" /></a></div><div class="separator" style="clear: both; text-align: left;"><br />
</div><div>The second step mixes in 3-D perlin noise in some places. (This whole "in some places" bit will be fleshed out later into a nice, flexible biome system). The general shape of the terrain is still the same as in the first picture, though.</div><div><br />
</div><div>3-D Perlin noise is, simply put, a function that takes an x,y,z position as its input, and returns a value beween -1.0 and 1.0. It is a bit like measuring the temperature at a given point. For two positions that are right next to eachother, the returned values will be almost the same. But two points far apart will return completely unrelated values. This value is multiplied by some factor, 30 in this case.</div><div><br />
</div><div>Once we have this value, we subtract the relative height of that point to the surface that was generated in step 1. If the result is positive, a block of grass or dirt is placed. If not, it's air. The end result is some weird craggy terrain, and some floating boulders.</div><div><br />
</div><div>The same valley, seen from the other side:</div><div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVG7ny7MOKwTCduO49JsqRYyVagmSZm6AZ_vJh_o5g7hFaBarDmHxkNeZR1AMUtDEO-cGAhBSunwrRuzlSeWzbc6O5Y1_4EEhnh1d7kflGIgJEPq29fsgTK_0Q0ex5ipS5gZ2i_iypFZS-/s1600/farscape.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjVG7ny7MOKwTCduO49JsqRYyVagmSZm6AZ_vJh_o5g7hFaBarDmHxkNeZR1AMUtDEO-cGAhBSunwrRuzlSeWzbc6O5Y1_4EEhnh1d7kflGIgJEPq29fsgTK_0Q0ex5ipS5gZ2i_iypFZS-/s400/farscape.jpeg" width="400" /></a></div><div><br />
<br />
And some steeper terrain, while we're at it.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5s0i7-pOB-6tqPn0I8Do32BCfYb-cPEhanVWp3T2xhK5qXgaFMCb43up1Zg71RKG1wnOi_zg6xp9lA6zaaXxPyBl4bgIPm5tnkDrDFNHv44I9IUjRAOyQxONqou7j40AsCzJvNFbB0dPj/s1600/mountain1.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj5s0i7-pOB-6tqPn0I8Do32BCfYb-cPEhanVWp3T2xhK5qXgaFMCb43up1Zg71RKG1wnOi_zg6xp9lA6zaaXxPyBl4bgIPm5tnkDrDFNHv44I9IUjRAOyQxONqou7j40AsCzJvNFbB0dPj/s400/mountain1.jpeg" width="400" /></a></div><br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDCxp29zSSfBrQYgLn7bR0LtVWI4NFTY32krNhX1u3axIZDC12OWepRUOC91ycpwnDYgCq3q2e2KgbHabaCXiAhJYIqWrir6LFWomSIhXXUbmQBrmHW8R2ok4aXK_iMUDX1bl-ulwxvCFi/s1600/mountains2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgDCxp29zSSfBrQYgLn7bR0LtVWI4NFTY32krNhX1u3axIZDC12OWepRUOC91ycpwnDYgCq3q2e2KgbHabaCXiAhJYIqWrir6LFWomSIhXXUbmQBrmHW8R2ok4aXK_iMUDX1bl-ulwxvCFi/s400/mountains2.jpeg" width="400" /></a></div><br />
</div>Unknownnoreply@blogger.com5tag:blogger.com,1999:blog-8228224681659875765.post-33132338615527414622011-05-19T11:03:00.002+02:002011-05-19T13:19:06.214+02:00Bigass dragon invades BrovilleThe Minecraft world reader used to be a storage module. So instead of the usual <a href="http://www.sqlite.org/">Sqlite</a> database, the game would read and write all terrain data to a Minecraft save game. I have upgraded it to be a proper world generator, so I can combine it with other generators (and go back to the much faster sqlite for storage).<br />
<div><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjR1h9_1DEs4e0ZL4-EQAzG15JSAi_ngUsYzuwWBRvlHllSa6QKluGV9eKm__p7lQOCS2N9gFG2X6l6zsKsfs4VuXvmwmK7oaCROLMp5on7dq_gTPaK_YTVLl4FXGXVa6yiKurAYnLoAmI5/s1600/lolstatue.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="297" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjR1h9_1DEs4e0ZL4-EQAzG15JSAi_ngUsYzuwWBRvlHllSa6QKluGV9eKm__p7lQOCS2N9gFG2X6l6zsKsfs4VuXvmwmK7oaCROLMp5on7dq_gTPaK_YTVLl4FXGXVa6yiKurAYnLoAmI5/s400/lolstatue.jpeg" width="400" /></a></div><div><br />
</div><div>This screenshot shows the game running with three generators: infinite flatland, <a href="http://www.minecraftforum.net/topic/21991-super-neato-creation-broville-v9-v10-in-the-works/">Broville</a>, and the <a href="http://www.cs.princeton.edu/~min/binvox/">Binvox</a> reader. Now that the basic framework is in place, I can move on to creating more interesting generators, such as a tree planter, a cave digger, rivers, etc. ("Interesting" in the sense that they use the output of the previous modules. The ones shown here just superimpose their data, much like the layers in Photoshop.)</div><div><br />
</div><div>A few major changes under the hood: the world is now 4,294,967,296 blocks in every direction, including height. The old limitation of 65,536 blocks still applies to some terrain generators, though. </div><div><br />
</div><div>A lot of the code now uses <a href="http://threadpool.sourceforge.net/">Boost threadpool</a>, a not-yet official library for dividing up work across multiple threads. It works great on my 4 cores, although the code for feeding the results back to OpenGL is still a bit ugly. The result runs very smooth, but glitchy as well. Ergh, concurrency bugs... *headdesk*<br />
<br />
Edit:<br />
More screenies, yay.<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjioR9YOQhZph27aWKAvFTwOzR9i96IrhdkzP6nE6i6cLHvqvs50FAwtICkoIe0PSt6QLENUnrPtfEqfg29vh7qNkcrjA6XrKneIyQ2zAY-1Wt05GyBQUHtV0GotP-xg0uA-nzC5R7l_ahW/s1600/lookingdown.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="239" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjioR9YOQhZph27aWKAvFTwOzR9i96IrhdkzP6nE6i6cLHvqvs50FAwtICkoIe0PSt6QLENUnrPtfEqfg29vh7qNkcrjA6XrKneIyQ2zAY-1Wt05GyBQUHtV0GotP-xg0uA-nzC5R7l_ahW/s320/lookingdown.jpeg" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfTfpLGKms50AUK-gqXulxgp22OQS9-ZJc65AhQFw0kmMD-SzQOeR8qUXPlFKaqDa3-0X3bP6n4c7Nlii4mDTWj0-SFvHqRxyVanroax3pSFwpsN8aBlPe95DLPBa2sccpO6V-9OwTthC8/s1600/lowview.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgfTfpLGKms50AUK-gqXulxgp22OQS9-ZJc65AhQFw0kmMD-SzQOeR8qUXPlFKaqDa3-0X3bP6n4c7Nlii4mDTWj0-SFvHqRxyVanroax3pSFwpsN8aBlPe95DLPBa2sccpO6V-9OwTthC8/s320/lowview.jpeg" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibGRCLgZJhXq7PQLJkW_kXCiH5GYyrMllIFMMPMldb9H2pcj_5I_ts4xpBZcN6Vg4Dwwf5iVZxTLzp8-g47MS2zsXfkgXShbuc_PA836-nE3V7-X76ZT2d8qhJTuWjyj_lIqRqMky_LRij/s1600/lookingdown2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="240" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEibGRCLgZJhXq7PQLJkW_kXCiH5GYyrMllIFMMPMldb9H2pcj_5I_ts4xpBZcN6Vg4Dwwf5iVZxTLzp8-g47MS2zsXfkgXShbuc_PA836-nE3V7-X76ZT2d8qhJTuWjyj_lIqRqMky_LRij/s320/lookingdown2.jpeg" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"><br />
</div><br />
<div class="separator" style="clear: both; text-align: center;"><br />
</div>I just noticed in that last screenie that one of the Minecraft chunks missing. The shadow inside that square hole looks great though. ;P<br />
<br />
Had a couple of deadlocks and spontaneous suicides in the client while flying around. Holy shit this needs some serious debugging. Also, a little noclip screenshot to show that there are still caves underneath all this:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9KUmzb1Mfgf7VhDjAhJ21ZWnlBiHjs94QnwaggW1uQdc6utS9eXiyc6Fzc0S5ClYY3Z4rh_wTga4e0-BZpbyp3Q7WQoi6oGV6HzHjRKSVRb09WEH7voCguHGpAxZ2wvLuzrrRnKfjo6Mq/s1600/clippingerror.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="239" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEi9KUmzb1Mfgf7VhDjAhJ21ZWnlBiHjs94QnwaggW1uQdc6utS9eXiyc6Fzc0S5ClYY3Z4rh_wTga4e0-BZpbyp3Q7WQoi6oGV6HzHjRKSVRb09WEH7voCguHGpAxZ2wvLuzrrRnKfjo6Mq/s320/clippingerror.jpeg" width="320" /></a></div><br />
</div>Unknownnoreply@blogger.com4tag:blogger.com,1999:blog-8228224681659875765.post-87643571462511635812011-04-09T18:42:00.000+02:002011-04-09T18:42:43.483+02:00Back on trackAlright, I'm back from my long trip across Mexico, and development has resumed!<br />
<br />
I've ditched Irrlicht in favor of <a href="http://www.sfml-dev.org/">SFML</a> and straight-up OpenGL. Most importantly, this will help me to understand how 3-D works closer to the metal. But it also gives me more possibilities to get better performance and a smaller memory footprint. I'm currently trying to wrap my brain around <a href="http://www.cg.tuwien.ac.at/research/publications/2008/mattausch-2008-CHC/">CHC++</a>, it looks quite promising.<br />
<br />
Right now, the code is at the same point as it was back in early January, so instead of the usual screenshots, here's how the lightmap is constructed. First, there's the blueish light from the sky dome:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGcH8KGZEBiZezgxRPwlA6H5bwwDmuLhae3hqonTHf_MMbpc7LkHRPzgtVrdq8HKoYSh_-Y9xKhONwbxkbwlQG13LFxHdKaXjYZi_VFzRWG1ZFYufEbyRpq2Tmrh4l-E9sf8LVSJ0mvaHn/s1600/ambient-only.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhGcH8KGZEBiZezgxRPwlA6H5bwwDmuLhae3hqonTHf_MMbpc7LkHRPzgtVrdq8HKoYSh_-Y9xKhONwbxkbwlQG13LFxHdKaXjYZi_VFzRWG1ZFYufEbyRpq2Tmrh4l-E9sf8LVSJ0mvaHn/s400/ambient-only.jpeg" width="400" /></a></div><br />
In the second pass, the directional sunlight is added to that:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYnOVjoEokv7tyC4eamG9ktARP8_JfjoC4Gjx2bCE1J7XJpwMM7eEA88QUbi81mcxsAmSJV5Gnd73vooaJ5-MQxIU2V4t1lO7ffCuzSREGco25B8WoGr_yiBRe9G4s2YVDVnd8LO7ce9du/s1600/ambient-and-sun.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiYnOVjoEokv7tyC4eamG9ktARP8_JfjoC4Gjx2bCE1J7XJpwMM7eEA88QUbi81mcxsAmSJV5Gnd73vooaJ5-MQxIU2V4t1lO7ffCuzSREGco25B8WoGr_yiBRe9G4s2YVDVnd8LO7ce9du/s400/ambient-and-sun.jpeg" width="400" /></a></div>Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-8228224681659875765.post-51968347783969301202010-12-30T14:19:00.001+01:002010-12-31T00:01:27.214+01:00Colored lightIt would be nice to have colored light. For example, you could set the sunlight to something yellowish, and the sky light to a light blue.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnA2J1pWykpkDxf9ehqOgRY4bptxt2NtEB043K19LIzkK1WuDwh4q6e2UFteXQhPGq_4xIkYE0Y7DBx-My7W3pCrLYUbAVjXZLsksvzFcccvdaKaoPBVPd1260nNp14Hnyjf4O1Ojcyh7a/s1600/broville5.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjnA2J1pWykpkDxf9ehqOgRY4bptxt2NtEB043K19LIzkK1WuDwh4q6e2UFteXQhPGq_4xIkYE0Y7DBx-My7W3pCrLYUbAVjXZLsksvzFcccvdaKaoPBVPd1260nNp14Hnyjf4O1Ojcyh7a/s400/broville5.jpeg" width="400" /></a></div><br />
<br />
Broville never looked sunnier.<br />
<br />
Not only does this mean we can have green glowing radioactive ooze, and caves basking in the deep red glow of magma. The system already supports semi-transparent materials, so we can also have cathedrals with stained glass windows casting colorful light patterns onto the floor, trees with a greenish shadow,....<br />
<br />
The downside... it costs yet more memory. It's using 74 KB per chunk at the moment, just for the light map. And there are hundreds of chunks in a scene. Once occlusion culling works properly, it will become difficult to predict just how taxing a given scene will be. I guess I'll have to dynamically change the view distance based on the current frame rate and the memory load.Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-8228224681659875765.post-32760607278725687052010-12-25T16:50:00.000+01:002010-12-25T16:50:14.033+01:00Christmas shopping for a new UI libraryAfter fighting with CEGUI for the past week, I've come to the conclusion that this is not the right library for me. The user documentation is pretty much what I'd expect from an open-source project, but that's okay. As long as I have the source code, I'll find my way. No, it's the amount of work that needs to be done just to do something simple.<br />
<br />
I was hoping I could show a couple of cool things this weekend, but alas. In the meantime, I'm going to check out libRocket, Right Brain GUI, and MyGUI.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-62146450213360410052010-12-19T21:08:00.000+01:002010-12-19T21:08:18.002+01:00Done!I've made the changes I talked about in the previous post.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgplKpOV5d88wwjQuwc-gDXyiXntVHSt6YQr1D5sLvuPCLMzJvao2NMR9UA52VHa87_k3EOPzrZCC6Qs3SUle0qgp3bEwBkZWDukqkIfyWYcD5Is6heuLGOjyQuUe90qyDAZm78iONXtp6Q/s1600/broville3.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgplKpOV5d88wwjQuwc-gDXyiXntVHSt6YQr1D5sLvuPCLMzJvao2NMR9UA52VHa87_k3EOPzrZCC6Qs3SUle0qgp3bEwBkZWDukqkIfyWYcD5Is6heuLGOjyQuUe90qyDAZm78iONXtp6Q/s400/broville3.jpeg" width="400" /></a></div><br />
It looks so much better than the old, per-voxel light model:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguZ6Mcypr0uOfFqCClNN4dZVATBoaSlsqJK0rg73SyHppTVINbDF93nljMgKtmjJvESGmL_QnwUdCV24Xl2BPeghx0MlZqOXPUEKKcFUU6MT7r1aKsQHwv4v7SHKUyngXKcT0dt1FYjcke/s1600/compare.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="211" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEguZ6Mcypr0uOfFqCClNN4dZVATBoaSlsqJK0rg73SyHppTVINbDF93nljMgKtmjJvESGmL_QnwUdCV24Xl2BPeghx0MlZqOXPUEKKcFUU6MT7r1aKsQHwv4v7SHKUyngXKcT0dt1FYjcke/s400/compare.jpeg" width="400" /></a></div><br />
<br />
<br />
Next week: server-side Lua scripting, and maybe a first glance at the user interface.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-36935348396285882622010-12-18T13:08:00.000+01:002010-12-18T13:08:13.912+01:00Different lighting modelLooking at the screenshots from the previous post, I decided I don't like how light and shadows curl around edges. I'm going to switch from calculating the light map per voxel to one that does it per face. This is going to make it six times bigger, but so be it.<br />
<br />
There are some advantages that will make it worth it. I can add Lambert's cosine law, which will improve realism in general, but especially things such as sunlight coming through a window will be much prettier. And it's going to speed up the radiosity pass (because oblique faces can be ignored, something you can't do with per-voxel light).<br />
<br />
Small drawback: can't write it back to a Minecraft world anymore, or at least not without a little extra work and losing some detail. Oh well.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-53298588676109528112010-12-18T02:46:00.000+01:002010-12-18T02:46:16.117+01:00Minecraft level readerMost of the framework consists of modules that can be chained together. One example is the part that reads and writes the game world to some kind of persistent storage. The default module is something that sits on top of the face-meltingly fast <a href="http://www.sqlite.org/">sqlite</a>. (Bonus: save games are just one single file, not thousands.) And of course there's the binvox reader. But yesterday I wrote a module that can read Minecraft files, just to have some cool pre-made worlds to test with.<br />
<br />
This module reads a Minecraft chunk, slices and dices it in 8 cubes, roughly translates the block types (far from perfect), and passes it to the server. Everything higher than 64 blocks is air, everything below -64 is rock. If the requested chunk is outside the map, it falls through to the "null" module, which does nothing. This triggers the terrain generator, which right now is a simple, infinitely large flat plain. <br />
<br />
Today we're going to have a look around the <a href="http://www.minecraftforum.net/viewtopic.php?f=25&t=24148">Broville</a> map. It is legen... wait for it... dary:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtBhmWWOL6nQ6kxBQtxIfC6Ltffqu1xooThFnF1lCAUbfpi5BbgpAa8wbLlzmVknL3SgwYs8yfQwRZO1L_VX31jmXaypZOLq7A-_dzi00pTwICKYWmtHvbSmFPdefTmhvQP_Io7le7h1hyphenhyphen/s1600/broville.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="256" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjtBhmWWOL6nQ6kxBQtxIfC6Ltffqu1xooThFnF1lCAUbfpi5BbgpAa8wbLlzmVknL3SgwYs8yfQwRZO1L_VX31jmXaypZOLq7A-_dzi00pTwICKYWmtHvbSmFPdefTmhvQP_Io7le7h1hyphenhyphen/s320/broville.jpeg" width="320" /></a></div><br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHHsZXSWgLD0F0ZhyphenhypheneRp9hWjqaxh7SW3tTm3PElXhyOBkla0q7-DLehXA7b1KFS6oGkUKPsVLcM8IjJySlQY2IGpbr-UDsOLpuDJqkAP2CRuBZaH2r8u22sWXFGKUDdBGTw2BgmFqzHMSt/s1600/broville2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="262" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjHHsZXSWgLD0F0ZhyphenhypheneRp9hWjqaxh7SW3tTm3PElXhyOBkla0q7-DLehXA7b1KFS6oGkUKPsVLcM8IjJySlQY2IGpbr-UDsOLpuDJqkAP2CRuBZaH2r8u22sWXFGKUDdBGTw2BgmFqzHMSt/s320/broville2.jpeg" width="320" /></a></div><br />
<br />
One of the problems I've encountered here is that windows don't let much light through:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPTCrG6sjxoY3SKyGD5g54hnIHV-jdmIm6b1deahMwf53t_oYEv_5qim21lYdnMUMninEb7K1zF7TQAcONReG21YyOxO7hsiRW4oKQNYlUpZ0LHDQLmivY6bIaJ5nmawkGizr6bHuybqp0/s1600/dark_room.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhPTCrG6sjxoY3SKyGD5g54hnIHV-jdmIm6b1deahMwf53t_oYEv_5qim21lYdnMUMninEb7K1zF7TQAcONReG21YyOxO7hsiRW4oKQNYlUpZ0LHDQLmivY6bIaJ5nmawkGizr6bHuybqp0/s400/dark_room.jpeg" width="400" /></a></div><br />
<br />
The room is rather dark for several reasons. One, the walls are 1m thick, so the sides occlude a good part of the sky outside. Two, there's no radiosity: the light doesn't bounce around the room like it usually does. I was planning to add a radiosity pass after I've implemented point light sources, and it should be interesting to see how much of a difference this makes.<br />
<br />
Even the church with its big windows looks gloomy... (The trees right in front of all the windows don't help either...)<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGRNOGNrpAGdL9aplbr4y9kJlQovhYLm-ZO0Tp5GcK34yHP4b9IBOcYXFtscZBBQL_aazcnRPgy-rd6UW6SwGECbUw88OTnn9W_sBFxk9tWaofTLPj8fHskkYRsAQh6yr_KeKFAjWqOFC7/s1600/dark-church.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="296" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiGRNOGNrpAGdL9aplbr4y9kJlQovhYLm-ZO0Tp5GcK34yHP4b9IBOcYXFtscZBBQL_aazcnRPgy-rd6UW6SwGECbUw88OTnn9W_sBFxk9tWaofTLPj8fHskkYRsAQh6yr_KeKFAjWqOFC7/s400/dark-church.jpeg" width="400" /></a></div><br />
<br />
If the radiosity solution doesn't work, I guess people will have to build huge sun-facing windows and place plenty of lanterns. :P<br />
<br />
(Minecraft doesn't have this problem; the light is always spread out across 15 blocks in a diamond pattern.)<br />
<br />
The next step would be to convert the light map back to the Minecraft files. It would look odd once MC's own light model takes over again, but perhaps it'd be a cool addition for the static parts of a multiplayer map.<br />
<br />
<br />
Also, check out <a href="http://codeflow.org/entries/2010/dec/09/minecraft-like-rendering-experiments-in-opengl-4/">this blog entry</a>. Very interesting techniques! I've been toying with the idea of using geometry shaders to build the meshes, and this is an excellent demonstration of how to do that.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-54675861895238469152010-12-13T00:10:00.000+01:002010-12-13T00:10:56.504+01:00Semi-transparency and shadowsI decided to add transparency to the shadow calculations anyway. It's not as slow as I had feared, and it's great for shading the bottom of lakes and oceans. When casting a ray to test for occlusion, it now adds the opacity of all the intersecting blocks. Air has an opacity of zero, rocks and such have 1. Water is 0.2, leaves are 0.4. As soon as the sum of the opacity of the blocks along the ray reaches 1, the loop stops. The sum of all the rays is then used to determine how much light the block receives.<br />
<br />
For water, this results in a nice gradient:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqTwz2JAnjpYzZT0HZzk03DJa9rpx2ikz5_bP0XcajKfPg7YRcu7hSEal-5pfv-7LKT_IDkOYjK65kOyDgT975ARiL3b6JtAe6k0h556uo85QcTbR8MY3kNkaRKQciHZUkj1C-YJb5Arke/s1600/water.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="259" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiqTwz2JAnjpYzZT0HZzk03DJa9rpx2ikz5_bP0XcajKfPg7YRcu7hSEal-5pfv-7LKT_IDkOYjK65kOyDgT975ARiL3b6JtAe6k0h556uo85QcTbR8MY3kNkaRKQciHZUkj1C-YJb5Arke/s320/water.jpeg" width="320" /></a></div><br />
And... *peers*... some sort of dark lines along the edges of the chunks. I'll have to look into that.<br />
<br />
As for the trees, it does make the shadows a bit softer, but the difference isn't huge:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9L7JWRNYKk6N68C98MDAc977s0TRxw_w-Slgq19BW7mJNI4QUhdpX5k1uLVOjtIVqQdoVN3dzI7NjKOtXcaRMuXS1kdOqcPvctLEAQ7cXjxDHgltjmHRjGldSKCTGk63r1GQMR3woi0Ix/s1600/trees-another-test.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="259" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg9L7JWRNYKk6N68C98MDAc977s0TRxw_w-Slgq19BW7mJNI4QUhdpX5k1uLVOjtIVqQdoVN3dzI7NjKOtXcaRMuXS1kdOqcPvctLEAQ7cXjxDHgltjmHRjGldSKCTGk63r1GQMR3woi0Ix/s320/trees-another-test.jpeg" width="320" /></a></div><br />
I've also managed to get rid of that z-ordering problem I had earlier. I no longer use my own custom scene node, I just generate plain SMesh'es. Less code, works better. (So why use a custom scene node in the first place? Eh, I was following a tutorial. :P )<br />
<br />
<br />
Another cool side-effect is that I can now make things emit light as well, simply by setting their opacity to a negative value:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXQDOfX9JqFwIpBTg_EgxBtV5zmIyK_GJ8vFC3P86oF7gDpiZrxdDWnJlQtuZJioGfdvEnqkVETEDhKnLCUy8BVdQNpwttuXgYyyEwtAxGpHNPpzzqYStI61QqKqt23I6Bjda1W9zYSB2E/s1600/trees-lightsource.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiXQDOfX9JqFwIpBTg_EgxBtV5zmIyK_GJ8vFC3P86oF7gDpiZrxdDWnJlQtuZJioGfdvEnqkVETEDhKnLCUy8BVdQNpwttuXgYyyEwtAxGpHNPpzzqYStI61QqKqt23I6Bjda1W9zYSB2E/s400/trees-lightsource.jpeg" width="400" /></a></div><br />
Light sources will be done in a different way, this is just a little trick I thought of right now.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-36962291757200787622010-12-12T16:22:00.000+01:002010-12-12T16:22:54.709+01:00First look at treesHacked in some trees to test with:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRdHkwYhXwPqWke2o2OhBjArp0IFHBmSmpQbhIrHfNi-eHCQWfplmL4hoRi_8QAvyUGxGlvj4iNm5tofxd_Gmxg60xM_Cv7x_7-shjvKNgQebZIpzgUTtOq2UDPAbg3E3aOX4PTc9UzfcD/s1600/trees-first-test.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjRdHkwYhXwPqWke2o2OhBjArp0IFHBmSmpQbhIrHfNi-eHCQWfplmL4hoRi_8QAvyUGxGlvj4iNm5tofxd_Gmxg60xM_Cv7x_7-shjvKNgQebZIpzgUTtOq2UDPAbg3E3aOX4PTc9UzfcD/s400/trees-first-test.jpeg" width="400" /></a></div><br />
(Yeah yeah, trees are growing on the beach, I know. This will be much better once biomes are implemented.)<br />
<br />
The shadows look nice, but I wonder if it would look more natural with some sort of <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Volume_ray_casting">volume ray casting</a> algorithm. This would not be hard to implement; instead of simply checking whether a ray intersects a block, you assign a transparency to every block type, and calculate how much light is left after it passes through every block that intersects the ray. But it would slow down the light map generation even more.<br />
<br />
Also, I noticed something odd while looking around:<br />
<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBaFIx9uyHzA3DcGcFU-OfznnzSdqFuuFm_s0mxiAjgeNXXiOKe-rd6S1LLM25t35j7u1TBX4_PKAQCNxShJ9SQ__WXI-I1fCgMmgq8Rx5Rc5Dgd_NaLDdOBdAl4TQrIrVcMbevJ9kvLAf/s1600/trees-bug.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgBaFIx9uyHzA3DcGcFU-OfznnzSdqFuuFm_s0mxiAjgeNXXiOKe-rd6S1LLM25t35j7u1TBX4_PKAQCNxShJ9SQ__WXI-I1fCgMmgq8Rx5Rc5Dgd_NaLDdOBdAl4TQrIrVcMbevJ9kvLAf/s400/trees-bug.jpeg" width="400" /></a></div><br />
The far trees overlap the nearby tree. Hmm, I thought one of the reasons to use a 3-D engine is that you don't have to worry about z-ordering and all that low-level stuff? I'm sure this is just me being a n00b with Irrlicht, and there's an easy and obvious fix for it...Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-8228224681659875765.post-24908389146669867642010-12-07T12:21:00.001+01:002010-12-07T12:33:05.671+01:00Terrain generation and lightingThe terrain generator is quite simple at the moment. It starts with 2-D Perlin noise to generate a height map. In some places, it adds 3-D noise around the surface, up to a certain vertical distance above and below (right now set to 30 meters). The amount of extra noise that gets mixed in tapers off at the edges. The result is a world with bits of rolling hills, and bits with weird rock formations. And the occasional floating boulder.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdVnSD2Y478WsdBSbIZL-kmi-v8jJ9SBIYU5kLpVrYFMHzHjMB_OEuGr6Sc_VqSrJfpj2VwZY7Q7vP2lpFrlC-SQJF_bATKmjGuw1m_zuFDwt_OKIR22igbLTz-Rmo7M44vHzBCwbcV_Zl/s1600/landscape1.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgdVnSD2Y478WsdBSbIZL-kmi-v8jJ9SBIYU5kLpVrYFMHzHjMB_OEuGr6Sc_VqSrJfpj2VwZY7Q7vP2lpFrlC-SQJF_bATKmjGuw1m_zuFDwt_OKIR22igbLTz-Rmo7M44vHzBCwbcV_Zl/s400/landscape1.jpeg" width="400" /></a></div><br />
Now something didn't go quite right, the transition between the two terrain types isn't as smooth as I had hoped. It's easy to fix, but on the other hand, now you get all these cool faults and fissures. Hmm, I think I'll keep this glitch, but make it rare. Keeps the game world fun to explore.<br />
<br />
The lighting is calculated per block. From the center of each block, a bunch of rays are shot out, to see if the sky is visible in that direction. The total number of rays that don't intersect with another block determine how much light reaches that particular block.<br />
<br />
For the ambient occlusion, the rays are distributed in a hemisphere, to model an overcast sky that evenly lights everything. But if you add a couple of extra rays, very close together like a narrow beam, one part of the sky starts acting like a very bright disc. So in the same algorithm, we can get ambient light, sunlight, and soft shadows. Here's the Stanford dragon again, but this time you can see how his head casts a shadow on the neck:<br />
<br />
<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1NHsK21xsgczNXqdgcfQqoBMEKLsxCPpyDd_wQLnNS4mlhhOnSaLXv4Aa1bXhP2TLjx1owwUxgjnjOoDHMSoA7b2I3UncLUA8NSxBRnkDjOlsP4_JMXn3PPTrMf9Kcangrlotzb9R6sPa/s1600/dragon-shadow.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh1NHsK21xsgczNXqdgcfQqoBMEKLsxCPpyDd_wQLnNS4mlhhOnSaLXv4Aa1bXhP2TLjx1owwUxgjnjOoDHMSoA7b2I3UncLUA8NSxBRnkDjOlsP4_JMXn3PPTrMf9Kcangrlotzb9R6sPa/s400/dragon-shadow.jpeg" width="400" /></a></div><br />
Ergh, that would have looked much better without the distance fog...<br />
<br />
The first results looked promising, but had a lot of artifacts in it. A block on a hillside that has three blocks around it (say, north, east, and down) would already be almost halfway occluded. This leads to a lot of dark spots in an otherwise sunny hillside. To prevent this, there's a blur filter applied to the light map as a second step. (It doesn't yet work perfectly at the edges of a chunk, so you will still see some dark specks:)<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEEgKfzMV5e3L4dONxF12S10p2LtGpNi9Hvr0i5oGlqgkIc09viYgOQM4Vk2-6aKlYfiEDLej3mN7lwI0vP5jZlHgxItVm-SCqV37GDOo7rw_5Bvg7kMk2mD8lg6eHFRytFxJ6zwZmN0Ie/s1600/landscape2.jpeg" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiEEgKfzMV5e3L4dONxF12S10p2LtGpNi9Hvr0i5oGlqgkIc09viYgOQM4Vk2-6aKlYfiEDLej3mN7lwI0vP5jZlHgxItVm-SCqV37GDOo7rw_5Bvg7kMk2mD8lg6eHFRytFxJ6zwZmN0Ie/s400/landscape2.jpeg" width="400" /></a></div><br />
You might be wondering if it doesn't take ages to calculate the lighting. The first version was indeed incredibly slow. But there are some ways to speed this up tremendously. For example, you only need to calculate the light voxels that are close to the surface of the terrain. Right now, with 56 sampling rays, it runs at about 300 chunks (=16x16x16) per second on my 3 Ghz AMD64, but there's still some really dumb code in there that should be optimized. Using the other 3 cores would be an easy speed boost, too.<br />
<br />
The speed isn't <i>much</i> of an issue though. It has to be done only once. And the client also generates a preliminary light map using a much faster method. Only when the server is done number-crunching it replaces it with the awesomer version. Remember that new terrain is only generated as the player explores new areas. The new chunks are far away, so the switch is not very noticeable. <br />
<br />
<br />
Next time, water and trees. Now that the world isn't 64 blocks high anymore, we can skip the little 6-block fruit trees and plant mighty oaks and sequoias, and more importantly, build a proper tree house. There's still a limit in the current code that prevents me from generating a Na'vi home tree, but I hope to have that part redesigned next week.Unknownnoreply@blogger.com0