Page 1 of 5

[GSoC 2011 - Accepted] Terrain paging improvements

Posted: Sun Mar 20, 2011 11:14 pm
by kuxv
Hello,
here is my proposal for GSoC project:

Motivation
Current terrain component introduced in Ogre3D 1.7 uses chunked level of detail(LOD) together with geomorphing to achieve continuous LOD for terrain(heightmap) rendering. This terrain component performs very well on smaller sets of height data which is it's purpose however problems with limited size of memory come with larger sets of data. Paging of data is common solution for memory issues of this kind and paging component already exists in Ogre3D however it's performance is very poor when used together with terrain component and is not ready to be used in a real project. The current paging strategy which is used for paging terrain tiles in/out is also not optimal in some cases.

Project
There are basically two problems using terrain paging in Ogre3D. Poor performance of terrain paging and simple paging strategy used to select tiles for swapping in/out.

Poor terrain paging performance causes visible tearing/delay when it comes to load another page tile for rendering. This project will address this issue by modifying the way terrain component handles data. That involves:
  • separate load of specific terrain data belonging to specific LOD instead of only possibility to load whole terrain data at once so more distant terrain tiles could be loaded only in low LOD
  • load of terrain data in background or at users own decision
  • notification system for various terrain component events like progress of data loading/preparation so user knows what about the progress
In some cases there is a problem with terrain tiles missing in the view or problem with actually rendering more tiles then needed. This issue is caused by default simple paging strategy used(Grid2DPageStrategy) which loads terrain tiles based on radius around camera. The project will bring new paging strategy which will try to be more accurate using actual terrain shape visibility from camera.

There will be introduced new demo to demonstrate above functionality:
  • import and prepare terrain data
  • load/unload specific terrain LOD
  • use of/react on terrain load events
  • switch between different LOD strategies
Proposal Timeline
Bonding period (27 Apr – 24 May):
  • Play and experiment with Ogre3D terrain and paging components and with its demo and test applications to further improve knowledge about it. Examine threading Ogre3D threading model and other needed core functionality as well.
  • Actively interact with my mentor and Ogre3D community to discuss final details of my intended implementation. After this I will be absolutely sure about every bit of my future work.
Official coding time starts (25 May – 12 Jul 2011):
First work to do is to implement separate LOD load mechanism for terrain component, notification system for it and test it. I divided whole project into stages so progress can be easily followed. Each stage also involves testing of added functionality.
  • Stage 1 (25 May – 14 Jun): Separate LOD loading for terrain component. Modification of terrain component’s code to allow separate loading of height data.
  • Stage 2 (15 Jun – 21 Jun): Implement loading and preparation methods as background tasks.
  • Stage 3 (22 Jun – 30 Jun): User notification system for background tasks. Make this system configurable by user.
  • Stage 4 (1 Jul – 12 Jul): Make demo using new load mechanism. Option to display various debug statistics as well.
Mid-term deadline (15 Jul):
At this point separate LOD loading should be fully working and integrated in Ogre3D. There should be test/demo showing it’s functionality as well.

After mid-term (17 Jul – 16 Aug 2011):
In this phase implementation of new paging strategy takes place as well as creation of new terrain features showcase demo and its documentation.
  • Stage 5 (17 Jul – 30 Jul): Implement new paging strategy to replace current paging strategy (Grid2DPageStrategy).
  • Stage 6 (31 Jul – 10 Aug): Put together final application to show and demonstrate new features.
  • Stage 7 (11 Aug – 16 Aug): Final tests, bug fixes and documentation.
Any remaining time will be used for overall testing and bug fixing.

Suggested ‘pencils down’ (16 Aug):
All the project’s targets will be fulfilled now and there will be application demonstrating them in a practical way.

Why I’m the one for the project
I’ve been interested in Computer Graphics for a few years now. I have studied CG at Masaryk University in Brno, Czech Republic. I have used Ogre3D in my little pet projects and I’m familiar with it’s design and concepts. I have experience with heightmap terrain rendering as I did that as part of my thesis and worked on game engine which involved heightmap rendering as well. I also have a sound knowledge of C++ coding and project development as I was working as a developer in software company. Now I’ve decided to continue university and so I have whole summer for this GSoC project. I would like to give something useful back to community as well.

Re: [GSoC 2011] Terrain paging improvements

