Accessibility Analysis Using Computer Graphics Hardware.
AbstractAnalyzing the accessibility of an object's surface to probes or tools is important for many planning and programming tasks that involve spatial reasoning and arise in robotics and automation. This paper presents novel and efficient algorithms for computing accessible directions for tactile probes used in 3D digitization with Coordinate Measuring Machines. The algorithms are executed in standard computer graphics hardware. They are a nonobvious application of rendering hardware to scientific and technological areas beyond computer graphics.
Introduction
Reasoning about space is crucial for planning and programming of tasks
executed by robots and other computer-controlled machinery. Accessibility
analysis is a spatial reasoning activity that seeks to determine the directions
along which a tool or probe can contact a given portion of a solid object's
surface. For concreteness, this paper discusses accessibility in the context
of automatic inspection with Coordinate Measuring Machines (CMMs), but
the concepts and algorithms are applicable to many other problems such
as tool planning for assembly [30, 31], sensor placement for vision [14, 28],
numerically controlled machining [3, 6], and so on.

Figure

1: A typical coordinate measuring machine. The large component
directly attached to the touch probe is called the ram.
A CMM (

Figure

1) is essentially a very precise Cartesian robot equipped
with a tactile probe, and used as a 3-D digitizer [2]. The probe, under computer
control, touches a sequence of points in the surface of a physical object
to be measured, and the CMM produces a stream of x, y, z coordinates of
the contact points. The coordinate stream is interpreted by algorithms that
support applications such as reverse engineering, quality control, and process
control. In quality and process control, the goal is to decide if a manufactured
object meets its design specifications. This task is called dimensional inspec-
tion, and amounts to comparing the measurements obtained by a CMM with
a solid model of the object. The model defines not only the solid's nominal
or ideal geometry, but also the tolerances or acceptable deviations from
the ideal [1]. The inspection results are used to accept or reject workpieces
(quality control), and also to adjust the parameters of the manufacturing
processes (process control).
This paper focuses on accessibility analysis for automatic planning and
programming of dimensional inspection tasks with CMMs. Given a solid
model of an object, including tolerances, and a specification of the task (typ-
ically as a set of features to be inspected), the goal is to generate a high-level
plan for the task, and then to expand this plan into a complete program for
driving the CMM and inspecting the object. The high-level plan specifies
how to setup the part on the CMM table, which probes to use and how to
orient them, and which surface features to measure with each setup, probe
and probe orientation. The final program contains specific probe paths and
points to be contacted by the probe tip, and is interpretable by the CMM
controller.
Automatic planning algorithms are beyond the scope of this paper, but a
brief outline of the planning methodology we assume is useful to understand
the role of accessibility analysis. We envisage a planner that operates within
the generate-test-repair paradigm. A tentative plan is generated by taking
into consideration the task and various constraints, the most important of
which is accessibility. A proposed plan is then tested by simulation. If
the test fails, for example because there are tool/workpiece collisions, the
plan is either repaired or a new tentative plan is generated. The generate-
test-repair cycle continues until an acceptable solution has been found. This
architecture requires a smart generator that produces good plans most of the
time, to avoid expensive repair and backtracking. The knowledge obtained
through accessibility analysis guides the plan generator to favorable solutions.
However, a plan proposed by the generator does not necessarily have to be
correct, because no plan is accepted without being tested for correctness.
It follows that the accessibility algorithms used by the plan generator can
produce erroneous results without compromising the correctness of the final
plan. Of course, incorrect results must occur infrequently, or testing will fail
too often and planning will proceed very slowly.
Exact and complete algorithms for accessibility analysis in the domain of
curved objects are either unknown or impractically slow. We present in this
paper several accessibility algorithms that make a variety of approximations
and trade speed of execution for accuracy or correctness. Some of the approximations
are pessimistic, i.e., they may miss correct solutions, typically as a
result of discretizations. Other approximations are optimistic and may sometimes
produce incorrect solutions. (These will eventually be rejected when
the plan is tested.) The algorithms described here have been implemented
and tested on real-world mechanical parts, and have been incorporated in a
prototype inspection planner.
The remainder of the paper is organized as follows. First, related work is
briefly reviewed. Next, we discuss accessibility for the tips of probes. Then
accessibility for the case in which probes are straight, i.e., aligned with the
CMM's ram. Then we consider bent probes, which consist of two non-aligned
components. A final section summarizes the chapter and draws conclusions.
Related Work
2.1 Accessibility Analysis
Spyridi and Requicha introduced the notion of accessibility analysis as a tool
for high-level inspection planning for CMMs [24, 25, 26]. Their implementation
computed exact global accessibility cones (GACs, defined below) for
planar faces of polyhedral parts using Minkowski operations. Sets of direc-
tions, called direction cones, were represented as 2-D boundaries on the unit
sphere and GACs were computed by projecting elements of the Minkowski
sum onto the sphere. Their algorithm proved to be impractical for complex
parts with curved surfaces.
Other researchers computed GACs at single points, thus eliminating the
need of computing Minkowski sums. This is the approach that we take as
well. Lim and Menq used a ray casting technique with an emphasis on
parts with free-form surfaces [11]. Limaiem and ElMaraghy developed a
method to compute GACs that used standard operations on solids [12, 13].
A similar technique was independently developed by Jackman and Park [7].
Medeiros et al. use visibility maps, which provide a representation for non-homogeneous
direction cones [9, 33, 34]. All of the above methods are too
slow for practical inspection planning, where many accessibility cones must
be computed for complex objects.
Accessibility analysis is related to work in other fields. The visibility
problem is a generalization of the global accessibility problem, because directions
of accessibility correspond to points of visibility at infinity [16, 17, 4].
Sensor placement in visual inspection systems is related to the problem of
straight probe accessibility [14, 27, 28]. Other fields which require accessibility
analysis for high-level task planning include assembly planning [30, 31]
and numerically-controlled machining [3, 6, 8, 29, 32].
We are not aware of previous work involving accessibility analysis of bent
probes as introduced in Section 5. The theoretical foundations for bent
probe accessibility appear in [24], and a rigorous mathematical analysis of
accessibility in [23].
2.2 Cubic Maps
We use a cubic mapping of the unit sphere to represent direction cones, i.e.,
subsets of the unit sphere. This technique has been used in other areas of
computer graphics, such as radiosity, shadow computations and reflections.
This is not surprising, because global accessibility is strongly related to global
visibility, as noted above.
Environment (or reflection) maps ([5], pg. 758-759) are a generalization
of the direction-cone map presented here. The environment map holds color
images, while the direction-cone map holds bitmaps. The light-buffer ([5],
pg. 783) is another cubic map that is used to partition the space visible
to a light source. The hemi-cube structure ([5], pg. 795-799) is used to
determine visibility between surface patches and calculate their contribution
to the radiosity equation. Unlike our direction-cone mapping, the hemi-cube
is not aligned with the world coordinate system. It is aligned with each
patch, and therefore is not suitable for Boolean operations between direction
cones.
Shadow maps ([5], pg. 752) are depth images of a scene as viewed from
a light source. These are used to compute the space that is visible to a light
source in order to apply global shading. This is not a cubic map, but the
technique used in the two-pass z-buffer shading algorithm ([5], pg. 752) is
similar to our method of extracting the first-component directions of a bent
probe (Section 5.3).
A CMM has a touch-trigger (or tactile) probe with a spherical tip. We define
the origin of the probe to be the center of the tip. The CMM measures the
spatial coordinates of the tip's center when the tip comes in contact with
an obstacle. We say that a point p is accessible to a tip with respect to
an obstacle X if the tip does not penetrate X when its origin is placed at
p. With CMMs, the obstacle X is normally the workpiece to be inspected.
(Fixturing devices and other obstacles are ignored here, because they are not
relevant to accessibility analysis in the early stages of inspection planning.)
Testing tip accessibility is a simple matter of placing the tip at p and
checking for collisions with the obstacle. Notice that if p is the point to
be measured on the surface of the workpiece, then placing the center of the
tip at p will cause the probe to penetrate the part. Instead, we perform
accessibility analysis for the offset point Figure 2), where r
is the radius of the tip and ~n is the normal to the surface at p. (We assume
that p is not singular, because it is not wise to measure a singular point with

Figure

2: The offset point
(a) (b) (c)
ram
tip
stylus

Figure

3: A straight probe and some possible abstractions
a tactile probe.) For the remaining of this chapter, we ignore these issues
and assume that p is the offset point to be accessed by the center of the tip.
We assume that the CMM has a small number of probes, therefore testing
the accessibility of each tip at each point is reasonable. See [15] for an
alternative approach.
A straight probe (Figure 3a) is attached to the CMM ram (Figure 1), which
is much longer than the probe and aligned with its axis. In the remainder
of this dissertation we refer to the whole ram/probe assembly as a straight
probe and assume in this case that the CMM has a fixed head, such as the
Renishaw PH6 [18]. In general, the straight probe can be any tool, not
necessarily a CMM probe, that is symmetric about an axis. Examples of
GAC

