Poor rendering performance with a lot of grid lines

[ocharles]

I am trying to make a cartography application, where the user starts with a "blank canvas" - a grid. The grid extends [-1000, 1000] in both the X and Y-axis, so there are 2000 * 2000 = 4mil grid lines to render:

gridLines :: Diagrams.Diagram Diagrams.Cairo Diagrams.R2
gridLines =
  Diagrams.lc
    Diagrams.white
    (gridLinesIn (negate gridHalfWidth) gridHalfWidth <>
     Diagrams.rotate
       (90 Diagrams.@@ Diagrams.deg)
       (gridLinesIn (negate gridHalfHeight) gridHalfHeight))

gridLinesIn :: Double -> Double -> Diagrams.Diagram Diagrams.Cairo Diagrams.R2
gridLinesIn x y = Diagrams.dashingG [1 / 20, 1 / 20] 0 $
  foldMap (\n ->
             Diagrams.opacity
               (0.5 + 0.5 *
                (fromIntegral (round n `mod` 2 :: Int))) $
             Diagrams.translate (Diagrams.r2 (0,n)) $
             Diagrams.scale len $
             gridLine)
          [x .. y]
  where len = y - x

gridHalfWidth, gridHalfHeight :: Double
(gridHalfWidth, gridHalfHeight) = (1000, 1000)

As the user never sees the full grid, I am zooming/clipping to create a viewport:

Diagrams.clipped $
Diagrams.scale zoomFactor $ 
Diagrams.square 100 $ 
gridLines

This renders in about 0.15s (diagrams-gtk), which unfortunately not going to fly for real-time interaction.

[ocharles]

I spoke to @fryguybob about this on IRC:

1:25 PM <ocharles> If I draw gridlines from -1000 to 1000, it's super slow, despite using `clipping` to `square 10`
1:28 PM <fryguybob> ocharles: That might be Cairo's fault, but I think we should probably have some way to specialize clipping to a rectangle as that should be much faster then clipping to some path.
1:29 PM <fryguybob> (a rectangle aligned to the output coordinates specifically)
1:29 PM <ocharles> Hmm
1:30 PM <ocharles> Well, I can draw lines at 1 unit apart from [-100,100]^2 at a very interactive framerate, but [-1000,1000]^2 kills performance. so it does seem to be in the extreme ends
1:30 PM <ocharles> That is 4 million lines, though only 100 are in the viewport
1:31 PM <ocharles> (Viewport is [-5, 5]^2)
1:32 PM <fryguybob> ocharles: Oh, in that case diagrams always handling all of those lines, that would be much slower.  We don't prune anything with clipping, it is just handed off to the backend.
1:32 PM <fryguybob> I was thinking about the case of a long line vs a short line.
1:32 PM <ocharles> Ah, no
1:32 PM <ocharles> I was hoping I could be very declarative about the whole scene, and have diagrams figure out the most efficient way to get that to the screen
1:34 PM <fryguybob> ocharles: Yeah, that is an optimization that we should do at least at the level of some quick bounding box test.  But the semantics are not completely clear.
1:34 PM <ocharles> ok
1:34 PM <fryguybob> Queries on clipped things are expected to include subdiagrams that are not clipped (I think)

[byorgey]

Why 4 million? I would expect on the order of 2000 + 2000 = 4000 lines to make a 2000x2000 grid.

[jeffreyrosenbluth]

What if you restructured so that the grid is a [-1000, 1000] X [-1000, 1000] array or vector of cells :: Diagram. Then the viewport function simply grabs the appropriate cells and concatenates them.

[ocharles]

@byorgey: You are right, that was some sloppy maths! So it struggles with only 4000 lines then, which is even worse :)

@jeffreyrosenbluth There are various ways that I can fix this, but I see the purpose of diagrams to be declarative, and now the implementation is leaking out into the code structuring.

[fryguybob]

@ocharles What you get now is declarative, it is only the performance of the implementation that is leaking out. This isn't nice nonetheless.

[fryguybob]

@jeffreyrosenbluth I think this is how you get the 4million items drawn performance. Drawing cells takes squared overhead, while lines is linear in the sum of the sides. Sure, you are clipping down to the viewport, but you pay for squared performance inside the viewport.

[jeffreyrosenbluth]

Yes, i agree. It would be nice if we had some sort of lazy clipping function handled before the diagrams is passed to the backend.

[ocharles]

@fryguybob, that's sort of my point - I can't be declarative and ship a workable product. Right now I have to compromise on usability, or muddle the declarative structuring of code to something that has more context, purely for performance reasons.

[jeffreyrosenbluth]

hmmm, It might be possible to add a cairo specific function say clipToRect that takes advantage of:

http://cairographics.org/FAQ/#clipping_performance (the section "Clipping should only make things faster, right?")

[fryguybob]

If you think of a clipToRect that semantically was like filter inRect and your grid lines were grid :: ... -> [Diagram], then you would want the filter to somehow fuse with the generation inside grid to avoid touching all 4000 diagrams. I don't see this happening, though perhaps there is some clever way to get this sort of thing. Certainly we could use the geometry to structure the diagram, but inserting into this structure will still involve touching all 4000 diagrams. Subsequent geometry driven queries, however, would avoid paying the cost. Another way to make it cheaper is to bake in this fusion and in the backend handle a Grid where we generate after knowing the view. But what if Grid doesn't do exactly what you want...

[fryguybob]

Also relevant with efficient implementations: https://trello.com/c/rKCAA3OZ

[JohnLato]

FWIW Cairo seems to struggle with grid lines as well, so even if diagrams
gets improved clipping performance may still be an issue. (For an
application at work we've had to resort to direct OpenGL at a much lower
scale than I would have expected.)

John
On Oct 3, 2014 7:58 AM, "Ryan Yates" [email protected] wrote:

Also relevant with efficient implementations:
https://trello.com/c/rKCAA3OZ

—
Reply to this email directly or view it on GitHub
#216 (comment)
.