Thread Subject: transform arbitrary 3-D scattered points into a sphere of points

I realize this isn't a technical question per se, but I think that
some of you may have some insight into this type of problem.

I have a set of x,y,z arbitrarily scattered points/particles that I
would like to collapse into a sphere containing the same number of
particles, all are on the same 3-D grid with no overlapping
particles. For example, the grid has a 1.0 spacing in x, y, z
directions, some of the grid points are initially occupied with
particles in the domain (51x51x51), most points are not.

I would like to "walk" or move the particles toward the center of the
domain (defined as 0,0,0), but need to do it in (at least) 10 steps so
I can do some analysis on the intermediate steps. "Teleporting" is
fine, it doesn't have to random walk.... just as long as the general
progress is "collapsing" in some fashion.

One idea is a 3-D random walk, avoiding occupied sites, proceeding
generally inward. If I loop over all points and let it make a step
each time, then eventually it will collapse, but may take a longer
time as it gets closer to a spherical shape. The other idea I had
was to simply teleport along a straight line toward the center, each
iteration would check for open spots nearby and occupy them. It
should fill sphere shape faster.

I guess this is essentially "volumetric morphing" .. . any thoughts
about relatively efficient / novel methods for doing this?

Thanks,
-Ben

Ben <jbenjam@gmail.com> wrote in message <0b53be5b-dc84-441b-
80bb-4cd283fa67fe@26g2000hsk.googlegroups.com>...
> I realize this isn't a technical question per se, but I think that
> some of you may have some insight into this type of problem.
>
> I have a set of x,y,z arbitrarily scattered points/particles that I
> would like to collapse into a sphere containing the same number of
> particles, all are on the same 3-D grid with no overlapping
> particles. For example, the grid has a 1.0 spacing in x, y, z
> directions, some of the grid points are initially occupied with
> particles in the domain (51x51x51), most points are not.
>
> I would like to "walk" or move the particles toward the center of the
> domain (defined as 0,0,0), but need to do it in (at least) 10 steps so
> I can do some analysis on the intermediate steps. "Teleporting" is
> fine, it doesn't have to random walk.... just as long as the general
> progress is "collapsing" in some fashion.
>
> One idea is a 3-D random walk, avoiding occupied sites, proceeding
> generally inward. If I loop over all points and let it make a step
> each time, then eventually it will collapse, but may take a longer
> time as it gets closer to a spherical shape. The other idea I had
> was to simply teleport along a straight line toward the center, each
> iteration would check for open spots nearby and occupy them. It
> should fill sphere shape faster.
>
> I guess this is essentially "volumetric morphing" .. . any thoughts
> about relatively efficient / novel methods for doing this?

Sorry, but I need a better description of
your goal here.

You have a list of points in 3-d, that you
wish to move onto the surface of a unit
sphere?

Assuming that your points will move along
a linear path towards the origin, whats the
problem?

% pick a random set of points in a cube.
xyz0 = (rand(100,3)-.5)*50;

% the distance for each point from the origin
D = sqrt(sum(xyz0.^2,2));

% their final location on the surface of
% a unit sphere
xyzfinal = xyz0.*repmat(1./D,1,3);

% You apparently want the points to
% move slowly from xyz0 to xyzfinal
% Here we will do so in 11 linear steps
plot3(xyz0(:,1),xyz0(:,2),xyz0(:,3),'ro')
hold on
for t = 0.1:.1:0.9
  xyzt = xyz0*(1-t) + xyzfinal*t;
  plot3(xyzt(:,1),xyzt(:,2),xyzt(:,3),'g.')
end
plot3(xyzfinal(:,1), xyzfinal(:,2), xyzfinal(:,3),'bo')
hold off
box on
grid on

I honestly don't know if this is what you
are trying to do.

John

Hi John,

Thanks. This is close, but I'm thinking about the points forming a
"solid" sphere, rather than the surface.

The points need to remain on a 3-D lattice point at each step. Using
your solution, snapping to the lattice sites would be required at each
step. Because of the requirement that the points remain on the
lattice, there would need to be a way to check for occupied lattice
sites, especially as the points get closer to the center.

Imagine scattered marbles attracted by a source of gravity at the
origin. They will bump around but eventually form a "sphere" of
marbles (still remaining on lattice points). Of course it won't be a
perfect sphere, since we're talking about discrete points.

The purpose of this exercise is to transform a non-spherical object
into a sphere through multiple steps. At each step I do some
electromagnetic calculations on the current shape to see how this
transformation influences the calculations of interest. The code I
use to do these calculations treats the points as discrete dipoles, so
they are each representing a bit of mass, hence the need for lattice
sites and non-overlap.

I could use your idea, but at each step, update the directions the
particles will go in order to approach a sphere.
Overlap and snapping isn't really a problem, but it limits where the
points can move.

Cheers,

-Ben

In article <580bcf52-67eb-4841-9f38-1d273a43caba@m36g2000hse.googlegroups.com>,
Ben <jbenjam@gmail.com> wrote:

