Dunno if you want my stuff?

crener commented 3 years ago

Hey, I've been playing around with this for a little bit and added/changed a bunch of things. I think that other people would find it useful to get these changes as it adds a bunch of stuff but I dunno if you want to pull them all in?

Changes:

Added Circular query shape
Added basic job based queries
Added demo scene for visually showing queries
Changed namespacing, broke up the massive multi-file partial class, some stylistic changes - potentially breaking change
Moved files around into sub folders where I think it makes sense
Added assembly definitions to better split this code from projects using it
Added some basic tests to check query shape collision logic
Changed readme to include demo scene preview image
Added editor only check to assert when trying to add an entry into a leaf that exceeds the node capacity (great for sanity checking)
Got some experimental code that will try to parallelise bulk adding operations (still needs some work though)

Figured I'd drop a line here cause most people wouldn't click through all the Forks to see if there are improvements in them

marijnz commented 3 years ago

Hey,That's awesome. I'm currently on holidays (no laptop) till 11 sep. but will then definitely look at this!On Aug 30, 2021 17:46, Martin Kruger @.***> wrote:Hey, I've been playing around with this for a little bit and added/changed a bunch of things. I think that other people would find it useful to get these changes as it adds a bunch of stuff but I dunno if you want to pull them all in? Changes: Added Circular query shapeAdded basic job based queriesAdded demo scene for visually showing queriesChanged namespacing, broke up the massive multi-file partial class, some stylistic changes - potentially breaking changeMoved files around into sub folders where I think it makes senseAdded assembly definitions to better split this code from projects using itAdded some basic tests to check query shape collision logicChanged readme to include demo scene preview imageAdded editor only check to assert when trying to add an entry into a leaf that exceeds the node capacity (great for sanity checking)Got some experimental code that will try to parallelise bulk adding operations (still needs some work though) Figured I'd drop a line here cause most people wouldn't click through all the Forks to see if there are improvements in them

You can view, comment on, or merge this pull request online at: https://github.com/marijnz/NativeQuadtree/pull/11

Commit Summary Fixed tests, added assembly definitions, got compiling with up to date pacakgesAdded Circle Range Query TypeAllow better native compatabilityImproved burst compatability, alternate way to bulk add entries with more parallelismMajor organisation of file structureFixed some collision calculation logic when using circle and added unit testsFixed issues with Circle Range queries, added unit tests for correct intersection behaviourCreated demo scene for debugging results, Fixed inacurate circle results, added more tests, updated solution to 2021.2Found and fixed edge case where center of circle was outside the tested boxAdded example image to readmefix type in readme

File Changes

M
Assets/AABB2D.cs
(146)

A
Assets/Circle2D.cs
(62)

R
Assets/Circle2D.cs.meta
(2)

A
Assets/Editor/CollisionShapeTests.cs
(292)

A
Assets/Editor/CollisionShapeTests.cs.meta
(11)

A
Assets/Editor/NativeQuadTree.Editor.asmdef
(21)

A
Assets/Editor/NativeQuadTree.Editor.asmdef.meta
(7)

M
Assets/Editor/QuadTreeDrawer.cs
(11)

M
Assets/Editor/QuadTreeTests.cs
(34)

A
Assets/Example.meta
(8)

A
Assets/Example/NativeQuadTree.Example.asmdef
(19)

A
Assets/Example/NativeQuadTree.Example.asmdef.meta
(7)

A
Assets/Example/NativeQuadTreeCreator.cs
(121)

A
Assets/Example/NativeQuadTreeCreator.cs.meta
(11)

A
Assets/Example/NativeQueryCircle.cs
(68)

A
Assets/Example/NativeQueryCircle.cs.meta
(11)

A
Assets/Example/NativeQueryRect.cs
(84)

A
Assets/Example/NativeQueryRect.cs.meta
(3)

A
Assets/Example/Test Scene.unity
(353)

A
Assets/Example/Test Scene.unity.meta
(7)

A
Assets/Helpers.meta
(8)

A
Assets/Helpers/ArraySizeHelpers.cs
(41)

A
Assets/Helpers/ArraySizeHelpers.cs.meta
(3)

R
Assets/Helpers/LookupTables.cs
(0)

A
Assets/Helpers/LookupTables.cs.meta
(11)

A
Assets/Helpers/NativeQuadTreeDrawHelpers.cs
(73)

A
Assets/Helpers/NativeQuadTreeDrawHelpers.cs.meta
(11)

A
Assets/Jobs.meta
(8)

A
Assets/Jobs/AddBulkJob.cs
(34)

A
Assets/Jobs/AddBulkJob.cs.meta
(11)

A
Assets/Jobs/CircleQueryJob.cs
(36)

A
Assets/Jobs/CircleQueryJob.cs.meta
(11)

A
Assets/Jobs/Internal.meta
(8)

A
Assets/Jobs/Internal/QuadTreeCircleRangeQuery.cs
(91)

