Методы определения и разрешения столкновений на полигональных моделях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Ермолин, Егор Николаевич

• Ермолин, Егор Николаевич
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Ермолин, Егор Николаевич

Перечень условных обозначений.

Введение.

Общая характеристика работы.

Содержание работы.

Глава 1 Обзор работ по моделированию движения твердых тел.

Постановка задачи.

Решение задачи с помощью ЭВМ.

Представление геометрии тел.

Обзор методов определения столкновений.

Обзор методов разрешения столкновений.

Обзор сопутствующих задач — расчет динамических свойств сетки, приближенная выпуклая декомпозиция.

Глава 2 Динамический модуль.

Глава 3 Определение столкновений.

Алгоритм GJK определения столкновений пары выпуклых тел.

Алгоритм ЕРА определения минимальной глубины проникновения и направления разрешения столкновений.

Нахождение дополнительных точек контакта.

Производительность алгоритма определения столкновений.

Оптимизация определения столкновений. Окружающие примитивы.

Глава 4 Разрешение столкновений.

Поддержка ограничений "кинематическая пара".

Учет силы трения.

Выбор метода определения столкновений.

Оптимизация метода разрешения столкновений.

Глава 5 Приближенная выпуклая декомпозиция.

Деление многограничного контура.

Деление двухграничного контура.

Упрощение однограничного контура.

Примеры работы приближенной выпуклой декомпозиции.

Введение диссертации (часть автореферата) на тему «Методы определения и разрешения столкновений на полигональных моделях»

Общая характеристика работы Актуальность работы.

Развитие ЭВМ и растущая доступность персональных компьютеров, игровых приставок и прочих мультимедийных устройств повлекло рост потребности в интерактивных приложениях, моделирующих виртуальную среду и позволяющих получить нужную информацию или ожидаемое поведение от некоторого виртуального объекта, обычно являющегося моделью реального объекта. Примерами могут послужить расчеты прочностных характеристик деталей, осуществляемые инженером в современной САПР; нахождение массы тела; моделирование движения автомобиля в игровом симуляторе.

Рассмотрим задачу моделирования на ЭВМ движения системы твердых недеформируемых тел в соответствии с законами механики. Ее самое распространенное применение проще всего описать с точки зрения конечного пользователя — взаимодействие в некотором виртуальном окружении с предметами и предметов друг с другом, при этом предметы должны двигаться натуральным, привычным образом и, отталкиваясь, не проникать внутрь друг друга. Более строгая формализация потребует разделения задачи на два основных этапа — определения столкновений и пересчета скоростей тел в результате удара. Второй этап все чаще называют разрешением столкновений (collision resolution). Помимо этого в реализациях обычно существует еще третий модуль, согласовывающий работу вышеупомянутых. Также он отвечает за пересчет положений тел, скоростей под действием внешних сил (например, силы тяжести) и осуществляет взаимодействие с конечнопользовательским приложением.

Алгоритмы определения столкновений зависят от представления геометрии объектов, но, как правило, укладываются в общую схему - попарно рассматривают тела на предмет столкновений, предлагают подход по быстрому отсечению заведомо непересекающихся пар тел, после чего позволяют локализовать информацию о контакте. В настоящее время в качестве определения столкновений используются алгоритмы, производные от GJK+EPA, которые работают только на выпуклых телах. Это, в свою очередь, обращает внимание на задачу декомпозиции геометрии на выпуклые части. Таким образом, текущий фронт задач включает в себя как определение столкновений, так и вспомогательные задачи вычислительной геометрии.

В настоящей работе упор был сделан на верный с точки зрения классической механики пересчет скоростей системы соударяющихся тел, при этом столкновения рассматриваются комплексно. От подхода требуется соблюдение законов сохранения импульса, момента импульса и, при определенных условиях, энергии. Также предложенный подход обладает функциональностью, свойственной геометрическим решателям — позволяет совместить пару тел и сохранить контакт (ограничение "кинематическая пара").

Таким образом, актуальной проблемой является развитие методов разрешения столкновений, гарантирующих реалистичное поведение объектов, и согласованных с этими методами алгоритмов определения столкновений.

Цель диссертационной работы: разработка и программная реализация алгоритмов определения и разрешения столкновений гранично заданных тел в соответствии с законами механики твердых тел.

