当前位置: 首页 > news >正文

关于三维布尔运算的几点思考

目录

  • 三维布尔运算概述
    • 三角网格布尔运算
    • 效率提升思考
    • `BSPTree`方式优化
  • 参考

三维布尔运算概述

三维布尔运算根据三维实体数据结构表达分为CSG布尔运算、Brep布尔运算、三角网格布尔运算等类型。这几种类型算法在不同情境下有不同的优势,根据情况进行选择。但这也不能作为随意选择方案的借口,在不分析实际情况下。

CSG和BRep布尔运算能够保留原始几何拓扑信息,适用于各类设计编辑场景,如建模设计软件中。而三角网格布尔运算也是常见和常用的,由于一些因素,当前实体的表达方式就是三角面网格方式,也需要对这些实体进行编辑,这时候三角网格布尔运算是最佳选择方案。当然也有其他方案,如将三角网格实体拟合为Brep实体,然后使用BRep布尔运算方法进行计算,至于有没有必要,还是上述表达的那样,根据实际情况分析,进行选择取舍。

本文就三角网格布尔运算几点思考进行简单记录。

三角网格布尔运算

三维布尔运算的一个核心思想是得到运算两实体彼此相对内外部分,然后根据布尔运算类型对这些部分进行组合。如实体A与实体B进行计算得到A in BA out BB in AB out A四部分,实体A与实体B求交运算即为A in B + B in A,求并、求差运算类似,求差会涉及到组合前对对应部分进行取反,这里不再赘述。

那么问题来了,如何提高运算得到两实体彼此相对内外部分的效率?

效率提升思考

关于该问题有不少论文、文章、开源库、商业库进行过思考,并形成各自提出的方案,思路主线是怎样降低判断一个三角面与实体的包含关系的运算时间。

目前有空间分区二叉树(BSPTree)和其它搜索树(如八叉树、球体空间位置树)等方案。

