**comp.graphics.algorithms**

## Subject: **Re: method of separating angles?**

news:1148992122.581934.53490@j55g2000cwa.googlegroups.com...

> 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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

method of separating angles? =>Re: method of separating angles? =>Re: method of separating angles? =>Re: method of separating angles? =>Re: method of separating angles? =>Re: method of separating angles? =>Re: method of separating angles? =>

Replies:

Re: method of separating angles?

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.