Declutter roadmap status update

[Ognjen Bubalo]

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

[Patrick Cozzi]

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

Patrick

[Ognjen Bubalo]

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

[Ognjen Bubalo]

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: 

• http://gamma.cs.unc.edu/users/gottschalk/main.pdf
• http://www.geometrictools.com/Documentation/MethodOfSeparatingAxes.pdf
• http://gamedev.tutsplus.com/tutorials/implementation/collision-detection-with-the-separating-axis-theorem

I will post as soon it is ready.

Ogi

[Ognjen Bubalo]

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 

 

[Ognjen Bubalo]

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

[Ognjen Bubalo]

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 

[Ognjen Bubalo]

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

[Patrick Cozzi]

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

Patrick

--
You received this message because you are subscribed to a topic in the Google Groups "cesium-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cesium-dev/L8EvEBNZb10/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cesium-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

twitter.com/pjcozzi

[Ognjen Bubalo]

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

[Ognjen Bubalo]

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

[Patrick Cozzi]

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

Patrick

[Ognjen Bubalo]

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

[Ognjen Bubalo]

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

[Ognjen Bubalo]

Hi Everyone,

Happy New Year! :)

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

[Rencia Cloete]

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

Thanks. Rencia 

[Ognjen Bubalo]

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

On Fri, May 23, 2014 at 10:26 AM, Rencia Cloete <rencia...@gmail.com> wrote:

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

Thanks. Rencia 

--

You received this message because you are subscribed to a topic in the Google Groups "cesium-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cesium-dev/L8EvEBNZb10/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cesium-dev+...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

[Rencia Cloete]

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

[joedo...@gmail.com]

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.

[Patrick Cozzi]

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

[Joseph Donofry]

I came up with a partial solution that measures the distance from the camera to the label and uses that to generate a scale for the label and to determine how far apart labels should be.  Labels that overlap are hidden.  Zooming in results in more labels being displayed as long as they don't intersect according to the new camera distance.  Then, after a certain threshold, all labels are shown.  It seems to work for now, but I would like to revisit this in the future, possibly with some kind of grouping based on location or using some kind of force repulsion between labels.  I wasn't sure of a good way to do either of these things.

If there's any interest, I can share what I have done for the time being.

[Patrick Cozzi]

Glad you found something that works for you.  Can you post a link to a demo?  This could be a good fit for a Cesium plugin.

Patrick

--
You received this message because you are subscribed to a topic in the Google Groups "cesium-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cesium-dev/L8EvEBNZb10/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cesium-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

twitter.com/pjcozzi

[Joseph Donofry]

I'll have to remember to write something up when I get home.  My work computer is on an internal network.

[Rencia Cloete]

HI Joseph, I am very interested in your code - a plug-in sounds good but meanwhile be great to incorporate it meanwhile... thanks!

Rencia

[Ognjen Bubalo]

Hi Joseph,

When I was working on it there were two approaches we considered in case of intersection. 

One was the spiral/circle idea, where you put one label and try to put the next. If they are overlapping then you try to find a place around the original placement point on a circle, if there is no space then extend the circle for a while.

The other was the force vector based idea which I think you mentioned as well. Here is an abstract: http://wwwcg.in.tum.de/fileadmin/user_upload/Lehrstuehle/Lehrstuhl_XV/Research/Publications/2012/Force_Labeling/2012_Vaaraniemi_Temporally_Coherent_Real-Time_Labeling_of_Dynamic_Scenes.pdf

Ogi

[vdiwakar...@gmail.com]

Hi Joseph,

Could you please let me know whether your code included as a plug-in to Cesium. I have a similar requirement to implement.

Regards,
Diwakar

[supar...@gmail.com]

Hi,

Is there any update on the declutter roadmap or could you please let me know how can i find out whether the labels are overlapping at a particular zoom level?

[Patrick Cozzi]

Hi,

There's no update on the roadmap, but if you search the forum, I believe some developers have created partial solution specific to their app that could provide some ideas.

Patrick

On Wed, Nov 11, 2015 at 4:56 PM, <supar...@gmail.com> wrote:

Hi,

Is there any update on the declutter roadmap or could you please let me know how can i  find out whether the labels are overlapping at a particular zoom level?

--
You received this message because you are subscribed to a topic in the Google Groups "cesium-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/cesium-dev/L8EvEBNZb10/unsubscribe.
To unsubscribe from this group and all its topics, send an email to cesium-dev+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

twitter.com/pjcozzi

[Daniel Wild]

I've posted this elsewhere - but just wanted to point out that server-side clustering and heat-mapping of point data can be handled by GeoServer quite easily (if you have control of the data) using rendering transformations and consumed in Cesium as as simple WMS layer: http://docs.geoserver.org/stable/en/user/styling/sld-extensions/rendering-transform.html.