Řešení geometrických vazeb - Geometric constraint solving

Řešení geometrických vazeb je omezení spokojenosti v výpočetní geometrie nastavení, které má primární aplikace v počítačem podporovaný design.[1] Problém, který má být vyřešen, se skládá z dané sady geometrických prvků a popisu geometrických prvků omezení mezi prvky, které mohou být neparametrické (tečnost, horizontálnost, souosost atd.) nebo parametrické (jako vzdálenost, úhel, poloměr). Cílem je najít polohy geometrických prvků v 2D nebo 3D prostoru, které splňují daná omezení,[2] což se provádí vyhrazenými softwarovými komponentami zvanými řešitelé geometrických omezení.

Řešení geometrických omezení se stalo nedílnou součástí CAD systémů v 80. letech, kdy Pro / Engineer poprvé představil nový koncept konceptu parametrického modelování založeného na vlastnostech.[3][4]

Existují další problémy řešení geometrických vazeb, které souvisejí se sadami geometrických prvků a vazeb: dynamický pohyb daných prvků při zachování všech omezení,[5] detekce příliš a příliš omezených sad a podmnožin,[6][7] automatické omezení nedostatečně omezených problémů atd.

Metody

Obecné schéma řešení geometrických omezení sestává z modelování sady geometrických prvků a omezení pomocí systému rovnic a následného řešení tohoto systému nelineárním algebraickým řešičem. Kvůli výkonu, řada techniky rozkladu lze použít ke zmenšení velikosti množiny rovnic:[8] algoritmy plánování dekompozice a rekombinace,[9][10] rozklad stromů,[11] Rozklad C-stromu,[12] redukce grafu,[13] re-parametrizace a redukce,[14] výpočet základních obvodů,[15] struktura těla a těla,[16] nebo metoda konfigurace svědka.[17]

Některé další metody a přístupy zahrnují analýzu stupňů volnosti,[18][19] symbolické výpočty,[20] výpočty založené na pravidlech,[21] programování omezení a šíření omezení,[21][22] a genetické algoritmy.[23]

Systémy nelineárních rovnic jsou většinou řešeny iteračními metodami, které řeší lineární problém při každé iteraci, nejoblíbenějším příkladem je Newton-Raphsonova metoda.[21]

Aplikace

Řešení geometrických omezení má aplikace v široké škále oborů, jako je počítačový design, strojírenství, inverzní kinematika a robotika,[24] architektura a stavebnictví, molekulární chemie,[25] a prokazování geometrické věty. Primární oblastí aplikace je návrh podporovaný počítačem, kde se řešení geometrických omezení používá jak v parametrickém modelování založeném na historii, tak v variačním přímém modelování.[26]

Softwarové implementace

Seznam řešitelů geometrických omezení obsahuje alespoň

