From wsommer@ping.at Sat Jan  7 08:27:06 1995
Date: Sat, 7 Jan 1995 16:26:52 +0100 (MET)
From: Wolfgang Sommerer <wsommer@ping.at>
Subject: paper.tex
To: vladik@cs.utep.edu
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Transfer-Encoding: QUOTED-PRINTABLE
Content-Length: 13680
Status: RO
X-Lines: 430

\documentstyle[IEEEtran,psfig]{article}

\begin{document}

\title{Rendering Swept Volumes \\ Using \\ Interval Methods \\[0.5em]\norma=
lsize{Extended Abstract}}
\author{Wolfgang A. Sommerer, Monika Kerbl}
\maketitle

\section{Introduction}

Most manufacturing processes are based on the principle of material removal=
.=20
Different process types exist, each of them having its importance in divers=
e fields=20
of the industry.=20

One process type in common use is milling. This process uses a rotating too=
l which=20
is moved along some path to produce the desired product shape. Other proces=
ses that
must be mentioned here are turning (where a moving tool removes material fr=
om a
rotating part) and sheet punch, to mention just a few. In case of the milli=
ng=20
process the motion of the tool can be performed in three, five or more axes=
=20
(i.e., degrees of freedom).

These manufacturing processes have one common feature: material removal thr=
ough=20
movement of some tool.

Most of the machines in use today are programable, i.e., have a controlling=
 unit=20
attached which directs the tool according to a given part program (NC progr=
am).=20
Different methods for programing these controllers exist.=20

In almost common use today are CAD/CAM systems which semiautomatically crea=
te=20
NC programs by analysing the part shape. Since these tools allow the easy c=
reation=20
of complex programs (i.e., thousands of source lines), program validation h=
as=20
become a major problem.=20

Traditionally, program validation is done by stepwise execution of the prog=
ram on=20
the target machine under close control by an operator. The possible damage =
done to=20
the machine by an undetected program error can be severe. Also, the cost in=
volved=20
in using machines which are part of the normal production cycle are signifi=
cant,=20
thus making alternative approaches to program validation attractive.

One such approach is program simulation by solid modeling \cite{M=E4ntyl=E4=
 1988}. The machining=20
process is simulated by performing Boolean set difference operations betwee=
n the=20
workpiece and the swept tool volumes.=20

Different data structures and algorithms have been proposed for representin=
g and=20
analysing swept volumes \cite{Wang 1986,Menon 1994,Snyder 1992,vanHook 1986=
}. Due to the inherent complexity of the problem=20
to be solved, these approaches made trade-offs either in generality or=20
time-efficiency. We present a general, time efficient solution which makes =
use of=20
interval analytic methods for rendering swept volumes.


\section{Swept Volume}

In a 2D or 3D space, a swept volume is described as the totality of all poi=
nts=20
that belong to the trace of a generating object moved along some path.

Figure 1 shows a simple example of a sweep operation in Euclidean 2D space.=
 The=20
generating object moves along the path, indicated by the dashed arc, from=
=20
position 1 to position 4. The swept area is the set of all points covered b=
y the=20
generator during its movement along the given path.

\centerline{\psfig{file=3Df1.ps}}

{\centerline{\noindent\small Figure 1: Swept area of a circle moving along =
an arc.}}

\medskip

In Euclidean 3D space, we can describe a solid by the implicit equation=20
\cite{Duff 1992}:\\

{\noindent
$f(x,y,z) \le 0$ , \hspace*{1cm} $f:R^3 \rightarrow R $ \hspace*{2cm}(1)
}
\\

Given a coordinate transformation function\\

{\noindent
$m((x,y,z),t)$,$t \in \tau =3D [t_S,t_E]$,$m:R^3$x$ R\rightarrow R^3$=20
\hspace*{1.8mm}(2)
}
\\

describing the motion of the solid, the resulting swept volume can be defin=
ed as=20
follows:\\

{\noindent
$\{m((x_0,y_0,z_0),t)| t \in \tau \wedge f(x_0,y_0,z_0) \le 0\}$=20
\hspace*{7mm}(3)
}
\\

Assume that, for each $t \in \tau$ fixed, an inverse transformation w=20

{\noindent
$( w((x,y,z),t) : w( m((x_0,y_0,z_0),t),t) =3D (x_0,y_0,z_0))$=20
}
{\noindent
exists. This implies=20
that any point $(x,y,z)$ in $R^3$ can be classified w.r.t. the swept volume=
 using=20
the following defintion:\\
}

{\noindent
$f(x_0,y_0,z_0), (x_0,y_0,z_0) \in \{ w((x,y,z),t) | t \in \tau\} $=20
\hspace*{0.2cm}(4)
}
\\
{\indent
The result of this classification can be either {\it in}=20
$(\exists (x_0,y_0,z_0):f<0)$, {\it on}=20
$(\exists (x_0,y_0,z_0):f=3D0 \wedge f \ge 0\ \forall (x_0,y_0,z_0))$ or {\=
it out}=20
$(f>0\ \forall (x_0,y_0,z_0))$ .
}


