Thursday, November 17, 2011

Streaming Meshes

Here is a quick video I did over the weekend. It shows a new program which connects to a web server and downloads chunks of terrain as you move.



I had posted similar videos in the past, but there is a radical difference. In earlier videos the meshes were loaded from the hard-drive. This baby you could run from your home. I actually plan to put it out for everyone to try it early next year. Since it will be the fist foray of this technology out there, I called it Sputnik.

It is only the first level of the clipmap, but I have expanded it so the load it generates is similar to a full scene spanning several kilometers. I capped the download speed to one megabyte per second to see if the downloading can cope with the camera movement.

The meshes are not textured in this video, but the all the information required for the final rendering is being downloaded. So this is really it. The chunks average 20K. They contain the mesh, normal maps and material information. I tried hard to make them smaller than that, but the loss in quality was not acceptable.

Using HTTP for transfer is a gamble, I'm still not sure about it. So far the results are encouraging, but I'm still weary of the worst case scenario happening too often. With HTTP it is not really about the transfer speed, it is the overhead of starting requests what worries me.

If you have any experience on this field, I would really appreciate your insight.

27 comments:

  1. This looks very good!

    I was half expecting to see LOS on the meshes as they are sent to the client. I mean, if I never get near the top of a mountain, probably it's ok if the server only sent me the lowest LOS for it. But you seem to imply that you send all the data to the client nevertheless. Is this correct?

    Regarding performance in general, I confess I have little experience, other than the generic programming advice regarding performance: start with the simplest solution, and if you need more performance, profile, and optimize the parts that need it. The transport protocol is only one of the possible bottlenecks.

    Regards!

    ReplyDelete
  2. It looks like you get an awful lot of polys on the underside of small ledges, which is a shame because the player can't get in there and can only see the insides of these ledges from specific angles. Have you considered perhaps being more aggressive with simplification when the normal of the triangle points down-ish?

    I was also wondering if the addition of vegetation models could be used to increase the level of acceptable compression. If you had a tree with spreading roots, rougher ground modeling would be unnoticeable.

    ReplyDelete
  3. 1MB/s? How will it run on, say, 250kb/s which is pretty much the top speed I get here?

    ReplyDelete
  4. You could use a long-open http connection using the "Comet" model.

    ReplyDelete
  5. Long time lurker here.. I really enjoy reading about your project. Thanks for sharing. If connection setup time is a concern, you might want to consider ZeroMQ. (http://zguide.zeromq.org/page:all) It's what I would reach for if I were in your position. You could easily set up a pub-sub topology which would give you near direct BSD-socket speeds without much overhead, be easy to set up so you can get back to writing terrain code, and give you network topology and language freedom down the line. Let me know if you have any questions!

    ReplyDelete
  6. @kikito: No LOD in this video, but the load is similar cause there are many more cells at the highest LOD.

    Regarding "early optimization as the root of all evil", this is misquoted so frequently it does not meany anything anymore. Bad design is the root of all evil. You should identify the design bottlenecks and work your solution from there. If it is a plane how you get it off the ground, if it a bridge how you make it so it won't fall down. This is where you begin.

    In my case picking a transport protocol is where the design starts. World representation, data structures, everything changes depending on what I pick. It cannot come as afterthought optimization.

    ReplyDelete
  7. @tentus: I love the advice. It did not occur to me to lower resolution in harder-to-see places. Still it is a bit tricky to implement, I will need some sort of occlusion testing. Sometimes you have large overhangs, even if the normal is pointing down, you could get under them.

    ReplyDelete
  8. @Paul: I did not try throttling down to 250K/s. Once thing I could do is to switch to lower resolution models. I'll think of something.

    ReplyDelete
  9. @Paul 2: The only reason I'm considering HTTP is to make my life simpler and be able to release something soon. I don't want to design and maintain servers. With HTTP I can just drop all these files on Amazon S3/CloudFront, which is also very very affordable. If I was going to use sockets, I would stream using UDP. But I'm not going there yet.

    ReplyDelete
  10. @Wouter: Right, but then the Comet pattern would require me to write custom server logic. This is what I want to avoid. With classic HTTP 1.1 you get Keep-Alive, which may work nicely in this case since there are many requests in sequence, and as you keep moving they continue at a steady flow.

    ReplyDelete
  11. So you are just pre-calculating a huge set of terrain files at various resolutions, then fetching them as needed in the client?

    If the web server keeps the connection open, I don't see any problems processing requests and sending replies. Any socket-based protocol is going to do basically the same work.

    If it closes the connection on each file, that could be a problem.

    Amusing to see you diving into servers. That was my latest project as well.

    http://www.sea-of-memes.com/LetsCode39/LetsCode39.html

    ReplyDelete
  12. @Michael: Well, even with Keep-Alive the very nature of HTTP imposes the need for requests. The existing connection is used, but requests still waste time.

    If I was using sockets (or HTTP streaming like Comet, reverse AJAX, etc), there would be a control signal going up from the client to the server for camera position etc, and a constant stream going down with the data. No more individual requests for blocks. There is a big difference there.

    ReplyDelete
  13. I've forgotten the details of HTTP 1.1, but I thought the idea was that a browser requests an HTML page, gets it, then immediately writes GET requests for all the images. It doesn't do them one at a time and wait for each one.

    Your client will just write multiple chunk requests to the socket without waiting, right?

    On the server side, it just reads the socket and parses the GET requests as they come in. It queues up all the files for write and puts them out as fast as the socket will accept them.

    HTTP 1.1 has some wrappers around the pieces of each file, but I don't think there are any waits. I think there's even some protocol for interleaving chunks of multiple files?

    So read and write are independent on the socket, and neither side should wait for replies. But I may be forgetting something and there are ACKs required. I hope not!

    A bigger problem is that I don't think you can cancel a request once made. If the client moves past a bit of scenery and no longer needs the high res version, it would be nice to cancel the request and save the bandwidth.

    Are you going to have a local cache so you don't request a chunk again if the user backs up and enters old terrain?

    ReplyDelete
  14. Well, let me say this is really amazing!
    I know little about network protocols, so better I dont'n say anything, anyway I was wondering how and if the terrain is "modifiable" by the clients (minecraft or dwarf fortress - like game need this): I think is something you need to include in the design.
    Anyway great work, keep going!

    ReplyDelete
  15. @Michael: I think you mean HTTP pipelining. It is a nice feature, but comes at a development cost. There is also some risk. It must make sure the entire stack down from server, proxies and client supports it properly. Google Chrome just got support for it a month ago I think, after years out there. Internet Explorer does not support it yet.

    But even Keep-Alive won't get you that far, most servers set a limit on the number of concurrent requests you can have in a Keep-Alive connection. A default Apache installation comes with five if I remember correctly. At some point the server will close the connection on you.

    ReplyDelete
  16. @Andrea: Thanks. I have not decided on a gameplay yet. What you see here is how meshes are received from the server. How they came to be, it does not matter at this point. They could contain features created by other players.

    ReplyDelete
  17. this is nice but i wanted to ask, is this all being handled inside an octree ? if it is would it be possible to download the octree level by level so that you could have a larger view distance , basically download the highest level of the octree for the most far off distance , then for anything closer you have already downloaded the previous level so you can download a lower / higher detail level of the octree for things that are closer to the camera. my only critique so far is that but maybe this is simply a proof of concept to show that you can definitely download mesh chunks in a stable manner.

    ReplyDelete
  18. @planaria: This video only shows cells in LOD zero, that's why you don't see too far. When I show cells at higher LOD (also higher in the octree) I can have a very large viewing distances, several kilometers to the horizon. Check out my earlier posts and videos about clipmaps, it is basically the same.

    ReplyDelete
  19. This comment has been removed by the author.

    ReplyDelete
  20. Once you have implemented LOD loading and have great viewing distance, will you implement world curvation? Meaning, things that are farther away are displayed lower. This way no elements pop in to existence, they just look naturally coming from horizon.

    ReplyDelete
  21. @aXu: I have considered it, yes. I was thinking of bending the far edges, like putting cloth over a table.

    ReplyDelete
  22. @MCeperoG @aXu:
    Like with Deathspank, but hopefully not quite as strongly?
    ( http://youtu.be/7Qbwa4Pgm7E?t=40s )

    ReplyDelete
  23. We got a meeting in 5 minutes! :P

    ReplyDelete
  24. Hey, just wanted to say I think your really going somewhere with this. Its coming along really well, and whatever it will become in the end, I think "Voxel" would be a pretty interesting and original name for it.

    ReplyDelete
  25. Surely if you implement your without HTTP you would want to use tcp; with udp packet loss is far more likely and presumably would result in bits of mesh going missing. Admittedly the resend on tcp may add too much latency but if you used several tcp connections you should be able to mitigate that while reducing packet loss probability.
    @Anonymous, I think "Voxel" would be a bad name because it would probably be swamped on most search engines by eg. people talking about minecraft.

    ReplyDelete
  26. @Adam: You can have lost packets resent over UDP, you need to do it yourself but it is not difficult. It is not an overhead as TCP does this anyway. People often say UDP with delivery control is equivalent to TCP, so why bother in the first place and just don't use TCP. They are missing one key point. TCP is also a streaming protocol, they make sure data arrives in the same order. For streaming mesh chunks, the order is irrelevant as long as all pieces are received. So UDP still has a big advantage if you don't care about the order.

    Also some of the packets you can afford to loose, for instance if the chunks are refined progressively, for the last layer of refinements it does not matter if they arrive or not.

    One thing to be careful about UDP is you need some form of throttling. You could flood the network easily and cause congestion.

    ReplyDelete