Formed in 2009, the Archive Team (not to be confused with the archive.org Archive-It Team) is a rogue archivist collective dedicated to saving copies of rapidly dying or deleted websites for the sake of history and digital heritage. The group is 100% composed of volunteers and interested parties, and has expanded into a large amount of related projects for saving online and digital history.
Add Octree #6229
Add Octree #6229
Conversation
I made a first quick review, don't take it badly, i didn't take gloves for the sake of review efficiency :D
I'd like to see a first implementation of a query(Frsutum) method to see how it looks, especially userObject/geometry pairing.
to me the nominal case of geometry is BoundaryBox. Vector3 is an edge case IMO.
i'm not even sure we would need more than boundary box approximation, user code could fine grain check collisions over their original shapes. Even for the rayCast scenario, they could supply a handler to perform perfect collision over their original shape. Octree still an approximation to reduce complexity.
Also, maybe we could make it generic : Octree, it would be cleaner. User could always use Octree if they want to mix apples with oranges.
Also i'm a bit balance between using java collection over libgdx collections. I know java one could performs better in most cases but i think we should stay consistent with libgdx code (i know i'll get a shit storm because of what i say here, i'm ready for it :D )
Feel free to disagree with my comments, i could be wrong. I'll probably be more confident about what i said as we going further with the implementation.
Thank you for your work.
|
@mgsx-dev Thank you so much for taking the time to review it. For the next days I will work on your comments, and build a working example.
Don't worry at all, we don't have time for that.
Yep, I didn't think about it before you suggested, I had plans for geometry only and do the mapping outside but makes sense to have it.
Yes, let's start with AABB and see how it goes. I am still not sure how to integrate this structure for the broad phase and a different structure for the narrow phase. I really would like to hide technical details as much as possible.
Let's go full libgdx then! I've never tried libgdx collections before that's why I didn't think about it.
Thank you, all your points are valid. |
|
@mgsx-dev I just updated the code following your precious comments. I didn't added the maxItemsPerNode logic yet. I quickly ran a debug and it seems to be working. I will try to find some time this weekend to create a visual "test" example. Thanks again! |
|
I just realized that the query method would not work as expected, I will work on that as well. |
yuripourre
force-pushed
the
spatial-database
branch
3 times, most recently
from
ae8e82c
to
9628be4
Compare
Mostly, I think there's some rough edges on this but they should be easy to polish up. Making the docs use punctuation would be nice.
we also need to think about the "update" case and a proper "remove" :
- some dynamic objects could move and we would need to update it in the tree (probably remove it and add it again for now, but it could be optimized in the future).
- when removing an object, we may want to merge some nodes in order to reduce memory footprint. maxItemsPerNode should be true at any time (except for the last depth level of course).
Considering these 2 use cases, we don't want to generate garbage so we may want to handle nodes lifecycle a bit differently :
- by using a node pool (Pool)
- by having final Array children. An empty children array would means it's a leaf node.
|
@yuripourre i prefer to keep it as a draft PR until it becomes stable. |
yuripourre
force-pushed
the
spatial-database
branch
4 times, most recently
from
761f6ca
to
86768e1
Compare
I gave her a once over. Not sure my comments are terribly useful, but here they are! Overall it looks nice.
There's no need to squash PRs. Whoever merges this PR can (should!) choose to squash (if they forget, they will be beaten). |
| return boxes; | ||
| } | ||
|
|
||
| protected class OctreeNode { |
There was a problem hiding this comment.
Is there a reason why is this nested class not static? If it was, the node pool could be static as well and I suspect that it would allow children to be raw array as well.
There was a problem hiding this comment.
we need to avoid garbage as much as possible especially for dynamic stuff, children as raw array wouldn't be better.
sharing pool across multiple Octrees could be an issue, geometry array could be small in some case an big in other case which could lead to unnecessary heavy allocations. This could happen within a single octree though but it would be less annoying (isolated) than with a shared pool.
There was a problem hiding this comment.
we need to avoid garbage as much as possible especially for dynamic stuff, children as raw array wouldn't be better.
I was referring to the related discussion around the children above, I am not arguing for or against that change, as I have not read the code that thoroughly. That comment was only about the static-ness of OctreeNode.
There was a problem hiding this comment.
Sorry i have deep knowledge of that class now :D, so i got directly to the point of shared pool.
To answer your question, OctreeNode use some information from Octree (collider, maxItems), we could pass them to OctreeNode, but not sure it worth it.
There was a problem hiding this comment.
nice catch, i forgot about duplicates. However this strategy is not optimal : temporary ObjectSet will produce garbage and doing this for each removal is maybe not a good idea, maybe we should introduce a new method "pack" called by user code when it feels necessary to optimize the tree, what do you think?
also, avoid diamond operator, it's not supported by some backends :-)
There was a problem hiding this comment.
I totally missed too. I just found it because the unit test broke.
Yes, it's far from optimal, I will think about it tomorrow.
I think we can leave it as-is atm and update in the future. Do you agree with that? |
|
Fixed conflicts. |
|
Is she all done? :) |
I think so, I don't have any plans to change the implementation. I hope it can be useful for other developers |
* Use default access to avoid synthetic accessors, compiler warnings. * Don't initialize geometries at worst case capacity, maxItemsPerNode. * Use OctreeNode[] for children: fewer objects/memory per node, iteration without Iterator, initialized only when/if needed. * Use createNode() for root, move to Octree. * Use leaf field internally. Overriding isLeaf to return a different doesn't seem useful. * Added remove() to OctreeTest. * Fixed removal being broken because geometries weren't collected recursively. * Only create a set and add all geometries to it if an object was removed. * When child nodes were freed they weren't returned to the pool recursively. #6229
|
@yuripourre It is neat, thanks for sharing! I made a few updates, see 85db7fa. Let me know if you hate any of my changes and we'll revert them. |
|
@NathanSweet not at all! Thanks for the upgrade! |
|
There's this warning when compiling libGDX which probably causes Octree not to work on GWT: I don't do GWT or Octrees but setting OctreeNode to public seems to fix it but haven't tested properly. |
|
@obigu thanks for reporting, I will try that! |
Binary Space Partition (BSP) allows developers to work with just a subset of geometries at a given moment, it can be used to improve rendering and/or check collisions. This is a must-have feature for many 3d games.
I really appreciate all feedbacks here!
@mgsx-dev this is the implementation I mentioned. I removed the triangle part so we can start discussing the structure.
Steps
References:
https://github.com/mgsx-dev/dl13/blob/master/core/src/net/mgsx/dl13/navmesh/NavMesh.java#L105