Reference

  1. ^ Roller, editoval Beat Brüderlin, Dieter (1998). Řešení geometrických vazeb a aplikace. Berlin, Heidelberg: Springer Berlin Heidelberg. s. 3–23. ISBN  978-3-642-58898-3.CS1 maint: další text: seznam autorů (odkaz)
  2. ^ Christoph M. Hoffmann; Pamela J. Vermeer. Řešení geometrických vazeb v R2 a R3. doi:10.1142/9789812831699_0008. S2CID  18272588.
  3. ^ Robert Joan-Arinyo. Základy řešení geometrických vazeb. CiteSeerX  10.1.1.331.9554.
  4. ^ R. Anderl; R. Mendgen (1996). "Modelování s omezeními: teoretický základ a aplikace". Počítačem podporovaný design. 28 (3): 155–168. doi:10.1016/0010-4485(95)00023-2.
  5. ^ Marc Freixas; Robert Joan-Arinyo; Antoni Soto-Riera (2010). "Dynamický geometrický systém založený na omezeních". Počítačem podporovaný design. 42 (2): 151–161. doi:10.1016 / j.cad.2009.02.016.
  6. ^ Rossignac, Jaroslaw; SIGGRAPH, Joshua Turner, redaktoři; sponzorované ACM (1991). Sborník: Symposium on Solid Modeling Foundations and CAD / CAM Applications, Radisson Plaza Hotel, Austin, Texas, 5-7 June, 1991. New York: Sdružení pro výpočetní techniku. ISBN  978-0-89791-427-7.
  7. ^ Simon E.B. Thierry; Pascal Schreck; Dominique Michelucci; Christoph Fünfzig; Jean-David Génevaux (2011). „Rozšíření metody svědka pro charakterizaci nedostatečně, příliš a dobře omezených systémů geometrických omezení“ (PDF). Počítačem podporovaný design. 43 (10): 1234–1249. doi:10.1016 / j.cad.2011.06.018.
  8. ^ Pascal Mathis; Simon E. B. Thierry (2010). „Formalizace systémů geometrických vazeb a jejich rozklad“. Formální aspekty práce na počítači. 22 (2): 129–151. doi:10.1007 / s00165-009-0117-8.
  9. ^ Christoph M. Hoffman; Andrew Lomonosov; Meera Sitharam (2001). "Plány rozkladu pro systémy geometrických vazeb, část I: Měření výkonu pro CAD". Journal of Symbolic Computation. 31 (4): 367–408. doi:10.1006 / jsco.2000.0402.
  10. ^ Christoph M. Hoffman; Andrew Lomonosov; Meera Sitharam (2001). "Plány rozkladu pro problémy s geometrickými omezeními, část II: Nové algoritmy". Journal of Symbolic Computation. 31 (4): 409–427. doi:10.1006 / jsco.2000.0403.
  11. ^ Marta Hidalgoa; Robert Joan-Arinyo (2015). „h-graphs: a new representation for tree decompositions of graphs“ (PDF). Počítačem podporovaný design. 67-68: 38–47. doi:10.1016 / j.cad.2015.05.003. hdl:2117/78683.
  12. ^ Xiao-Shan Gao; Qiang Lin; Gui-Fang Zhang (2006). „Algoritmus rozkladu C-stromu pro řešení 2D a 3D geometrických omezení“ (PDF). Počítačem podporovaný design. 38: 1–13. doi:10.1016 / j.cad.2005.03.002.
  13. ^ Samy Ait-Aoudia; Sebti Foufou (2010). "Řešič 2D geometrických omezení pomocí metody redukce grafu". Pokroky v inženýrském softwaru. 41 (10–11): 1187–1194. doi:10.1016 / j.advengsoft.2010.07.008.
  14. ^ Hichem Barki; Lincong Fang; Dominique Michelucci; Sebti Foufou (2016). „Opětovná parametrizace snižuje neredukovatelné systémy geometrických omezení“ (PDF). Počítačem podporovaný design. 70: 182–192. doi:10.1016 / j.cad.2015.07.011.
  15. ^ R. Joan-Arinyo; M.Tarrés-Puertas; S.Vila-Marta (2014). "Rozklad grafů geometrických omezení na základě výpočtu základních obvodů. Správnost a složitost". Počítačem podporovaný design. 52: 1–16. doi:10.1016 / j.cad.2014.02.006.
  16. ^ Kirk Haller; Audrey Lee-St.John; Meera Sitharam; Ileana Streinu; Neil White (2012). "Systémy geometrických vazeb tělo-a-kad". Výpočetní geometrie. 45 (8): 385–405. arXiv:1006.1126. doi:10.1016 / j.comgeo.2010.06.003.
  17. ^ Dominique Michelucci; Sebti Foufou (2006). Msgstr "Řešení geometrických omezení: metoda konfigurace svědků". Počítačem podporovaný design. 38 (4): 284–299. CiteSeerX  10.1.1.579.2143. doi:10.1016 / j.cad.2006.01.005.
  18. ^ Kramer, Glenn A. (1992). Řešení systémů geometrických vazeb: případová studie v kinematice (1: upplagan, ed.). Cambridge, Massachusetts: MIT Press. ISBN  9780262111645.
  19. ^ Xiaobo Peng; Kunwoo Lee; Liping Chen (2006). "Řešič geometrických omezení pro modelování 3D sestavy". International Journal of Advanced Manufacturing Technology. 28 (5–6): 561–570. doi:10.1007 / s00170-004-2391-1.
  20. ^ Xiao-Shan Gao; Shang-Ching Chou (1998). Řešení systémů geometrických vazeb II. Symbolický přístup a rozhodnutí o konstrukci Rc. doi:10.1016 / s0010-4485 (97) 00055-9. S2CID  775489.
  21. ^ A b C William Bouma; Ioannis Fudos; Christoph M. Hoffmann; Jiazhen Cai; Robert Paige (1993). Řešič geometrických vazeb.
  22. ^ Michela Farenzena; Andrea Fusiello (2009). "Stabilizace 3D modelování s šířením geometrických omezení". Počítačové vidění a porozumění obrazu. 113 (11): 1147–1157. doi:10.1016 / j.cviu.2009.05.004.
  23. ^ R. Joan-Arinyo; M.V. Luzón; A. Soto (2002). Paralelní řešení problémů z přírody - PPSN VII. Přednášky z informatiky. 2439. 759–768. doi:10.1007/3-540-45712-7_73. ISBN  978-3-540-44139-7.
  24. ^ "Řešitel geometrických omezení".
  25. ^ Rémi Imbach; Pascal Schreck; Pascal Mathis (2014). "Vedení metody pokračování pomocí geometrie pro řešení geometrických omezení". Počítačem podporovaný design. 46: 138–147. doi:10.1016 / j.cad.2013.08.026.
  26. ^ Dmitrij Ushakov (2008). Variační přímé modelování: Jak zachovat záměr návrhu v CAD bez historie (PDF).
  27. ^ „Správce 2D rozměrových omezení (D-Cubed 2D DCM)“.
  28. ^ „Zákazníci ve tvaru D“.
  29. ^ „Technologie komponent Bricsys pro správu omezení ve 2D / 3D“.
  30. ^ „Cimatron představí nový simulátor pohybu s technologií LEDAS LGS 3D“.
  31. ^ „Exkluzivní otázky a odpovědi: Co to znamená, když Bricsys koupil IP od společnosti Ledas“.
  32. ^ „Řešič C3D“.
  33. ^ „C3D Toolkit“.
  34. ^ „Stránka projektu GeoSolver“.