Posted: Thu Mar 24, 2011 1:34 am
by kuxv
I would like to also give terrain and paging components more work in future at least by fixing all their bugs. Also a demo showing
how to combine terrain with overhangs, cliffs or caves is on my ideas list.

Re: [GSoC 2011] Terrain paging improvements

Posted: Thu Mar 24, 2011 10:06 am
by syedhs
While I am already more than happy to see smooth, seamless terrain paging out of the box (with all bugs ironed out), I am curious.. are you going to address Very Large Terrain (VLT) issues as well such as objects jitters when the coordinate is large eg x or z with value > 100,000? Because when we speak about terrain paging, we also speaking about VLT as well, although I can see there are cases not needing it.

Re: [GSoC 2011] Terrain paging improvements

Posted: Thu Mar 24, 2011 9:26 pm
by kuxv
Hello. No I'm not going to consider VLT issues for now. My primary concern here is smooth paging. But VLT problems seems like very good topic to look on next. Thank you for idea.

Re: [GSoC 2011] Terrain paging improvements

Posted: Sun Mar 27, 2011 10:54 pm
by kuxv
I have put together my draft of GSoC 2011 proposal for this project. If there will be no objections or comments I will send it as it is. I updated first post with the link. All kinds of comments are welcome.

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Mar 28, 2011 4:56 am
by kuxv
I have more thoughts to share with you about my intentions on what I want to do.

Terrain Component:
- Separate LOD loading:
Should allow for fluent paging of terrain because problem here is big delay caused by loading more distant tiles. So modify code to allow load/unload of just specific LOD level(s).

- Different file structure:
Should allow more faster load of terrain data, like loading only specific LOD level(s). I want to reorganize it to have lowest LOD data and textures at beginning of file to read it faster sequentially to more improve loading time Because what you really need at the beginning is to load only low LOD + its textures for displaying it. There should be different format for single terrain component and paged terrain. Format should be like this:
- Terrain Component specific: file should contain LOD metadata, then textures(composite, lightmap, ...), then heightfield data belonging only to LOD N (lowest detail first), then LOD N-1, ... LOD 0
- Paged Terrain specific(ie more Terrain Components used together): LOD metadata of all terrains, heightfield data for LOD N and textures of one Terrain for all Terrains, then only heightfields(no textures needed) for LOD N-1 of all Terrains, ..., LOD 0

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Mar 28, 2011 9:27 am
by stealth977
IMO, there is not much need to change terrain file format. Lower lods of all terrains belonging to a terrain group can be saved in a terraingroup.dat file.

If we save all but highest 3 LODS, the space required would be around 1/32 to 1/64 of the actual data...

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Mar 28, 2011 10:37 am
by Noman
Had a look at your proposal. Definitely in the right direction.

The first thing that popped out to me was that I'm not 100% convinced you can pull all of the tasks in time. To prove me wrong, you can :
1 - Start estimating the time needed for each task in your list, and see that it finishes in time. Be honest and consider real-life limitations (exams in university, for example)
2 - Divide your project into milestones, where at each milestone you have something deliverable to OGRE, so that if time runs out you don't end up with a pile of untested, unpolished code which won't be integratable in Ogre. You might already have such a division, but its good to state it explicitly in the application.

Despite the critique, it is a good application! Keep it up!

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Mar 28, 2011 11:28 pm
by kuxv
@Noman: I updated my proposal according to your suggestions. I split timeline into more pieces and added little more info. I'm quite confidend about the tasks I want to do and I would be working on it full time. There is nothing in my plan otherwise. I have just had big holiday and I'm going to jump straight back to coding.

@stealth977: Ok, that sounds like a good point. I will look into that and let you know about my thoughts.

Thank you.

Re: [GSoC 2011] Terrain paging improvements

Posted: Fri Apr 01, 2011 3:49 am
by kuxv
@stealth977: About different file format. I wanted to make new format to speed up height data loading(reorganisation of data in file to be avoid some skipping during file read). Saving lower LOD data in terraingroup.dat file would help to speed load time and avoid new file format but then there is duplication of those data(in terrain.dat and terraingroup.dat). That's what I wanted to avoid. But after all I don't think that reading of height data in different order would make big difference in overall terrain rendering. So I will make it as a option to try when I would have spare time on project. I would first go with data duplication(ie storing low LODs in terraingroup.dat) and if there is any measurable speed up I would also try to look at option to avoid data duplication(so new file format probably). But you are right that storing just low LODs in separate file takes only fraction of actual terrain data. So it would be good to try it first. I just wanted to avoid data duplication even if it is just a little extra size.

