ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Stepan Polovnikov                    2:5056/16.47   14 May 2001  21:05:30
 To : Serge Kanilo
 Subject : пеpесечения
 -------------------------------------------------------------------------------- 
 

 
 SK> Ладно, с направлением можно согласится, хотя в исходной задаче был трезок.
 SK> Слово "значительный выигрыш" употребляется здесь достаточно часто.
 SK> ИМХО, после подробного анализа часто оказывается, что такой "выигрыш"
 SK> редко превосходит 5%.
 
     Прочитав "значительный выигрыш" я не разбирался и использовал его ;)
 
 SK> В настоящем геометрическом решении используются операции
 SK> типа "приложить линейку и провести линию через две точки",
 SK> "провести окружность с центром в такой-то точке".
 SK> И никаких аддитивных и мультипликативных, это же геометрия :).
 
     Хм. Я думал тут все понятно. Уточню - аналитическая геометрия в
 пространстве. Полученные выражения были выведены путем предварительных
 рассуждений о возможных вариантах пересечения луча со сферой (там и теорема
 Пифагора упоминается :), которые были опущены (интересен полученный алгоритм).
 Когда используются координатные методы геометрии, то "в нем ведущую роль играют 
 вычисления, построения же имеют вспомогательное значение." Эта терминология
 (алгоритмическое - геометрическое решение) была использована в статьях по
 оптимизации вычислений пересечения луча с объектами, которую я и придерживался.
 
 >>     "The important difference is that the rejection tests are done
 >> much earlier in the process, making the overall cost of this algorithm
 >> lower on average."
 SK> От того что это написано на английском, это не становится правдой.
 SK> Отсев комплексных решений идет на том же шаге - проверка знака
 SK> детерминанта, и абсолютно все операции тождественны.
 SK> Если кто-то написал два решения - одно хуже а другое лучше и назвал
 SK> одно "алгоритмическим", а другое - "геометрическим", то это не значит,
 SK> что он был пророком. И я совсем не согласен с такой трактовкой.
 SK> Если в геометрическом решении нужна одна точка, то и в алгоритмическом
 SK> надо сказать, что ищется один из корней. И тогда все станет на место,
 SK> потому что главное различие здесь не в методе, а в том, что один
 SK> из них явно ставится в более жесткие условия чем другой. Как насчет
 SK> если я потребую, чтобы геометрический метода определял обе точки
 SK> пересечений и сравнивал расстояние до них? А аналитическому позволю искать
 SK> наименьший положительный действительный корень - кто тогда
 SK> окажется в выигрыше? Кстати в такой постановке я могу сразу отсеять еще
 SK> часть решений как явно ложные
 
     Постановка на самом деле такая: необходимо найти расстояние от точки луча до
 пересечения луча с объектом. Заметь вариант, что точка луча может находиться
 внутри объекта.
 
 SK> bool ...(.....,double*t){
 SK> ....
 SK> l=c-o
 
     l=o-c
     Для алгебраического решения ;)
     Т.к. выводиться из уравнения сферы (x-xc)*(x-xc) ... = r*r
     Здесь же l=c-o в полученном алгоритме выглядит не логично ;) Hепонятна
 причина такой записи для алгебраического рещения.
 
 SK> l2=l*l
 SK> ld=l*d     // это то же, что и tca
 SK> if(r2<l2){ // просто перестановка проверок
 
     Да - просто перестановка ;)
     Геометрически это означает, что точка луча находится вне сферы :)
 
 SK>   if(ld<0) return false // а вот здесь отсекаются два отрицательных корня
 
     Если сможешь себе представить, то это означает, что центр сферы лежит как бы
 позади начальной точки луча.
 
 SK>   det =ld*ld+r2-l2 // это еще может быть отрицательно
 SK>   if (det<0) return false
 SK>   *t =ld-sqrt(det)
 SK>   }
 SK> else {
 SK>   det =ld*ld+r2-l2 // здесь и так ясно, что положительно
 SK>   *t =ld+sqrt(det)
 SK>   }
 SK> return true
 SK> }
 
 SK> (я особо знаки не проверял :)
 >> SK> Просто непонятно, что возвращается и как его потом анализировать.
 >>     Если вернулся false (т.е. 0), то нет пересечения, иначе расстояние до
 >> объекта - t.
 SK> Т.е. 0.0. Или это все в целочисленной арифметике.
 SK> А если мы вплотную к объекту? :) Hу да ладно, это вопрос философский.
 
     Если быть точным, то используют константу точности threshold. Считается, что
 есть пересечение, когда t > threshold.
 
 SK> Я весь разговор затеял к тому, что в данной задаче оба подхода
 SK> идентичны, а тонкости несущественны.
 
     Как раз подходы совсем различны, а результат получается похожим. Сейчас сам 
 с обоими разобрался :) Hо в нескольких источниках рекомендуют именно
 геометрическое решение.
 
 SK> В отличие например от заметных различий например в быстром и простом
 SK> преобразовании Фурье, методе Якоби  и QR алгоритме для определения
 SK> собственных значений симметричных матриц.
 
     Хотя и мелочи, но иногда на них стоит обращать внимание. Считай это примером
 получения алгоритма, когда используются различные подходы к поставленной задаче.
 Сейчас разбираюсь с этим: "Optimized geometric algorithms exist for computing
 the intersection between a ray and some other quadrics. For example, there are
 methods for the cylinder and the cone." ;)
 
 Bye!
 --- GoldED+/W32 snapshot-2001.02.24
  * Origin: NETMAIL (2:5056/16.47)
 
 

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

Тема:    Автор:    Дата:    Re: пеpесечения   Serge Kanilo   14 May 2001 00:33:30   пеpесечения   Stepan Polovnikov   14 May 2001 21:05:30