Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 13 Jan 2007
Offline Last Active Oct 20 2016 03:47 AM

Posts I've Made

In Topic: Job Based Rendering

24 June 2016 - 01:45 PM



I am not sure how this approach fits in with your design, but it may spark some new ideas.




Doesn't that architecture only allow for two primary threads?



In the example, there are two update loops in different threads: game loop and physics loop.  I don't see why you couldn't have more.



Why not just implement a simple job graph at that point? They're not particularly difficult to write.


In that particular architecture, the more threads you have trying to communicate like that, the deeper the pipeline becomes, so you end up with more latency.

In Topic: Job Based Rendering

24 June 2016 - 12:06 PM

I am not sure how this approach fits in with your design, but it may spark some new ideas.




Doesn't that architecture only allow for two primary threads?

In Topic: glsl represent 1 big texture as 4 smaller ones (tearing)

23 June 2016 - 02:49 PM

You're gonna have trouble with bilinear (gets worse with trilinear) filtering at the edges because the GPU should be interpolating between the two textures, but obviously this won't happen, so you need to do it yourself.


Potentially you may have to sample all four textures and interpolate it yourself:

// Assuming layout of textures:
// |0|1|
// |2|3|
result = mix(
mix( c0, c1, fract( uv.x * 1024.0 - 0.5/1024.0 ),
mix( c2, c3, fract( uv.x * 1024.0 - 0.5/1024.0 ),
fract( uv.y * 1024.0 - 0.5/1024.0 ) );

If you're at the left/right edge, you only need c0 & c1 or c2 & c3; if you're at the top/bottom edge you only need c0 & c2 or c1 & c3. But if you're close to the cross intersection, you're going to need to sample and mix all 4 textures.


Also the mipmaps need to be generated offline based on the original 1024x1024 rather than generating them on the GPU since it will generate them based on the 512x512 blocks individually.


I can't think quickly of a way to fix the trilinear filtering problem though.


If I recall correctly, we solved this (trilinear with discontinuous textures) in the past using tex2dGrad, which should be textureGrad on OpenGL... though that was sampling a texture in an atlas, rather than to another texture, so I'm not sure if it would still work.

In Topic: What maximum amount of flood fill can a dijkstra handle?

23 June 2016 - 10:43 AM

Dijkstra's minimum path between a pair of points routine is the famous algorithm you are probably writing about, he had several major algorithms so you might mean another.

The single pair algorithm potentially takes quite a lot of memory when implemented naively, on the order of N^3 sounds correct. Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

Since you mention "flood fill", I'm guessing you are talking about an all-pairs shortest path algorithm? Those exist, but are much more memory intensive for anything other than just storing a binary reachable status. Using the single pair shortest path over and over for all pairs is a bit extreme.

You might also mean having a path that follows a space filling curve across an entire board. That can take as much resources as your path requires, entirely dependent on your implementation.

Finally, there are many implementations of these algorithms online, some quite efficient and others are terribly inefficient. Can you share what implementation you are following?


As has been said, so long as your heuristic does not overestimate (the heuristic is always less than or equal to the actual optimal path cost) it is guaranteed to be optimal. Also, to note, A* can run faster if you do not require an optimal path, so that's also something to keep in mind... though if you really want greedy best-first search, don't use A* as that has the bookkeeping logic required to keep track of the length of the path so far which is what let's A* not be greedy.

Without knowing what exactly he's doing, though, it is impossible to recommend an ideal solution. Floodfill can be used for anything from pathfinding, to image editing, to determining if two voxel volumes connect, to other things. They're all just functionally graph-processing algorithms. There's other ways to do pathfinding as well (that generally couple with A*), including preprocessing certain pairs (jump point search - it basically identifies obstructions and preprocesses the pairs at the corners so you can get around blocking corners with 1 test), using hierarchical space above the nodes to quickly check path validity, and so on. That, and different algorithms are used if your map is dynamic vs static.

In Topic: MSVC generating much slower code compared to GCC

15 February 2016 - 02:03 PM

 __restrict cannot be used on references though, for whatever reason. And even though I read an explanation on those forums that references are already thought of to not be able to be rebound, testing it with assembler showed significant worse generated code than with pointers and __restrict (or whatever equivalent).


__restrict can be used on references as of Visual C++ 2015. It was one of the things that I was glad that they added. You also can functionally specify member functions as restrict in 2015 (where this is restrict).