>The purpose of this exercise is to transform a non-spherical object
>into a sphere through multiple steps. At each step I do some
>electromagnetic calculations on the current shape to see how this
>transformation influences the calculations of interest. The code I
>use to do these calculations treats the points as discrete dipoles, so
>they are each representing a bit of mass, hence the need for lattice
>sites and non-overlap.

That imposes distinct restraints compared to your original problem
statement.

Your original problem statement would be, it seems to me, most easily
solved by working in reverse, starting with the semi-spherical form and
moving objects -outward-. The outermost layer of the sphere could move
full distance the first step, the next layer could move at the very
least to inside the new outer layer (and possibly further since in the
original statement you did not indicate that everything moved at the
same speed for the same length of time per step, so the second layer
could move more slowly until it had a clear path to its final location
on the outside and then could move faster.)

You may have been -thinking- about smooth movement and attractions
and what-not in your original problem statement, but you only asked
how the particle movements could be modelled efficiently, and my answer
to that is "model them in reverse, in layers, so that you don't have to
worry about the collisions very much." Efficient, see? ;-)

But if the destination of a particle depends upon interactions with
other nearby particles, then unless you can reasonably model the
reverse interaction, you would have to move your simulation forward,
not able to use the reversing strategy. And that's probably going to
end up less efficient. For one thing I think you may have to give
up your original statement about teleportation: if you are doing
electromagnetic calculations, then as two dipoles pass very close to
each other there would be a quite noticable interaction changing
the path of both dipoles; the teleportation model you mentioned before
implies that the two dipoles are "blind" while in movement.
--
   So you found your solution
   What will be your last contribution?
   -- Supertramp (Fool's Overture)

On May 12, 1:39 pm, rober...@ibd.nrc-cnrc.gc.ca (Walter Roberson)
wrote:
> That imposes distinct restraints compared to your original problem
> statement.

My original statement was not explicit enough.

I agree that if I were considering a time dependence here, then I
would need to consider the dipole-motion-dipole interaction. However,
what I am doing is taking "snapshots" of intermediate forms: let's
assume that they've achieved quasi-steady state (i.e. have stopped for
a long time) at each of the 10 steps.

So really this comes back to a problem of modeling the motion of "hard
spheres" (although with no momentum/collisions) moving on lattice
points. The "transformation" of the points from a non-sphere shape
to spherical shape is artificial and not necessarily physical. The
only physical constraints that I impose for each point are the hard
sphere, no collision, and stay-on-the-lattice constraints. [I only
mentioned dipoles because the EM code treats each point as a dipole
when it does the calculation for a given fixed shape: No time
dependence (which is good).]

Given this, the problem seems equally "challenging" in forward and
reverse directions. Imagine if your original shape is a disc
(composed of points on a lattice), and you want the final shape to be
a sphere (composed of points on a lattice). Going forward or
backward, you still have the problem of collisions/lattice occupying
etc.
This generated the "random walk" idea I mentioned in the original
post, and I'm still leaning toward it -- walking the points from one
place to another.

 I already have written a 3-D random walk code on a lattice with
occupied site avoidance, so I think that I'll just stick with that and
let it crank away. I may need a way to force a faster convergence to
the sphere though.

Thanks for your comments!

-Ben

In article <1829870a-6cb6-46a7-b758-9d19c42351c7@l64g2000hse.googlegroups.com>,
Ben <jbenjam@gmail.com> wrote:

>Given this, the problem seems equally "challenging" in forward and
>reverse directions. Imagine if your original shape is a disc
>(composed of points on a lattice), and you want the final shape to be
>a sphere (composed of points on a lattice). Going forward or
>backward, you still have the problem of collisions/lattice occupying
>etc.

If the radius of your sphere is greater than or equal to the number
of time steps, then if you work in reverse you do not need any
collision detection. Step 1: Peel off the outer layer of the sphere and
move those points in a single step to their final destinations on
the outer edge of the disk. Step 2: peel off the new outer layer
of the sphere and move those points in a single step to their final
destinations lining the inside of the outer edge of the disk. Repeat
for each radii of the sphere. If the radius of the original sphere
exceeds the timestep, insert timesteps will null moves, or split
some of the steps to only move (e.g.) half way to the final destination.

The specific case of a sphere to a disk involves only deterministic
destinations: the destinations inside the disk can be calculated
by knowing the spherical coordinates of the points. You only
have to establish one line of symmetry, to deal with rise vs fall.

It is of course entirely true that this is not a smooth movement
of the points; smoother movement of the points could probably be
achieved, with it probably being calculable in advance exactly
how many layers at once could move without collisions at a given
velocity. But jerky layer-by-layer forward movement satisfies the
terms of the original problem statement, which asked only about
the transformation of the points into a sphere. Constraints
about where it is "reasonable" for a point to move at any one
time complicate matters.
--
  "The whole history of civilization is strewn with creeds and
  institutions which were invaluable at first, and deadly
  afterwards." -- Walter Bagehot