一种快速收敛的自适应算法求解最小包围盒（OBB）

本文主要是介绍一种快速收敛的自适应算法求解最小包围盒（OBB），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一种快速收敛的自适应算法求解最小包围盒（OBB）
最小包围盒沿坐标轴向包围盒AABB（Axis-Aligned Bounding Boxes）算法简单，适用场合有限。沿任意方向的包围盒OBB（Oriented Bounding Boxes）适用面广，但大多算法效率不高，一方面是模型本身复杂导致，另一方面是精度越高、循环叠代次数沿指数增加而导致。博主几年前提出的一种求解OBB问题的自适应算法，并用UG NX二次开发Grip语言实现了此算法，经过测试，运算效率和精度都十分理想。
程序算法设计思路如下：
1. 利用最小距离RELDST/可间接计算某三垂直方向上的最小体积（如构造面法）
2. 遍历所有空间方向的体积，记录最小体积
3. 遍历的时候采取变步长法，以减少计算量
下载附件obb.grx,在UG NX中运行，按如下操作步骤可看到整个动态计算过程：
1. 新建一任意实体体素，如圆柱体，不失一般性，转动该体，在XYZ三方向使其与绝对坐标系成角度
2. Ctrl+G运行OBB.grx，选择该体测试

3. 运行结束后，Ctrl+F，使主窗口适合整个界面4. 保持3步中的界面，再运行OBB.grx，再次选择该体素（选择时不要缩小界面），即可看到构造面运动的轨迹

很多留言的朋友希望学习代码，很受感动！今天特意整理了一下手写的备注，分享如下（非科班专业程序猿，程序代码如有不足敬请谅解）-2020.4.25

