Линейная интерполяция

[ED]

Может кто знает алгоритм линейной интерполяции без делений? Брезенхем не интересует по причине фиксированного шага равного 1 или -1.

[fyrex]

Если ты будеш использовать шкалу от 0 до 1, то деление не понадобится - только умножение и сдвиг.

[annoynimous]

[quote="ED"]Может кто знает алгоритм линейной интерполяции без делений? Брезенхем не интересует по причине фиксированного шага равного 1 или -1.[/quote]

Вообще без делений не бывает. Если надо путь от a до b пройти за n шагов, то сначала надо посчитать шаг x=(b-a)/n (делением), а потом его в фиксированной точке прибавлять к сумме, которая сначала инициализируется a.

[fyrex]

Соответственно, если выбрать шкалу интерполяции равной 1.0,
читай "степени 2", то деление разумеецо не понадобицо !

[annoynimous]

[quote="fyrex"]Соответственно, если выбрать шкалу интерполяции равной 1.0,
читай "степени 2", то деление разумеецо не понадобицо ![/quote]

Фурех, ты не на пьянке, выражовывайся точнее! =))))


Если надо за N шагов проинтерполировать от A (16бит) до B (16бит), то делается так:
считается смещение за 1 шаг d=65536*(B-A)/N, d - 16.16 (фикс. точка), потом инициализируется сумматор S числом 65536*A (16.16 тоже) и к нему N раз добавляется смещение d. Из старших 16 бит суммы S берётся значение на текущем шагу.

Из формулы видно, что не делить можно в 2 случаях:
1 - если N - степень двойки,
2 - если N - константа всегда (тогда деление заменяется умножением).

[ED]

[quote="annoynimous"]

Из формулы видно, что не делить можно в 2 случаях:
1 - если N - степень двойки,
2 - если N - константа всегда (тогда деление заменяется умножением).[/quote]

А ведь можно и по брезенхему от A до B за N шагов без делений и умножений. Для меня тема неактуальна...

[annoynimous]

[quote="ED"][quote="annoynimous"]

Из формулы видно, что не делить можно в 2 случаях:
1 - если N - степень двойки,
2 - если N - константа всегда (тогда деление заменяется умножением).[/quote]

А ведь можно и по брезенхему от A до B за N шагов без делений и умножений. Для меня тема неактуальна...[/quote]

1 - ну попробуй текстуратор брезенхемом сделать, гыгы.
2 - если A и B целые, а |A-B|>N, то шаг будет или int((B-A)/N), или на единицу больше. Опять деление.
3 - брезенхем просто бессмысленен для фиксед-поинт.

[ED]

[quote="annoynimous"]

2 - если A и B целые, а |A-B|>N, то шаг будет или int((B-A)/N), или на единицу больше. Опять деление.
3 - брезенхем просто бессмысленен для фиксед-поинт.[/quote]

Я тебя не понимаю, какое деление?
Если B-A>N, то брезенхемом все интерполируется нормально.

Причем здесь фикс.пнт вообще?
Чем фикс.пнт отличается от обычного целого?

[annoynimous]

[quote="ED"][quote="annoynimous"]

2 - если A и B целые, а |A-B|>N, то шаг будет или int((B-A)/N), или на единицу больше. Опять деление.
3 - брезенхем просто бессмысленен для фиксед-поинт.[/quote]

Я тебя не понимаю, какое деление?
Если B-A>N, то брезенхемом все интерполируется нормально.
[/quote]
Я тебя - тоже. Поясни. На примере рисования линии с углом более 45 градусов (y=(234/123)*x), точки ставятся так, чтобы на каждой координате x 1 точка. Я представляю себе брезенхем только когда наклон менее 45 градусов.

[quote]
Причем здесь фикс.пнт вообще?
Чем фикс.пнт отличается от обычного целого?[/quote]
Тогда почему нету ни одного текстуратора на брезенхеме, а все на DDA?

[Q-Master]

[quote="annoynimous"][quote="ED"][quote="annoynimous"]

2 - если A и B целые, а |A-B|>N, то шаг будет или int((B-A)/N), или на единицу больше. Опять деление.
3 - брезенхем просто бессмысленен для фиксед-поинт.[/quote]

Я тебя не понимаю, какое деление?
Если B-A>N, то брезенхемом все интерполируется нормально.
[/quote]
Я тебя - тоже. Поясни. На примере рисования линии с углом более 45 градусов (y=(234/123)*x), точки ставятся так, чтобы на каждой координате x 1 точка. Я представляю себе брезенхем только когда наклон менее 45 градусов.

[quote]
Причем здесь фикс.пнт вообще?
Чем фикс.пнт отличается от обычного целого?[/quote]
Тогда почему нету ни одного текстуратора на брезенхеме, а все на DDA?[/quote]

Насколько я помню Брезенхем учитывает углы более 45 градусов без проблем. Там тупо меняются приращения местами. Это еще в какой-то древнючей книжке по 2д-3д графике написано. Дома у меня валяется.

[ED]

[quote="annoynimous"][quote="ED"][quote="annoynimous"]

2 - если A и B целые, а |A-B|>N, то шаг будет или int((B-A)/N), или на единицу больше. Опять деление.
3 - брезенхем просто бессмысленен для фиксед-поинт.[/quote]

Я тебя не понимаю, какое деление?
Если B-A>N, то брезенхемом все интерполируется нормально.
[/quote]
Я тебя - тоже. Поясни. На примере рисования линии с углом более 45 градусов (y=(234/123)*x), точки ставятся так, чтобы на каждой координате x 1 точка. Я представляю себе брезенхем только когда наклон менее 45 градусов.[/quote]

Стоять!!!
Ты что-то перепутал!
Я проверяю в каком положении линия, если по y меньше чем по х, то просто меняю в брезенхеме расчет местами. Могу показать свой исходник на асме 68к отрисовки wire-полигона по брезенхему. Линии рисуются под любыми углами. Используется фиксед.пнт 16:8(мне так больше нравится;)). Все летает, нет никаких делений, умножений. Только сложения, условия и сдвиг.

[quote]
Тогда почему нету ни одного текстуратора на брезенхеме, а все на DDA?[/quote]

Я не видел ни одного текстурирования, поэтому ничего сказать не могу.

[annoynimous]

[quote="ED"]
Я проверяю в каком положении линия, если по y меньше чем по х, то просто меняю в брезенхеме расчет местами. Могу показать свой исходник на асме 68к отрисовки wire-полигона по брезенхему. Линии рисуются под любыми углами. Используется фиксед.пнт 16:8(мне так больше нравится;)). Все летает, нет никаких делений, умножений. Только сложения, условия и сдвиг.
[/quote]
Вот о чём и речь, что во-1 брезенхем без делений только когда шаг 0 или 1, во-2, допускает обобщение на случай, когда шаг N или N+1 (опять же для линий или заполненных полигонов), но требует в этом случае деления, и как бы не 1 умножения ещё, в-3 брезенхем как таковой не есть линейная интерполяция в общем виде, а лишь особо частный случай, оптимизированный для целочисленных координат линии и определённого шага.

[quote]
[quote]
Тогда почему нету ни одного текстуратора на брезенхеме, а все на DDA?[/quote]

Я не видел ни одного текстурирования, поэтому ничего сказать не могу.[/quote]

Я думал, что ты знаешь что-то, чего не знаю я, а оказалось - наоборот... =))

[ED]

[quote="annoynimous"][quote="ED"]

[quote]
Вот о чём и речь, что во-1 брезенхем без делений только когда шаг 0 или 1, во-2, допускает обобщение на случай, когда шаг N или N+1 (опять же для линий или заполненных полигонов), но требует в этом случае деления, и как бы не 1 умножения ещё, в-3 брезенхем как таковой не есть линейная интерполяция в общем виде, а лишь особо частный случай, оптимизированный для целочисленных координат линии и определённого шага.[/quote]

Так ведь можно использовать приращение 1, просто в некоторых случаях цикл будет длиннее.

[quote]
Тогда почему нету ни одного текстуратора на брезенхеме, а все на DDA?[/quote]

[quote]
Я не видел ни одного текстурирования, поэтому ничего сказать не могу.[/quote]

[quote]
Я думал, что ты знаешь что-то, чего не знаю я, а оказалось - наоборот... =))[/quote][/quote][/quote]

Если ты про текстурирование, то я писал линейное, просто не видел никогда чужого, да и где мне его видеть? Делал все делениями, переделывать уже ничего не буду.