\section{Rendering Swept Volumes}

Rendering algorithms approximate objects and scenes so that they can be dis=
played=20
on raster graphics display devices. In particular, a rendering algorithm co=
mputes=20
color and other information (e.g. depth values, etc.) for every pixel of th=
e screen
or image, thus generating a shaded image of the object. Unfortunately, a co=
mputer=20
algorithm which renders a swept volume cannot apply definition 4 directly b=
ecause=20
an infinite number of points would have to be classified for every pixel in=
 the=20
image.

Interval arithmetic methods \cite{Snyder 1992,Moore 1966} extend the scope =
of=20
implict forms from point checking to range checking \cite{Duff 1992}. This =
allows=20
the development of efficient algorithms which navigate along the envelope s=
urface.
Following definition 4, the classification of a box :

{\noindent
$X=3D[x_A,x_B]$

\noindent
$Y=3D[y_A,y_B]$

\noindent
$Z=3D[z_A,z_B]$
}

{\noindent
which includes part of the envelope surface is defined as:\\
}

{\noindent
$0 \in [f([w((X,Y,Z),\tau)])]$ \hspace*{3.5cm}(5)
}
\\

Using intervals for geometric queries allows the classification of regions =
and=20
thus can be used in simple divide and conquer algorithms.

Our algorithm belongs to the category of ray casting algorithms \cite{Foley=
 1990b}
and consists of two phases. In the first phase, a ray, which is perpendicul=
ar to=20
the view plane, is cast through every pixel in the image and the entry poin=
t of=20
each ray (i.e., the Z value of the first entry into the object) is calculat=
ed.

In the second phase, pixel color intensity is determined by calculating sur=
face=20
gradient values. This can be easily performed by fitting an algebraic surfa=
ce=20
(typically linear) through neighbouring points \cite{Foley 1990a}. In the r=
emainder
of this paper we will concentrate on the calculation of depth values given =
an=20
implicit representation.=20

For a given view, we cast a ray through any discrete point (i.e., pixel) of=
 the=20
image (see Fig. 2). The ray is perpendicular to the view plane and bounded =
by=20
preset start and end values. Transforming the ray from view space to world=
=20
coordinates results in a rectilinear region of the world space, which is us=
ed for=20
classification w.r.t. the generating object using definition 5.

\centerline{\psfig{file=3Df2.ps,angle=3D270}}

{\centerline{\noindent\small Figure 2: Scan converting a swept volume}}

\medskip

If the result of the classification of the ray is {\it in} or {\it out} we =
discard=20
the ray because it doesn't cross the envelope surface. Otherwise, the ray i=
s=20
divided and the results of this division are classified. This process of=20
classifying and dividing is continued until the length of the ray is suffic=
iently=20
small.

Since we are looking for the minimum depth value, the front part (i.e., the=
 part=20
closer to the observer) of the division is examined first. If we detect the=
=20
envelope surface to cross this part, the process is continued immediately  =
(i.e,=20
the second part of the current ray is discarded). Otherwise, the second par=
t is=20
examined.=20

Classifying a region of Euclidean 3D space against a swept volume is not a =
trivial=20
task. The straightforward solution would be the direct application of defin=
ition 5=20
(i.e., to inverse transform the region for $\tau$ and use the result for=20
classification w.r.t. the generator).

The problem of this approach is that the inverse transformation generates a=
=20
parallelpiped which is likely to extend into the generating object. Figure =
3 shows=20
a case where the classification of a region, located completely outside of =
the=20
swept volume, results in {\it on} because the inverse transformation for $\=
tau$=20
generates a region which extends into the generating object.

\centerline{\psfig{file=3Df3.ps,angle=3D270}}

{\centerline{\noindent\small Figure 3: Inverse transformation of a region}}

\medskip

Our approach to overcome this problem and achieve reliable classifications =
is=20
structured as follows:

\newcounter{l1}
\begin{list}{\arabic{l1}.}{\usecounter{l1}}
\item Determine if the moving object enters the region to be classified dur=
ing the=20
time interval.
\item Determine if there exists a point in time where the moving object cov=
ers the=20
region completely.
\end{list}

If the result of the first query is no, the examined region is completely o=
utside=20
of the swept volume. Otherwise the second question must be answered. If the=
=20
solution is no, the region is only partially covered by the swept volume, t=
hus=20
containing part of the envelope surface. If the solution of the second quer=
y is=20
yes, the region is completely inside the swept volume.

To answer these questions, we have to prove the existence of certain critic=
al=20
points in time. We define these critical points as follows (see also Fig. 4=
):

