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