Jump to content
  • Advertisement
  • entries
    3
  • comments
    27
  • views
    1228

Mountain Ranges

Gnollrunner

1247 views

For this entry we implemented the ubiquitous Ridged Multi-fractal function.  It's not so interesting in and of itself, but it does highlight a few features that were included in our voxel engine.  First as we mentioned, being a voxel engine, it supports full 3D geometry (caves, overhangs and so forth) and not just height-maps. However if we look at a typical world these features are the exception rather than the rule.  It therefor makes sense to optimize the height-map portion of our terrain functions. This is especially true since our voxels are vertically aligned. This means that there will be many places where the same height calculation is repeated.  Even if we look at a single voxel, nearly the same calculation is used for a lower corner and it's corresponding upper corner. The only difference been the subtraction from the voxel vertex position. ......

Enter the unit sphere! In our last entry we talked about explicit voxels, with edges and faces and vertexes. However all edges and faces are not created equal. Horizontal faces (in our case the triangular faces), and horizontal edges contain a special pointer that references their corresponding parts in a unit sphere, The unit sphere can be thought of as residing in the center of each planet. Like our world octree, it is formed from a subdivided icosahedron, only it is not extruded and is organized into a quadtree instead of an octree, being more 2D in nature. Vertexes in our unit sphere can be used to cache height-map function values to avoid repeated calculations.  We also use our unit sphere to help the horizontal part of our voxel subdivision operation. By referencing the unit sphere we only have to multiply a unit sphere vertex by a height value to generate voxel vertex coordinates.  Finally our unit-sphere is also used to provide coordinates during the ghost-walking process we talked about in our first entry.  Without it, our ghost-walking would be more computationally expensive as it would have to calculate spherical coordinates on each iteration instead of just calculating heights, which are quite simple to calculate as they are all generated by simply averaging two other heights.

Ownership of units sphere faces is a bit complex. Ostensibly they are owned by all voxel faces that reference them (and therefore add to their reference counter) . However this presents a bit of a problem as they are also used in ghost-walking which happens every LOD/re-chunking iteration, and it fact they may or may not end up being referenced by voxels faces, depending on whether mesh geometry is found.  Even if no geometry is found  we may want to keep them for the next ghost-walk search.  To solve this problem, we implemented undead-objects. Unit sphere faces can become undead and can even be created that way if they are built by the ghost-walker.  When they are undead they are kept in a special list which keeps them psudo-alive. They also have an un-dead life value associated with them. When they are touched by the ghost-walker that value is renewed.  However if after a few iterations they are untouched, they become truly dead and are destroyed.

Picture time again.....

RMF.thumb.jpg.f3078d10165695735989304660b701a6.jpg

So here is our Ridged Multi-Fractal in wire frame.  We'll flip it around to show our level transition........

RMFTrans.thumb.jpg.f7c0680aa783aec98b7c8d1b33beb436.jpg

Here's a place that needs a bit of work. The chunk level transitions are correct but they are probably a bit more complex than they need to be. We use a very general voxel tessellation algorithm since we have to handle various combinations of vertical and horizontal transitions. We will probably optimize this later, especially for the common cases but for now it serves it's purpose. Next up we are going to try to add threads. We plan to use a separate thread(s) for the LOD/re-chunk operations, and another one for the graphics . 



11 Comments


Recommended Comments

This is ridiculously awesome.  That's about all I can say about it.

Share this comment


Link to comment

Thanks guys! :D Wait until you can walk around on the ground.  The physics JIT (Just in time) terrain model is mostly built. I'm just trying to debug stuff and get it working in a certain order.

Share this comment


Link to comment
3 minutes ago, Gnollrunner said:

Thanks guys! :D Wait until you can walk around on the ground.  The physics JIT (Just in time) terrain model is mostly built. I'm just trying to debug stuff and get it working in a certain order.

Nice! Keep us posted! I love this stuff. :) 

Share this comment


Link to comment

@Gnollrunner, can you explain this part

"We also use our unit sphere to help the horizontal part of our voxel subdivision operation. By referencing the unit sphere we only have to multiply a unit sphere vertex by a height value to generate voxel vertex coordinates.  Finally our unit-sphere is also used to provide coordinates during the ghost-walking process we talked about in our first entry.  Without it, our ghost-walking would be more computationally expensive as it would have to calculate spherical coordinates on each iteration instead of just calculating heights, which are quite simple to calculate as they are all generated by simply averaging two other heights.

