AntV G6 is an open source graph visualization and analysis engine focused on relational data.

GitHub：github.com/antvis/G6

Liverpoolfc.tv: g6. Antv. Vision/useful

preface

This paper will introduce the design, calculation and optimization principle of Minimap in G6 in detail. Will involve a lot of calculation logic, see math on the head of the partners can choose to omit 🌝.

Minimap purpose

It is mainly used for navigation of large scale diagrams, most of which do not require minimaps to display as much detailed information as the original.

Concept to explain

The main figure and the Minimap

  • The size of the Main Canvas is the width and height set when instantiating the diagram.
  • The BBox is the smallest bounding box of the current Main Graph. It may have a different aspect ratio from the Main Canvas, or it may exceed the Main Canvas.
  • The size of the Minimap Canvas is the size specified when instantiating the Minimap plug-in, which may be different from the aspect ratio of Main Cavans.
  • Minimap Graph BBox is the Main Graph BBox isometric scale.

Graphics and graphics grouping

The types of graphics are circle, text, rect, path… [seeG6 Attributes of each graph], and graph groups are containers for managing and combining these graphs. Similar to the relationship between G and other graphic labels in SVG.

In G6, the relationship between graphs on graphs and graph groups is shown as follows:

  • In the figure above, the adjacent layer blocks represent the direct inclusion relationship;
  • The main image canvas has a Root graph Group Root Group, which contains Nodes Group, Edges Group Combos Group, Delegates Group, including node, edge, Combos, Delegates Group.
  • The Delegates Group mainly houses temporary graphics on the picture, such as the virtual representation box when dragging nodes/groups:

  • A Node Group in a Nodes Group contains all graphs in a Node, including circles, text, rect, and so on. Edges Group and Combos Group are similar.

matrix

Each graph and graph group has its own transformation matrix, which is used to control its translation, scaling and rotation (rotation is less common in G6). You can get your own matrix with element.getmatrix (). The initial value of this matrix is NULL in the absence of any panning, scaling, or rotation. An identity matrix can also be used to indicate that there are no matrix operations. In G6, each Node Group in Nodes Group has a matrix to control the specific position of the Node on the canvas, and the x and Y of the specific graph (circle, text, etc.) in a Node Group are used as reference to establish the sub-coordinate system. Is not directly related to the coordinates of the entire node. Combos Group works the same as Nodes Group. Different from nodes, each Edge Group in the Edge Group does not use a matrix to control the position of Edges. The starting and ending positions of Edges are defined by the path graph in the Edge Group.

Bounding Boxes (BBox)

A bounding box is a minimum rectangle enclosing a figure or group of figures, described using the following objects:

{
  minX: number,
  minY: number,
  maxX: number,
  maxY: number,
  centerX: number,
  centerY: number,
  width: number,
  height: number
}
Copy the code

To use bBox well, we need to distinguish getBBox from getCanvasBBox:

  • Element.getbbox () : Gets an element’s bounding box that is independent of the matrix of that element and its children;
  • Element.getcanvasbbox () : Gets the bounding box of the current graph relative to the canvas after the transformation of element’s matrix and its children.


The following circle figure is translated and enlarged from the form of A through the matrix to form A. Since a is not matrix changed, its matrix is null, and a.getcanvasbbox () returns the same value as a.getbbox (). A.getcanvasbbox () returns the bounding box after the matrix operation. A.getbbox () ignores the matrix and is equal to a.getbbox ().





The following figure shows a grouping of graphs.

  • In form G: a figure without any matrix transformation; Here, the x and y of figure B are both zero, that is, its position is (0, 0), which is shifted to (35, 15) by the matrix; G itself doesn’t have any matrix transformations. GetBBox is a bounding box that is not affected by any matrix. GetCanvasBBox considers the influence of the matrix of B;
  • Transform to G form: A figure is enlarged by the matrix to obtain A, b -> B matrix is unchanged, G is translated by the matrix applied to the group to obtain the new position. Similarly, getBBox yields a bounding box that is unaffected by any matrix and is therefore equal to g.gebbox (). On the other hand, g. gettcanvasbbox considers the influence of matrices on A, B and G.



