Improve hit testing performance by using R-tree - #21306
Conversation
|
You can test this PR using the following package version. |
There was a problem hiding this comment.
We are using render-thread-computed transforms for hit-testing. This means that they are affected by render thread animations. Which means that assuming that we can track hit-test tree validity from the UI thread is incorrect (we can, however, assume that readback revision bump indicates tree invalidation)
Another thing here is that the tree seems to be rebuilt entirely on every frame. This significantly affects the benchmark that needs to account tree rebuild amortization and subsequent allocation pressure.
|
What kind of visual structure are you using for benchmark? Somewhat balanced "natural" UI tree or 16K visuals attached directly to the tree root? |
Will look into this.
I don't think the tree is rebuilt on every frame. It only gets rebuilt when the hit test index becomes dirty (see
I'm using the benchmark I included in this PR ( |
|
I suppose we don't really need an RTree for the entire composition target. Since visuals already include information about their subtree bounds we can opportunistically enable such indexing for direct children of visuals with >100 nodes. Would this make sense? |
Sounds like a BVH-like approach on top of AABB. So yeah, I think it should be fine as well. I will give it a try. |
Can the subtree visuals be out-of-bound to their parent visual? If yes I think we will still need to build a separate index based on their transformed bounds. |
|
We generally try to avoid effects that trigger a full tree walk on one visual change. This was a source of major perf problems with deep visual trees in 11.x. i. e. consider a scene with animated progressbar at the corner. Since it technically invalidates composition target for every frame, it will trigger a full tree rebuild. |
|
I think we also propagate readback revision bump to all parents (need to recheck this, but I think it should happen automatically since those are marked as having dirty subtree bounds), so it could potentially be useful for per-visual hittest tree cache invalidation. |
Own bounds and subtree bounds are things we are tracking separately. Subtree bounds are guaranteed to contain all of child visuals. Existing hit-test code should already rely on this for filtering out nodes. Note that bounds reported to the UI thread might be in visual's parent coordinate space (need to recheck, don't remember) |
|
Thanks for the background! I'm turning this PR into draft for now and will be back after investigating into some hierarchy-based approach (such as per-visual index cache). |
|
Quickly prototyped a dynamic AABB tree for hit testing (per visual AABB tree) and benchmarked it against static visuals and animated visuals respectively. See bc3c5ba It still has room for optimization, but I ran the benchmark anyway. Static visual benchmarks: public class CompositionHitTesting
{
private const int CellSize = 8;
private const int CellStride = 12;
private const int TreeDepth = 4;
private CompositorTestServices? _services;
private Point _hitPoint;
private Border? _expectedHit;
[Params(1, 2, 4, 8, 16, 32, 64, 1024, 4096, 16384)]
public int VisualCount { get; set; }
[GlobalSetup]
public void Setup()
{
var canvas = BuildGrid(VisualCount, out var size, out _expectedHit);
_services = new CompositorTestServices(size);
_services.TopLevel.Content = canvas;
_services.RunJobs();
_hitPoint = new Point(CellSize / 2d, CellSize / 2d);
if (!ReferenceEquals(HitTestFirst(), _expectedHit))
throw new InvalidOperationException("Hit test returned an unexpected visual.");
}
[GlobalCleanup]
public void Cleanup()
{
_services?.Dispose();
_services = null;
_expectedHit = null;
}
[Benchmark]
public Visual? HitTestFirst()
{
return _services!.Renderer.HitTestFirst(_hitPoint, _services.TopLevel, null);
}
internal static Canvas BuildGrid(int visualCount, out Size size, out Border? firstChild)
{
var columns = (int)Math.Ceiling(Math.Sqrt(visualCount));
var rows = (visualCount + columns - 1) / columns;
size = new Size(columns * CellStride, rows * CellStride);
firstChild = null;
var root = new Canvas
{
Width = size.Width,
Height = size.Height
};
var leafHost = root;
for (var depth = 0; depth < TreeDepth; depth++)
{
var nested = new Canvas
{
Width = size.Width,
Height = size.Height
};
leafHost.Children.Add(nested);
leafHost = nested;
}
for (var i = 0; i < visualCount; i++)
{
var child = new Border
{
Width = CellSize,
Height = CellSize,
Background = Brushes.Red
};
Canvas.SetLeft(child, i % columns * CellStride);
Canvas.SetTop(child, i / columns * CellStride);
leafHost.Children.Add(child);
if (i == 0)
firstChild = child;
}
return root;
}
}
Animated visual benchmarks: public class CompositionHitTestingAnimated
{
private const int CellSize = 8;
private const int CellStride = 12;
private const int TreeDepth = 4;
private CompositorTestServices? _services;
private CompositionVisual? _animatedVisual;
private Border? _expectedHit;
private Point _hitPoint;
[Params(1, 2, 4, 8, 16, 32, 64, 1024, 4096, 16384)]
public int VisualCount { get; set; }
[GlobalSetup]
public void Setup()
{
var canvas = BuildDeepAnimatedGrid(VisualCount, out var size, out _expectedHit);
_services = new CompositorTestServices(size);
_services.TopLevel.Content = canvas;
_services.RunJobs();
_animatedVisual = _expectedHit!.CompositionVisual;
StartOffsetAnimation();
_services.RunJobs();
UpdateHitPoint();
if (!ReferenceEquals(HitTestAnimatedChild(), _expectedHit))
throw new InvalidOperationException("Hit test returned an unexpected visual.");
}
[GlobalCleanup]
public void Cleanup()
{
_services?.Dispose();
_services = null;
_animatedVisual = null;
_expectedHit = null;
}
[Benchmark]
public Visual? HitTestAnimatedChild()
{
_services!.RunJobs();
UpdateHitPoint();
return _services.Renderer.HitTestFirst(_hitPoint, _services.TopLevel, null);
}
private void StartOffsetAnimation()
{
var animation = _animatedVisual!.Compositor.CreateVector3KeyFrameAnimation();
animation.Target = "Offset";
animation.InsertKeyFrame(0f, new Vector3(CellStride, CellStride, 0), new LinearEasing());
animation.InsertKeyFrame(1f, new Vector3(CellStride * 3, CellStride * 3, 0), new LinearEasing());
animation.Duration = TimeSpan.FromSeconds(1);
animation.Direction = PlaybackDirection.Alternate;
animation.IterationBehavior = AnimationIterationBehavior.Forever;
_animatedVisual.StartAnimation("Offset", animation);
}
private void UpdateHitPoint()
{
var server = _animatedVisual!.Server;
var bounds = server.GetReadback(server.Compositor.Readback.LastCompletedWrite)!.TransformedSubtreeBounds!.Value;
_hitPoint = new Point((bounds.Left + bounds.Right) / 2, (bounds.Top + bounds.Bottom) / 2);
}
private static Canvas BuildDeepAnimatedGrid(int visualCount, out Size size, out Border target)
{
var branchCount = Math.Min(8, Math.Max(1, visualCount / 64));
var leavesPerBranch = (visualCount + branchCount - 1) / branchCount;
var columns = (int)Math.Ceiling(Math.Sqrt(leavesPerBranch + 1));
var rows = (leavesPerBranch + columns - 1) / columns;
var branchSize = new Size(columns * CellStride + CellStride * 4, rows * CellStride + CellStride * 4);
size = new Size(branchSize.Width * branchCount, branchSize.Height);
target = null!;
var root = new Canvas
{
Width = size.Width,
Height = size.Height
};
var remaining = visualCount;
for (var branch = 0; branch < branchCount; branch++)
{
var branchRoot = new Canvas
{
Width = branchSize.Width,
Height = branchSize.Height
};
Canvas.SetLeft(branchRoot, branch * branchSize.Width);
root.Children.Add(branchRoot);
var leafHost = branchRoot;
for (var depth = 0; depth < TreeDepth; depth++)
{
var nested = new Canvas
{
Width = branchSize.Width,
Height = branchSize.Height
};
leafHost.Children.Add(nested);
leafHost = nested;
}
var count = Math.Min(leavesPerBranch, remaining);
remaining -= count;
if (branch == 0)
count--;
for (var i = 0; i < count; i++)
{
var child = new Border
{
Width = CellSize,
Height = CellSize,
Background = Brushes.Red
};
Canvas.SetLeft(child, (i % columns) * CellStride);
Canvas.SetTop(child, (i / columns) * CellStride);
leafHost.Children.Add(child);
}
if (branch == 0)
{
target = new Border
{
Width = CellSize,
Height = CellSize,
Background = Brushes.Blue
};
Canvas.SetLeft(target, CellStride);
Canvas.SetTop(target, CellStride);
leafHost.Children.Add(target);
}
}
return root;
}
}
It seems that it may be better to set the threshold to 32? |
|
Will open a new PR with new numbers. |
I suspect that it will add allocation / memory footprint for little gains. Also, the animated child benchmark is actually more informative: it indicates when building the tree and hit-testing starts to take roughly the same time as just hit-testing. |
I opened a new PR with updated numbers after some optimizations, and included an actual test page. See #21310. |
4 participants
What does the pull request do?
Added an R-tree for composition hit testing. Instead of recursively walking every composition visual for each hit test,
CompositionTargetnow queries spatial candidates from an R-tree, restores topmost ordering, and then runs the existing exact transform/clip/filter/custom-hit-test checks.Also added a benchmark which uses a linear test as the reference baseline. Benchmark result:
The hit test performance improved by ~1430x with 16384 visuals, and reduced the allocation by 57%
What is the current behavior?
Composition hit testing walks the composition visual tree recursively.
HitTestFirstalso materializes the full hit list and then returns the first result, so pointer hit testing can scale linearly with the number of composition visuals.What is the updated/expected behavior with this PR?
Hit testing first queries an R-tree of transformed render-data AABBs to reduce the candidate set, then verifies candidates with the same exact checks used by the previous implementation.
HitTestFirstnow uses a direct first-hit path instead of collecting every matching visual first.How was the solution implemented (if it's not obvious)?
The R-tree is used to reduce candidates: it does not decide the final hit result by itself. The candidate order is restored to existing topmost-first order before exact hit testing. Exact verification still performs existing checks like transforms, visibility, clipping and etc.
ICustomHitTestvisuals are treated conservatively as unbounded candidates, since their hit region can extend outside normal render bounds.Checklist
Breaking changes
No