Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 24 Jan 2013
Offline Last Active Oct 01 2016 02:50 PM

#5313482 Care to take a look at my dynamic terrain algorithm?

Posted by on 01 October 2016 - 10:25 AM

Hi everyone,

I really like the idea of creating a simulation of a (virtually) unlimited terrain using something like a perlin noise algorithm to determine the height of any (x, z) location and applying the height to a grid of vertices. Doing this requires some sort of dynamic LOD system to simplify the distant terrain while making nearby sections appear more detailed depending on camera distance. I have a rough working version right now which is built something like this:
- The terrain consists of a quadtree where each node represents a single tile. A tile contains four vertices and may contain four immediate child tiles of the same type. This allows the quadtree to be stored by creating a set of 'base' tiles and adding/removing children recursively as requierd. My terrain tiles are defined like this:
struct TerrainCell
    float sideLength;
    D3DXVECTOR3 centre;
    TerrainVertex vertices[4]; //bottom-left, top-left, bottom-right, top-right
    vector <TerrainCell> children;
    TerrainCell(D3DXVECTOR2 in_centre, float in_sideLength)
        //Logic to determine locations of vertices using the centre and sideLength.
- Each frame, I traverse the ENTIRE quadtree starting at the base cells. For each cell I add or remove child cells depending on the camera distance. If a cell needs to become more detailed, I add the four children if they do not already exist. I then process the children recursively in the same way. Eventually, I reach a point where a given cell decides it should NOT split. At this point, I add a reference to that cell into a 'render queue' so that I know to draw it on this frame.
Note: the logic used to determine whether cells should split is simple, and it is currently governed by this function:
bool ShouldCellSplit(TerrainCell *cell)
    return D3DXVec3Length(&(cell->centre - mainCam.pos)) < 10*cell->sideLength;
- Once this frame's render queue is built, I loop through all the cells in there and add them sequentially to a vertex buffer. The size of the buffer is hard-coded - at the moment I have made it large enough to contain 1000 cells (each with 4 vertices). It is created using the following parameters when the program starts: d3ddev->CreateVertexBuffer(vertBufferSize*4*sizeof(TerrainVertex), D3DUSAGE_DYNAMIC | D3DUSAGE_WRITEONLY, 0, D3DPOOL_DEFAULT, &vertexBuffer, 0). vertBufferSize is 1000 (i.e. the buffer can contain up to 1000 cells). Here is how I then add and render the cells:
unsigned numTilesProcessed = 0;
for (unsigned rqc = 0; rqc < renderQueue.size(); rqc++) //Loop through all the cells in the render queue
    void* pVoid;
    if (numTilesProcessed >= vertBufferSize) //The vertex buffer is full - need to render the contents and empty it
        if (FAILED(d3ddev->SetVertexDeclaration(vertexDecleration))){return false;} //A declaration matching the content of a TerrainVertex
        if (FAILED(d3ddev->SetStreamSource(0, vertexBuffer, 0, sizeof(TerrainVertex)))){return false;}
        for (unsigned prt = 0; prt < vertBufferSize; prt++) //Draw the tiles one by one
            if (FAILED(d3ddev->DrawPrimitive(D3DPT_TRIANGLESTRIP, prt*4, 2))){return false;}
        if (FAILED(vertexBuffer->Lock(0, 0, (void**)&pVoid, D3DLOCK_DISCARD))){return false;}
        numTilesProcessed = 0;
    else //This will occur if we have not reached the buffer's size limit yet
        if (FAILED(vertexBuffer->Lock(numTilesProcessed*4*sizeof(TerrainVertex), 4*sizeof(TerrainVertex), (void**)&pVoid, D3DLOCK_NOOVERWRITE))){return false;}
    memcpy(pVoid, renderQueue[rqc]->vertices, 4*sizeof(TerrainVertex));
    if (FAILED(vertexBuffer->Unlock())){return false;}
    numTilesProcessed += 1;
(There is also some more very similar code afterwards to handle the final batch of tiles which probably won't fill the vertex buffer up to its capacity).
...and that's pretty much it! The thing is, I came up with this algorithm having had little experience of terrain rendering or quadtrees before, so I suspect that people more experienced in this area will see ways to improve it or optimise certain parts. Perhaps it's ugly and could be entirely re-written in a much cleverer way! So what do you think?
Thanks for taking a look - any comments would be much appreciated :)

#5274642 Dumping every frame to an image file

Posted by on 06 February 2016 - 06:03 AM

Hey, thanks for the replies everyone:


- cozzie: Basically, my program is a demonstration of a simple autopilot program which is used to control a spacecraft in two dimensions. All I have to do is set the program running and the autopilot algorithm does the rest. Setting a fixed time-per-frame ensures the results are consistent and the autopilot is using a fixed timestep for each update. Hence there is no need for a good realtime framerate when I am capturing the video, I just need to make sure I can save every frame in sequence. So the answer to the second question is no - I like to render them on-screen so I can see what it's up to, but it's not totally necessary.


- Hodgman, harveypekar: I'll give those methods a go, thanks for the help :)

#5229599 SetDlgItemText in a loop or function

Posted by on 18 May 2015 - 09:07 AM

Thanks for the replies everyone. I got it to work using threads as follows:


void on_press(HWND hwnd)
SetDlgItemText(hwnd, IDC_STATUS, "Starting task 1...");
SetDlgItemText(hwnd, IDC_STATUS, "Starting task 2...");
SetDlgItemText(hwnd, IDC_STATUS, "Tasks complete!");
//When the button is pressed:
thread t_button(on_press, hwnd);


