Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (562)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2
  ignore  |  Print  
  RenderBin optimization  (Read 7337 times)
0 Members and 1 Guest are viewing this topic.
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Posted 2006-10-04 02:08:07 »

So far I can only give you a littel interim report Sad.

There're some things able to be further optimized and some changes I'm not currently being notified of when they change. And dor some strange reason, all shapes disappear in the Q3 level, when I move the mouse. But the CameraFlight works and I got a 22% boost, which is not too bad, but I really expected more. Well... maybe I find more things to optimize tomorrow Wink.

I've also run the Bleeding_BlendingTest and it works Grin. The upper place stays transparent all the time. Maybe this problem is solved by accident, because I have no idea why it is solved Wink. I'll commit my changes, when everything works fine again.

Marvin
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #1 - Posted 2006-10-04 14:49:02 »

I've also run the Bleeding_BlendingTest and it works Grin. The upper place stays transparent all the time. Maybe this problem is solved by accident, because I have no idea why it is solved Wink
I do have an idea why it is solved : renanse fixed transparency a few days ago, don't remember ?

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #2 - Posted 2006-10-04 17:54:37 »

I do have an idea why it is solved : renanse fixed transparency a few days ago, don't remember ?

No renanse fixed the Q3 flames transparency problem. But this fix didn't touch the Bleeding_BlendingTest transparency problem nor your transparency problem. But is is also fixed now.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #3 - Posted 2006-10-04 18:16:17 »

I do have an idea why it is solved : renanse fixed transparency a few days ago, don't remember ?

No renanse fixed the Q3 flames transparency problem. But this fix didn't touch the Bleeding_BlendingTest transparency problem nor your transparency problem. But is is also fixed now.
No (  Grin ) renanse fixed the whole transparency problems : the render bins were wrongly ordered.. Or I am totally wrong ?

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #4 - Posted 2006-10-04 18:56:46 »

No (  Grin ) renanse fixed the whole transparency problems : the render bins were wrongly ordered.. Or I am totally wrong ?

The Transparent and Opaque Bins where rendered as a whole in the wrong order. But after I applied his patch, I tested the Bleeding test and it wasn't fixed.
Offline bohdan

Junior Member




Java-positive...


« Reply #5 - Posted 2006-10-05 00:15:53 »

I totally agree with Marvin! Transparency problems like one demonstrated in Bleeding_BlendigTest existed at least for a year or even more!!!, I can garantee that.

What about render bins - they were always properly ordered till some very recent changes (I belive when you, Marvin was optimising staff with bins, bins by mistake got swapped), this had happen just back one-two weeks ago. Yes, this totaly destroyed transparencies   Wink. Again I can confirm that too. But when renanse fixed it, things got back to "normal", still with those problem like with Bleeding_BlendingTest happening.

And only now, that BlendingTest start working properly! It was simple test case, and it doesn't meen yet that the the problem is really fixed, but I hope so of course. I will check other problems (of the same nature) I had and see if it is sorted now, if it is - well, Marvin, I don't know how - but you did a miracle somehow!!!  Grin Grin Grin

Bohdan.
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #6 - Posted 2006-10-05 00:26:17 »

What about render bins - they were always properly ordered till some very recent changes (I belive when you, Marvin was optimising staff with bins, bins by mistake got swapped), this had happen just back one-two weeks ago. Yes, this totaly destroyed transparencies  Smiley.

Yes, that was my fault. Sorry Embarrassed.

And only now, that BlendingTest start working properly! It was simple test case, and it doesn't meen yet that the the problem is really fixed, but I hope so of course. I will check other problems (of the same nature) I had and see if it is sorted now, if it is - well, Marvin, I don't know how - but you did a miracle somehow!!!  Grin Grin Grin

Is it actually working? Did you test it? I didn't know if it is working on my current code state, which I haven't committed or on the one already committed. If it is, then I suspect, that the following changes did the trick:
I changed the RenderBin implementation the the way, that the RenderAtoms are not put into an array anymore but are chained like a linked list. This is moch more efficient, if one wants to remove a Node from the list and Nodes can be easily added. Then I had to replace the sorting algorithm (Quicksort added by lilian I think) with a mergesort, which works even faster in worst case (all three cases, bast, average and worst case O(n * log(n)) ), when it's run on linked lists like in our case. qicksort has a worse worst case behaviour. and we're not wasting any memory neither by the sorting algorithm nor by the renderbin itself.

So I suspect the Quicksort did anything wrong, which the mergesort does correctly. Don't know. But I think, this will have solved it.

Marvin
Offline bohdan

Junior Member




Java-positive...


« Reply #7 - Posted 2006-10-05 00:49:00 »

And only now, that BlendingTest start working properly! It was simple test case, and it doesn't meen yet that the the problem is really fixed, but I hope so of course. I will check other problems (of the same nature) I had and see if it is sorted now, if it is - well, Marvin, I don't know how - but you did a miracle somehow!!!  Grin Grin Grin

Is it actually working? Did you test it? I didn't know if it is working on my current code state, which I haven't committed or on the one already committed.
No-no, I didn't tested it yet myself!!! But you said in you first post you did and it worked for you!
 