Re: [GSoC 2011] Terrain paging improvements

Posted: Fri Apr 01, 2011 9:38 am
by stealth977
@kuxv:

Data duplication wont be an issue since as i mentioned, depending on the LOD range, duplication can be ~1/40 - ~1/N which is very very small. But the main benefit is using A SINGLE FILE for lowest lod, where the traffic will be high.

Lets say you have a 3x3 hot spot and a 5x5 on hold area, which means one patch around your active patch will be always visible and 2 patches away will always be kept ready/or background prepared, each time you move, depending on your movement direction between 3(vert/horz movement) - 5(diagonal movent) patches need to be loaded. This increases rapidly as your hotspot area increases.

Most of the time, those new patches will not be at full detail and again most of the time the user will not even get close to them to force them to be at full detail, so, most of the actual traffic will be at LOWER LODS.

And, for the highest lods, the data size will be huge enough to make any data ordering obsolete, data ordering(preventing seeks) is only important if you are gonna make many small reads, but in the case of high lods, the data is huge and a seek wont cause any comparable delay.

But for lower lods, you would definitely want to avoid seeks as much as possible, but another important thing to avoid is ACCESSING MANY MANY FILES, if you order your data inside the patch file, you will still need to access all those files one by one and there can be many many files depending the load/hold radius. Keeping lower lods in one file and in ordered form would decrease both seek time and file access delay, while not breaking the old format since its been around for a year and am sure there are lots of people who got used to it...

Thats my 2 cents =)

Re: [GSoC 2011] Terrain paging improvements

Posted: Fri Apr 01, 2011 10:12 am
by syedhs
What is the typical size of lower lod per chunk? If the size is not too big, then probably what can be done is to store one file per terrain page, and then have the background process to load the whole file (or asynchronously load the whole file) and from there, any 'seek' is just a pointer arithmetic. I think one of the factors which ensured paging smoothness is not to introduce a big enough file that causes the FPS to stutter. Probably need to introduce a setting which dictate the maximum file size before writing a new one, but this could be unnecessarily complicated :mrgreen:

Re: [GSoC 2011] Terrain paging improvements

Posted: Fri Apr 01, 2011 10:39 am
by stealth977
lets say full patch size is 256x256

Avg Data = 257 x 257 x 40(avg per sample data) = 2.5 MB per patch

lods are:

0 - 257x257x40 = 2640K (full detail file size)
1 - 129x129x40 = 666K
2 - 65x65x40 = 170K
3 - 33x33x40 = 44K
4 - 17x17x40 = 12K
5 - 9x9x40 = 3K
6 - 5x5x40 = 1K
7 - 3x3x40 = 0.5K

if we keep lods 3 - 7 in a separate file : 44K + 12K + 3K + 1K + 0.5K = ~60K which is 1/40 of the actual patch data (only %2.5 duplication)..., if we store lods 2-7 then it becomes 230K which is 1/11 of actual patch data, even which is acceptable (only %9 duplication)

Of course this all depends on your splat/color/light map sizes too and at what lods those maps will be saved, also the number of lods may change, a lod of 3x3 - 5x5 maybe too low for current hardware and can be skipped, same can be applied to various splat/light/color maps...

Another feature, although can make the usage more complicated, could be to divide the data to 3 stages; (example 10 GiG data set 16385x16385 map size with pretty detailed light/color/splat maps)
1 - In memory stage, some few lower lods are always in memory, configurable by programmer (lets say lod 5, 6 and 7) (only %0.18 of actual data, 18 MB for a 10 GiG data set)
2 - Middle Lod stage, pre-determined number of lods are read from a unified single file on demand (lets say lod 2, 3, and 4) (%8.6 of actual data, 860MB for a 10 GiG data set)
3 - High lod stage, pre-determined top lods are read from patch file (lod 0 and 1) (%91.2 of actual data)

of course all this can be configurable according to programmer's needs, can keep more in memory, less in middle stage for example, or the opposite...

Re: [GSoC 2011] Terrain paging improvements

Posted: Sun Apr 03, 2011 6:30 am
by kuxv
So if it sounds to me like I make preparation stage for paged terrain which creates new file used for whole paged terrain and stores low LODs of all used terrains inside. Then paged terrain will use this file to load low LODs and specific terrain file for higher LODs as needed. Paged terrain filesize should be relatively small because we store just a fraction of actual terrains. For example if paged world of size 256x256 is used and one tile is 257x257x40 then actual paged terrain filesize would be:

