Code optimisation

edited November 2014 in Modding and Coding
Just a thought for now but I post it while it's in my head.
Gavan did a really great job developing his engine and the result is really impressing.

However with the new perspective camera + possible support for CastAR and Oculus Rift there is a huge need for top performances.
I think Gavan already has an mental roadmap for that but he can't possibly be expert in all computer-science fields (plus he will be quite busy with AI and gameplay).

That's the motivation behind this thread: a place for Gavan to expose his 'problems' and a place for experts from various domains to answer and propose optimizations.

Comments

  • **thinks of post LT release Josh Parnell and grins hopefully**
  • Yep, there is a lot of work to do in terms of optimization. I often get quite a few good suggestions from other coders. Just today, Florian Bosch emailed me a few, you may recognize some of his work:
    http://twitter.com/pyalot

    I'm generally at least vaguely aware of many optimizations that can be done, but always open to suggestions and there are definitely things I might not think of.

    Currently, with perspective cam I am definitely going to do volumetric mipmapping, for lack of a better term - less voxels rendered as objects get farther away. This requires approximately twice as much memory though. I already have viewport culling working; it renders chunks only within the viewport (using a crude but effective method - a dot product with the lookAt vector of the camera).
    Another optimization is front to back sorting, so that clipped fragments dont get processed. Additionally considering rendering far away chunks to a skybox or skysphere. Many more relatively "low hanging" optimizations that can be made.

    My primary problems I think will be around things that are really "simple." There are many tricks and gotchas with C++ that I simply unaware of, and releasing source will reveal this. I've also made some poor decisions, including writing my own vector class, and that probably needs to be phased out (I never actually intended to, I just whipped together a vector class to test some stuff, not bothering to search for a good existing implementation, and added more and more features to it over time, and it still lacks overloaded operators (+,-,=,etc) and up until recently had really cumbersome accessor methods. I have odd ways of going about some problems that are probably not the best solution - i.e. in order to speed up compile times, I knew that much of the compile time is created in figuring out headers, dependencies, and linking, so I created a batch script that creates a single linear C++ file (out of many base files) and compiles it. It also auto-generates header information using LZZ, which probably increases compile time but also saves me sanity and having to write duplicate code. This script also helps me avoid "header hell" where you have a hard time figuring out what to include and where - since everything is linear, it is relatively straight forward and you simply name a file name in the order you want it included (preceded with a number like "f00200_filename.cpp"), with a forward class declaration if needed (this means you have to rely on class pointers though, not explicit generation, but its not entirely bad and there are ways to do this without using the new operator all the time). Overall, it does seem to speed up compile time significantly, at the cost of debugging a generated file instead the original source files (which actually has never been much of a problem yet - fairly easy to match the two up).

    Anyway, I feel that some of my practices will likely annoy most sane coders. :)

    In general I'm not always the best at sticking to accepted practices and this will have to change as the code goes out - being a solo coder means I do things usually with the least resistance, and to my fault I'm often inclined to write things myself versus learning an existing library (on the plus side, I must say that some of my libraries are better than existing stuff I have found - namely, the GUI and text render that I wrote are far better than most libraries I have seen yet, and they are not even that great, its just that so many GUI libraries are severely lacking in one way or another, as anyone knows who has tried to find one). Additionally, in writing everything myself over the years, I think I've developed a better understanding of everything - to point to the GUI again, I've written over 6 GUIs at this point, so I know what kinds of things I find annoying or cumbersome.
  • I'm DEFINITELY gonna be putting LZZ in my back pocket for later use, that sounds ridiculously useful.
  • mmnumbp said:

    I'm DEFINITELY gonna be putting LZZ in my back pocket for later use, that sounds ridiculously useful.

    http://www.lazycplusplus.com/

    Yeah it is seriously the best tool I have ever found, and quite easy to use. How many times have you written a variable or changed a function parameter, only to forget to declare it in the header?
  • edited November 2014
    gavanw said:

    Currently, with perspective cam I am definitely going to do volumetric mipmapping, for lack of a better term - less voxels rendered as objects get farther away.

    To me that looks like dynamic tree structure (simple example : octree). Voxel Farm uses dynamic octrees for that and for occlusion too : http://procworld.blogspot.fr/2013/05/covering-sun-with-finger.html

    Concerning other optimizations, before going too far I'd benchmark every loading/rendering step to address the costlier first (i.e. if function A takes 20% of the time and function B takes 5%, even a small optimization of A is better than working on B).

    Outside of frame rate : judging from the videos, loading data seems to take quite a long time. That could be interesting so see what can be done there.
  • Clement said:

    gavanw said:

    Currently, with perspective cam I am definitely going to do volumetric mipmapping, for lack of a better term - less voxels rendered as objects get farther away.

    To me that looks like dynamic tree structure (simple example : octree). Voxel Farm uses dynamic octrees for that and for occlusion too : http://procworld.blogspot.fr/2013/05/covering-sun-with-finger.html

    Concerning other optimizations, before going too far I'd benchmark every loading/rendering step to address the costlier first (i.e. if function A takes 20% of the time and function B takes 5%, even a small optimization of A is better than working on B).

    Outside of frame rate : judging from the videos, loading data seems to take quite a long time. That could be interesting so see what can be done there.
    Yeah still need to benchmark, I have done no profiling to date. Chunk generation is slow, lots of things can be done to speed it up though (for example, lowering resolution by half is an 8x chunk generation speed up (2x2x2).
  • edited December 2014
    Hello, I am really impressed with what the game engine has become so far and I am totally your fan : ). As happy with some of the work done with optimizations I think theres still a lot that can be done. I was considering the idea of trying to write a highly technical microservices networking thing for the voxel engine when it is out. Microservices would help procedural generation scale a heck of a lot better, but it would take some work to get right. I have a good quick intro to what microservices in response to a question on hackernews here: https://news.ycombinator.com/item?id=8678446
    (The development stack here is a bit different from what I think would be constructed a bit but it is a good overview of the concept. The great thing about microservices now though is that they are becoming mainstream in concept for developing major company services, AI, and whatever else you name it microservices makes things more scalable/dealable as an approach.)

    A more related example for microservices is Joyent's Manta ( https://github.com/joyent/minecrab ) allows you to save minecraft games and reload them in real-time. Something similar but working for the game engine using Elixir would probably be just as powerful. Part of it may rely on xcat: http://sourceforge.net/p/xcat/wiki/Main_Page/ . It would also probably end up using redis as a cache for loading some assets. I am still sort of working out specifics in how to design such a thing and drawing out which connected projects will be used, but If you want to work on this with me I'd be very happy : ).

    As for something that can be done now though sometime around the release to github. I think you should take a look at a few of the papers posted here: http://users.soe.ucsc.edu/~amsmith/papers/ In particular these two: http://users.soe.ucsc.edu/~amsmith/papers/voxel-pcg.pdf and http://users.soe.ucsc.edu/~amsmith/papers/ucsc-soe-10-08.pdf

    There is also a good voxel blog here: http://realtimevoxels.blogspot.com/

    There are also some things worth looking at or adding from this guy that are more than worthwhile: https://github.com/syoyo/tinyobjloader , https://github.com/SmallVCM/SmallVCM , https://github.com/syoyo/Fujiyama-Renderer , https://github.com/lighttransport/mallie

    Also some design patterns in cplusplus besides lazycplusplus that may be of interest: Await 2.0
    Stackless Resumable
    Functions: http://emma.memect.com/t/af63dd393a938c4669bc68fed55d586ed009d5225da610891e030b1878add082/await 2.0 - Stackless Resumable Functions - Gor Nishanov - CppCon 2014.pdf
    And:
    https://github.com/kohler/tamer
    And:
    http://gamadu.com/artemis/index.html (there is a C++ version on github somewhere)
  • @Switch33‌ Awesome, thanks for these links, I am already digging into some of them (so far these resources look very useful). I had considered networking the generation aspect myself, using cheap discrete units like an XBOne or PS4, but of course this is something I don't have time to dig into at this point. Still, would not be too hard to take a single world seed and generate various parts of it on different machines or server instances.
  • edited December 2014
    Hardware is not as important with a microservice architecture. A lot of the work for the networking thing is probably already done, I've found good resources for it, but I think that it would take some time to figure out how to connect some of the dots.

    But networking is definitely an after thought after the code release. I am still very much in concept even after collecting lots of the resources for it.

    I appreciate you being so active on the project. It really is inspirational and is somewhat has lead me to go back to pursuing game development after I stopped before college. Even though I kept up with an IT major and marketing major/finished with them. I really wanted to do something really indie, and your project will hopefully allow me some real freedom if we make it truly great. :)
  • Switch33 said:

    Hardware is not as important with a microservice architecture. A lot of the work for the networking thing is probably already done, I've found good resources for it, but I think that it would take some time to figure out how to connect some of the dots.

    But networking is definitely an after thought after the code release. I am still very much in concept even after collecting lots of the resources for it.

    I agree, there are probably good existing implementations.
    Switch33 said:


    I appreciate you being so active on the project. It really is inspirational and is somewhat has lead me to go back to pursuing game development after I stopped before college. Even though I kept up with an IT major and marketing major/finished with them. I really wanted to do something really indie, and your project will hopefully allow me some real freedom if we make it truly great. :)

    I'm just happy that people are interested in this stuff, and to be able to work on it. :)
  • edited December 2014
    What would be really neat maybe even further down the line after networking is to maybe develop an in editor scripting language + live editing that is a bit restrictive, but that is entirely a different project.

    Lobster posted on HNs before is inspiring in that regard as well: https://github.com/aardappel/lobster The idea is if you make development even simpler you will have a much larger user base than just casual coders as well long as it's not too restrictive on modular development. You could even easily develop an asset type stores where content can be created etc. Or at least thats what I see as near an end final idea when things finally start getting finished. But that is a long way off.
  • Switch33 said:

    What would be really neat maybe even further down the line after networking is to maybe develop an in editor scripting language + live editing that is a bit restrictive, but that is entirely a different project.

    Lobster posted on HNs before is inspiring in that regard as well: https://github.com/aardappel/lobster The idea is if you make development even simpler you will have a much larger user base than just casual coders as well long as it's not too restrictive on modular development. You could even easily develop an asset type stores where content can be created etc. Or at least thats what I see as near an end final idea when things finally start getting finished. But that is a long way off.

    From the GLSL/JSON standpoint, you can do quite a lot of live editing, since both can be hotloaded. One area I see potential is just using it as a 3D graphing calculator. It is literally as simple as dropping in an equation and evaluating it - there are not many quality volumetric graphing solutions out there, unless you want to dig into more expensive/complex things like Matlab or Mathematica.

    I was considering running an app/asset store as one way of continuing to fund the game if/when it reaches the point of being permissive open source (and simulataneously provide trusted content), but as you say that is a long way off.
  • edited January 2015
    For graphics and model interchangeability there is https://github.com/assimp/assimp, https://code.google.com/p/alembic/ , http://openddl.org/ . I dunno if you are using any of them or not. They allow for quick importing/exporting between a large number of formats though. These are completely separable from the engine.

    Code optimizations that can be done much later:

    https://research.nvidia.com/publication/topological-approach-voxelization This is a topological based voxelization method that will reduce computation required. Found an example that could be done with using samplecode to trim isometric voxels for topology: http://research.microsoft.com/en-us/um/people/hoppe/proj/isotoposimp/
    Alternatively there is an article here about simplifying isosurfaces: http://0fps.net/2012/08/20/simplifying-isosurfaces-part-2/


    http://www.cse.chalmers.se/~d00sint/ There is optimized code for generating shadows for voxels here with a downloadable example as well as some other demos.

    http://www.cbloom.com/3d/ This guy has a few good points on how to develop games in text files or demo code files worth browsing through.

    http://www.openvdb.org/ openvdb - vertex based procedural content generation.


    As for water I think blender users often end up using "meta-balls" for water simulation. I'm not sure how the water is generated now either, but it may help to google it up and see if it can help improve physics simulations at all.


    A good reference for spherical voxels and smoothing them: http://0fps.net/2012/11/28/conways-game-of-life-for-curved-surfaces-part-2/


    http://0fps.net/2012/01/14/an-analysis-of-minecraft-like-engines/

    Something that can be done relatively with little effort that may provide a real speedup:
    Roaring bitmaps: https://github.com/lemire/RoaringBitmap , http://arxiv.org/abs/1402.6407
    For indexing: https://github.com/tuplejump/extendedset , http://arxiv.org/pdf/1004.0403v1.pdf

    also jpeg-xr: https://en.wikipedia.org/wiki/JPEG_XR

Sign In or Register to comment.