So I suspect the Quicksort did anything wrong, which the mergesort does correctly. Don't know. But I think, this will have solved it.
I believe you are right. It was more or the less obvious anyhow that the problem is with the sorting the transparencies. And I guess (well, basing on changes you said you did) QuickSort was not properly sorting transparencies from back-to-front!!!! That's it!!!

Thanks Marvin for finding that! I believe many people will confirm that it was long term headacke with the transparancies!!!

@lilian: can you have a look at it and confirm? It was good algorithm, anyhow, and with the little fix it may become needed at some stage again.. It really worth fixing...  Sorry  Embarrassed

Bohdan.

Edit: I said: "QuickSort was not properly sorting transparencies from back-to-front!!!!"
I really meant to say: "QuickSort was not properly sorting!!!!"
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #8 - Posted 2006-10-05 01:01:02 »

No-no, I didn't tested it yet myself!!! But you said in you first post you did and it worked for you!

Could you please test it. I guess I won't get the stuff ready today, which I'm currently working on, so I can't commit.
 
Thanks Marvin for finding that! I believe many people will confirm that it was long term headacke with the transparancies!!!

You're welcome Smiley.

Marvin
Offline bohdan

Junior Member




Java-positive...


« Reply #9 - Posted 2006-10-05 01:07:41 »

I just did a change from one sorting algorism to another as you mention above and - YES!!!  Grin Bleeding_Blending is working for me.. checking now mu other staff....  Wink
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #10 - Posted 2006-10-05 01:11:49 »

I just did a change from one sorting algorism to another as you mention above and - YES!!!  Grin Bleeding_Blending is working for me.. checking now mu other staff....  Wink

Good to know Grin But... what do you mean by this:
I just did a change from one sorting algorism to another

Do you mean, you've just updated your CVS? Or what did you do to switch?
Offline bohdan

Junior Member




Java-positive...


« Reply #11 - Posted 2006-10-05 01:24:20 »

Well.. I uncomment one line and commented another in RenderBin (few occurances)...

from:
1  
2  
//Arrays.sort(buckets,0,curSize, <comparator>);
quickSort(buckets, 0, curSize-1, <comparator>);


to:
1  
2  
Arrays.sort(buckets,0,curSize, <comparator>);
//quickSort(buckets, 0, curSize-1, <comparator>);


(this is from a bit older version of xith)

Well... but I'm sort of tired or stupid or smth..  Huh but there is something strange happening as well here, that I can't explaine... Give me little while, just want to make sure...  Smiley
Offline bohdan

Junior Member




Java-positive...


« Reply #12 - Posted 2006-10-05 01:44:41 »

Marvin, did you make any changes to comparators maybe as well?
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #13 - Posted 2006-10-05 01:52:06 »

Marvin, did you make any changes to comparators maybe as well?

No. I left the comparators unchanged. Why?
Offline bohdan

Junior Member




Java-positive...


« Reply #14 - Posted 2006-10-05 01:55:07 »

It just seems I was wrong before saying that test case worked, I discovered that it is working anyhow since I have set sorting for transparencies NONE when was playing with it (and forget about that)!

So basically, switch from one sorting to another doesn't seem to make a difference (regarding transparencies)... When I switching sorting OFF totaly - yes, that blending test case working, but just because order is correct straight away... In general case it will not work...

What I mean... I most likely was wrong blaming QickSort as for wrong sorting...

I asked about comparator since thay play role in sorting too... hmmmm... strange...
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #15 - Posted 2006-10-05 02:00:22 »

Do you have the current version from CVS now? The one working with mergesort and linked lists? If not please update and try it out.
Offline bohdan

Junior Member




Java-positive...


« Reply #16 - Posted 2006-10-05 02:04:55 »

It says for "sortBackToFront( Point3f point )":

/**
   * Sort the render bin from closest to furthest using bounding shpere center as reference point.
   * @param point
 */"

May be this is the clue?

And another thing BTW, Marvin, in that test that worked for you, can you try swap those botom and top planes as you adding them to scenegraph and see if the test stil works?

Edit:
No I don't have the very recent version, but I will try it, of course. But still would be interesting if you can swap those shapes in the test and confirm that it is still working..

Edit2: me getting recent version now...
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #17 - Posted 2006-10-05 02:15:30 »

Whaah. It isn't working anymore (I didn't swap the planes so far) Shocked. Only if I disable the sorting. Hmm... Maybe the clue really is in the comparators.  Angry
Offline bohdan

Junior Member




Java-positive...


« Reply #18 - Posted 2006-10-05 03:03:30 »

Whaah. It isn't working anymore (I didn't swap the planes so far) Shocked. Only if I disable the sorting. Hmm... Maybe the clue really is in the comparators.  Angry

It's a pitty...  Cry Cry

