Vectorize a triangle scan line in MATLAB/Octave

Question

I am new to Octave/MATLAB. I want to vectorize a simple scan-line fill for a triangle. Here is the while loop I want to eliminate:

 #Iterate over all the scan lines from bottom to top
 while(yCurr <= 200)

    #VARIABLES: 
    #  img - Zero matrix used as an image. Zero is black. Assume 320x200 pixels.
    #  leftIdx - Vector that contains the left-most pixel to fill in each
    #      scanline. Dim is 1x200. Each element represents x-coord of a pixel.
    #  rightIdx - Vector that contains the right-most pixel to fill in each
    #      scanline. Dim is also 1x200. Each element represents x-coord of a pixel.
    #  yCurr - The current row being scanned.    

    #Fill all the pixels in one scan line 
    img(leftIdx(yCurr) : rightIdx(yCurr), yCurr) = color;

    #Increment the row
    yCurr++;

 endwhile

Answer 1

Simple solution - you can change your loop directly to one arrayfun call. arrayfun is a fancy way of writing a loop - it calls user-defined function for all supplied parameters. The caveat is that anonymous functions that one usually uses with arrayfun can not assign variables. But, you can write a normal function that assigns color to img and pass it to arrayfun as parameter:

 function doAllWork(img, rightIdx, leftIdx)

 arrayfun(@fill, 1:size(img, 1));

    function fill(i)
      img(leftIdx(i):rightIdx(i), i) = color;
    end
 end

I have defined the fill function as a local function in doAllWork so that it has access to img, leftIdx, rightIdx.

Complicated solution Usually in such cases, to do an assignment in one go you want to use sub2ind to get a linear index into the matrix (in short, in C you would write sth. like j*nx+i). You then write img(ind) instead of img(indrow, indcol). The problem is that every row has a different number of non-zeros in different places.

The (complicated) idea is to create an explicit column index array Ii{row} = [leftIdx(row):rightIdx(row)] and corresponding row index array Ij{row} = [row*ones(1, lenght(Ii{row}))] for all rows. Without a loop that can be done using arrayfun. Once you have this, you can construct a linear index into your img using sub2ind on coresponding Ii/Ij entries, also called using arrayfun. The code looks like this

nrows=1:size(img, 1);
Ii=arrayfun(@(i)(leftIdx(i):rightIdx(i)), nrows, 'UniformOutput', false);
Ij=arrayfun(@(i)(i*ones(1,length(Ii{i}))), nrows, 'UniformOutput', false);
lin=arrayfun(@(i)(sub2ind(size(A), Ij{i}, Ii{i})), nrows, 'UniformOutput', false);
img([lin{:}])=color;

This approach is not of much use in your case - it is way too complicated. But it is instructive in what arrayfun can do, and the trick with sub2ind is generally very useful.

Answer 2

Although not the OPs main question (i.e. how to vectorize the raster scan), a clean looking solution in MATLAB for filling in values in a triangle can come from using poly2mask to specify the area inside the triangle, using the triangle vertices, and use logical indexing to assign values.

% Example values
yCurr = 1:200;
img = zeros(320, 200);
leftIdx = ones(1,200);
rightIdx = 1:200;
color = 1;

% Define polygon vertices and get mask
x = [leftIdx(1) leftIdx(200) rightIdx(1) rightIdx(200)];
y = [1 1 200 200];
bw = poly2mask(x,y,320,200);
% Assign color values
img(bw) = color; 

Since poly2mask most probably uses some underlying for, it is not a vectorized version of a rasterizing scan. However, it offers the benefit of handling more complex polygonal areas.

Answer 3

I think that your original loop-based solution is the best solution. Why?

1. Because until you haven't done profiling you cannot know whether a vectorized solution is actually faster.
2. Because your code that uses for loop is clear for the reader! It contains only 4 lines of code and one can understand its purpose merely by taking a look.

The only thing that I would change is while->for

for yCurr = 1:200
    img(leftIdx(yCurr) : rightIdx(yCurr), yCurr) = color;
 end