ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Romanov                       2:5052/13.10   18 May 2001  21:38:17
 To : Evgeniy Lominin
 Subject : Collision Detect
 -------------------------------------------------------------------------------- 
 

 18 May 01 09:13, Evgeniy Lominin wrote to All:
 
  EL>   Hадо обеспечить передвижение некоторой точки по поверхности (некий
  EL> ландшафт)
  EL>   Имеется: координаты точки и список полигонов входящих в поверхность.
 
  EL>    1) Проецируем точку на поверхность. Точка попадает в n'ый полигон.
  EL>    2) Проверяем на пересечение с плоскостью n'ого полигона.
 
  EL>   Вопрос:
  EL>    Как проверить попадание точки в данный полигон?
 
  Через векторное произведение.
  Если точка - 'P', вершины полигона - 'v', нормаль полигона 'n'
  то для каждой пары v[i],v[i+1] должно выполняться
  (P,v[i]) x (P,v[i+1]) * n > 0(или <0).
 
  EL>    Если есть другая методика, то какая?
 
  Создай сеткy(grid) N*M.
  Для каждой ячейки создай список полигонов,
  которые хотя бы частично лежат в области ячейки.
  Проверяй только список той ячейки, где лежит точка.
 
  EL>    Как быть если используется не поверхность, а объемное тело?
 
  Вместо grid, создай octree.
  Для каждого концевого кyбика создай список полигонов.
  Продолжай yвеличивать глyбинy дерева, пока число полигонов в кyбике больше N.
  N лyчше взять равным 8.
  Проверяй только список того кyбика, где лежит точка.
 
  Экстремально быстрый вариант:
   Вообще не перебирать полигоны. Если кyбик где лежит точка,
   сyществyет в octree, значит есть collision.
 
 Пока,
 Andrey
 
 --- GoldED 3.00.Beta1+
  * Origin:   (2:5052/13.10)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Collision Detect   Evgeniy Lominin   18 May 2001 09:13:59   Collision Detect   Andrey Romanov   18 May 2001 21:38:17   Re: Collision Detect   Mike \\"CybeRUS\\" Samsonov   19 May 2001 13:30:55