# comp.graphics.algorithms

## Subject: Re: method of separating angles?

wrote in message

> I'm busy with obstacle avoidance, and it's working good. I'm busy with
> a testing program, that generates obstacles. The thing is that I don't
> want the generated obstacles to overlap or collide. There was a great
> deal with vector calculus involved already, but I couldn't understand
> everything in the paper at first.

In my pathfinding system for collision avoidance, I project
a 3D obstacle onto the ground plane and determine the
"envelope" of the 2D projection. In practice, these are
all polygons (not necessarily convex). Visibility graphs are
constructed from these. In a level with a lot of rooms, the
visibility graph is effectively decomposed into small subgraphs,
one per room. You can add waypoints at the doorways
between rooms to connect the subgraphs.

It is not always the case that you want to avoid overlap.
the virtual observer who navigates the environment has
some "radius". Typical shortest path algorithms will generate
paths that "hug" the obstacle boundaries. In a 3D rendering
system, the 3D objects will invariably intersect the near plane
of the view frustum. It is better to "dilate" the obstacles by
the radius (or equivalent) of the observer. To keep things
polygonal, dilation by a square will work fine.

It is also possible that two obstacles are in close proximity,
not intersecting, but the distance between them is smaller
than the observer's radius. He cannot navigate between
the obstacles but a point-source observer can.

So obstacles in the scene might be disjoint, but the 2D
dilated representations can overlap (and in many cases
should overlap).

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