Serious performance degradtion in GuiRenderState#addGuiElement

When there are a large number of GuiElementRenderState in a stratum, may iterate large amout of gui element to do collision calculations every time a new element is added, which causes serious performance issues. This is most noticeable when there are a large number of non-intersecting rectangles. For example, when open the visulize_chunks_on_server debug overlay.

This performance issue can be greatly alleviated by quadtrees.

Image1 is the is the original situation, image2 is the effect of using the quadtree approach is evident. In this specific scenario, there is approximately a 10x performance difference.

The code that tried to optimize is as follows:

@Mixin(GuiRenderState.class)
public abstract class GuiRenderStateMixin {

	@Shadow private @Final	List<GuiRenderState.Node>	strata;
	@Shadow private			GuiRenderState.Node			current;

	@Shadow public abstract void up();

	@Inject(method = "addDebugRectangleIfEnabled", at = @At("HEAD"))
	public void addBoundsToQuadTree(ScreenRectangle bounds, CallbackInfo ci) {
		getNodeTree(current).insert(new ScreenElement(current, bounds));
	}

	/**
	 * @author Argon4W
	 * @reason Performance.
	 */
	@Overwrite
	private void navigateToAboveHighestElementWithIntersectingBounds(ScreenRectangle bounds) {
		var lastRootNode = strata.getLast();

		var intersection = getNodeTree(lastRootNode).highestIntersect(bounds);

		if (intersection != null) {
			current = intersection.node();
			up();
		} else {
			current = lastRootNode;
		}
	}

	@Mixin(GuiRenderState.Node.class)
	public static class NodeMixin implements NodeExtension {

		@Unique private QuadTree<ScreenElement>	nodeQuads;
		@Unique private int						nodeDepth;

		@Inject(method = "<init>", at = @At("TAIL"))
		public void onInit(GuiRenderState.Node parent, CallbackInfo ci) {
			if (parent == null) {
				var window = Minecraft.getInstance().getWindow();

				nodeDepth = 0;
				nodeQuads = new QuadTree<>(new ScreenRectangle(
						0,
						0,
						window.getGuiScaledWidth	(),
						window.getGuiScaledHeight	()
				), ScreenElement.COMPARATOR, 8, 6);
			} else {
				nodeDepth = ((NodeExtension) parent).getNodeDepth	() + 1;
				nodeQuads = ((NodeExtension) parent).getNodeTree();
			}
		}

		@Unique
		@Override
		public QuadTree<ScreenElement> getNodeTree() {
			return nodeQuads;
		}

		@Unique
		@Override
		public int getNodeDepth() {
			return nodeDepth;
		}
	}
}

public class QuadTree<T extends Area> {

    private final QuadTreeNode rootTreeNode;
    private final Comparator<T>    comparator;
    private final int        maxElements;
    private final int        maxDepth;

    public QuadTree(
          ScreenRectangle    bounds,
          Comparator<T>  comparator,
          int             maxElements,
          int             maxDepth
    ) {
       this.rootTreeNode  = new QuadTreeNode(bounds);
       this.comparator       = comparator;
       this.maxElements   = maxElements;
       this.maxDepth     = maxDepth;
    }

    public T highestIntersect(ScreenRectangle bounds) {
       return rootTreeNode.highestIntersect(bounds);
    }

    public Set<T> intersects(ScreenRectangle bounds) {
       return rootTreeNode.intersects(new ReferenceOpenHashSet<>(), bounds);
    }

    public void insert(T element) {
       rootTreeNode.insert(element, 0);
    }

    public void reset() {
       rootTreeNode.reset();
    }

    public class QuadTreeNode {

       private final  ScreenRectangle    bounds;
       private final  List<T>          elements;
       private          T           maxElement;
       private          QuadTreeNode   q0Child;
       private          QuadTreeNode   q1Child;
       private          QuadTreeNode   q2Child;
       private          QuadTreeNode   q3Child;
       private          boolean          isLeaf;

       public QuadTreeNode(ScreenRectangle bounds) {
          this.bounds       = bounds;
          this.elements  = new ReferenceArrayList<>(maxElements);

          this.maxElement    = null;
          this.q0Child   = null;
          this.q1Child   = null;
          this.q2Child   = null;
          this.q3Child   = null;
          this.isLeaf       = true;
       }