A little more?

Share this comment


Link to comment
3 hours ago, Awoken said:

@Gnollrunner, can you explain this part

"We also use our unit sphere to help the horizontal part of our voxel subdivision operation. By referencing the unit sphere we only have to multiply a unit sphere vertex by a height value to generate voxel vertex coordinates.  Finally our unit-sphere is also used to provide coordinates during the ghost-walking process we talked about in our first entry.  Without it, our ghost-walking would be more computationally expensive as it would have to calculate spherical coordinates on each iteration instead of just calculating heights, which are quite simple to calculate as they are all generated by simply averaging two other heights.

A little more?

Sure, I'll try. It can be a bit hard to explain though........ We have an octree of voxels divided into chunks. A chunk is basically some point in the octree and everything below it. The depth of leaf nodes for a chunk is determined by the distance the chunk is from the player. However we don't build down to our leaf nodes unless there is a sign change, (i.e. mesh data) otherwise it would defeat the purpose of the octree.  So most parts of a chunk's octree or even the whole octree will not go all the way down to it's leaf depth, and it's leaf depth could be several levels down from a bottom voxel.......The problem is as you approach an area of terrain, the leaf node level will increase to provide more detail, and we can not assume that just because a voxel has no data it's children will not have data also.  A good example of this is if you have some floating terrain in the middle of a voxel.  However this can also happen without floating terrain.  For instance if some geometry pierces the side of a voxel but doesn't contact any of it's corners the voxel will appear empty, but after you subdivide it you might find data.

So for build iterations we have to go all the way down to where leaf nodes should be, just to check if there is data.  We need to do this because our terrain functions accept X,Y,Z coordinates and we don't have those until we have built the octree down. So it's kind of a chicken and egg problem. We need the octree to find the data, and we need the data to figure out where the octree should be.  Instead of building the whole octree down however, we use a lightweight tree without all the faces edges and nodes, just to find coordinates to feed to our functions.  Since our coordinates are on the surface of a sphere we need to subdivide an icosahedron and that's really what our unit sphere is. Then to calculate the position of a given voxel vertex we just multiply it's corresponding unit sphere vertex by it's altitude to get our final voxel vertex X,Y,Z coordinates. We are really dong this for virtual vertexes since they don't exist yet. The ghost-tree code handles this stuff.  Also we don't un-subdivide the unit sphere on every iteration. We use it to cache the sphere related part of our coordinates between build iterations, in addition to height related components of any terrain functions we are using. We therefore don't need to recalculate all that stuff on each iteration. We just recalculate the height part when we do our ghost walking which is a simple calculation..... Our ghost walking is implemented by recursion and on the way back up we throw away any parts of the ghost tree with no data, so we are left with a map of how to build the actual tree. Note this whole processes is only done on cells that appear empty.  Cells that already have a sign change will be at the current leaf level, and when we increase the level we can just subdivide them normally.   This handles the vast majority of cases. However as I said you can't make the assumption because for anything but the simplest cases it won't hold true very long.  Generally you won't have to ghost walk very deep but there are cases where it's possible. For instance say you have a long thin spike that avoids all nodes up until the last level of LOD.

There is one more feature I didn't really talk about yet but I'll add it in here.  if we have simple height-map data, we can store those terrain function values in the unit-sphere vertexes no problem.  However when we start getting into caves and stuff like that, you really can't do that.  So now there is another problem. As as you build your ghost tree down to find your data, you are running terrain functions on 3D coordinates and those can be expensive. Note that each voxel vertex is used by 12 voxels ( just like for cube voxels, each for vertex is used by 8 voxels).  Since during the ghost walk process there are no voxel vertexes built yet, there is no place to store calculated terrain function values.  Ostensibly you would have to calculate the same terrain function value 12 times, but that would be a disaster. Instead we have a 3D matrix cache that we use for temporarily storing terrain function values as we search for data,  and there is a special "chunk address" that we index it with so we can quickly see if we have already calculated a needed value. Since our voxels are prisms it uses something akin to barycentric integer coordinates. In fact there is a partially implicit addressing system that assigns each voxel a unique ID. 

I call it GNOLLS coordinators

