[GSoC 2012] CHC++

Threads related to Google Summer of Code
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

[GSoC 2012] CHC++

Post by Fritzendugan »

Project Proposal : CHC++ for Ogre

I would like to expand upon efforts done by tuan kuranes (see: http://www.ogre3d.org/forums/viewtopic.php?f=1&t=38383) to implement Coherent Hierarchical Culling and CHC++ techniques into the Ogre engine for GSoC 2012. A description of CHC++ can be found: http://www.cg.tuwien.ac.at/research/pub ... -draft.pdf

Occlusion culling is a useful technique for avoiding the processing of nodes that will be entirely covered up by other opaque nodes in the final scene. With the advent of hardware occlusion queries, and the exploitation of temporal coherence (as in CHC), run-time determination of visibility is becoming feasible. CHC++ expands upon CHC in such a way that introduces a number of significant improvements. These are described in the introduction of the linked article, so I won't describe them here.

How will this project benefit OGRE users?
CHC++ drastically improves upon the time it takes to render scenes that have moderate to high depth complexity. In heavily occluded scenes it excels, but unlike CHC, CHC++ doesn't heavily impact those scenes that don't. Therefore many users will benefit from this application because it can increase the efficiency of their scene renderings.

Is this project within the core scope of OGRE?
With the addition of a few more classes (many well on their way already thanks to the work done by tuan), CHC++ can be implemented into the Ogre engine. It is also possible that later work may be done with further abstraction to make it possible for Occlusion Culling to work with any SceneManager.

This project should be within scope of the time allotted by GSoC. As I have already stated, the foundation for such algorithms already exists thanks to previous contributors. It is just a matter of updating existing code and implementing CHC++ techniques.

Schedule

April 24th – May 21st
  • Get to know my mentor :)
  • Get deeply familiar with tuan's CHC and SpatialTree code
Deliverable: fix any run-time errors with tuan's demo and get everything updated
  • Week 1 (May 21)
    • fix demo
Deliverable: Necessary Queues and their associated classes
  • Week 2 (May 28)
    • work on the invisible and visible queues and the query queue
  • Week 3 (June 4)
    • finish up the queues
Deliverable: 'working' CHC++ (runs, but may not be optimal)
  • Week 4 (June 11)
    • begin making necessary changes to integrate the various new queues
  • Week 5 (June 18)
    • work on multiqueries to reduce number of queries
  • Week 6 (June 25)
    • continue work on multiqueries
    • implement estimations for coherence of visibility
  • Week 7 (July 2)
    • finish multiqueries and estimations if not already finished
    • work on "temporal jittering" for testing of previously visible nodes
  • Week 8 (July 9)
    • finish work on the pieces
    • finish up 'working' CHC++
Deliverable: optimized CHC++ and work on documentation
  • Week 9-15 (July 16)
    • work on optimizing CHC++ code
    • work on documentation
I'm not entirely sure how to break down the last deliverable. I could set dates for documentation of specific classes?

I think that thoroughly documenting mine as well as the existing code is an important and helpful step for further work on this code, and I would like to be able to spend some time toward the end on doing this.

My last day of finals is on friday May 12th, but I may be taking some summer classes. Summer classes tend to be much less demanding than traditional classes, not to mention I will only be taking one or two. This should not require much of my time, which will allow me to focus almost entirely on this project this summer with little distractions. There should be no scheduling issues.

Why You're The Person For This Project

I'm a 21 year old full-time student pursuing a bachelor's degree in computer science from the United States. I'm an enthusiastic problem solver and I love to code. Although much of my programming has been done in Java, I've also been coding in C++ for about 4 years. I've done some graphics programming with OpenGL (see below) and have recently been getting into GLSL. Although my experience or portfolio may not be massive, I love to learn and I pick things up quickly.

http://fritzendugan.com/ctc_competition/index.html -- A (somewhat basic) 3d game engine I created from scratch and worked on for about two weeks. It uses LWJGL for OpenGL bindings and some Slick2D-Util stuff for sound. Some of the more interesting things I was working on were a skeletal animation system and texture-packing/atlasing.

