Методы и алгоритмы компьютерной графики для моделирования природных явлений и объектов в системах виртуальной реальности тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Григорьев, Андрей Борисович

• Григорьев, Андрей Борисович
• кандидат технических наук
• 2000

Оглавление диссертации кандидат технических наук Григорьев, Андрей Борисович

1. ВВЕДЕНИЕ.

2. ОСНОВНЫЕ ПРИНЦИПЫ И ПОДХОДЫ К МОДЕЛИРОВАНИЮ ПРИРОДНЫХ ЯВЛЕНИЙ.

2.1 Реализм и реалистичность.

2.2 нечеткие природные явления и объекты.

2.3 Модели природных явлений.

2.4 Методы моделирования природных явлений.

3. МОДЕЛИРОВАНИЕ ДИСКРЕТНЫХ НЕЧЕТКИХ ОБЪЕКТОВ.

3.1 Особенности моделирования дискретных объектов.

3.2 Метод анимации базовых точек [51].

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

3.4 Использование метода базовых точек для визуализации пены от водопадов.

3.5 Использование метода анимации базовых точек для моделирования облака частиц, отлетающих от движущегося автомобиля [53], [54].

3.6 Использование метода базовых точек для решения задачи визуализации погодных явлений (снег и дождь) [52].!.

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

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

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

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

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

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

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

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

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

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

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

Следует отметить, что существуют графические программы-моделлеры, такие как Softimage, Alias/Wavefront, дающие хорошие результаты в виде заранее просчитанных анимированных изображений природных явлений. Но методы, используемые в этих программах, не могут быть применимы для приложений, работающих в реальном времени, из-за высокой полигональной и временной сложности используемых алгоритмов. Это вызвано тем, что при моделировании и визуализации нечетких объектов приходится воспроизводить процесс во всем объеме, а не только на поверхности. Поэтому неизбежно увеличивается полигональная и временная сложность соответствующих алгоритмов.

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

Приведенный в работе алгоритм визуализации клочковатого тумана был использован в авиационном тренажере, установленном в Санкт-Петербургском аэропорту Пулково. Кроме того, одна из его модификаций нашла применение в вертолетном тренажере, разработанном по заказу Сыктывкарского аэропорта.

Решение задачи моделирования водной пены, возникающей в кормовой части движущегося судна, было использовано в судовом тренажере, созданном для Таллинского морского порта и в компьютерной игре "Jetboat SuperChamps". Алгоритм визуализации пены, возникающей вблизи водопадов, был задействован при разработке компьютерной игры "SpeedBoat Attack". Приведенные в работе алгоритмы визуализации грязи, отлетающей из под колес движущегося автомобиля использовались в компьютерной игре "Redline Racer". Решение задач моделирования снега и дождя было получено в ходе работы над игрой "SuperChix 76".

Реультаты работы были доложены на научных конференциях "Nondestructive Testing and Computer Simulations in Science and Engineering (St-Petersburg)" в 1997, 1998, 1999 и 2000 годах; на межвузовских научных конференциях "Неделя науки СПбГТУ" в 1998, 1999 годах.

По результатам проведенных исследований в открытой печати было опубликовано 7 статей.

Диссертационная работа состоит из 6 разделов. Первым разделом является настоящее введение. Во втором разделе проведен анализ наиболее часто применяемых в компьютерной графике реального времени подходов и принципов моделирования природных явлений и объектов. Более подробно по сравнению с другими описаны используемые в дальнейшем "системы частиц" и процедурные текстуры. Введена подробная классификация нечетких явлений и объектов.

Третий раздел посвящен моделированию дискретных нечетких объектов. В нем предложен метод анимации базовых точек. Этот метод является достаточно общим и может быть использован для моделирования практически всех нечетких явлений и объектов. В качестве примера в работе приведены решения ряда типовых задач, таких как визуализаця водной пены, возникающей в кормовой части судна, движущегося по поверхности воды (п.3.3); пены, возникающей вблизи водопадов (п.3.4); облака частиц, вылетающих из под колес движущегося автомобиля (п.3.5), а также снега и дождя (п.3.6).

В четвертом разделе рассмотрено решение задачи моделирования непрерывных нечетких явлений и объектов. Здесь предложен общий метод анимации карты прозрачности. В работе рассмотрено неколько модификаций этого метода, на примере решения задачи визуализации клочковатого тумана (п.4.2.4- 4.2.5)

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

В заключении проведен анализ результатов работы и сформулированы основные рекомендации по использованию метода анимации базовых точек и метода анимации карты прозрачности.

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Григорьев, Андрей Борисович

Основные результаты диссертационной работы могут быть сформулированы следующим образом:

1. Предложена общая классификация нечетких природных явлений и объектов.

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

3. Для моделирования непрерывных нечетких природных явлений и объектов предложен метод анимации карты прозрачности. Основные особенности его использования показаны на примере решения задачи визуализации клочковатого тумана.

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

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

