автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ геометрических описаний сложных объектов на базе алгебраических уравнений суперповерхностей, их обработка и визуализация

Введение.

Глава I. Анализ существующих методов описания объектов в пространстве.?

1.1 Формирование векторных поверхностей.

1.2 Перенос и повороты в трехмерном пространстве.

1.3 Виды аппроксимации.

1.3.1 Радиусографический способ.

1.3.2 Способ кривых второго порядка.

1.3.3 Кривые типа В-сплайна.

1.3.4 Поверхности типа В-сплайна.

1.4 Алгебраическое описание поверхностей второго порядка.

1.4.1 Общее уравнение второй степени.

1.4.2 Инварианты поверхностей второго порядка.Г.7.

1.4.3 Классификация поверхностей второго порядка.

1.4.4 Характеристическая квадратичная форма и характеристическое уравнение.

1.4.5 Диаметральные плоскости, диаметры и центры поверхностей второго порядка.

1.4.6 Главные плоскости и главные оси.

1.4.7 Приведение уравнения поверхности второго порядка к стандартному (каноническому) виду.

1.4.8 Касательные и нормали поверхности второго порядка.

1.4.9 Некоторые дополнительные формулы и теоремы.

1.4.10 Параметрическое задание поверхности второго порядка.

Глава II. Метод параметрического описания, формирование сцен на основе суперповерхностей, описанных синусо-косинусоидальной кривой.

2.1 Формирование параметрической машинной модели синусо-косинусоидального метода описания аналитических поверхностей и их визуализация.

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

2.2.1 Машинная модель сферы (эллипсоида).

2.2.2 Машинная модель однополостного гиперболоида.

2.2.3 Машинная модель двуполостного гиперболоида.

2.2.4 Машинная модель конуса второго порядка.

2.2.5 Машинная модель параболоида (эллиптического параболоида).

2.2.6 Машинная модель цилиндра (эллиптического цилиндра).

2.3 Метод формирования параметрической машинной модели описания суперповерхностей и ее преобразования.

2.3.1 Машинная модель суперсферы.

2.3.2 Машинная модель однополостного супергиперболоида.

2.3.3 Машинная модель двуполостного супергиперболоида.

2.3.4 Машинная модель суперконуса.

2.3.5 Машинная модель суперпараболоида.

2.3.6 Машинная модель суперцилиндра.

2.4 Метод создания сцен на базе суперповерхностей.

2.4.1 Особенности метода.

Глава III. Метод алгебраического описания, обработка и визуализация сцен на основе аналитических суперповерхностей.

3.1 Поиск действительных корней алгебраических уравнений.