http://www.fritzendugan.com/ -- A holding place for many of the projects I've worked on. Although much of the work is incomplete, I think it reflects many of my interests.

Why OGRE?

I have always been interested in 3d graphics since I first played StarFox 64 on the Nintendo 64. Since then I've taken every opportunity I've gotten to learn and experiment with 3d graphics. Ogre seems very powerful and yet focused in scope--two characteristics I value in an engine. I think contributing to such a project would be an incredible opportunity. Also I've recently begun working with the NeoAxis open-source game engine which uses Ogre for 3d rendering, so this would be a good opportunity to learn about some of the back-end.

Anything Else

Ogre appears to have a very friendly community and I've already gotten lots of help from the forums and the irc channel. I would be somewhat honored to take part in such a community.

Thanks for reading this proposal. Any comments or guidance would be greatly appreciated.
Last edited by Fritzendugan on Mon Mar 26, 2012 3:55 am, edited 5 times in total.
User avatar
Wolfmanfx
OGRE Team Member
OGRE Team Member
Posts: 1525
Joined: Fri Feb 03, 2006 10:37 pm
Location: Austria - Leoben
x 99

Re: Genetic Algorithm to efficiently sort render queues

Post by Wolfmanfx »

Hi,

So atm there is no automatic way which does occlusion culling (using hardware occlusion queries or a software render based z-buffer) so first CHC++ must be implemented (here the paper http://www.cg.tuwien.ac.at/research/pub ... -2008-CHC/).

Also what you propose is to reduce render state changes (removing redundant render states). But i think just implementing a sorting algo. is not enough (but that is just my opinion).

cheers
User avatar
aguru
Goblin
Posts: 236
Joined: Tue Feb 26, 2008 5:48 pm
x 3

Re: Genetic Algorithm to efficiently sort render queues

Post by aguru »

Does not current mobile video hardware try and reject all hidden surfaces anyway? I understand PowerVR works so well because the entire design is aimed at keeping overdraw low on a hardware level?
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

Re: Genetic Algorithm to efficiently sort render queues

Post by Fritzendugan »

Thanks for the quick replies!

@Wolfmanfx, What I was looking at is idea #15 on http://www.ogre3d.org/tikiwiki/GSoC+Pro ... evelopment but after reading the article you provided it almost seems like the more interesting proposal would involve trying to implement CHC++ into Ogre.
User avatar
Wolfmanfx
OGRE Team Member
OGRE Team Member
Posts: 1525
Joined: Fri Feb 03, 2006 10:37 pm
Location: Austria - Leoben
x 99

Re: Genetic Algorithm to efficiently sort render queues

Post by Wolfmanfx »

@aguru
What you mean is tile based deferred rendering (TBDR). This technique is very powerful but is only supported on PowerVR(SGX) hardware tegra tablets do not have this (i think because this technique is patented). CHC++ do not submit the primitives to the renderer and saves time. Of course HOQ are not supported on iOS atm.
User avatar
masterfalcon
OGRE Team Member
OGRE Team Member
Posts: 4270
Joined: Sun Feb 25, 2007 4:56 am
Location: Bloomington, MN
x 126

Re: Genetic Algorithm to efficiently sort render queues

Post by masterfalcon »

User avatar
Wolfmanfx
OGRE Team Member
OGRE Team Member
Posts: 1525
Joined: Fri Feb 03, 2006 10:37 pm
Location: Austria - Leoben
x 99

Re: Genetic Algorithm to efficiently sort render queues

Post by Wolfmanfx »

@masterfalcon
Are HOQ are supported by your render systems? I mean thats great so would also mobile devices benefit from CHC++!
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

Re: Genetic Algorithm to efficiently sort render queues

Post by Fritzendugan »

If I were to pursue this as a project proposal, I think my focus would be on implementing CHC++ in a desktop environment, although a future extension of the project to implement it on mobile platforms would probably be a straightforward and logical next step in the future. It seems that implementing CHC++ is a task in and of itself and further complicating it by entering the mobile development sphere is too much for 15 weeks. However, if I do end up pursuing this and being accepted, I would gladly continue work after GSoC to port it to OpenGL ES :)

