NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/virtual/4559

Internet Message Format | 1993-01-24 | 10.8 KB

Path: sparky!uunet!zaphod.mps.ohio-state.edu!uwm.edu!ogicse!news.u.washington.edu!stein.u.washington.edu!hlab
From: [e-mail] (John Costella)
Newsgroups: sci.virtual-worlds
Subject: TECH: Test drivers sought for a C++ object
Message-ID: <[e-mail]>
Date: 23 Jan 93 02:33:56 GMT
Article-I.D.: shelley.1jvoupINNmdr
Organization: University of Washington
Lines: 248
Approved: [e-mail]
NNTP-Posting-Host: stein.u.washington.edu
Originator: [e-mail]


We have a C++ object that needs to be `test driven' on a variety of
platforms, and criticised wherever it either doesn't work or is
deemed unnecessarily inflexible.

The class essentially allows ``multi-dimensional arrays'' of arbitrary
objects to be dynamically allocated and manipulated with standard
[i][j][k][l]  type of notation, where there are no restrictions on the
dynamical specification of any of the indices, and any special memory
handling routines (which can be completely arbitrary, and indeed can
be different for each index of the ``array'') are encapsulated into
classes derived from this base class.

If you are a C++ programmer, whether a CS undergrad or experienced
veteran, and would like to give the above class a test drive, please
send an e-mail to    [e-mail]   .
The class can be used `as is' for the supplied example derived classes
for bytes and bits, or classes can be derived for your own needs.
Further technical details for those interested are given below. The
class is freely usable for any purpose, and should run with any flavour
of C++. Preliminary documentation will be available.

John Costella
The University of Melbourne

----------------------------------------------------------------------------
John P. Costella              School of Physics, The University of Melbourne
[e-mail]         Tel: [phone], Fax: [phone]
----------------------------------------------------------------------------


More details about the above class
==================================
(NOTE: Most of the following discussion applies to C without need
for any knowledge of C++.)

The class focusses on the somewhat primitive treatment that plain
C and C++ has for handling ``tensors'' of arbitrary objects.
By a ``tensor'' we mean what would be called in BASIC a ``multi-
dimensional array'' (we are borrowing the mathematical term
``tensor'' as a good fit, which has a descriptive language ready-
made for us).

The ``rank'' of a tensor of objects is essentially the number of
subscripts that are required to specify a single object. A rank 0
tensor is a ``scalar'', a rank 1 tensor is a ``vector'', a rank 2
tensor is a ``matrix'', a rank 3 tensor is like a 3-dimensional
rectangular prism of voxels, and so on.

A scalar of the object Object     =>   Object scalar
A vector of objects Object        =>   Object vector[ i ]
A matrix of objects Object        =>   Object matrix[ i ][ j ]
A rank 3 tensor of objects Object =>   Object rank_3[ i ][ j ][ k ]

...and so on.

The problem is that vanilla C++ is really only geared up to handle
scalars and vectors of objects dynamically (and even the handling
of vectors keeps changing as C++ shakes down). You can write

  int* scalar = new int;
  *scalar = 7;
  delete scalar;

  int* vector = new int[ num ];
  vector[ 3 ] = 12;
  delete [] vector;