6. Разработанные в работе методы анимации базовых точек и анимации карты прозрачности являются достаточно общими и могут быть использованы для моделирования большинства нечетких природных явлений и объектов. При этом затраты на визуализацию составлют не более 10 - 15 % от общего времени вывода сцены для типовой конфигурации современных персональных компьютеров. Таким образом, высокая скорость алгоритмов, основанных на этих методах, делает возможным их использование в приложениях, работающих в реальном времени.

6. Заключение

Список литературы диссертационного исследования кандидат технических наук Григорьев, Андрей Борисович, 2000 год

1. D. W. Tompson, "On Groth and Form", Cambridge University Press, 1961.

2. P. de Reffye, C. Edelin, J. Francon, M. Jaeger and C. Puech, "Plant Models Faithfull to Botanical Structure and Development", Computer Graphics 22(4) pp. 151 158, August 1988.

3. G. Y. Gardner, "Simulation of Natural Scenes Using Textured quadric Surfaces", Computer Graphics 18(3) pp 161 170, 1986

4. G. Y. Gradner, "Visual Simulation of Clouds", Computer Graphics 19(3) pp. 297-303, July 1985.

5. В. B. Mandelbrot, "The Fractal Geometry of Nature", W.H.Freeman and Co., 1982

6. W. T. Reeves, "Particle Systems A Technique for Modelling a Class of Fuzzy Objects", Computer Graphics 17(3) pp. 359 - 376, July 1983.

7. W. T. Reeves and R. Balu, "Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems", Computer Graphics 19(3) pp. 313-322, July 1985

8. D. Tonnesen, "Modeling Liquids and Solids Using Thermal Particles", Procedings of Grpahics Interface'91, pp 255 262, 1991.

9. R. Szeliski and D. Tonessen, "Surface Modeling with Oriented Particle Systems", Cambridge Research Lab, 1991

10. E. E. Catmull, "A Subdivision Algorithm for Computer Display of Curved Surfaces", PhD thesis, Department of Computer Science, University of Utah, December 1974.