I will try and get a first draft of the proposal finished by the end of this week if you guys think this is a valid project avenue to explore
User avatar
Wolfmanfx
OGRE Team Member
OGRE Team Member
Posts: 1525
Joined: Fri Feb 03, 2006 10:37 pm
Location: Austria - Leoben
x 99

Re: Genetic Algorithm to efficiently sort render queues

Post by Wolfmanfx »

So here something to read

http://www.ogre3d.org/forums/viewtopic.php?f=4&t=53817

Last year GSOC draft
http://www.ogre3d.org/forums/viewtopic.php?f=13&t=63022

Contact Praetor to get the resources like the demo from the original authors.

Look at tuans impl as a starting point

http://www.ogre3d.org/forums/viewtopic.php?t=38383

I think this is really a heavy topic but its doable - would be great if tuan could mentor you.

Change the title of the topic to GSOC12: CHC++
User avatar
masterfalcon
OGRE Team Member
OGRE Team Member
Posts: 4270
Joined: Sun Feb 25, 2007 4:56 am
Location: Bloomington, MN
x 126

Re: Genetic Algorithm to efficiently sort render queues

Post by masterfalcon »

@wolfmanfx Yeah, the 1.8 branch has had support for that extension since iOS 5 was publicly released.
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

Re: [GSoC 2012] CHC++

Post by Fritzendugan »

I've read http://www.ogre3d.org/forums/viewtopic. ... 3&start=25 and it seems as though they were making some real progress and it looks like a good starting point. I will try and get their demo code running tonight and start delving into their code. I'm sure I'll have a better understanding of where that code is once I do so.

While browsing through some of the other threads in the forum I noticed there was talk of having to make heavy modifications to the RenderQueue and SceneManager and possibly a need to multi-thread the engine (it's my understanding that OGRE doesn't currently support multi-threading). Is this something that would be involved in such a GSoC project? I'm just trying to wrap my head around the scope of this proposal. So far it seems like something that would be an interesting challenge, but doable.
User avatar
Wolfmanfx
OGRE Team Member
OGRE Team Member
Posts: 1525
Joined: Fri Feb 03, 2006 10:37 pm
Location: Austria - Leoben
x 99

Re: [GSoC 2012] CHC++

Post by Wolfmanfx »

You should focus on CHC++ and i think you will have to change some interfaces here and there but multithreading is out of scope (its a own topic for gsoc).
Yeah i also think getting the demo run think a little bit where you want to start and what do you want to deliver.

And nobody atm is doing any heavy interface changes this changes were planned by steve (founder-retired).
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

Re: [GSoC 2012] CHC++

Post by Fritzendugan »

Yeah, I assumed multi-threading would be out of scope that's why I was a little worried. Glad to hear I don't have to worry about that.

Ok, focusing on CHC++ sounds great. I will start messing with their demo tonight.
PhilipLB
Google Summer of Code Student
Google Summer of Code Student
Posts: 550
Joined: Thu Jun 04, 2009 5:07 pm
Location: Berlin
x 108

Re: [GSoC 2012] CHC++

Post by PhilipLB »

One interesting thing would be: CHC++ draws in some random sorted way. Correct me if I'm wrong, but don't you lose here the benefit of material ordered rendering avoiding state changes?
Google Summer of Code 2012 Student
Topic: "Volume Rendering with LOD aimed at terrain"
Project links: Project thread, WIKI page, Code fork for the project
Mentor: Mattan Furst


Volume GFX, accepting donations.
Fritzendugan
Gnoblar
Posts: 15
Joined: Mon Mar 19, 2012 3:43 pm

