Sirisian

Members
  • Content count

    2414
  • Joined

  • Last visited

Community Reputation

2263 Excellent

About Sirisian

  • Rank
    mmm bacon
  1. This video contains a rough overview of how Microsoft does it. There are no complete libraries for this as far as I'm aware. It's possible there are papers though on each individual technique, but the process is essentially a pipeline of different point cloud and mesh algorithms. (This problem seems extremely complex by the way when it comes to creating keyframes and delta frames. Microsoft might have broken new ground when performing this research).
  2. Would this happen to be a normal uniform grid? I wrote a blog article years ago that covered the grid and spatial hashing methods. Might compare the data structures I use against yours.   A big picture idea of interest management is that you don't have to run it in real-time. As Frob mentioned loose variations will often be used that exploit this. If designed correctly you can update entities in cells, quadtrees, etc like once per second then query and build the list of nearby entities every 2 seconds or stagger updates across many ticks. This can get kind of complex, but in the end you can end up with a system that supports thousands of entities and scales. (Overkill usually).
  3. OpenGL Vulkan is Next-Gen OpenGL

    Speaking of differences since I saw someone else online ask it. Can Vulkan do Rasterizer Order Views?
  4. OpenGL Vulkan is Next-Gen OpenGL

    https://github.com/KhronosGroup/SPIRV-LLVM https://github.com/google/shaderc   Not aware of any others. I'm sure someone is writing an HLSL to Spir-V though, but I haven't seen one yet.
  5. OpenGL Vulkan is Next-Gen OpenGL

    https://github.com/SaschaWillems/Vulkan <-- More examples in case people missed them.
  6. OpenGL Vulkan is Next-Gen OpenGL

    Someone just brought this to my attention: https://github.com/nvpro-pipeline/vkcpp Very simple to use C++ conversion. Should help with learning the API.
  7. OpenGL Vulkan is Next-Gen OpenGL

    Not sure if anyone else was planning to use Skia for text rendering, but they confirmed they have a Vulkan backend in the works. Kind of surprised since I thought I'd be waiting months or have to write my own backend.
  8. OpenGL Vulkan is Next-Gen OpenGL

    This should be fun. The quick reference makes it look so easy too. (Looks like for D3D12 users they'll have no trouble jumping over).
  9. Decompress quadtree image

    From an image processing standpoint you should be able to use a gradient technique. https://en.wikipedia.org/wiki/Image_gradient I'd use a 3x3 kernel to start with and maybe combine a larger kernel to generate a gradient map. Post process the gradient to smooth it then apply the changes to the grayscale image. Using this you can even increase the resolution.
  10. I should have been more clear. I can probably write an iterative solution, but I'm more concerned with a closed form solution. (Since I've shown a partial solution can be calculated already for most cases).   edit: Someone solved it on stackoverflow. Interesting.
  11. I asked this over on stackoverflow, but I'm not sure it'll be answered there.   I have a cubic bezier defined by four points. I need to find the time t along the cubic bezier where the tangent is equal to a given vector. This problem is not as straightforward as it may seem on first glance. I'll explain the basic math first for how I approached it so you can find flaws and possibly a better solution. A 2D cubic bezier and its tangent can be defined by these equations. Specifically the tangent:     T(t) = -3(1-t)^2 * P0 + 3(1-t)^2 * P1 - 6t(1-t) * P1 - 3t^2 * P2 + 6t(1-t) * P2 + 3t^2 * P3 And expanded for a 2D vector:     T_x(t) = -3(1-t)^2 * x0 + 3(1-t)^2 * x1 - 6t(1-t) * x1 - 3t^2 * x2 + 6t(1-t) * x2 + 3t^2 * x3     T_y(t) = -3(1-t)^2 * y0 + 3(1-t)^2 * y1 - 6t(1-t) * y1 - 3t^2 * y2 + 6t(1-t) * y2 + 3t^2 * y3 Then we also have a vector (x, y) representing the tangent we want to find the time t for. These are simple quadratic equations so we just need an equation to solve. We can take the cross product (vx0 * vy1 - vy0 * vx1) between the two and solve for 0. This would find when the tangent of the cubic bezier is equal to our given tangent vector and we'd solve for t. (I don't care if the vector is opposite the tangent so if our vector is (1, 0) then it would also look for (-1, 0)). In Mathematica solving for t with this cross product approach would look like this:     Solve[(-3(1-t)^2*x0+3(1-t)^2*x1-6t(1-t)*x1-3t^2*x2+6t(1-t)*x2+3t^2*x3)*y-(-3(1-t)^2*y0+3(1-t)^2*y1-6t(1-t)*y1-3t^2*y2+6t(1-t)*y2+3t^2*y3)*x==0,t,Reals] Mathematica would then output:     {{t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)-\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]},          {t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)+\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]}} Here's an image that's easier to see. That said most of those cases have duplicate variables so it's much simpler than it looks. (Both condition cases are identical and the solutions are a positive or negative case in the equation since it solved a quadratic equation). In code form this is easy to see:     var temp1 = (tx2 - tx3) / (y2 - y3);     var temp2 = (tx1 * tx1 + tx2 * tx2 + tx2 * (ty0 + ty1 - 2 * ty2) + tx1 * (-tx2 - tx3 - 2 * ty1 + ty2 + ty3) + tx3 * (ty1 - ty0) + ty1 * ty1 - ty0 * ty2 + ty2 * ty2 + ty0 * ty3 - ty1 * (ty2 + ty3)) / (tangent.y * (tx2 - tx3 - ty2 + ty3));     console.log ('Temp1: ', temp1, ' Temp2: ', temp2);     if     (         tangent.x < temp1 &&         (             tangent.y < 0 &&             (                 x0 < temp2 && y2 < y3 ||                 x0 > temp2 && y2 > y3             ) ||             tangent.y > 0 &&             (                 x0 < temp2 && y2 > y3 ||                 x0 > temp2 && y2 < y3             )         ) ||         tangent.x > temp1 &&         (             tangent.y < 0 &&             (                 x0 < temp2 && y2 > y3 ||                 x0 > temp2 && y2 < y3             ) ||             tangent.y > 0 &&             (                 x0 < temp2 && y2 < y3 ||                 x0 > temp2 && y2 > y3             )         )     )     {         var tx0ty0 = tx0 - ty0;         var ty1tx1 = ty1 - tx1;         var tx2ty2 = tx2 - ty2;              var temp6 = 2 * (tx0ty0 + tx2ty2) + 4 * ty1tx1;         var temp5 = tx0ty0 + 3 * (tx2ty2 + ty1tx1) + ty3 - tx3;         var temp7 = temp6 * temp6 - 4 * (tx0ty0 + ty1tx1) * temp5;         var temp3 = Math.sqrt(temp7);         var temp4 = 2 * temp5;         var t1 = (temp6 - temp3) / temp4;         var t2 = (temp6 + temp3) / temp4;     } So what we have is two possible times as we'd expect since the problem is quadratic. Here's an interactive example in JS. That example uses a hardcoded tangent vector of (0.707, 0.707). (So a vector pointing down and to the right in that coordinate system). There are problems though with the above code. Even correcting for floating point errors in the inequalities and square root calculations there are cases that aren't well defined. Like when y2 - y3 is 0 resulting in a division by zero case. There are subtleties to this also like in certain cases temp4 will have valid results that are very close to zero either producing the correct result or due to floating point issues generating a value for t1 and t2 much larger than expected. I've noticed this specifically in the cases where t1 or t2 are 0.5. Was thinking that flipping it across the the diagonal and solving again might solve some edge cases, but I'm just not confident on that approach. What I'd like is a tried and tested approach, possibly with a code example, or another way to tackle this without weird edge cases.
  12. OpenGL Vulkan is Next-Gen OpenGL

    This seems strange. Wouldn't it be easier as a source file than embedding it into the driver thus making the driver harder to maintain? I assume someone will release one later though.
  13. The surface in yours looks like a large ocean of jello. The primary reason for this is you stretch and compress the whole mesh even the finest details. From watching videos of oceans waves the high noise and slow moving froth stay in place and move much less than the low frequency waves and crests. When watching videos it's like you start with a large taunt blanket then you have high frequency noise that moves very little in relation to the lower frequency waves. As you add lower frequencies of waves the movements go up and they affect each other more. Also low frequency waves crest. The lower the frequency (larger) the wave the more foam. You lose a lot of detail without this.   Also for more realistic rendering (which adds a lot to the overall effect) you might want to render your objects first to a texture and extract a depth map. Then use that when rendering the water and take the difference between the depth values. Using something like beer-lambert for the depth based transparency would add a lot. (I'm sure there's a paper with a more accurate volumetric transparency though for the water).
  14. Client/Server rendering

    This should probably be in the Multiplayer and Networking section. There are a few ways to handle what you're describing.   Assuming you have a hash grid with uniform cell size then you just need to use the player's current camera on the server to collect all the entities in range. That just requires iterating through the cells and performing a look-up in the hash grid. Then for all the cells that exist in the hash grid union the entities into a list. This list represents all the entities the client can see. I have a tutorial on spatial partitioning and the queries here. That said the basic query function would look like this in C#:   public HashSet<IGridEntity> Query(AxisAlignedBoundaryBox aabb) {     var entities = new HashSet<IGridEntity>();       var startX = (int)(aabb.MinX / CellSize);     var endX = (int)(aabb.MaxX / CellSize);     var startY = (int)(aabb.MinY / CellSize);     var endY = (int)(aabb.MaxY / CellSize);       for (var x = startX; x <= endX; ++x)     {         for (var y = startY; y <= endY; ++y)         {             Cell cell;             if (grid.TryGetValue(y * dimensions + x, out cell))             {                 entities.UnionWith(cell.Entities);             }         }     }     return entities; } Now once you have all the entities you have to tell the player about them. In the past I've advocated using a full and delta state pattern. That is for every client you store an array of all the entities you've told the client about and then on every message after that you simply tell them what's changed. If you do that then you'll have an array that's empty when the client connects. We can refer to this array as the "known entities" array.   Depending on how you're building packets you'd want to add all the information about the new entities that aren't in the array (so that the client can recreate it). This would include things like the entity type. You're right that you'll want to give all the entities a unique id. You'll use this id to refer to the client entity later. If the entity is already known by the client (it's in the known entities array) then you just need to send a delta packet with things that have changed, like position. You can use bools to track changed items in the entity then after sending data to all the clients just set the bool to false.   That's all there is to it. Every tick of the server query for the entities in the camera then check the known entities and either add new entity data to the packet or write a delta entity data. The client has its own array of known entities so if it receives an entity id it's never seen it knows it needs to deserialize the full state and if it already knows about the entity then it'll deserialize a delta for the entity.   The two tutorials I linked go into things a lot more including how to forget entities. There are a lot of optimizations, but this is a fairly simple technique especially for a lock-step game. (It forms the basis though for a lot of technique for drastically reducing bandwidth though).
  15. Real-Time WebSockets and REST

    In regards to WebSockets I personally wouldn't bother with socket.io. You can just use the ws module for games. Falling back isn't necessary anymore for any browser or device. (Nor for a game is it really worth it).