...and it works as I was expecting :)


ankhd: I am using a dialog box created using the WIn32 DIalogBox() function which means that it creates its own message loop and as far as I'm aware it doesn't respond to WM_PAINT messages.


SmkViper: That's a good point about the controls, I will see what I can do! Thanks.

#5228772 Generating random rays within a cone

Posted by on 13 May 2015 - 06:34 AM

No problem. The full source is available from here:




in the 'files' section :)

#5196920 Annoying shadow map artifacts

Posted by on 08 December 2014 - 04:13 AM

Ah, OK, never mind - it turns out I was clearing my shadow map to D3DCOLOR_XRGB(1, 1, 1) rather than D3DCOLOR_XRGB(255, 255, 255), meaning that the whole thing was basically black.

#5196850 Annoying shadow map artifacts

Posted by on 07 December 2014 - 03:06 PM

OK, so changing my sampler to:


AddressU = Border; 
AddressV = Border;
BorderColor = float4(1111);


...and removing the conditional has solved the problem. Thanks! So just to make sure I know what's going on here: the tex2D(ShadowMapSampler, projTexCoord).r is returning maximum depth (1) for any pixel outside the shadow map, and hence PSIn.Pos2DLight.- f_ShadowBias will always be less than the depth stored in the shadow map?


Thanks again :)

#5189241 Spherified cube

Posted by on 26 October 2014 - 10:56 AM

Thankyou for the replies. I tried it and found that it is indeed incredibly simple to do assuming that the cube's model space origin is right at its centre, as kauna said.


swiftcoder: at the moment I'm just experimenting and this was just a passing thought. I am eventually hoping to apply something like this to planets but I will most likely scale the planet itself down and just render it closer so that I can still use a small mesh.

#5189047 Scenes with large and small elements

Posted by on 25 October 2014 - 02:48 AM

Ok, thanks for all the replies! I have solved it for the time being by calculating the actual positions using metres, and when I render I put the camera at (0, 0, 0) and render everything relative to that. For the Earth I'm using a sphere of radius 1 which I render 6378100 times closer than the actual calculated distance. Disabling the z-buffer for the planet rendering makes sure it's in the background.

#5158245 Recalculating terrain normals

Posted by on 04 June 2014 - 05:12 PM

Sorry for not replying and thanks for the ideas everyone, since my terrain is static and isn't changing per-frame, I think the best idea may be to create another texture-based container to store the normals which can then be looked up in the shader. I'll see how it goes :)

#5151833 Updated ray tracer

Posted by on 06 May 2014 - 10:34 AM

I've been working on my ray racer recently, and I've changed it in a few ways:


- It now supports multicore rendering

- It can parse external text files and import scenes

- It can handle soft shadows

- It can handle textures


Here are a few pics I though I'd share:




To do: It would be nice to add the ability to render via path tracing so that I can add caustics, etc... but I haven't really found a good explanation of exactly how to do this. I understand that rather than spawning recursive reflection/refraction rays at each hitpoint, you spawn a single probabilstic ray, but I'm still a bit hazy on how to actually determine the final pixel color.


Thanks for looking smile.png

#5137540 Avoiding dark areas in ray tracing

Posted by on 09 March 2014 - 09:20 AM

Also, another question: when I multiply colour together, for example when I multiply the colour of a reflection by the colour of the surface it reflects off, is it standard to normalise the colour vectors?

#5137445 Avoiding dark areas in ray tracing

Posted by on 08 March 2014 - 06:20 PM

Here's how it looks after the new algorithm:




Still not sure if it's right, but there's some more light in there! The spheres don't reflect any ambient light by the way, just specular.

#5137433 Avoiding dark areas in ray tracing

Posted by on 08 March 2014 - 04:46 PM

OK, so you mean something like this:


trace(float attenuation)
reflectionColour = refractionColour = (0, 0, 0);
if (intersectedShape.reflectivity*attenuation > cutoff){reflectionColour = trace(intersectedShape.reflectivity*attenuation);}
if (intersectedShape.transparency*attenuation > cutoff){refractionColour= trace(intersectedShape.transparency*attenuation);}


i.e. I'd start my initial rays with an attenuation value of 1 and then every time the recursive rays hit a new object, if the attenuation value of the spawned ray would be less than the cutoff, I wouldn't spawn a new ray? I think that makes sense! It could also lead to better efficiency.

#5137321 Avoiding dark areas in ray tracing

Posted by on 08 March 2014 - 08:48 AM

Hi everyone,


I'm getting some nice pictures from my ray tracer but I've noticed a problem with some geometry setups. For example, this pile of spheres:




Between the lower and the middle level, the inner areas are completely dark. I'm not sure if this is realistic or not (I don't have any spheres to test it with) but it doesn't look right. I think I know why it's happening - my maximum ray depth is 5, and the rays probably get stuck in the cavities and never collect any colour. Is this realistic, and can I fix it without using infinite ray depth?



#5136257 Ray tracer minor issue

Posted by on 04 March 2014 - 02:02 AM

Thanks very much for the replies, Bacterius was correct - my bias was too small. I don't know why I didn't think of that, it's sitting there right underneath my ray depth constant, in big capital letters!


Krypt0n - I also enabled floating point exceptions (at least I think I did!) and ran my program in debug in VS2012 and nothing showed up. Thanks for the suggestion :)