11. J. F. Blinn, "Models of Light Reflection for Computer Synthesized pictures", In Computer Graphics (SIGGRAPH '77 Proceedings), 11(2), pp. 192 198 (July 1977)

12. J. F. Blinn, "Simulation of Wrinkled Surfaces", In Computer Graphics (SIGGRAPH '82 Proceedings), 16(3), pp. 21 29, July 1982.

13. K. Perlin, "An Image Synthesizer", In Computer Graphics (SIGGRAPH '85 Proceedings), 19(3), pp. 287 296, July 1985.

14. K. S. Fu and S. Y. Lu, "Computer Generation of Texture Using a Syntatic Approach", Computer Graphics (SIGGRAPH '78 Proceedings), 12(3), pp. 147 152, August 1978.

15. A. Fournier, D. Fussell and L. Carpenter, "Computer Rendering of Stochastic Models", Communications of ACM, 25(6), pp. 371 384, June 1982.

16. K. Sims, "Artificial Evolution for Computer Graphics", Computer Graphics (SIGGRAPH '91 Proceedings), 25(4), pp. 319 328, July 1991.

17. E. Rich, "Artificial intelligence", New York, McGraw Hill, 1983.

18. J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes, "Computer Graphics Principles and Practice", Addison-Wesley Publishing Company, 1996.

19. D. Ebert, F. Musgrave, D. Peachey, K. Perlin, S. Worley, "Texturing & Modeling", AP Professional, 1998.

20. J. Stam, E. Fiume, "Depicting Fire and Other Gaseous Phenomena Using Diffusion Processes", Computer Graphics (SIGGRAPH'95 Proceedings), pp 129 — 136, 1995.

21. D. S. Ebert, R. E. Parent, "Rendering and Animation Gaseous Phenomena by Combining Fast Volume and Scanline A-Buffer Techniques", Computer Graphics (SIGGRAPH'90 Proceedings), 24(4) pp 357-366,1990.

22. C. H. Perry, R. W. Picard, "Synthesizing Flames and Their Spread", Computer Graphics (SIGGRAPH'94 Proceedings), July 1994.

23. G. Ward, "A Recursive Implementation of the Perlin Noice Function", Computer Graphics (SIGGRAPH'87 Proceedings), July 1987.

24. R. A. Gingold, J. J. Monaghan, "Smoothed particle hydrodinamics: Theory and application to non spherical stars", Mon. Not. Roy. Astr. Soc., 181, pp 375-389

25. J. J. Monaghan, "Why Particle Methods Work", SIAM Jornal of Scientific and Statistical Computing, Vol 3, December 1982.

26. F. Uhl, J. Blanc-Talon, "Rendering Explosions", ETCA/CREA/SP, 1998.

27. J. D. Foley, A.van Dam, S.K.Feiner, J.F.Hughes "Computer graphisc: principles and practice", Addison Wesley, 1996.

28. G. Miller, H. E. Rushmeier, M. F. Cohen, D. P. Greenberg and K. E. Torrance. "An Experimental Evaluation of Computer Graphics Imagery". ACM Transactions on Graphics, 5(1) pp 30 50, January 1986.

29. J. F. O'Brien, J. K. Hodgins "Dynamic Simulation of Splashing Fluids". Proceedings of Computer Animation '95, April 1995.

30. J. Stam "Multi-Scale Stochastic Modelling of Complex Natural Phenomena , PhD Thesis, Dept. of Computer Science, University of Toronto, 1995.

31. R. Booth "Inner loops : a source book for fast 32-bit software development", Addison-Wesley Developers Press, 1997.

32. D. K. Birdsall, D Fuss "Clouds-in-clouds, Clouds-in-cells, Physics for Many Body Plasma Simulation", J. Comp. Phys., 3, pp. 494 511, 1969.

33. L. Lucy "A Numerical Approach to Testing the Fission Hypothesis", Astron. J., 82, pp. 481 -499, 1977.

34. R.A. Gingold, J. J. Monaghan "Smoothed Particle Hydrodinamics : Theory and Application to non spherical stars", Mon. Not. Roy. Astr. Soc., 181, pp 375 389, 1977.

35. R. A. Gingold, J. J. Monaghan "Binary Fission in Damped Rotating Polytropes", Mon. Not. Roy. Astr. Soc., 184, pp 481 -499, 1978.

36. R.A. Gingold, J. J. Monaghan "Kernel Estimates as a Bassis for Particle Methods", J. Comp. Phys., 1982.

37. J. Stam "Stochastic Rendering of Density Fields", Dept. of Computer Science, Univeristy of Toronto, 1994.

38. W. Dungan "A Terrain and Cloud Computer Image Generation Model", Computer Graphics (SIGGRAPH'79 Proceedings), 13(2), pp 41 44, August 1979

39. A. Watt, M. Watt "Advanced Animation and Rendering Techniques : Theory and Practice" ACM Press, 1994.

40. R.C. Gonzalez, R.E.Woods "Digital Image Processing", Reading, Massachusetts: Addison Wesley 1992.

41. E. Haines "Essential Ray Tracing Algorithms". In A.Glassner, ed.,"An Introduction to Ray Tracing", Boston: Academic Press, 1989.

42. R. Rubenstain, H. Hersh "The Human Factor Designing Computer Systems for People", Digital Press, Burlington, MA, 1984.

43. R.S. Gallagher "Computer Visualization", CRC Press, 1995.

44. G.S. Miller "The Definition and Rendering of Terrain Maps", Computer Graphics (SIGGRAPH'86 Proceedings), 20(4), pp 39 48,1986.

45. H.O. Peitgen, D. Saupe "The Science of Fractal Images", New York: SpringerVerlag, 1988.

46. J. Bloommenthal, С. Bajaj, J. Blinn, M.P. Cani-Gascuel, A. Rockwood, B. Wyvill, G. Wyvill "Introduction to Implicit Surfaces", Morgan Kaufman Publishers, Inc., 1997.

47. D.S. Ebert, R.E. Parent "Rendering and Animation of Gaseous Phenomena by Combining Fast Volume and Scanline A-buffer Techniques", Computer Graphics (SIGGRAPH'90 Proceedings), 25, pp 357 366, August 1990.

48. V.V. Aleksandrov, N.D Gorsky "From humans to computers : cognition through visual perseption", Word Scientific Publishing, 1991.

49. B.B. Александров, Н.Д. Горский "Представление и обработка изображений. Рекурсивный подход", изд. Наука 1985.

50. В.В Александров "Глаз и визуальное восприятие", Оптический журнал, т.66, 9, Сентябрь 1999.

51. А.В. Grigoriev, S.Yu. Belyaev "Case Study for Natural Phenomena Visualization: water foam", New Approaches to High-Tech Materials: Nondestructive Testing and Computer Simulations in Materials Science and Engineering, pp. 289 -293, June 1997.

52. A.B.Grigoriev "Case study for natural phenomena visualization: weather effects", Nondestructive Testing and Computer Simulations in Science and Engineering, pp. 224 228, June 1998.

53. A.B.Grigoriev "Case study for natural phenomena visualization: water foam and smoke", Nondestructive Testing and Computer Simulations in Science and Engineering, pp. 243 249, June 1999.

54. С.Ю.Беляев, А.Б.Григорьев "Моделирование природных явлений и объектов в компьютерной графике реального времени:водная пена", Труды кафедры Прикладной математики, 1999.

55. А.Б.Григорьев "Моделирование природных явлений и объектов: клочковатый туман", Студенческая конференция СПбГТУ, 1999.

56. К. Akeley, Т. Jermoluk "High Performance Polygon Rendering", (SIGGRAPH'88 Proceedings), 22(4), pp. 239 - 246, August 1988.

57. J.C. Chung "Exploring Virtual World with Head Mounted Displays", Proc. SPIE Meeting on Non-Holographies True 3-Dimensional Display Technologies, 1083, Los Angeles, Jan. 15-20, 1989.

58. Л. Г. Лойцянский "Механика жидкости и газа", М.: Наука, 1970.

59. А. А. Самарский "Теория разностных схем", М.: Наука. 1989.