fury-gl / fury

FURY - Free Unified Rendering in pYthon.
https://fury.gl
Other
227 stars 165 forks source link

WIP: Spatial Tree Accelerating Data Structures #783

Open JoaoDell opened 1 year ago

JoaoDell commented 1 year ago

This PR introduces quadtree and octree data structures to FURY.

Below, an example of a quadtree generated and rendered with this module:

https://user-images.githubusercontent.com/61475630/232117770-3946f09e-9ca3-4d3e-9fa9-cbba5b336586.mp4

And below, an example of an octree:

https://user-images.githubusercontent.com/61475630/232118279-5e8ce23f-acbf-46b2-811a-a40434144241.mp4

The classes added contain the most basic implementation of those structures, and some simple functions for rendering them.

JoaoDell commented 1 year ago

Hey @skoudoro and @filipinascimento, thanks for the quick reply, I will be looking into those issues soon! I just wanted to clarify better why I am using classes like Point2d and 3d to store coordinates so I can be sure they are really unecessary: Analyzing the whole code now maybe I left it redundant and abused of class engineering indeed, but I thought about using specific classes for that so a user that decides to use trees for any abstract purpose could build a class based on those and complement it with it's own necessary information for the intended purpose, still preserving the tree structure. Do you think that makes sense or a better approach could be taken? Maybe cleaning the base classes to make it simpler, or using only arrays, as you mentioned?

JoaoDell commented 1 year ago

Actually, about my last comment, after some thinking, I just realized that indeed it may be a redundant choice, as if someone wanted to do that, they would create a class using an array as a base, so you guys have a point, and I will try it later.

devmessias commented 1 year ago

"test_tree.py" is running without errors. But it seems more appropriate as an example that can be added following the standard of examples here: https://github.com/fury-gl/fury/tree/master/docs/examples.

JoaoDell commented 1 year ago

Hey everyone, I am sorry for the big commit, I entered in a very rushed week and forgot to commit every time I got to a good checkpoint, but here it is. I've changed a lot of things regarding pep8 and python conventions in general, as well as implemented a test for the features and some other things.

JoaoDell commented 1 year ago

Hey everyone, just to let you know that i am currently working on the changes to this PR, I just haven't submitted yet because I am having issues with the testing file and implementation choices as i've abolished point2d and 3d, so you can expect an update soon

JoaoDell commented 1 year ago

Hello everyone, so I just commited my lastest attempt on adressing the points you mentioned. I have abolished point2d and point3d usage for simple arrays, and added an id system based on python native uuid to keep track of the points inside the tree. I must admit I am not that sure about all the choices I made to make this work, but it is working and it seems simple to use, so I guess I can accept that as a checkpoint.

skoudoro commented 1 year ago

@devmessias @filipinascimento @guaje. Can you review this PR ?