[GSoC 2008 - Accepted] Different Level of Detail Strategies

Threads related to Google Summer of Code
LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

[GSoC 2008 - Accepted] Different Level of Detail Strategies

Post by LostEra » Tue Apr 01, 2008 4:05 am

My proposed GSoC project for the Different LOD Strategies project was accepted.

Here is my proposal abstract:

In determining what level of complexity to use in representing 3D objects, OGRE currently implements only one approach, a level of detail strategy based on entity distance from the camera. In this implementation, each level of detail for a mesh has an associated reference distance. However, there are several drawbacks to this approach. It does not account for changes in camera field of view (for instance, when zooming) or viewport size. Multiple methods have been proposed to solve these issues. Of these, the simplest and fastest is to estimate the pixel count by projecting the bounding sphere, replacing the reference distance for each level of detail with a reference pixel count.

The goal of the project is to extend the current level of detail system to support multiple strategies and then to create a new strategy that remedies the drawbacks of the current approach while still providing support for older mesh assets.

Project Components:
- Extend the level of detail system to allow for multiple strategies while continuing support for assets using the current strategy.
- Within this new system, implement a pixel count approximation strategy which provides more appropriate level of detail selection for a variety of viewing conditions.
- Change the automatic level of detail generation to utilize the new strategy.
- Provide a means to address the drawbacks for assets using the old system by computing an automatic correction bias.


In a comment on my proposal, tuan kuranes asked that I read about the "lod listener" ideas on the forums, and see if I can take it into account in my framework/planning work. After reading the posts and doing some preliminary work to see what was involved, I decided to proceed with that project immediately instead of including it in the summer project. You can see what was accomplished and the discussion here.
EDIT: The lod listener project is now being incorporated into this project and all new discussion should take place in this thread, but previous discussion can still be viewed by following the link above.

The wiki page for my GSoC project can be found here. It contains a description of my progress to date.
Last edited by LostEra on Tue May 27, 2008 12:01 am, edited 1 time in total.
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Tue Apr 22, 2008 5:55 am

I'd like to get some input from the community before coding begins. I can think of two methods of allowing multiple strategies.

The most general method would be to incorporate an abstract LOD strategy class, but this would probably be associated with a performance penalty. The primary benefit of this method would be the ability to add additional strategies from plug-ins through the use of factories.

The simpler and faster method would be a basic conditional in the LOD calculation.

Let me know which method you think would be optimal or if there is a better alternative.

Thanks!
0 x

User avatar
KamiKage
Kobold
Posts: 25
Joined: Thu Mar 27, 2008 11:02 am
Location: Portugal

Post by KamiKage » Tue Apr 22, 2008 8:44 am

Hello and congratulations to you being selected ^^

What I think is that if you want to allow multiple strategies the first option seems more appropriate, as it also may fit better in the philosophy that "Ogre is design-led".

The problem with this option, I think, it's that there has to be a way for strategies to calculate a normalized lod value. And it might not be that straight forward to find a way to normalize them. Or maybe I'm still looking at it the wrong way :)

Anyway good luck to you ^^
0 x

User avatar
Zeal
Ogre Magi
Posts: 1260
Joined: Mon Aug 07, 2006 6:16 am
Location: Colorado Springs, CO USA

Post by Zeal » Tue Apr 22, 2008 7:10 pm

Do you plan on implementing new ways to HANDLE lod? Or just ways to calculate it? Dont get me wrong, having more options other than just 'how far is this from the camera' would be nice, but this information is only useful if you can actually DO something with it (automatic imposters hint hint).

Of course I understand that would mean quite a bit more work, so I would understand if you dont want to bite off that much :p.
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Tue Apr 22, 2008 10:18 pm

@KamiKage
Thanks. I agree that the Ogre philosophy would certainly indicate the most flexible solution should be pursued as long as the performance penalty is not prohibitive. Personally, I liked this solution, too, so it's nice hear other opinions which support it.

@Zeal
The project, as proposed, does not deal with ways of handling lod once it is determined, only calculation, but you might want to look at the lod listener project mentioned in the initial post for a framework to build strategies for handling lod off of. The thread for that project is here.

