Fix the bugs in SetSegmentation, both the original and new

[sts1skj]

The original (written by me) had two bugs. One would make the code segfault if a partition number in inTriParts was negative; it was probably never triggered. The main bug would cause all triangle segment assignments to be lost if there was an empty partition at the end of the list.

Two commits were added to this code over the past two years to try to fix the empty-partition-at-end bug and additional bugs introduced in those commits: eae5755 and bb1f7a6. Neither fixed the original bug, and each had problems: the resulting code would tend to reassign triangles in some circumstances. So I reverted both of those commits and fixed the original bug.

The mistakes in the two bug-fix commits suggest that the original code was unclear. I've tried to make it more clear by adding comments, renaming variables, and deleting blank lines that made closely related code seem unrelated.

[ousnius]

@sts1skj Can you confirm all the test cases listed in #20 are working with these changes?

[sts1skj]

I think so. There doesn't seem to be much to test in those test cases. Here's what I did just now:

• Deleted all but one segment, saved, and reloaded.
• One empty segment before one used segment, hit apply.
• One used segment followed by one empty segment, hit apply.
• Empty, used, empty, used, hit apply.

Also, in my earlier testing, I did lots of random changes, saved them, and reloaded them.

I believe I understand this code thoroughly. I believe I know exactly why it misbehaved with empty segments at the end of the list in the original version, and why it would sometimes reassign partitions in the newer versions. However, additional code review and discussion seems like it could be valuable, given the problems with this function in the past.

Do you want me to try to explain exactly what was wrong with the original code and why it did what it did? And why the two commits that tried to fix it didn't completely fix it?

[ousnius]

@sts1skj Thanks for the tests.

Yes, a short and concise explanation of what the new partTriInds loop does correctly and the original code or fixes for it did not would be appreciated before I merge. No need to go too much into detail though.

[sts1skj]

Here's the buggy code that I wrote originally (updated with new variable names and types):

std::vector<uint32_t> partTriInds(newPartID + 1);
int nextPartID = 0;
for (uint32_t i = 0; i < numTris; ++i)
    while (triParts[triInds[i]] >= nextPartID)
        partTriInds[nextPartID++] = i;
partTriInds.back() = numTris;

Suppose we have 3 partitions with 100, 200, and 300 triangles. Then the input to this code is:

triParts[triInds[0]] = 0
triParts[triInds[1]] = 0
...
triParts[triInds[99]] = 0
triParts[triInds[100]] = 1
...
triParts[triInds[299]] = 1
triParts[triInds[300]] = 2
...
triParts[triInds[599]] = 2

After the code, partTriInds will look like this:

partTriInds[0] = 0
partTriInds[1] = 100
partTriInds[2] = 300
partTriInds[3] = 600

This says, concisely: partition 0 starts at triangle index 0 and has 100 triangles; partition 1 starts at triangle index 100 and has 200 triangles; and partition 2 starts at triangle index 300 and has 300 triangles.

Now suppose, instead of 3 partitions, we have 6: the first three have the same sizes as before; the last three are empty. triParts[triInds[i]] will look exactly the same for all i. What we want this code to produce is:

partTriInds[0] = 0
partTriInds[1] = 100
partTriInds[2] = 300
partTriInds[3] = 600
partTriInds[4] = 600
partTriInds[5] = 600
partTriInds[6] = 600

But what it actually produces is this:

partTriInds[0] = 0
partTriInds[1] = 100
partTriInds[2] = 300
partTriInds[3] = 0
partTriInds[4] = 0
partTriInds[5] = 0
partTriInds[6] = 600

This is bad. The number of triangles in partition 2 is -300, partition 5 has all 600 triangles, and partition 5 overlaps with partitions 0 and 1.

The problem in the original code is the last line:

partTriInds.back() = numTris;

It only sets partTriInds[6] to 600; it should have set partTriInds[3..6] to 600. It should have been:

while (nextPartID < static_cast<int>(partTriInds.size()))
    partTriInds[nextPartID++] = numTris;

In commit eae5755, this code was inserted before the buggy last line:

int maxInd = 0;
for (int i = 0; i < partTriInds.size(); ++i) {
	if (partTriInds[i] == 0) {
		if (maxInd != 0) {
			partTriInds[i] = maxInd;
		}
	}
	else {
		if (partTriInds[i] > maxInd) {
			maxInd = partTriInds[i];
		}
	}
}

For our 6-partition example, this will produce:

partTriInds[0] = 0
partTriInds[1] = 100
partTriInds[2] = 300
partTriInds[3] = 300
partTriInds[4] = 300
partTriInds[5] = 300
partTriInds[6] = 600

This is not right. The last 300 triangles are now in partition 5 instead of partition 2.

Then commit bb1f7a6 wiped out the previous commit and changed it to (still before the buggy last line):

size_t lastFilledPart = 0;
for (size_t i = 0; i < partTriInds.size(); i++)
	if (partTriInds[i] > 0)
		lastFilledPart = i;

// Fill gaps for partitions that don't have any tris assigned
int maxInd = 0;
for (size_t i = 0; i < partTriInds.size(); i++) {
	int& partTriInd = partTriInds[i];

	if (lastFilledPart > 0 && i > lastFilledPart) {
		partTriInd = static_cast<int>(triInds.size());
	}
	else {
		if (partTriInd == 0) {
			if (maxInd != 0) {
				partTriInd = maxInd;
			}
		}
		else {
			if (partTriInd > maxInd) {
				maxInd = partTriInd;
			}
		}
	}
}

For our 6-partition example, this will produce:

partTriInds[0] = 0
partTriInds[1] = 100
partTriInds[2] = 300
partTriInds[3] = 600
partTriInds[4] = 600
partTriInds[5] = 600
partTriInds[6] = 600

That's correct. To spot the problem, we need to consider a different example. Suppose we have two partitions of sizes 50 and 0. Then we want partTriInds to look like this:

partTriInds[0] = 0
partTriInds[1] = 50
partTriInds[2] = 50

But the code produces this:

partTriInds[0] = 0
partTriInds[1] = 0
partTriInds[2] = 50

(The first loop calculates lastFilledPart to be 0. The second loop then does nothing. The final, original line sets the last value to 50.)