Для достижения указанной цели были сформулированы и решены следующие задачи:

- реализация метода определения столкновений, нахождения главной точки и дополнительных точек контакта, направления разрешения для пары выпуклых двумерных тел;

- разработка и реализация метода приближенной декомпозиции невыпуклых двумерных тел на множество выпуклых тел;

- разработка и реализация трехмерного метода разрешения столкновений для системы тел без ограничений на представление геометрии, число тел и число точек столкновения;

- развитие метода для поддержки неупругих столкновений и ограничений типа "кинематическая пара";

- разработка динамического модуля, отвечающего за предварительную обработку геометрии и согласующего работу методов определения и разрешения столкновений, обновления трансформаций тел, действия внешних сил и пружин;

- проведение вычислительных экспериментов;

- проведение физического эксперимента с костями домино;

- создание программного средства Noir для визуализации.

Область исследования. Содержание диссертации соответствует специальности 05.13.18 "Математическое моделирование, численные методы и комплексы программ", области исследования - п. 1 "Разработка новых математических методов моделирования объектов и явлений, перечисленных в формуле специальности", и п. 9 " Разработка систем имитационного моделирования" Паспорта специальности.

Научная новизна работы заключается в следующем:

- предложен метод приближенной выпуклой декомпозиции двумерного многоугольника с внутренними границами;

- предложен метод разрешения столкновений, отвечающий законам механики твердых тел;

- предложено расширение метода, позволяющее задавать геометрические ограничения между телами.

Научная ценность диссертационной работы заключается в создании эффективных реализаций алгоритмов декомпозиции многограничного многоугольника, определения и разрешения столкновений, разработке динамического модуля, пригодного для использования в интерактивных приложениях виртуальной реальности. Основные свойства разработанных алгоритмов сформулированы и доказаны в виде теорем.

Достоверность полученных результатов подтверждается:

- тестированием отдельных процедур и классов программной реализации;

- численными экспериментами на модельных тестах, имеющих аналитические решения;

- сравнением с результатами работы алгоритмов, решающих аналогичные задачи, но неэффективных с вычислительной точки зрения;

- корректностью работы трехмерного разрешения столкновений на двумерной геометрии. Это, в том числе, проверялось путем задания произвольной пары ортогональных осей, определяющих плоскость моделирования;

- физическим экспериментом, заключающемся в измерении времени удара последней кости домино в цепочке и визуализации движения. Время, полученное с помощью расчетов, отличается в среднем на 20% от измеренного в реальном эксперименте, качественная картина движения костей воспроизведена достоверно.

Апробация работы. Основные научные результаты докладывались автором на международных конференциях isiCAD 2004 (Новосибирск, Россия, 2004), GraphiCon (Новосибирск, Россия, 2005), на конференции "Технологии Microsoft в теории и практике программирования" (Новосибирск, Россия, 2007), на семинаре "3D графика и геометрия, высокопроизводительные вычисления" (Новосибирск, Россия, 2008),), на выпускном семинаре ИСИ СО РАН (Новосибирск, Россия, 2010) под руководством д.ф.-м.н., профессора Марчука А.Г.

Личный вклад соискателя. Все выносимые на защиту результаты принадлежат лично автору. Представление результатов совместных исследований в диссертационной работе согласовано с соавторами. Личный вклад соискателя заключается в обсуждении постановок задач; разработке адекватных численных алгоритмов и методов решения; разработке, реализации и тестировании программ, проведении численных экспериментов и интерпретации результатов.

Структура и объем работы Диссертационная работа состоит из введения, шести глав, заключения и списка литературы. Общий объем работы - 155 страниц. Список литературы содержит 67 наименований. Работа включает 14 таблиц, 88 рисунков и графиков.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Ермолин, Егор Николаевич

Заключение

Разработан и реализован трехмерный алгоритм разрешения столкновений системы тел, основанный на обмене импульсами между телами. Направление импульса определяется как оптимальное направление раздвижения тел, величина импульса рассчитывается из системы линейных уравнений. Решение допускает варьирование столкновений от абсолютно неупругих до абсолютно упругих и отвечает законам сохранения энергии, импульса и момента импульса системы. Развитие подхода и введение временного шага моделирования позволяет естественным образом получить поддержку ограничений типа "соединение", обеспечивая совпадение координат выбранных пар точек на телах системы. Проведена оптимизация алгоритма, уменьшающая размер системы линейных уравнений.