Thanks for the feedback.
0 x

User avatar
Zeal
Ogre Magi
Posts: 1260
Joined: Mon Aug 07, 2006 6:16 am
Location: Colorado Springs, CO USA

Post by Zeal » Tue Apr 22, 2008 10:52 pm

Yes it sounds like a good coupling between the 'calculations' and the 'handling of those calculations' is important. So I suppose it sounds like the best approach you could take in your project would be something that allows for great user customization (the 'lod listener' concept sounds like a good idea).

So your lod calculations fire a custom listener, then it should be somewhat trivial to do 'automatic' impostering, ect...
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Mon May 26, 2008 11:47 pm

Coding on this project has now started, and you can see the current state in the repository. At present, the LodStrategy class is utilized when computing lod for meshes, and the old (distance based) strategy has been implemented.

Sinbad has suggested that I incorporate the lod listener work into this project, so that and material lod are next on the priority list.
0 x

User avatar
sparkprime
Ogre Magi
Posts: 1137
Joined: Mon May 07, 2007 3:43 am
Location: Ossining, New York
Contact:

Post by sparkprime » Sat May 31, 2008 7:32 pm

First it'd be good to have some kind of FOV consideration going on in ogre rather than just the distance.

More generally, it would be interesting to see different methods of LOD in ogre.

Of particular importance is lessening the visual effect of the LOD shift.

The earlier GTA games used an alpha fade technique which works if the models are done in a particular way.

GTA4 uses dithering instead of alpha but essentially does the same thing.

In my game I've created a MovableObject that has its own manual LOD implementation (I needed to transform the low LOD mesh on top of the scene node transformations which entities don't support). It fades between LOD levels and fades out at max render distance. It assumes every material "blah" has a material "blah'" (with an apostrophe on the end) and uses the blah' material when it's fading. The intention is the blah' material has a shader, and my code uses a custom parameter to tell the shader how faded out it should be. This doubles the number of materials, but apart from that it seems to work well. A client app can clone materials at runtime and do some basic stuff (turn on scene blending, set up the shader) if they don't have a special fading version already.

I can configure the % of distance during which a fade occurs, I do it globally but I'm not sure this is generally correct.


By having manual LOD, you get material LOD for free because your low detail meshes can refer to low detail materials. I think the key benefit of LOD is to reduce the number of batches. Especially with buildings. It would be good to have a LOD strategy where things faded from high to low LOD and then faded into some kind of InstancedGeometry batching scheme. I think this would allow you to render the whole city all the time like in GTA4. Also using smaller textures at low LOD, and unloading the bigger ones is good for memory use.

Just my experience implementing LOD and some ideas in case you're interested.
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Sun Jun 01, 2008 6:21 pm

I've put the next batch of code up, so now materials also make use of the LodStrategy class. LOD listeners are next up.

@sparkprime
As part of the project, I intend to implement a pixel count approximation strategy, this would not only take FOV into account but viewport size.

While fading between LOD levels would be very useful, I don't think I have time to incorporate it into the summer project. However, I believe such a system could make use of the LOD listener work which is now part of this project.

Thanks for the input. It will be very helpful to have these usage scenarios in mind when I continue work on the LOD listeners.
0 x

User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19265
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 2
Contact:

Post by sinbad » Mon Jun 02, 2008 10:04 am

Good work, and thanks for being so consciencious about keeping track of interface changes in your documentation, that will come in very handy.
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Sun Jun 15, 2008 1:27 am

Sorry I haven't posted here in a bit, but here's a progress update. I merged in the lod listener work a week ago (with some modifications and additional features). I've also just put up code extending the usage of lod strategies to instanced geometry. With that complete, it shouldn't take too long to do the same for static geometry as they're structured similarly.

@sinbad Thanks. I'll certainly try to continue to document thoroughly.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Mon Jun 16, 2008 5:03 am

