Навигация
· XNA FAQ
· С чего начать
· Конкурсы
· Обратная связь
· XNA Блоги
Сейчас на сайте
· Гостей: 1

· Пользователей: 0

· Всего пользователей: 3,684
· Новый пользователь: headron
Последние фото
Эх, чуть не проспал закрытие.
Эх, чуть не проспал ...
Альбом: XNA Engine

GB
GB
Альбом: XNA Engine

South Park Coon & Friends
South Park Coon & Fr...
Альбом: XNA Games

Блоги
yavshoke
» XboxOne - интерес...
dampirik
» Push уведомления ...
dampirik
» Реклама,статистик...
Chort
» XNA и StartCoroutine
Chort
» Curve Class
dampirik
» Реклама, статисти...
dampirik
» Увеличение скорос...
dampirik
» Реклама, статисти...
general
» Распаковка DxtCom...
general
» Как работать с XN...
Поддержка
microsoft.com
1gb.ru - Дом для вашего сайта
Статистика посещений:

Просмотр темы
 Распечатать тему
О пересечениях
MCSMrDoctorWatson
#1 Распечатать сообщение
Опубликовано 19.12.2012 00:29:18
Новичок


Сообщений: 3
Зарегистрирован: 22.09.12

Здравствуйте, уважаемые участники форума!

Прошу у вас о помощи.

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

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

Поиск дал алгоритм нахождения пересечения полигона и сферы, полигона и линии, но, к сожалению, не дал нужного мне. (а может, я просто не умею искать Smile ).

Порылся в исходниках BepuPhysics (http://bepuphysic...eplex.com/), нашел код пересечения в BepuPhysics>CollisionTests>CollisionAlgorithms>TriangleTrianglePairTester.

Однако копировать код, тем более если его не понимаешь - не слишком, так сказать, прилично.

***************************

Итак, прошу описать алгоритм нахождения пересечения трехмерных полигонов и характеристик пересечения, или хотя бы дать ссылочку на материал, где это описывается, ну или на худой конец описать, как работает алгоритм от BepuPhysics, ибо сам я не особо понимаю его физ. смысл (понимаю, что делается с данными, но как это укладывается в общую картину для достижения цели, непонятно).
 
FlameXander
#2 Распечатать сообщение
Опубликовано 19.12.2012 01:09:08
Специалист


Сообщений: 129
Зарегистрирован: 19.01.11

Что сразу пришло в голову - через второй полигон провести(?) плоскость, найти точки пересечения двух сторон первого полигона с этой плоскостью и усреднить их координаты - получится именно центральная точка пересечения. В формулах это выразить сейчас не могу(ночь уже), завтра если что попробую посчитать. Вроде особых сложностей не вижу.
Изменил(а) FlameXander, 19.12.2012 06:38:08
 
beaver
#3 Распечатать сообщение
Опубликовано 19.12.2012 09:11:53
Аватар пользователя

Администратор


Сообщений: 1772
Зарегистрирован: 22.02.09

Всё придумано давно, не нужно изобретать велосипед.
В JitterPhysics есть TriangleMeshShapeRigidBody, попробуйте.
Я в своих опытах скармливал сложную выпукло-впуклую модель - всё работало прекрасно.
 
Hale_32bit
#4 Распечатать сообщение
Опубликовано 19.12.2012 10:10:05
Аватар пользователя

Администратор


Сообщений: 783
Зарегистрирован: 23.02.10

Поиск дал алгоритм нахождения пересечения полигона и сферы, полигона и линии


Проверяй пересечение всех отрезков одного полигона со всеми отрезками другого и наоборот. Наверняка это не самый быстрый способ, но способ же.
Блог: http://hale32bit....
 
Chort
#5 Распечатать сообщение
Опубликовано 20.12.2012 13:24:44
Аватар пользователя

Администратор


Сообщений: 1296
Зарегистрирован: 16.02.09

Пересечение 2 треугольников -> пересечение ребер треугольника с другим треугольником. Пересечение ребра АВ -> пересечение луча АВ на растоянии меньшим за длину АВ. Пересечение луча и треугольника - http://dzindzinov...angle.html

+ http://xbox.creat...g_triangle
+ https://sites.goo...tersection
Изменил(а) Chort, 20.12.2012 13:25:37
На вопросы отвечаю с головы. Ссылка на ответы или запускаю студию только в интересных случаях.
 
MCSMrDoctorWatson
#6 Распечатать сообщение
Опубликовано 27.12.2012 19:12:50
Новичок


Сообщений: 3
Зарегистрирован: 22.09.12

Всем спасибо за ответы, я выбрал способ через нахождение пересечений отрезков и плоскостей треугольников. Однако у меня у меня возникают проблемы реализации. Собственно говоря, я делал по третьей ссылке Chort-а, и прошу поправить меня, что я неправильно делаю. :)