Реализован двумерный метод определения столкновений для выпуклых сеток на основе GJK. Данный метод был выбран потому, что по эффективности не уступает подходу с иерархией ограничивающих примитивов, но позволяет для пары тел определять оптимальное направление разрешения столкновения, для которого глубина проникновения будет минимальной.

Для возможности работы с невыпуклыми телами предложен и реализован эффективный алгоритм приближенной выпуклой декомпозиции плоского многограничного контура, позволяющий получить покрытие фигуры, ограниченной исходным контуром, выпуклыми однограничными контурами. Введен параметр, позволяющий наглядным образом контролировать качество разбиения.

Разработана и реализована архитектура динамического модуля, позволяющая комбинировать двух- и трехмерные реализации описанных выше алгоритмов. Архитектура позволяет подменять модули определения и разрешения столкновений, работать с произвольной пользовательской геометрией. Динамический модуль оперирует фиксированным шагом по времени, на каждом шаге происходит обновление трансформаций тел; допускается действие внешних сил, что приводит к пересчету скоростей. На каждом шаге вызывается модуль определения столкновений, после чего обнаруженные точки взаимного проникновения тел и соединения передаются модулю разрешения столкновений. Динамический модуль поддерживает особый вид внешних сил, моделирующих работу линейных пружин.

Для визуальной демонстрации результатов было реализовано Win32-приложение на MFC и OpenGL.

Список литературы диссертационного исследования кандидат физико-математических наук Ермолин, Егор Николаевич, 2011 год

1. Ли К.: Основы САПР (CAD/CAM/CAE). // Питер, СПб 2004

2. Lombardo J.-C., Cani М.-Р, Neyret F.: Real-time Collision Detection for Virtual Surgery // Computer Animation May 1999

3. Lafleur В., Magnenat Thalmann N., Thalmann D.: Cloth Animation with Self-Collision Detection // IFIP Conference on Modeling in Computer Graphics, Springer, Tokyo, 1991 Tokyo, 1991,-pp. 179-187.

4. Sobottka G., Varnik E., Weber A.: Collision Detection in Densely Packed Fiber Assemblies with Application to Hair Modeling // Proceedings of CISST, June, 2005 pp. 244-250

5. Cohen J., Lin M., Manocha D., Ponamgi M.: Interactive and Exact Collision Detection for Large-Scale Environments. Technical Report TR94-005, University of North Carolina at Chapel Hill, March 1994.

6. Gottschalk S., Lin M.C., Manocha D.: OBBTree: a hierarchical structure for rapid interference detection. //ASM SIGGRAPH, 1996 pp. 171-180

7. O'Rourke J.: Finding minimal enclosing boxes // International Journal of Computational. Informatics Science, vol. 14 (3), 1985 pp. 183-199

8. Ермолин E., Богданов M., Кусков Р., Лыков К., Попова А.: Автоматическое определение минимальных габаритов деталей // САПР и Графика, Выпуск 12. Москва, 2007. - С. 80-81

9. Golshtein Е., Tretyakov N.: Modified Lagrangians and monotone maps in optimization. // New York: Wiley, 1996 p. 6

10. Klosowski J., Held M., Mitchell J.: Efficient collision detection using bounding volume hierarchies of k-DOPs. // IEEE Transactions on Visualization and Computer Graphics, 4(1), 1998 — pp. 21-36

11. Bradshav G., O'SuIlivan C.: Sphere-tree construction using dynamic medial axis approximation.// ACM SIGGRAPH, 2002 July, 2002, San Antonio, Texas- pp.22-40

12. Larsen E., Gottschalk S., Lin M.C., Manocha D.: Fast distance queries with rectangular swept sphere volumes // IEEE Conf., 2002, Vol.4 - pp. 37193726

13. Krishnan S., Patteka A., Lin M.: Spherical Shell: A Higher Order Bounding Volume for Fast Proximity Queries // Proceedings of 3rd International Workshop on Algorithmic Foundations of Robotics, 1998 pp. 177-190

14. Held M.: ERIT: A Collection of Efficient and Reliable Intersection Tests// Journal of Graphical Tools, volume 2 (4), 1997 pp. 25-44

