Hello all!
I'm sure this has been done before, but not by me... ;) I'm writing a small
C-Programm to generate some simple Meshes. I've got an Array of points,
which is unsorted, and now I want to generate a closed Mesh. I'm just not
sure about the algorithm to use for that. I thought that I could search for
the nearest four points and connect them to two triangles and that would fit
to a closed Mesh... But this doesn't seem to work (Maybe there is also a
fault in the programm, who knows ;)). I would be interested in a working
algorithm (not in finished macros).
Thanks
Florian

Post a reply to this message

Florian Pesth wrote:
> 
> Hello all!
> I'm sure this has been done before, but not by me... ;) I'm writing a small
> C-Programm to generate some simple Meshes. I've got an Array of points,
> which is unsorted, and now I want to generate a closed Mesh. I'm just not
> sure about the algorithm to use for that. I thought that I could search for
> the nearest four points and connect them to two triangles and that would fit
> to a closed Mesh... But this doesn't seem to work (Maybe there is also a
> fault in the programm, who knows ;)). I would be interested in a working
> algorithm (not in finished macros).

This is an extremely nontrivial question and for an arbitrary point cloud
there needn't be a reasonable mesh representation.

You could try a seach fore more information:

http://www.google.com/search?q=point+cloud+mesh

Christoph

-- 
POV-Ray tutorials, IsoWood include,                 
TransSkin and more: http://www.tu-bs.de/~y0013390/  
Last updated 06 Feb. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

Hello Christoph!
> This is an extremely nontrivial question and for an arbitrary point cloud
> there needn't be a reasonable mesh representation.
upps...
> You could try a seach fore more information:
>
> http://www.google.com/search?q=point+cloud+mesh
>
> Christoph
Thanks, I will look for it.
Florian

Post a reply to this message

"Florian Pesth" <fpe### [at] webde> wrote in message
news:3c62e3dc@news.povray.org...

<snip>

This has come up before under various guises. Such an algorithm would be
something of a holy grail (since it would allow the fast creation of meshes of
any arbitary function).

If your output IS function-based, then you might want to look into Pov 3.5
iso-surfaces....

Post a reply to this message

Tom Melly <tom### [at] tomandlucouk> wrote:
: (since it would allow the fast creation of meshes of
: any arbitary function).

  Not necessarily, as calculating the best distribution of triangles among
the vertex points can be a very slow thing to do (sounds a bit like an
exponential-time problem).

-- 
#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

Hi Tom and Warp!
> If your output IS function-based, then you might want to look into Pov 3.5
> iso-surfaces....
No, it's not function-based. And I don't think, this can done with
functions. BTW iso-surfaces seem interesting for other purposes. But I don't
want to download Pov 3.5 again and again until it's official released. (I
don't care about the bugs, there are so much in Windows, but I have a slow
56K modem).
> Not necessarily, as calculating the best distribution of triangles among
>the vertex points can be a very slow thing to do (sounds a bit like an
>exponential-time problem).
First I have to find an algorithm, that works., than the PC can run a week,
or so... ;)
I've got another idea for that problem, but at this week I have absolutely
no time :(. I think that there is not only one possible solution to put a
mesh around an arbitrary poin cloud, but that there should be a way to find
one solution, that will do it.
Many thanks so far,
Florian

Post a reply to this message

Florian Pesth wrote:
> 
> No, it's not function-based. And I don't think, this can done with
> functions. BTW iso-surfaces seem interesting for other purposes. But I don't
> want to download Pov 3.5 again and again until it's official released. (I
> don't care about the bugs, there are so much in Windows, but I have a slow
> 56K modem).

You can use isosurface based methods for your points problem too, blobs
would also be a possible solution, see for example:

http://graphics.stanford.edu/~henrik/papers/psp/

Christoph

-- 
POV-Ray tutorials, IsoWood include,                 
TransSkin and more: http://www.tu-bs.de/~y0013390/  
Last updated 06 Feb. 2002 _____./\/^>_*_<^\/\.______

Post a reply to this message

Florian Pesth wrote:

> > Not necessarily, as calculating the best distribution of triangles among
> >the vertex points can be a very slow thing to do (sounds a bit like an
> >exponential-time problem).
> First I have to find an algorithm, that works., than the PC can run a week,
> or so... ;)

Have a look at:

http://astronomy.swin.edu.au/pbourke/modelling/polygonise/

All you need from your problem to this approach is an evaluation function
which compute the proximity of a 3D position to your array of point.
The closer the higher value is probably the way to go,

A function that would do it would be like Sum/i(Proximity[i])
where Proximity[i] is = 1/(distance between position and vertex i)
Or even the square of it, so as to avoid the square root computation,

Sum has the interesting effect that the more points are closer, the bigger 
the tesselated sphere.
If you do not like that effect, you can use Max/i(proximity[i]) instead.
(or just Min/i(Distance[i]) which is nearly the same).

P.S.: Proximity should be maxed when position and vertex are identical
      (when distance is smaller than a fixed value).

P.S.2: Beware of USA patent if it can apply to you...

P.S.3: the isovalue to use depends on your choice for the function.
        Sum: tricky, Min or Max : easier.

-- 
Non Sine Numine
http://grimbert.cjb.net/
Puis, s'il advient d'un peu triompher, par hasard,

Post a reply to this message

Hello Christoph!
| You can use isosurface based methods for your points problem too, blobs
| would also be a possible solution, see for example:
|
| http://graphics.stanford.edu/~henrik/papers/psp/
Many thanks, I'm downloading it at the moment. I've never thought about
blobs,
because I hardly use them. I'm sorry I have no time this week (math test),
so I
will post next week, what I've done at the weekend.
Best regards,
Florian

Post a reply to this message

Hi!
| Have a look at:
|
| http://astronomy.swin.edu.au/pbourke/modelling/polygonise/
I'm very sorry, but this week I have no time for poving or programming,
because
I write a math test on friday. I will post next week the results of the
weekend
work on this.
| P.S.2: Beware of USA patent if it can apply to you...
I would like some kind of open source for more parts of life ;)
Thanks for the hints,
Florian

Post a reply to this message