[PLUG] Computational Geometry

[Fedor G. Pikus]

If your shapes are very simple, i.e. they are known "named" shapes
(spheres, prisms, etc) which can be described by few parameters each, then
your problem is very easy. For such shapes, you can find the minimal
distance from a given point to the shape analytically, as an function of
the same parameters. Some of these expressions may be "conditional" (i.e.
you may have to check which region you're in and then use the right
formula). If your shapes are parts of cilinders, spheres, etc, there will
be more conditions (is the shortest distance to the real part of the shape
or to the cut-off part).
Now, since computing all these distances is very fast, because they are
all rather simple formulas, you can iterate over pretty large number of
shapes before you need to worry about performance. A trivial optimization
with bounding box (or bounding sphere) will quickly take care of all the
distant shapes.
This approach is limited to "known" shapes, i.e. there is a hardcoded set
of shapes you can handle, say, spheres, cylinders, prisms, and piramids.
But as long as that covers your shapes, nothing can beat analytical
formulas.


On 12 Apr 2002, Russell Senior wrote:
>
> >>>>> "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!
>
>

-- 
                                  Fedor G. Pikus
Mentor Graphics Corporation         | Phone: (503) 685-4857
8405 SW Boeckman Road               | FAX:   (503) 685-1239
Wilsonville, Oregon 97070           | http://www.pikus.net/~pikus/