15. Eberly D.: Intersection of a Sphere and a Cone // Technical Report, Magic Software, March 2002

16. Eberly D.: Intersection of Cylinders // Technical Report, Magic Software, November 2000.

17. Guibas L., Nguyen A., Zhang L.: Zonotopes as Bounding Volumes // Proceedings of 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, USA, 2003.

18. Fares C., Hamam Y. Collision detection for rigid bodies: a state of the art review // Graphicon 2005, Russia, Novosibirsk

19. Coeurjolly D., Hulin J., Sivignon I.: Finding a minimum medial axis of a discrete shape is NP-hard // Theoretical Computer Science, Vol. 406, Issue 12, 2008 pp. 72-79

20. Dey T., Zhao W.: Approximate medial axis as a voronoi subcomplex // Proceedings of the seventh ACM symposium on Solid modeling and applications, 2002 — pp. 356-366

21. Foskey M., Lin M., Manocha D.: Efficient computation of a simplified medial axis // Proceedings of the eighth ACM symposium on Solid modeling and applications, 2003 — pp. 96-107

22. Bradshaw G., O'Sullivan C.: Sphere-tree construction using dynamic medial axis approximation // Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, 2002 pp. 3340

23. Lin M.: Efficient collision detection for animation and robotics // PhD Thesis, University of California, Berceley, USA, 1993.

24. Mirtich B.: V-Clip: Fast and robust polyhedral collision detection // ACM Trans. Graph, Vol.17, N. 3., July, 1998 pp. 177-208

25. Cohen J., Lin M., Manocha D., Ponamgi M.: I-COLLIDE: an interactive and exact collision detection system for large-scale environments // Proceedings of the 1995 symposium on Interactive 3D graphics table of contents, 1995 pp. 189-196

26. Van Den Bergen G.: A Fast and Robust GJK Implementation for collision detection of convex objects // Journal of Graphics Tools, 1999, 4(2) pp. 7-25

27. Van Den Bergen G.: Proximity queries and penetration depth computation on 3D game objects // Proc. Game Developers Conf., 2001

28. Van den Bergen G.: Collision Detection in Interactive 3D Environments // Morgan Kaufmann Series, USA, 2004

29. Ericson C.: Real-time collision detection // Morgan Kaufmann, 2005

30. Barzel R., Barr A.: A Modeling System Based on Dynamic Constraints // Computer Graphics 22(4), 1994 pp. 179-188

31. Cremer J., Stewart J.: The Architecture of Newton a General purpose Dynamics Simulator // International Conference on Robotics and Automation, IEEE, 1989-pp. 1806-1811

32. Mirtich B., Canny J.: Impulse-based Simulation of Rigid Bodies // Proceedings of 1995 Symposium on Interactive 3D Graphics, 1995 pp. 181-ff

33. Raibert M., Hodgins J.: Animation of dynamic legged locomotion // Computer Graphics, SIGGRAPH Conference Proceedings, 1991, pp. 349-358

34. McKenna M., Zeltzer D.: Dynamic simulation of autonomous legged locomotion// Computer Graphics, SIGGRAPH Conference Proceedings, 1991, pp. 29-38

35. Moore M., Wilhelms J.: Collision detection and response for computer animation // Computer Graphics Proceedings, 1988, pp. 289-298

36. Hahn J.: Realistic animation of rigid bodies // Computer Graphics Proceedings, 1988, pp. 299-308

37. Яблонский А.: Курс теоретической механики. Часть II. Динамика // Издательство Высшая Школа, Москва, 1966

38. Gengsheng W.: Three-Dimensional Collision Modeling for Rigid Bodies and its Coupling with Fluid Flow Computation // Flow Science Technical Note 75, 2006

39. Giang Т., Bradshaw G., O'Sullivan C.: Complementarity Based Multiple Point Collision Resolution // Proc. Fourth Irish Workshop Computer Graphics, 2003, pp. 1-8

40. Baraff D.: Analytical methods for dynamic simulation of non-penetrating rigid bodies // Computer Graphics Proceedings, 1989, pp. 223-232

41. Baraff D: Fast contact force computation for nonpenetrating rigid bodies // Computer Graphics Proceedings, 1994, pp. 23-34

42. Ермолин E., Казаков А.: Импульсный метод одновременного разрешения столкновений твердых тел // "Сибирский Журнал Вычислительной Математики", Том 9. Новосибирск, 2006. - С. 253-262

