AiC Форум

ED 29 дек 2006, 15:59

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

**fyrex** 07 мар 2007, 14:20

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

**annoynimous** 08 мар 2007, 17:10

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

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

**fyrex** 13 мар 2007, 21:39

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

**annoynimous** 14 мар 2007, 01:21

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

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

Если надо за 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 15 мар 2007, 16:49

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

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

**annoynimous** 15 мар 2007, 18:55

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

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

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

ED 16 мар 2007, 00:12

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

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

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

**annoynimous** 16 мар 2007, 01:01

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

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

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

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

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

**Q-Master** 16 мар 2007, 10:28

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

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

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

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

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

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

ED 16 мар 2007, 13:23

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

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

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

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

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

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

**annoynimous** 17 мар 2007, 22:15

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

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

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

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

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

ED 19 мар 2007, 01:38

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

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

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

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

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

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

AiC Форум

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

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

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

Кто сейчас на конференции