[PLUG] Computational Geometry

[Russell Senior]

>>>>> "Fedor" == Fedor G Pikus <fedorp at wv.mentorg.com> writes:

Fedor> The solution to your problem depends greatly on how the
Fedor> geometries are specified. If you have formulaes, i.e. f1(x, y,
Fedor> z) = 0, f2(x, y, z ) = 0, etc, then what you have is a
Fedor> non-linear optimization problem: find minimum of a certain
Fedor> function or the smallest of minimums of several functions.

The objects will all be in the form of 3D primitive shapes: cylinders,
spheres, toroids, boxes, maybe more general primitives, all
parametrized, and possibly composites of these, maybe using
Constructive Solid Geometry (CSG) boolean operations.  The set of
shapes might come out of a CAD or similar program (directly or
indirectly).

So, part of my question is how are such shapes usually represented?
And secondly, what algorithms exist that are applicable (or even
specific) to those shapes and representations?  Generally, I expect to
have to iterate over all the shapes in the model, computing the
distance to each one and picking the smallest.

Fedor> There are, of course, various optimization techniques, for
Fedor> example using bounding boxes on the shapes to quickly determine
Fedor> which ones are definitely not the closest one.  

Yeah, I had thought of that possibility.

Fedor> Mathematically, your problem is not specific to geometry, but
Fedor> is an optimization problem, of one of several kinds. After you
Fedor> determine what type of optimization problem you are dealing
Fedor> with, look for books on optimization.

My problem seems like something that someone else would have solved
before.  I was hoping I could converge on a suitable approach fairly
quickly, but even without that, if someone could just point me at a
resource that surveyed what I needed to get up-to-speed, that would be
great.

For those interested, I am preparing to rewrite a program that
computes space potential and electric field using a monte-carlo
random-walk procedure.  From each point of interest, a large number of
random walks are launched which ultimately terminate on a conductor in
the model, which has a specified potential (i.e. voltage).
Statistically, the space potential of the point of interest is equal
to the product of the probability of landing on the conductor and its
voltage.  I am not an EE so I don't quite understand why that works,
just that, as revealed wisdom, it apparently does.  Each step of the
random walk has a length equal to the distance of the nearest surface,
which means that computing the distance is in the inner-most loop of
the algorithm and so doing it as efficiently as possible is a Good
Thing.

The version I am working from was written by an EE in Fortran "some
time ago", originally to run on big iron and later minimally ported to
MS Fortran on NT.  I am rewriting it to try to take advantage of
"advances" made in the interim, tighten up a few algorithmic things,
and also to give us more operational flexibility (better control over
input and output, etc).  Also probably design in some distributed
computation (since the random walks are pretty much independent
operations and there are lots of them).

Thanks!

-- 
Russell Senior         ``The two chiefs turned to each other.        
seniorr at aracnet.com      Bellison uncorked a flood of horrible       
                         profanity, which, translated meant, `This is
                         extremely unusual.' ''