43. Ермолин Е., Казаков A.: Impulse-based Simultaneous Resolution of Rigid Body Collisions // isiCAD 2004. Proceedings of the International Forum. -Novosibirsk, 2004. pp. 214-223

44. Ermolin E., Kazakov A.: Impulse-based Approach for Rigid Body Collisions Simultaneous Resolution // Graphicon 2005. Conference Proceedings. -Novosibirsk, 2005. pp. 58-62

45. Ермолин E., Казаков А.: Подход к моделированию механических систем твердых тел // Препринт 10. ЗАО ЛЕДАС. Новосибирск, 2004. - 60 стр.

46. Blow J., Binstock A.: How to find the inertia tensor (or other mass properties) of a 3D solid body represented by a triangle mesh // Technical report, http://www.number-none.com, 2004

47. Keil J.: Polygon decomposition // Handbook of Computational Geometry, Elsevier Science Publishers B.V., North-Holland, 2000, pp. 491-518

48. Ермолин Е., Личман И., Казаков А., Лавров Р.: Построение гибридных полигональных сеток для задач САПР // Конференция-конкурс "Технологии Microsoft в теории и практике программирования". — Новосибирск, 2007.

49. Ермолин Е. Моделирование механических систем и связанные задачи // Семинар "3D графика и геометрия, высокопроизводительные вычисления" ИВМиМГ СО РАН, Intel-Novosibirsk. — Новосибирск, 2008.

50. Chazelle В.: Convex decompositions of polyhedra // Proc. 13th Annu. ACM Sympos. Theory Comput., 1981, pp. 70-79

51. Chazelle В.: Convex partitions of polyhedra: A lower bound and worst-case optimal algorithm // SIAM J. Comput., vol. 13, 1984, pp. 488-507

52. Bajaj C., Dey Т.: Convex decomposition of polyhedra and robustness // SIAM J. Comput., vol. 21, 1992, pp. 339-364

53. Lien J.: Approximate Convex Decomposition and Its Applications // Ph.D. Thesis, Department of Computer Science, Texas A&M University, 2006

54. Chazelle В., Dobkin D., Shouraboura N.: Strategies for polyhedral surface decomposition: An experimental study // Proc. 11th Annu. ACM Sympos. Comput. Geom., 1995, pp. 297-305

55. Chazelle В., Palios L.: Decomposing the boundary of a nonconvex polyhedron // Proc. 3rd Scand. Workshop Algorithm Theory, ser. Lecture Notes Comput. Sci., vol. 621. Springer-Verlag, 1992, pp. 364-375

56. Chazelle В.: A theorem on polygon cutting with applications // Proc. 23rd Annu. IEEE Sympos. Found. Comput. Sci., 1982, pp. 339-349

57. Greene D.: The decomposition of polygons into convex parts // Computational Geometry, ser. Adv. Comput. Res., F. P. Preparata, Ed. Greenwich, CT: JAI Press, vol. 1, 1983, pp. 235-259

58. Chazelle В., Dobkin P.: Optimal convex decompositions // Computational Geometry, G. T. Toussaint, Ed. Amsterdam, Netherlands: North-Holland, 1985, pp. 63-133

59. Tor S. and Middleditch A.: Convex decomposition of simple polygons // ACM ransactions on Graphics, vol. 3, N. 4, 1984, pp. 244-265

60. Siddiqi K., Kimia В.: Parts of visual form: Computational aspects // IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, N. 3, 1995, pp. 239-251

61. Dey Т., Giesen J., Goswami S.: Shape segmentation and matching with low discretization // Proc. Workshop on Algorithms and Data Structures, 2003, pp. 25-36

62. ODE, Open Dynamics Engine // www.ode.org

63. Newton Game Dynamics // http://newtondynamics.com

64. Millington I.: Game Physics Engine Development // Morgan Kaufmann Publishers, USA, 2007

65. Toussaint G.: Solving geometric problems with the rotating calipers // Proc. MELECON '83, Athens, 1983

66. Lloyd Т., Bau D.: Numerical Linear Algebra // SIAM, 1997

67. Широносов В.: Резонанс в физике, химии и биологии // ИД "Удмуртский университет", Ижевск, 2000/01й/