But anyhow, to move forward. I checked default comparator for sorting transparencies, and yes... it seems to be far from being universal... The idea is, that centers of bounding spheres are taken and just distance is compared to the camera location... that's it.
If you think about this - it will cause just exactly same behaviour as we see in the test..... Top plane would be top till the moment it get far away enough so that bottoms' plane bounding sphere center become actually closer to the camera then the top one.. - which is totaly wrong, of course.
So:
1. top one (BLUE) will be drawn first (instead of to be second) and will be blended with the background.
2. bottom one (GREEN) drawn next and where it is not overlapping top one - is blended with background, but !!! - where it is overlapping top one (onscreen pixels wisely) - will not be drawn at all because it will not pass GL depth test! - so we see still BLUE plane there blended with the background.

That's it. Comparators seems to be pretty simple... to simple maybe...
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #19 - Posted 2006-10-06 16:52:36 »

I'm near to complete with the optimizations. We should be up to par with Java3D now Grin.

But there's one thing driving me crazy. The Appearance is not updated when it's been modified. Could please someone check, if this is the case with the current CVS code? e.g. In the HUD test the Buttons should change the texture, when they're hovered. If they don't then I won't break anything when I commit the current changes and you can benefit from the speed-up.

Marvin
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #20 - Posted 2006-10-06 16:59:12 »

I'm near to complete with the optimizations. We should be up to par with Java3D now Grin.

But there's one thing driving me crazy. The Appearance is not updated when it's been modified. Could please someone check, if this is the case with the current CVS code? e.g. In the HUD test the Buttons should change the texture, when they're hovered. If they don't then I won't break anything when I commit the current changes and you can benefit from the speed-up.
Works correctly here.

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #21 - Posted 2006-10-06 17:03:17 »

Works correctly here.

OK. Thanks. I'll investigate, why it isn't here.
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #22 - Posted 2006-10-06 18:56:38 »

The optimization is done Grin As I said: From my calculations we should be up to par with Java3D now (even if I haven't tested it myself).

The scenegraph is now only refilled when, one sets the dirty flag on the VirtualUniverse object or the Locale or a BranchGroup. Or when a Switch node has changed it's value. The least behaviour can be avoided, too. But this needs some more brainstorming and I don't expect too much from it.

The scenegraph modifiactions are managed by com.xith3d.scenegraph.modifications.ScenegraphModificationsListener respectively com.xith3d.render.ScenegraphModificationsManager. Maybe I forgot to manage anything (being notified of a specific change in the scenegraph) if this is the case. please tell me.

Frustum culling of course needs to be done each frame. I've written a new class called FrustumCuller, which does the job quite efficiently. It makes use of the current frame id, which simply is a number, that is incremented each frame. Only atoms holding this number are rendered. This way the groupwise culling can still be done without clearing the RenderBins.

RenderBin sorting can be an FPS killer. It must not be done too often. I've added a field to the Renderer class called get/setMaxViewDelta(), which is by default 0.1f and which I have set to 1.0f for Q3 test. The view has to move 1.0f in the virtual world until the atoms get resorted (or if anything else has been changed, which needs resorting). 1.0f is a good tradeoff. Play with this value to increase performance.

renanse, could you please use the current version for the webstart thing?

If i forgot to mention anything, I'll tell you when I remember (or just ask).

Enjoy Wink

Marvin
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #23 - Posted 2006-10-07 12:44:17 »

Woohoo ! 23.69151467089611 FPS now ! (which is incredible compared to the previous flights.. I used to run at ~16.8 FPS)

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #24 - Posted 2006-10-07 14:34:02 »

Are link and sharedgroups correctly handled with display lists now ?

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline Marvin Fröhlich

Senior Member




May the 4th, be with you...


« Reply #25 - Posted 2006-10-07 14:42:28 »

Are link and sharedgroups correctly handled with display lists now ?

Will do it this evening.
Offline Amos Wenger

Senior Member




Everything's possible, but not everything's fun...


« Reply #26 - Posted 2006-10-07 15:00:04 »

Are link and sharedgroups correctly handled with display lists now ?

Will do it this evening.
OK, so I don't use them for now in my game.

"Once you start working on something, don't be afraid of failure and don't abandon it. People who work sincerely are the happiest"
Offline renanse

Junior Member




Intelligence is light to a dark world.


« Reply #27 - Posted 2006-10-07 22:38:50 »

renanse, could you please use the current version for the webstart thing?

Sure, I'll plan to go forward with this then soon here.

Renanse  (ruh-NON-say)
Offline renanse

Junior Member




Intelligence is light to a dark world.


« Reply #28 - Posted 2006-10-08 02:30:04 »

Hmm, after updating xith3d and xith-tk, the geometry of the quake level is a bit odd.  It looks like the indices are messed up in some places or something, especially over the doorways.  Anyone else see that?

Renanse  (ruh-NON-say)
Offline kevglass

JGO Kernel


Medals: 164
Projects: 23
Exp: 18 years


Coder, Trainee Pixel Artist, Game Reviewer


« Reply #29 - Posted 2006-10-08 02:33:04 »

Got a screenshot?

Kev

Pages: [1] 2
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

BurntPizza (28 views)
2014-09-21 02:42:18

BurntPizza (18 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (27 views)
2014-09-20 20:14:06

BurntPizza (29 views)
2014-09-19 03:14:18

Dwinin (46 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (101 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56

mitcheeb (71 views)
2014-09-08 06:06:29
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!