Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2001-03-30 11:15:54

On Thu, 29 Mar 2001, Ullrich Koethe wrote:
koethe> Indexing:
koethe> ---------
koethe> Most proposals I've seen so far are using integers for indexing.
koethe> However, in higher dimensions this causes all kinds of trouble - Shall
koethe> we use (i,j,k) or [i][j][k]? Is the horizontal index first or last? Is
koethe> the first index 0 or 1? Therefore, I've found *index objects* a very
koethe> powerful alternative. For example:
koethe> Index2D start = matrix.upperLeft(),
koethe> end = matrix.lowerRight().
koethe> i;
koethe> for(i.y = start.y; i.y < end.y; ++i.y)
koethe> {
koethe> for(i.x = start.x; i.x < end.x; ++i.x)
koethe> {
koethe> matrix[i] = 42;
koethe> }
koethe> }

Actually, the multi_array spec included an elt() function which takes the
equivalent of one of these index objects. There are two small differences:

  - the index object is just sequence of indices (not data members
     x and y)
  - the elt() function took an iterator to the beginning of the sequence.

So, your example above would have looked like this:

for (i[0] = start[0]; i[0] < end[0]; ++i[0])
  for (i[1] = start[1]; i[1] < end[1]; ++i[1])

I think you'll agree that the "x" and "y" are very must image specific,
and it would be better to go with a sequence of indices.

So what's left to debate:
  - the name of the function. I'm not all that crazy about elt().
    My current favorate is operator() because it is not operator[]
    (which people are use to using with a single integer) and
    because it is shorter.

  - how to pass the index object.
    1) As an iterator (more flexible)
    2) As an container (nicer syntax)

    1) is what we've currently got in the spec, but I actually
      like 2) better.

    Either way, it be cool to make the element access funtion
    templated, so people could make their own index objects.

koethe> Iterators:
koethe> ----------
koethe> A property of images is that all coordinate directions are 'equal'.
koethe> Therefore, a design like the following, where one direction is the
koethe> 'outer' direction, and the other the 'inner', is very artificial:
koethe> JeremySiek> 1. Use two iterators, the "outer iterator" iterates over
koethe> rows
koethe> JeremySiek> of the image, and the "inner iterator" iterates down each
koethe> row.
koethe> JeremySiek>
koethe> JeremySiek> PixelRowIterator row_iter = rows_begin(myPix);
koethe> JeremySiek> for (; row_iter != rows_end(myPix); ++row_iter) {
koethe> JeremySiek> PixelIterator iter = begin(*row_iter);
koethe> JeremySiek> for (; iter != end(*row_iter); ++iter)
koethe> JeremySiek> ...
koethe> JeremySiek> }
koethe> In VIGRA, I'm preferring a different iterator concept that doesn't have
koethe> this asymmetry (expet for cache performance):
koethe> ImageIterator start = image.upperLeft(),
koethe> end = image.lowerRight(),
koethe> i;
koethe> for(i.y = start.y; i.y < end.y; ++i.y)
koethe> {
koethe> for(i.x = start.x; i.x < end.x; ++i.x)
koethe> {
koethe> *i = 42;
koethe> }
koethe> }

This isn't really a conceptual difference, just a difference in packaging.
It's interesting, but it produces iterators that are not std conformant.
If I see iterators, I want to be able to use them with std::copy(), etc.
Also, there might be some performance advantage in the "hierarchical"
approach because the index*extent multiplications can be moved to outer
loops, effectivly performing what compiler guys call strength reduction.
With the above iterators, you might as well just use the index objects

koethe> Different views on the pixel data:
koethe> ----------------------------------
koethe> This has proven more important than I expected. Consider, for example,
koethe> an image that contains complex numbers (e.g. the Fourier transform of an
koethe> image). Now, the magnitude of a complex number is a scalar that can be
koethe> used in any algorithm that requires a scalar image (for example, image
koethe> display). By using *data accessors* to create a magnitude view, I can
koethe> calculate the magnitude on the fly, without creating an extra magnitude
koethe> image.
koethe> displayImage(complex_image, MagnitudeAccessor());

Yes, this is a very important capability.


 Jeremy Siek www:
 Ph.D. Candidate email: jsiek_at_[hidden]
 Univ. of Notre Dame work phone: (219) 631-3906

Boost list run by bdawes at, gregod at, cpdaniel at, john at