如何雕刻半个感恩节火鸡？

Question

我有一个很酷的问题。我试着突出这只火鸡质量的50%。实际上，它不会是50%，但如果我能得到50%，我就可以计算出其余的。

我现在的想法是:扫描每一个像素，找出火鸡的质量，以像素为单位。然后，当我想要50%的火鸡时，从左到右突出显示像素，直到我突出显示了50%的像素。

有没有更好的主意？这是最慢的，蛮力的想法，需要在每个像素上循环一次来计算像素，然后再次高亮显示其中的50%。

请注意，垂直分割图片不会留下50%的火鸡，因为火鸡的身体比它的脖子要肥得多。

​

​

Answer 1

你说百分比会改变，但我要冒险假设火鸡本身不会改变。

所以你不需要循环两次。你只需要做一次，将数据映射到你可以引用的某种形式的结构中，然后在每次你需要突出显示的时候引用它，以确定你需要走多远。

例如，创建一个<percentage of mass (integer out of a hundred) => vertical column number (int)>的关联数组

这样，当您需要对x百分比进行着色时，只需循环遍历像素的cached_datapercent_to_highlight列，对所有像素进行着色，然后在到达该列时完全退出循环。

为了获得更好的性能，可以使用两张图片--一张是全阴影图片，另一张是普通图片。关联数组应映射percentage => byte_offset

对于您希望生成的每个图像，只需简单的memcpy或任何PHP的等价物的快速，范围的拷贝，从0 -> byte_offset的阴影图片在非阴影和保存。没有更多的循环。你不能比这更快了。

Answer 2

这个问题看起来没有一个聪明的算法在我的头顶上去做它。但是，我也不是CG方面的专家，所以在这一点上我可能是错的。

如果你最终在n上使用嵌套循环，那么尝试寻找这样的解决方案会很好地增加时间复杂度(比O(N))，其中n是火鸡使用的像素总数。

相反，做两遍的方法非常容易实现(实现的时间/精力非常少)，而且忽略常量2也是O(n)，这是一个不错的解决方案。这取决于您编写此解决方案的目的、硬件、空间限制等；采用两种方式可能更有价值。