A
Assets/Jobs/Internal/QuadTreeCircleRangeQuery.cs.meta
(11)

A
Assets/Jobs/Internal/QuadTreeRectRangeQuery.cs
(91)

A
Assets/Jobs/Internal/QuadTreeRectRangeQuery.cs.meta
(11)

A
Assets/Jobs/Internal/RangeQueryHelpers.cs
(22)

A
Assets/Jobs/Internal/RangeQueryHelpers.cs.meta
(3)

A
Assets/Jobs/NativeQuadTreeParallelAdd.cs
(196)

A
Assets/Jobs/NativeQuadTreeParallelAdd.cs.meta
(11)

A
Assets/Jobs/RangeQueryJob.cs
(32)

A
Assets/Jobs/RangeQueryJob.cs.meta
(11)

A
Assets/Jobs/RectQueryJob.cs
(36)

A
Assets/Jobs/RectQueryJob.cs.meta
(3)

D
Assets/LookupTables.cs.meta
(3)

A
Assets/NativeQuadTree.asmdef
(19)

A
Assets/NativeQuadTree.asmdef.meta
(7)

M
Assets/NativeQuadTree.cs
(216)

D
Assets/NativeQuadTreeDrawing.cs
(74)

D
Assets/NativeQuadTreeDrawing.cs.meta
(3)

D
Assets/NativeQuadTreeRangeQuery.cs
(110)

A
Assets/QuadElement.cs
(13)

A
Assets/QuadElement.cs.meta
(3)

A
Assets/QuadNode.cs
(12)

A
Assets/QuadNode.cs.meta
(3)

D
Assets/QuadTreeJobs.cs
(54)

D
Assets/QuadTreeJobs.cs.meta
(3)

A
Assets/package.json
(20)

A
Assets/package.json.meta
(7)

A
Demo Scene.PNG
(0)

M
Packages/manifest.json
(21)

A
Packages/packages-lock.json
(566)

A
ProjectSettings/BurstAotSettings_Android.json
(13)

A
ProjectSettings/BurstAotSettings_StandaloneWindows.json
(16)

A
ProjectSettings/CommonBurstAotSettings.json
(6)

A
ProjectSettings/PackageManagerSettings.asset
(45)

M
ProjectSettings/ProjectSettings.asset
(122)

M
ProjectSettings/ProjectVersion.txt
(4)

A
ProjectSettings/VersionControlSettings.asset
(8)

A
ProjectSettings/XRPackageSettings.asset
(5)

M
README.md
(2)

A
UserSettings/EditorUserSettings.asset
(30)

A
UserSettings/Search.settings
(1)

Patch Links: https://github.com/marijnz/NativeQuadtree/pull/11.patchhttps://github.com/marijnz/NativeQuadtree/pull/11.diff

—You are receiving this because you are subscribed to this thread.Reply to this email directly, view it on GitHub, or unsubscribe.

crener commented 3 years ago

I was playing around with this a little more today and I've found a bug where range queries suddenly return no more results once you have more total entries than the max amount per leaf in the tree even when the entries are spread out across multiple nodes (not actually above the per node limit on any individual node).

I don't know if this is because of my changes or if this is an existing issue, so might want to wait a bit when merging this...

crener commented 3 years ago

So I spent a while trying to figure out what exactly is going on (added a bunch of temp code that exposes the raw structures so I can watch them change) and I've come up with a unit test which illustrates the issue.

Still looking at it when I have time but since figuring out what is going on inside native memory isn't straight forward I don't have a solution for this yet. My current theory is that the shape intersection code doesn't behave as expected when a query shape is a very small part of the QuadTree bounds....

Hope you had a nice Holiday :)

crener commented 3 years ago

Got around to looking at this again and it was more of an issue with the location that I places the node count assert... So I moved the assert so that is tests the nodes correctly which makes the test fail as expected.

but while looking around and actually visualising the data so I could see what was going on I came across an interesting case where I don't know why a QuadElement was sorting in a specific QuadNode.

Untitled That is MultiDepth2 unit test which does this.

Then MultiDepth3 also seems to do some strange behaviour where the node at depth 2 is populated with a single entry where the depth 1 node for the depth 2 cluster is empty with the leaf element size being at 3... I would have expected that there would be 2 nodes at depth 1 being used... but apparently not?

marijnz commented 3 years ago

Heya, so I'm back :) Note that I'm not actively working on this project anymore. Otherwise I'd love to debug thing together with you, but I can't find the time for that right now. Have you continued since the last bug you've found?

crener commented 3 years ago

I've not really done more since I added the failing unit test.

I did try to figure it out but I need to read up on the specifics of how Morton codes work in order to fix it cause it seems like some part of the lookup is failing to set items correctly when doing the recursive add stuff.

There is a unit test though so getting a repo is super easy :)

marijnz / NativeQuadtree

Dunno if you want my stuff? #11