哈希表的应用-浅析顶点聚簇网格简化算法的实现

2024-09-04 19:48

本文主要是介绍哈希表的应用-浅析顶点聚簇网格简化算法的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

  本篇接顶点去重那一篇,继续使用哈希表来实现网格算法。这次介绍的是一种比较简单的网格简化算法,叫做顶点聚簇。

 

网格简化

  为了介绍这个算法,首先说明一下网格简化算法。随着计算机绘图在现代科技领域中的广泛应用, 计算机图形在现代制造业中发挥着重要的作用。计算机图形学中对模型的要求更加精密, 也更加复杂, 生成的面片数也更加庞大, 庞大的数据量必然对计算机的计算能力提出更高要求, 对模型的生成也带来更多困难[。为此, 需要对重建得到的复杂的数学模型进行简化, 以减少数据量和数据模型的复杂程度, 这就使得网格简化的提出成为必然。模型简化也称数据缩小或数据删减, 对于实时应用来说, 通常需要这个过程来减少存储的顶点数并将这些顶点发送到图形管线。网格简化的目的是在尽量保持原模型可视特征的条件下, 减少模型的多边形数目。

 

网格简化方法之顶点聚簇网格削减

  顶点聚簇方法又被叫做顶点聚类。顶点聚簇方法的原理首先是将原模型统一归于一个大区域,然后对大区域进行划分,使得小区域中包含了许多散落其中的顶点,再将此区域中的顶点合并,形成新的顶点,再根据原始网格的拓扑关系,把这些顶点三角化后,从而得到简化模型。下图也可以生动的说明顶点聚簇的原理。

  顶点聚簇是比较简单高效的网格简化算法,不过缺点是生成结果的质量不如其他的网格简化算法。

 

使用顶点聚簇来简化SMC算法生成的网格

  由于SMC算法生成的网格顶点坐标都是基于原来三维图像中的体素索引,所以这些顶点都可以看作是处在单位长度为1的笛卡尔网格之上。坐标范围则是从(0,0,0)到(Mesh的X最大值,Mesh的Y最大值,Mesh的Z最大值),所以实际上这样的网格可以当作已经被单位长度为1的正方体区域所划分了。这样假如想要进行顶点聚簇简化,就需要用一个大于1的浮点值为边长再来给空间划分正方体区域,这个值是用户提供的参数,下文用unitLength来指代这个参数,表示它是新的单位长度。同时不难想到unitLength越大,网格削减的越厉害。

  算法可以采用在“浅议顶点焊接”一篇中的哈希表来实现,这个哈希表的作用就是为三维空间中的整点提供快速存储与查找。在顶点聚类算法中,我们可以将在一个新正方体单位区域的点都合并为一个点并存入这样的哈希表中。这样我们就能将新的点重新存在新的Mesh中,而原来的三角形用同样的道理来替换其中点的索引,最后将位退化的三角形存在新Mesh的三角形表中。

  综上所述,用C#实现算法的代码如下:

复制代码
public class VertexCluster
{Mesh mesh;public VertexCluster(Mesh mesh){this.mesh = mesh;}public void Clear(){mesh = null;}public void ExecuteSimplification(float unitLength){if (unitLength <= 1){return;}Mesh newMesh = new Mesh();//新建Mesh存放削减后的网格Box3Float box = mesh.GetBox3();//首先获取Mesh的空间范围 XYZ方向的最大最小值存在box中int resx = (int)((box.Max3[0] - box.Min3[0]) / unitLength) + 1;int resy = (int)((box.Max3[1] - box.Min3[1]) / unitLength) + 1;int resz = (int)((box.Max3[2] - box.Min3[2]) / unitLength) + 1;//在新的单位长度下,得出新空间划分出的每一维的长度
HashTable_Double2dArray<int> hash = new HashTable_Double2dArray<int>(resx+1, resy+1, resz+1);//创建hash表,这里使用的是双二维数组哈希表for (int i = 0; i < mesh.Vertices.Count; i++){Point3d p = mesh.Vertices[i];int xindex = (int)((p.X - box.Min3[0]) / unitLength);int yindex = (int)((p.Y - box.Min3[1]) / unitLength);int zindex = (int)((p.Z - box.Min3[2]) / unitLength);//计算点在新单位长度下的坐标int value = 0;bool hasValue = hash.GetHashValue(xindex, yindex, zindex, ref value);if (!hasValue){hash.SetHashValue(xindex, yindex, zindex, newMesh.Vertices.Count);newMesh.AddVertex(new Point3d(xindex, yindex, zindex));}//新单位长度下肯定有原来不同的点映射到相同的位置,//总是添加第一次映射到这个位置的点入Mesh,之后的不再添加
        }for (int i = 0; i < mesh.Faces.Count; i++){Triangle t = mesh.Faces[i];Point3d p0 = mesh.Vertices[t.P0Index];Point3d p1 = mesh.Vertices[t.P1Index];Point3d p2 = mesh.Vertices[t.P2Index];int xindex0 = (int)((p0.X - box.Min3[0]) / unitLength);int yindex0 = (int)((p0.Y - box.Min3[1]) / unitLength);int zindex0 = (int)((p0.Z - box.Min3[2]) / unitLength);int index0 = 0;hash.GetHashValue(xindex0, yindex0, zindex0, ref index0);int xindex1 = (int)((p1.X - box.Min3[0]) / unitLength);int yindex1 = (int)((p1.Y - box.Min3[1]) / unitLength);int zindex1 = (int)((p1.Z - box.Min3[2]) / unitLength);int index1 = 0;hash.GetHashValue(xindex1, yindex1, zindex1, ref index1);int xindex2 = (int)((p2.X - box.Min3[0]) / unitLength);int yindex2 = (int)((p2.Y - box.Min3[1]) / unitLength);int zindex2 = (int)((p2.Z - box.Min3[2]) / unitLength);int index2 = 0;hash.GetHashValue(xindex2, yindex2, zindex2, ref index2);if (!(index0 == index1 || index0 == index2 || index1 == index2)){newMesh.AddFace(new Triangle(index0, index1, index2));}//对于每个三角形,找出其三点对应的新位置,检查是否有两个点重合(退化),//添加不退化的三角形
        }for (int i = 0; i < newMesh.Vertices.Count; i++){Point3d p = newMesh.Vertices[i];p.X = (float)(unitLength * p.X + box.Min3[0]);p.Y = (float)(unitLength * p.Y + box.Min3[1]);p.Z = (float)(unitLength * p.Z + box.Min3[2]);}//将新Mesh的坐标放大到和原来一样的尺度
        mesh.Clear();mesh.Vertices = newMesh.Vertices;mesh.Faces = newMesh.Faces;//替换旧Mesh的数据
    }
}
复制代码

 

算法测试

  数据采用Engine数据,下表展示了算法的结果。

- 简花前   简化后
数据预览  
顶点数 216147   110910
三角形数 432370   220528
单位长度 1.0   1.5
削减比例(顶点) -   48.7%
削减比例(三角形) -   49.0%

  可以看出,顶点聚簇算法均匀的减少了三角网格的密度。

这篇关于哈希表的应用-浅析顶点聚簇网格简化算法的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136861

相关文章

C#使用yield关键字实现提升迭代性能与效率

《C#使用yield关键字实现提升迭代性能与效率》yield关键字在C#中简化了数据迭代的方式,实现了按需生成数据,自动维护迭代状态,本文主要来聊聊如何使用yield关键字实现提升迭代性能与效率,感兴... 目录前言传统迭代和yield迭代方式对比yield延迟加载按需获取数据yield break显式示迭

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作(适用于大文件)四、使用 pand

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1,PDF转Word2,PDF转Excel三、前端页面效果展示总结一

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求:新用户入职 创建一系列账号比较麻烦,打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中,常将INI文件作为配置文件,用于存储应用程序的

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候,发现软件中的端口号并不是普通的COM1,而是带有硬件信息的。那么如果我们使用C#编写软件时候,如

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