Fast Clipping [SOLUTION]

[maverick_pol]

Hi guys,

I have been asking a lot of questions about clipping and in Qt 4.4 it works bad.
I couldn't find a way to optimize the clipping until now.
The weak part in Qt clipping is, in my opinion, the algorithm.
I haven't checked the algorithm that Qt developers have implemented, but after implementing another algorithm clipping works about 10 times faster( at least in my application).

The algorithm I am using is:

Sutherland and Hodgman's polygon-clipping algorithm

[IMPORTANT]
To speed up clipping even more I have improved the algorithm a bit to work faster in my use case; so I recommend everyone doing the same in their apps.



Hope that it helps.

Kacper

[fullmetalcoder]

what kind of widget rendering actually require a modified clipping to get good performance
how did you add custom clipping if you did not modify Qt internals (and so have a look at them)
where can your implementation be found (why would you recommend using it if you do not provide it)
under which license would you release this code
have you considered reporting this to Trolltech? Qt 4.5 has a big focus on performances so if they haven't improved clipping and your implementation is o much faster they'll probably be pleased to hear about it.

[maverick_pol]

1. When you have lot of polygons inside a small area, let's say that I had to zoom into 100 times to see the polygons which points differ by 1e-10. When Qt tried to clip te polygons when zoom more I had to wait about 8 to 10 sec to see the clipped area. I was drawng the polygons (QPainterPath) in the graphicsscene background.
2. I used my clipping algorithm before Qt clipping.
3.
where can your implementation be found (why would you recommend using it if you do not provide it)

Using the algorithm in the previous post is faster when only using Qt clipping.
You have the algorithm name and the implemntation can be found in many places.
If still that this topic is useless to you stop reading it.
4. I have reported the topic many times to Trolltech I only got response:
"In qt 4.5 clipping in fast".

Still I apologize if this topic is useless for anyone.[sure]
Please do not reply again.
Kacper

[wysota]

Kacper, nobody said your topic is useless. Actually clipping is really bad in Qt and I'm sure you could speak about it to Uwe (author of Qwt) who shares this point of view. Despite that Qt4.5's clipping is said to be fast, it might still be slower in a particular usecase (like yours). Qt has to be fast in as many usecases as possible. It is not surprising (at least for me) if your algorithm (actually it's not yours, but let's call it that way) is faster here and there.

[maverick_pol]

Lets say that the "useless" was ironic.

where can your implementation be found (why would you recommend using it if you do not provide it)

I have been working on clipping optimization for a long time and wanted to share the result as I believe someone can find it a good solution.

All in all, the algorithm works ok and you can find its' implementation in many places.

[Uwe]

Kacper, nobody said your topic is useless. Actually clipping is really bad in Qt and I'm sure you could speak about it to Uwe (author of Qwt) who shares this point of view.
The main problem of clipping in Qt is not the clipping algo, but the fact that it renders before it clips. F.e. when you draw a huge circle ( because of zooming ) in a dotted line style, Qt renders trillions of dots ( maybe antialiased ), before they are thrown away - instead of rendering only the couple of dots, that are really on the screen. Depending on the zoom depth this might take minutes(!).
The Trolls told me, that these type of clipping can only be done with the additional knowledge of the application use case, so I don't expect to see any improvement in Qt 4.5.

Another problem is clipping against circular boundaries ( f.e. the canvas of a polar plot), because QRegion splits a circle into many small rectangles forgetting, that it was a circle. Setting such a clip slows down painting of a polygon by factor 4 ( even, when all lines are inside the circle ), while the calculation of the intersection of a line and a circle could be done much faster.

Unfortunately my conclusion is, that without clipping in the application code it is almost impossible to implement deep zoom operations with Qt.

Uwe

PS1: Qwt offers a class called QwtClipper, that includes an implementation of the Sutherland-Hodgman algo. I once wrote it to avoid overruns of coordinates on X11 ( here coordinates are shorts ), but it is also used, when you enable the clipping mode for a curve.

PS2: Right now I'm checking the effect of the Qt 4.5 performance improvements on the Qwt examples, but my first impressions doesn't look too promising. I will analyze what's going on and post my results to qt4-preview-feedback.

[fullmetalcoder]

