[submitted] Scene manager

Threads related to Google Summer of Code
Post Reply
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
Contact:

Post by jacmoe » Wed Sep 13, 2006 5:54 pm

Lee04 and others:
I am sick and tired of you spamming this topic with totally unrelated posts.
Let's give this topic back to Farakon and his Master SM.
0 x
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.

User avatar
volca
Gnome
Posts: 393
Joined: Thu Dec 08, 2005 9:57 pm
Contact:

Post by volca » Fri Sep 15, 2006 2:37 pm

@farakon: How do you stop the MovableObjects to be queued twice if they intersect the portal to another cell? I'm trying to implement something like this now.

Out of curiosity:
I read in the specification you'll be doing visibility test based on the frustum culling (portal frusta?). I was trying to do portal frustum culling too.
Will you do some kind of frustum unions for multiple portals between any two cells? I had a recursive traversal function, which created the frustum from clipped portal edges and camera position, and it was too slow, as the maps I use are unoptimised. I'm now doing screen space bounding rectagle tests for portal visibility, which allows me to easily union the screen rectangles, and thanks to this, lowers the number of needed iterations (I can't imagine doing something like this with frustum planes). Just asking because I could have missed some optimisation tricks...

Sorry if this was already discussed here.

I hope you're project goes well and wish you luck!

Thanks
Volca
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Mon Sep 18, 2006 7:25 pm

Sorry for the long delay, I m not dead, at least not yet ;) It was a busy week, and I m affraid it's going to be like this for the next couple of days.

@detox: I never played city of heroes and most of screenshots I v seen r exterior shots. The BSP tree structure was used to reduce as much the error of camera location. With BSP, as long as you are inside, u know in which cell u r, and what's around u.

@volca: For movable objects, I m using a flag/token, once the movable is queued u tag it, this way u r sure that no object is rendered twice. I m now trying to do that on scene managers to allow multiple cells to have same scene manager.
About the frustum culling, I do have an idea on how to do it, but I m still digging inside Ogre API to do it correctly. The idea is to compute the bounding box of a portal after projection and construct the frustum afterward. I m not sure if that's what u did.
Another thing that I m trying to figure out is how to do scissoring in Ogre when u have multiple scene managers, I wonder whether we should create something like a scissor queue command so we can do that on each scene manager! because when u use scissoring, u gain some noticable performance as ur culling pixels.
0 x

User avatar
volca
Gnome
Posts: 393
Joined: Thu Dec 08, 2005 9:57 pm
Contact:

Post by volca » Wed Sep 20, 2006 7:59 am

That is the method I'd like to use too - basicaly just marking the MovableObjects with the frame number.

