Nate Andrew's Monotone Chain. Here I have used the following more common writing method. I analyzed your writing method and used the quick sort algorithm, while I used std::sort, which combines quick sort and heap sort. The time complexity of both is the same O(n log n). Compared with your maintenance of the index, I don't have the corresponding requirements, so my constant factor is smaller. Therefore, I think it is efficient enough.
//（Andrew's Monotone Chain）
static int cross(const sf::Vector2i& O, const sf::Vector2i& A, const sf::Vector2i& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
static std::vector<sf::Vector2i> convexHull(std::vector<sf::Vector2i> P) {
int n = P.size(), k = 0;
if (n <= 1) return P;
std::sort(P.begin(), P.end(), [](auto& a, auto& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
});
std::vector<sf::Vector2i> H(2 * n);
for (int i = 0; i < n; ++i) {
while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
H[k++] = P[i];
}
for (int i = n - 2, t = k + 1; i >= 0; --i) {
while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
H[k++] = P[i];
}
H.resize(k - 1);
return H;
}
Regarding the acquisition of the point set, as you said, I don't have a very good method. I traversed all the pixels. This is indeed a bottleneck. But as you said, I don't want to introduce more things, and the time consumption is actually within the acceptable range. Overall, this has met my needs. Thank you for your suggestion.
Regarding the rendering issue, I have made more attempts below and should be able to provide more details.
This is the complete process I attempted. Meanwhile, I tried to output the duration of the animation, and unsurprisingly, the result was 0.000000.
Next, I will talk about the differences under different conditions.
The difference between the upper left corner and the lower left corner lies in whether this is enabled or not. I found that if the attachment is not explicitly set, even if I do not set an exit condition when counting the bounding box, the unrendered attachments will not be recorded.
for (int i = 0; i < skeleton->slotsCount; ++i) {
spSlot* slot = skeleton->drawOrder[i];
if (!slot->attachment && slot->data->attachmentName) {
spAttachment* att = Skeleton_getAttachmentForSlotName(skeleton, slot->data->name, slot->data->attachmentName);
if (att) slot->attachment = att;
From the difference between the upper left and the right, I learned that not all attachments need to be forcibly opened. There might be a judgment condition here, and I don't know how to handle it.
Then let's look at another example. The layout is consistent with the previous one, but we can see that after enabling all attachments, there is no difference. At the same time, just like above, it is not included in the statistics of the bounding box.
As you said, I have rendered it on the screen. In fact, there is no difference between it and when I output it to PNG (always as an example in the upper left corner).
Is there any extra processing in the skeletonViewer rendering process, the latter example still has no idea for me.
Nate I can only guess at what is wrong, but it seems as if some batched geometry was not flushed at the end of your rendering.
For this issue, I only performed such rendering once throughout the full text and there was no cross-thread operation. I don't think it matters much here. According to the previous examples, the location where the error occurred should be at or before the earlier traversal.