Figure

4: The GAC of point p with respect to obstacle X
such tools are drills, screw drivers and laser range finders.
On the axis of the tool we define a point that is the origin of the tool.
Accessibility analysis for a point p with respect to an obstacle X seeks to
determine the directions of the tool axis, such that the tool does not penetrate
X when the tool's origin is placed at p.
In this section we investigate the accessibility of a point by several straight
probe abstractions. Then we generalize to the accessibility of surfaces and
briefly outline how to apply the results to setup planning for dimensional
inspection with CMMs.
4.1 Half-line Probes
Consider a straight probe abstracted by a half-line that is the main axis of
the probe (see Figure 3b). This is an optimistic abstraction of the probe,
because it ignores the fact that the probe has volume, but it captures the
fact that the CMM ram is typically very long. Furthermore, it is simplistic
enough to give rise to efficient algorithms.
We say that a point p in the presence of obstacle X is accessible if the
endpoint of a half-line can be placed at p while not penetrating X. The
direction of such a half-line is called an accessible direction. The set of all
accessible directions is called the global accessibility cone (GAC) of point p
with respect to obstacle X, and is denoted by GAC(X; fpg).

Figure

4 illustrates the global accessibility cone of a point p with respect
to an obstacle X. GAC(X; fpg) is the highlighted portion of the unit sphere
centered at p. It is easy to verify that the GAC complement is the projection
of X onto the sphere. This forms the basis for our algorithm to compute the
GAC of a point: project the obstacle onto a sphere centered at p and take
the complement.
The global accessibility cone is computed in the same fashion as environment
maps [5]. The obstacle (i.e., environment) is projected onto the faces
(a) (b)

