Declutter roadmap status update

Hi Everyone,

I just want to post a little status update about the Declutter project.

Information about this road map: https://github.com/AnalyticalGraphicsInc/cesium/issues/1097

Currently what we first wanted to have with Dan is the calculation of an oriented bounding box. We decided to have a general 3d OOBB calculation. After checking several papers I decided to implement this solution: http://gamma.cs.unc.edu/users/gottschalk/main.pdf

I implemented it and created some testcases. I opened a pull request on Dan’s fork: https://github.com/bagnell/cesium/pull/1

More testcases are coming.

If the implementation passes, I will create a pull request to the AGI fork.

While planning this project we had some discussions with Patrick and Dan about handling the label overlapping. The next step will be creating a solution for this.

Have a nice day!

Ogi

Thanks for sharing. We’ll look forward to your continued progress.

Patrick

Hi Everyone,

Dan gave me great comments in the pull request of the ObjectOrientedBoundingBox. After fixing the issues, I continued working on a function which computes the OOBB from a BoundingRectangle and a rotation (2D solution for labelling). Also I started implementing the separating axis theorem for rectangles and boxes, so we can determine intersection of two rectangles or boxes.

Hopefully I can add these features to the pull request on the first part of next week.

I will post regularly status updates. If you have any questions about this project, do not hesitate.

Best Regards,

Ogi

Hi Everyone,

I added a method for computing OOBB from a BoundingRectangle and a rotation with testcases. I am working on the SAT for checking intersections.

Some reference:

I will post as soon it is ready.

Ogi

Hi Everyone,

I implemented the collision check for two ObjectOrientedBoundingBoxes. Also I added testcases.

The method’s name is intersect, but I am not sure that this is a good choice. As I know it is used for other purpose.

During the weekend I will add more testcases.

Have a nice weekend!

Ogi

Hi!

I added more testcases, fixed some conflicts, and did some refactor. If you have time to tell me your opinion about this pull request, please do it. Thanks!

You can find it here currently: https://github.com/bagnell/cesium/pull/1

I will post a reply with the next steps soon.

Ogi

Hi Everyone,

After Dan reviewed the code I updated the pull request. I created a function for getting the vertices from the OOBB’s properties, but Dan told me that there is already a solution for that, so I will rewrite some testcases.

During the weekend I want to compute OOBB-s for labels.

Regards,

Ogi

Hi,

I’ve added computing the OOBB-s for labels. This will be soon a new pull request. In the next 1-2 days I’ll add the intersect checking for the Labels, + tests for that.

Have a nice day,

Ogi

Thanks for the update Ogi. Your recent progress is looking good.

Patrick

Hi,

Dan after some fixes merged the ObjectOrientedBoundingBox model. I’ve added oobb-s to the Labels, and added computing when reposition occurs. Currently we are discussing about the declutter algorithm with Patrick and Dan. Soon I will post the fix plan and the schedule.

Thanks,

Ogi

Hi Everyone,

Just a little update.

Dan merged the ObjectOrientedBoundingBox to the AGI/master branch. Also we had a discussion about the declutter algorithm. We decided to implement first the solution based on circle/spiral.

If we the actual label we want to place would collide we try to find a place on a circle around the original placement position. If we don’t succeed we enlarge this circle. If we still cannot find a good placement, we start playing with the translucency.

One important thing is that Label can have a priority, so the labels with a higher priority will be placed first.

During the weekend I implemented this algorithm. I need 1-2 days to complete it.

Ogi

Looking forward to your progress on the algorithm. Congrats on getting your code merged.

Patrick

Hi,

Just a little update.

Currently I am working on setting the new position of the Label to the VBO. When I finish this, I think we can start to test the declutter based on the circle/spiral method.

Regards,
Ogi

Hi Everyone,

With Dan’s help I’ve pushed an initial declutter. During the next days I will clean the code and hopefully reach the first milestone.

Regards,

Ogi

Hi Everyone,

Happy New Year! :slight_smile:

Dan checked the initial declutter and gave me his czml test set. I’ve optimized the declutter after his comments. I will push the update during the weekend.

Regards,

Ogi

Hi Ogi / Dan, by any chance you got a working version of declutter yet?

Thanks. Rencia

Hi Rencia,

No. Unfortunately I couldn’t find time in the last couple of months to finish declutter, however I would like to continue in some way. The calculation of Object oriented bounding boxes was implemented and a half ready spiral/circle solution. The next step would be testing it. Future plan was to use force vectors.

May I ask what is your plan with the declutter?

Ogi

Hi Ogi, basically when there is clutter then I was hoping for a similair result to the STk software where the labels are then spread out with a little line connecting each to its object or point of reference. AS one zooms in & the clutter is reduced the label then comes nearer.
Many thanks for your reply…

please let me know when you make further progress.

Regards

Rencia

Is there any word on when this is going to continue to get worked? I see that it's part of the roadmap, but not any releases. For my project, we have some dynamic data that often results in labels being stacked right on top of each other! I have tried manually adding the changes to b27 (what we're using currently), but I think I missed some of them since I keep getting rendering issues in the updateFrustrum function.

In the meantime are there any good workarounds? I currently have a O(n^2) function that checks all labels for overlap and repositions them that runs every 1/10th of a second. I would like to try to find a more elegant solution that works more efficiently.

Thanks.

There hasn’t been any work on this recently. You may be able to get ideas for an app-specific low-tech solution by reading through the roadmap: #1097.

Patrick