$$ 
$$ FUNCTION : FIND THE MINIMUM BOX BY THREE TIMES LOOP
$$            X :  ALPAH  From 0 tO 90 degrees 
$$            Y :  ALPAH  From 0 TO 90 degrees 
$$            Z :  ALPAH  From 0 TO 90 degrees 
$$            The section of ZSY is one programe to adjust
$$            the begin point and end point automaticly.
$$            So, it is ZiShiYing.
$$
$$   AUTHOR : TANGXIAOLI
$$    DATE  : JULY 21, 2012
$$NUMBER/A(3),B(3),C(3),k(4),vol(2),AA(3),BB(3),CC(3)
NUMBER/ap,bt,gm,x,y,z
NUMBER/d1(7),d2(7),d3(7),d4(7),d5(7),d6(7),off(6)
ENTITY/PA,PB,PC,PO,PAm,PBm,PCm
ENTITY/OAB,OBC,OCA,OABm,OBCm,OCAm,OABp,OBCp,OCAp
ENTITY/ploff(6),L(12)
ENTITY/GRP(10)DATA/Cstp,20,Fstp,3i=0
j=0
t=0
dmax=5000
vol(1)=dmax**3back:
PARAM/'MVB',$'Coarse step',Cstp,$'Fine step',Fstp,Rsp
JUMP/back:,cancel:,ok:,,Rsp
ok:IFTHEN/Cstp<=0 OR Cstp>90 OR Fstp<=0 OR Fstp>Cstp
PRINT/' '
PRINT/' '
PRINT/'====================IMPORTANT NOTES======================='
PRINT/'Coarse step must be  >  0.000                 '
PRINT/'Coarse step must be  <=  90.000                '
PRINT/'  Fine step must be  > 0.000                 '
PRINT/'  Fine step must be  <= Coarse step'
PRINT/' '
PRINT/'If set a small value for coarse step, such less than 0.1,'
PRINT/'it takes a long time to run.'
PRINT/'If set a large value for fine step, such more than 30,'
PRINT/'the result is not so good.'
PRINT/'However, you need to balance the precision your want to get'
PRINT/'and performance of the computer!'
PRINT/' '
PRINT/'It is a test version for study only! All copyrights belong to tangxiaoli'
PRINT/'Any questions contact author tangxiaoli711@yahoo.com.cn'
MESSG/'Input Coarse/Fine step error, see info window'
JUMP/back:
ENDIFMASK/70L10:
IDENT/'select target object',GRP,CNT,count,resp
IFTHEN/count>1MESSG/'MVB test version, select the first object only.'JUMP/cnt:
ENDIF
JUMP/L10:,term:,,respcnt:
ag_stp=Cstp
ap_agb=0
ap_age=90
bt_agb=ap_agb
bt_age=ap_age
gm_agb=ap_agb
gm_age=ap_age
aag_stp=ag_stpZSY:DO/Lp1:,gm,gm_agb,gm_age,ag_stp
DO/Lp2:,bt,bt_agb,bt_age,ag_stp
DO/Lp3:,ap,ap_agb,ap_age,ag_stpk(1)=1-SINF(gm)*SINF(gm)*COSF(bt)*COSF(bt)
k(2)=SQRTF(k(1))
k(3)=SINF(gm)*SINF(bt)/COSF(gm)
k(4)=ap-ATANF(k(3))A(1)=k(2)*SINF(k(4))
A(2)=-k(2)*COSF(k(4))
A(3)=SINF(gm)*COSF(bt)
B(1)=COSF(ap)-(1-COSF(bt))*COSF(ap)
B(2)=SINF(ap)-(1-COSF(bt))*SINF(ap)
B(3)=SINF(bt)
C=CROSSF(A,B)
$$C=SCALVF(10,C)PA=POINT/A(1),A(2),A(3)
PB=POINT/B(1),B(2),B(3)
PC=POINT/C(1),C(2),C(3)
PO=POINT/0,0,0
PAm=POINT/-A(1),-A(2),-A(3)
PBm=POINT/-B(1),-B(2),-B(3)
PCm=POINT/-C(1),-C(2),-C(3)OAB=PLANE/PO,PA,PB
OBC=PLANE/PO,PB,PC
OCA=PLANE/PO,PC,PAOABp=PLANE/PARLEL,OAB,PC,dmax
OABm=PLANE/PARLEL,OAB,PCm,dmax
OBCp=PLANE/PARLEL,OBC,PA,dmax
OBCm=PLANE/PARLEL,OBC,PAm,dmax
OCAp=PLANE/PARLEL,OCA,PB,dmax
OCAm=PLANE/PARLEL,OCA,PBm,dmaxd1=RELDST/OCAm,GRP(1)
d2=RELDST/OCAp,GRP(1)
d3=RELDST/OBCm,GRP(1)
d4=RELDST/OBCp,GRP(1)
d5=RELDST/OABm,GRP(1)
d6=RELDST/OABp,GRP(1)x=2*dmax-d1(7)-d2(7)
y=2*dmax-d3(7)-d4(7)
z=2*dmax-d5(7)-d6(7)
vol(2)=x*y*z$$PRINT/'Point A: '+FSTRL(A(1))+' '+FSTRL(A(2))+' '+FSTRL(A(3))
$$PRINT/'Point B: '+FSTRL(B(1))+' '+FSTRL(B(2))+' '+FSTRL(B(3))
$$PRINT/'Point C: '+FSTRL(C(1))+' '+FSTRL(C(2))+' '+FSTRL(C(3))
$$PRINT/FSTRL(d1(7))+'   '+FSTRL(d2(7))
$$PRINT/FSTRL(d3(7))+'   '+FSTRL(d4(7))
$$PRINT/FSTRL(d5(7))+'   '+FSTRL(d6(7))IFTHEN/vol(2)<vol(1)
vol(1)=vol(2)
AA(1)=A(1)
AA(2)=A(2)
AA(3)=A(3)
BB(1)=B(1)
BB(2)=B(2)
BB(3)=B(3)
CC(1)=C(1)
CC(2)=C(2)
CC(3)=C(3)off(1)=d1(7)
off(2)=d2(7)
off(3)=d3(7)
off(4)=d4(7)
off(5)=d5(7)
off(6)=d6(7)xx=x
yy=y
zz=z
$$tt=tENDIFDELETE/PA,PB,PC,PAm,PBm,PCm,OAB,OBC,OCA
DELETE/OABp,OABm,OBCp,OBCm,OCAp,OCAmi=i+1
PRINT/'step : '+FSTRL(i)
Lp3:
$$j=j+1
$$PRINT/'bt --- '+FSTRL(j)
Lp2:
$$t=t+1
$$PRINT/'gm === '+FSTRL(t)
Lp1:IFTHEN/ag_stp>Fstp AND Fstp>0aap=ATANF(BB(2)/BB(1))-aag_stp
IFTHEN/aap<=0ap_agb=0ap_age=aag_stp
ELSEIFTHEN/(aap+2*aag_stp)>=90ap_agb=aapap_age=90ELSEap_agb=aapap_age=ap_agb+2*aag_stpENDIF
ENDIFbbt=ATANF(BB(3)/SQRTF(BB(1)**2+BB(2)**2))-aag_stp
IFTHEN/bbt<=0bt_agb=0bt_age=aag_stp
ELSEIFTHEN/(bbt+2*aag_stp)>=90bt_agb=bbtbt_age=90ELSEbt_agb=bbtbt_age=bt_agb+2*aag_stpENDIF
ENDIF$$===========
ggm=ASINF(AA(3)/COSF(bbt+aag_stp))-aag_stp
IFTHEN/ggm<=0gm_agb=0gm_age=aag_stp
ELSEIFTHEN/(ggm+2*aag_stp)>=90gm_agb=ggmgm_age=90ELSEgm_agb=ggmgm_age=gm_agb+2*aag_stpENDIF
ENDIF$$========Option Angle of gm=======
$$IFTHEN/tt<=0
$$  gm_agb=0
$$  gm_age=aag_stp
$$ELSE
$$  IFTHEN/((tt+1)*aag_stp)>=90
$$    gm_agb=tt*aag_stp
$$    gm_age=90
$$  ELSE
$$    gm_agb=(tt-1)*aag_stp
$$    gm_age=(tt+1)*aag_stp
$$  ENDIF
$$ENDIF
$$================================$$PRINT/'=========RUN ZSY=========='
PRINT/'----------'
$$PRINT/FSTRL(ag_stp)
$$PRINT/ap_agb
$$PRINT/ap_age
$$PRINT/bt_agb
$$PRINT/bt_age
$$PRINT/gm_agb
$$PRINT/gm_age
$$PRINT/'=========END ZSY=========='$$ag_stp=Fstp
ag_stp=ag_stp/2
aag_stp=ag_stpJUMP/ZSY:ENDIFPA=POINT/AA(1),AA(2),AA(3)
PB=POINT/BB(1),BB(2),BB(3)
PC=POINT/CC(1),CC(2),CC(3)
PAm=POINT/-AA(1),-AA(2),-AA(3)
PBm=POINT/-BB(1),-BB(2),-BB(3)
PCm=POINT/-CC(1),-CC(2),-CC(3)OAB=PLANE/PO,PA,PB
OBC=PLANE/PO,PB,PC
OCA=PLANE/PO,PC,PAOABp=PLANE/PARLEL,OAB,PC,dmax
OABm=PLANE/PARLEL,OAB,PCm,dmax
OBCp=PLANE/PARLEL,OBC,PA,dmax
OBCm=PLANE/PARLEL,OBC,PAm,dmax
OCAp=PLANE/PARLEL,OCA,PB,dmax
OCAm=PLANE/PARLEL,OCA,PBm,dmaxploff(1)=PLANE/PARLEL,OCAm,PO,off(1)
ploff(2)=PLANE/PARLEL,OCAp,PO,off(2)
ploff(3)=PLANE/PARLEL,OBCm,PO,off(3)
ploff(4)=PLANE/PARLEL,OBCp,PO,off(4)
ploff(5)=PLANE/PARLEL,OABm,PO,off(5)
ploff(6)=PLANE/PARLEL,OABp,PO,off(6)L(1)=INTSEC/ploff(1),WITH,ploff(3),ploff(5),PCm,ploff(6),PC
L(2)=INTSEC/ploff(1),WITH,ploff(4),ploff(5),PCm,ploff(6),PC
L(3)=INTSEC/ploff(1),WITH,ploff(5),ploff(4),PA,ploff(3),PAm
L(4)=INTSEC/ploff(1),WITH,ploff(6),ploff(4),PA,ploff(3),PAmL(5)=INTSEC/ploff(2),WITH,ploff(3),ploff(5),PCm,ploff(6),PC
L(6)=INTSEC/ploff(2),WITH,ploff(4),ploff(5),PCm,ploff(6),PC
L(7)=INTSEC/ploff(2),WITH,ploff(5),ploff(4),PA,ploff(3),PAm
L(8)=INTSEC/ploff(2),WITH,ploff(6),ploff(4),PA,ploff(3),PAmL(9)=INTSEC/ploff(6),WITH,ploff(3),ploff(1),PBm,ploff(2),PB
L(10)=INTSEC/ploff(6),WITH,ploff(4),ploff(1),PBm,ploff(2),PB
L(11)=INTSEC/ploff(5),WITH,ploff(3),ploff(1),PBm,ploff(2),PB
L(12)=INTSEC/ploff(5),WITH,ploff(4),ploff(1),PBm,ploff(2),PBDELETE/PA,PB,PC,PAm,PBm,PCm,OAB,OBC,OCA,ploff
$$DELETE/OABp,OABm,OBCp,OBCm,OCAp,OCAmPRINT/'============ OBB Copyrights ============'
PRINT/'=It is a test version for study only!'
PRINT/'=Any questions contact author'
PRINT/'=tangxiaoli711@yahoo.com.cn'
PRINT/'======================================='
PRINT/'Input Coarse step is : '+FSTRL(Cstp)
PRINT/'Input Fine step is   : '+FSTRL(Fstp)
PRINT/'The Minimum Volume Box is:'
PRINT/FSTRL(xx)+' x '+FSTRL(yy)+' x '+FSTRL(zz)+'='+FSTRL(vol(1))
Term:
HALT
Cancel:
HALT