Hi I realised somewhat late about a LOD problem I had which couldn't easily be fixed at the time. Now with some breaking changes in action it might be a good time to address it. Sinbad thought it was worth considering so I repost it here. If it could somehow work without too much disruption to your project I think it would help.
Here's the post

"I noticed when I implemented my test for lipspm (non self shadowing) that the shadow was super low detail. Then I realised it was a lower lod and the light itself was rendering it's own view, which is also using it's own distance to determine the lod level.
I know I could set the lod bias probably but that seems inefficient as it would be rendering stuff at a high lod when it wouldn't need to.
Would it be better to have an option to use the lod info in the viewport active camera for the light depth shadow render? This would also save the distance calculations that are being wasted in the light."
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Mon Jun 16, 2008 5:25 am

Adding functionality to allow lod to be computed from the perspective of a different camera would be a pretty big task, but I think this particular problem might be solved by simply using the pixel count approximation strategy. Forgive me if I'm mistaken, but when the camera is far away in shadow mapping, the FOV will be small (otherwise you wouldn't have good resolution anyway). If this is the case (again, correct me if I'm completely wrong) the pixel count approximation strategy should solve the problem as it takes FOV into account. While this strategy hasn't been implemented yet, if I remain on schedule it should be available for testing in about 3 weeks.

While I agree the ability to change the camera with respect to which the LOD is computed would be useful, I'm a bit hesitant to start piling more functionality onto this project before the core features are completed.
0 x

User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic » Mon Jun 16, 2008 6:06 am

Relying on the pixel-count method might actually be better, in a way, compared to calculating LOD from the main camera; If a light/shadow configuration causes an object to cast only a small clump of shadow texels, it makes sense to render that object at a lower LOD because any extra detail will most likely be lost anyways.
0 x

User avatar
Kencho
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 4011
Joined: Fri Sep 19, 2003 6:28 pm
Location: Burgos, Spain
x 1
Contact:

Post by Kencho » Mon Jun 16, 2008 8:28 am

The problem I see there happens when the hi-res model has "concave" edges. Lower resolution versions might remove those vertices/concavity, and then shadows would appear where they shouldn't be.
0 x
Image

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Mon Jun 16, 2008 4:09 pm

that might be a problem with selfshadowing as the depth calculations need to match the cameras depth calcs exactly. If they are using 2 different lod levels then I imagine it will look bad.
Also the need to recalculate the lod algorithm from the lights view seems a waste, but as you say the light will have a tight fov so it's probably not a big deal.
The tight fov and pixel count approx probably would make it look ok most of the time as it would probably be using the highest lod level anyway, unlike the current distance based one which doesn't work well at all. But still, it sounds like a problem worth solving down the track.
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Mon Jun 16, 2008 10:30 pm

I hadn't though about concave edges or self-shadowing. The new strategy wouldn't fix those problems, but it might be possible to write a strategy which would do exactly as you suggested, calculating lod relative to the view camera instead of the light. Nevertheless, it would probably be advantageous to have this functionality built-in. That said, from what I've seen, it would be a big task, and I don't feel I can really commit to adding that functionality until the project, as originally proposed, is completed. Towards that end, however, I've now finished up static geometry and will be starting on the XML converter next.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Tue Jun 17, 2008 10:14 am

LostEra wrote:I hadn't though about concave edges or self-shadowing. The new strategy wouldn't fix those problems, but it might be possible to write a strategy which would do exactly as you suggested, calculating lod relative to the view camera instead of the light. Nevertheless, it would probably be advantageous to have this functionality built-in. That said, from what I've seen, it would be a big task, and I don't feel I can really commit to adding that functionality until the project, as originally proposed, is completed. Towards that end, however, I've now finished up static geometry and will be starting on the XML converter next.
that's cool. Just keep it in mind if a decision could go either way to ease later implementation
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Thu Jun 19, 2008 6:56 am

I will certainly try to avoid writing code that would preclude the addition of such a feature. As I said before, I don't feel I can commit to it at the moment, but I do mention it at the bottom of the wiki page. I've also poked around a bit to make a first pass at determining what changes would probably need to be made and listed them briefly along with the description of the feature. If anyone were interested in implementing this now, it might be worthwhile to check that list.

On another note, I've got some more code up. These changes consist of minor additions to the lod strategy functionality and a first go at the xml converter (but this needs more thorough testing).
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Tue Jul 01, 2008 5:04 am

Last week was pretty quiet as I was scheduled to work on cleaning up, but this week I finally got to implement the pixel count approximation strategy, and that code is up for anyone who wants to try it out.
0 x

Lioric
Google Summer of Code Mentor
Google Summer of Code Mentor
Posts: 295
Joined: Fri Aug 06, 2004 10:25 pm

Post by Lioric » Tue Jul 01, 2008 11:24 pm

That is great, excellent work

Using the approximate screen area of the bounding sphere (a long time desired feature for the lod system) of the objects will improve the performance of the scenes as it is based on the screen size and not in the camera distance

A question, why have you changed the distance (and pixel count) strategy to be singletons?

The factory pattern should be used at all times over the singleton pattern, only use the singleton when the case is justified

The LodStrategyManager::getStrategy() method was well suited, is there any reason for the change?

About this, it should be good to define a default strategy, in case the user dont manually define a strategy, the getStrategy("default") will return whatever strategy is the system default, in the current case will be the "distance"(or the strategy the user has registered as the default)
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Wed Jul 02, 2008 8:42 pm

I changed them to singletons for a few reasons. The first reasons is that, by design, there should only be one instance of each, indicating the use of a singleton to enforce this constraint. The second reason was to avoid the lookup by string for each mesh that was constructed (although, your suggestion of a default strategy is a much better solution to this problem). The third reason is that the distance lod strategy will have additional configuration associated with it as the last part of my project, and it would be more convenient for the user to access it via a singleton than a lookup and a cast (however, here, only the distance strategy would need to be be a singleton).

The singletons are not meant to replace the strategy manager, only to supplement it.

Thanks for the suggestions, and please let me know if my reasoning is sound or if I still need to reconsider the use of singletons.

I'm going to go implement the default strategy feature now. :D
0 x

Lioric
Google Summer of Code Mentor
Google Summer of Code Mentor
Posts: 295
Joined: Fri Aug 06, 2004 10:25 pm

Post by Lioric » Thu Jul 03, 2008 5:03 pm

Yes, if there is the need for a Signleton, then it is justified, lets see how that fits in the project when you implement the next part (with the additional distance strategy configuration), you can always Refactor later if needed

Good job!
0 x

LostEra
Google Summer of Code Student
Google Summer of Code Student
Posts: 56
Joined: Wed Jun 07, 2006 8:33 pm

Post by LostEra » Sat Jul 12, 2008 8:36 pm

I hadn't posted any new code since I added the default strategy last week. There was a reason for this. This week was scheduled for integration (particularly with the automatic lod generation), but everything already worked together nicely. Instead I took this time to go ahead and implement reference view functionality for the distance lod strategy. This will allow meshes and materials using the distance lod strategy to take into account viewport size and fov. This is done by setting a "reference view" upon which the distances were based. When using exactly that view, nothing will change, but if the viewport or fov are different, the distances at which the lod changes will be biased accordingly. I implemented this now to help evaluate the decision to make the strategies singletons.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Sun Jul 13, 2008 5:17 am

LostEra wrote:I hadn't posted any new code since I added the default strategy last week. There was a reason for this. This week was scheduled for integration (particularly with the automatic lod generation), but everything already worked together nicely. Instead I took this time to go ahead and implement reference view functionality for the distance lod strategy. This will allow meshes and materials using the distance lod strategy to take into account viewport size and fov. This is done by setting a "reference view" upon which the distances were based. When using exactly that view, nothing will change, but if the viewport or fov are different, the distances at which the lod changes will be biased accordingly. I implemented this now to help evaluate the decision to make the strategies singletons.
I kind of thought that using screen space for object lod decisions took care of viewport zoom and fov issues? As a small viewport for eg a mirror the objects would be small, hence lower lod
0 x

Post Reply