Towards a High Performance Line of Sight Tool

We have a number of ArcObjects-based applications that require thousands to tens of thousands of Line of Sight Analyses to run to obtain the desired output.  As part of a Research and Development project I was looking for alternate ways of achieving the same result but allow us to optimize performance and have access to finer grained control of the underlying analysis. The following is a description of what I found with the ArcObjects code and the beginning of an alternative solution.

ArcObjects is thread-safe, but some of ArcObject’s operations lock out concurrent processing to ensure thread safety.

I discovered this fact while working on an algorithm that performs several calls to ISurface::GetLineOfSight.  After profiling the algorithm, I discovered that the line of sight operation was the algorithm’s bottleneck.  To get more speed, I multi-threaded the algorithm.  The result was unexpected: The algorithm took twice as long to process and required twice as much processing power.

I came to the conclusion that I needed to write my own line of sight algorithm.

After a bit of research, I decided to use a Triangle-Ray Intersection technique (used by some ray tracing methods).  The method requires converting the surface to a collection of 3D triangles.  To determine the intersection point, search through the triangle collection for an intersection with the ray.

(Source: http://www.cs.cornell.edu/courses/cs465/2003fa/homeworks/raytri.pdf)

The reason to use triangles is that the math becomes much simpler (and faster).  In fact, there are no computationally complex (and slow) mathematical operations.  Take a look at the code:

Granted, the math is complex, but the math isn’t computationally complex.  The above method, “flattens” the surface and then determines the intersection of the triangle’s plane with the ray.  The PointInTriangle method then determines if the intersection point is inside the triangle.

The way the PointInTriangle method works is by checking which “side” of each of the triangle’s lines the point is on.  If the point is outside of the triangle, the point will be on the left side of 2 of the lines, and on the right of the other (1: Left, 2: Left, 3: Right).  If the point is inside of the triangle, the point will be on the same side of each line.

So far, my implemented version is 10x slower, but just as accurate as the ArcObjects line of sight operation (the trick is to use the same points to build the triangle collection).  But not to worry, there is plenty of room for improvement.

Currently, the triangles are stored in a 2D array.  A more efficient data structure will greatly improve performance.  Another positive note is that this implementation is thread-safe and doesn’t lock out concurrent processing.

This implementation can be modified for GPU processing.  Using a GPU technique, every triangle can be checked for intersection at the same time.

In conclusion, there is a lot of potential using GPUs to perform line of sight operations.  Transferring the surface’s data to the GPU is a relatively considerable investment (about 2-3 ms).  Luckily, when performing thousands of line of sight operations, the data transfer happens only once at the beginning.  Compared to ArcObjects running on a single thread, we can expect to see at least a 14 times speed up.  This means an algorithm that previously took an hour to run could potentially run in 4 minutes.

It took a bit of research to determine a good method of implementation.  Luckily there were several sources out there to read and use:

http://www.cs.cornell.edu/courses/cs465/2003fa/homeworks/raytri.pdf

http://en.wikipedia.org/wiki/Ray_tracing

http://en.wikipedia.org/wiki/Line-plane_intersection

http://www.codeproject.com/KB/graphics/Simple_Ray_Tracing_in_C_2.aspx

http://t-ray.googlecode.com/svn/trunk/ORayTracer/RayTracer/tTriangle.cs

Esri Mid-Atlantic User Group Conference Recap: Part 2

I was glad to join Christopher at the Esri Mid-Atlantic User Group Conference outside of Baltimore recently.  It’s very exciting to step outside of the daily routine once in a while to learn about the future and direction of the GIS industry, be inspired by work that our colleagues are doing, and to talk about some of the work GISi has been engaged in.

Like Christopher mentioned, integration was certainly a buzz word tossed around a fair amount.  Demos given during the main session talks showed how a user could fairly easily push maps and data from ArcGIS Desktop to ArcGIS Server and ArcGIS online.  As Clint Brown, Director of Software Products at Esri, was casting vision for the future of ArcGIS, he liked to refer to ArcGIS as a system.  To paraphrase, “What is ArcGIS?  It is a system that enables people to work with your online maps and associated geographic info.”  It would seem that Esri’s heavy investment in cloud technology (in the form of ArcGIS Online) is the key to the advancement of this vision.

In line with this vision is the idea that maps are windows into our data.  Maps are way more than a way to find directions from A to B.  Thanks to Google, the general public is familiar with the idea of using a map to explore data from the world around them.  Esri wants to harness this general population spatial awareness.  Again, Clint Brown: “Everyone knows how to use a map.  The map is the window into everything else GIS related.  It is one of the most universally recognized ways to present information.”  He encouraged us to think of new ways to use the map as a window into our respective organization’s business data.

Like Christopher mentioned in his previous post, the Esri MUG was a very inspirational event.  In addition to the array of fine user presentations, I was particularly inspired by the recipient of the First MUG Community Service Award, Dr. Jay Morgan of Towson University.  This man has used his career to increase the public’s awareness of GIS and how it can be used to create a better world.  He inspired us to find ways to volunteer in the community and transfer our passion for GIS to the next generation.

Esri Mid-Atlantic User Group Conference Recap: Part 1

This year’s Esri Mid-Atlantic User Group (MUG) Conference was located just north of Baltimore City in Hunt Valley, Maryland.  Having grown up in Northern Maryland and attended UMBC, this conference was a little bit like heading home for me.  I ran into a number of former classmates and colleagues from across the state of Maryland and really enjoyed “geeking out” about the innovative work we have been doing over the years.

If I could choose one buzz word to describe the future of GIS it would be Integration. With Esri’s upcoming 10.1 release and increasing push into cloud infrastructures, it is becoming easier to push data developed in ArcGIS Desktop to map services hosted by ArcGIS online, that feed applications hosted on a webserver to clients anywhere in the world.  It is a different concept than what I am used to.  I think Clint Brown said it best when he proclaimed ArcGIS Online the Flickr of GIS.

In addition to integrating a number of their software products, it sounds like Esri has invested a lot of time simplifying the everyday maintenance of their ArcGIS Server and ArcSDE products.  ArcGIS Server is getting a total make over, dropping support for DCOM connections and trimming down the number of installed users from three to one.  Also, I really like the incorporation of more Database Administration tools into ArcCatalog.  Hopefully gone are the days of cracking open SQL management studio to manage users.

I was left really inspired by this year’s MUG.  There were a bunch of presentations that showed the increasing role that GIS plays in disseminating information to typically non-GIS users.  The Flex Site the Baltimore City Fire Department set up for emergency responders working the Grand Prix showcased how GIS can be used to help dispatchers make decisions on the fly in a rapidly changing environment.   I also thought the model the National Capital Region Geospatial Data Exchange utilized to distribute data between local governments, private industry and non-profits was really innovative.  Silos of data are nice and all, but real information comes when multiple data is shared throughout the community.