One could imagine a super-mesher that does a big brute force search for the best mesh compared to a faster, but dumber method that generates a suboptimal mesh. Intuitively, it seems like there should be some tradeoff here. Therefore, we come to our second (and final) criteria for assessing mesh algorithms: Criteria 2: The latency of meshing cannot be too high. It would be unacceptable to wait for more than a frame or two to update the displayed geometry in response to some user change. While it is true that chunk updates are rare, when they do happen we would like to respond to them quickly. Of course, the above analysis is at least a little naive. The only way this cost can be reduced is by reducing the total number of polygons in the mesh, and so we make the following blanket statement about Minecraft meshes: Criteria 1: Smaller meshes are better meshes. In general, there really isn’t any way to change the number of pixels/fragments which need to be drawn without changing either the resolution, framerate or scene geometry and so for the purposes of rendering we can regard this as a fixed cost (this is our second assumption). That leaves primitive assembly, and the cost of this operation is strictly a function of the number of faces and vertices in the mesh. Recall that at a high level polygon rendering breaks down into two parts: 1.) primitive assembly, and 2.) scan conversion (aka polygon filling). Thus, over the lifetime of a mesh, the total amount of computational work it consumes is asymptotically dominated by the cost of rendering. As a result, it is quite sensible to cache the results from a mesher and only ever call it when the geometry changes. In a typical Minecraft game chunks do not get modified that often compared to how frequently they are drawn. I hope you are convinced that making these assumptions does not appreciably change the core of the meshing problem (and if not, well I’ll try to sketch out in the conclusion how the naive version of these algorithms could be extended to handle these special cases.) Finally, we shall suppose that our chunks are stored naively in a flat bitmap (array).Similarly we won’t make any assumptions about the position of the camera, nor will we consider any level of detail type optimizations.Instead of having multiple block types with different textures and lighting conditions, we’ll suppose that our world is just a binary 0-1 voxel map.For the sake of exposition, we’ll consider meshing in a very simplified setting: But before doing this, we first need to say a bit more precisely what exactly meshing is (in the context of Minecraft maps) and what it means to do meshing well. This process is called meshing, and in this post I’m going to discuss three different algorithms for solving this problem. The main challenge in using polygons is figuring out how to convert the voxels into polygons efficiently. One of the main innovations in Infiniminer (and Minecraft) is that they use polygons instead of raycasting to render their volumes. This time I’ll try to tackle a different problem: Meshing The last post I wrote on Minecraft-like engines got a lot of attention, and so I figured it might be interesting to write a follow up.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |