Когда не нужна тригонометрия

[tagir_valeev]

Рейтрейсер напишите без тригонометрии, это веселее :-) Основы те же самые :-)

[Error_403_Forbidden]

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

[Error_403_Forbidden]

Не знаком со способом трассирования лучей? Какие ещё треугольники в сфере?

[JC_Piligrim]

Хорошая статья по теме: www.thg.ru/graphic/ray_tracing_rasterization/print.html

А вообще, википедия: ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%B0%D1%81%D1%81%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%BB%D1%83%D1%87%D0%B5%D0%B9
, и по ссылкам

[Error_403_Forbidden]

Зачем это мне? Я прекрасно знаю про этот метод, т.к. писал его ещё в 1999 году

[JC_Piligrim]

Извините, промахнулся. Это для Horse, с трИугольниками в сфере. :)

[cramen]

любой учебник аналитической геометрии вам все расскажет о пространствах, матрицах и их геометрическом смысле.

[WaReZ_MEN]

Тригонометрия часто нужна тем кто пишет игры и различные редакторы для окон мебели и прочее а всем остальным она скорее всего и не нужна…

[wishope]

а графические редакторы и ГИС?

[WaReZ_MEN]

я их в прочее внес :)

[kolen]

Сеошникам и создателям дейтинг-стартапов точно не нужна!

[elliadan]

Действительно полезная статья!

[amarao]

На чём основывается утверждение, что sin(0.3) считается медленее, чем 1.2/0.33? И то и то FPU.

[mace]

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

[amarao]

Ну вы просто заставляете меня сделать тесты самому.

1.c:

#include <stdio.h>
#include <math.h>
void main(){
double a;
double b;
for(a=0;a<1000000000;a++){
        b=sin(a);
}
}

time ./a.out

real 0m1.412s
user 0m1.400s
sys 0m0.012s

2.c

#include <stdio.h>
#include <math.h>
void main(){
double a;
double b;
for(a=0;a<1000000000;a++){
        b=a/0.3;
}
}

time ./a.out

real 0m1.413s
user 0m1.408s
sys 0m0.004s

Итого — синус и деление выполняются за строго ОДИНАКОВОЕ время.

[alexmay]

кэш процессора активно работает здесь.
как мне кажется — точнее было бы использовать разные коэфициенты, дабы исключить особенности процессоров

[amarao]

При чём тут кеш? О чём вы? Это строго одинаковый код, в котором в одном случае выполняется инструкция fdiv, а во втором fsin. Какие особенности каких процессоров?

Если вы хотите предложить свой метод сравнить скорость деления и вычисления sin на современных FPU, приводите.

[Rulexec]

>>> def sinus():
… last = time.clock()
… for i in xrange(1000000):
… x = math.sin(i)
… return time.clock() — last
…
>>> print sinus()
0.436118277602

>>> def delit():
… last = time.clock()
… for i in xrange(1000000):
… x = i/0.3
… return time.clock() — last
…
>>> print delit()
0.15221040663

В питонах деление быстрее

[amarao]

Это всего лишь означает, что в питоне хреновая работа с float стилем. В gсс sin и / для double просто разворачивается в ассемблерную инструкцию. Что происходит в питоне — одному богу известно, а на скорость выполнения программы может влиять, например, смена [] на функцию map и т.д.

Вот ассемблерный код для 1.c (синус):

[Smerig]

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

[amarao]

Упс, вчитался в ассемблер. Был неправ, гцц просто сожрало ненужную инструкцию.

[mace]

Вы не учитываете:
а) оптимизацию компилятора, который может отсекать некоторые ветви кода, когда видит, что результат нигде не используется;
б) то что у вас результат накапливается в переменной b, которая быстро стремится к нулю. Функция sin(x) обрабатывает ноль как особый случай.
Попробуйте потестировать следующие примеры:

#include <stdio.h>
#include <math.h>

void main(){
	int a;
	double b = 1;
	for(a=0;a<50000000;a++){
		if(a&1) {
			b = sin(b);
		}
		else {
			b = sin(1-b);
		}
	}
	printf("%lf\n", b);
}

#include <stdio.h>
#include <math.h>

void main(){
	int a;
	double b = 1;
	for(a=0;a<50000000;a++){
		if(a&1) {
			b = b/0.3;
		}
		else {
			b = 0.3/b;
		}
	}
	printf("%lf\n", b);
}

[amarao]

real 0m1.534s
user 0m1.520s
sys 0m0.016s

real 0m0.306s
user 0m0.308s
sys 0m0.000s

Да, ок, убедили, был неправ.

[amarao]

кстати, причина даже не в fdiv, а в том, что при делении gcc юзает mmx во все поля:

.L9:
        addl    $1, %eax
        divsd   %xmm1, %xmm0
        cmpl    $50000000, %eax
        je      .L8
.L4:
        testb   $1, %al
        jne     .L9
        movapd  %xmm1, %xmm2
        addl    $1, %eax
        cmpl    $50000000, %eax
        divsd   %xmm0, %xmm2
        movapd  %xmm2, %xmm0
        jne     .L4
.L8:
        movl    $.LC2, %edi
        movl    $1, %eax
        jmp     printf

сравнить с sin-версией, у которой таки call sin.

.L4:
        testb   $1, %bl
        jne     .L7
        movsd   .LC0(%rip), %xmm1
        subsd   %xmm0, %xmm1
        movapd  %xmm1, %xmm0
.L7:
        addl    $1, %ebx
        call    sin
        cmpl    $50000000, %ebx
        jne     .L4
        popq    %rbx
        movl    $.LC1, %edi
        movl    $1, %eax
        jmp     printf
        .cfi_endproc

[jcmvbkbc]

добавь -ffast-math -m32 — получишь fsin и никаких xmm, а всё равно синус медленнее.

[amarao]

… т.е. даже не mmx, а штатные AMD64 инструкции:

siyobik.info/index.php?module=x86&id=75

[dmbreaker]

Надо все же понимать как оптимизируют компиляторы, прежде чем приводить такие тесты.
И зачем double? Если float быстрее и часто достаточен.

[apangin]

А-а-а! Хочу такой же процессор, как у Вас, чтобы миллиард синусов вычислял за 1 секунду! :))
А то мой Core i7 сто миллионов итераций секунд 5 крутит!

Если серьезно, боюсь, Ваш тест неправилен. Похоже, компилятор выкинул неиспользуемые вычисления в обоих случаях. На самом деле, тест с синусом работает в 6-7 раз медленнее, чем с делением.

[nckma]

а вы уверены, что Ваши программы вообще работают?
в этих программах вычисляемое значение «b» в конечном итоге нигде не используется. Компилятор вполне мог скомпилировать программу без цикла вообще.

сделайте хотя бы вот так:

#include <stdio.h>
#include <math.h>
void main(){
double a;
double b=0;
for(a=0;a<1000000000;a++){
b=b+a/0.3;
}
printf("%f\n",b);
}

[ixSci]

Предполагать, что либо подобное заранее не имеет смысла. Оптимизировать нужно только тогда, когда профайлер Вам показал, что sin есть узкое место. Вы не можете знать как преобразует Ваш код компилятор, а следовательно и делать заявления, что этот код отработает быстрее, чем вот этот.

[mace]

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

[Aux]

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

[michurin]

Ну следующий шаг развития — целочисленные алгоритмы построения графики. Очень советую двинуться в этом направлении. Обещаю — вам понравится. Успехов! Отличная статья!

[ExxY]

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

[Xao]

напомните решение?

[jcmvbkbc]

Для каждой вершины многоугольника компонента Z векторного произведения векторов выходящих из этой вершины в две соседние имеет один и тот же знак.

[tagir_valeev]

Да, векторное произведение векторов — тоже очень нужная штука, просто я не хотел перегружать статью :-)

[jcmvbkbc]

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

[aumeena]

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

[graninas]

Спасибо!

Еще по теме: некто Винни пишет о том же самом: что вместо сложных вычислений можно использовать простые и быстрые.
Угол между двумя векторами: users.livejournal.com/_winnie/237714.html
Пересечение двух отрезков: users.livejournal.com/_winnie/152327.html#cutid1

[Foror]

Спасибо за статью :) В последнее время веб-программирование утомляет и превращается в рутину, решил для разнообразия сделать игру в свободное время. И столкнулся с тем, что позабыл большую часть геометрии и алгебры :(

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

[0re1]

rghost.ru/2886683
Возможно, будет полезно

[sba]

404 страницы не существует

[middle]

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

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

[tagir_valeev]

Да, вы правы. Результат вращения разный получится. Уберу про тождество.
А с тангенсом надо аккуратно — он в бесконечность может уйти, если поворачивать на 180°.

[Julles]

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

[Benderlidze]

у нас в универе тут же был курс «ком. графики» где все эти матрицы и повороты показывали на примерах.

[Julles]

у нас был просто курс «высшей математики». правда, факультет экономический, и потому часть задач имела отношение к бизнесу, но вот векторы прошли чем-то совершенно оторванным от реальности. пост сейчас прочла с большим интересом.

[fyga]

И объясняют. Естественно, не на экономических факультетах.

[Julles]

Почему же «естественно»?
В хорошем учебном заведении любую излагаемую теорию должны иллюстрировать практикой. Если вам с учебным заведением/преподавателем повезло, я могу за вас лишь порадоваться.

[fyga]

Потому что это выходит за рамки курса линейной алгебры. Линейная алгебра это чистая теория, которая применима в очень многих областях. Одна из этих областей — компьютерная графика, по которой есть отдельный курс. И вполне логично, что его не читают экономистам.

[Julles]

Статистики под рукой нет, но большинство людей, насколько мне известно, плохо воспринимают «чистую теорию». Наверняка и у вас были одноклассники, например, возмущавшиеся, что им необходимо изучать физику/химию/биологию, если им при поступлении в ВУЗ экзамены по этим предметам все равно сдавать не придется. Предположить как им могут пригодиться полученные знания в реальной жизни они не могли. Между тем, если бы преподаватель химии взяла бутылку «Спрайта» и вместе с учениками «расшифровала» состав, а преподаватель биологии обсудила преимущества подсолнечного масла с рекламным слоганом «не содержит холестерина», глядишь, мотивация была бы выше.

[fyga]

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

[Julles]

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

[fyga]

Ну если вопрос стоит таким образом… С теорией вероятности как-то проще. А где применять линейную алгебру экономистам я, например, придумать не могу.

[tronix286]

Увы, далеко не всегда и не везде возможно отказаться от синусов и косинусов… Когда нужно быстро молотить косинусы и синусы в цикле — использую только таблицы до сих пор, ибо как заметили выше, fsin и fcos — тормозные операции даже на современных CPU.
Вот кстати набросал пример небольшой — вращающийся тор. Вряд-ли можно вращать точки не через чинус-косинус: Пример 3D Tor

[tagir_valeev]

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

Lookup tables — это тоже очень хорошо.

[Sone]

Как один из тех программистов который любит использовать тригонометрию:) Автору спасибо за статью, пойду векторную алгебру вспоминать:)

[XaBoK]

Я бы посоветовал аналитическую геометрию, а не векторную алгебру. Во всяком случае нас учили решать задачки по геометрии и тригонометрии векторами именно там, а на алгебре были совсем другие материи, не смотря на то, что одно тесно связанно с другим.

[Sone]

Спасибо за совет.

[iontsev]

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

[Vitamon]

а угол вектора (0,0) -> (x,y) можно как-то вычислить не прибегая к atan2?

[tagir_valeev]

Главный вопрос — не можно ли, а нужно ли. Как правило, в большинстве случаев не нужно. Если вам кажется, что нужно, возможно, вы что-то не учли.

[Refridgerator]

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

в Mathematica

Значение для поворота (и масштабирования при необходимости) r тоже можно задать константно (например, как 1+i) или получить его в результате операций над другими комплексными числами.

Отражённый луч ещё проще считается: a*сonjugate(b/a) (где a это отражающий вектор и неважно, в какую именно сторону он направлен), и не менее легко это всё алгебраически упрощается при цепочке преобразований.