明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 1053|回复: 7

[图形系统] 魔改系列-9该死的填充

[复制链接]
发表于 2024-8-21 17:33:06 | 显示全部楼层 |阅读模式
本帖最后由 你有种再说一遍 于 2024-9-3 20:29 编辑

# 捕捉点卡顿
cad现在采用了一种密集填充就不显示的策略.
系统变量hpmaxlines:默认值100000(十万).
其实挺傻的,
我们无论何时都要看到填充啊.
不然我怎么删掉密集填充呢?
不然我还以为没有填充再填充一次呢~

它卡顿是发生在画图期间,鼠标经过填充区域密集计算交点,端点...密集计算长期占用主线程,没有适当让主出线程进行渲染,系统计数器到期之后认为卡死.
而且我极怀疑,cad是通过遍历填充内部全部碎线求最近距离的图元,然后每次滑动一像素,就遍历获取交点,端点...它的填充结构连树或者网格都没有做,更不用说捕捉时机的优化了.

分析之后,我们知道了,不修改cad的捕捉,但是我们可以选择填充捕捉的时机,操控此变量进行忽略捕捉填充:(setvar 'OSNAPHATCH 0)

方案一:按键捕捉版
默认不捕捉填充,通过鼠标钩子触发,按ctrl才捕捉.可以制作命令组,只允许某几个命令这样做,例如move.
缺点是改变了用户习惯,按照"把用户当傻子"的惯例,此方案很快否掉了.

方案二:像素判断版
默认不捕捉填充,通过鼠标钩子触发,
判断命令期间才执行(通过doc命令执行前事件设置一个全局flag给它).
鼠标悬停0.1秒后触发任务,通过一个鼠标范围的矩形(50*50像素,再换算到cad坐标)递归获取鼠标所在四叉树节点得到填充.
计算填充的像素间距,15像素以外才设置捕捉.
这样令用户需要界面放大之后,才有填充捕捉,保证cad调用自己界面缓冲区时候能够不过密卡死.
鼠标快速划过(少于0.1秒),应该什么也不做才对.

这样每次执行命令中的鼠标移动,都有一个进入四叉树节点的2ms的消耗?
关键是鼠标移动的触发频率,如果鼠标DPI是400,并且它的刷新率是125Hz,那么每秒移动1英寸它可以检测到400*125=50000个点.
然后乘2ms...似乎是不可接受的...
降低触发四叉树获取还是很简单的,这里就不展开了.

为了尽可能加速.
1,计算填充像素的时候是不需要遍历填充内容的,我们假设填充总是均匀的.
采用面平均密度(填充密度/填充面积),然后每次缩放就是面平均密度*视口高度,就能得到大概的像素间距了.填充密度是lines要*2才是点数.
可惜大家总是不去想优化这些底层功能,玩lisp的也不知道什么时候才能玩到这里.很多人不在乎细节,但是细节多了之后会让人感觉很舒服.
2,不使用四叉树,采用填充的全局缓存,这就是为什么我强调并行遍历句柄篇章重要性.

方案三:填充名的黑白名单,
设定一些永久不捕捉的填充,可以和其他方案组合使用.


# 提取和替换填充
由于acad填充内置了三叶草版权.(中望cad案件)
http://www.jsgctxxh.com/110/33/6/news.html
https://tolmbpxs.com/redirect?from=nwoqp
所以你会发现填充充满bug,甚至天正没有对填充进行自定义图元(最新版本我就不知道了).

## 原点丢失
在写拉伸填充到时候就发现,依据旧填充创建新填充是外观不吻合的,因为旧填充原点只需要矩阵平移一下,原点信息就丢失了.
所以拉伸填充真的是靠新建关联边界,再移动边界夹点实现的,没法不断创建填充实现.这样给人一种很怪的感觉,明明创建的方案也应该是通的,怎么就无法实现呢?

dwg是保存了填充绘制信息,而不是原PAT,这样即使你没有这个PAT也能提取出来(为什么字体就没有这样做呢?)
使用源泉的提取填充,会发现提取的绘图信息和原PAT就是有点不一样.
名称,角度,比例,他们没啥特别问题,重点是重复单元不同,还丢了原点.
有英制和公制两个版本,所以就有同名同比例也是大小不一样的,不过并不关心这个话题,因为根本没有人用什么英制,而写替换的代码倒是要考虑怎么防止双标准融合.
因为制作填充没有强制规定归一化,享受没有归一化的自由,也同时承担了的代价.

cad保存填充的记录在哪里了呢?
或许可以在图元序列化和DXF上面找到...
你们找到可以告诉我[这是传送门](https://www.cnblogs.com/JJBox/p/11614714.html)

如果我们直接使用了提取出来的PAT,然后双击,确认,也会导致变化,因为它重复单元不一样了.
我都是自己再手造一个PAT,直到吻合,如果能提取填充直接就是一个外观吻合的就好了.或者提取之后遍历全图,使其吻合.

万一有个大傻春炸开了全图填充,然后你要复原,难道你会采取手工?虽然我的本意不是这个,但是还真的能实现此功能.

## 判断两个填充外观是否相同
### 概念
填充内部图元的两条碎直线组合成夹角,出现相同的概率总是很低的,那么两个不同的填充的碎直线组成相同三个角概率就更低了,多个三角形就能组合一个识别群.
如何获取这个三角形呢?
如果是随机三条线组成三角形,然后怎么找?随机找?
那,天知道什么时候能筛选出来哦,直接O(n^n)爆炸性时间复杂度.

根据前一篇MapReduce得知,其实有序数组降低极大的时间复杂度.
由于我并没有去提取过重复单元,只能假设最坏情况,就是无序,处理无序最好就是排序之后线性比较.
时间复杂度:O(快排nlogn+线性m).

### 执行步骤
比较两个填充的方式非常像比较两个图纸,所以,其实用图纸比较的方式也可以.不过填充有单元偏移问题,所以我没有采用.

填充理论上有单元序,没有单元内部序,我们要排单元内部序.
0,如果填充边界不闭合,出现"奇异"填充得先修复不闭合.
1,填充角度会影响获取单元序,所以填充角度要归0.
2,提取单元.
3,单元内部图元排序.
4,求夹角数组.

### 单元寻找
单元的边界是模糊的,它虽然是一个矩形,但是我用环形队列比喻:
[..3123123123..]怎么找到重复单元123呢?231,312似乎也可以.
原点丢失表示没有起点,这就是提取填充单元多解的地方,每个填充都能获取不同偏移的单元,我们只需要其中一个就好了.

[1231231231234...]
如果断言到中间觉得是单元,那岂不是bug了...
尤其是填充中间如果有个洞,那么信息是破缺的?
最坏情况,就是拉伸填充边界之后,必然产生重复单元,所以我觉得是存在元信息的.理论上应该有直接获取单元或者单元长度.

### 夹角数组
为什么需要夹角数组?因为夹角是天然的归一化,都在一个圆范围.如果是用点集,还得考虑比例,然后全部缩放一次,别忘了不同标准的同比例大小不一样,因此缩放比例是没有直接给你的,你只能通过包围盒边界猜...

根据填充单元,再前后前后求夹角,形成夹角数组[4,5,6..].
夹角数组就可以和其他填充比较(名称相同,比例相同也可能不一样).
同样的下一个同名填充也可能出现单元偏移,提取夹角数组是[6,7,8,4,5,4,5,6..].
两个夹角数组长度是一样的,我们先找到共同部分.
每个夹角数组都用min角作为起点,这样就是头对齐了,上SIMD一一比较.
多个min怎么办?记录索引进行跳跃比较咯.

### 不用夹角数组
通常填充是铺贴花纹瓷砖,如果提取的时候获取是最长线,那么重复单元就是瓷砖长条开始,更合理.
不过怎么比较呢,还是排序之后一一比较.

### 重建填充
通过上述,找到了重复单元,这样就不需要管原点丢失问题了,起铺点就是重复单元的左下角.

### 优化地方
一,提取单元的时候,求夹角的时候采取降低数值精度,例如定点数.
二,因为求夹角前后无关联,所以能用CPU的分支流水线+SIMD.
三,并行求全部的同名填充.

# 拉伸填充
我在IFox上面的拉伸填充已经算是标志性作品了,处理了各种事件联动,还通过标记来终止行为,实现一种状态机.
1,lisp在生成的边界之后,用户在双击填充无法删除边界,会导致弹出修改面板.
2,lisp做不到调用鼠标钩子,用户选择填充后生成关联边界,用户拉伸夹点,如果获取这个夹点呢?通过鼠标钩子一直记录鼠标给你,然后换算到dwg坐标,再比较是多段线哪个.

https://gitee.com/inspirefunctio ... 4%BA%8B%E4%BB%B6.cs

# 填充预览的卡顿
填充面板的预览图是每次都生成的,且没有进行缓存,所以会发现它太糟糕了,想预览一下看到一坨白的.
因此我们重建一个填充预览界面.它类似图库,因此可以复用技术.

1,提前生成全部填充预览的bimmap,可以利用遍历截图方式批量制作预览图,见此类上面的截图方式.
https://gitee.com/inspirefunctio ... yclip/BitmapTool.cs

2,填充过多,使用界面下拉栏虚拟化技术,并且根据排序后定位.

3,常用的填充在预览面板下方加一个LRU算法,放置最近使用的填充.

4,搜索文件,这只是锦上添花,根据排序后的设计,我们可以用二分法进行搜索文件.

(完)

评分

参与人数 1明经币 +1 收起 理由
tranque + 1 赞一个!

查看全部评分

发表于 2024-8-22 12:42:51 | 显示全部楼层
感觉路径阵列用 jig 模仿命令 S 拉伸的效果,也不好弄呀
 楼主| 发表于 2024-8-22 17:47:46 | 显示全部楼层
yupeng_dyp 发表于 2024-8-22 12:42
感觉路径阵列用 jig 模仿命令 S 拉伸的效果,也不好弄呀

很简单啊,不就是获取矩形内夹点,然后知道了可以移动的夹点集合,再向量化修改每个图元.
如果是阵列,就向量化添加和删除阵列图元..
发表于 2024-8-22 18:53:35 | 显示全部楼层
要开发一个cad啊?
发表于 2024-8-24 16:26:55 | 显示全部楼层
可惜论坛不支持markdown
发表于 2024-8-26 11:13:53 来自手机 | 显示全部楼层
支持打字多的文章。
发表于 2024-8-27 07:00:01 来自手机 | 显示全部楼层
支持打字多的文章,有质量有内涵,超出我的认知了
发表于 2024-9-3 14:11:25 | 显示全部楼层
说得真是详细,收藏
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-11-23 01:50 , Processed in 0.170689 second(s), 23 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表