Решение геометрических ограничений - Geometric constraint solving

Решение геометрических ограничений является удовлетворение ограничений в вычислительная геометрия настройка, которая имеет основное применение в системы автоматизированного проектирования.[1] Решаемая задача состоит из заданного набора геометрических элементов и описания геометрических ограничения между элементами, которые могут быть непараметрическими (касание, горизонтальность, соосность и т. д.) или параметрическими (например, расстояние, угол, радиус). Цель состоит в том, чтобы найти положения геометрических элементов в 2D или 3D пространстве, которые удовлетворяют заданным ограничениям,[2] что выполняется специальными программными компонентами, называемыми решателями геометрических ограничений.

Решение геометрических ограничений стало неотъемлемой частью систем САПР в 80-х годах, когда Pro / Engineer впервые представил новую концепцию параметрического моделирования на основе элементов.[3][4]

Существуют дополнительные проблемы решения геометрических ограничений, которые связаны с наборами геометрических элементов и ограничений: динамическое перемещение заданных элементов с соблюдением всех ограничений,[5] обнаружение избыточных и недостаточно ограниченных множеств и подмножеств,[6][7] автоматическое ограничение задач с недостаточными ограничениями и т. д.

Методы

Общая схема решения геометрических ограничений состоит из моделирования набора геометрических элементов и ограничений с помощью системы уравнений, а затем решения этой системы с помощью нелинейного алгебраического решателя. Для повышения производительности ряд методы разложения можно использовать для уменьшения размера набора уравнений:[8] алгоритмы планирования декомпозиции-рекомбинации,[9][10] разложение дерева,[11] Разложение C-дерева,[12] редукция графика,[13] повторная параметризация и редукция,[14] вычисление фундаментальных схем,[15] кузовная конструкция,[16] или метод настройки свидетеля.[17]

Некоторые другие методы и подходы включают анализ степеней свободы,[18][19] символьные вычисления,[20] вычисления на основе правил,[21] программирование ограничений и распространение ограничений,[21][22] и генетические алгоритмы.[23]

Системы нелинейных уравнений в основном решаются итерационными методами, которые решают линейную задачу на каждой итерации, наиболее популярным примером является метод Ньютона-Рафсона.[21]

Приложения

Решение геометрических ограничений находит применение в самых разных областях, таких как автоматизированное проектирование, машиностроение, обратная кинематика и робототехника,[24] архитектура и строительство, молекулярная химия,[25] и геометрическое доказательство теорем. Основная область применения - это автоматизированное проектирование, в котором решение геометрических ограничений используется как в параметрическом моделировании на основе истории, так и в вариационном прямом моделировании.[26]

Программные реализации

Список решателей геометрических ограничений включает не менее

Рекомендации

  1. ^ Roller, под редакцией Бита Брюдерлина, Дитера (1998). Решение геометрических ограничений и приложения. Берлин, Гейдельберг: Springer Berlin Heidelberg. С. 3–23. ISBN  978-3-642-58898-3.CS1 maint: дополнительный текст: список авторов (связь)
  2. ^ Кристоф М. Хоффманн; Памела Дж. Вермеер. Решение геометрических ограничений в R2 и R3. Дои:10.1142/9789812831699_0008. S2CID  18272588.
  3. ^ Роберт Джоан-Ариньо. Основы решения геометрических зависимостей. CiteSeerX  10.1.1.331.9554.
  4. ^ Р. Андерл; Р. Мендген (1996). «Моделирование с ограничениями: теоретические основы и применение». Системы автоматизированного проектирования. 28 (3): 155–168. Дои:10.1016/0010-4485(95)00023-2.
  5. ^ Марк Фрейшас; Роберт Джоан-Ариньо; Антони Сото-Риера (2010). «Система динамической геометрии на основе ограничений». Системы автоматизированного проектирования. 42 (2): 151–161. Дои:10.1016 / j.cad.2009.02.016.
  6. ^ Россиньяк, Ярослав; SIGGRAPH, Джошуа Тернер, редакторы; спонсируется ACM (1991). Труды: Симпозиум по основам твердотельного моделирования и приложениям CAD / CAM, Radisson Plaza Hotel, Остин, Техас, 5-7 июня 1991 г.. Нью-Йорк: Ассоциация вычислительной техники. ISBN  978-0-89791-427-7.
  7. ^ Саймон Э. Б. Тьерри; Паскаль Шрек; Доминик Микелуччи; Кристоф Фюнфциг; Жан-Давид Женево (2011). «Расширения метода свидетелей для характеристики систем геометрических ограничений с недостаточными, избыточными и хорошими ограничениями» (PDF). Системы автоматизированного проектирования. 43 (10): 1234–1249. Дои:10.1016 / j.cad.2011.06.018.
  8. ^ Паскаль Матис; Саймон Э. Б. Тьерри (2010). «Формализация геометрических систем ограничений и их декомпозиция». Формальные аспекты вычислений. 22 (2): 129–151. Дои:10.1007 / s00165-009-0117-8.
  9. ^ Кристоф М. Хоффман; Андрей Ломоносов; Мира Ситхарам (2001). «Планы декомпозиции для геометрических систем ограничений, Часть I: Показатели производительности для САПР». Журнал символических вычислений. 31 (4): 367–408. Дои:10.1006 / jsco.2000.0402.
  10. ^ Кристоф М. Хоффман; Андрей Ломоносов; Мира Ситхарам (2001). «Планы декомпозиции для задач геометрической зависимости, часть II: новые алгоритмы». Журнал символических вычислений. 31 (4): 409–427. Дои:10.1006 / jsco.2000.0403.
  11. ^ Марта Идальгоа; Роберт Джоан-Ариньо (2015). «h-графы: новое представление древовидных разложений графов» (PDF). Системы автоматизированного проектирования. 67-68: 38–47. Дои:10.1016 / j.cad.2015.05.003. HDL:2117/78683.
  12. ^ Сяо-Шань Гао; Цян Линь; Гуй-Фан Чжан (2006). «Алгоритм декомпозиции C-дерева для решения геометрических ограничений 2D и 3D» (PDF). Системы автоматизированного проектирования. 38: 1–13. Дои:10.1016 / j.cad.2005.03.002.
  13. ^ Сами Айт-Аудиа; Себти Фуфу (2010). «Решатель 2D геометрических ограничений, использующий метод сокращения графа». Достижения в инженерном программном обеспечении. 41 (10–11): 1187–1194. Дои:10.1016 / j.advengsoft.2010.07.008.
  14. ^ Хичем Барки; Lincong Fang; Доминик Микелуччи; Себти Фуфу (2016). «Повторная параметризация уменьшает неприводимые геометрические системы ограничений» (PDF). Системы автоматизированного проектирования. 70: 182–192. Дои:10.1016 / j.cad.2015.07.011.
  15. ^ Р. Джоан-Ариньо; Г-н Таррес-Пуэртас; С. Вила-Марта (2014). «Декомпозиция геометрических графов ограничений на основе вычислений фундаментальных схем. Корректность и сложность». Системы автоматизированного проектирования. 52: 1–16. Дои:10.1016 / j.cad.2014.02.006.
  16. ^ Кирк Халлер; Одри Ли-Сент-Джон; Мира Ситхарам; Илеана Стрейну; Нил Уайт (2012). «Системы геометрических ограничений body-and-cad». Вычислительная геометрия. 45 (8): 385–405. arXiv:1006.1126. Дои:10.1016 / j.comgeo.2010.06.003.
  17. ^ Доминик Микелуччи; Себти Фуфу (2006). «Решение геометрических ограничений: метод конфигурации свидетеля». Системы автоматизированного проектирования. 38 (4): 284–299. CiteSeerX  10.1.1.579.2143. Дои:10.1016 / j.cad.2006.01.005.
  18. ^ Крамер, Гленн А. (1992). Решение геометрических систем ограничений: пример кинематики (1: Упплаган. Ред.). Кембридж, Массачусетс: MIT Press. ISBN  9780262111645.
  19. ^ Сяобо Пэн; Куну Ли; Липин Чен (2006). «Решатель геометрических ограничений для трехмерного моделирования сборок». Международный журнал передовых производственных технологий. 28 (5–6): 561–570. Дои:10.1007 / s00170-004-2391-1.
  20. ^ Сяо-Шань Гао; Шан-Чинг Чоу (1998). Решение геометрических систем ограничений II. Символический подход и решение Rc-конструктивности. Дои:10.1016 / с0010-4485 (97) 00055-9. S2CID  775489.
  21. ^ а б c Уильям Баума; Иоаннис Фудос; Кристоф М. Хоффманн; Цзячжэнь Цай; Роберт Пейдж (1993). Решатель геометрических ограничений.
  22. ^ Микела Фарензена; Андреа Фузиелло (2009). «Стабилизирующее 3D моделирование с распространением геометрических ограничений». Компьютерное зрение и понимание изображений. 113 (11): 1147–1157. Дои:10.1016 / j.cviu.2009.05.004.
  23. ^ Р. Джоан-Ариньо; М.В. Лусон; А. Сото (2002). Параллельное решение проблем с натуры - PPSN VII. Конспект лекций по информатике. 2439. С. 759–768. Дои:10.1007/3-540-45712-7_73. ISBN  978-3-540-44139-7.
  24. ^ "Решатель геометрических ограничений".
  25. ^ Реми Имбах; Паскаль Шрек; Паскаль Матис (2014). «Ведущий метод продолжения по геометрии для решения геометрических ограничений». Системы автоматизированного проектирования. 46: 138–147. Дои:10.1016 / j.cad.2013.08.026.
  26. ^ Дмитрий Ушаков (2008). Вариационное прямое моделирование: как сохранить конструктивный замысел в САПР без истории (PDF).
  27. ^ «Диспетчер ограничений 2D-размеров (D-Cubed 2D DCM)».
  28. ^ "Клиенты D-Cubed".
  29. ^ «Технология компонентов Bricsys для управления ограничениями в 2D / 3D».
  30. ^ «Cimatron представляет новый симулятор движения на базе LEDAS LGS 3D».
  31. ^ «Эксклюзивные вопросы и ответы: что это значит теперь, когда Bricsys купила IP у Ledas».
  32. ^ «C3D Solver».
  33. ^ «C3D Toolkit».
  34. ^ «Страница проекта GeoSolver».