Tk Source Code

View Ticket
Login
Ticket UUID: e9a842a3c584d6e709398529863fb8f798c83e3c
Title: TkCanvas events search for all objects , even they are not displayed
Type: Patch Version:
Submitter: nataraja18 Created on: 2013-08-29 09:55:30
Subsystem: 04. Canvas Basics Assigned To: jan.nijtmans
Priority: 5 Medium Severity: Minor
Status: Open Last Modified: 2014-11-15 12:49:50
Resolution: None Closed By: nobody
    Closed on:
Description:
All the events of TkCanvas are searching the entire linked list nextPtr/prevPtr, irrespective of whether they are displayed or not .

This has become a major overhead for my application , which draws 3million+ objects and frequently user performs panning/zooming .

Sol :
while rendering objects on canvas we can create a new linked list which actually save's the objects which are displayed on screen and also rejecting objects which are less than 1pixel and some more optimizations .

I've used nextPtr1 as a original clone for nextPtr  and prevPtr1 for prePtr .
and got a huge improvements in canvas rendering .
my modified TkCanvas http://www.youtube.com/watch?feature=player_embedded&v=HmAmXoTo5Uc 

If Tk community is interested in this enhancement 
I would like to share my code , so that it will be merged in future releases .

Regards
Nataraja G
User Comments: arjenmarkus added on 2014-11-15 12:49:50:
I have written some text describing the option:

--- canvas.n
+++ canvas.n
@@ -53,10 +53,15 @@
 appearance of the item can be different in different situations. The
 options that start with \fBactive\fR control the appearance when the mouse
 pointer is over it, while the option starting with \fBdisabled\fR controls
 the appearance when the state is disabled. Canvas items which are
 \fBdisabled\fR will not react to canvas bindings.
+.OP \-suppresssmallitems SuppressSmallItems SuppressSmallItems
+Specifies that items that are smaller than 2 pixels on the screen will not
+be drawn. Currently this holds for rectangle and oval items. Not drawing
+such small items may improve the performance if there are a large number,
+without seriously effecting the resulting image.
 .OP \-width width width
 Specifies a desired window width that the canvas widget should request from
 its geometry manager. The value may be specified in any
 of the forms described in the \fBCOORDINATES\fR section below.
 .OP \-xscrollincrement xScrollIncrement ScrollIncrement

jan.nijtmans added on 2014-01-02 21:11:45: (text/x-fossil-wiki)
Patch committed in branch [http://core.tcl.tk/tk/timeline?r=rfe-e9a842a3c5|rfe-e9a842a3c5] (with minimal edits in the ParseProc and PrintProc, obsoleting the offset parameter).

TODO:
- documentation.
- other types than oval and rect

arjenmarkus added on 2014-01-02 14:33:03:
Oh dear, yes, I have to agree that those lines should not be part of this ;)