BSPTree方式:基于实体本身的几何拓扑数据构造树(三角面所在超平面对实体空间进行分割

  • 优势是在搜索时即可以得到精确的结果;
  • 劣势是会产生较多的碎三角面构造的BSPTree可能不太平衡,当然这两个问题都有方案去应对;

八叉树方式:根据实体空间分布进行八叉树的构造,得到的搜索树比较平衡,搜索得到相关三角面子集后,由三角面子集对目标三角面进行切割,根据切割线(有向)和目标三角面本身的轮廓线(有向)进行路径搜索得到目标三角面在实体内外部分。当然可能没有切割到,这时就需要判断目标三角面是在实体内部还是外部,同样可以利用实体八叉树降低此判断复杂度。

  • 优势是根据实体空间分布进行八叉树的构造,得到的搜索树比较平衡,同时不会产生多余的三角面;
  • 劣势是计算实现复杂;

如果不进行优化,判断一个三角面与实体的包含关系的时间复杂度为O(N),而上述两种优化方案复杂度均为O(logN),但并不意味着效率一样,只是效率的级数一致,但毕竟N和6N还是有倍数差距的。

BSPTree方式优化

在构建实体BSPTree时产生零散的三角面是合理的,也是为了计算精确。目标三角面在BSPTree中进行搜寻过程中由于切割产生了很多零碎的三角面,这个问题可以通过记录新产生的零碎三角面对应的原始三角ID的方式,进行针对性的拟合,达到消除冗余三角面的目的。

至于怎么尽可能保持BSPTree平衡,可以选择与所在超平面与三角面集质心距离最近或较近的三角面作为拆分左右子树的参照三角面

参考

1.三维模型的布尔运算研究
2.几何算法学习实践(三维)
3.3D网格布尔运算开源库

相关文章:

关于三维布尔运算的几点思考

目录 三维布尔运算概述三角网格布尔运算效率提升思考BSPTree方式优化 参考 三维布尔运算概述 三维布尔运算根据三维实体数据结构表达分为CSG布尔运算、Brep布尔运算、三角网格布尔运算等类型。这几种类型算法在不同情境下有不同的优势,根据情况进行选择。但这也不能…...

【03.04】大数据教程--html+css基础

当谈到大数据时,HTML和CSS可能并不是最相关的技术。HTML和CSS主要用于构建网页和应用程序的用户界面,而大数据则涉及处理和分析大规模数据集。但是,如果您想展示有关大数据的信息或结果,并在网页上呈现,那么HTML和CSS可…...

深入理解与实践Seata:分布式事务解决方案

✅作者简介:热爱Java后端开发的一名学习者,大家可以跟我一起讨论各种问题喔。 🍎个人主页:Hhzzy99 🍊个人信条:坚持就是胜利! 💞当前专栏:微服务 🥭本文内容&…...

Python学习笔记 - 探索元组Tuple的使用

欢迎各位,我是Mr数据杨,你们的Python导游。今天,我要为大家讲解一段特殊的旅程,它与《三国演义》有关,而我们的主角是元组(tuple)。 让我们想象这样一个场景,三国演义中的诸葛亮&am…...

JAVA网络编程(一)

一、什么是网络编程 定义:在网络通信协议下,不同计算机上运行的程序,进行的数据传输。 应用场景:即时通信,网游,邮件等 不管什么场景,都是计算机与计算机之间通过网络在进行数据传输 java提供一…...

Python 线程队列

文章目录 Python 中的线程在 Python 中使用队列限制线程 本篇文章将介绍限制 Python 中的活动线程数。 Python 中的线程 Python 中的线程允许多个执行线程在单个进程中同时运行。 每个线程独立于其他线程运行,允许并发执行并提高性能。 线程对于执行受 I/O 限制或…...

创建web后端程序(servlet程序搭建)

目录 一、Servlet概述 二、创建servlet程序 1.创建类继承HttpServlet 2.重写HttpServlet类中 service、destroy、init方法 3.重新启动服务器 一、Servlet概述 Server Applet的简称,用Java编写的服务器端的程序。它运行在web服务器中,web服务器负责…...

【章节1】git commit规范 + husky + lint-staged实现commit的时候格式化代码

创建项目我们不多说,可以选择默认的,也可以用你们现有的项目。注意章节1和章节2请一起看! 章节1: commit规范 husky lint-staged格式化代码 章节2: husky 检测是否有未解决的冲突 预检查debugger 自动检查是否符合commit规范 前言&#x…...

【入门】拐角III

【入门】拐角III Description 输入整数N&#xff0c;输出相应方阵。 Input 一个整数N。&#xff08; 0 < n < 10 ) Output 一个方阵&#xff0c;每个数字的场宽为3。 Sample Input 1 5 Sample Output 1 5 5 5 5 55 4 4 4 45 4 3 3 35 4 3 2 25 4…...

如何使用 Fail2ban 防止对 Linux 的暴力攻击?

在当今数字化世界中&#xff0c;网络安全成为了一个极其重要的话题。Linux 作为一种广泛使用的操作系统&#xff0c;也面临着各种网络攻击的风险&#xff0c;包括暴力攻击、密码破解和恶意登录等。为了保护 Linux 系统的安全&#xff0c;我们可以使用 Fail2ban 这样的工具来防止…...

2023年,真的别裸辞....

作为IT行业的大热岗位——软件测试&#xff0c;只要你付出了&#xff0c;就会有回报。说它作为IT热门岗位之一是完全不虚的。可能很多人回说软件测试是吃青春饭的&#xff0c;但放眼望去&#xff0c;哪个工作不是这样的呢&#xff1f;会有哪家公司愿意养一些闲人呢&#xff1f;…...

规则引擎架构-基于easy-rules

目录 概念理解实例和编码抽象出2条规则简单的规则引擎事实1的处理事实2的处理 easy-rules 规则的抽象和执行事实描述规则的抽象默认的规则 动态代理执行规则和动作规则的执行&#xff1a;org.jeasy.rules.core.DefaultRulesEngine#doFirepublic class RuleProxy implements Inv…...

【数据结构】第七周

目录 稀疏矩阵快速转置 三元组的矩阵加法 九宫格数独游戏 数组主元素 螺旋数字矩阵 蛇形矩阵 数组循环右移K位 稀疏矩阵快速转置 【问题描述】 稀疏矩阵的存储不宜用二维数组存储每个元素&#xff0c;那样的话会浪费很多的存储空间。所以可以使用一个一维数组存…...

人体三维重构论文集合:awesome 3d human reconstruction

A curated list of related resources for 3d human reconstruction. Your contributions are welcome! Contents papers AIGCnerf or pifugeo fusionphoto3D human whole body3D human...

揭秘Redis持久化原理,探索fork与Copy-on-Write的魔法!

大家好&#xff0c;我是小米&#xff0c;今天我将和大家一起探索Redis持久化原理中的两个关键概念&#xff1a;fork和Copy-on-Write。这两个概念对于理解Redis的数据持久化机制至关重要。让我们一起来揭开这些技术的神秘面纱吧&#xff01; Redis持久化简介 在开始之前&#…...

应届生如何提高职场竞争能力

摘要&#xff1a; 应届生面对竞争激烈的职场&#xff0c;需要不断提高自身的职业素养和竞争能力&#xff0c;才能在激烈的竞争中脱颖而出。本文从积极心态的培养、专业知识的优化、职业规划的制定、团队协作的加强和自我拓展的开展五个方面&#xff0c;提出了提高应届生职场竞争…...

ISIS 实验

(1)拓扑图 2&#xff09;需求&#xff1a; -实现PC1和PC2的通信 3&#xff09;配置步骤&#xff1a; -配置接口IP地址 -开启ISIS---类似于在OSPF中创建进程 -配置NET地址---类似于在OSPF中创建区域&#xff0c;指定Router-id -在接口上启用ISIS--类似于在OSPFv2中用ne…...

国产系统:麒麟之人大金仓数据库部署

一、基本信息和资源 1.1 查看服务器信息 [root7PGxjKPL4 ~]# cat /etc/*release Kylin Linux Advanced Server release V10 (Sword) DISTRIB_IDKylin DISTRIB_RELEASEV10 DISTRIB_CODENAMEjuniper DISTRIB_DESCRIPTION"Kylin V10" DISTRIB_KYLIN_RELEASEV10 DISTRI…...

flink1.17.0 集成kafka,并且计算

前言 flink是实时计算的重要集成组件&#xff0c;这里演示如何集成&#xff0c;并且使用一个小例子。例子是kafka输入消息&#xff0c;用逗号隔开&#xff0c;统计每个相同单词出现的次数&#xff0c;这么一个功能。 一、kafka环境准备 1.1 启动kafka 这里我使用的kafka版本…...

【华为OD机试】数组组成的最小数字【2023 B卷|100分】

【华为OD机试】-真题 !!点这里!! 【华为OD机试】真题考点分类 !!点这里 !! 题目描述: 给定一个整型数组,请从该数组中选择3个元素组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述: 一行用半角逗号分割的字符串记录的整型数…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...