The problem

  1. Two canvases will double the rendering cost;
  2. Copying graphics from the main canvas to a minimap requires careful scaling;
  3. Using the View Port to locate the current main graph shows part of the logic that is slightly more complicated.

plan

In logic

Minimaps come in three types:

  • Default: keep it consistent with all graphs on the main graph, that is, draw all graphs on the main graph, including all graphs in complex nodes/edges;
  • KeyShape: Only keyShape of nodes/edges on the main graph;
  • Delegate: Uses a square instead of a main graph node, with edges drawn only as keyShape.

These three types of minimaps have different logic for copying the main graph, and the latter two will perform better. To understand replication logic, first we need to know

1. Copy logic

  • Defualt: Directly clear the matrix of the Root Group of the main graph (maybe pan, zoom) and copy it to the Minimap Canvas.
  • KeyShape: In this mode, there is only one graph Group Root Group on the Minimap Canvas. KeyShape of all nodes/edges is directly added to the Root Group.

First copy the edge keyShape to the Minimap Canvas:

// Iterate over the elements in the Edges Group
EdgesGroup.children.forEach(nodeGroup= > {
  // In the group of edges, get the keyShape of this edge
  const keyShape = nodeGroup.findKeyShape(); 
  // Copy to a new object
  const cKeyShape = clone(keyShape);
 	// Add cKeyShape to the Root Group of the minimap
  minimap.rootGroup.children.push(cKeyShape);
});
Copy the code

Then copy the keyShape of the node to the Minimap Canvas: because in the main graph, the position of the node is controlled by the matrix of its parent group, while the nodes in the keyShape have no independent parent group. Therefore, we need to write the node positions of the main graph to the corresponding keyShape in the minimap. The pseudocode is as follows:

// Iterate over the elements in the Nodes Group
NodesGroup.children.forEach(nodeGroup= > {
  // In the group of the node, get the keyShape of the node
  const keyShape = nodeGroup.findKeyShape(); 
  // Copy to a new object
  const cKeyShape = clone(keyShape);
  // Get the canvasBBox of the nodeGroup
  const canvasBBox = nodeGroup.getCanvasBBox();
  // Specify a location for cKeyShape
  cKeyShape.attr({
    x: canvasBBox.centerX,
    y: canvasBBox.centerY
  });
 	// Add cKeyShape to the Root Group of the minimap
  minimap.rootGroup.children.push(cKeyShape);
});
Copy the code
  • Delegate: Same as keyShape mode. In this mode, there is only one graph Group Root Group on the Minimap Canvas. Keyshapes of all nodes/edges are directly added to the Root Group.

The logic of the copy edge is the same as keyShape’s pattern. Currently, the delegate uses a rectangle representing the length, width, and position of each node, with pseudo-code like this:

// Iterate over the elements in the Nodes Group
NodesGroup.children.forEach(nodeGroup= > {
  // Get the canvasBBox of the nodeGroup to get the correct node size and position
  const canvasBBox = nodeGroup.getCanvasBBox();
  const delegateShapeAttrs = {
    x: canvasBBox.minX,
    y: canvasBBox.minY,
    width: canvasBBox.width,
    height: canvasBBox.height
  }
 	// Add a delegate to the Root Group of the minimap
  minimap.rootGroup.addShape('rect', {
    attrs: delegateShapeAttrs
  });
});
Copy the code

2. Zoom and pan logic of Minimap Canvas

The Minimap Root Group obtained from the copy logic is the same length and width as the Main Graph Root Group, and we need to scale it to the size of the Minimap Canvas. Generally speaking, Minimap Canvas is smaller than the main Canvas, but there are several issues that need to be considered carefully:

  • In most cases, the aspect ratios of the Minimap Canvas, Main Graph Root Group, and Main Graph Canvas are different.
  • The Main Graph Root Group may be outside the Main Graph Canvas.