Re: [GSoC 2012] CHC++

Post by Fritzendugan »

I'm certainly no expert on this subject (not yet anyway ^^) but I would think if what you're saying is true then perhaps the benefit of occluding so much of the geometry outweighs any loss of benefit of the out-of-order rendering.

I've taken a look at the code and it seems as though tuans has already gotten a lot of the preliminary work out of the way and has a basic framework set up that should be fairly easy to continue work off of. However, I haven't as of yet been able to get his code to compile. I'm not sure if there is something trivial I'm missing or what. I will try and contact Praetor to see if I can get another (perhaps more recent) version of the source. In the meantime, I've posted in the thread where I got the source asking if anyone has any idea what I'm doing wrong http://www.ogre3d.org/forums/viewtopic.php?f=1&t=38383
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: [GSoC 2012] CHC++

Post by bstone »

PhilipLB wrote:One interesting thing would be: CHC++ draws in some random sorted way. Correct me if I'm wrong, but don't you lose here the benefit of material ordered rendering avoiding state changes?
No, that's not the case. CHC++ doesn't draw in a random order. What you refer to is the randomized jitter in the delays for checking the visibility of previously visible nodes. That's the only random part that CHC++ introduced compared to CHC. The idea is to break temporal alignment of visibility queries that is otherwise possible and might result in a noticeable frame drop depending on the scene.

In fact the major advantage of CHC++ over CHC is that it is state change friendly and is much more easier to integrate into Ogre because of that. Namely the occlusion algorithm is doing its work before the engine renders the render queues. The engine can proceed with ordering the queues to minimize the state changes as usual.
PhilipLB
Google Summer of Code Student
Google Summer of Code Student
Posts: 550
Joined: Thu Jun 04, 2009 5:07 pm
Location: Berlin
x 108

Re: [GSoC 2012] CHC++

Post by PhilipLB »

Sorry, my time with CHC is some time ago. :) What I meant by random is, that you draw front-to-back from the camera. And you use the time when something is drawn to fire some HOQ, so it can't take the material into account.
Google Summer of Code 2012 Student
Topic: "Volume Rendering with LOD aimed at terrain"
Project links: Project thread, WIKI page, Code fork for the project
Mentor: Mattan Furst


Volume GFX, accepting donations.
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: [GSoC 2012] CHC++

Post by bstone »

Yeah, I see what you mean now. CHC had this issue no doubt. CHC++ significantly improves over that by batching HO queries so the rendering queue is relatively large when it's time to render things. The engine can order it to minimize state changes per material, etc.
PhilipLB
Google Summer of Code Student
Google Summer of Code Student
Posts: 550
Joined: Thu Jun 04, 2009 5:07 pm
Location: Berlin
x 108

Re: [GSoC 2012] CHC++

Post by PhilipLB »

CHC++ batches? Ok, cool. :) Just knowing CHC because I once tried to implement it in Ogre but failed and came up with something own. :)
It was basically this: Fire HOQs but ignore them the current frame and render the objects anyway. Next frame, check the results and if invisible, don't render them anymore but still fire HOQs and check to make them visible again. This gave a speedup if the scene had a lot of occlusion.
Google Summer of Code 2012 Student
Topic: "Volume Rendering with LOD aimed at terrain"
Project links: Project thread, WIKI page, Code fork for the project
Mentor: Mattan Furst


Volume GFX, accepting donations.
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: [GSoC 2012] CHC++

Post by bstone »

Have a look at the CHC++ paper. I highly recommend it esp. since you made an attempt at implementing CHC. It's just amazing.
User avatar
tuan kuranes
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 2653
Joined: Wed Sep 24, 2003 8:07 am
Location: Haute Garonne, France
x 4

Re: [GSoC 2012] CHC++

Post by tuan kuranes »

CHC++ does indeed give good results, at a very high cost => code complexity. Ogre current code is already hugely complex on that part (scene+batch+multi-rendertarget/shadow pass).
That's why serious refactoring was planned before seriously adding an even more complex render path. (it adds a per camera conservative render list to the puzzle)

