Quaternary Logic
The idea is that cube<=object relation is answerable as Y/N/O for
primitive objects, but for non-primitive the answer may not be
immediately obtainable (e.g, for object composed using intersection),
in which case we can subdivide cube and try again. For non-primitives
the answer to cube<=object proceeds by recursive structural expansion
of CSG expression, using <= test on subcomponents whose results (with
values of Y/N/O/M) are combined using logic operators AND, OR, and NOT
conservatively extended for quaternary values.
Tables: (think of as: is cube<=A^B?, etc.)
M ^ Y = M
M ^ N = N
M ^ M = M
M v Y = Y
M v N = M
M v M = M
! M = M (chosen so that !(cube<=B) iff cube*B=empty)
! O = N
! Y = N
! N = Y
O ^ Y = M
O ^ N = N
O ^ M = M
O ^ O = M
O v Y = Y
O v N = M
O v M = M
O v O = O
Geometric Algorithm
The algorithms include the checking of relationships of cube with
sphere, halfspace, infinite cylinder and finite cylinder. We have
designed several algorithms especially for the checking of a cylinder
with a cube, ranging from very accurate and slow to very fast but not
accurate.
Implementation
The current implementation includes three module : interface, main and
geometric algorithms.
Interface
The interface takes the input and transform it input the format
which can be dealt by our geometric algorithms. It includes the
complete transformation sub-module from longitude/latitude
representation to Cartesian coordination system which is orthogonal to
the clipping_region. A flow is shown below,
(lat, long) ... on surface of the earth
|
|
spherical coordinate (w/ origin at the center of the earth)
|
|
Cartesian coordinate (including rotation and transformation of
the coordinate system to the center of the
clipping_region and orthogonal to that
plane)
It also transforms the cylinder as the intersection of infinite
cylinder with two spheres, and the polygon to the intersection of a
series halfspaces with two spheres.
Main
This is the main control module. It calls the interface to make the
format transformation and calls the geometric module to calculate the
volume. It also includes the oct-tree decomposition algorithms and
output generation functions. The general flow is shown below,
Call interface
For radar, doctrine and (radar^doctrine) do
Initialize pixmap to 0.
Push initial cube (bbox of doctrine) on stack.
While stack not empty:
pop cube from stack.
cube <= object? ... call geometric module
if no => continue
if maybe || overlap =>
subdivide cube (if >= threshhold)
push subdivisions on stack
if yes => drop cube onto pixmap
(i.e., pixmap[i,j] += cube_radius for i,j in cube bottom)
Generate the output
Geometric Module
Besides the implementation of the geometric checking algorithms, it
also includes the functions for quaternary logic.
Discussion
Pros and Cons of oct-tree approach
The objects defined in our geometric algorithms are quite general
and can deal with most of the random shapes and rotated 3D objects. The
oct-tree representation is easy to adapt to the data parallel
execution and presumably it can need more accurate result and
efficient execution. Another interesting of this prototyping exercise is
that we developed the quartenary logic to fully handle the logic
operations in CSG expressions and the coordinate system transformation
itself could be a useful sub-module for other experiment.
However, the generality also leads the inefficiency for this
particular problem (look at out ray-tracing approach). There is quite
a bit of transformation and adjustments to be made to the original
input, obscurring the beauty of our original design. Well, part of the
argument for this is that we did not know what is the input and output
was going to be when we began development. The productive result from
this is that our prototyping system is quite flexible which can
relatively easy to adapt itself to the changed requirements,
demonstrated here by the changing geometric primitives.
Development time and effort metrics
The time I spent is divided into following five parts (unit : hours),
Discussion : 16
Reading and Literature Searching : 21
Algorithm Design : 48
Coding : 22
Debug : 33
Total : 140
Warning: this is really vague statistic especially there are lots of time
when the problem was hanging in our mind which is hard to count.