jan.nijtmans added on 2014-01-01 12:52:57: (text/x-fossil-wiki)
Thanks, Arjen, implementation looks good to me. I only would leave out this part:

    [http://core.tcl.tk/tk/artifact/238426e59d7e1e4a?ln=879-882]    ;-)

arjenmarkus added on 2013-12-28 14:45:22:
I have attached a first patch that implements the ideas from Nataraja's original patch, but without using an aditional list or additional fields (merely using two bits in the existing structures).

The patch is not complete yet:
- No documentation
- Only rectangles and ovals affected

Here is the program I used to test it:

# chkoptim.tcl --
#     Incrementally check the adaptation of the canvas widget to the patch
#

#
# Step 1: option -suppresssmallitems is properly recognised
#
package require Tk
#console show
pack [canvas .c -suppresssmallitems 1 -width 400 -height 400]
puts [.c cget -suppresssmallitems]

#
# Step 2: create large and small rectangles
#
.c create rectangle  10  10  20  20 -tag {RECT LARGE}
.c create rectangle 101 101 102 102 -tag {RECT SMALL}

.c scale SMALL 100 100 0.1 0.1

catch {
    console show
}
#puts "Suppress on:  [.c find withtag SMALL]"
#after 2000 {
#   .c configure -suppresssmallitems 0
#   puts "Suppress off: [.c find withtag SMALL]"
#}

#
# Step 3: create a large number of (small) rectangles and measure the
#         time it takes to draw them
#
for {set i 0} {$i < 1000000} {incr i} {
    set x [expr {rand()*400}]
    set y [expr {rand()*400}]

    set id [.c create rectangle $x $y [expr {$x+0.1}] [expr {$y+0.1}]]
    #.c scale $id 0 0 1 1
}

after 1000 {
    .c configure -suppresssmallitems 1
    set id [.c create rectangle 0 0 400 400 -fill white]
    .c create rectangle 10 200 20 210 -fill yellow -width 3
    after 100 {
        .c delete $id
    }
}

arjenmarkus added on 2013-11-10 15:16:42:
I have had a closer look at the patch and I realised that it can be implemented in a different way that is perhaps a bit less efficient, but requires no extra fields.

A simple test program with a list of 1 million items shows that there is a small overhead of iterating over the entire list if the number of items to be considered is small (1%), but it is still 30 times faster than considering all items, where "considering" meant printing a number of the item. That seems quite acceptable.

The idea is to keep track of the visibility of the items. We can simply iterate over the whole list and check if the item is visible. If not, there is no need to consider it any further. This can also be used to add an extra attribute, -hidden, to the set of properties of a canvas item, so that you can control at the scripting level if an item is visible or not.

Also, there is an issue of compatibility to consider: the patch would suppress displaying rectangles and ovals that are smaller than two pixels, but that effectively means that applications that use small rectangles will give different results.

So I suggest turning this feature on by an extra option to the canvas: -hidesmallitems.

Also: the visibility of all items should be managed, not just rectangles and ovals.

jan.nijtmans added on 2013-09-16 14:20:26: (text/x-fossil-wiki)
>Is the extension of Tk_Item indeed a major problem?

Yes, it is a problem. Tk extensions which define there
own Canvas items will break. Not many extensions do
that but BLT is a well-known example:

E.g. in src/bltCanvEps.c:
<pre>
typedef struct {
    Tk_Item header;		/* Generic stuff that's the same for all
				 * types.  MUST BE FIRST IN STRUCTURE. */
    Tk_Canvas canvas;		/* Canvas containing the EPS item. */
    .....
} EpsItem;
</pre>

If fields are added to Tk_Item, then the "canvas" field and
all fields after it will move position. The added fields in
Tk_Item can overwrite the value in the Tk_Canvas variable -> crash.

A solution is to rename the existing "reserved1" field, let it point
to some additional storage and store the additional information
to be remembered there.

arjenmarkus added on 2013-09-16 13:53:17:
I have received a new RAR-file from Nataraja, this time based on Tcl/Tk 8.6.0

Is the extension of Tk_Item indeed a major problem?

(I do not understand why the RAR file contains truncated files - odd)

jan.nijtmans added on 2013-09-13 23:30:46: (text/x-fossil-wiki)
I couldn't resist having a look, and try to reconstruct some missing parts:

See: [/ci/a47459c6e6?sbs=1]. It doesn't compile. Many missing things like
"struct Tk_BgTile_", 

Also, Tk_Item has fields added at the end, which causes binary
incompatibility..... This will be a lot of work to get right.

dgp added on 2013-09-13 15:18:04:
I have confirmation that the truncation is in the .rar file
itself.

If an actual patch file is difficult to produce, then just
attaching the complete modified files to this ticket will be fine.

dgp added on 2013-09-13 14:57:22:
I have a truncated tkCanvas.c file.  Is it truncated
in the attached rar file too, or am I the victim of
a poor extraction program?

Could we just get a patch file?

arjenmarkus added on 2013-09-13 12:37:30:
Note: There is a global variable canvas_global in the patched source file tkCanvas.c (line 218). This might cause problems - multithreading. I am not sure if that will actually cause trouble, but its role should be closely examined.

jan.nijtmans added on 2013-09-07 08:01:26:
In a few weeks, Tk 8.6.1 will be released, but immediately after that I am willing to evaluate your patch for inclusion in Tk 8.6.2.

Attachments: