CGAL CGAL::Polygon_mesh_processing::self_intersections解析

CGAL::Polygon_mesh_processing::self_intersections 是用于检测多边形网格(Polygon Mesh)中的自相交的函数。自相交是指网格中的某些面(例如三角形)与同一网格中的其他面交叉的情况。这种情况通常是不期望的,因为它会导致网格的不一致性和潜在的几何错误。

    std::vector<std::pair<Mesh::face_index, Mesh::face_index>> self_intersections;CGAL::Polygon_mesh_processing::self_intersections(mesh,std::back_inserter(self_intersections));

关键代码:


// Checks for 'real' intersections, i.e. not simply a shared vertex or edge
template <class GT, class TM, class VPM>
bool do_faces_intersect(typename Triangle_mesh_and_triangle_soup_wrapper<TM>::face_descriptor fh,typename Triangle_mesh_and_triangle_soup_wrapper<TM>::face_descriptor fg,const TM& tmesh,const VPM vpmap,const typename GT::Construct_segment_3& construct_segment,const typename GT::Construct_triangle_3& construct_triangle,const typename GT::Do_intersect_3& do_intersect)
{typedef Triangle_mesh_and_triangle_soup_wrapper<TM>       Wrapper;typedef typename Wrapper::vertex_descriptor     vertex_descriptor;typedef typename GT::Segment_3                            Segment;typedef typename GT::Triangle_3                          Triangle;std::array<vertex_descriptor, 3> hv, gv;Wrapper::get_face_vertices(fh, hv, tmesh);Wrapper::get_face_vertices(fg, gv, tmesh);// check for shared edgestd::array<vertex_descriptor, 4> verts;if (Wrapper::faces_have_a_shared_edge(fh, fg, verts, tmesh)){if (verts[2]==verts[3]) return false; // only for a soup of triangles// there is an intersection if the four points are coplanar and the triangles overlapif(CGAL::coplanar(get(vpmap, verts[0]),get(vpmap, verts[1]),get(vpmap, verts[2]),get(vpmap, verts[3])) &&CGAL::coplanar_orientation(get(vpmap, verts[0]),get(vpmap, verts[1]),get(vpmap, verts[2]),get(vpmap, verts[3]))== CGAL::POSITIVE){return true;}else{// there is a shared edge but no intersectionreturn false;}}// check for shared vertex --> maybe intersection, maybe notint i(0), j(0);bool shared = false;for(; i<3 && (! shared); ++i){for(j=0; j<3 && (! shared); ++j){if(hv[i] == gv[j]){shared = true;break;}}if(shared)break;}if(shared){// found shared vertex:CGAL_assertion(hv[i] == gv[j]);// geometric check if the opposite segments intersect the trianglesconst Triangle t1 = construct_triangle(get(vpmap, hv[0]), get(vpmap, hv[1]), get(vpmap, hv[2]));const Triangle t2 = construct_triangle(get(vpmap, gv[0]), get(vpmap, gv[1]), get(vpmap, gv[2]));const Segment s1 = construct_segment(get(vpmap, hv[(i+1)%3]), get(vpmap, hv[(i+2)%3]));const Segment s2 = construct_segment(get(vpmap, gv[(j+1)%3]), get(vpmap, gv[(j+2)%3]));if(do_intersect(t1, s2))return true;else if(do_intersect(t2, s1))return true;return false;}// check for geometric intersectionconst Triangle th = construct_triangle(get(vpmap, hv[0]), get(vpmap, hv[1]), get(vpmap, hv[2]));const Triangle tg = construct_triangle(get(vpmap, gv[0]), get(vpmap, gv[1]), get(vpmap, gv[2]));if(do_intersect(th, tg))return true;return false;
}

解析:

1.初步筛选

将每个三角形的Bbox计算出来,再调用CGAL::box_self_intersection_d,使用分段树算法,快速筛选两两相交的Bbox对,此时得到的三角形对有可能相交,有可能只是相邻但不相交

//self_intersections_impltypedef internal::Strict_intersect_faces<Box, TM, VPM, GT, FacePairOutputIterator> Intersecting_faces_filter;Intersecting_faces_filter intersect_faces(tmesh, vpmap, gt, out);//省略......CGAL::box_self_intersection_d<CGAL::Sequential_tag>(box_ptr.begin(), box_ptr.end(), intersect_faces, cutoff);

2.精确判断

当检测到两个Bbox相交,box_self_intersection_d函数会调用函数对象(第三个参数Intersecting_faces_filter)的成员 void operator()(const Box* b, const Box* c)进一步判断

template <class Box, class TM, class VPM, class GT,class OutputIterator>
struct Strict_intersect_faces // "strict" as in "not sharing a subface"
{//省略.......void operator()(const Box* b, const Box* c) const{if(do_faces_intersect<GT>(b->info(), c->info(), m_tmesh, m_vpmap, m_construct_segment,         m_construct_triangle, m_do_intersect))*m_iterator++ = std::make_pair(b->info(), c->info());}
};

do_faces_intersect的流程分三种情况,即有公共边,公共点的,没有公共边和公共顶点。

  • ① t1和t2有公共边

1.若t1和t2不共面则不相交

2.若t1和t2共面,则判断v2是否在v0v1左边,若在左边则t1和 t2相交,否则不相交

  • ② t1和t2有公共的顶点

1.判断边s1和三角形t2是否相交

2.判断边s2和三角形t1是否相交

  • ③ t1和t2没有公共边和公共顶点

调用do_intersect碰撞检测,判断是否相交

步骤②步骤③中,判断边与三角形相交、三角形与三角形相交具体看CGAL\Intersections_3里面的实现

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479211.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

⭐ Unity 资源管理解决方案:Addressable_ Demo演示

一、使用Addressable插件的好处&#xff1a; 1.自动管理依赖关系 2.方便资源卸载 3.自带整合好的资源管理界面 4.支持远程资源加载和热更新 二、使用步骤 安装组件 1.创建资源分组 2.将资源加入资源组 3.打包资源 4.加载资源 三种方式可以加载 using System.Collections…

Vue前端开发2.3.5 条件渲染指令

本文介绍了Vue中两种条件渲染指令&#xff1a;v-if和v-show。v-if通过布尔值控制元素的DOM树存在&#xff0c;适用于不频繁切换显示状态的场景&#xff1b;v-show则通过CSS的display属性控制显示&#xff0c;适合频繁切换。通过创建单文件组件示例&#xff0c;演示了如何使用这…

GitLab指定用户分配合并权限

进入项目 -》 Project Settings Repository -》展开 Protected branches -》 添加要保护的分支&#xff0c;设置角色 管理用户角色权限 查看到不同用户的角色&#xff0c;一般设置Developer只有Merger Request权限&#xff0c;Maintainer还有Merge审批权限 GitLab 中的权限…

计算机网络socket编程(5)_TCP网络编程实现echo_server

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 计算机网络socket编程(5)_TCP网络编程实现echo_server 收录于专栏【计算机网络】 本专栏旨在分享学习计算机网络的一点学习笔记&#xff0c;欢迎大家在评论区交…

C++ 二叉搜索树(Binary Search Tree, BST)深度解析与全面指南:从基础概念到高级应用、算法优化及实战案例

&#x1f31f;个人主页&#xff1a;落叶 &#x1f31f;当前专栏: C专栏 目录 ⼆叉搜索树的概念 ⼆叉搜索树的性能分析 ⼆叉搜索树的插⼊ ⼆叉搜索树的查找 二叉搜索树中序遍历 ⼆叉搜索树的删除 cur的左节点为空的情况 cur的右节点为空的情况 左&#xff0c;右节点都不为…

uniCloud云开发

uniCloud 是 DCloud 联合阿里云、腾讯云、支付宝云&#xff0c;为开发者提供的基于 serverless 模式和 js 编程的云开发平台。 普通云函数 callFuction方式云函数&#xff0c;也称之为普通云函数 uni-app的前端代码&#xff0c;不再执行uni.request联网&#xff0c;而是通过…

org.apache.log4j的日志记录级别和基础使用Demo

org.apache.log4j的日志记录级别和基础使用Demo&#xff0c;本次案例展示&#xff0c;使用是的maven项目&#xff0c;搭建的一个简单的爬虫案例。里面采用了大家熟悉的日志记录插件&#xff0c;log4j。来自apache公司的开源插件。 package com.qian.test;import org.apache.log…

day05(单片机高级)PCB基础

目录 PCB基础 什么是PCB&#xff1f;PCB的作用&#xff1f; PCB的制作过程 PCB板的层数 PCB设计软件 安装立创EDA PCB基础 什么是PCB&#xff1f;PCB的作用&#xff1f; PCB&#xff08;Printed Circuit Board&#xff09;&#xff0c;中文名称为印制电路板&#xff0c;又称印刷…

fastjson不出网打法—BCEL链

前言 众所周知fastjson公开的就三条链&#xff0c;一个是TemplatesImpl链&#xff0c;但是要求太苛刻了&#xff0c;JNDI的话需要服务器出网才行&#xff0c;BCEL链就是专门应对不出网的情况。 实验环境 fastjson1.2.4 jdk8u91 dbcp 9.0.20 什么是BCEL BCEL的全名应该是…

C#基础控制台程序

11.有一个54的矩阵&#xff0c;要求编程序求出其中值最大的那个元素的值&#xff0c;以及其所在的行号和列号。 12.从键盘输入一行字符&#xff0c;统计其中有多少个单词&#xff0c;单词之间用空格分隔开。 13.输入一个数&#xff0c;判断它是奇数还是偶数&#xff0c;如果…

深度学习干货总结(持续更新)

机器学习核心组件 可以用来学习的数据&#xff08;data&#xff09;&#xff1b; 如何转换数据的模型&#xff08;model&#xff09;&#xff1b; 一个目标函数&#xff08;objective function&#xff09;&#xff0c;用来量化模型的有效性&#xff1b; 调整模型参数以优化…

腾讯云OCR车牌识别实践:从图片上传到车牌识别

在当今智能化和自动化的浪潮中&#xff0c;车牌识别&#xff08;LPR&#xff09;技术已经广泛应用于交通管理、智能停车、自动收费等多个场景。腾讯云OCR车牌识别服务凭借其高效、精准的识别能力&#xff0c;为开发者提供了强大的技术支持。本文将介绍如何利用腾讯云OCR车牌识别…

如何制作项目网页

一、背景 许多论文里经常会有这样一句话Supplementary material can be found at https://hri-eu.github.io/Lami/&#xff0c;这个就是将论文中的内容或者补充视频放到一个网页上&#xff0c;以更好的展示他们的工作。因此&#xff0c;这里介绍下如何使用前人提供的模板制作我…

goframe开发一个企业网站 在vue-next-admin 显示验证码 19

index.go 文件中的代码&#xff0c;我将为该文件中的主要功能和方法添加注释&#xff0c;并生成一篇 Markdown 格式的文章。这将包括对每个函数的用途、输入参数和返回值的简要说明。 index.go 包和导入 package adminimport ("context""errors""gf…

Elasticsearch中的节点(比如共20个),其中的10个选了一个master,另外10个选了另一个master,怎么办?

大家好&#xff0c;我是锋哥。今天分享关于【Elasticsearch中的节点&#xff08;比如共20个&#xff09;&#xff0c;其中的10个选了一个master&#xff0c;另外10个选了另一个master&#xff0c;怎么办&#xff1f;】面试题。希望对大家有帮助&#xff1b; Elasticsearch中的节…

Scrapy图解工作流程-cnblog

1.1 介绍部分&#xff1a; 文字提到常用的Web框架有Django和Flask&#xff0c;接下来将学习一个全球范围内流行的爬虫框架Scrapy。 1.2 内容部分&#xff1a; Scrapy的概念、作用和工作流程 Scrapy的入门使用 Scrapy构造并发送请求 Scrapy模拟登陆 Scrapy管道的使用 Scrapy中…

SpringCloud入门实战-Nacos简介、安装、运行详解

❤️ 《SpringCloud入门实战系列》解锁SpringCloud主流组件入门应用及关键特性。带你了解SpringCloud主流组件,是如何一战解决微服务诸多难题的。项目demo&#xff1a;源码地址 ❤️ 作者&#xff1a;一只IT攻城狮。关注我&#xff0c;不迷路。 ❤️ 再小的收获x365天都会成就…

量子安全与经典密码学:一些现实方面的讨论

量子安全与经典密码学 背景&#xff1a;量子安全与经典密码学量子计算对传统密码学的威胁 安全性分析经典密码学的数学复杂性假设**量子密码学的物理不可克隆性假设** **性能与实现难度**后量子算法在经典计算机上的运行效率**量子通信设备的技术要求与成本** **可扩展性与适用…

Ubuntu20.04运行msckf_vio

文章目录 环境配置修改编译项目运行MSCKF_VIO运行 Launch 文件运行 rviz播放 ROSBAG 数据集 运行结果修改mskcf 保存轨迹EVO轨迹评价EVO轨迹评估流程实操先把euroc的真值转换为tum&#xff0c;保存为data.tum正式评估 报错1问题描述 报错2问题描述问题分析问题解决 参考 环境配…

vscode下面python调试报错ImportError: cannot import name ‘Literal‘ from ‘typing‘

1 问题描述 我在vscode下面编写python程序&#xff0c;这个程序是在一个英伟达anoconda环境下的项目。之前能运行能调试&#xff0c;最近发现只能运行ctlf5&#xff0c;但是使用f5进行调试时&#xff0c;报错“File “c:\Users\86137.vscode\extensions\ms-python.debugpy-202…