3.1.1 Поиск действительных корней квадратного уравнения вида ах2+Ьх+с=0 (а#0).

3.1.2 Поиск корней кубического уравнения вида: хЗ+ах2+Ьх+с=0.

3.1.3 Поиск корней уравнения четвертой степени вида: х4+ахЗ +Ьх2+сх+с1=0.

3.1.6 Другие алгебраические уравнения.

3.2 Численные методы нахождения корней уравнений.

3.2.1 Метод половинного деления.

3.2.2 Метод хорд.

3.2.3 Метод Ньютона (метод касательных).

3.2.4 Метод секущих.

3.2.5 Метод простых итераций.

3.3 Используемые методы визуализации.

3.3.1 Обратная трассировка лучей.

3.3.2 Модели освещенности.

3.3.3 Расчет нормали к объекту.

3.4 Алгебраическое описание суперповерхностей и трехмерных аналогов плоских кривых.

3.5 Методы сопряжения и сшивки аналитических поверхностей.

3.5.1 Сопряжение поверхностей с резким переходом.

3.5.2 Сшивка поверхностей с плавным переходом.

Глава IV. Описание алгоритмов программ.

4.1 Алгоритм построения при помощи параметрически описанной пространственной кривой.

4.2 Алгоритм построения при помощи алгебраически описанных аналитических поверхностей.

В настоящее время моделирование трехмерных сцен, их визуализация и математический анализ приобретают все большую популярность при решении с помощью компьютера многих задач пространственного моделирования - расчеты на прочность, имитация полета, движение молекул в потоках газа, создание мультфильмов (игр), решение задач столкновений и отражений объектов в трехмерном пространстве. Решение таких трехмерных задач, с точки зрения ресурса вычислительных затрат, для объектов сложной конфигурации весьма дорого и для снижения их стоимости требуется индивидуальный подход к каждой задаче: необходим подбор конфигурации вычислительной графической системы, выбор специального математического и программного обеспечения для решения геометрической задачи и последующего анализа получаемых трехмерных сцен [1,2,15].

На сегодняшний день трехмерные сцены моделируются объектами, состоящими из плоскостей [31,40], расположенных определенным образом друг относительно друга - векторным методом. Это подходит для кубов, призм, пирамид, параллелепипедов, плоскостей и сцен состоящих из них [3, 10,14,45]. Но все это формы искусственных предметов созданных человеком; в природе подобное встречается крайне редко. Для того чтобы создать сложную модель с плавными кривыми поверхностями в векторном методе используют аппроксимацию полигонами [14,49]. В настоящее время организации, занимающиеся созданием аппаратного и программного обеспечения для моделирования трехмерных сцен, используют и развивают именно этот векторный метод [62,70,73]. На основе этой технологии созданы специальные программные и аппаратные средства - оптимизированные для этого центральные процессоры и ЗБ ускорители, работающие с полигонами, ускоряющими их математическую обработку, добавлением текстур на них и прочие спецэффекты. 6

Более полное описание, подходящее для создания кривых поверхностей, дает структурно-аналитический метод моделирования, где элементарные поверхности, формирующие сцену, описываются аналитическими уравнениями [18,19,20,71]. Кроме того, в таком методе сцена описывается гораздо более компактно, чем в векторных методах. Подобное математическое описание применимо для компьютерного моделирования таких сложных объектов как, например, человеческое тело, излучатели СВЧ, корпуса и детали кораблей, самолетов, процессы горения в турбинах, различные гидро и аэродинамические задачи.

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

Заключение

В ходе проведенных исследований и разработок получены следующие научные и практические результаты:

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

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

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

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

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

- получены алгебраические уравнения трехмерных аналогов плоских кривых на основе их классических уравнений;

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

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

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

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

- подходит для описания криволинейных поверхностей.

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

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

- исследование и расширение библиотеки аналитических поверхностей.

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

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

1. Абраш, М. Программирование графики. Таинства. -Киев: ЕвроСиб, 1995.

2. Аммерал JI. Машинная графика на персональных компьютерах. Пер. с англ.- М.: «Сол Систем», 1992. 232 стр.: ил.

3. Аммерал J1. Принципы программирования в машинной графике. Пер. с англ. М.: «Сол Систем», 1992. - 224 е.: ил.

4. Апатенок Р.Ф. и др. Элементы линейной алгебры и аналитической геометрии: Учебн. пособие. Мн.: Вышэйш. шк., 1986.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979.

6. Бахвалов Н., Жидков Н., Кобельков Г. Численные методы, ФИЗМАТЛИТ, М, С-Пб, 2001.

7. Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: Учебн. пособие. М.:Наука, 1980.

8. Березин И. С., Жидков Н. П. Методы вычислений. М., 1959. Т. 1. 1960. Т.2.

9. Богалев Ю.П., Вычислительная математика и программирование, М, Высш. шк., 1990.

10. Боресков A.B., Е.В. Шикин, Г.Е. Шикина. Компьютерная графика: первое знакомство. /М.: Финансы и статистика, 1996. 176 с. ил.

11. Воеводин В.В. Вычислительные основы линейной алгебры, М., Наука, 1977.

12. Воеводин В.В. Численные методы алгебры. Теория и алгоритмы, М, Наука, 1966

13. Волков Е.А. Численные методы, М., Наука, 1982.

14. Гардан П., Люка М. Машинная графика и автоматизация конструирования. / М., Мир, 1987.

15. Гил ой В. Интерактивная машинная графика: Структуры данных, алгоритмы, языки. / М., Мир, 1981.

16. Гуревич Натан, Гуревич Ори. Visual С++ 5: Освой самостоятельно / Пер. с англ. М.: ЗАО «Издательство БИНОМ», 1998 г. - 624 е.: ил.

17. Де Бор К. Практическое руководство по сплайнам. М., 1985.

18. Дегтярев В.М. Визуализация трехмерной математической модели объекта. / Вопросы специальной радиоэлектроники, вып.22, серия PJIT, 1990.

19. Дегтярев В.М. Плоскостной метод преобразования пространственной геометрической информации в автоматизированном процессе проектирования. / Труды ЛИАП, вып.94, JX, 1975.

20. Дегтярев В.М. Структурно-аналитический способ представления трехмерных геометрических объектов в ЦВМ/ НИИЭИР. М., 1973. -Вып. 10.

21. Ермаков С.М., Метод Монте-Карло и смежные вопросы, «Наука», 1971.

22. Иванов В. П., Батраков А. С. Трехмерная компьютерная графика. -М.: Радио и связь, 1994.

23. Иванов Г.С. Начертательная геометрия: Учебник для вузов. М.: Машиностроение, 1995. 224 с. с ил.

24. Ильин В. А., Позняк Э.Г. Аналитическая геометрия. М.: Наука, 1971.

25. Ильин В.А., Позняк Э.Г. Аналитическая геометрия: Учеб. М.: Наука, 1988. 223 с.

26. Ильин В.А., Позняк Э.Г. Линейная алгебра: Учеб. М.: Наука, 1984. 295 с.

27. Калиткин Н. Н. Численные методы. М., 1978.

28. Камке Э. Справочник по обыкновенным дифференциальным уравнениям. М., 1971.

29. Кейлингерт П. Элементы операционных систем. М., 1985.

30. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров М.: Наука, 1974 - 832 е.: ил.

31. Котов И.И., Полозов B.C., Широкова Л.В. Алгоритмы машинной графики. М., «Машиностроение», 1977. 231 с. с ил.

32. Лапковский A.K. Алгоритмы изображения движущихся тел при параллельном и центральном проецировании. Аксонометрия и компьютеризация изображений. Мн.: Навука i тэхшка, 1993.-207 с.

33. Майкл, Ласло. Вычислительная геометрия и компьютерная графика на С++. -М.: Бином, 1997.

34. Марчук Г.И. Методы вычислительной математики. М., 1989.

35. Математика и САПР:, в 2 кн. -М.: Мир, 1988.

36. Мудров А.Е. Численные методы для ПЭВМ на языках бейсик, фортран и паскаль. Томск: МП «Раско», 1991 272 е.: ил.

37. Найджел Томпсон. Секреты программирования трехмерной графики для Windows 95. С-Пб. Питер, 1997. 352 с.

38. Незбайло Т.Г. Теория нахождения корней алгебраических уравнений в аналитической форме. СП-б. РПМ Библиотеки РАН. 2000г.

39. Ньюмен У., Спрулл Р. Основы интерактивной графики. -М.: Мир, 1985

40. Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. М., 1986.

41. Павлидис У. Алгоритмы машинной графики и обработка изображений. -М.: Радио и связь, 1988.

42. Питер Нортон, Роб Макгрегор, Программирование в Windows 95/NT 4 с помощью MFC. Справочное издание в двух книгах. CK Пресс, 1998.

43. Погорелов A.B. Аналитическая геометрия. -М.: Наука, 1968.

44. Полигональные модели. Москва. Диалог-МИФИ, 2000 г. 462 с.

45. Роджерс Д., Адаме Дж. Математические основы машинной графики. -М. Машиностроение, 1980.

46. Самарский A.A. Введение в численные методы. М., 1987.

47. Системы параллельной обработки/ Под ред. Д. М. Ивенса, 1985.

48. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973 - 312 е.: ил.

49. Стечкин С.Б., Субботин Ю.Н., Сплайны в вычислительной математике, М., Наука, 1976.

50. Тихомиров Ю. Программирование трехмерной СПб. BHV-Санкт Петербург, 1998. 256 е., ил.

51. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М., 1986.

52. Уилтон Р. Видеосистемы персональных компьютеров IBM PC и PS/2. Руководство по программированию. -М.: Радио и связь, 1994.

53. Фокс Ф., Прап М. Вычислительная геометрия. Применение в проектировании и на производстве. -М.: Мир, 1982.

54. Фоли Дж., ван Дэм Ф. Основы интерактивной машинной графики. -М.: Мир, 1985.

55. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М., 1980.

56. Хартскорн Р. Алгебраическая геометрия. М., 1981

57. Хейни, Лорен. Построение изображений методом слежения луча. -М., 1994.

58. Шафаревич И.Р. Основы алгебраической геометрии. М., 1972

59. Шикин Е. В., Боресков А. В. Компьютерная графика. Динамика, реалистические изображения. -М.: Диалог-МИФИ, 1995.

60. Шикин Е. В., Боресков А. В., Зайцев А. А. Начала компьютерной графики. -М.: Диалог- МИФИ, 1993.

61. Шикин Е.В. Боресков А.В. Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 2001. - 464 с.

62. Шикин Е.В., Плис А.И. Кривые поверхности на экране компьютера. -М.: Диалог-МИФИ, 1996.

63. Энджел Й. Практическое введение в машинную графику. -М. : Радио и связь, 1984

64. Янке Е., Эмде Ф., Леш Ф. Специальные функции. Формулы, графики, таблицы. М., 1977.

65. Ammeraal, L. (1986). С for Programmers, Chichester: John Wiley & Sons.

66. Ammeraal, L. (1987) .Computer Graphics for the IBM PC, Chichester: John Wiley & Sons.

67. Ammeraal, L. (1987). Programs and Data Structures in C, Chichester: John Wiley & Sons.F

68. Axelsson O. Numerical linear algebra. Cambrige, 1996.

69. Ayres, F.Jr. (1967). Schaum's Outline Series, Theory and Problems of Projective Geometry, New York: McGraw-Hill.

70. Barsky B. Computer graphics and geometric modeling using Beta-splines. -Springer Verlag, 1988.

71. Degtyarev V. M., Morozov S. M. Computer representation of structure-analytic model of 3D objects. //Symposium LMI, Leningrad, issue 6,1991.

72. Escher, M.C., et al. (1972). The World of M.C. Escher, NewYork: Harry N. Abrams.

73. Farin G. Curves and surfaces for computer aided geometric design. A practical guide. Academic Press, 1990.

74. Foley D.J., A. van Dam, Feiner S.K., Hughes J.F.Computer graphics. Principles and practice/ Addison-Wesley,1991.

75. Foley, J.D., and A. van Dam (1982). Fundamentals of Interactive Computer Graphics, Reading, Mass,: Addison-Wesley.

76. Forsythe, G.E., M.A. Malcolm and C.B. Moler (1977) .Computer Methods for Mathematical Computations, Englewood Cliffs, NJ: Prentice-Hall.

77. Hall R. Illumination and color in computer generated imagenary. -1991.

78. Hopkins, E.J., and J.S. Hails (1953). An Introduction to Plane Projective Geometry, Oxford: The Clarendon Press.

79. Kernighan, B.W., and O.M. Ritchi (1978). The Programming Language, Englewood Cliffs, NJ: Prentice-Hall.

80. Kreyszig, E. (1962). Advanced Engineering Mathematics, New York: John Wiley & Sons.

81. McGregor, J., and A. Watt (1984). The Art of Microcomputer Graphics for the BBC Micro/ Electron, Reading, Mass.: Addison-Wesley.

82. Newman, M.N., and R.F. Sproull (1979). Principles of Interactive Computer Graphics, New York: McGraw-Hill.

83. Norton, P. (1983). Inside the IBM PC, Bowie, MD.: Brady.

84. Norton, P. (1985). Programmer's Guide to the IBM PC, Washington: Microsoft Press.

85. Plum, T. (1983). Learning to Program in C, Englewood Cliffs, NJ: Prentice-Hall.

86. Rogers, D.F. (1985) Procedural Elements for Computer Graphics, New York: McGraw-Hill.

87. Sargent, M., and R.L. Shoemaker (1984) The IBM Personal Computer from Inside Out, Reading, Mass.: Addison-Wesley.

88. Периодические издания «Компьютер-Пресс»,

89. Периодические издания «Мир ПК»

90. Ссылка в Интернет www.enlight.ru

91. Ссылка в Интернет www.hornet.org

92. Ссылка в Интернет www.scene.org

93. Ссылка в Интернет www.mhri.edu.au/~pdb

94. Ссылка в Интернет cg.cs.tu-berlin.de/~ki

95. Ссылка в Интернет www.intel.com

96. Ссылка в Интернет www.neutralzone.org/home/faqsys

97. Ссылка в Интернет www.t-80.ru/dl/

98. Ссылка в Интернет www.lgg.ru/~graphics3d/win/

99. Ссылка в Интернет www.paragraph.com