[PLUG] Computational Geometry

Aj Lavin aj at haightmail.org
Sat Apr 13 10:46:44 UTC 2002


On Fri, Apr 12, 2002 at 09:26:31PM -0700, 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).
> 

Hello, interesting problem. I am by no means an expert, but I enjoy a
math puzzle sometimes.

Given what I understand about your problem, I like the idea of using
an octree.

Here's what I am going on:

1) You want to find the shortest distance from a given point to a set
of objects

2) The objects are simple 3d primitives and CSG thereof

3) You will be repeating 1) many times with different reference points
but the same objects.

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

Using an octree, you only need to compute whether the objects
intersect arbitrary axis-aligned cubes. This should be simple and
efficient for primitive shapes and CSG thereof.

I don't know what representation will be best. You might represent
objects by a combination of intrinsic and extrinsic parameters. The
intrinsic parameters depend on the primitive, like a cylinder might
have a radius and height, a box a length, height, and width, a sphere
a radius only. The extrinsic parameters then describe the position and
rotation of the object, together a euclidean transformation. The
rotation might best described as a 3x3 matrix, the columns of which
are the axes of the object. The translation can be a 3 element vector.

You could instead use implicit functions, described earlier in the
thread.

Ok, so basically the algorithm I am thinking of would use the octree
to search for the object-point that is closest to the reference
point. Octants which could feasibly contain the closest point would be
subdivided and labeled with intersecting objects. Octants are feasible
iff they intersect at least one object and are not entirely farther
than any other feasible octant.

Then the process recurses on the child octants until the size of all
remaing feasible octants is less than the tolerance. These octants
represent the closest object points.

When you run the algorithm again with a different reference point, you
can re-use the octree that was derived before, because the objects
have not moved. You start with the smallest octant containing the
reference point, and then search up and down the octree for feasible
octants. As before, the octree is refined until the answer is found.

Periodic octree pruning may be necessary to limit memory usage.

I believe this algorithm might be efficient and easy to implement for
the problem you describe. The error should decrease geometrically with
each iteration. Iterations involve a limited number of primitive-cube
intersection computations. The octree naturally caches the result of
previous computation.

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

Yes, I would think this is a well studied problem. I regret I don't
know enough to suggest a reference. Octrees are just what I would try
because I don't know any better. :)

- Aj




More information about the PLUG mailing list