当前位置:网站首页>Vulkan 预旋转处理设备方向
Vulkan 预旋转处理设备方向
2022-06-22 05:34:00 【警醒与鞭策】
使用 Vulkan 预旋转处理设备方向
本文介绍了如何通过实现预旋转来有效地处理 Vulkan 应用程序中的设备旋转。
Vulkan允许您指定比 OpenGL 更多的有关渲染状态的信息。伴随着这种力量而来的是一些新的责任;您应该明确地实现由 OpenGL 中的驱动程序处理的事情。其中之一是设备方向及其与 渲染表面方向的关系。目前,Android 可以通过 3 种方式来协调设备的渲染表面与设备方向:
- 该设备有一个显示处理单元 (DPU),可以有效地处理硬件中的表面旋转。(仅在支持的设备上)
- Android 操作系统可以通过添加合成器通道来处理表面旋转,这将产生性能成本,具体取决于合成器必须如何处理旋转输出图像。
- 应用程序本身可以通过将旋转的图像渲染到与显示器的当前方向匹配的渲染表面来处理表面旋转。
这对您的应用意味着什么?
目前没有一种方法可以让应用程序知道在应用程序之外处理的表面旋转是否是免费的。即使有一个 DPU 可以为您解决这个问题,仍然可能需要支付可衡量的性能损失。如果您的应用程序受 CPU 限制,由于 Android 合成器(通常以更高的频率运行)增加了 GPU 使用率,这将成为一个电源问题。如果您的应用程序受 GPU 限制,那么 Android 合成器也可以抢占您应用程序的 GPU 工作,从而导致额外的性能损失。
在 Pixel 4XL 上运行交付游戏时,我们看到 SurfaceFlinger(驱动 Android 合成器的更高优先级任务)会定期抢占应用程序的工作,从而导致 1-3 毫秒的帧时间命中,并增加 GPU 顶点的压力/texture 内存,因为合成器必须读取整个帧缓冲区才能完成合成工作。
正确处理方向几乎完全停止了 SurfaceFlinger 的 GPU 抢占,而 GPU 频率下降了 40%,因为不再需要 Android 合成器使用的提升频率。
为了确保以尽可能少的开销正确处理表面旋转(如上例所示),我们建议实施方法 3,这称为预旋转。这告诉 Android 操作系统您的应用程序 处理表面旋转。您可以通过在创建交换链期间传递指定方向的表面变换标志来做到这一点。这会阻止Android 合成器自己进行旋转。
知道如何设置表面变换标志对于每个 Vulkan 应用程序都很重要,因为应用程序倾向于支持多个方向或支持单一方向,其中渲染表面的方向与设备认为的身份方向不同。例如,纵向身份手机上的仅横向应用程序,或横向身份平板电脑上的仅纵向应用程序。
在本文中,我们将详细描述如何在您的 Vulkan 应用程序中实现预旋转和处理设备旋转。
修改 AndroidManifest 。xml
要在您的应用程序中处理设备旋转,首先要更改应用程序的 AndroidManifest.xml文件,告诉 Android 您的应用程序将处理方向和屏幕尺寸的变化。这可以防止 Android在发生方向更改时销毁和重新创建 Android 并在现有窗口表面上Activity调用该 函数。onDestroy()这是通过将orientation(以支持 API 级别 <13)和screenSize属性添加到活动 configChanges部分来完成的:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)"><activity</span> <span style="color:var(--devsite-code-types-color)">android:name</span>=<span style="color:var(--devsite-code-strings-color)">"android.app.NativeActivity"</span>
<span style="color:var(--devsite-code-types-color)">android:configChanges</span>=<span style="color:var(--devsite-code-strings-color)">"orientation|screenSize"</span><span style="color:var(--devsite-code-keywords-color)">></span>
</code></span>如果您的应用程序使用该属性修复其屏幕方向,screenOrientation 则无需执行此操作。此外,如果您的应用程序使用固定方向,那么它只需要在应用程序启动/恢复时设置一次交换链。
获取身份屏幕分辨率和相机参数
接下来需要做的是检测与该VK_SURFACE_TRANSFORM_IDENTITY_BIT_KHR值关联的设备的屏幕分辨率。此分辨率与设备的身份方向相关联,因此始终需要设置交换链。最可靠的方法是在应用程序启动时调用 vkGetPhysicalDeviceSurfaceCapabilitiesKHR()并存储返回的范围。您需要根据 currentTransform返回的 交换宽度和高度,以确保存储身份屏幕分辨率:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-types-color)">VkSurfaceCapabilitiesKHR</span> capabilities;
vkGetPhysicalDeviceSurfaceCapabilitiesKHR(physDevice, surface, &capabilities);
uint32_t width = capabilities.currentExtent.width;
uint32_t height = capabilities.currentExtent.height;
<span style="color:var(--devsite-code-keywords-color)">if</span> (capabilities.currentTransform & VK_SURFACE_TRANSFORM_ROTATE_90_BIT_KHR ||
capabilities.currentTransform & VK_SURFACE_TRANSFORM_ROTATE_270_BIT_KHR) {
<span style="color:var(--devsite-code-comments-color)">// Swap to get identity width and height</span>
capabilities.currentExtent.height = width;
capabilities.currentExtent.width = height;
}
displaySizeIdentity = capabilities.currentExtent;
</code></span>displaySizeIdentity 是VkExtent2D我们用来存储应用程序窗口表面在显示器自然方向上的标识分辨率的结构。
检测设备方向变化 (Android 10+)
检测应用程序中方向变化的最可靠方法是验证vkQueuePresentKHR()函数是否返回 VK_SUBOPTIMAL_KHR。例如:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">auto</span> res = vkQueuePresentKHR(queue_, &present_info);
<span style="color:var(--devsite-code-keywords-color)">if</span> (res == VK_SUBOPTIMAL_KHR){
orientationChanged = <span style="color:var(--devsite-code-keywords-color)">true</span>;
}
</code></span>注意:此方案仅适用于运行 Android 10 及更高版本的设备;那是 Android 开始 VK_SUBOPTIMAL_KHR从vkQueuePresentKHR(). 我们存储此签入的结果,orientationChanged可以boolean从应用程序的主渲染循环访问。
检测设备方向变化(Android 10 之前的版本)
对于运行低于 10 的旧版本 Android 的设备,需要不同的实现,因为VK_SUBOPTIMAL_KHR不支持。
使用轮询
在 Android 10 之前的设备上,您可以每 pollingInterval帧轮询当前设备变换,其中pollingInterval的粒度由程序员决定。执行此操作的方法是调用 vkGetPhysicalDeviceSurfaceCapabilitiesKHR()返回的字段,然后将其 currentTransform与当前存储的表面变换的字段进行比较(在此代码示例中存储在 中pretransformFlag)。
<span style="color:var(--devsite-code-color)"><code>currFrameCount++;
<span style="color:var(--devsite-code-keywords-color)">if</span> (currFrameCount >= pollInterval){
<span style="color:var(--devsite-code-types-color)">VkSurfaceCapabilitiesKHR</span> capabilities;
vkGetPhysicalDeviceSurfaceCapabilitiesKHR(physDevice, surface, &capabilities);
<span style="color:var(--devsite-code-keywords-color)">if</span> (pretransformFlag != capabilities.currentTransform) {
window_resized = <span style="color:var(--devsite-code-keywords-color)">true</span>;
}
currFrameCount = <span style="color:var(--devsite-code-numbers-color)">0</span>;
}
</code></span>在运行 Android 10 的 Pixel 4 上,轮询 vkGetPhysicalDeviceSurfaceCapabilitiesKHR()耗时 0.120-.250 毫秒,而在运行 Android 8 的 Pixel 1XL 上,轮询耗时 0.110-.350 毫秒。
使用回调
运行在 Android 10 以下的设备的第二个选项是注册 onNativeWindowResized()回调以调用设置 orientationChanged标志的函数,向应用程序发出方向更改发生的信号:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">void</span> android_main(<span style="color:var(--devsite-code-keywords-color)">struct</span> android_app *app) {
...
app->activity->callbacks->onNativeWindowResized = <span style="color:var(--devsite-code-types-color)">ResizeCallback</span>;
}
</code></span>其中 ResizeCallback 定义为:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">void</span> <span style="color:var(--devsite-code-types-color)">ResizeCallback</span>(<span style="color:var(--devsite-code-types-color)">ANativeActivity</span> *activity, <span style="color:var(--devsite-code-types-color)">ANativeWindow</span> *window){
orientationChanged = <span style="color:var(--devsite-code-keywords-color)">true</span>;
}
</code></span>这个解决方案的缺点是onNativeWindowResized()只在 90 度方向变化时被调用(从横向到纵向,反之亦然),所以例如从横向到反向横向的方向变化不会触发交换链重建,需要 Android合成器为您的应用程序进行翻转。
处理方向变化
orientationChanged 要处理方向更改,请在变量设置为 true时调用主渲染循环顶部的方向更改例程。例如:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">bool</span> <span style="color:var(--devsite-code-types-color)">VulkanDrawFrame</span>() {
<span style="color:var(--devsite-code-keywords-color)">if</span> (orientationChanged) {
<span style="color:var(--devsite-code-types-color)">OnOrientationChange</span>();
}
</code></span>在该OnOrientationChange()函数中,您将完成重新创建交换链所需的所有工作。这涉及销毁 Framebuffer和的任何现有实例ImageView;在销毁旧交换链的同时重新创建交换链(将在下面讨论);然后使用新交换链的 DisplayImages 重新创建帧缓冲区。请注意,附件图像(例如深度/模板图像)通常不需要重新创建,因为它们基于预旋转交换链图像的身份分辨率。
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">void</span> <span style="color:var(--devsite-code-types-color)">OnOrientationChange</span>() {
vkDeviceWaitIdle(getDevice());
<span style="color:var(--devsite-code-keywords-color)">for</span> (<span style="color:var(--devsite-code-keywords-color)">int</span> i = <span style="color:var(--devsite-code-numbers-color)">0</span>; i < getSwapchainLength(); ++i) {
vkDestroyImageView(getDevice(), displayViews_[i], <span style="color:var(--devsite-code-keywords-color)">nullptr</span>);
vkDestroyFramebuffer(getDevice(), framebuffers_[i], <span style="color:var(--devsite-code-keywords-color)">nullptr</span>);
}
createSwapChain(getSwapchain());
createFrameBuffers(render_pass, depthBuffer.image_view);
orientationChanged = <span style="color:var(--devsite-code-keywords-color)">false</span>;
}
</code></span>在函数结束时,您将orientationChanged标志重置为 false 以表明您已经处理了方向更改。
交换链娱乐
在上一节中,我们提到必须重新创建交换链。这样做的第一步是获取渲染表面的新特性:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">void</span> createSwapChain(<span style="color:var(--devsite-code-types-color)">VkSwapchainKHR</span> oldSwapchain) {
<span style="color:var(--devsite-code-types-color)">VkSurfaceCapabilitiesKHR</span> capabilities;
vkGetPhysicalDeviceSurfaceCapabilitiesKHR(physDevice, surface, &capabilities);
pretransformFlag = capabilities.currentTransform;
</code></span>使用新信息填充结构后,您现在可以通过检查字段VkSurfaceCapabilities来检查方向是否发生了变化 。currentTransform您将其存储在pretransformFlag 现场以备后用,因为您稍后对 MVP 矩阵进行调整时将需要它。
为此,请在VkSwapchainCreateInfo结构中指定以下属性:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-types-color)">VkSwapchainCreateInfoKHR</span> swapchainCreateInfo{
...
.sType = VK_STRUCTURE_TYPE_SWAPCHAIN_CREATE_INFO_KHR,
.imageExtent = displaySizeIdentity,
.preTransform = pretransformFlag,
.oldSwapchain = oldSwapchain,
};
vkCreateSwapchainKHR(device_, &swapchainCreateInfo, <span style="color:var(--devsite-code-keywords-color)">nullptr</span>, &swapchain_));
<span style="color:var(--devsite-code-keywords-color)">if</span> (oldSwapchain != VK_NULL_HANDLE) {
vkDestroySwapchainKHR(device_, oldSwapchain, <span style="color:var(--devsite-code-keywords-color)">nullptr</span>);
}
</code></span>该imageExtent字段将填充displaySizeIdentity您在应用程序启动时存储的范围。该preTransform字段将填充pretransformFlag变量(设置为 的 currentTransform 字段surfaceCapabilities)。您还将该oldSwapchain字段设置为将被销毁的交换链。
注意:字段和 字段匹配很重要, 因为这让 Android 知道我们正在自己处理方向更改,从而避免了 Android 合成器。surfaceCapabilities.currentTransformswapchainCreateInfo.preTransform
MVP矩阵调整
需要做的最后一件事是通过将旋转矩阵应用于 MVP 矩阵来应用预转换。这实质上是在剪辑空间中应用旋转,以便将生成的图像旋转到当前设备方向。然后,您可以简单地将这个更新的 MVP 矩阵传递到您的顶点着色器中,并像往常一样使用它,而无需修改您的着色器。
<span style="color:var(--devsite-code-color)"><code>glm::mat4 pre_rotate_mat = glm::mat4(<span style="color:var(--devsite-code-numbers-color)">1.0f</span>);
glm::vec3 rotation_axis = glm::vec3(<span style="color:var(--devsite-code-numbers-color)">0.0f</span>, <span style="color:var(--devsite-code-numbers-color)">0.0f</span>, <span style="color:var(--devsite-code-numbers-color)">1.0f</span>);
<span style="color:var(--devsite-code-keywords-color)">if</span> (pretransformFlag & VK_SURFACE_TRANSFORM_ROTATE_90_BIT_KHR) {
pre_rotate_mat = glm::rotate(pre_rotate_mat, glm::radians(<span style="color:var(--devsite-code-numbers-color)">90.0f</span>), rotation_axis);
}
<span style="color:var(--devsite-code-keywords-color)">else</span> <span style="color:var(--devsite-code-keywords-color)">if</span> (pretransformFlag & VK_SURFACE_TRANSFORM_ROTATE_270_BIT_KHR) {
pre_rotate_mat = glm::rotate(pre_rotate_mat, glm::radians(<span style="color:var(--devsite-code-numbers-color)">270.0f</span>), rotation_axis);
}
<span style="color:var(--devsite-code-keywords-color)">else</span> <span style="color:var(--devsite-code-keywords-color)">if</span> (pretransformFlag & VK_SURFACE_TRANSFORM_ROTATE_180_BIT_KHR) {
pre_rotate_mat = glm::rotate(pre_rotate_mat, glm::radians(<span style="color:var(--devsite-code-numbers-color)">180.0f</span>), rotation_axis);
}
MVP = pre_rotate_mat * MVP;
</code></span>注意事项 - 非全屏视口和剪刀
如果您的应用程序正在使用非全屏视口/剪刀区域,则需要根据设备的方向对其进行更新。这要求您在 Vulkan 创建管道期间启用动态 Viewport 和 Scissor 选项:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-types-color)">VkDynamicState</span> dynamicStates[<span style="color:var(--devsite-code-numbers-color)">2</span>] = {
VK_DYNAMIC_STATE_VIEWPORT,
VK_DYNAMIC_STATE_SCISSOR,
};
<span style="color:var(--devsite-code-types-color)">VkPipelineDynamicStateCreateInfo</span> dynamicInfo = {
.sType = VK_STRUCTURE_TYPE_PIPELINE_DYNAMIC_STATE_CREATE_INFO,
.pNext = <span style="color:var(--devsite-code-keywords-color)">nullptr</span>,
.flags = <span style="color:var(--devsite-code-numbers-color)">0</span>,
.dynamicStateCount = <span style="color:var(--devsite-code-numbers-color)">2</span>,
.pDynamicStates = dynamicStates,
};
<span style="color:var(--devsite-code-types-color)">VkGraphicsPipelineCreateInfo</span> pipelineCreateInfo = {
.sType = VK_STRUCTURE_TYPE_GRAPHICS_PIPELINE_CREATE_INFO,
...
.pDynamicState = &dynamicInfo,
...
};
<span style="color:var(--devsite-code-types-color)">VkCreateGraphicsPipelines</span>(device, VK_NULL_HANDLE, <span style="color:var(--devsite-code-numbers-color)">1</span>, &pipelineCreateInfo, <span style="color:var(--devsite-code-keywords-color)">nullptr</span>, &mPipeline);
</code></span>命令缓冲区记录期间视口范围的实际计算如下所示:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">int</span> x = <span style="color:var(--devsite-code-numbers-color)">0</span>, y = <span style="color:var(--devsite-code-numbers-color)">0</span>, w = <span style="color:var(--devsite-code-numbers-color)">500</span>, h = <span style="color:var(--devsite-code-numbers-color)">400</span>;
glm::vec4 viewportData;
<span style="color:var(--devsite-code-keywords-color)">switch</span> (device-><span style="color:var(--devsite-code-types-color)">GetPretransformFlag</span>()) {
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_90_BIT_KHR:
viewportData = {bufferWidth - h - y, x, h, w};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_180_BIT_KHR:
viewportData = {bufferWidth - w - x, bufferHeight - h - y, w, h};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_270_BIT_KHR:
viewportData = {y, bufferHeight - w - x, h, w};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">default</span>:
viewportData = {x, y, w, h};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
}
<span style="color:var(--devsite-code-keywords-color)">const</span> <span style="color:var(--devsite-code-types-color)">VkViewport</span> viewport = {
.x = viewportData.x,
.y = viewportData.y,
.width = viewportData.z,
.height = viewportData.w,
.minDepth = <span style="color:var(--devsite-code-numbers-color)">0.0F</span>,
.maxDepth = <span style="color:var(--devsite-code-numbers-color)">1.0F</span>,
};
vkCmdSetViewport(renderer-><span style="color:var(--devsite-code-types-color)">GetCurrentCommandBuffer</span>(), <span style="color:var(--devsite-code-numbers-color)">0</span>, <span style="color:var(--devsite-code-numbers-color)">1</span>, &viewport);
</code></span>x和y变量定义视口左上角的坐标,而和w分别h定义视口的宽度和高度。相同的计算也可用于设置剪刀测试,为了完整性,将其包含在下面:
<span style="color:var(--devsite-code-color)"><code><span style="color:var(--devsite-code-keywords-color)">int</span> x = <span style="color:var(--devsite-code-numbers-color)">0</span>, y = <span style="color:var(--devsite-code-numbers-color)">0</span>, w = <span style="color:var(--devsite-code-numbers-color)">500</span>, h = <span style="color:var(--devsite-code-numbers-color)">400</span>;
glm::vec4 scissorData;
<span style="color:var(--devsite-code-keywords-color)">switch</span> (device-><span style="color:var(--devsite-code-types-color)">GetPretransformFlag</span>()) {
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_90_BIT_KHR:
scissorData = {bufferWidth - h - y, x, h, w};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_180_BIT_KHR:
scissorData = {bufferWidth - w - x, bufferHeight - h - y, w, h};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">case</span> VK_SURFACE_TRANSFORM_ROTATE_270_BIT_KHR:
scissorData = {y, bufferHeight - w - x, h, w};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
<span style="color:var(--devsite-code-keywords-color)">default</span>:
scissorData = {x, y, w, h};
<span style="color:var(--devsite-code-keywords-color)">break</span>;
}
<span style="color:var(--devsite-code-keywords-color)">const</span> <span style="color:var(--devsite-code-types-color)">VkRect2D</span> scissor = {
.offset =
{
.x = (int32_t)viewportData.x,
.y = (int32_t)viewportData.y,
},
.extent =
{
.width = (uint32_t)viewportData.z,
.height = (uint32_t)viewportData.w,
},
};
vkCmdSetScissor(renderer-><span style="color:var(--devsite-code-types-color)">GetCurrentCommandBuffer</span>(), <span style="color:var(--devsite-code-numbers-color)">0</span>, <span style="color:var(--devsite-code-numbers-color)">1</span>, &scissor);
</code></span>考虑 - 片段着色器衍生物
dFdx如果您的应用程序正在使用和之类的导数计算dFdy,则可能需要额外的转换来解释旋转坐标系,因为这些计算是在像素空间中执行的。这要求应用程序将一些 preTransform 指示传递给片段着色器(例如表示当前设备方向的整数)并使用它来正确映射导数计算:
- 对于90 度预旋转框架
- dFdx需要映射到dFdy
- dFdy需要映射到-dFdx
- 对于270 度预旋转框架
- dFdx需要映射到-dFdy
- dFdy需要映射到dFdx
- 对于180 度预旋转框架,
- dFdx需要映射到-dFdx
- dFdy需要映射到-dFdy
结论
为了让您的应用程序在 Android 上充分利用 Vulkan,必须实现预旋转。这篇文章最重要的收获是:
- 确保在创建或重新创建交换链期间,设置了 pretransform 标志,使其与 Android 操作系统返回的标志相匹配。这将避免合成器开销。
- 将交换链大小固定为应用程序窗口表面在显示器自然方向上的标识分辨率。
- 旋转剪辑空间中的 MVP 矩阵以考虑设备方向,因为交换链分辨率/范围不再随显示器方向更新。
- 根据应用程序的需要更新视口和剪刀矩形
//
边栏推荐
- Global and Chinese carbon conductive filler market demand trend and future prospect report 2022-2027
- 独立站优化清单丨如何有效提升站内转化率?
- 随鼠标移动的提示框
- Report on global and Chinese direct coupled actuator market demand and future development planning recommendations 2022-2027
- Independent station optimization list - how to effectively improve the conversion rate in the station?
- Analysis of 43 cases of MATLAB neural network: Chapter 28 Application Research of decision tree classifier - breast cancer diagnosis
- mysql基础面试题
- Introduction to golang Viper Library
- 数据的存储(进阶)
- Facebook账户 “ 解封、防封、养号 ” 知识要点,已收藏!
猜你喜欢
随机推荐
Record some problems and solutions encountered in processing SIF data
Xshell download and installation (solve the problem of expired evaluation)
我不建议你工作太拼命
sourcetree报错ssh失败
Network, IO flow, reflection, multithreading, exception
Mobile terminal layout adaptation
机器学习笔记 八:Octave实现神经网络的手写数字识别
搜狗输入法无法输出中文
向量空间视角看高数(1)——系列简介
独立站优化清单丨如何有效提升站内转化率?
vscode极简安装教程
Tensorflow 2. Chapter 14: callbacks and custom callbacks in keras
I2C接口
Research Report on global and Chinese active Ethernet access device industry demand trend and investment prospect 2022-2027
北峰助力南昌市应急管理局打造公专融合应急通信保障网
QEMU ARM interrupt system architecture
Parameter serialization
mysql基础面试题
Analysis report on market demand trend and investment prospect of global and Chinese pulse transistor industry 2022-2027
n个整数的无序数组,找到每个元素后面比它大的第一个数,要求时间复杂度为O(N)