So it's a performance over complexity choice for Ogre. (doing render refactor then chc++ would already give very complex code, but doing that in reverse order will possibly give non usable code or umaintanable code)

Nowadays, I would really go for another route on visibility computing, that allows it to be non blocking and out of rendering loop, even multithreaded.
Very good source code and papers with lots of xp since the first CHC paper time :
http://blog.selfshadow.com/publications ... isibility/
http://bouliiii.blogspot.fr/2011/11/ray ... point.html
http://rastergrid.com/blog/2010/10/open ... -released/
http://www.slideshare.net/DICEStudio/cu ... n-practice
http://www.slideshare.net/DICEStudio/fi ... ed-the-run
http://www.slideshare.net/repii/paralle ... 09-1860503
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: [GSoC 2012] CHC++

Post by bstone »

Thanks for the links. Interesting stuff indeed.

I am personally not a big fan of speculative refactoring. Often it results in more issues than it tries to solve due to all the speculations. Refactoring is much more effective when you have working code and you know exactly what you have to do and how. I think having a working CHC++ based scene manager would exactly show how you could generalize/optimize Ogre internals to adapt CHC++ and the likes effectively.
User avatar
tuan kuranes
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 2653
Joined: Wed Sep 24, 2003 8:07 am
Location: Haute Garonne, France
x 4

Re: [GSoC 2012] CHC++

Post by tuan kuranes »

Well, refactoring ogre render pass code is not for its own sake but Ogre 2.0 Tindalos oriented, with its own very goals.

CHC++ would just be a "use-case" of the new architecture, rather than its goal, and would even finish as a plugin or user-side, as it's not useful for all Ogre application, but only heavily occluded dynamic scenes with low fps.
CHC++ is very flexible, very effective and very powerful, but sadly leads to very complex code, no way to escape it.

Architecturing Ogre render passes around CHC would impose them more code complexity, and doesn't seem the good choice as Ogre has to be maintained by very kind and benevolent maintainers, whose time are very precious.

Especially when other solution might do nearly as well, and with hopefully less complexity.
User avatar
tuan kuranes
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 2653
Joined: Wed Sep 24, 2003 8:07 am
Location: Haute Garonne, France
x 4

Re: [GSoC 2012] CHC++

Post by tuan kuranes »

My idea is to craft some type of a genetic algorithm that would try different orderings of the queue and then assign fitness values based upon which ones performed the best, trying to over time approach an optimal solution. If you guys think this is something worth pursuing I will happily do more research and write up a proposal for this project.
@Fritzendugan on CHC++ and "Optimized parameters" you might want to read that thesis on just that http://www.cg.tuwien.ac.at/research/pub ... Thesis.pdf

Make sure to read alsot the last paper on original author, with generalized use of chc (shadow caster culling using chc) http://www.cg.tuwien.ac.at/research/pub ... -paper.pdf and that includes further chc++ optimizations in it.
bstone
OGRE Expert User
OGRE Expert User
Posts: 1920
Joined: Sun Feb 19, 2012 9:24 pm
Location: Russia
x 201

Re: [GSoC 2012] CHC++

Post by bstone »

I see your point, but Ogre 2.0 is yet to come while CHC++-based scene manager would benefit multiple projects already. Furthermore, I didn't mean building Ogre 2.0 around CHC++ but accounting for the required scene manager <-> render system interactions required by CHC++ or Hierarchical Z-Buffering, or anything similar for that matter. Ideally CHC++ would be just another scene manager plugin at first, but later I would consider introducing a separate abstraction for culling into Ogre. It would be awesome to have VFC, CHC++, and HZB as separate implementations that could be used depending on the scene specifics. I admit that this might not be very straightforward, but I bet that having a cross-platform 3d engine with such a high level of abstraction as Ogre is now wasn't very straightforward back then when it started :D