2. I used my clipping algorithm before Qt clipping.
So you basically computed areas to clip and passed an appropriate QRect to the update() function right? (please correct me if I'm wrong)


Using the algorithm in the previous post is faster when only using Qt clipping.
You have the algorithm name and the implemntation can be found in many places
Would be nice to provide a link to the source(s) you used. If you managed to get something out of them it means they are worth the look and it saves sometimes. Besides my point was more regarding YOUR implementation as you said you had changed a couple of things which may be responsible for even more improvement.


If still that this topic is useless to you stop reading it.
No way! If I took time to read your post and write an answer it's precisely because I am interested :rolleyes:
I hope you did not take my comments badly. I was just trying to get more informations. THere was absolutely no offence meant, a summary of short and straight sentences is just my way of answering when I'm in a rush.


4. I have reported the topic many times to Trolltech I only got response:
"In qt 4.5 clipping in fast".
(don't take it badly again ;)) : have you supplied the code and an example to showcase the speed improvement it brings? Qt devs actually get LOADS of bug reports/feature requests so it may not be easy for them to provide a proper answer when faced whit such an input (and insufficient data to decide wether your claim is valid).

[maverick_pol]

Hi guys,

Because the project is a commercial solution I can't paste the code here.
I have given all the information that's leads to faster clipping.
When you try to draw polygons outside the visible rectangle Qt does the clipping.
When you use the clipping algorithm(clip polygons) before drawing then the Qt clipping should not take place and this algorithm works faster.
That's all. You need some code? see this; This is the pseudo-code with which I started:
http://www.cc.gatech.edu/grads/h/Hao-wei.Hsieh/Haowei.Hsieh/code2.html

I have also got some other explanations from other sites, but can't find them right now.

[fullmetalcoder]

Because the project is a commercial solution I can't paste the code here.
Not true, unless there is a special clause in your contract that explicitely prohibits it, releasing the code under public domain or BSD license for instance would not be a source of problem (unless of course clipping is part of your core business and, as such, part of the things that make your software valuable).

Thanks for the informations anyway.

[Uwe]

We are talking about the standard algo for polygon clipping, that needs about 100 lines of code. I agree, that the argumentation of maverick is weak, but IMHO translating 100 lines of pseudo code (you will find in every related book or web page) to Qt is indeed not worth to setup web space or a project page.

But if someone really needs it: the source code for an Qt implementation of the Sutherland-Hodgman polygon clipping is available from the Qwt package since more than 10 years. When you remove the defines, that are for Qt3/Qt4 compatibility the code doesn't depend on the rest of Qwt.

By the way: AFAIR Qt internally uses a variation of this algo. So it's true, when the Trolls answer, that their clipping is fast. But as written before: the type of algo is completely unimportant, the question is when clipping happens.

Uwe

[maverick_pol]

Hi guys,

I suppose we did not understand each over very well. I have been working with clipping for a while and couldn't make things work fast. After using this algorithm + adding some changes I got a good improvement.
I wanted to share the result. It maybe sound a bit strange, but
I do not really mind if you question it or not. Why? because I did not wanted to be selfish and keep it to myself.
I am not going to try to win a prize for the best clipping improvement or talk how great this solution is. This is just a hint for those who may find it useful; may code is working 10 times faster (clipping) and if you do not believe I can live with this knowledge.
Still I must say that I feel like stepping on foot of those who were standing and looking for clipping improvement for a while : )
All in all, thank you guys for such attention for this topic.

I can't paste the code due to the project contract. Leave this here.
I was given help many times here and if I could paste the code I would surely do so.

[fullmetalcoder]

is indeed not worth to setup web space or a project page
Sure. But a simple copy/paste is not particularly hard.


After using this algorithm + adding some changes I got a good improvement.
I wanted to share the result.
Back to my point : could you give more precisions about what improvements you made? I'm not even asking for code/pseudo-code just directions.


I can't paste the code due to the project contract.
Can't blame you for this. I won't bother you about it anymore.

[wysota]

Back to my point : could you give more precisions about what improvements you made? I'm not even asking for code/pseudo-code just directions.
Well... he already gave you the algorithm name and Uwe told you the algorithm was implemented in Qwt, so you can simply fetch the sources from there. I'm not sure what more information can be provided...

[fullmetalcoder]

I've had a look at the pseudo code he gave a link to but I'm also interested in the improvments he made and he is the only one who can possibly give me an answer to that (even though similar optimizations may have been used already by someone else).

[wysota]

I'm sure the changes were tailored specifically to one particular use-case so probably they will be useless for you.