284250 2024-12-08 13:43:11 -0800 [TextureMapper] Preserve 3d may split layers unnecessarily when they don't intersect 2024-12-19 01:08:38 -0800 1 1 1 Unclassified WebKit WPE WebKit WebKit Nightly Build Unspecified Unspecified RESOLVED FIXED https://bugs.webkit.org/show_bug.cgi?id=284279 P2 Normal --- 283820 1 jani jani bugs-noreply fujii webkit-bug-importer zimmermann oldest_to_newest 2080013 0 jani 2024-12-08 13:43:11 -0800 The BSP (Binary Space Partitioning) calculation in the TextureMapper uses the 3D plane formula to determine layer ordering and splits layer primitives into two parts if they intersect. The implementation creates a plane formula for the layer polygon and checks if other layers intersect this plane. Since the plane spans infinitely across the entire scene, it may detect intersections of layers that are spatially distant from the tested layer polygon. This leads to incorrect splitting of layers, even when they don't physically intersect. To mitigate this issue, a preprocessing step using bounding volumes can be introduced before creating the BSP tree. This step would limit the calculation to only potentially intersecting volumes, improving accuracy and reducing unnecessary splits. 2080189 1 473511 jani 2024-12-09 07:03:09 -0800 Created attachment 473511 WIP patch 2080190 2 jani 2024-12-09 07:03:19 -0800 This change shows only marginal improvement on specific tests and does not significantly address the issues highlighted in Bug 283820. I have decided to set this aside for now and redirect my efforts toward Bug 284279. For reference, a WIP patch is attached. 2080284 3 fujii 2024-12-09 12:44:53 -0800 poster-circle has no intersecting layers. I think no needs to use stencil clipping if we can precisely compute intersecting layers and sort layers correctly. https://webkit.org/blog-files/3d-transforms/poster-circle.html 2080469 4 jani 2024-12-10 03:00:28 -0800 That's correct, the layers in the poster-circle example don’t actually intersect. The intersections arise from how the BSP tree splits the scene rather than from the layers themselves. I’ve tried to refine the BSP splitting logic, but ultimately the BSP tree must be constructed using splitting planes, so there’s limited flexibility there. In my WIP patch, I attempted using axis-aligned bounding boxes (AABBs) to detect collisions and pre-sort layers before entering the BSP phase. AABBs are computationally fast but they don’t yield correct results in this scenario because the poster-circle scene rotates and undergoes perspective transformations thus invalidating the assumptions AABBs rely on. Another approach might be oriented bounding boxes (OBBs), which would be more accurate but also significantly more expensive to compute. I’m still planning to explore that option to see how it performs on RPi3. The underlying cause of the regression (issue 283820) is that stencil usage on the RPi3 is very slow, whereas on many other platforms stencil operations are much faster. The ultimate fix for this is 284279. Skia includes a fast path that checks at runtime whether it can achieve clipping by rendering only a portion of the target when the clip is simple enough. Unfortunately, implementing a similar strategy in TextureMapper is challenging. TextureMapper was designed from the ground up with the assumption of rectangular rendering, making more advanced clipping techniques difficult to integrate without stencil usage. 2081418 5 jani 2024-12-12 20:38:03 -0800 I have OBB collision/intersection detection now in place and it resolves poster-circle regression. However, there's a regression. In certain scenarios, multiple layers appear to overlap from the viewer’s perspective, creating a situation where none of them are clearly frontmost. Even though no actual 3D intersection occurs in these cases, layers still need to be split to maintain correct visual ordering. When using 3d collision detection to filter out non-colliding layers, these purely visual overlap scenarios fail to render correctly. Although I was aware of these situations, I didn’t fully recognize until now that 3D intersection detection alone does not handle them. Attached an example. 2081420 6 473558 jani 2024-12-12 20:39:16 -0800 Created attachment 473558 Overlap test case 2081452 7 zimmermann 2024-12-13 00:42:13 -0800 That sounds promising Jani -- do you have ideas left how to fix the remaining regression with the solve-poster-circle-regression-patch? 2081454 8 jani 2024-12-13 01:04:13 -0800 I have a few ideas in mind, and I’ll start experimenting with them now. I’ve had limited time recently, but I’ll be able to devote more time on this now. 2082177 9 jani 2024-12-16 15:07:52 -0800 Pull request: https://github.com/WebKit/WebKit/pull/38039 2082953 10 ews-feeder 2024-12-19 01:08:35 -0800 Committed 288080@main (ca6c3486ddd3): <https://commits.webkit.org/288080@main> Reviewed commits have been landed. Closing PR #38039 and removing active labels. 473511 2024-12-09 07:03:09 -0800 2024-12-09 07:03:09 -0800 WIP patch 0001-TextureMapper-Preserve-3d-may-split-layers-unnecessa.patch text/plain 11545 jani RnJvbSBiZWNhYjBlZjczN2VhMzAyYWJkN2JiYzNiNmE5MjhmODIzMzNhNTk0IE1vbiBTZXAgMTcg MDA6MDA6MDAgMjAwMQpGcm9tOiBKYW5pIEhhdXRha2FuZ2FzIDxqYW5pQGtvZGVnb29kLmNvbT4K RGF0ZTogTW9uLCA5IERlYyAyMDI0IDE2OjU0OjE5ICswMjAwClN1YmplY3Q6IFtQQVRDSF0gW1Rl eHR1cmVNYXBwZXJdIFByZXNlcnZlIDNkIG1heSBzcGxpdCBsYXllcnMgdW5uZWNlc3NhcmlseQog d2hlbiB0aGV5IGRvbid0IGludGVyc2VjdCBodHRwczovL2J1Z3Mud2Via2l0Lm9yZy9zaG93X2J1 Zy5jZ2k/aWQ9Mjg0MjUwCgpSZXZpZXdlZCBieSBOT0JPRFkgKE9PUFMhKS4KCkV4cGxhbmF0aW9u IG9mIHdoeSB0aGlzIGZpeGVzIHRoZSBidWcgKE9PUFMhKS4KCiogU291cmNlL1dlYkNvcmUvcGxh dGZvcm0vZ3JhcGhpY3MvdGV4bWFwL1RleHR1cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4 dC5jcHA6CihXZWJDb3JlOjpUZXh0dXJlTWFwcGVyTGF5ZXIzRFJlbmRlcmluZ0NvbnRleHQ6OnBh aW50KToKKFdlYkNvcmU6OlRleHR1cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dDo6Y29t cHV0ZUJvdW5kaW5nQm94Rm9yTGF5ZXIpOgooV2ViQ29yZTo6VGV4dHVyZU1hcHBlckxheWVyM0RS ZW5kZXJpbmdDb250ZXh0OjpkZXB0aFNvcnRCb3VuZGluZ1ZvbHVtZXMpOgoqIFNvdXJjZS9XZWJD b3JlL3BsYXRmb3JtL2dyYXBoaWNzL3RleG1hcC9UZXh0dXJlTWFwcGVyTGF5ZXIzRFJlbmRlcmlu Z0NvbnRleHQuaDoKLS0tCiAuLi4vVGV4dHVyZU1hcHBlckxheWVyM0RSZW5kZXJpbmdDb250ZXh0 LmNwcCAgfCAxMzUgKysrKysrKysrKysrKy0tLS0tCiAuLi4vVGV4dHVyZU1hcHBlckxheWVyM0RS ZW5kZXJpbmdDb250ZXh0LmggICAgfCAgMzUgKysrKysKIDIgZmlsZXMgY2hhbmdlZCwgMTM3IGlu c2VydGlvbnMoKyksIDMzIGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL1NvdXJjZS9XZWJDb3Jl L3BsYXRmb3JtL2dyYXBoaWNzL3RleG1hcC9UZXh0dXJlTWFwcGVyTGF5ZXIzRFJlbmRlcmluZ0Nv bnRleHQuY3BwIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvdGV4bWFwL1RleHR1 cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dC5jcHAKaW5kZXggMDMxYWY3MDQwZjY2Li5m MWFlNjk0NTEzYjUgMTAwNjQ0Ci0tLSBhL1NvdXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNz L3RleG1hcC9UZXh0dXJlTWFwcGVyTGF5ZXIzRFJlbmRlcmluZ0NvbnRleHQuY3BwCisrKyBiL1Nv dXJjZS9XZWJDb3JlL3BsYXRmb3JtL2dyYXBoaWNzL3RleG1hcC9UZXh0dXJlTWFwcGVyTGF5ZXIz RFJlbmRlcmluZ0NvbnRleHQuY3BwCkBAIC0zMiw3ICszMiw2IEBACiAjaW5jbHVkZSAiRmxvYXRQ bGFuZTNELmgiCiAjaW5jbHVkZSAiVGV4dHVyZU1hcHBlckdQVUJ1ZmZlci5oIgogI2luY2x1ZGUg IlRleHR1cmVNYXBwZXJMYXllci5oIgotI2luY2x1ZGUgPHd0Zi9EZXF1ZS5oPgogI2luY2x1ZGUg PHd0Zi9UWm9uZU1hbGxvY0lubGluZXMuaD4KIAogbmFtZXNwYWNlIFdlYkNvcmUgewpAQCAtNDUs NTIgKzQ0LDEyMiBAQCB2b2lkIFRleHR1cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dDo6 cGFpbnQoVGV4dHVyZU1hcHBlciYgdGV4dHVyZU1hcHBlciwgYwogICAgIGlmIChsYXllcnMuaXNF bXB0eSgpKQogICAgICAgICByZXR1cm47CiAKLSAgICBEZXF1ZTxUZXh0dXJlTWFwcGVyTGF5ZXJQ b2x5Z29uPiBsYXllckxpc3Q7Ci0gICAgZm9yIChhdXRvKiBsYXllciA6IGxheWVycykKLSAgICAg ICAgbGF5ZXJMaXN0LmFwcGVuZCh7IHsgbGF5ZXItPmVmZmVjdGl2ZUxheWVyUmVjdCgpLCBsYXll ci0+dG9TdXJmYWNlVHJhbnNmb3JtKCkgfSwgbGF5ZXIsIGZhbHNlIH0pOworICAgIC8vIENvbXB1 dGUgYm91bmRpbmcgdm9sdW1lcy4gVGhlc2UgYXJlIGRpc3RpbmN0IGFyZWFzIHRoYXQgY2FuIGJl IHJlbmRlcmVkIGluZGVwZW5kZW50bHkuCisgICAgLy8gQm91bmRpbmcgdm9sdW1lcyBoZWxwIHJl c3RyaWN0IEJTUCBjdXR0aW5nIHBsYW5lcyB0byB0aGVpciByZXNwZWN0aXZlIGFyZWFzLCBwcmV2 ZW50aW5nCisgICAgLy8gdW5uZWNlc3Nhcnkgc3BsaXR0aW5nIG9mIGxheWVycyB0aGF0IGFyZSBz cGF0aWFsbHkgZGlzdGFudCBidXQgd291bGQgb3RoZXJ3aXNlIGludGVyc2VjdCB0aGUgY3V0dGlu ZyBwbGFuZS4KKyAgICBWZWN0b3I8Qm91bmRpbmdWb2x1bWU+IGJvdW5kaW5nVm9sdW1lczsKKyAg ICBmb3IgKGF1dG8qIGxheWVyIDogbGF5ZXJzKSB7CisgICAgICAgIFRleHR1cmVNYXBwZXJMYXll clBvbHlnb24gbGF5ZXJQb2x5Z29uKHsgbGF5ZXItPmVmZmVjdGl2ZUxheWVyUmVjdCgpLCBsYXll ci0+dG9TdXJmYWNlVHJhbnNmb3JtKCkgfSwgbGF5ZXIsIGZhbHNlKTsKKyAgICAgICAgYXV0byBs YXllckJvdW5kaW5nQm94ID0gY29tcHV0ZUJvdW5kaW5nQm94Rm9yTGF5ZXIobGF5ZXJQb2x5Z29u KTsKIAotICAgIGF1dG8gcm9vdCA9IG1ha2VVbmlxdWU8VGV4dHVyZU1hcHBlckxheWVyTm9kZT4o bGF5ZXJMaXN0LnRha2VGaXJzdCgpKTsKLSAgICBidWlsZFRyZWUoKnJvb3QsIGxheWVyTGlzdCk7 CisgICAgICAgIGJvb2wgYWRkZWRUb0V4aXN0aW5nQm91bmRpbmdWb2x1bWUgPSBmYWxzZTsKIAot ICAgIC8vIENvbGxlY3QgY2xpcCBkYXRhCisgICAgICAgIGZvciAoYXV0byYgYm91bmRpbmdWb2x1 bWUgOiBib3VuZGluZ1ZvbHVtZXMpIHsKKyAgICAgICAgICAgIGlmIChib3VuZGluZ1ZvbHVtZS5i b3VuZGluZ0JveC5pbnRlcnNlY3RzKGxheWVyQm91bmRpbmdCb3gpKSB7CisgICAgICAgICAgICAg ICAgYm91bmRpbmdWb2x1bWUuYm91bmRpbmdCb3guZXh0ZW5kKGxheWVyQm91bmRpbmdCb3gpOwor ICAgICAgICAgICAgICAgIGJvdW5kaW5nVm9sdW1lLmxheWVyTGlzdC5hcHBlbmQobGF5ZXJQb2x5 Z29uKTsKKyAgICAgICAgICAgICAgICBhZGRlZFRvRXhpc3RpbmdCb3VuZGluZ1ZvbHVtZSA9IHRy dWU7CisgICAgICAgICAgICAgICAgYnJlYWs7CisgICAgICAgICAgICB9CisgICAgICAgIH0KKwor ICAgICAgICBpZiAoIWFkZGVkVG9FeGlzdGluZ0JvdW5kaW5nVm9sdW1lKSB7CisgICAgICAgICAg ICBCb3VuZGluZ1ZvbHVtZSBuZXdCb3VuZGluZ1ZvbHVtZTsKKyAgICAgICAgICAgIG5ld0JvdW5k aW5nVm9sdW1lLmJvdW5kaW5nQm94ID0gbGF5ZXJCb3VuZGluZ0JveDsKKyAgICAgICAgICAgIG5l d0JvdW5kaW5nVm9sdW1lLmxheWVyTGlzdC5hcHBlbmQobGF5ZXJQb2x5Z29uKTsKKyAgICAgICAg ICAgIGJvdW5kaW5nVm9sdW1lcy5hcHBlbmQoV1RGTW92ZShuZXdCb3VuZGluZ1ZvbHVtZSkpOwor ICAgICAgICB9CisgICAgfQorCisgICAgZGVwdGhTb3J0Qm91bmRpbmdWb2x1bWVzKGJvdW5kaW5n Vm9sdW1lcyk7CisKKyAgICAvLyBCdWlsZCB0cmVlIGFuZCBjb2xsZWN0IGNsaXAgZGF0YSBmb3Ig YWxsIGJvdW5kaW5nIHZvbHVtZXMKICAgICBWZWN0b3I8ZmxvYXQ+IGNsaXBWZXJ0aWNlczsKLSAg ICB0cmF2ZXJzZVRyZWUoKnJvb3QsIFsmY2xpcFZlcnRpY2VzXShUZXh0dXJlTWFwcGVyTGF5ZXJO b2RlJiBub2RlKSB7Ci0gICAgICAgIGZvciAoYXV0byYgcG9seWdvbiA6IG5vZGUucG9seWdvbnMp IHsKLSAgICAgICAgICAgIGF1dG8gdG9MYXllclRyYW5zZm9ybSA9IHBvbHlnb24ubGF5ZXItPnRv U3VyZmFjZVRyYW5zZm9ybSgpLmludmVyc2UoKTsKLSAgICAgICAgICAgIGlmIChwb2x5Z29uLmlz U3BsaXR0ZWQgJiYgdG9MYXllclRyYW5zZm9ybSkgewotICAgICAgICAgICAgICAgIHBvbHlnb24u Y2xpcFZlcnRleEJ1ZmZlck9mZnNldCA9IGNsaXBWZXJ0aWNlcy5zaXplKCk7Ci0KLSAgICAgICAg ICAgICAgICB1bnNpZ25lZCBudW1WZXJ0aWNlcyA9IHBvbHlnb24uZ2VvbWV0cnkubnVtYmVyT2ZW ZXJ0aWNlcygpOwotICAgICAgICAgICAgICAgIGZvciAodW5zaWduZWQgaSA9IDA7IGkgPCBudW1W ZXJ0aWNlczsgaSsrKSB7Ci0gICAgICAgICAgICAgICAgICAgIGF1dG8gdiA9IHRvTGF5ZXJUcmFu c2Zvcm0tPm1hcFBvaW50KHBvbHlnb24uZ2VvbWV0cnkudmVydGV4QXQoaSkpOwotICAgICAgICAg ICAgICAgICAgICBjbGlwVmVydGljZXMuYXBwZW5kKHYueCgpKTsKLSAgICAgICAgICAgICAgICAg ICAgY2xpcFZlcnRpY2VzLmFwcGVuZCh2LnkoKSk7CisgICAgZm9yIChhdXRvJiBib3VuZGluZ1Zv bHVtZSA6IGJvdW5kaW5nVm9sdW1lcykgeworICAgICAgICBib3VuZGluZ1ZvbHVtZS5ic3BSb290 ID0gbWFrZVVuaXF1ZTxUZXh0dXJlTWFwcGVyTGF5ZXJOb2RlPihib3VuZGluZ1ZvbHVtZS5sYXll ckxpc3QudGFrZUZpcnN0KCkpOworICAgICAgICBidWlsZFRyZWUoKmJvdW5kaW5nVm9sdW1lLmJz cFJvb3QsIGJvdW5kaW5nVm9sdW1lLmxheWVyTGlzdCk7CisKKyAgICAgICAgdHJhdmVyc2VUcmVl KCpib3VuZGluZ1ZvbHVtZS5ic3BSb290LCBbJmNsaXBWZXJ0aWNlc10oVGV4dHVyZU1hcHBlckxh eWVyTm9kZSYgbm9kZSkgeworICAgICAgICAgICAgZm9yIChhdXRvJiBwb2x5Z29uIDogbm9kZS5w b2x5Z29ucykgeworICAgICAgICAgICAgICAgIGF1dG8gdG9MYXllclRyYW5zZm9ybSA9IHBvbHln b24ubGF5ZXItPnRvU3VyZmFjZVRyYW5zZm9ybSgpLmludmVyc2UoKTsKKyAgICAgICAgICAgICAg ICBpZiAocG9seWdvbi5pc1NwbGl0dGVkICYmIHRvTGF5ZXJUcmFuc2Zvcm0pIHsKKyAgICAgICAg ICAgICAgICAgICAgcG9seWdvbi5jbGlwVmVydGV4QnVmZmVyT2Zmc2V0ID0gY2xpcFZlcnRpY2Vz LnNpemUoKTsKKworICAgICAgICAgICAgICAgICAgICB1bnNpZ25lZCBudW1WZXJ0aWNlcyA9IHBv bHlnb24uZ2VvbWV0cnkubnVtYmVyT2ZWZXJ0aWNlcygpOworICAgICAgICAgICAgICAgICAgICBm b3IgKHVuc2lnbmVkIGkgPSAwOyBpIDwgbnVtVmVydGljZXM7IGkrKykgeworICAgICAgICAgICAg ICAgICAgICAgICAgYXV0byB2ID0gdG9MYXllclRyYW5zZm9ybS0+bWFwUG9pbnQocG9seWdvbi5n ZW9tZXRyeS52ZXJ0ZXhBdChpKSk7CisgICAgICAgICAgICAgICAgICAgICAgICBjbGlwVmVydGlj ZXMuYXBwZW5kKHYueCgpKTsKKyAgICAgICAgICAgICAgICAgICAgICAgIGNsaXBWZXJ0aWNlcy5h cHBlbmQodi55KCkpOworICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgfQog ICAgICAgICAgICAgfQotICAgICAgICB9Ci0gICAgfSk7CisgICAgICAgIH0pOworICAgIH0KIAog ICAgIHVuc2lnbmVkIGNsaXBCdWZmZXJTaXplID0gY2xpcFZlcnRpY2VzLnNpemUoKSAqIHNpemVv ZihmbG9hdCk7CiAgICAgYXV0byBjbGlwQnVmZmVyID0gdGV4dHVyZU1hcHBlci5hY3F1aXJlQnVm ZmVyRnJvbVBvb2woY2xpcEJ1ZmZlclNpemUsIFRleHR1cmVNYXBwZXJHUFVCdWZmZXI6OlR5cGU6 OlZlcnRleCk7CiAgICAgY2xpcEJ1ZmZlci0+dXBkYXRlRGF0YShjbGlwVmVydGljZXMuZGF0YSgp LCAwLCBjbGlwQnVmZmVyU2l6ZSk7CiAKICAgICAvLyBQYWludAotICAgIHRyYXZlcnNlVHJlZSgq cm9vdCwgWyZjbGlwVmVydGljZXMsICZjbGlwQnVmZmVyLCAmcGFpbnRMYXllckZ1bmN0aW9uXShU ZXh0dXJlTWFwcGVyTGF5ZXJOb2RlJiBub2RlKSB7Ci0gICAgICAgIGZvciAoYXV0byYgcG9seWdv biA6IG5vZGUucG9seWdvbnMpIHsKLSAgICAgICAgICAgIHVuc2lnbmVkIG51bWJlck9mQ2xpcFZl cnRpY2VzID0gcG9seWdvbi5pc1NwbGl0dGVkID8gcG9seWdvbi5nZW9tZXRyeS5udW1iZXJPZlZl cnRpY2VzKCkgOiAwOwotCi0gICAgICAgICAgICBWZWN0b3I8RmxvYXRQb2ludD4gcG9pbnRzOwot ICAgICAgICAgICAgaWYgKG51bWJlck9mQ2xpcFZlcnRpY2VzID4gMCkgewotICAgICAgICAgICAg ICAgIHBvaW50cy5yZXNlcnZlQ2FwYWNpdHkobnVtYmVyT2ZDbGlwVmVydGljZXMpOwotICAgICAg ICAgICAgICAgIGF1dG8geHkgPSBjbGlwVmVydGljZXMuc3VidmVjdG9yKHBvbHlnb24uY2xpcFZl cnRleEJ1ZmZlck9mZnNldCwgbnVtYmVyT2ZDbGlwVmVydGljZXMgKiAyKTsKLSAgICAgICAgICAg ICAgICBmb3IgKHNpemVfdCBpID0gMDsgaSA8IHh5LnNpemUoKTsgaSArPSAyKQotICAgICAgICAg ICAgICAgICAgICBwb2ludHMuYXBwZW5kKEZsb2F0UG9pbnQoeHkuYXQoaSksIHh5LmF0KGkgKyAx KSkpOworICAgIGZvciAoYXV0byYgYm91bmRpbmdWb2x1bWUgOiBib3VuZGluZ1ZvbHVtZXMpIHsK KyAgICAgICAgaWYgKGJvdW5kaW5nVm9sdW1lLmxheWVyTGlzdC5zaXplKCkgPiAxKQorICAgICAg ICAgICAgY29udGludWU7CisgICAgICAgIHRyYXZlcnNlVHJlZSgqYm91bmRpbmdWb2x1bWUuYnNw Um9vdCwgWyZjbGlwVmVydGljZXMsICZjbGlwQnVmZmVyLCAmcGFpbnRMYXllckZ1bmN0aW9uXShU ZXh0dXJlTWFwcGVyTGF5ZXJOb2RlJiBub2RlKSB7CisgICAgICAgICAgICBmb3IgKGF1dG8mIHBv bHlnb24gOiBub2RlLnBvbHlnb25zKSB7CisgICAgICAgICAgICAgICAgdW5zaWduZWQgbnVtYmVy T2ZDbGlwVmVydGljZXMgPSBwb2x5Z29uLmlzU3BsaXR0ZWQgPyBwb2x5Z29uLmdlb21ldHJ5Lm51 bWJlck9mVmVydGljZXMoKSA6IDA7CisKKyAgICAgICAgICAgICAgICBWZWN0b3I8RmxvYXRQb2lu dD4gcG9pbnRzOworICAgICAgICAgICAgICAgIGlmIChudW1iZXJPZkNsaXBWZXJ0aWNlcyA+IDAp IHsKKyAgICAgICAgICAgICAgICAgICAgcG9pbnRzLnJlc2VydmVDYXBhY2l0eShudW1iZXJPZkNs aXBWZXJ0aWNlcyk7CisgICAgICAgICAgICAgICAgICAgIGF1dG8geHkgPSBjbGlwVmVydGljZXMu c3VidmVjdG9yKHBvbHlnb24uY2xpcFZlcnRleEJ1ZmZlck9mZnNldCwgbnVtYmVyT2ZDbGlwVmVy dGljZXMgKiAyKTsKKyAgICAgICAgICAgICAgICAgICAgZm9yIChzaXplX3QgaSA9IDA7IGkgPCB4 eS5zaXplKCk7IGkgKz0gMikKKyAgICAgICAgICAgICAgICAgICAgICAgIHBvaW50cy5hcHBlbmQo RmxvYXRQb2ludCh4eS5hdChpKSwgeHkuYXQoaSArIDEpKSk7CisgICAgICAgICAgICAgICAgfQor CisgICAgICAgICAgICAgICAgQ2xpcFBhdGggY2xpcFBhdGgoV1RGTW92ZShwb2ludHMpLCBjbGlw QnVmZmVyLT5idWZmZXJJRCgpLCBwb2x5Z29uLmNsaXBWZXJ0ZXhCdWZmZXJPZmZzZXQgKiBzaXpl b2YoZmxvYXQpKTsKKworICAgICAgICAgICAgICAgIHBhaW50TGF5ZXJGdW5jdGlvbihwb2x5Z29u LmxheWVyLCBjbGlwUGF0aCk7CiAgICAgICAgICAgICB9CisgICAgICAgIH0pOworICAgIH0KK30K IAotICAgICAgICAgICAgQ2xpcFBhdGggY2xpcFBhdGgoV1RGTW92ZShwb2ludHMpLCBjbGlwQnVm ZmVyLT5idWZmZXJJRCgpLCBwb2x5Z29uLmNsaXBWZXJ0ZXhCdWZmZXJPZmZzZXQgKiBzaXplb2Yo ZmxvYXQpKTsKK1RleHR1cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dDo6QXhpc0FsaWdu ZWRCb3VuZGluZ0JveAorVGV4dHVyZU1hcHBlckxheWVyM0RSZW5kZXJpbmdDb250ZXh0Ojpjb21w dXRlQm91bmRpbmdCb3hGb3JMYXllcihjb25zdCBUZXh0dXJlTWFwcGVyTGF5ZXJQb2x5Z29uJiBs YXllclBvbHlnb24pCit7CisgICAgRmxvYXRQb2ludDNEIG1pbkNvcm5lciA9ICBsYXllclBvbHln b24uZ2VvbWV0cnkudmVydGV4QXQoMCk7CisgICAgRmxvYXRQb2ludDNEIG1heENvcm5lciA9IGxh eWVyUG9seWdvbi5nZW9tZXRyeS52ZXJ0ZXhBdCgwKTsKIAotICAgICAgICAgICAgcGFpbnRMYXll ckZ1bmN0aW9uKHBvbHlnb24ubGF5ZXIsIGNsaXBQYXRoKTsKLSAgICAgICAgfQorICAgIHVuc2ln bmVkIG51bVZlcnRpY2VzID0gbGF5ZXJQb2x5Z29uLmdlb21ldHJ5Lm51bWJlck9mVmVydGljZXMo KTsKKyAgICBmb3IgKHVuc2lnbmVkIGkgPSAxOyBpIDwgbnVtVmVydGljZXM7IGkrKykgeworICAg ICAgICBhdXRvIHBvaW50ID0gbGF5ZXJQb2x5Z29uLmdlb21ldHJ5LnZlcnRleEF0KGkpOworICAg ICAgICBtaW5Db3JuZXIuc2V0WChzdGQ6Om1pbihtaW5Db3JuZXIueCgpLCBwb2ludC54KCkpKTsK KyAgICAgICAgbWluQ29ybmVyLnNldFkoc3RkOjptaW4obWluQ29ybmVyLnkoKSwgcG9pbnQueSgp KSk7CisgICAgICAgIG1pbkNvcm5lci5zZXRaKHN0ZDo6bWluKG1pbkNvcm5lci56KCksIHBvaW50 LnooKSkpOworCisgICAgICAgIG1heENvcm5lci5zZXRYKHN0ZDo6bWF4KG1heENvcm5lci54KCks IHBvaW50LngoKSkpOworICAgICAgICBtYXhDb3JuZXIuc2V0WShzdGQ6Om1heChtYXhDb3JuZXIu eSgpLCBwb2ludC55KCkpKTsKKyAgICAgICAgbWF4Q29ybmVyLnNldFooc3RkOjptYXgobWF4Q29y bmVyLnooKSwgcG9pbnQueigpKSk7CisgICAgfQorCisgICAgcmV0dXJuIHttaW5Db3JuZXIsIG1h eENvcm5lcn07Cit9CisKK3ZvaWQgVGV4dHVyZU1hcHBlckxheWVyM0RSZW5kZXJpbmdDb250ZXh0 OjpkZXB0aFNvcnRCb3VuZGluZ1ZvbHVtZXMoVmVjdG9yPEJvdW5kaW5nVm9sdW1lPiYgYm91bmRp bmdWb2x1bWVzKQoreworICAgIHN0YXRpYyBhdXRvIGNvbXB1dGVDZW50ZXIgPSBbXShjb25zdCBB eGlzQWxpZ25lZEJvdW5kaW5nQm94JiBhYWJiKSB7CisgICAgICAgIHJldHVybiBGbG9hdFBvaW50 M0QoCisgICAgICAgICAgICAoYWFiYi5taW5Db3JuZXIueCgpICsgYWFiYi5tYXhDb3JuZXIueCgp KSAvIDIsCisgICAgICAgICAgICAoYWFiYi5taW5Db3JuZXIueSgpICsgYWFiYi5tYXhDb3JuZXIu eSgpKSAvIDIsCisgICAgICAgICAgICAoYWFiYi5taW5Db3JuZXIueigpICsgYWFiYi5tYXhDb3Ju ZXIueigpKSAvIDIKKyAgICAgICAgKTsKKyAgICB9OworCisgICAgc3RkOjpzb3J0KGJvdW5kaW5n Vm9sdW1lcy5iZWdpbigpLCBib3VuZGluZ1ZvbHVtZXMuZW5kKCksIFtdKGNvbnN0IEJvdW5kaW5n Vm9sdW1lJiBhLCBjb25zdCBCb3VuZGluZ1ZvbHVtZSYgYikgeworICAgICAgICBGbG9hdFBvaW50 M0QgY2VudGVyQSA9IGNvbXB1dGVDZW50ZXIoYS5ib3VuZGluZ0JveCk7CisgICAgICAgIEZsb2F0 UG9pbnQzRCBjZW50ZXJCID0gY29tcHV0ZUNlbnRlcihiLmJvdW5kaW5nQm94KTsKKworICAgICAg ICByZXR1cm4gY2VudGVyQS56KCkgPCBjZW50ZXJCLnooKTsKICAgICB9KTsKIH0KIApkaWZmIC0t Z2l0IGEvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvdGV4bWFwL1RleHR1cmVNYXBw ZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dC5oIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3Jh cGhpY3MvdGV4bWFwL1RleHR1cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dC5oCmluZGV4 IDIyOWQzZTdlZjY2Ny4uMTFmM2YxOWRjYzg2IDEwMDY0NAotLS0gYS9Tb3VyY2UvV2ViQ29yZS9w bGF0Zm9ybS9ncmFwaGljcy90ZXhtYXAvVGV4dHVyZU1hcHBlckxheWVyM0RSZW5kZXJpbmdDb250 ZXh0LmgKKysrIGIvU291cmNlL1dlYkNvcmUvcGxhdGZvcm0vZ3JhcGhpY3MvdGV4bWFwL1RleHR1 cmVNYXBwZXJMYXllcjNEUmVuZGVyaW5nQ29udGV4dC5oCkBAIC0yOCw2ICsyOCw3IEBACiAjcHJh Z21hIG9uY2UKIAogI2luY2x1ZGUgIkZsb2F0UG9seWdvbjNELmgiCisjaW5jbHVkZSA8d3RmL0Rl cXVlLmg+CiAjaW5jbHVkZSA8d3RmL1Rab25lTWFsbG9jLmg+CiAKIG5hbWVzcGFjZSBXZWJDb3Jl IHsKQEAgLTU4LDYgKzU5LDI5IEBAIHByaXZhdGU6CiAgICAgICAgIHVuc2lnbmVkIGNsaXBWZXJ0 ZXhCdWZmZXJPZmZzZXQgeyAwIH07CiAgICAgfTsKIAorICAgIHN0cnVjdCBBeGlzQWxpZ25lZEJv dW5kaW5nQm94IHsKKyAgICAgICAgV1RGX01BS0VfU1RSVUNUX0ZBU1RfQUxMT0NBVEVEOworCisg ICAgICAgIGJvb2wgaW50ZXJzZWN0cyhjb25zdCBBeGlzQWxpZ25lZEJvdW5kaW5nQm94JiBvdGhl cikgY29uc3QgeworICAgICAgICAgICAgcmV0dXJuIChtaW5Db3JuZXIueCgpIDw9IG90aGVyLm1h eENvcm5lci54KCkgJiYgbWF4Q29ybmVyLngoKSA+PSBvdGhlci5taW5Db3JuZXIueCgpKSAmJgor ICAgICAgICAgICAgICAgIChtaW5Db3JuZXIueSgpIDw9IG90aGVyLm1heENvcm5lci55KCkgJiYg bWF4Q29ybmVyLnkoKSA+PSBvdGhlci5taW5Db3JuZXIueSgpKSAmJgorICAgICAgICAgICAgICAg IChtaW5Db3JuZXIueigpIDw9IG90aGVyLm1heENvcm5lci56KCkgJiYgbWF4Q29ybmVyLnooKSA+ PSBvdGhlci5taW5Db3JuZXIueigpKTsKKyAgICAgICAgfQorCisgICAgICAgIHZvaWQgZXh0ZW5k KGNvbnN0IEF4aXNBbGlnbmVkQm91bmRpbmdCb3gmIG90aGVyKSB7CisgICAgICAgICAgICBtaW5D b3JuZXIuc2V0WChzdGQ6Om1pbihtaW5Db3JuZXIueCgpLCBvdGhlci5taW5Db3JuZXIueCgpKSk7 CisgICAgICAgICAgICBtaW5Db3JuZXIuc2V0WShzdGQ6Om1pbihtaW5Db3JuZXIueSgpLCBvdGhl ci5taW5Db3JuZXIueSgpKSk7CisgICAgICAgICAgICBtaW5Db3JuZXIuc2V0WihzdGQ6Om1pbiht aW5Db3JuZXIueigpLCBvdGhlci5taW5Db3JuZXIueigpKSk7CisKKyAgICAgICAgICAgIG1heENv cm5lci5zZXRYKHN0ZDo6bWF4KG1heENvcm5lci54KCksIG90aGVyLm1heENvcm5lci54KCkpKTsK KyAgICAgICAgICAgIG1heENvcm5lci5zZXRZKHN0ZDo6bWF4KG1heENvcm5lci55KCksIG90aGVy Lm1heENvcm5lci55KCkpKTsKKyAgICAgICAgICAgIG1heENvcm5lci5zZXRaKHN0ZDo6bWF4KG1h eENvcm5lci56KCksIG90aGVyLm1heENvcm5lci56KCkpKTsKKyAgICAgICAgfQorCisgICAgICAg IEZsb2F0UG9pbnQzRCBtaW5Db3JuZXI7CisgICAgICAgIEZsb2F0UG9pbnQzRCBtYXhDb3JuZXI7 CisgICAgfTsKKwogICAgIHN0cnVjdCBUZXh0dXJlTWFwcGVyTGF5ZXJOb2RlIGZpbmFsIHsKICAg ICAgICAgV1RGX01BS0VfU1RSVUNUX0ZBU1RfQUxMT0NBVEVEOwogCkBAIC03Myw2ICs5NywxNyBA QCBwcml2YXRlOgogICAgICAgICBzdGQ6OnVuaXF1ZV9wdHI8VGV4dHVyZU1hcHBlckxheWVyTm9k ZT4gYmFja05vZGU7CiAgICAgfTsKIAorICAgIHN0cnVjdCBCb3VuZGluZ1ZvbHVtZSBmaW5hbCB7 CisgICAgICAgIFdURl9NQUtFX1NUUlVDVF9GQVNUX0FMTE9DQVRFRDsKKworICAgICAgICBBeGlz QWxpZ25lZEJvdW5kaW5nQm94IGJvdW5kaW5nQm94OworICAgICAgICBEZXF1ZTxUZXh0dXJlTWFw cGVyTGF5ZXJQb2x5Z29uPiBsYXllckxpc3Q7CisgICAgICAgIHN0ZDo6dW5pcXVlX3B0cjxUZXh0 dXJlTWFwcGVyTGF5ZXJOb2RlPiBic3BSb290OworICAgIH07CisKKworICAgIEF4aXNBbGlnbmVk Qm91bmRpbmdCb3ggY29tcHV0ZUJvdW5kaW5nQm94Rm9yTGF5ZXIoY29uc3QgVGV4dHVyZU1hcHBl ckxheWVyUG9seWdvbiYpOworICAgIHZvaWQgZGVwdGhTb3J0Qm91bmRpbmdWb2x1bWVzKFZlY3Rv cjxCb3VuZGluZ1ZvbHVtZT4mKTsKICAgICB2b2lkIGJ1aWxkVHJlZShUZXh0dXJlTWFwcGVyTGF5 ZXJOb2RlJiwgRGVxdWU8VGV4dHVyZU1hcHBlckxheWVyUG9seWdvbj4mKTsKICAgICB2b2lkIHRy YXZlcnNlVHJlZShUZXh0dXJlTWFwcGVyTGF5ZXJOb2RlJiwgY29uc3Qgc3RkOjpmdW5jdGlvbjx2 b2lkKFRleHR1cmVNYXBwZXJMYXllck5vZGUmKT4mKTsKICAgICBzdGF0aWMgUG9seWdvblBvc2l0 aW9uIGNsYXNzaWZ5UG9seWdvbihjb25zdCBUZXh0dXJlTWFwcGVyTGF5ZXJQb2x5Z29uJiwgY29u c3QgRmxvYXRQbGFuZTNEJik7Ci0tIAoyLjQzLjAKCg== 473558 2024-12-12 20:39:16 -0800 2024-12-12 20:39:16 -0800 Overlap test case tris.html text/html 1918 jani PCFET0NUWVBFIGh0bWw+CjxodG1sIGxhbmc9ImVuIj4KPGhlYWQ+CiAgICA8bWV0YSBjaGFyc2V0 PSJVVEYtOCI+CiAgICA8bWV0YSBuYW1lPSJ2aWV3cG9ydCIgY29udGVudD0id2lkdGg9ZGV2aWNl LXdpZHRoLCBpbml0aWFsLXNjYWxlPTEuMCI+CiAgICA8dGl0bGU+M0Qgb3ZlcmxhcDwvdGl0bGU+ CiAgICA8c3R5bGU+CiAgICAgICAgYm9keSB7CiAgICAgICAgICAgIG1hcmdpbjogMTBweDsKICAg ICAgICAgICAgbWFyZ2luOiAwcHg7CiAgICAgICAgICAgIGRpc3BsYXk6IGZsZXg7CiAgICAgICAg ICAgIGp1c3RpZnktY29udGVudDogY2VudGVyOwogICAgICAgICAgICBhbGlnbi1pdGVtczogY2Vu dGVyOwogICAgICAgICAgICBoZWlnaHQ6IDEwMHZoOwogICAgICAgIH0KCiAgICAgICAgLnNjZW5l IHsKICAgICAgICAgICAgd2lkdGg6IDUwMHB4OwogICAgICAgICAgICBoZWlnaHQ6IDUwMHB4Owog ICAgICAgICAgICBwZXJzcGVjdGl2ZTogMTIwMHB4OwogICAgICAgIH0KCiAgICAgICAgLmNvbnRh aW5lciB7CiAgICAgICAgICAgIHdpZHRoOiA1MDBweDsKICAgICAgICAgICAgaGVpZ2h0OiA1MDBw eDsKICAgICAgICAgICAgdHJhbnNmb3JtLXN0eWxlOiBwcmVzZXJ2ZS0zZDsKICAgICAgICAgICAg LXdlYmtpdC1hbmltYXRpb246IHNwaW4gMTBzIGluZmluaXRlIGxpbmVhcjsKICAgICAgICB9Cgog ICAgICAgIC5sYXllciB7CiAgICAgICAgICAgIHBvc2l0aW9uOiBhYnNvbHV0ZTsKICAgICAgICAg ICAgdG9wOiAwcHg7CiAgICAgICAgICAgIGxlZnQ6IDBweDsKICAgICAgICAgICAgd2lkdGg6IDUw MHB4OwogICAgICAgICAgICBoZWlnaHQ6IDgwcHg7CiAgICAgICAgICAgIG9wYWNpdHk6IDUwJTsK ICAgICAgICB9CgogICAgICAgIC5sYXllcjEgewogICAgICAgICAgICBiYWNrZ3JvdW5kOiByZWQ7 CiAgICAgICAgICAgIHRyYW5zZm9ybTogdHJhbnNsYXRlWigxMHB4KSB0cmFuc2xhdGVZKDBweCkg cm90YXRlWSgxMmRlZyk7CiAgICAgICAgfQoKICAgICAgICAubGF5ZXIyIHsKICAgICAgICAgICAg YmFja2dyb3VuZDogYmx1ZTsKCSAgICAgICAgICB0cmFuc2Zvcm0tb3JpZ2luOiB0b3AgbGVmdDsK ICAgICAgICAgICAgdHJhbnNmb3JtOiB0cmFuc2xhdGVYKDIwcHgpIHRyYW5zbGF0ZVooOHB4KSB0 cmFuc2xhdGVZKC00MHB4KSByb3RhdGVaKDQ1ZGVnKSByb3RhdGVZKC01ZGVnKTsKICAgICAgICB9 CgogICAgICAgIC5sYXllcjMgewogICAgICAgICAgICBiYWNrZ3JvdW5kOiB5ZWxsb3c7CgkgICAg ICAgICAgdHJhbnNmb3JtLW9yaWdpbjogdG9wIHJpZ2h0OwogICAgICAgICAgICB0cmFuc2Zvcm06 IHRyYW5zbGF0ZVgoLTIwcHgpIHRyYW5zbGF0ZVooMTJweCkgdHJhbnNsYXRlWSgtNDBweCkgcm90 YXRlWigtNDVkZWcpIHJvdGF0ZVkoLTVkZWcpOwogICAgICAgIH0KCiAgICAgICAgQC13ZWJraXQt a2V5ZnJhbWVzIHNwaW4gewogICAgICAgICAgZnJvbSB7IC13ZWJraXQtdHJhbnNmb3JtOiByb3Rh dGVZKDApOyB9CiAgICAgICAgICB0byAgIHsgLXdlYmtpdC10cmFuc2Zvcm06IHJvdGF0ZVkoMzYw ZGVnKTsgfQogICAgICAgIH0KICAgIDwvc3R5bGU+CjwvaGVhZD4KPGJvZHk+CiAgICA8ZGl2IGNs YXNzPSJzY2VuZSI+CiAgICAgICAgPGRpdiBjbGFzcz0iY29udGFpbmVyIj4KICAgICAgICAgICAg PGRpdiBjbGFzcz0ibGF5ZXIgbGF5ZXIxIj48Y2VudGVyPjxoMT5MYXllciAxPC9oMT48L2NlbnRl cj48L2Rpdj4KICAgICAgICAgICAgPGRpdiBjbGFzcz0ibGF5ZXIgbGF5ZXIyIj48Y2VudGVyPjxo MT5MYXllciAyPC9oMT48L2NlbnRlcj48L2Rpdj4KICAgICAgICAgICAgPGRpdiBjbGFzcz0ibGF5 ZXIgbGF5ZXIzIj48Y2VudGVyPjxoMT5MYXllciAzPC9oMT48L2NlbnRlcj48L2Rpdj4KICAgICAg ICA8L2Rpdj4KICAgIDwvZGl2Pgo8L2JvZHk+CjwvaHRtbD4KCg==