Friday, April 11, 2008

Ray Casting and Line of Sight for WWJ

It is a common issue to be able to find out where in the world does a line intersect the terrain surface. The WorldWind Java SDK allows to resolve the intersection from the eye point of view using the pick process - based on drawing objects in unique colors, but that does not help much when you need to compute such intersections from another perspective, like for line of sight calculations.

Ray casting and line of sight calculations in WorldWind JavaLine of sight calculation from the top of Mount Jackson (3064m),
Glacier National Parc, Montana, USA.

Here is a helper class to answer such questions, along with an example application that will display areas from where you can see a central point.

Download RayCastingSupport.java and LineOfSight.java - remove the .txt extensions, save the first one in 'util' and the application in 'examples'. You may also need the crosshair layer.

Update april 18: there appears to be two dependencies on the not yet published SDK version: centerPosition calculation and PatternFactory.blur() - see this post comments. You can simply comment out the blur, or replace it with a ConvolveOp, and change the center position line with:
Position centerPosition =
     RayCastingSupport.intersectRayWithTerrain(globe,
           view.getEyePoint(), view.getForwardVector(), 30, 3);


Ray castingRay casting - figure 1

The ray casting code samples points at regular intervals along the 'ray' until it finds one which elevation is below ground - figure 1.1. It then recursively resamples the last segment every tenth of the previous sample length - fig 1.2, until that sampling step is smaller then or equal to the required precision.

The longer the initial sample length, the quicker an intersection will be found - 1, and the sub sampling process will start narrowing onto the terrain - 2. However, the larger the value the less accuracy you will get since the ray will be able to go through some surface features in just one step and completely miss them. The default values for sampling length and precision are 100 meters and 10 meters and can be overrided in the methods arguments.

Note that the example application also shows how to 'paint' both on the terrain and on the screen using BufferedImage, Java 2D, SurfaceImage and ScreenAnnotation classes.

9 comments:

Anonymous said...

Allo Pat!

Your experiments with WWJ are REALLY interesting! Keep blogging about them as much as you can! Will your personal additions be included in the demo package of the next WWJ or just stay on your blog pages?

P.S Pour quelqu'un qui n'aime pas trop la neige, tu y a gouté cet hiver, hein? ;-)

Patrick Murris said...

As usual, some of these code bits will end up in the SDK, others won't... I can't tell which right now.

Anonymous said...

i add the source code to the sdk,
there are some errors in it.
Position centerPosition = view.getCenterPosition();
getCenterPosition is undefined.

PatternFactory.blur(image)
blur is undefined for the type PatternFactory.

Anonymous said...

Bonjour Pat, j'ai le même problème que le commentaire précédent avec la ligne

Position centerPosition = view.getCenterPosition();

J'utilise la version 0.4.1 du sdk worldwind.

Je suppose que tu utilise une version plus récente non publié par la NASA.

Pourrait tu poster les modifications de code nécessaire pour que ton application fonctionne a partir du sdk 0.4.1 ?

Bravo pour cette contribution qu'il me tarde d'essayer.

Anonymous said...

J'ai put essayer ton plugin, il est impressionnant :O . Néanmoins j'ai un petit souci, quand je l'utilise sur des zones maritimes il prend en compte la bathymétrie du fond dans le calcul de visibilité ce qui peut etre souhaitable dans certains cas mais poser problème dans d'autres.

Voici une capture d'écran du problème http://img156.imageshack.us/img156/7994/captpbfondloslp2.png

Merci encore pour toutes tes inestimables contributions.

Patrick Murris said...

Effectivement cet exemple ne fait pas de différence entre le relief au dessus et au dessous du niveau de la mer. Si c'est un probleme, simplement ajouter un test dans la boucle de calcul afin d'éviter des élévations négatives: double el = Math.max(globe.getElevation(lat, lon), 0);

Attention, ce programme n'utilise que les données d'élévation qui sont déja chargées en mémoire - ce qui se produit lorsque l'on se raproche du terrain. Il est donc préférable de survoler 'à basse altitude' la zone concernée avant de lancer un calcul.

Anonymous said...

Merci ton astuce fonctionne dans la plupart des cas. Il peut arriver que l'altitude en mer soit supérieure a 0 mais c'est plutôt rare.

Unknown said...

Hi Patrick, nice blog!
I want to ask you some hints about Ray Casting. I want to compute Ray Casting also considering some 3d shapes that I rendered on the globe surface. I have to first compute the projection of the rays on the object and then on the terrain, considering the shadows on it.
Thanks anyway.

Patrick Murris said...

If you are looking into producing shadows you may want to do some researches and consider the various techniques available like shadow volumes using a stencil buffer.

In any case i recommend you post your question on the World Wind Java forum so that others will be able to share ideas and comments - and it is a more convenient place for discussion ;)