橢球排列的完全分類及快速判定

2021-01-15 中國科學院數學與系統科學研究院

中國科學院數學與系統科學研究院賈曉紅副研究員與香港大學王文平教授、山東大學屠長河教授、法國國家信息與自動化研究所Bernard Mourrain教授合作的論文「Complete Classifications and Efficient Determination of Arrangements Formed by Two Ellipsoids」被計算機圖形學國際頂級期刊ACM Transactions on Graphics錄用。該工作完成了兩橢球在三維空間中所有排列方式的分類、窮舉、快速判定算法，及在連續運動及變形下橢球排列變化的連通圖。

 

 

幾何體的排列反映了幾何體的位置關係和對空間的劃分方式，廣泛應用於CAD/CAM、機器人、分子模擬、計算物理、雷射手術等領域，特別適用於碰撞檢測相關問題。由於真實世界物體的表面幾何通常很複雜，因此在碰撞檢測等相關幾何計算中常用簡單包圍體逼近真實物體，從而把問題降解為包圍體之間的計算。而橢球是具有簡單代數表示並能反映各向異性特徵的包圍體，比常用的球、有向長方體等包圍體在形體逼近方面更有優勢。圖二是橢球包圍體在圖形學、機器人、計算機遊戲中的示例。然而橢球相關的幾何計算和判定較為困難，該工作首次窮舉了兩個橢球排列在微分同胚下的所有情形，見圖一。

 


 在上述應用特別是碰撞檢測中，核心問題常是判定兩幾何體的相對位置關係。根據具體應用環境的不同，「位置關係」可有不同層次的劃分標準。例如，常見的碰撞檢測任務僅區別「分離、相交、包含」的簡單位置關係；其中，「相交」情形往往含有豐富的變化，因此可進一步對幾何體交線的拓撲及代數性質進行區別。然而，無論是「分離、相交、包含」還是「交線形態判定」，都僅反映幾何體之間的相互關係，忽略了它們各自的行為特性。在這兩種準則下，圖三(a)中的兩對橢球及(b)中的兩對橢球都不能得到區別。而在「排列」意義下，圖三(a)中，橢球「A包含B」與「B包含A」 被視為兩種不同的排列；(b)中，「A穿透B」與「B穿透A」被視為兩種不同的排列。因此，排列分析從對空間的劃分角度使每個物體各自的幾何特性得到區分，適用於幾何體發生相互穿透的環境，如機器人手臂的主被動防禦中，及分子生物學中分子之間發生相互作用或貫穿時。此外，該工作對排列等價類的劃分是在微分同胚意義下進行的，即橢球交線上奇點的存在及階數情況將影響等價類劃分。例如，圖四(a)與(b)分別給出了兩對不同的排列。

 

該工作同時證明了兩橢球的排列方式可由簡單代數序列快速判定。例如，圖四(a)中兩種排列的代數序列為<1|0|1|2|3>及<1|2|3|4|3>，(b)中兩種排列的代數序列為<1|2|3|2|3>及<1|2|1|2|3>。序列中的各個指標僅來自於一個單變元四次多項式實根分布情況、一個動4*4矩陣在相應區間上的正特徵根數量及約當塊排布情況。而這些指標均可由符號計算方式給出，無需真正計算實根、特徵根、約當塊的具體值。對於給定的兩橢球方程，對該代數序列的計算複雜度為O(1)。

 

該工作同時建立了所有排列的連通圖（圖一）。兩排列稱為連通的，是指當兩橢球在空間中進行連續運動及變形時，這兩種排列可不經第三種排列而相互轉化。連通圖的構建給出了在連續運動及變形下兩橢球排列的所有可能的變化方式，證明了幾何上排列的連通可由代數序列的連通給出，保證了幾何臨界情形下的判定算法的穩定性，也可輔助具體應用環境中對兩物體的走向進行快速預判。圖五給出了部分普通排列（低退化情形）的連通圖。

