In article <3f452810@news.povray.org> , "RetroJ" <jjf### [at] earthlinknet> 
wrote:

>     I wonder if anyone can point me toward an algorithm for creating a
> triangle mesh from a group of points.  The project is to render a landscape,
> so I assume up front that there will be no overlap in the elevation axis.

Note that there is no universal way of generating a specific mesh.
Depending on the algorithm, you will get a different mesh.  But I guess you
are aware of this already.

I assume given that you got this information using GPS, it is not absolutely
precise and thus a little loss of position precision will be acceptable.
Further, given that you know the maximum resolution of the GPS data (I guess
it is precise up to about 5 to 15 meters), you might try this:

Assume all points are actually on a grid with grid points spaced about as
far apart as the maximum resolution you have.  Now, for each grid cell, find
all points inside it, and average time (on average you should only have
about one point per grid cell).  Now you can use this data to create a
height field.  This algorithm will run in O(n) time.

Alternatively, if you really want a mesh, I would always connect the three
points closest to each other.  You can find the closest points of every
other point in O(n*n) time.  Note that if a point that is closest is already
in another triangle, you will have to check if the newly created triangle
does not interfere with any existing triangle, which also takes O(n*n) time.
Thus, the total runtime is O(n*n).  However, I don't know if such a simple
algorithm will create good results.

I would really try the grid method first.  You could even make better use of
the GPS precision property and extend it such that it actually deforms the
grid to exactly match the GPS sample points.  This should work as long as
you properly deal with impossible cases of two very close-by sample points,
which can simply be considered identical as GPS has limited resolution.

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message