Код структуры Triangle (прошу не обращать внимания на огрехи с буфером - я знаю, что подобный код сказывается на производительности, но мне хотелось написать все по-быстрому):

Загрузить источник  GeSHi: C#
  1. public partial struct Triangle
  2. {
  3. public Vector3 V1, V2, V3; // Вершины треугольника
  4.  
  5. public VertexBuffer Buffer; // Буфер вершин
  6.  
  7. public Triangle(ExampleGame game, Vector3 v1, Vector3 v2, Vector3 v3)
  8. {
  9. // Задаем координаты вершин
  10. this.V1 = v1;
  11. this.V2 = v2;
  12. this.V3 = v3;
  13.  
  14. this.Buffer = new VertexBuffer(game.GraphicsDevice, typeof(VertexPositionColor), 3, BufferUsage.None);
  15.  
  16. InitializeBuffer();
  17. }
  18. private void InitializeBuffer()
  19. {
  20. VertexPositionColor[] vertArray = new VertexPositionColor[3];
  21. vertArray[0] = new VertexPositionColor(this.V1, Color.Red);
  22. vertArray[1] = new VertexPositionColor(this.V2, Color.Green);
  23. vertArray[2] = new VertexPositionColor(this.V3, Color.Blue);
  24.  
  25. this.Buffer.SetData<VertexPositionColor>(vertArray);
  26. }
  27.  
  28. // Сдвиг треугольника по вектору путем прибавления ко всем вершинам этого вектора
  29. public void Move(Vector3 vector)
  30. {
  31. this.V1 += vector;
  32. this.V2 += vector;
  33. this.V3 += vector;
  34.  
  35. InitializeBuffer();
  36. }
  37.  
  38. // Собственно, отрисовка
  39. public void Draw(ExampleGame game)
  40. {
  41. game.GraphicsDevice.SetVertexBuffer(this.Buffer);
  42. game.GraphicsDevice.DrawPrimitives(PrimitiveType.TriangleList, 0, 1);
  43. }
  44. }
Добавлено за 0.011 секунд, используя GeSHi 1.0.8.2


Теперь собственно код пересечения:
Загрузить источник  GeSHi: C#
  1. public partial struct Triangle
  2. {
  3. public CollisionResult Collide(Triangle triangle)
  4. {
  5. // Структура, содержащая информацию о тесте
  6. CollisionResult info = new CollisionResult();
  7.  
  8. // Точка давления
  9. Vector3? result = new Vector3?();
  10.  
  11. // Проверяем три стороны на пересечение
  12. Vector3? abCollision = SideTriangleCollide(V1, V2, triangle),
  13. bcCollision = SideTriangleCollide(V2, V3, triangle),
  14. acCollision = SideTriangleCollide(V3, V1, triangle);
  15.  
  16. // Усредняем
  17. if (abCollision.HasValue)
  18. result = abCollision;
  19.  
  20. if(bcCollision.HasValue)
  21. if (result.HasValue)
  22. result = Middle(result.Value, bcCollision.Value);
  23. else
  24. result = bcCollision.Value;
  25.  
  26. if (acCollision.HasValue)
  27. if (result.HasValue)
  28. result = Middle(result.Value, acCollision.Value);
  29. else
  30. result = acCollision.Value;
  31.  
  32. // Пакуем результаты
  33. info.Collision = result.HasValue;
  34.  
  35. if(info.Collision)
  36. {
  37. info.abCollision = abCollision.HasValue;
  38. info.bcCollision = bcCollision.HasValue;
  39. info.acCollision = acCollision.HasValue;
  40.  
  41. info.CollisionPoint = result.Value;
  42. }
  43.  
  44. return info;
  45. }
  46.  
  47. private Vector3? SideTriangleCollide(Vector3 firstVertex, Vector3 secondVertex, Triangle triangle)
  48. {
  49. // Луч, описывающий сторону
  50. Ray ray = new Ray(firstVertex, Vector3.Normalize(secondVertex - firstVertex));
  51.  
  52. // Проверяем на наличие пересечения с плоскостью
  53. Plane plane = new Plane(triangle.V1, triangle.V2, triangle.V3);
  54. float? result = ray.Intersects(plane);
  55.  
  56. /* В случае, если пересечения с плоскостью, содержащей треугольник, нет,
  57.   или расстояние точки пересечения от начала луча больше, чем длина стороны */
  58. if (!result.HasValue || result.Value > Vector3.Distance(firstVertex, secondVertex) || result.Value < 0) return null;
  59.  
  60. // Точка пересечения луча с плоcкостью
  61. Vector3 cp = ray.Position + ray.Direction * result.Value;
  62.  
  63. // Проверяем, проходит ли луч через треугольник по правилу "левой стороны"
  64. // (Действительно для модели пересечения против часовой стрелки)
  65. if (
  66. Vector3.Dot(Vector3.Cross(V2 - V1, cp - V1), plane.Normal) < 0
  67. ||
  68. Vector3.Dot(Vector3.Cross(V3 - V2, cp - V2), plane.Normal) < 0
  69. ||
  70. Vector3.Dot(Vector3.Cross(V1 - V3, cp - V3), plane.Normal) < 0)
  71. return null;
  72.  
  73. return cp;
  74. }
  75.  
  76. // Нахождение середины трехмерного отрезка
  77. private Vector3 Middle(Vector3 f, Vector3 s)
  78. {
  79. return new Vector3((f.X + s.X) / 2, (f.Y + s.Y) / 2, (f.Z + s.Z) / 2);
  80. }
  81. }
  82.  
  83. // Структура для сохранения информации о результате теста
  84. public struct CollisionResult
  85. {
  86. // Есть ли пересечение
  87. public bool Collision;
  88.  
  89. // Пересечение граней
  90. public bool
  91. abCollision,
  92. bcCollision,
  93. acCollision;
  94.  
  95. // Средняя точка соприкосновения
  96. public Vector3 CollisionPoint;
  97. }
Добавлено за 0.017 секунд, используя GeSHi 1.0.8.2


Код нахождения пересечения выше находит только пересечения сторон одного треугольника с поверхностью другого, и только, то есть за полноценное нахождение пересечения считать нельзя.

Собственно, проблема в том, что алгоритм иногда показывает пересечения тогда, когда явно видно, что его нет, и наоборот.

Пожалуйста, укажите на ошибку в коде.
 
MCSMrDoctorWatson
#7 Распечатать сообщение
Опубликовано 08.01.2013 15:09:26
Новичок


Сообщений: 3
Зарегистрирован: 22.09.12

Прошу помочь, в чем моя ошибка?
 
Перейти на форум:
Авторизация
Логин

Пароль



Вы не зарегистрированы?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Мини-чат
Вы должны авторизироваться, чтобы добавить сообщение.

27.08.2014
Я умею немного на asp.net + html и css

22.08.2014
на ASP mvc 3 есть пару проектов. Могу помочь, если нужно. Обидно, если закроется Frown

21.08.2014
я тоже ноль

21.08.2014
Я в вебе только с php занимался да и то на уровне чтоб работало.

21.08.2014
Я в вебе полный ноль…

21.08.2014
Переводить его надо, хоть на ту же азуру. И двиг менять на что-то современное. Если есть веб-разрабы - можем скооперироваться. Один делать не буду.

21.08.2014
не знаю всех нюансов по оплате и все хорошее когда нибудь заканчивается

21.08.2014
А что случилось?

21.08.2014
похоже сайт будет работать до 28го числа

09.08.2014
Апи пока не видел. Но есть приложение в магазине Live Lock Screen BETA, так что думаю скоро будет

08.08.2014
Я про API для Update1. На нем работает это

08.08.2014
А что именно нужно? Чтото и сейчас открыто http://msdn.micro.
...105).aspx

06.08.2014
Кто-нибудь слышал об открытии доступа к Lock Screen Api?

31.07.2014
VPDExpress на базе MVS 2012, ни в какую не ловит исключения. Даже если их сам создаешь. И всех так?

25.07.2014
С днем системного администратора причастных к этой профессии! По случаю - тортик от жены

RSS каналы сайта
XNA - Новости
XNA - Статьи
XNA - Форум
XNA - Галерея
XNA - Файлы
Время загрузки: 1,05 секунд 8,709,542 уникальных посетителей