图学学报
圖學學報
도학학보
Journal of Graphics
2013年
4期
54-62
,共9页
几何计算%三角形相交%降维%几何奇异%计算坐标系
幾何計算%三角形相交%降維%幾何奇異%計算坐標繫
궤하계산%삼각형상교%강유%궤하기이%계산좌표계
geometric computing%triangles intersection%dimension reduction%geometric singularity%computational coordinates
重点考虑几何奇异问题,同时兼顾算法的效率.运用“分而治之”的方法从一维解得到二维解,进而得到三维解,将空间问题变为平面问题、线性问题.基于几何代数化依赖于坐标系,引入“计算坐标系”,简化了几何的表述与关系的类型,使“几何奇异”状态最后归结为平面上线段被三角形裁剪时的共点、共线问题,简单而明晰,从而可从理论上保证算法的鲁棒性,以平面处理的形式给出了两个空间三角形求交的完整解决方案.测试证明,几何关系、几何奇异类型与计算的简化足以弥补因“变换”而增加的额外开销.算法的速度也能达到实用要求——在笔记本电脑上也能达到每秒100万对三角形的相交计算.
重點攷慮幾何奇異問題,同時兼顧算法的效率.運用“分而治之”的方法從一維解得到二維解,進而得到三維解,將空間問題變為平麵問題、線性問題.基于幾何代數化依賴于坐標繫,引入“計算坐標繫”,簡化瞭幾何的錶述與關繫的類型,使“幾何奇異”狀態最後歸結為平麵上線段被三角形裁剪時的共點、共線問題,簡單而明晰,從而可從理論上保證算法的魯棒性,以平麵處理的形式給齣瞭兩箇空間三角形求交的完整解決方案.測試證明,幾何關繫、幾何奇異類型與計算的簡化足以瀰補因“變換”而增加的額外開銷.算法的速度也能達到實用要求——在筆記本電腦上也能達到每秒100萬對三角形的相交計算.
중점고필궤하기이문제,동시겸고산법적효솔.운용“분이치지”적방법종일유해득도이유해,진이득도삼유해,장공간문제변위평면문제、선성문제.기우궤하대수화의뢰우좌표계,인입“계산좌표계”,간화료궤하적표술여관계적류형,사“궤하기이”상태최후귀결위평면상선단피삼각형재전시적공점、공선문제,간단이명석,종이가종이론상보증산법적로봉성,이평면처리적형식급출료량개공간삼각형구교적완정해결방안.측시증명,궤하관계、궤하기이류형여계산적간화족이미보인“변환”이증가적액외개소.산법적속도야능체도실용요구——재필기본전뇌상야능체도매초100만대삼각형적상교계산.