       public T highestIntersect(ScreenRectangle bounds) {
          if (!this.bounds.intersects(bounds)) {
             return null;
          }

          var maxElement = (T) null;

          if (isLeaf) {
             maxElement = this.maxElement;
          } else {
             var q0 = q0Child.highestIntersect(bounds);
             var q1 = q1Child.highestIntersect(bounds);
             var q2 = q2Child.highestIntersect(bounds);
             var q3 = q3Child.highestIntersect(bounds);

             maxElement = q0;

             if (maxElement == null || (q1 != null && comparator.compare(maxElement, q1) < 0)) { maxElement = q1; }
             if (maxElement == null || (q2 != null && comparator.compare(maxElement, q2) < 0)) { maxElement = q2; }
             if (maxElement == null || (q3 != null && comparator.compare(maxElement, q3) < 0)) { maxElement = q3; }
          }

          return maxElement;
       }

       public Set<T> intersects(Set<T> intersections, ScreenRectangle bounds) {
          if (!this.bounds.intersects(bounds)) {
             return intersections;
          }

          if (isLeaf) {
             for (var element : elements) {
                if (element.area().intersects(bounds)) {
                   intersections.add(element);
                }
             }
          } else {
             q0Child.intersects(intersections, bounds);
             q1Child.intersects(intersections, bounds);
             q2Child.intersects(intersections, bounds);
             q3Child.intersects(intersections, bounds);
          }

          return intersections;
       }

       public boolean insert(T area, int depth) {
          if (!bounds.intersects(area.area())) {
             return false;
          }

          if (isLeaf) {
             if (elements.size() < maxElements || depth >= maxDepth) {
                elements.add(area);

                if (maxElement == null || comparator.compare(area, maxElement) > 0) {
                   maxElement = area;
                }

                return true;
             } else {
                maxElement = null;
                q0Child       = new QuadTreeNode(getQ0(bounds));
                q1Child       = new QuadTreeNode(getQ1(bounds));
                q2Child       = new QuadTreeNode(getQ2(bounds));
                q3Child       = new QuadTreeNode(getQ3(bounds));
                isLeaf    = false;

                for (var index = 0; index < elements.size(); index ++) {
                   var oldElement = elements.get(index);

                   q0Child.insert(oldElement, depth + 1);
                   q1Child.insert(oldElement, depth + 1);
                   q2Child.insert(oldElement, depth + 1);
                   q3Child.insert(oldElement, depth + 1);
                }

                elements.clear();
             }
          }

          var result = false;

          result |= q0Child.insert(area, depth + 1);
          result |= q1Child.insert(area, depth + 1);
          result |= q2Child.insert(area, depth + 1);
          result |= q3Child.insert(area, depth + 1);

          return result;
       }

       public void reset() {
          if (isLeaf) {
             elements.clear();
          } else {
             q0Child.reset();
             q1Child.reset();
             q2Child.reset();
             q3Child.reset();
          }
       }
    }

    public static ScreenRectangle getQ0(ScreenRectangle bounds) {
       return getQ(
             bounds,
             bounds.position().x() + bounds.width() / 2,
             bounds.position().y()
       );
    }

    public static ScreenRectangle getQ1(ScreenRectangle bounds) {
       return getQ(
             bounds,
             bounds.position().x(),
             bounds.position().y()
       );
    }

    public static ScreenRectangle getQ2(ScreenRectangle bounds) {
       return getQ(
             bounds,
             bounds.position().x(),
             bounds.position().y() + bounds.height() / 2
       );
    }

    public static ScreenRectangle getQ3(ScreenRectangle bounds) {
       return getQ(
             bounds,
             bounds.position().x() + bounds.width   () / 2,
             bounds.position().y() + bounds.height  () / 2
       );
    }

    public static ScreenRectangle getQ(
          ScreenRectangle    bounds,
          int             screenX,
          int             screenY
    ) {
       return new ScreenRectangle(
             screenX,
             screenY,
             bounds.width   () / 2,
             bounds.height  () / 2
       );
    }
}

public interface Area {

    ScreenRectangle area();
}

public interface NodeExtension {

    QuadTree<ScreenElement>    getNodeTree    ();
    int                   getNodeDepth();

    static QuadTree<ScreenElement> getNodeTree    (GuiRenderState.Node node) { return ((NodeExtension) node).getNodeTree (); }
    static int                getNodeDepth(GuiRenderState.Node node) { return ((NodeExtension) node).getNodeDepth    (); }
}

public record ScreenElement(GuiRenderState.Node node, ScreenRectangle area) implements Area, Comparable<ScreenElement> {

    public static final Comparator<ScreenElement> COMPARATOR = Comparator.naturalOrder();

    @Override
    public int compareTo(@NonNull ScreenElement that) {
       return Integer.compare(
             NodeExtension.getNodeDepth(this.node),
             NodeExtension.getNodeDepth(that.node)
       );
    }
}