3D viewshed initial work

PREAMBLE:

The 3D implementation of the viewshed is something that needs to be completed prior to integration with pathing solutions which itself is a prerequisite for the development of the overall problem solution.

 

AIM:

Work on 3D viewshed implementation.

CONDUCT:

  • Developed 3D viewshed visualisation and related interaction
  • Attempted implementation of 3D viewshed algorithm
    • Algorithm complete has bugs
    • Fully functional along the X and Y axis of the viewer
    • Capabilities the same as the linear implementation

RESULTS:

Visualisation works well. The Unity profiler allows observation of CPU time spent in each activity so it is possible to determine timing for each element of the program – this means the viewshed calculation time can be determined accurately.

The 3D algorithm has a bug in the calculation of the intersection point on angles. This is something that should be able to be worked through fairly quickly when I next pick it up.

The algorithm works fine in a line along the X and Y axis of the viewer. The implementation here is only a minor extension of the linear version. The results were good.

Unity editor with 3D viewshed running as per current implementation
The 3D viewshed being updated real time and visualised inside Unity.

The above image was a 129x129m terrain with heights sampled every 2m.

This results in a total of 4225 sample points. The visualised viewshed is 130 points and the processing time to calculate is ~ 5ms (Only linear calculation done as per visualisation so only ~130 calculations.

When the sampling was reduced to 1m samples (16.6k points), the processing time ballooned to ~170ms. This seems reasonable however the code to calculate the points outside the linear X and Y axis from the viewing location was not run. This means only 258 calculations were run (This result is very concerning!). Obviously this isnt going to be constantly recalculated however it may need some optimisation or further research. It does seem strange as the algorithm appears to be O(n) but the timings above dont agree with that.

When the sampling was extended to 4m samples the CPU time was ~1ms or less.

TIME SPENT:

4 hours (28 hours running total)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s