Hello,

    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.

Thank you,
RetroJ

Post a reply to this message

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.

  In general this is a difficult problem and not too many utilities have
been made which do this (at least not free ones). The only free utility
which I could find with google was this one:

http://paraform.com/ppdl/index.html

but it seems to be an NT-only program (but could perhaps work in
Windows 2000/XP?) and it's not directly downloadable (why so much
protection, I wonder).

  You could try also this site to see if you find anything useful:

http://aranz.com/research/modelling/surface/applications/pointcloud.html

>  The project is to render a landscape,
> so I assume up front that there will be no overlap in the elevation axis.

  This might make the job easier, but if you can't make any other
assumption than that no points will have the same x-z coordinates,
it might not be trivial either.

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

Thanks guys.  You don't want to see my source code, but I got it working
using Delaunay's method.  It runs in O(n^4) time where n is the number of
points, so I'll be doing some major cleanup on my code before I post
anything.

RetroJ

Post a reply to this message

RetroJ <jjf### [at] earthlinknet> wrote:
> It runs in O(n^4) time

  So forget using any larger amount of points?-)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

My project is actually to make 3D renderings from GPS data, so I
necessarily will have a large set of datapoints..  So what I need is a
refined algorithm.  I set up my program to test all possible triangles
against Delaunay's criteria.  If I could mathematically exclude some of
those triangles it would make a huge difference in running time.  Even if I
don't find a better algorithm in that sense, there are some other
improvements I can make... fewer variables, eliminate duplicate
calculations.  Shall see, shall see.

Nice looking sig-macro you have there.

RetroJ



"Warp" <war### [at] tagpovrayorg> wrote in message
news:3f47f9b2@news.povray.org...
> RetroJ <jjf### [at] earthlinknet> wrote:
> > It runs in O(n^4) time
>
>   So forget using any larger amount of points?-)
>
> -- 
> #macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb
M()}}
> N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
> N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  -
Warp -

Post a reply to this message

in news:3f481124@news.povray.org RetroJ wrote:

>     My project is actually to make 3D renderings from GPS data, so I
> necessarily will have a large set of datapoints..

Why don't you use hightfields then? Can't you convert your GPS data to a 
gray scale image?

Ingo

Post a reply to this message

RetroJ <jjf### [at] earthlinknet> wrote:
>     My project is actually to make 3D renderings from GPS data, so I
> necessarily will have a large set of datapoints..

  I don't know anything about this type of algorithms, but I'm pretty
sure there must be a much faster than O(n^4) algorithm for this.
I would say that it's extremely rare that O(n^4) would be the fastest
you can do something related to a set of points.
  I very wild guess is that there exists sone O((n^2)*log n) or even O(n^2)
algorithm. It would make sense.
  OTOH, I think there are some matrix-handling algorithms which are O(n^3),
so it's not impossible that that would be the faster possible for this
problem as well.

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

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

In article <3f48adc3@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>>     My project is actually to make 3D renderings from GPS data, so I
>> necessarily will have a large set of datapoints..
>
>   I don't know anything about this type of algorithms, but I'm pretty
> sure there must be a much faster than O(n^4) algorithm for this.
> I would say that it's extremely rare that O(n^4) would be the fastest
> you can do something related to a set of points.
>   I very wild guess is that there exists sone O((n^2)*log n) or even O(n^2)
> algorithm. It would make sense.
>   OTOH, I think there are some matrix-handling algorithms which are O(n^3),
> so it's not impossible that that would be the faster possible for this
> problem as well.

Delaunay triangulation takes O(n log n) time if I recall correctly.

    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

In article <3f46013c@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

>   In general this is a difficult problem and not too many utilities have
> been made which do this (at least not free ones). The only free utility
> which I could find with google was this one:

Not really so if you know where to look for it ...

<http://astronomy.swin.edu.au/~pbourke/>

A paper and sample implementation at:
<http://astronomy.swin.edu.au/~pbourke/terrain/triangulate/>


    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