only lvl 7 stored: 24 M
7 - 6: 90 M
7 - 5: 303 M
7 - 4: 1.1 G
7 - 3: 4 G

full detail: 174 G

Of course it heavily depends on size of paged world. So storing just a few lowest LODs looks good. How many LOD levels will be actually stored should be calculated on fly according to world and terrains size.

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Apr 18, 2011 11:16 pm
by Beauty
Thanks kuxv for your proposal. :D
In my eyes the terrain component would be a good point for Ogre improvement.
Good luck. I hope your project will be accepted by google.

Re: [GSoC 2011] Terrain paging improvements

Posted: Mon Apr 25, 2011 9:16 pm
by Noman
Congratulations! Your project has been accepted to Google Summer of Code 2011, and you have the honors of having sinbad as your mentor!

We'll be setting up a working environment in the coming weeks. In the meantime, could you please update the wiki page of your project with the latest version of your proposal?

http://www.ogre3d.org/tikiwiki/SummerOf ... evelopment

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Tue Apr 26, 2011 12:10 am
by kuxv
Thx, awesome ;) Wiki page updated with project proposal.

Re: [GSoC 2011] Terrain paging improvements

Posted: Tue Apr 26, 2011 12:13 am
by Beauty
Noman wrote:Congratulations! Your project has been accepted to Google Summer of Code 2011, and you have the honors of having sinbad as your mentor!
Amazing!!
Congratulation to kuxv and the whole Ogre community :D

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Tue Apr 26, 2011 10:45 am
by spacegaier
One general note: Please always add important points such as the link to the Ogre fork where you will do your work also to the wiki page, so that those key information are stored at a central place. Thanks!

Re: [GSoC 2011] Terrain paging improvements

Posted: Tue Apr 26, 2011 12:23 pm
by syedhs
Noman wrote:Congratulations! Your project has been accepted to Google Summer of Code 2011, and you have the honors of having sinbad as your mentor!
Wow this is really great.. if all objectives are achieved then Ogre terrain has grown even greater! :) + the man himself as the mentor.. congratulation..

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Fri Apr 29, 2011 3:43 pm
by SunSailor
I'm really looking forward to these changes and I hope, this will be one of the few GSoC projects, which get finished and get accepted in the main trunk.

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Wed May 18, 2011 8:08 am
by Noman
Hi,

Coding season is nearly upon us, so it is a good time to read up on mercurial and set up a fork that you will use to develop your project.
I recommend first reading a bit about distributed source control (if you aren't familiar with it). I used http://www.hginit.com as its fairly friendly and simple.
Afterwards, create a user on bitbucket and fork ogre. Some URLs to help you do that :

http://www.ogre3d.org/developers/mercurial
http://www.ogre3d.org/docs/OGREDevelope ... index.html
http://www.ogre3d.org/tikiwiki/Getting+ ... TortoiseHG (if using windows)

The fork name should be Ogre-GSoC2011-TerrainPaging

Good luck!

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Wed May 18, 2011 8:42 am
by kuxv
Hi, I have set up mercurial repository already. It is here https://bitbucket.org/kuxv/ogre_soc_tpi/overview
I put link to it at wiki page http://www.ogre3d.org/tikiwiki/SoC2011+ ... repository
Project's name is different thou. Should I change it? I'm not sure it bitbucket supports that. Sinbad knows about it anyway and he cloned it already.
If I make any progress should I update this forum's thread and wiki as well or is wiki enough?

Cheers

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Wed May 18, 2011 9:27 am
by Noman
The project name isnt critical, its fine to keep it as it is.
When I was a GSoC student, I mainly used the forum for progress updates and updated the wiki 3-4 times during the project when major progress points finished. I like it that way because the forum is more suitable for time-based progress IMO (each post has a date and can notify people etc), and you can just read the latest post instead of search the wiki page for the latest changes to see whats up. Its also better for discussion around your progress. With that being said, it is still up to you and your mentor to decide.

Re: [GSoC 2011 - Accepted] Terrain paging improvements

Posted: Wed May 18, 2011 12:19 pm
by sinbad
Yeah I agree - the forum is the best for a running commentary of updates, but the wiki page should be kept periodically up to date for people who want an overview of the project. Mostly you'll want to update the wiki only on major milestones, Noman's 3-4 times is a good guide (with the last one being at the end of the project).