RenderBin optimization

[Qudus]

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

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 ;).

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

Marvin

[eMKa]

@Marvin Fröhlich

I’ve also run the Bleeding_BlendingTest and it works ;D. The upper place stays transparent all the time. Maybe this problem is solved by accident, because I have no idea why it is solved

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

[Qudus]

@Amos Wenger

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.

[eMKa]

@Marvin Fröhlich

@Amos Wenger

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 ( ;D ) renanse fixed the whole transparency problems : the render bins were wrongly ordered… Or I am totally wrong ?

[Qudus]

@Amos Wenger

No ( ;D ) 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.

[bohdan]

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 ;). 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!!! ;D ;D ;D

Bohdan.

[Qudus]

@bohdan

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 :).

Yes, that was my fault. Sorry :-[.

@bohdan

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!!! ;D ;D ;D

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

[bohdan]

@Marvin Fröhlich

@bohdan

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!!! ;D ;D ;D

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!

@Marvin Fröhlich

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 :-[

Bohdan.

Edit: I said: “QuickSort was not properly sorting transparencies from back-to-front!!!”
I really meant to say: “QuickSort was not properly sorting!!!”

[Qudus]

@bohdan

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.

@bohdan

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

You’re welcome :).

Marvin

[bohdan]

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

[Qudus]

@bohdan

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

Good to know ;D But… what do you mean by this:

@bohdan

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?

[bohdan]

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

from:

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

to:

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… ??? but there is something strange happening as well here, that I can’t explaine… Give me little while, just want to make sure…

[bohdan]

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

[Qudus]

@bohdan

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

No. I left the comparators unchanged. Why?

[bohdan]

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…

[Qudus]

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.

[bohdan]

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…

[Qudus]

Whaah. It isn’t working anymore (I didn’t swap the planes so far) :o. Only if I disable the sorting. Hmm… Maybe the clue really is in the comparators. >:(

[bohdan]

@Marvin Fröhlich

Whaah. It isn’t working anymore (I didn’t swap the planes so far) :o. Only if I disable the sorting. Hmm… Maybe the clue really is in the comparators. >:(

It’s a pitty… :’( :’(

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…

[Qudus]

I’m near to complete with the optimizations. We should be up to par with Java3D now ;D.

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