此前，該研究團隊在幾何形態的代數判定方面有多個合作成果，包括橢球連續碰撞檢測、二次曲面交線形態連續變化檢測、圓紋面的交線形態窮舉及判定、達布圓紋面形態窮舉等，被機器人、力學、機械工程、計算物理、建築學、分子生物、晶體學、計算機視覺、計算代數幾何等多個學科引用。

 

參考文獻：

[1] X. Jia, C. Tu, B. Mourrain and W. Wang. Complete classification and efficient determination of arrangements formed by two ellipsoids. To appear in ACM Transactions on Graphics, 2020.

[2] M. Zhao, X. Jia, C. Tu, B. Mourrain and W. Wang. Enumerating the Morphology of Non-Degenerate Darboux Cyclides. Vol. 75, Computer Aided Geometric Design, 2019.

[3] X. Jia, W. Wang, Y.-K. Choi, B. Mourrain and C. Tu.  Continuous Detection of the Variations of the Intersection Curve of Two Moving Quadrics in 3-Dimensional Projective Space. Journal of Symbolic Computation, Vol. 73, 221-243, 2016. 

[4] X. Jia, C. Tu and W. Wang. Topological Classifications of the Intersection Curves of Two Ring Tori. Computer Aided Geometric Design, Vol. 30, 181-198, 2013.

[5] X. Jia, Y.-K. Choi, B. Mourrain and W. Wang. An Algebraic Approach for Continuous Collision Detection for Ellipsoids. Computer Aided Geometric Design, Vol. 28, 164 - 176, 2011.

[6] Y.-K. Choi, J.-W. Chang, W. Wang, M.-S. Kim and G. Elber. Continuous Collision Detection for Ellipsoids. Vol. 15(2), p311-325, IEEE Transactions on Visualization and Computer Graphics, 2009

[7] Y.-K. Choi. Collision Detection for Ellipsoids and Other Quadrics. Ph.D. Thesis, the University of Hong Kong, 2008」.

[8] L. Lu, Yi-King. Choi, W. Wang and M.-S. Kim. Variational 3D shape segmentation for Bounding volume computation. Vol. 26(3), 329-338, Computer Graphics Forum (Eurographics), 2007.

[9] Y.-K. Choi, W. Wang, Y. Liu, and M.-S. Kim. 2006. Continuous Collision Detection for Two Moving Elliptic Disks. Vol.22(2), 213–224, IEEE Transactions on Robotics, 2006..


作者：賈曉紅副研究員，中國科學院數學與系統科學研究院


來源：中國科學院數學與系統科學研究院


長按二維碼—識別—關注