If you you start at the top, the world is constructed from an icosahedron. That's twenty faces. we can combined those into pairs to a get a diamond shape which we call a "Group".  The group has two axes one that points roughly "North" and the other is at an "Oblique" angle to it.   That gets us to a pair of voxels which we call "Legs" (a term I stole form investment jargon, there is a one "up" Leg and one point "down" Leg). Then we have the altitude of the a voxel which we call a "Level" and finally we have the "Subdivision" as defined by our octree. So its:

Group
North
Oblique
Leg
Level

Subdivision

GNOLLS! (Yes I had to think a while to make the acronym work :D

 

Edited by Gnollrunner

Share this comment


Link to comment

Okay, I think I've finally wrapped my head around it enough to formulate a reasonable question, or three.. ;)

So, this game/engine that you are describing here, maybe I'm dumbing it down but primarily you're describing a terrain generation system with entirely dynamic LOD capabilities...yes?  Is this functionality going to extend to other meshes that I expect will be part of the game/environment?  Or is it strictly tied to the terrain/planet system you are building?  My mind is blown either way, I think it's artwork in progress.

Share this comment


Link to comment
On 10/16/2018 at 8:56 PM, Septopus said:

Okay, I think I've finally wrapped my head around it enough to formulate a reasonable question, or three.. ;)

So, this game/engine that you are describing here, maybe I'm dumbing it down but primarily you're describing a terrain generation system with entirely dynamic LOD capabilities...yes?  Is this functionality going to extend to other meshes that I expect will be part of the game/environment?  Or is it strictly tied to the terrain/planet system you are building?  My mind is blown either way, I think it's artwork in progress.

So basically the terrain is described not by polygons, but by functions. They can be stacked on top of each other in various ways so you have regions of different types of terrain: mountains, hills deserts, caves, what have you. The voxels just make it into a mesh at whatever LOD is required. This way the world can be very large and all players can fit on the same world. It also means that you can have a game were you can really travel long distances, so I'm hoping that gives more of a sense of adventure. Finally I want to implement some function override ability that will let players do some limited modification of terrain. For instance you could flatten an area you want to build a house on.

That's just for the terrain however. there has to be trees, cities, and stuff like that for a real MMO.  I think the trees aren't too bad. I'm working on an algorithm to build trees using voxels. The nice thing about prisms is that you can build a trunk or branch easily with voxels because it's easy to build a round structure with a central line with prisms.  I also came up with a particular way to put them together so you can branch off of a column of voxels but retain prism connectivity in a way the LOD will still work.  So the whole tree with branches will be built as a single mesh as it should be, except for the foliage.   Then it's a matter of just building the voxels in the right way to form a tree. 

For that I plan to use a series for 2D nose functions. one axis will run along the length of the branch and the second axis will the angles around the branch. With simplex and Perlin nose there is a trick you can use to copy the last row of vectors so basically as you go around the branch the function is continuous . At points where there is a noise value higher than some limit, you will start another branch at a some angel range defined by the tree building parameters. You should be able to apply other nose functions to twist branches around or change the diameters as they go along.  Ideally you have a lot of parameters to adjust things for a given type of tree.  For shading I want to use 4D simplex noise. Three dimensions will simply be the X,Y,Z coordinates of the mesh as usual, and the forth dimension will be generated along the length of the branches. The reason for the 4th dimension is so you can have some control of how bark is generated. I mean in general bark patterns follow branches so having a noise dimension along the branch will give you a lot of versatility.

For buildings I want to finish implementing normal cubic voxels and I have an idea for doing sharp corners that you need for buildings.  It's a modified version of marching cubes.

My general goal is address all the stuff that's needed for a real game. I know it's a huge undertaking but I'm hoping I can make it impressive enough that I can get help with, the more standard parts of an MMO.

Edited by Gnollrunner

Share this comment


Link to comment

Well, you have the impressive factor on lock down.  Truly incredible work so far.

Share this comment


Link to comment

I'll tag along for this one - it's going to be interesting to follow this project.
If I understand this correctly - given the functions and parameters it would be possible to create any subset of the world, and thus also split the simulation over multiple physical servers?

Share this comment


Link to comment
16 minutes ago, Polydone said:

I'll tag along for this one - it's going to be interesting to follow this project.
If I understand this correctly - given the functions and parameters it would be possible to create any subset of the world, and thus also split the simulation over multiple physical servers?

Exactly. That's how I plan to do the server side.  You can create any part of the planet you want with a minimal amount of data.  There will be some differences in the voxels to support 3D pathing  for flying creatures, and also you don't have to worry about LOD on the sever, but basically you create the same geometry on the server and the client.  On the server I have the advantage of being able to pick the hardware though.

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By sidbhati32
      How to calculate angle between two points from a third point with the help of D3DXMATH library?
    • By ryt
      I recently started to explore how operator new and malloc() really work. If I understood correctly they get implemented using linked-list or forward-list when an array is used. This is probably because free (dynamic, heap) memory gets allocated all over (within its bounds) the memory and so something like std::vector isn't used, something that has continuous allocation.
      If this is true than accessing such memory (through []) would not have access time of O(1) but some other, more complex.
      Is this true or I misplaced something?  
    • By somedev
      Hey guys, I'm pretty new to Direct3D and I try to generate a png image file to disk from a already loaded initialized image from `LPDIRECT3DTEXTURE9` object.
      Basically I'm creating a function that get's an std::string for the file destination path and get the pixels from the existing LPDIRECT3DTEXTURE9 object and save them to disk.
      Any help would be much appreciated!
      Thanks in advance!
       
      EDIT:
      I though I should add a sample code of how I do it with BitMap format to get the idea of what I'm trying to do.
      Note that this code works, but I try to do something similar with PNG format.
      int Width = 128; int Height = 128; LPDIRECT3DTEXTURE9 m_lpTexture; LPDIRECT3DDEVICE9 s_lpD3DDev = NULL; bool SaveToBitmapFile(const std::string & szPath) { LPDIRECT3DSURFACE9 lpSurfSrc = NULL; LPDIRECT3DSURFACE9 lpSurfDst = NULL; m_lpTexture->GetSurfaceLevel(0, &lpSurfSrc); s_lpD3DDev->CreateOffscreenPlainSurface(Width, Height, D3DFMT_A8R8G8B8, D3DPOOL_DEFAULT, &lpSurfDst, NULL); if (D3D_OK != D3DXLoadSurfaceFromSurface(lpSurfDst, NULL, NULL, lpSurfSrc, NULL, NULL, D3DX_FILTER_TRIANGLE, 0)) { lpSurfDst->Release(); lpSurfDst = NULL; lpSurfSrc->Release(); lpSurfSrc = NULL; } CBitMapFile myBmp; myBmp.Create(Width, Height); D3DLOCKED_RECT LR; lpSurfDst->LockRect(&LR, NULL, 0); for (int y = 0; y < Height; y++) { BYTE* pPixelsSrc = ((BYTE*)LR.pBits) + y * LR.Pitch; BYTE* pPixelsDst = (BYTE*)(myBmp.Pixels(0, y)); for (int x = 0; x < Width; x++) { pPixelsDst[0] = pPixelsSrc[0]; pPixelsDst[1] = pPixelsSrc[1]; pPixelsDst[2] = pPixelsSrc[2]; pPixelsSrc += 4; pPixelsDst += 3; } } lpSurfDst->UnlockRect(); lpSurfDst->Release(); lpSurfDst = NULL; lpSurfSrc->Release(); lpSurfSrc = NULL; HANDLE hFile = ::CreateFile(szPath.c_str(), GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL); DWORD dwRWC = 0; WriteFile(hFile, &myBmp.m_Header, sizeof(myBmp.m_Header), &dwRWC, NULL); WriteFile(hFile, &myBmp.m_InfoHeader, sizeof(myBmp.m_InfoHeader), &dwRWC, NULL); int iWidth = myBmp.Pitch(); for (int y = myBmp.m_InfoHeader.biHeight - 1; y >= 0; y--) WriteFile(hFile, (BYTE*)myBmp.m_pPixels + y * iWidth, iWidth, &dwRWC, NULL); CloseHandle(hFile); }  
    • By m5willmax
      Hi, sorry for my English. My comp specs are: Win 8.1, DirectX 11.2, Geforce GTX750 Ti with latest drivers. In my project I must use color blend mode max via SDL_ComposeCustomBlendMode which is supported in SDL 2.0.9 by direct3d11 renderer only. Changing defines in SDL_config.h or SDL_config_windows.h (SDL_VIDEO_RENDER_D3D11 to 1 and SDL_VIDEO_RENDER_D3D to 0) doesn't help. SDL says my system supports direct3d, opengl, opengles2 and software renderers. What should I do to activate direct3d11 renderer so I can use blend mode max?
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!