 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I've implemented an electrostatic repulsion algorithm
in order to distribute points on a sphere.
Now I'd like to know how can easily convert the
points into a mesh which has only triangles on the
outside surface.
I'd like it to work by selecting three closest points, make
triangle, and then move on, creating triangles as need,
until the entire area is covered.
I could go about and simply connect all combinations of
three points, but this is insane for point-amounts well
above 200 (at the moment 500).
Any links?
--
Tim Nikias
Homepage: http://www.digitaltwilight.de/no_lights/index.html
Email: Tim### [at] gmx de
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Tim Nikias" <tim### [at] gmxde> wrote in message
news:3d70e2d7$1@news.povray.org...
> I've implemented an electrostatic repulsion algorithm
> in order to distribute points on a sphere.
> Now I'd like to know how can easily convert the
> points into a mesh which has only triangles on the
> outside surface.
> I'd like it to work by selecting three closest points, make
> triangle, and then move on, creating triangles as need,
> until the entire area is covered.
> I could go about and simply connect all combinations of
> three points, but this is insane for point-amounts well
> above 200 (at the moment 500).
>
Hmm... You probably can't adapt your algorithm to do this, but if you
had a springy force between the points you could start with them linked up
into triangles and then allow them self organise over the sphere surface...
--
Pandora/Scott Hill/[::O:M:C::]Scorpion
Software Engineer.
http://www.pandora-software.com
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Any links?
http://news.povray.org/povray.newusers/22081/
Be aware of some problems... it is not so easy as it seems, and I have
not succeeded in the given time. Maybe I will try later again, but at
the moment I have absolutely no time :-(. I'm looking forward for your
results ;-).
Florian Pesth
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Tim Nikias wrote:
>
> I've implemented an electrostatic repulsion algorithm
> in order to distribute points on a sphere.
> Now I'd like to know how can easily convert the
> points into a mesh which has only triangles on the
> outside surface.
> I'd like it to work by selecting three closest points, make
> triangle, and then move on, creating triangles as need,
> until the entire area is covered.
> I could go about and simply connect all combinations of
> three points, but this is insane for point-amounts well
> above 200 (at the moment 500).
Brute force is an O(n^3) problem, so I can see how you'd want to
avoid that...
You could build three sets of indices, each of which sorts the points
according to the x, y, and z coordinates; then match only those that are
within a certain range along all three indices.
Regards,
John
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Tim Nikias" <tim### [at] gmxde> wrote in message
news:3d70e2d7$1@news.povray.org...
>
> Any links?
>
No links, but I can see a fairly straightforward way to accomplish this.
Three closest points *will not* work. No amount of time will ever make it
work, so patience isn't even an issue. Point B may be the closest point to
Point A, but Point A is not *necessarily* the closest point to PointB. Here
is an example:
A=========B==C
This is how I would accomplish what you are trying to. I don't know any
math, so I hope that I can communicate what I mean with words. Make a circle
around each point which is a little larger than half the maximum distance
around the closest points and make a polygons out of the circle
intersections. Then, make a polygon around any vertex for which the circle
method did not work out of all surrounding intersections or vertices.
Triangulate the polygons, and then you will be done, but with extra
triangles.
I had a better idea while I was typing the first. Just add planes making
sure all vertices are on one side of the plane until all vertices are
included and then figure out the plane intersections.
I haven't tested this, but it seems to make sense as I type.
-Shay
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Shay <shi### [at] houstonrrcom> wrote:
> Triangulate the polygons
By the way, that's far from trivial.
--
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Hmmm, forces ?
That makes me thinking about blobs...
Maybe a way to solve your problem ?
Regards
L.H.
3d70e2d7$1@news.povray.org...
> I've implemented an electrostatic repulsion algorithm
> in order to distribute points on a sphere.
> Now I'd like to know how can easily convert the
> points into a mesh which has only triangles on the
> outside surface.
> I'd like it to work by selecting three closest points, make
> triangle, and then move on, creating triangles as need,
> until the entire area is covered.
> I could go about and simply connect all combinations of
> three points, but this is insane for point-amounts well
> above 200 (at the moment 500).
>
> Any links?
>
> --
> Tim Nikias
> Homepage: http://www.digitaltwilight.de/no_lights/index.html
> Email: Tim### [at] gmxde
>
>
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Warp" <war### [at] tagpovrayorg> wrote in message
news:3d734a3f@news.povray.org...
> Shay <shi### [at] houstonrrcom> wrote:
> > Triangulate the polygons
>
> By the way, that's far from trivial.
>
I never said trivial. <g> Since all of the points lie on a sphere, however,
triangulating them would be pretty straightforward.
-Shay
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
From what I understand your problem the "convex hull" of the points is what
you are looking for. The convex hull is the smallest surface of set of
triangles that contains all of the points in its interior (probably a bad
description). This is the set of triangles that you are looking for. It can
be created in O(n log n) (where n is the number of points). I cannot give
you a detailed algortihm for that right now as I only know it for 2D. But
searching for "convex hull 3d" in google gives plenty of results.
- Micha
--
http://objects.povworld.org - the POV-Ray Objects Collection
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Shay <shi### [at] houstonrrcom> wrote:
> Since all of the points lie on a sphere, however,
> triangulating them would be pretty straightforward.
You'll have to explain that in more detail before I believe it. :)
--
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
