AcademySoftwareFoundation / AcademySoftwareFoundation/OpenImageIO

[INVESTIGATION] ImageBuffer iterators based on Space Filling Curves

Open
#4,554 8 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.4k
Forks
698
Avg merge
3d 4h
Merged PRs (30d)
47

Description

Recently I've been looking into space filling curves, in particular the Morton curve (see https://en.wikipedia.org/wiki/Z-order_curve) and the Hilbert curve (see https://en.wikipedia.org/wiki/Hilbert_curve). I've read that these curves can be used to iterate through the pixels of an image in a "cache-friendly" way as they preserve spatial locality fairly well, and thus could improve the performances of some image processing algorithms.

I've started doing some investigation work, however the results I got so far do not suggest any performance improvements when using the Morton curve to iterate: I'm applying a simple convolution with a Gaussian kernel on a 4096x4096 image (on a single thread), and iterating with `ImageBuffer::Iterator` vs with my custom Morton curve implementation both take on average the exact same time.

If someone has some knowledge around space filling curves, performance engineering, or simply wants to continue the investigation on their side and provide more insight on this, your help is definitely welcome!

Here is the code I wrote for this initial investigation:
```
#include
#include
#include

#include
#include
#include
#include

using namespace OIIO;

void process_ref(ImageBuf & dst, const ImageBuf & src, const ImageBuf & kernel)
{
ROI roi = src.roi();
ROI kroi = kernel.roi();

ImageBuf::Iterator dstit(dst);
ImageBuf::ConstIterator srcit(src);

for (; !dstit.done(); ++dstit) {
float sum = 0.f;

const float* k = (const float*)kernel.localpixels();
srcit.rerange(dstit.x() + kroi.xbegin, dstit.x() + kroi.xend,
dstit.y() + kroi.ybegin, dstit.y() + kroi.yend,
0 , 1 ,
ImageBuf::WrapClamp);
for (; !srcit.done(); ++srcit, k += 1) {
sum += k[0] * srcit[0];
}

dstit[0] = sum;
}
}

void process_morton(ImageBuf & dst, const ImageBuf & src, const ImageBuf & kernel, int nbits)
{
float* pixels = static_cast(dst.localpixels());

const ImageSpec & spec = dst.spec();
const uint64_t nmax = (1 << (2 * nbits));

ROI roi = src.roi();
ROI kroi = kernel.roi();

ImageBuf::ConstIterator srcit(src);

for (uint64_t i = 0; i < nmax; ++i) {
uint32_t xmorton = 0;
uint32_t ymorton = 0;
for (int j = 0; j < nbits; ++j) {
xmorton |= (i & (1 << (2 * j))) >> j;
ymorton |= (i & (1 << (2 * j + 1))) >> (j + 1);
}

float sum = 0.f;

const float* k = (const float*)kernel.localpixels();
srcit.rerange(xmorton + kroi.xbegin, xmorton + kroi.xend,
ymorton + kroi.ybegin, ymorton + kroi.yend,
0 , 1 ,
ImageBuf::WrapClamp);
for (; !srcit.done(); ++srcit, k += 1) {
sum += k[0] * srcit[0];
}

pixels[ymorton * spec.width + xmorton] = sum;
}
}

int main(int argc, char *argv[])
{
// Command-line arguments
const std::string mode = argv[1];
const int nbits = std::stoi(argv[2]);
const float kernel_size = std::stof(argv[3]);
const std::string filename = argv[4];

// Specs for image buffer
// We only use dimensions that are powers of 2,
// with an exponent specified by the user
const int xres = (1 << nbits);
const int yres = (1 << nbits);
const int nchannels = 1;
ImageSpec spec(xres, yres, nchannels, TypeDesc::FLOAT);

// Destination buffer
ImageBuf dst(spec);

// Source buffer
// Use a simple checker
ImageBuf src(spec);
float dark[3] = { 0.1, 0.1, 0.1 };
float light[3] = { 0.4, 0.4, 0.4 };
ImageBufAlgo::checker(src, 64, 64, 1, cspan(dark), cspan(light));

// Kernel buffer
// Use a normalized Gaussian kernel
ImageBuf kernel = ImageBufAlgo::make_kernel("gaussian", kernel_size, kernel_size);

// Apply convolution to compute the final image
// Measure elapsed time to compare iterator-based approach
// and Morton-curve-based approach
auto t_start = std::chrono::high_resolution_clock::now();
if (mode == "ref") process_ref(dst, src, kernel);
else if (mode == "morton") process_morton(dst, src, kernel, nbits);
auto t_end = std::chrono::high_resolution_clock::now();
std::cout << "Elapsed time: "
<< std::chrono::duration_cast(t_end - t_start).count()
<< " microseconds" << std::endl;

// Store final image on disk
auto out = ImageOutput::create(filename);
out->open(filename, spec);
dst.write(out.get());
out->close();

return EXIT_SUCCESS;
}
```

Contributor guide

Open the contributing guide

Research direction

Start by compiling and running the standalone C++ investigation, comparing process_ref with process_morton on the stated image and convolution sizes. Read the ImageBuf::Iterator and ImageBuf::ConstIterator usage shown in the example, then determine whether Morton or Hilbert traversal provides a measurable benefit. Done is not defined by the issue; results should establish performance evidence and a concrete implementation direction.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
computer-graphics, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.