How to speed up drawing thousands of elements

[seydar]

I display a graph like this:

And it has 1000 nodes and 999 edges. It gets a little slow when redrawing, and I was wondering if there's a better way for me to display the elements (circles and lines) — maybe the slowness when changing the screen size is simply part of life.

I am plotting nodes as circles, edges as lines, all within on_draw in an area.

(Also: is there a good way to detect when a user clicks on a line? It has the method for it, but I'm unable to trigger it, no matter how wide I make the line or how large I set the distance_tolerance)

[AndyObtiva]

I believe I redraw about 1200 shapes in the Tetris example on every change (block movement or elimination of a line). And, it runs smoothly with no performance slowdowns. I do that by using a divide and conquer strategy because I can conveniently break the Tetris grid into 20*10 (200) areas, and then only re-render the content of the single block area that changed when its color changes.

But, what you have is rendering more than 1200 shapes (1999 at least) in one giant area. I just tried to render the same thing on my machine, and I noticed it takes about 3 seconds per render of 1000 nodes/edges if I am using immediate mode (on_draw), and about 4 seconds if I am using stable paths (nesting shapes directly under area).

You might be able to adopt a divide and conquer strategy as per the one applied in Tetris, but you'd have to handle the math of dividing and conquering the calculations while keeping track of relative positioning per different area blocks.

For comparison, I believe SWT (supported in Glimmer DSL for SWT) gives the option of setting a clipping area in a canvas and only updating one small part of it if needed (similar to the divide & conquer strategy mentioned above, but in one area), which I think helps speed up rendering though I never personally tried using it. I wonder if supporting that in the LibUI C library would help improve performance when updating only one small part of the graph.

However, when updating the whole graph, I don't know how to speed it up beyond 3 seconds per render, but I will check with the upstream C libui project in case they could try to support leveraging the graphics card 2D hardware acceleration capabilities, which would be faster than CPU Processor rendering (assuming that's what they're doing right now).

As for your question on how to select a line by clicking on it. That is already supported in Glimmer DSL for LibUI.

If you use stable paths (slightly slower), then you can simply add an on_mouse_up listener directly inside a line like this and it takes care of everything:

        line(circle_center_x, circle_center_y, previous_point.first, previous_point.last) { |the_line|
          stroke rand(256), rand(256), rand(256), thickness: 10
          
          on_mouse_up do
            message = "(#{the_line.x}, #{the_line.y}), (#{the_line.end_x}, #{the_line.end_y})"
            msg_box('Line Selected!', message)
          end
        }

If you are using immediate mode rendering with on_draw, then the line object is not persistent, and the approach above would not work. But, you can save the produced line objects in an array that gets reset on every on_draw call, and then you can add an on_mouse_up listener to area and use the array of lines to figure which one got clicked (using its include? method), like this:

area {
  on_draw do
    ...
    @line_shapes = []
    @line_points.each do |pair|
      @line_shapes << line(pair.first.first, pair.first.last, pair.last.first, pair.last.last) {
        stroke rand(256), rand(256), rand(256), thickness: rand(3) + 2
      }
    end
    ...
  end

  on_mouse_up do |mouse_event|
    the_line = @line_shapes.find {|shape| shape.include?(mouse_event[:x], mouse_event[:y]) }
    if the_line
      message = "(#{the_line.x}, #{the_line.y}), (#{the_line.end_x}, #{the_line.end_y})"
      msg_box('Line Selected!', message)
    end
  end

}

[seydar]

Ah! I'll see if I can plot more areas instead of relying on replotting all thousand elements under the single stable path. Maybe I can just split the grid up into chunks so that the nodes are plotted in their grids, but the edges would be the only thing plotted in the large all-encompassing area. That should take the rendering time down by half.

Unfortunately, I still can't seem to get the line to tell that it's been clicked. I've tried using #include? and #contain?, but neither seem to work. It works for circles, though.

    def select_info_box(x, y)
      @info   = @circles.find {|c| c[:circle].contain?(x, y) }
      @info ||= @edges.find {|e| e[:line].include?(x,
                                                   y,
                                                   outline: true,
                                                   distance_tolerance: 25) }
      @plot.queue_redraw_all
    end

@plot = area {
        if x && y
          left x; xspan xs
          top  y; yspan ys
        end

        on_draw {|area|

          @dimensions = [area[:area_width], area[:area_height]]
          self.desc = grid_description

          scale = [area[:area_width]  / GridOperator::PLOT[0],
                   area[:area_height] / GridOperator::PLOT[1]]

          rectangle(0, 0, area[:area_width], area[:area_height]) {
            fill 0xffffff
          }

          plot_flows scale: scale

          if @info
            case @info[:type]
            when :node; plot_node_info
            when :edge; plot_edge_info
            end
          end
        }

        on_mouse_up do |area_event|
          select_info_box(area_event[:x], area_event[:y])
        end
      }

[AndyObtiva]

Here is a full code example that works with line clicking (note that I intentionally added some expensive logic upfront that is not optimized, so this can only handle 100 points/edges, but clicking lines should work). Hopefully, it will help you with that part only.

require 'glimmer-dsl-libui'

class ThousandNodeGraph
  include Glimmer::LibUI::Application
  
  WIDTH = 872
  HEIGHT = 512
  PADDING_X = 20
  PADDING_Y = 20
  NODE_COUNT = 100
  
  before_body do
    @points = NODE_COUNT.times.map do |n|
      x = rand(WIDTH - 2*PADDING_X) + PADDING_X
      y = rand(HEIGHT - 2*PADDING_Y) + PADDING_Y
      [x, y]
    end
    pairs = (@points.size - 1).times.map do |n|
      @points.rotate(n).zip(@points)
    end.flatten(1)
    pairs.reject! {|pair| PerfectShape::Point.new(pair.first).point_distance(pair.last) < 30 }
    pairs.sort_by! {|pair| PerfectShape::Point.new(pair.first).point_distance(pair.last) }
    @lines = pairs.take(NODE_COUNT)
  end
  
  body {
    window("Thousand Node Graph", WIDTH + 2*PADDING_X, HEIGHT + 2*PADDING_Y) {
      vertical_box {
        button {
          stretchy false
          
          text 'Refresh Nodes'
          
          on_clicked do
            refresh_nodes
          end
        }
        
        @area = area {
          on_draw do
            nodes
          end
          
        on_mouse_up do |mouse_event|
          the_line = @line_shapes.find {|shape| shape.include?(mouse_event[:x], mouse_event[:y]) }
          if the_line
            message = "(#{the_line.x}, #{the_line.y}), (#{the_line.end_x}, #{the_line.end_y})"
            msg_box('Line Selected!', message)
          end
        end
        }
      }
    }
  }
  
  def nodes
    @points.each_with_index do |point, index|
      circle_center_x = point.first
      circle_center_y = point.last
      circle_radius = 3
      circle(circle_center_x, circle_center_y, circle_radius) {
        stroke :black, thickness: 2
      }
      circle_radius = 2
      circle(circle_center_x, circle_center_y, circle_radius) {
        fill rand(256), rand(256), rand(256)
      }
    end
    
    @line_shapes = []
    @lines.each_with_index do |pair|
      @line_shapes << line(pair.first.first, pair.first.last, pair.last.first, pair.last.last) {
        stroke rand(256), rand(256), rand(256), thickness: rand(3) + 2
      }
    end
  end
  
  def refresh_nodes
    @area.queue_redraw_all
  end
end

ThousandNodeGraph.launch

By the way, if you want to pass your own distance tolerance, you should use contain? instead of include?. That's part of the problem of your code. include? only takes point x, y dimensions. Also, you are not showing where you are building your lines from @edges. It would help to see that code in case it has an issue. Some of the include? calculations make assumptions based on how you're stroking the line.

[kojix2]

Hi @seydar,

I'm kojix2, working with Ruby and libui-ng bindings. Your demo is very beautiful. I want to see if I can make your app faster. If possible, it would be helpful if you could share a piece of code that can reproduce the problem. If you could do so, it would make it easier for us to benchmark based on a real-world example.
Thanks!

[AndyObtiva]

@kojix2 my code above can reproduce the problem if you change NODE_COUNT to 1000.

But, the startup time being slow is unrelated to libui. To see the slowdown in libui, after the app starts (takes 15-30 seconds with 1000 nodes), click the "Refresh Nodes" button on top. It takes about 1 second to redraw all points with different colors. Ideally, it would happen in under 200ms. BTW, if you want, you could have the app startup Ruby code store the nodes initially generated in a yml file, and the next time you start the app, you could load the nodes from the yml file instead of taking a long time to generate them.

Another slowdown example to look into is if you try to use the "Area Image" feature (which breaks down an image into many 1 pixel rectangles), it takes a while to render an image, and more time if the image is bigger: https://github.com/AndyObtiva/glimmer-dsl-libui#area-image

[AndyObtiva]

Here is a version of the app above that caches objects through Ruby Marshal so that after the first time starting the app and closing it, the second time, it starts much more quickly. That should help you with testing the node rendering performance.

require 'glimmer-dsl-libui'

class ThousandNodeGraph
  include Glimmer::LibUI::Application
  
  WIDTH = 872
  HEIGHT = 512
  PADDING_X = 20
  PADDING_Y = 20
  NODE_COUNT = 1000
  FILE = 'nodes'
  
  before_body do
    @file_content = File.read(FILE) rescue ''
    if @file_content.empty?
      @points = NODE_COUNT.times.map do |n|
        x = rand(WIDTH - 2*PADDING_X) + PADDING_X
        y = rand(HEIGHT - 2*PADDING_Y) + PADDING_Y
        [x, y]
      end
      pairs = (@points.size - 1).times.map do |n|
        @points.rotate(n).zip(@points)
      end.flatten(1)
      pairs.reject! {|pair| PerfectShape::Point.new(pair.first).point_distance(pair.last) < 30 }
      pairs.sort_by! {|pair| PerfectShape::Point.new(pair.first).point_distance(pair.last) }
      @lines = pairs.take(NODE_COUNT)
      file_content_hash = { points: @points, lines: @lines }
      @file_content = Marshal.dump(file_content_hash)
      File.write(FILE, @file_content)
    else
      file_content_hash = Marshal.load(@file_content)
      @points = file_content_hash[:points]
      @lines = file_content_hash[:lines]
    end
  end
  
  body {
    window("Thousand Node Graph", WIDTH + 2*PADDING_X, HEIGHT + 2*PADDING_Y) {
      vertical_box {
        button {
          stretchy false
          
          text 'Refresh Nodes'
          
          on_clicked do
            refresh_nodes
          end
        }
        
        @area = area {
          on_draw do
            nodes
          end
          
        on_mouse_up do |mouse_event|
          the_line = @line_shapes.find {|shape| shape.include?(mouse_event[:x], mouse_event[:y]) }
          if the_line
            message = "(#{the_line.x}, #{the_line.y}), (#{the_line.end_x}, #{the_line.end_y})"
            msg_box('Line Selected!', message)
          end
        end
        }
      }
    }
  }
  
  def nodes
    @points.each_with_index do |point, index|
      circle_center_x = point.first
      circle_center_y = point.last
      circle_radius = 3
      circle(circle_center_x, circle_center_y, circle_radius) {
        stroke :black, thickness: 2
      }
      circle_radius = 2
      circle(circle_center_x, circle_center_y, circle_radius) {
        fill rand(256), rand(256), rand(256)
      }
    end
    
    @line_shapes = []
    @lines.each_with_index do |pair|
      @line_shapes << line(pair.first.first, pair.first.last, pair.last.first, pair.last.last) {
        stroke rand(256), rand(256), rand(256), thickness: rand(3) + 2
      }
    end
  end
  
  def refresh_nodes
    @area.queue_redraw_all
  end
end

ThousandNodeGraph.launch

[kojix2]

@AndyObtiva
Thanks!