相關焦點

  • 中國科大首次實驗驗證量子導引橢球
    此時Alice所能導引Bob的量子態的集合在Bloch表示下將構成一個橢球。我們知道單比特量子態可以可視化地表示為Bloch球中的一個矢量，而量子導引橢球則為兩比特量子態提供了一個簡單的可視化表示方法。在多方共享量子態的情況下，量子導引橢球具有體積單配性。
  • GPS-RTK神器之一:橢球及其參數
    1、認識幾種橢球地球在測量中不是定義為圓球，而是一個橢球，有下列相關參數：a-橢球長軸b-橢球短軸c-a^2/bf-扁率：(a-b)/ae^2-第一偏心率平方e1^2-第二偏心率平方一般資料給定橢球長軸a和扁率f，可以通過如下公式計算其他參數
  • 北京事業單位數量關係:淺析排列組合基礎知識
    數量關係一直是考生較為頭疼的內容，其難度較高，尤其是排列組合問題。對於排列組合問題，其難度較高的主要原因是其基本知識獨立，研究的思路或者方法跟我們之前所學的有很大的差別，所以理解起來會有一定的難度，對於這一部分大家一定要學精學透，才可以真正解決相關類型的題目。一、含義排列組合，主要是用來計算方法數或情況數。簡單而言，就是計數。
  • 新化學物質持久性、生物累積性和毒性的判定及登記要求
    b）如快速生物降解試驗結果為可快速生物降解的，根據篩選標準，可判定不具有持久性；如快速生物降解試驗結果為不可快速生物降解的，可將該化學物質視為具有持久性，或者進一步提交強化快速生物降解試驗、固有生物降解試驗、水解、光解等更多篩選性降解數據。若前述任意一項測試結果顯示可降解，可判定不具有持久性。
  • 地面光伏電站組串接地故障的快速判定方法
    發表於：2018-06-11 10:27:52     作者：劉恆 鄭建飛 等來源：太陽能雜誌針對地面光伏電站常見的光伏組串接地故障，提出一種快速、實用的判定方法。地面光伏電站;組串接地故障;判定。組串接地故障的判定方法301判定故障光伏控制器在輻照度為1000 W/m2、環境溫度為25 ℃的條件下，用萬用表分別對已停運的逆變器直流配電櫃內各光伏控制器正、負極進線端的對地電壓進行測量。正常情況下，正、負極進線端對地電壓絕對值應在300～380 V 之間，並且測量過程中對地電壓會逐漸下降。
  • 國土資源部關於統一圖幅理論面積與圖斑橢球面積計算要求的通知
    各省、自治區、直轄市第二次土地調查領導小組辦公室，國土資源廳（國土環境資源廳、國土資源局、國土資源和房屋管理局、房屋土地資源管理局），解放軍土地管理局、新疆生產建設兵團國土資源局：中華會計網校　　面積計算是第二次土地調查的一項重要內容，國務院第二次全國土地調查領導小組辦公室組織有關專家，依據《第二次全國土地調查技術規程》，對圖幅理論面積與圖斑橢球面積計算公式進行了細化
  • 橢球？還是這樣的······
    如果後者是正確的，那麼我們的橢球將是三軸的。根據這一點，在我們的南極，伴隨著北極相同水平的更高地勢。這意味著北中緯度將被扁平化，而南中緯度將以類似的方式更加明顯。但其實關於地球真實形狀的有另一種爭議的理論，我們的星球更像是一個大地水準面。這種形式更多地用於科學測量。這種表示方式使用中等水位作為準確查明某個位置的垂直位置的主要方法。
  • 新東方在線教你重新認識排列組合
    所謂排列，是指從給定個數的元素中取出指定個數的元素進行排序，而組合則是從給定個數的元素中取出指定個數的元素，不考慮排序。因此，新東方在線老師提醒，同學們在判定一個問題是排列還是組合時，要重點分析元素組成有無順序性，有順序就是排列，無順序就是組合。　　因遺漏計算或重複計算而出錯。
  • GMAT數學:排列與組合的區別
    這裡要注意區分兩個原理，要做一件事，完成它若是有n類辦法，是分類問題，第一類中的方法都是獨立的，因此用加法原理;做一件事，需要分n個步驟，步與步之間是連續的，只有將分成的若干個互相聯繫的步驟，依次相繼完成，這件事才算完成，因此用乘法原理。　　這樣完成一件事的分「類」和「步」是有本質區別的，因此也將兩個原理區分開來。
  • 2021國家公務員考試行測數量關係備考技巧:排列組合分類分步如何...
    2021國家公務員考試行測數量關係備考技巧：排列組合分類分步如何區分和使用 2021 國家公務員考試是今年下半年最為重要的公職類考試， 不知道大家備考情況如何。
  • 多彩類金剛石薄膜,助力快速分類
    而當薄膜中氫元素含量增加時，薄膜會逐漸演變為-CHx結構主導的類高聚物碳膜（PLC），各項性能則會出現完全不同的情況。因此，DLC薄膜的分類以及分類標準的制定，直接影響了其在眾多領域的應用。而傳統的DLC薄膜分類方法通常需要根據DLC薄膜的微結構定量分析來完成。然而，這一方法需要基於大型同步輻射光源的X射線近邊吸收精細結構譜（NEXAFS）分析碳元素的成分和狀態；需要大型靜電加速器的盧瑟福背散射彈性反衝（RBS/ERDA）或者中子源等分析氫元素含量，執行起來非常困難。
  • 新分類理論:從根本上改善你的分類思想
    上述傳統的分類方法存在的問題是：沒有形成統一的分類理論，分類方法沒有統一的框架，難免讓人的分類思維浮於表層，抓不住分類的本質，對事物的分類往往也流於表面，人云亦云。02、新分類理論：分類維度公式正確而深刻的分類，本質上應該是由事物互斥的若干屬性的完全排列組合。麥肯錫MECE分析法所謂的「相互獨立，完全窮盡」，正是這個意思。
  • 如何快速了解排列組合經典模型基本公式及題型特點
    事業單位考試的行測中，有一類題型叫做排列組合，而在排列組合的應用中，有一些題型需要構造模型才能快速解題，否則難以下手。本文就排列組合常見的三種模型，環形排列、錯位重排、同素分堆給大家作簡單介紹。基本公式及題型特點1.環線排列與直線排列相比，環線上的排列問題沒有前後與首尾之分。任取一個元素作為隊首，環線排列問題便轉化為剩下的(n-1)個元素的直線排列問題。
  • 考研數學:10分鐘幫你拿下排列組合重難點問題!
    排列與組合的概念：1、排列數的概念：從n個不同元素中，任取m（m≤n）個元素有順序的排成一列，則所有不同的排列個數，稱為排列數。2、組合數的概念：從n個不同元素中，任取m（m≤n）個元素不計順序的組成一組，則所有不同的組合個數，稱為組合數。
  • 食品檢驗結果符合性判定注意事項解讀(下)
    繼上篇分析了食品檢驗結果符合性判定中樣品採集與保存、樣品製備、檢驗方法的採用、檢驗結果準確性保證、判定依據應用的合理性等注意事項，本篇繼續分析判定標準基本原則、食品分類、結果評估以及如何防控風險等。
  • 遊戲創新的一般方法論,本質就是排列組合?
    很多人都聽過「創新的本質就是排列組合」，但怎麼個排列組合法？用什麼材料來排列組合？這些材料又是如何產生的？這些問題是排列組合的前提，也就是創新的前提。創新必須有系統的方法，不能靠隨機的「靈感」，不然想不出來是不是就不做了？開始創新前必須要確定自己對要創新的領域有足夠的了解，即了解這個領域的基本原理、流程。
  • 2021國家公務員考試行測排列組合分類分步如何區分和使用
    在數量關係專項中，排列組合問題最基礎的就是兩個基本計數原理，而許多同學都知道分類相加，分步相乘，但是往往分不清什麼是分類什麼是分步。所以，今天我們就分類分步的區別來和大家分享一下經驗。能獨立完成這件事為分類，不能獨立完成這件事為分步。
  • 《重大火災隱患判定方法》
    《重大火災隱患判定方法》2009/1/8/08:30來源：慧聰消防網整理    【頒布機關】中華人民共和國公安部【頒布日期】2006-10-25【實施日期】2007-01-01【時效性】現行有效     重大火災隱患判定方法    Criterion for major fire potential        前言     本標準的4.2、4.3、4.6為強制性條文，其餘為推薦性條文。
  • 每天解決一個小問題之排列組合
    引言：(1)高考中對兩個計數原理、排列、組合的考查以基本概念、基本方法(如「在」「不在」問題、相鄰問題、相間問題)為主，主要涉及數字問題、樣品問題、幾何問題、塗色問題、選取問題等；對二項式定理的考查，主要是利用通項求展開式的特定項，利用二項式定理展開式的性質求有關係數問題．主要考查分類與整合思想、轉化與化歸思想、補集思想和邏輯思維能力．
  • 周冬雨排列上熱搜 一文看懂不同像素排列方式
    而像那些IPS、TN、Super AMOLED和PMOLED一類的屏幕則是基於這兩種材質的升級版技術，所以大家只需記住這點，就可以避免被複雜的屏幕分類搞暈了。身邊的朋友或許都聽到過這樣的話，「買手機當然要買OLED屏幕的手機，顏色鮮豔、手機輕薄，還有屏幕指紋識別，LCD屏幕慢慢被淘汰了。」其實這樣的問題已經說了多年，但首先我們要搞清楚LCD和OLED指的是什麼？