Figure

5: Experimental results - GAC
of a cube centered at p. The cube is aligned with the world coordinate sys-
tem, and each face is a bitmap. The algorithm first sets all the bits of the
cube to 1, then renders the obstacle as 0s in order to delete the projected
obstacle from the direction cone. The remaining directions are the desired
complement set that form the GAC.
The cubic map is used as a non-uniform partition of the unit sphere.
There is a one-to-one mapping between directions and unit vectors in 3-D
space, therefore the cubic map is a discrete representation for a set of directions
or a direction cone. The mapping between a direction and a bit on the
cube involves selecting the appropriate face of the cube, projecting the unit
vector (i.e., direction) onto the face, and normalizing the result to bitmap
coordinates. The direction falls on the face of the cube that lies on the axis
of the largest coordinate of the (x; vector, with the sign of this
coordinate used to distinguish between the two opposing faces.
Figure 5a shows the result of running our algorithm on a real-world mechanical
part, which was modeled in ACIS [22]. The GAC is projected onto
a sphere that is centered about the point of interest (in the center of the
figure). As a preprocessing step, the ACIS faceter produced the mesh that
was used to render the mechanical part. This mesh is a collection of convex
polygons that were not optimized for rendering other than being placed in
an OpenGL display list. The mechanical part contains 103 faces (including
curved surfaces) and the mesh contains 1980 polygons. The code executed
on a Sun ULTRA 1 with Creator 3D graphics hardware, Solaris 2.1 and 128
MB of memory. Direction cones were represented by six 32 \Theta 32 bitmaps, for
a total of 6144 directions at a cost of 768 bytes. The running time for the
algorithm was 0.08 seconds. Not surprisingly, most of the load was on the
graphics hardware.
The complexity of the algorithm described above depends solely on the
time to render the obstacles. The obstacle X may be rendered many times
to compute GACs at different points, so it is wise to optimize the mesh used
to display X. For example, one can use triangle strips [21].
4.2 Grown Half-lines
In the previous section we abstracted a straight probe by a half-line. Here
we generalize this to a half-line that is grown by a radius r (see Figure 3c).
An object grown by a radius r includes all the points that are at a distance
no greater than r from another point in the object [20]. It also equals the
Minkowski sum of the object and a ball of radius r. Thus, a grown half-line
is a semi-infinite cylinder with a hemi-sphere over the base. This leads to a
straight probe abstraction that can serve as an envelope for the volume of a
probe, and therefore is a pessimistic approximation.
It is easy to verify that a half-line grown by a radius r penetrates an
obstacle X iff the non-grown half-line penetrates
grown by r. (This is a well known result in robot motion planning [10].)
In other words, GAC(X " describes the directions from which a point
p is accessible by a half-line grown by r.
A straightforward algorithm to compute GAC(X " fpg) is to compute
the grown obstacle X and to apply the algorithm presented previously in
Section 4.1. Unfortunately, computing the solid model of a grown object is
an expensive and non-trivial task that is prone to precision errors [20] and
produces curved objects even when the input is polyhedral. If the accessibility
algorithm is to be applied many times and for a small set of given radii,
then it may be wise to compute the grown solids as a preprocessing step.
We choose an alternative approach in which we implicitly compute the
grown obstacle, as it is rendered. The main observation is that only
the silhouette of the obstacle is needed as it is projected onto the cubic map.
Therefore, we render a superset of the boundary of the grown object that is
also a subset of the grown object itself. The naive approach is to render each
vertex of the mesh as a ball of radius r, each edge as a cylinder of radius r,
(a) mesh (b) grown nodes (c) grown edges
(d) nodes and edges (e) convex edges (f) offset faces

Figure

Growing a solid
and to offset each polygon by a distance r along the normal. This algorithm
is correct and can be optimized by not rendering concave edges, which will
not be part of the grown obstacle's boundary. A more drastic optimization
can be applied, if the mesh is partitioned into face sets, each corresponding
to a face of the original solid model. Then a facial mesh is represented by
an array of nodes and an array of polygons. Each node corresponds to a
point on the face and the normal to the face at this point. Each polygon
is represented as a list of nodes. To offset a facial mesh, first we offset the
nodes by translating each point along its normal, and then we render the
polygons at these offset nodes. The gain is that the edges and vertices that
are internal to a facial mesh do not need to be rendered as grown entities.
The only vertices and edges of the mesh that are rendered are those which
fall on actual edges of the solid model (see Figure 6).
The spheres and cylinders are rendered as quad strips [21] of very low
resolution to maximize rendering speed. The cylinders contain 6 faces with
no tops or bottoms, because they are "capped" by spheres on either end.
ram
d
r
GAC
(a) (b) (c)

Figure

7: The GAC for the ram component of a straight probe
The spheres are composed of 3 stacks of 6 slices each (latitude and longitude,
respectively). Our results show that these approximations are adequate for
practical problems. Finer approximations can be used for more accurate
results. The running time to compute the GAC of Figure 5b is 1.3 seconds.
4.3 Ram Accessibility
The straight probe abstractions introduced so far have constant thickness.
In practice, the CMM ram is considerably fatter than the probe stylus. An
improved probe abstraction will take this fact into account as shown in Figure
3a. In this case, the probe is modeled by two components, two dilated
half-lines that are aligned with each other, one to model the ram and the
other to model the stylus. Notice that in order for such a probe to access
a point both the ram and the stylus must be able to access it. In other
words, the GAC of such an abstraction is the intersection of the GACs of
each component of the probe. In this section we focus on the ram component.
We model the ram by a truncated half-line (d; 1) that is grown by a radius
r (Figure 7a). A truncated half-line (d; 1) includes all the points on the half-line
at a distance no less than d from the origin. Using similar arguments
as in the previous sections, the GAC for a ram with respect to an obstacle
X is identical to the GAC of the ram shrunken by r with respect to X " r.
The shrunken ram is precisely the truncated half-line (d; 1) (Figure 7b).
We already know how to render therefore we reduced the problem to
computing the GAC for a truncated half-line.
It is clear from Figure 7b that the GAC of a truncated half-line (d; 1) is
the GAC of a half-line but with a different obstacle. The idea is to remove the
irrelevant region from the obstacle. A truncated half-line (d; 1) positioned
at p cannot collide with any portion of the obstacle that is at a distance
closer than d from p. In other words, the ball of radius d that is centered
at p can be removed from the obstacle. The GAC with respect to the new
obstacle corresponds to the GAC of the truncated half-line (Figure 7c).
Calculating the GAC of a truncated half-line (d; 1) then entails subtracting
a ball centered at p from the obstacle and using our algorithm for regular
GACs. However, computing the solid difference between an obstacle and a
ball is an expensive computation that we wish to avoid. In addition, we do
not have a solid model of the grown obstacle itself (see previous section).
Consequently, we choose an alternative approach in which we use clipping
operations to approximate the solid difference. The clipping is performed
during the projection of the obstacle within the GAC algorithm, by introducing
a read-only depth-buffer that is initialized with a spherical surface of
radius d. This is the portion of the sphere that is visible through each face
of the cubic mapping (the depth values are symmetrical for each face). If the
depth-buffer is enabled with a "greater-than" comparison, then the clipping
operation will approximate the subtraction of a ball of radius d, as needed.
Notice that, in general, the clipping operation is an operation between
surfaces and not a Boolean operation between solids [19]. In our case, we
position the far clipping plane beyond the obstacle. This ensures that the projection
of the solid difference is correct, because a truncated half-line (d; 1)
positioned at p intersects X iff it intersects the boundary of X. Therefore,
the point of intersection is rendered along with the boundary of X and it is
not clipped, because it is within the viewing frustum and not closer than d
to the viewer.
The quality of the approximation depends on the depth-buffer precision.
To maximize the precision of the depth-buffer, the distance between the far
clipping plane and the near clipping plane should be minimized. Therefore,
the far clipping plane should be a tight bound on the obstacle - we use the
diameter of the bounding box as a reasonable bound. The near clipping plane
is set to a distance of d=
3, so that the near face of the viewing frustum is
contained in the ball of radius d.

Figure

8 shows the viewing volume through a single face of a cube centered
at p. The size of the cube is irrelevant, since the result is projected onto
the face. The near and far clipping planes are labeled
d
f
Z Z
d=f
r
r

Figure

8: The viewing volume for truncated half-lines (d; 1) and (0; d)
respectively. The viewing volume is bound by the clipping planes and is
shaded in the figure. The lighter shade corresponds to the volume clipped by
the depth-buffer, which is initialized to be the sphere of radius d centered at p.
The left hand side of the figure is the desired viewing volume for a truncated
half-line (d; 1). The far clipping plane is assumed to be beyond the obstacle.
It is easy to see that the near clipping plane must satisfy
3.
The complexity of the algorithm is identical to the regular GAC algorithm
with the addition of depth-buffer comparisons and the overhead of initializing
the depth buffer with a spherical surface. The depth-buffer comparisons are
performed in hardware and should have negligible run-time overhead. Notice
that the depth-buffer is read-only, thus it needs to be initialized only once.
In addition, the same depth buffer may be used for all probes that have a
stylus of length d. Therefore, the cost of initializing the depth-buffer may be
amortized over many direction cones.
Our results show that the cost of computing the GAC for a truncated
half-line is identical to the cost of computing a regular GAC. The cost of
initializing the depth-buffer is negligible, because the buffer is relatively small
(32 \Theta 32 bits).
To review, Figure 9 illustrates the GACs computed with our system for a
simple "L" shaped obstacle. The left column shows the GACs for the original
obstacle, and the right column shows the GACs with respect to the obstacle
regular obstacle grown obstacle
(a) (a')
half-line
(b) (b')
truncated
(c) (c')
truncated
(0;
d)
(d) (d')

Figure

9: The variety of GACs for straight probe abstractions
grown by a constant radius. Figure 9c' shows the GAC for a truncated half-line
(d; 1) with respect to a grown obstacle, which is precisely the GAC for a
ram. The last row of this figure illustrates the GACs for truncated half-lines
(0; d), which will be introduced in Section 5.1.
To aid visualization, the 3-D cones have been rendered with transparent
material. For example, the GAC in Figure 9b has 3 shades of gray. The
lightest shade of gray is on the bottom of the cone. This portion includes
the directions that go out of the page and downward. The top potion of
the cone is darker, because it includes both outward directions and inward
directions. In other words, two surfaces overlap. They are both rendered,
because the cone is transparent. The intermediate shade of gray (in the
nearly rectangular region) only includes directions that go into the page and
away from the protrusion on the obstacle.
4.4 Surface Accessibility
Up to this point we have discussed the accessibility of a single point. Now,
we extend the notion of accessibility to arbitrary regions of the workspace,
which we call features. For dimensional inspection, these are normally surface
features on the boundary of a workpiece. The goal is to find the set of
directions from which a straight probe can access all the points of a feature.
The global accessibility cone of a feature F with respect to an obstacle
X is denoted by GAC(X;F ), and corresponds to the directions from which
all the points in F can be accessed by a half-line. Clearly, this cone is the
intersection of the GACs for all the points in F . Notice that GAC(X; fpg)
is a special case - the GAC of a feature containing a single point p.
Exact GACs for planar surfaces and polyhedral obstacles can be computed
using Minkowski operations [24]. Algorithms for Minkowski operations
are expensive, do not scale well, and are not available for curved surfaces.
We choose an alternative approach in which we sample a few points from
F and compute the intersection of the GACs at these points. This approximation
is especially suitable for CMMs, which are normally restricted to
inspect discrete points. In addition, computing the intersection of direction
cones represented by cubic maps is an efficient and trivial operation on
bitmaps. The approximation is optimistic because it is a lower bound on the
intersection of the infinite number of GACs for all the points of the feature.
Notice that the direction of the straight probe corresponds to the direction
of the CMM ram with respect to the workpiece. Therefore, we can use this

Figure

10: Setup planning with a straight probe
direction to represent the orientation of the workpiece setup on the CMM
table. Computing the GAC for a feature translates to finding the set of
setup orientations from which the entire feature can be inspected. If the
GAC of a feature is empty, then this feature cannot be inspected in a single
setup orientation. (In this case the feature is segmented into sub-features or
a different probe is used.)
For dimensional inspection planning, computing the GACs for all surface
features that need to be inspected may be the first step of a high-level planner.
Clustering these GACs can produce a minimum number of workpiece setup
orientations. This is a very important characteristic, since each setup change
is usually a time-consuming manual operation.

Figure

shows the usefulness of accessibility analysis for spatial reason-
ing. In this example, we computed the GACs of all the faces of the work-
piece. The cones where partitioned into three clusters, each cluster composed
of cones whose intersection is not empty. A direction was chosen from each
cluster. The result is that each face can be accessed from at least one of
these directions. The directions of the probes and the faces on the part are
color coordinated (or in different shades of gray) to illustrate which faces a
probe can access.
4.5 Path Accessibility
When the CMM inspects a point, the probe normally traverses a short path,
which we call an approach/retract path. This path is along a line segment
that is normal to the point of contact and is proportional in length to the
ram
tip
stylus
(b)
(a)
rotary joint
tip
2nd component
1st component
d

Figure

11: A bent probe and a possible abstraction
size of the tip. The probe will approach the point in a slow motion along this
path and then retract. The idea is to minimize crashes at high speed and to
maximize the accuracy of the measurement.
The goal is to find the set of directions from which a probe can access all
the points along the approach/retract path, so that the entire path (minus
the endpoint) is collision free. Notice that the path can be viewed as a feature
in the system, thus all the arguments from the previous section hold true.
Since the approach/retract path is typically short relative to the size of the
workpiece, it is reasonable to approximate this path by its two end points.
Again, this is an optimistic approximation.
5 Bent Probes
Orientable probes, such as the Renishaw PH9, are more expensive than
straight probes, but much more versatile, and are used often in CMM in-
spection. The probe can be oriented in digital steps under computer control.
We consider the whole ram/probe assembly as forming a bent probe, which is
not necessarily aligned with the ram. A bent probe is a linked chain of two
components that are connected at a 2 degrees-of-freedom rotary joint.
We model the probe by a 2-component abstraction as in Figure 11b.
The first component is a truncated half-line (0; d) straight probe abstraction,
which includes all the points of a half-line at a distance no greater than d
from the origin. The center of the tip of the bent probe coincides with the
tip of the first component. The second component is a half-line or straight
probe abstraction with endpoint at a distance d along the axis of the first
component. This endpoint corresponds to the probe's rotary joint.
d
qF
GAC
(a) (b) (c)

Figure

12: Computing D 1
and a portion of D 2
For the rest of this section we assume that a bent probe has no volume,
i.e., it is modeled by (truncated) half-lines. Similar generalizations, such as
grown half-lines, can be introduced very easily in the manner of Section 4.2.
Additionally, one can generalize the bent probe concept to more than 2 com-
ponents, but we will not do so here.
The length of the first component, d, is a constant. Therefore, we can
describe the configuration of a bent probe by using a pair of directions -
one for each component of the probe. The result is that a GAC for a bent
probe is a 4-D cone. Fortunately, applications normally need the second
component directions rather than the entire 4-D cone. For example, as with
straight probes, the directions of the second component are used to find a
minimal number of orientations for setting up the workpiece on the machine
table.
The remainder of this section is outlined as follows: Section 5.1 introduces
the GAC for the first component of a bent probe, Section 5.2 shows how to
compute the GAC for the second component of a bent probe, and Section 5.3
shows how to compute the first component accessibility given a direction of
the second component.
5.1 First Component Accessibility
The first component of a bent probe is a truncated half-line (0; d). This is
the complement of the ram abstraction that was introduced in Section 4.3.
Assume that the point of interest is p and the obstacle is X. Then, using
arguments similar to those of Section 4.3, the GAC for the first component is
a regular GAC after the irrelevant parts of the obstacle have been removed.
In this case the obstacle is intersected with the ball of radius d centered at
(see

Figure

12a-b). We denote the GAC of the first component of a bent
probe by D 1 (X; fpg). It is assumed that d is known, therefore, for clarity, it
is omitted from D 1
Notice that D 1 is exactly the set of accessible directions for the first component
of a bent probe when the second component is ignored. This means
that given a direction in D 1
(X; fpg), then a truncated half-line (0; d) that is
oriented along this direction and with an endpoint at p will not penetrate X.
However, D 1
is only an upper bound on the accessible directions of the first
component when the whole probe is taken into account, because it is not
guaranteed that an accessible second component direction exists for every
direction selected from D 1 .
The algorithm to compute D 1
uses a spherical surface in the depth buffer
to approximate the intersection of the obstacle with a ball of radius d. This
is similar to the algorithm used to compute the ram GAC for a truncated
half-line (d; 1) but now the depth-buffer acts as a far clipping surface (see
right hand side of Figure 8). If the depth-buffer is enabled with a "less-than"
comparison, then the clipping operation will approximate the intersection of
a ball, as needed.
Again, the quality of the approximation depends on the depth-buffer pre-
cision, therefore the distance between the far clipping plane and the near
clipping plane should be minimized. We assume that the studied point is accessible
to the probe's tip (see Section 3). Therefore it must be at a distance
of at least r from the obstacle, where r is the radius of the tip. The near
clipping plane is then set to a distance of r=
3, which is the furthest it can
be and still have the viewing volume include all the points that are outside
of the tip (see right hand side of Figure 8). The far clipping plane is placed
at a distance d, which is a tight bound on the ball of radius d.
The clipping operation is only an approximation of the Boolean intersection
between the obstacle and the ball. However, since the near clipping
plane does not intersect the obstacle (based on the assumption that the tip
does not penetrate the obstacle), then we argue that the projection of the
clipped obstacle is correct. Section 4.3 gives a similar argument using the far
clipping plane.
The complexity of computing D 1
, i.e., the GAC of a truncated half-line
(0; d), is identical to the complexity of computing the GAC of a truncated
probe (d; 1), which is the abstraction of a shrunken ram (see Section 4.3).
Our experiments confirm this fact and show that the cost of computing D 1
is
nearly identical to the cost of computing a regular GAC. Figure 9d illustrates
the D 1
cone with respect to a simple obstacle. Notice that the GAC in
Figure 9b is the intersection of the cones in Figure 9c and Figure 9d. This
illustrates the fact that an accessible direction of the probe as a whole must
be a common accessible direction of its components.
5.2 Second Component Accessibility
When the first component takes every possible orientation in D 1
, the articulation
point between the first and second components traverses a locus which
is the projection of D 1
on a sphere of radius d that is centered at p. Without
loss of generality we assume that p is the origin, and we denote this locus by
, since it is also the result of scaling D 1
by a factor of d.
If we succeed in placing the second component such that the articulation
point lies in dD 1
, it is clear that the first component can be placed with its
tip at the origin without collisions. In other words, if the second component
can access some point of dD 1 , then the entire probe can access the origin.
The converse is also true and therefore the origin is accessible iff the second
component accesses some point of dD 1
(see

Figure

12).
The set of directions for which the second component can access at least
one point of dD 1 is called the weak GAC of the feature dD 1 . In general, the
global accessibility cone of a feature F with respect to an obstacle X,
is denoted by WGAC(X;F ), and corresponds to the directions from which
at least one point in F can be accessed by a half-line (notice the analogy
to weak visibility [16]). While the GAC of a feature is the intersection of
the GACs of all the points in the feature, the WGAC of a feature is the
corresponding union.
We denote the GAC of the second component as D 2
. Then D 2
WGAC(X;F ), where the feature F is D 1
(X; fpg) scaled by d about the point
p. To compute D 2 we sample points on F and take the union of the GACs
at these points. This is a lower bound on the real D 2
, so it is a pessimistic
approximation. Figure 12c shows F when p is the origin, and illustrates the
GAC of a point q sampled on F . This GAC will be a part of the union that
forms D 2 .
Notice that the accessibility of a point by a bent probe is weaker than the
concept of approachability. The fact that a bent probe can access a point does
not guarantee that there exists a collision-free path for the probe to reach the
point. (This happens to be true with straight probe abstractions.) Figure 13
shows an example of a point that is accessible, but not approachable by a

Figure

13: A point that is accessible but not approachable by a bent probeX
d
eye
not obstructed by X
portion of dD1 that's

Figure

14: Computing D 0ae D 1 that corresponds to ~
bent probe with the given obstacle. Computing the approachable directions
for the second component of a bent probe is a problem that can be as hard as
the FindPath problem [10]. We use accessibility instead of approachability,
because of the efficient algorithms that are available. A generate-and-test
planner, as described in the introduction, will have to verify the approach-
ability condition with a path planner or a simulator. Our experiments on
real-world mechanical parts show that failures of this kind occur infrequently.
5.3 First Component Accessibility Revisited
We have shown how to compute the GAC of the first component, D 1 , and
from this the GAC of the second component, D 2
. The D 2
cones are used
to compute setup orientations from which points are accessible to the bent
probe. Once a setup is selected, we wish to compute the directions from
which the first component of the probe can access a point.
Given a direction of the second component, ~
, what are the corresponding
directions of the first component for the bent probe to access a
point p? Without loss of generality we assume that p is the origin, then the
articulation point must lie in dD 1 . Hence, for each ~
we are looking
for the directions ~
, such that the second component oriented along ~
and with endpoint at d~v 1 does not collide with X. Spyridi [24] observed that
these directions correspond to the points on dD 1
that are not obstructed by
X in the orthographic projection of dD 1
onto a plane perpendicular to ~

Figure

14 illustrates this fact. The projection lines in the figure correspond
to possible placements for the second component.
We use this observation in our algorithm to compute the subset D 0ae D 1
that corresponds to ~
. The viewing parameters for the orthographic projection
are depicted in Figure 14. We use a parallel projection with direction ~
and a view port large enough to enclose the projection of the ball of radius
d, which is a superset of dD 1 . To check if a point on dD 1 is obstructed by
the obstacle X we use the depth-buffer in a process that is similar to the
two-pass z-buffer shading algorithm [5]. First, we render X into the depth-
buffer. Next, we check if a point is obstructed by X by transforming it to
the viewing coordinates and comparing its depth value with the value in the
depth-buffer. It is not obstructed by X iff its depth value in the appropriate
depth-buffer location is closer to the viewer. Note that D 1
is represented by
bitmaps on the faces of a cube and therefore dD 1 is also discretized. This
is another approximation used by the algorithm. To maximize depth-buffer
precision, the distance between the near and far clipping planes should be
minimized, while still enclosing the obstacle.
The top of Figure 15 illustrates the result of computing D 1 . The length of
the probe, d, is equal to the radius of the sphere used to represent the cone.
It took 0.07 seconds to compute D 1
. The bottom of the figure shows the
accessible directions for the first component of a bent probe, D 0, given that
the second component is normal to the figure. Notice that these directions
are exactly those that are not obstructed by the obstacle in the given view
(some of the obstructed direction are inside a slot). It took 0.07 seconds to
compute D 0. The inaccuracies in the cone are due to aliasing effects from
the use of the same low resolution frame buffer (32 \Theta 32 bits) as with the
GAC algorithm and the limited precision available with the depth-buffer. In
addition, Figure 15 is illustrated with a perspective projection rather than an
orthographic projection, which is used to compute the obstructed directions.
Figure

15: Experimental results - D 1
and D 0
6 Summary and Conclusions
This paper describes simple and efficient algorithms that exploit computer
graphics hardware to compute accessibility information for applications in
spatial reasoning. Our approach is an unconventional application of graphics
hardware. We approximate spherical projections using perspective projec-
tions, and we use clipping and the depth-buffer to approximate the intersection
and the difference of a solid with a sphere. The depth-buffer is also
used to compute the articulation points (between the first and second components
of a bent probe) that are not obstructed by an obstacle under an
orthographic projection.
The algorithms have been implemented and tested. The empirical results
are satisfactory for practical applications with parts of realistic complexity.
A dimensional inspection planner that uses the accessibility tools presented
here is currently operational, and will be described elsewhere.

Acknowledgments

The research reported in this paper was supported by the National Science
Foundation under grants DMI-96-34727 and DDM-87-15404.



--R


Coordinate measuring machines and systems.
Computing machinability on three-
Computer graphics.
Computer Graphics: Principles and Practice.
Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC machining
Probe orientation for coordinate measuring machine systems using design models.
Manufacturing processes.
Part orientations for CMM inspection using dimensioned visibility maps.
Robot Motion Planning.
CMM feature accessibility and path genera- tion
A general method for accessibility analysis.
A general method for analysing the accessibility of features using concentric spherical shells.
Automatic inspection of three-dimensional geometric features
Efficient algorithms for local and global accessibility shading.
Art Gallery Theorems and Algorithms.
Visibility. In Jacob E.
Renishaw Inc.
Interactive inspection of solids: Cross-sections and interferences
Offsetting operations in solid modelling.
The OpenGL graphics system: A specification (version 1.1).

Accessibility analysis for planning of dimensional inspection with coordinate measuring ma- chines
Automatic Generation of High Level Inspection Plans for Coordinate Measuring Machines.
Accessibility analysis for the automatic inspection of mechanical parts by coordinate measuring ma- chines
Accessibility analysis for polyhedral objects.
Computing occlusion-free view- points

Accessibility analysis in 5-axis machining of sculptured surfaces
On Geometric Assembly Planning.
Geometric reasoning about assembly tools.
Visibility maps and spherical algorithms.
Automated feature accessibility algorithm for inspection on a coordinate measuring machine.
Automating probe selection and part setup planning for inspection on a coordinate measuring machine.
--TR

--CTR
Aristides A. G. Requicha , Steven N. Spitz, Spatial modeling and reasoning for automatic dimensional inspection, From geometric modeling to shape modeling, Kluwer Academic Publishers, Norwell, MA, 2002
A. James Stewart, Vicinity Shading for Enhanced Perception of Volumetric Data, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.47, October 22-24,
Min Liu , Karthik Ramani, Computing an exact spherical visibility map for meshed polyhedra, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
rasterizing computer graphics hardware;visibility;spatial reasoning;direction cones;visual inspection;dimensional inspection planning;configuration space;accessibility analysis;CAD/CAM;coordinate measuring machines