After copying the logic above, we get a Minimap that looks like this:





It needs to be scaled and shifted by manipulating the matrix mMatrix of the Minimap Root Group.

  • Move the Minimap Graph Group to the upper left corner of the Minimap Canvas according to its canvasBBox:
const canvasBBox = MinimapGraphGroup.getCanvasBBox(); // Get the CanvasBBox of the Minimap Graph Group
let mMatrix = [ 1.0.0.0.1.0.0.0.1 ]; // The initialization matrix is the identity matrix

// Pan it to the upper left corner
transform(mMatrix, [
  ['t', canvasBBox.minX, canvasBBox.minY], 
]);
Copy the code

At this point, we get the following results:



  • Step 2: Scale the Minimap Graph Group to an appropriate size to fit the Minimap Canvas. The scaling factor ratio is:
const ratio = Math.min(width(Minimap Canvas) / canvasBBox.width,
                      height(Minimap Canvas) / canvasBBox.height);
Copy the code

Scaling with ratio:

transform(mMatrix, [
  ['s', ratio, ratio], 
]);
Copy the code

At this point, we get the following results:



  • Move the Minimap Graph Group to the center of the Minimap Canvas
const dx = (width(Minimap Canvas) - CanvasBBox.width * ratio) / 2;
const dy = (height(Minimap Canvas) - CanvasBBox.height * ratio) / 2;
transform(mMatrix, [
  ['t', dx, dy], 
]);
Copy the code

Finally, the following results are obtained:



At this point, the Minimap Canvas is completed. The main Canvas’s panning and zooming do not affect the Minimap Canvas. However, local node/edge style and position changes need to be updated by the Minimap Canvas.

3. Link the View Port logic with the main diagram

View Port is used to locate the corresponding portion of the Minimap Canvas displayed in the main diagram. Note the following issues:

  • The aspect ratio of the View Port is always the same as that of the Main Canvas.
  • The position and size of the View Port are affected when the user zooms and drags the canvas on the main image.
  • Users can also drag and drop the View Port to navigate the main diagram.

Update the position and size of the View Port when zooming and dragging the canvas in the main image by following steps:

  • Step 1: Calculate the width and height of View Port: viewPort-width, viewPort-height. First, we need to get the relative width and height of the main canvas coordinate. The following figure shows what is the relative width and height. When the main drawing is shifted and scaled, the coordinate system of the drawing will also be shifted and scaled:



As a result, We use the main viewport’s upper-left coordinates (0, 0) and lower-right coordinates (maincanvas.width, Height) (mainCanvas.width and mainCanvas.height are the size of the Main Canvas specified when instantiating the graph), we can calculate the relative coordinates of the Canvas topLeft and bottomRight, Thus, the relative width and height can be calculated:

// obtain the corresponding canvas coordinates topLeft and bottomRight based on the topLeft and bottomRight positions of the main canvas viewport
const topLeft = graph.getPointByCanvas(0.0);
const bottomRight = graph.getPointByCanvas(mainCanvas.width, mainCanvas.height)
// Relative width and height
const width = bottomRight.x - topLeft.x;
const height = bottomRight.y - topLeft.y;
Copy the code
  • Step 2: Calculate the position of the View Port relative to the Minimap DOM container (left, top).

First of all, let’s think about not scaling, just translating. Here we need to discuss four cases:

First, the left side of the main canvas canvasBBox exceeds the left side of the main canvas:



Then the left value of View Port isdx - mainGraphRootGroup.getCanvasBBox().minX * ratio 。



Second, the right side of the main canvas canvasBBox exceeds the right side of the main canvas:



Then the left value of View Port is:

const mainGraphBBox = mainGraphRootGroup.getCanvasBBox();
const a = (mainGraphBBox.width - mainGraphBBox.maxX + mainCanvas.width) * ratio;
const left = -(width - a - dx);
Copy the code





Third, the upper side of the main image canvasBBox exceeds the upper side of the main canvas. It’s similar to the first case, but instead of the Y-axis contrast;

