# comp.graphics.algorithms

## Subject: Re: Offset curves on a 3D surface for area coverage planning

<4805455@gmail.com> wrote in message
> Hello. I am looking into existing algorithms for computing offset
> curves on a 3D surface. The intent is to use this algorithm to compute
> a planned path on a 3D surface that completely covers the surface. The
> input will be the 3D surface data and an initial curve over the surface
> to guide the shape of the remaining, offset curves. One application
> might be removing material on a mild 3D surface such as cutting grass
> on some hills. I have seen some work on 2D as it relates to milling,
> but not much on 3D. I do seem to see a lot of computer graphics
> pictures with what looks like what I need, such as the the gargoyle
> found lower down on the following page
> . (Not looking for geodesics
> though). The whole subject is wide open for me:

The generalization of offset curves for a planar curve to
offset curves for a curve on a surface does in fact require
differential geometry and geodesic distance.

> 1. What is the best way to represent the surface?

Use parametric surfaces, (x(u,v),y(u,v),z(u,v)) for
parameters (u,v) in a planar region.

> 2. What is the best way to represent a curve on the surface?

A curve on the surface is generated by a curve in the
parameter plane, (u(t),v(t)) for some interval of t values.
The curve on the surface is
C(t) = (x(u(t),v(t)),y(u(t),v(t)),z(u(t),v(t)))

> 3. How has anyone done this algorithm in 3D already?

Perhaps. My experience with it has to do with generalizing
the following problem that has to do with the "Blum medial
axis". Given a curve (x(t),y(t)) and a radius function r(t) > 0,
the union of all disks with centers (x(t),y(t)) and radii r(t)
forms a planar region. Construct the boundary curve (or
curves).

In 3D, a "disk" with center at a point (x0,y0,z0) and with
radius r > 0 is the set of all points (x,y,z) on the surface
whose geodesic distance to (x0,y0,z0) is smaller or equal
to r. The union of all such disks along a curve on the
surface gives you a surface region. The problem is to
construct the boundary of the region.

Computing geodesic distances on an arbitrary surface is
generally a difficult computational problem, usually solved
by setting up a parabolic PDE whose steady-state solution
is a geodesic curve. Relaxation is applied to an initial
curve so that it evolves eventually to the geodesic curve.
To obtain a reasonable initial guess, you can rasterize the
surface into a 3D grid and use Dijkstra's algorithm to
generate a shortest path through the grid connecting
two voxels representing the end points to be connected
by the geodesic curve.

Another approach is to use "active contours" (sometimes
called "snakes") in the parameter domain of the surface.
Place a closed curve in the parameter domain that contains
your central path. The closed curve can be defined, say,
using control points (or some other parameters). Set up
an iteration scheme to let the closed curve evolve. The
goal is to move the control points to minimize an integral
of the (squared) distance between the curve points and
the central curve. The distance is with respect to the
metric tensor, so you are back to dealing with geodesic
distance.

> 4. Are there any good books on this subject?

I am unaware of any. Most of the useful information is found
in research papers.

--
Dave Eberly
http://www.geometrictools.com