\newcounter{l2}
\begin{list}{\arabic{l2}.}{\usecounter{l2}}
\item $t_1$ ... generator enters region.
\item $t_2$ ... generator covers region completely for the first time.
\item $t_3$ ... generator covers region completely for the last time.
\item $t_4$ ... generator leaves region.
\end{list}

The algorithm for proving the existence of $t_1$ (and $t_4$ as well) is sim=
ple:

\newcounter{l3}
\begin{list}{\arabic{l3}.}{\usecounter{l3}}
\item Inverse transform the region for $\tau$ and classify the result w.r.t=
. the=20
generator.
\item If the result of the classification is {\it on}, subdivide in t and r=
epeat=20
steps 1, 2 and 3 by substituting the result of the subdivision for $\tau$ o=
r, if=20
the time interval grew sufficiently small, terminate and take the lower bou=
nd=20
(or in case of searching for $t_4$ the upper bound) of the interval as the =
solution.
\item If the result is {\it in}, the lower bound (or the upper bound in cas=
e of=20
searching for $t_4$) of the time interval is the solution.
\end{list}

\centerline{\psfig{file=3Df4.ps,angle=3D270}}

{\centerline{\noindent\small Figure 4: Critical points for classification}}

\medskip

In case of searching for $t_1$, intervals earlier in time must be checked f=
irst.=20
If the search is for $t_4$, the strategy has to be reversed.

Finding $t_2$ and $t_3$ is done by identifying either a subregion of the re=
gion=20
to be classified which is not covered in $\tau$ or a subinterval of $\tau$ =
where=20
the region is completely covered. If we find a subregion then the region is=
=20
partially covered by the swept volume. In case of identifying a subinterval=
 of=20
$\tau$ then the region is completely covered by the swept volume.

\section{Conclusion}

Due to the increasing usage of computer based manufacturing technology in t=
he shop=20
floor as well as in the design department, simulation of manufacturing proc=
esses=20
will become more important because it increases reliability and saves expen=
sive=20
machine time. Complete simulation (i.e., a simulation able to represent and=
 process
all important parameters) of these processes is still an unsolved problem b=
ecause=20
the technology in use today is based on simplifying assumptions (e.g. restr=
ictions=20
regarding tool shapes).

We have presented a general, time efficient solution to a basic requirement=
 of=20
such a simulation system. Although rendering swept volumes is not sufficien=
t for=20
performing Boolean set operations on solids, the extension of the algorithm=
 to=20
find all entry and exit points of the ray is relatively easy.

The ideas presented in this paper are currently being implemented as part o=
f a=20
system which allows the verification of complex NC programs. We based this =
system=20
on object oriented methods using C++ as our implementation language of choi=
ce.

\begin{thebibliography}{99}

\bibitem{M=E4ntyl=E4 1988}
M. M\"antyl\"a, {\bf An Introduction to Solid Modeling}, Computer Sience Pr=
ess,=20
Rockville, MA, 1988.

\bibitem{Wang 1986}
W. P. Wang, K. K. Wang, ``Geometric Modeling for Swept Volume of Moving Sol=
ids'',=20
{\it IEEE Computer Graphics and Applications}, December 1986, pp. 8-17.

\bibitem{Menon 1994}
J. Menon, R. J. Marisa, J. Zagajac, ``More Powerful Solid Modeling through =
Ray=20
Representations'', {\it IEEE Computer Graphics and Applications}, May 1994,=
 pp. 22-35.
\bibitem{Snyder 1992}
J. M. Snyder, {\bf Generative Modeling for Computer Graphics and CAD}, Acad=
emic=20
Press, San Diego, CA, 1992.

\bibitem{vanHook 1986}
T. van Hook, ``Real-Time Shaded NC Milling Display'', {\it Proceedings of S=
IGGRAPH
'86}, volume 20, number 4, August, 1986, pp. 15-20.

\bibitem{Duff 1992}
T. Duff, ``Interval Arithmetic and Recursive Subdivision for Implicit Funct=
ions and
Constructive Solid Geometry'', {\it Computer Graphics}, July 1992, pp. 131-=
137.

\bibitem{Foley 1990a}
J. D. Foley, A. van Damm, S. K. Feiner, J. F. Hughes, {\bf Computer Graphic=
s},=20
2nd ed., Addison-Wesley, Reading, MA, 1990, pp. 471 ff.

\bibitem{Foley 1990b}
J. D. Foley, A. van Damm, S. K. Feiner, J. F. Hughes, {\bf Computer Graphic=
s},=20
2nd ed., Addison-Wesley, Reading, MA, 1990, pp. 701 ff.

\bibitem{Moore 1966}
R. E. Moore, {\bf Interval Analysis}, Prentice Hall, Englewood Cliffs, NJ, =
1966.


\end{thebibliography}

\end{document}