Fourth, the lower side of the main canvas canvasBBox exceeds the lower side of the main canvas. It’s similar to the second case, but I’m going to replace it with the Y-axis contrast.



In the following cases, only the X-axis and Y-axis of the above four cases need to be combined, and the X-axis and Y-axis do not affect each other:





Finally, when the Main Graph is scaled, it affects the size of the Main Graph Root Group. So if the graph is scaled, you also need to scaleratio /= zoom 。

4. View Port linkage main diagram logic

At present, only the View Port drag-and-drop function is provided, so as to move the main map in linkage. You cannot drag a View Port beyond the top, bottom, left, and right boundaries of the Minimap Canvas. The View Port listener is placed on the DOM. During the drag process, control the translation of the main graph by using the following code:

// previousX previousY is the last mouse position during the drag
const dx = previousX - e.clientX;
const dy = previousY - e.clientY;
constzoom = graph.getZoom(); The current scaling factor of the main graph// Ratio is the scaling factor of the main image scaled to the Minimap Canvas above
graph.translate((dx * zoom) / ratio, (dy * zoom) / ratio);
previousX = e.clientX;
previousY = e.clientY;
Copy the code

5. Boundary situation processing

In order to prevent users from dragging the canvas indefinitely, there is a limit in the built-in interactive Drag-Canvas, which can only drag one more screen above or below the Main Graph Root Group. This does not affect the use of the canvas if the user wants to add nodes or drag them farther away from the current Main Graph Root Group, since the Main Graph Root Group’s scope is updated and the canvas can be dragged more. Therefore, when the Canvas is dragged to its limit, the ViewPort will not completely exceed the Minimap Canvas, and the remaining part will be more or less on the Minmap Canvas. The Minimap Canvas container is set to overflow: hide, so the View Port beyond the Minimap Canvas is hidden. When the user drags the main Canvas so that the View Port is partially outside the Minimap Canvas, clicking on the View Port will jump back to the View Port that is completely inside the Minimap Canvas. The case where an edge that was originally out of bounds tops the edge of the Minimap Canvas. Help users quickly locate back to the main map content.

Performance optimization

1. Provide the Delegate or keyShape mode

The default mode of copying all the graphics of the main diagram into a Minimap will cause pressure to draw and update. As a result, the Delegate and keyShape modes were provided in the earliest versions of Minimap. Delegate is the best performing mode.

2. Reduce redrawing of the Minimap Canvas

As mentioned above, the Minimap Canvas does not need to be redrawn when the main drawing is zooming and shifting. In older Minimaps, the beforePaint of the main drawing is listened on, meaning that every redraw update of the main drawing triggers a redraw of the Minimap Canvas. And the original implementation was to completely empty the Minimap during redrawing, create and add again, which was very performance consuming. 3.4.5 Minimap listens for AfterRender, AfterLayout, AfterAddItem, AfterUpdateItem, afterRemoveItem. Trigger the Canvas of the Minimap Canvas to be redrawn and modified differentially, instead of being readded after being emptied. In other words, the Minimap Canvas is updated only when elements on the main diagram are added or deleted, their positions are changed, and the layout is rearranged. Beforepaint only triggers updates of View Port size and position.

3. debounce

The Minimap Canvas redraw mechanism mentioned above still cannot avoid frequent refresh in some cases, such as:

  • Afteradditems are triggered frequently when the main image is rendered for the first time.
  • In Force Layout, each iteration triggers the rerendering of the main drawing, which triggers frequent redrawing of the Minimap. However, it does not make sense for the Minimap to keep updating when the main drawing is not stable.

Therefore, in version 3.4.5, debounce was used to merge the redraw Minimap Canvas into one execution that triggered frequently over a short period of time. Greatly reduces the performance cost of redrawing.

conclusion

Minimap has been around since the G61.x era and has been ridiculed by users for its performance and accuracy. After this revamp, WE believe Minimap can provide users with efficient and accurate navigation. Maybe it has more room for performance and function optimization, welcome friends from the community to discuss and build together.