About the frustum culling. Are you then computing the portal visiblity in the screen space? From my experience, when doing the naive world space culling using a recursive function, the iteration count grows geometricaly. The main cause is a situation in which some portal (A) is seen through N portals. You end up testing all the portals behind the A for N times. This is bad.
When doing this in screen space, you only merge the visible rectangles together (union them), and traverse the portals behind B once using the unioned rectangle. Another good thing about this is that you get scissor rectangle for free. (Well it is slightly more complicated, if you want, look at the traversePortals method here:
http://opde.cvs.sourceforge.net/opde/op ... iew=markup )

I guess this is ok for up to 50 portals visible, but I have situations where there are ~300 (The portal testing function was called ~10000 times, leaving FPS at 0.5). Now I have minimally 40FPS. This is because the portals are placed automatically after CSG is processed.

Sorry for writing so long reaction. So I was just curious how you handle this kind of situation.
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Thu Sep 21, 2006 3:20 am

I didn't compute it yet, but yes, that's what I want to do, project the portal and compute bounding box, then it's going to be rectangle union/substraction to get visibility. It should be pretty much faster than frustum portals.

I didn't have the chance to look at the source code of your engine, but judging from the screenshots, looks pretty impressive :)
I assume you are doing the CSG of convex objects, how do u construct ur level, I couldn't find information about it on the project wiki.

Having 50 portals visible is quite alot! How many portals are there in a level? r u sure u need as much?
0 x

User avatar
volca
Gnome
Posts: 393
Joined: Thu Dec 08, 2005 9:57 pm
Contact:

Post by volca » Thu Sep 21, 2006 9:00 am

As I load the maps generated by dromed (Thief1/Thief2), I do not have a chance to lower the portal counts - the levels are in binary, proprietary form.

The CSG splits the geometry to convex only pieces. This causes a huge number of portals to be generated (If I remember correctly, there can be around 3000-4000 per level). 200-300 Is the number of visible portals in one frame (maximum I encountered, normally ~20-100). The current algorithm is still bit unoptimized, but it does handle those counts quite well.
I didn't have the chance to look at the source code of your engine, but judging from the screenshots, looks pretty impressive :)
Thanks! There are more screenshots in the showcase here. The sceneManager is just a tool for me, so I hope to replace it with yours if possible (I want to concentrate on other things).

I can explain the algorithm if you would like.
0 x

Ajare
Goblin
Posts: 282
Joined: Sat May 14, 2005 9:20 pm

Post by Ajare » Thu Sep 21, 2006 6:47 pm

volca wrote: The CSG splits the geometry to convex only pieces. This causes a huge number of portals to be generated (If I remember correctly, there can be around 3000-4000 per level).
4000! I always thought that Dromed was pretty clever to automatically portalise maps (something that Sinbad started with World Minion), but now I'm not so sure.
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Sat Sep 23, 2006 7:15 pm

Hmm 4000 is far too much, can't u precompute visibility of portals? that would lead to less time in real time processing.
0 x

User avatar
volca
Gnome
Posts: 393
Joined: Thu Dec 08, 2005 9:57 pm
Contact:

Post by volca » Sun Sep 24, 2006 7:13 pm

This is what I do not want to do, actually. I'd like to load the original data without any conversion/preprocessing. The portal counts are even greater than I thought. can be as high as 30000 per level :shock: . There is some optimizer in the Dromed, but I guess the original missions were already optimized.

I do not want to mess your thread with my project, sorry if I did too much postings.
0 x

Zemedelec
Gnoblar
Posts: 1
Joined: Mon Oct 16, 2006 11:02 am

Post by Zemedelec » Mon Oct 16, 2006 11:06 am

So, this implementation is tied with the HW occlusions?
Did you tried to test the portals on CPU (ignoring the occlusion from concave sectors)? It should be trivial to write and can be fast.
Especially for hardware that don't support hw occlusion queries.
0 x

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

Post by Wolfmanfx » Fri Oct 20, 2006 11:59 pm

@farakon
Are u still on it or is it left as it current state?
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Sat Oct 21, 2006 5:10 pm

Wolfmanfx: I m still on it, but since the school begun, I have a lot of work to do on my PhD thesis (or as I call it: mental torture :cry:) and don't have any free time. I m committed to this project, and I hope I ll finish the current PhD work soon and return to work on the HPBSP on my free time. Of course if someone is willing to contribute, feel free to PM me :)
0 x

User avatar
Praetor
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3335
Joined: Tue Jun 21, 2005 8:26 pm
Location: Rochester, New York, US
Contact:

Post by Praetor » Sat Oct 21, 2006 6:26 pm

[SARC]Only a PhD thesis? What a small distraction....

Good luck with that farakon. I think this project is very promising so far.
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Tue Oct 24, 2006 12:31 pm

I ran into a problem in my PhD, I thought it would take me a week to solve it, this week turned out to be more than a month and still not solved! If I only knew that it could be as such of a mental torture....
0 x

Ajare
Goblin
Posts: 282
Joined: Sat May 14, 2005 9:20 pm

Post by Ajare » Tue Oct 24, 2006 12:52 pm

No worries, I did my dissertation on computational geometry, and that happened several times!

I've actually been looking into a way to automate the creation of the low-res bounding mesh. If it seems practical I may pursue it, but I'll say no more at the moment.
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Sun Oct 29, 2006 7:39 pm

Indeed, mine is also in computational geometry, but a more theoritical topic. Proofs take all the time, some time 10x more time than the implementation :(
0 x

Chaster
OGRE Expert User
OGRE Expert User
Posts: 557
Joined: Wed May 05, 2004 3:19 pm
Location: Portland, OR, USA
Contact:

Post by Chaster » Sat Nov 04, 2006 8:06 pm

Volca & Farakon,

Just curious - you both plan to (or are) using the 2d rectangular union method - does your implementation take into account non-aligned rectangles? (I mean rectangles that are at an angle compared to the viewing frustum)?. Just curious... (I've seen several implementations of rectangle union method which do not account for this scenario, only when the rectangles are oriented in the same major axis as the camera frustum, which makes the rectangle unions trivial and fairly non-conservative).

Also, I'm a bit out of synch here - is there anywhere to see the code for the Master Scenemanager yet? (trolled through this entire thread but must have missed the post if there was one..)

Chaster
0 x

User avatar
farakon
Google Summer of Code Student
Google Summer of Code Student
Posts: 66
Joined: Sat May 13, 2006 6:47 am

Post by farakon » Sun Nov 05, 2006 12:47 pm

@Chaster: what do you mean by non aligned rectangle? The bounding rectangle of the portal is computed in camera space. This eliminates alot of complexity such as line/line intersection. The code is already on sourceforge. Last time I checked, the ogre team hasn't decided where to include the code (ogre addons/plugin...), maybe they are waiting me to make a final release, but given my current (research) situation it'll have to be in few weeks! :(
0 x

User avatar
volca
Gnome
Posts: 393
Joined: Thu Dec 08, 2005 9:57 pm
Contact:

Post by volca » Mon Nov 06, 2006 1:33 pm

@Chaster: Not by me. This would cause too much trouble. If non aligned, you'd have to compute the union/intersection using polygon math, and then the simplicity of using screen axis aligned rectangles goes away.

Why would you want to do this? It would only be worth for huge levels with small number of portals, where adding a certain part of level geometry would cause a big FPS drop, so computing more accurately would be useful (but then it would be even better to work with projected portals themselves, not their bounding rects).
0 x

Chaster
OGRE Expert User
OGRE Expert User
Posts: 557
Joined: Wed May 05, 2004 3:19 pm
Location: Portland, OR, USA
Contact:

Post by Chaster » Thu Nov 09, 2006 10:56 am

Ah, I see. I was misreading how you implemented.

Chaster
farakon wrote:@Chaster: what do you mean by non aligned rectangle? The bounding rectangle of the portal is computed in camera space. This eliminates alot of complexity such as line/line intersection. The code is already on sourceforge. Last time I checked, the ogre team hasn't decided where to include the code (ogre addons/plugin...), maybe they are waiting me to make a final release, but given my current (research) situation it'll have to be in few weeks! :(
0 x

Chaster
OGRE Expert User
OGRE Expert User
Posts: 557
Joined: Wed May 05, 2004 3:19 pm
Location: Portland, OR, USA
Contact:

Post by Chaster » Thu Nov 09, 2006 10:59 am

volca wrote:@Chaster: Not by me. This would cause too much trouble. If non aligned, you'd have to compute the union/intersection using polygon math, and then the simplicity of using screen axis aligned rectangles goes away.

Why would you want to do this? It would only be worth for huge levels with small number of portals, where adding a certain part of level geometry would cause a big FPS drop, so computing more accurately would be useful (but then it would be even better to work with projected portals themselves, not their bounding rects).
I didn't say I wanted to do this - I was just curious. I agree - the overhead is substantial, and frankly, I have always found that doing the clipping in 3D worked better for my projects - but those projects used hand-designed portal/cells for the levels, and never had more than a dozen portals in view at any time...

Anyway, I'm looking forward to seeing the Master SceneManager work in all it's glory!

Chaster
0 x

tgraupmann
Gnoll
Posts: 696
Joined: Sun Feb 20, 2005 5:28 am
Contact:

Post by tgraupmann » Thu Nov 16, 2006 5:15 pm

One feature that is needed by the scene manager is to create a "super frustum".
http://www.gamedev.net/reference/progra ... erfrustum/

The task (should you accept it) is to cache part of the SceneManager to disk based on an LOD clipping range. Since the entire Scene for a level doesn't need to stay loaded in memory.

This would alleviate every group from having to implement a super frustum when their projects get big.

You would need to add a new technique property to material scripts for "super-frustum-clipping-range".
0 x

User avatar
jomunoz
Goblin
Posts: 228
Joined: Wed Apr 13, 2005 5:07 pm
Location: Medellin - Colombia

Post by jomunoz » Thu Jan 18, 2007 6:02 pm

Just wanted to know how this is going.
0 x

User avatar
jwatte
Gnome
Posts: 347
Joined: Sat Feb 05, 2005 12:56 am

Post by jwatte » Fri Feb 23, 2007 7:42 am

Bump?
0 x

Post Reply