(for C, substitute `malloc' and `free' for the `new' and `delete'
operators; for older versions of C++, read:

  delete [ num ] vector;

for the deletion of a vector), but you can't write

  int* matrix = new int[ numx ][ numy ];   // WRONG

or

  int** matrix = new int[ numx ][ numy ];  // ALSO WRONG

There are two standard ways to get around this problem. One is to
essentially lay all the ``rows'' of the matrix end-to-end and
allocate a single large vector:

  int* matrixfudge = new int[ numx * numy ];

But then you need to perform a multiplication to access every
element:

  i = matrixfudge[ y * numx + x ];   // Fudge for matrix[ y ][ x ]

and so not only is the syntactical cleanliness lost, you are also
invoking multiplications just to access an element. In general, for a
rank r tensor, you need to perform (r-1) obscure, processor-consuming
and error-prone multiplications. Consider, as an example, a rank 4
tensor:

  temp1 = numw;
  temp2 = numx * temp1;
  temp3 = numy * temp2;

  int* rankfour = new int[ numz * temp3 ];

  // Fudge for i = rankfour[ z ][ y ][ x ][ w ] follows:
  i = rankfour[ z * temp3 + y * temp2 + x * temp1 + w ];

This approach also requires that the whole memory for the tensor
be allocated in one huge contiguous chunk, which might not be
either possible or desirable.

The other standard workaround (* see footnote), which avoids the
obscurity, the performance penalty and the contiguity problems of
the above, at the small expense of a smaller number of extra pointers,
is to allocate a vector of pointers, each pointing to another vector
of pointers, each pointing to another vector of pointers, ..., and so
on until we finally have each of the last vector of pointers pointing
to a vector of objects. For example, a matrix of integers is
implemented via the code

  int** matrix = new int*[ numy ];

  for( int y = 0; y < numy; y++ )
    matrix[ y ] = new int[ numx ];

Now we can validly use clean syntax:

  i = matrix[ y ][ x ]; // Now OK

There are no multiplications needed to access an element, only
an additional pointer dereference per rank. And best of all, the
memory is allocated as (numy) separate rows, each of length (numx)
integers, rather than a single block of (numy*numx) integers.
The only size penalty is the vector of pointers, which is in
general insignificant compared to the matrix as a whole.

This second workaround is clearly the better of the two, but
it suffers from lack of code re-use. To implement a matrix of
doubles, or a matrix of Windows, or a matrix of any other arbitrary
object that we haven't even invented yet, we have to rewrite the
above code replacing `int' by `double' or `Win' or whatever. (* see
footnote for details) To then go to rank 3 objects we would have to
write another swag of routines to create a vector of matrices, and
again for rank 4, and so on. And then each of this large population
of routines would need to be modified if we needed a different
memory handling---say, __far or __huge pointers for 16-bit PC apps.
We'd end up with hundreds of different specialised routines just to
handle a handful of objects with a handful of ranks and a few memory
models.

Clearly, the desired solution is to create a generic Tensor class
that will automatically recurse down into itself to allocate and
free all the pointers needed for an arbitrary-rank tensor. But it
is slightly complicated because the Tensor class doesn't know what
sort of object it is that we want a tensor of (if we want to be
able to use it for any arbitrary objects), it doesn't know how
to allocate memory (if we want that to be changeable) and it
doesn't even know how large the pointers are that point to either
the objects or even its own subtensors (if we need to use
different types of pointers). In addition, virtual functions are
*disabled* within constructors (because the derived classes don't
exist at that point) so we can't use polymorphism to help us out.

Nevertheless, it is not impossible to write a Tensor class that
does this job. The tensors only recurse down to the vector level
(not the scalar level) to ensure that the tensor structure does not
take up more memory than the objects it houses. There is still a thin
layer of wrapping that needs to be performed at the vector level,
once for each memory model, and once for each different type of
object that needs to be tensorised. However, once this is done,
the job is complete. For example, if a BitTensor class wrapping is
written (a page or two of code), then one can create bitmaps via
the code

{
  unsigned int rank = 2;  // dynamically specify rank
  unsigned long dimensions[ rank ] = { numx, numy };  // dynamically
                                                      // specify dims

  BitTensor bitmap( rank, dimensions );  // create the tensor: actually
                                         // dynamically allocated

  bitmap[ 34 ][ 47 ] = 1;  // access a bit entry in the bitmap

  BitTensor bitmap2( bitmap );  // create a new tensor which is a
                                // copy of the first
}
// bitmaps are dynamically freed at end of scope

There is not even any need to delete the bitmaps when finished: the
objects `bitmap' and `bitmap2' are automatic variables (of size only
a few bytes) which contains pointers to its subtensors, and so on;
when the variables `bitmap' and `bitmap2' go out of scope, their
destructors automatically clean away the tensors.

Now imagine that you wanted to create simple 1-bit-deep voxmaps
to represent three-dimensional volumes (say, for spatial-occupancy
enumeration). But say that you need some number N of these voxmaps,
one for the volume surrounding each of the N participants in your
virtual world. Without writing a single extra line of code, you can
simply say

  unsigned int rank = 4;
  unsigned long dimensions[ rank ] = { N, sizex, sizey, sizez };

  BitTensor vector_of_voxmaps( rank, dimensions );

  // set the voxel ( 445, 28, 112 ) for the third participant.
  vector_of_voxmaps[ 3 ][ 445 ][ 28 ][ 112 ] = 1;

  // out-of-bounds automatically trapped and avoided for the following
  vector_of_voxmaps[ N + 18 ][ 0 ][ 0 ][ 0 ] = 0;

By instead using a derived class which allows arbitrary floating
point values as indices to the closest voxel, a test for occupancy
could then be written

  if( vector_of_voxmaps[ 3 ][ -4.77 ][ 12.3 ][ 196.65 ] )
    ; // do something meaningful

which is about as clean a syntax as one could ask for.

. . .

The tensor class described above is the one that requires test
drivers. It should be emphasised that the class is designed
for high performance and low overheads: using it for a tensor
structure of any type of object is at least as fast as any
other method, and the memory overheads are negligible.

If you would like a copy of class (supplied via source code in
plain ASCII), please follow the intructions at the start of this
post.

John Costella

---------------------------------------------------------------------
*Footnote: The `pointer to vector of pointers to vectors of pointers
to vectors of ...' trick is described in detail in

  W. H. Press, B. P. Flannery, S. A. Teukolsky and W. T. Vetterling,
  _Numerical_Recipes_In_C_ (Cambridge University Press, Cambridge,
  1988), section 1.2, `Some C Conventions for Scientific Computing'.

The explosion in code needed to even service a handful of C built-in
types using this method, without the benefit of a Tensor class, is
exemplified by their library of utilities in Appendix D.
---------------------------------------------------------------------