**comp.graphics.algorithms**

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

<4805455@gmail.com> wrote in message

news:1145063767.401088.259900@u72g2000cwu.googlegroups.com...

> 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

>

> 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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Offset curves on a 3D surface for area coverage planning =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.