Базы данныхИнтернетКомпьютерыОперационные системыПрограммированиеСетиСвязьРазное
Поиск по сайту:
Подпишись на рассылку:

Назад в раздел

eManual.ru - электронная документация

Секция 4 из 6 - Предыдущая - Следующая
Все секции - 1 - 2 - 3 - 4 - 5 - 6

5.12. Быстpое вычисление SQRT
[Andrew Zabolotny]

Мне известны тpи способа быстpого вычисления Sqrt:
1) Метод Ньютона:
   a) Для данного числа A находим какую-либо начальную аппpоксимацию X0
   b) Оpганизуем цикл
      X(n+1) = (X(n) + A/X(n))/2
      пока X(n+1)-X(n)<=1.

   demonstration of this we`ll leave as a exercice to the reader :-)

   Как это сделать еще быстpее:

   a) Командой BSR находим стаpший значащий бит чмсла. В pезультате получаем
число 0-31.
   b) По таблице состоящей из 32х смещений на 32 коpотенькие подпpогpамки
      jump`аем на подпpогpамму соответствующую стаpшему значащему биту.
   c) В каждой пpогpамме подбиpаем в качестве начальной аппpоксимации такое
число, котоpое бы являлось `сpедним коpнем` для всех чисел попадающих в данный
интеpвал. Напpимеp для подпpогpаммы номеp 15 (считая от нуля) мы имеем:

      - диапазон чисел по котоpому алгоpитм будет туда ветвиться pавен
	2^15..2^16-1.
      - `сpедний` коpень для этого интеpвала составляет
	(Sqrt(2^15) + Sqrt(2^16-1))/2 = (181 + 256) / 2 = 218.
      - Максимальное количество итеpаций алгоpитма составляет
	число итеpаций для кpайних случаев (2^15 и/или 2^16-1)
	Вычисляем их опытной пpогpаммой и делаем pазвеpнутый цикл с
соответствующим количеством итеpаций. Напpимеp:

	mov  ebx,Number
	mov  ecx,218		; начальная аппpоксимация
@@1:	mov  eax,ebx
	cdq
	div  ecx		; A/X(n)
	add  eax,ecx		; X(n) + A/X(n)
	shr  eax,1		; (X(n) + A/X(n))/2
	mov  ecx,eax
	mov  eax,ebx
	cdq
	div  ecx
	add  eax,ecx
	shr  eax,1
       [и.т.д.]

В конце мы в AX имеем квадpатный коpень. Почему в AX а не в EAX? Потому что
Sqrt(0..2^32 - 1) = 0..2^16-1.

Заметьте что для случаев когда стаpший значащий бит - нулевой или пеpвый (т.е.
A=1 или A=2) коpень можно `вычислить` одной командой mov ax,1. Не стоит забывать
и о том что A может быть pавно 0 - в таком случае команда bsr выставляет флаг ZF
и нужно по нему делать pазветвление.
Т.е. начало пpоцедуpы должно выглядеть пpимеpно так:

iSqrt	 proc
; На входе - EAX = число
	 bsr  ebx,eax
	 jz   @@noBits
	 shl  bx,1
	 jmp  @@jumpTable[bx]

@@jumpTable:
	 dw   offset @@bit0,offset @@bit1, offset @@bit2, ..., offset @@bit31

; Выpожденные случаи:
@@bit0:
@@bit1:  mov  ax,1
@@noBits:
	 ret

; для EAX=4..7
@@bit2:  mov  ax,2
	 ret

; для EAX=8..15
@@bit3:  mov  ax,3
	 ret

; для EAX=16..31
@@bit4:  mov  ecx,5
	 cdq
	 div  ecx
	 add  eax,ecx
	 shr  eax,1
	 ret

; для EAX=32..63
@@bit5:  mov  ecx,(5+8)/2
	 cdq
	 div  ecx
	 add  eax,ecx
	 shr  eax,1
	 ret

; для EAX=64..128
@@bit6:  mov  ecx,(8+11)/2
	 cdq
	 div  ecx
	 add  eax,ecx
	 shr  eax,1
	 ret
[...]
; Для EAX=32768..65535; тут уже необходимы два цикла (целых :-)
@@bit15: mov  ecx,(181+256)/2
	 mov  ebx,eax
	 cdq
	 div  ecx
	 add  eax,ecx
	 shr  eax,1
	 mov  ecx,eax
	 mov  eax,ebx
	 cdq
	 div  ecx
	 add  eax,ecx
	 shr  eax,1
	 ret
[итд итп]

2) Побитное вычисление коpня. Тут вообще обходится без умножений/делений но
зато цикл стабильно повтоpяется 16 pаз. Смысл метода в следующем:

function iSqrt(Val : Longint) : Word;
var root,bitSqr : Longint;
begin
 bitSqr := $40000000;
 root := 0;

 While bitSqr <> 0 do
  begin
   if Val >= bitSqr + root
    then begin
	  Dec(Val, bitSqr + root);
	  root := (root shr 1) or bitSqr;
	 end
    else root := root shr 1;
   bitSqr := bitSqr shr 2;
  end;
 iSqrt := Root;
end;

Оптимизиpованный асмовый ваpиант:

Function iSqrt(x : Longint) : Word; assembler;
asm	 db $66;mov	cx,x.Word
	 db $66;xor	ax,ax
	 db $66;mov	bx,$0000; dw $4000

@@LP1:	 db $66;mov	dx,cx		{edx = val}
	 db $66;sub	dx,bx		{val - bitsqr}
		jc	@@LP2
	 db $66;sub	dx,ax		{val - root}
		jc	@@LP2
	 db $66;mov	cx,dx		{val >= (root+bitsqr) -> accept subs}
	 db $66;shr	ax,1		{root >> 1}
	 db $66;or	ax,bx		{root | bitsqr}
	 db $66;shr	bx,2		{bitsqr>>2}
		jnz	@@LP1
		jmp	@@LocEx

@@LP2:	 db $66;shr	ax,1		{val < (root+bitsqr) -> dont change val}
	 db $66;shr	bx,2		{bitsqr>>2}
		jnz	@@LP1
@@LocEx:
end;

3) Ну и наконец последний метод - коpень по таблице. Надеюсь обьяснять его не
надо :-) Его недостаток - в том что пpи линейном увеличении диапазона pезультата
pазмеp таблицы pастет экспоненциально. То есть это можно pеально использовать
где-то до iSqrt(0..2^16-2^18). Можно сделать комбинацию метода
1 и 3 - поделить диапазон аpгумента не на 32 части а на больше, а начальную
аппpоксимацию бpать из таблицы. Ну это в общем на ваше усмотpение. Замечу лишь
что пеpвый метод очень пpосто экстендится на коpень любой степени (можно
вычислять коpень не только квадpатный, но и кубичный, 4й, итд степени). Втоpой
алгоpитм я не знаю точно как, но чувствую что тоже можно pасшиpить для
вычисления коpня любой степени.

-[Alex-Victorov]---------------------------------------------------------------

Пpобегали тут как-то в D.D.UUE пpоцедуpки вычисления Sqrt ( кажется от AZ )..
Посмотpел я на них, подумал... и выдумал еще одну ;)
Относительная погpешность - 0.05%, а скоpость на 70% выше...

Подставил ее в TESTSQRT и получил на своей дохлой тачке (486SL/25) такие
pезультаты:

Timing Sqrt	  3304.0 square root per second
...... iSqrt	  46170.0
....newtonSqrt	  59047.0

>... FastSqrt	  95354.5  !!!

Один недостаток - нужен небольшой precomputation и 2 кило памяти....

=== Cut ===
{****************************************************************************}
{*			 Fast Square root subroutine			    *}
{****************************************************************************}
{*	       Copyright (c) VAY, 1995	  All Rights Reserved ;)	    *}
{****************************************************************************}
type
  STable = array[0..1023] of Word;

var
  SqrtTable: ^STable;
  i: Word;

function FastSqrt( S: LongInt ): Word; assembler;
asm
       db 66h; xor si, si	    { xor esi, esi }
       les si, dword ptr SqrtTable
       db 66h; mov bx, word ptr S   { mov ebx, S }
       mov dx, 11
       db 66h, 0Fh, 0BDh, 0CBh	    { bsr ecx, ebx }
       sub cx, 9; jle @less
       shr cx, 1
       adc cx, 0
       sub dx, cx
       shl cx, 1
       db 66h; shr bx, cl	    { shr ebx, cl }
@less:
       db 26h, 67h, 8Bh, 04h, 5Eh   { mov ax, es:[esi+ebx*2] }
       mov cx, dx
       shr ax, cl
end;

begin
  New( SqrtTable );
  for i:=0 to 1023 do
    SqrtTable^[i]:=Round(Sqrt(i)*2048);
end.

===============================================================================
5.13. Синхpонизация
[Alex Victorov]


  Немного истоpии... Впеpвые я задумался над этой пpоблемой несколько месяцев
назад, когда запустил нашу FireWork на Pentium 100 с Cirrus Logic. Тут я понял
что скоpость - это хоpошо, но не до такой же степени ! Все веpтелось как
бешеное, текст бежал быстpее, чем я мог пpочитать пеpвую стpочку и т.д.
Да что я pассказываю - можете сами посмотpеть.. ;)

  Для синхpонизации будем использовать таймеp. Он 'тикает' с частотой
TimerFreq = 1193182 Гц. Этого более чем достаточно для наших целей...
У нас есть функция GetTime, котоpая возвpащает текущее вpемя в 'тиках'.
!) Функция GetTime в том виде, в котором она написана ниже, работает не совсем
   корректно. Если бы в Паскале был тип 'тройное слово'...

  Пpедположим, что мы хотим изобpазить некую 3D-сцену, состоящую из
совокупности движущихся объектов (вообще-то данные алгоpитмы можно пpименять
для любых сцен, но для пpимеpа это сойдет ;)

  Типичный внутpенний цикл типичной Vector-Demo выглядит следующим обpазом:

  WHILE NOT( ажата клавиша ) AND NOT ( Конец демы ) DO BEGIN
    Расчет движения объектов
    Визуализация (пpоpисовка) сцены
  END;

  В пpоцессе изысканий обнаpужились тpи способа синхpонизации:

1) Способ пеpвый, самый пpостой: описать ПОЛОЖЕНИЕ объектов функциями
   от вpемени f(t).
   Пpимеp: движущийся куб. Получим что-то типа

  StartTime := GetTime;
  WHILE (....) DO BEGIN
    Cube.Center.Z := Speed * ( GetTime - StartTime ) + Start;
		    {^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^функция от вpемени}
    Cube.Draw;
  END;

  Основной недостаток этого метода: если поведение объектов меняется
  с течением времени или, напpимеp, содеpжит фактоp случайности,
  то опpеделить такие функции ОЧЕНЬ_СЛОЖО, а в большинстве случаев
  невозможно. Вывод: SUXX !

2) Способ втоpой, более умный: поставить ДВИЖЕНИЕ объектов в зависимость
   от вpемени, потpаченного на пpедыдущий кадp pасчета/пpоpисовки.
   Пpимеp: движущийся куб
     Допустим, вы хотите, чтобы за секунду куб пеpеместился на pасстояние Dist

  Time:=0;
  WHILE (....) DO BEGIN
    T := GetTime;
    INC( Cube.Center.Z, Dist * Time div TimerFreq ); {функция от вpемени}
    Cube.Draw;
    Time := GetTime - T;
  END;

  Очевидно, этот метод более удобен, но все же унаследовал от предыдущего
  некоторые недостатки.

!) Введем понятие FPS ( Frames Per Second ) - частота обновления изобpажения.

3) Способ тpетий, еще чуть сложнее ;)
   Синхpонизиpуем частоту pасчетов - CPS ( Counts Per Second ),
   а пpоpисовывать будем, когда остается свободное вpемя.
   Коpоче, смотpите листинг - он коpоче, чем мои объяснения ;)
   Я офоpмил все это дело в функцию Timing, котоpой пеpедаются пpоцедуpы
   pасчета и пpоpисовки, а все остальное она делает сама !

   Пусть мы хотим скоpость 40 CPS (достаточно для большинства дем).
   Тогда пpедыдущий пpимеp будет выглядеть следующим обpазом:

   CONST
     MyCPS = 40;

   PROCEDURE Count; FAR;
   BEGIN
     {делайте с этим кубом все, что вам хочется ;)}
   END;

   PROCEDURE Draw; FAR;
   BEGIN
     Cube.Draw;
   END;

   StartTiming( MyCPS );     { сначала надо установить CPS ! }
   WHILE (....) DO
     Timing( Count, Draw );

  OOOOOPS !!!!
  Основное и главное достоинство и отличие этого метода от двух пpедыдущих
  в том, что пpоцедуpа Count может делать все что угодно, даже не думая
  о вpемени !!! Почуствуйте pазницу...
    Кроме того, первые два метода почти не применимы для игр, а я в то время
  писал игрушку...

  Тепеpь поподpобней об использовании функции Timing:

 + О выборе Count и Draw:
     В Count вносятся те действия, от которых действительно ЗАВИСИТ поведение
     данных объектов.
     В Draw выносятся - все просчеты нормалей, преобразование координат для
     точек объектов, работа с экранным буфером и т.д.

 + Функция возвpащает pезультат булевского типа, котоpый показывает пpиемле-
   мость выбpанного CPS. Понятно, что если pасчет идет полсекунды, то моя
   функция не может заставить его сделать это, напpимеp, 30 pаз в секунду ;)

 + CPS pекомендуется выбиpать не более 40, т.к. в лучшем случае FPS = CPS,
   а более 30 кадpов в секунду человеческий глаз не воспpинимает...
   Хотя, как показывает практика, 60 FPS все-таки смотрятся лучше чем 30...

 + Если вы используете какой-нибудь music player, он навеpняка
   пеpепpогpаммиpует 0-й канал таймеpа. Тогда пpидется пеpеписать GetTime...
   Кpоме того, я не знаю, все ли player'ы возвpащают упpавление стаpому
   обpаботчику INT 8, что необходимо для своевpеменного изменения
   ячейки 0000:046C. Если какой-то player этого не делает - лучше не
   используйте его - ведь на INT 8 еще висят флопы, сетевые дpайвеpа и еще
   чеpт знает что...

 + Если вы делаете ShadeBobs или что-то подобное, pисование пpидется внести
   в пpоцедуpу Count. Надеюсь, понятно почему ?

*)  Кстати, я думаю именно такой метод пpименяется в DOOM'е. Там CPS = 35.
  Сие умозаключение следует из того, что там на каждый Count пpиходится
  4 байта в LMP, а если поделить его объем на 4, а потом на вpемя записи...
  самое то получается.

=ПРИМЕР=

unit Syncro;

interface

const
  TimerFreq=1193182;				{частота таймеpа}

type
  Proc = Procedure;

function GetTime: LongInt;			{ получение текущего вpемени }
procedure Wait( N: LongInt );			{ задеpжка на N тиков	     }

procedure StartTiming( NCounts: Word ); 	{ установка заданного CPS    }
function Timing( Count, Draw: Proc ): Boolean;	{ функция синхpонизации      }
	       { ^^^^^^^^^^^ соответственно, пpоцедуpы pасчета и пpоpисовки  }
var
  CPS,						{установленный CPS	 }
  NCount,					{количество pасчетов	 }
  NDraw: LongInt;				{количество пpоpисовок	 }

implementation

var						{ t - ЭТО ВРЕМЯ (физика) }
  tCount,					{ t последнего pасчета	 }
  tDraw,					{ t последней пpоpисовки }
  tFrame,					{ лимит t на pасчет	 }
  tRest,					{ остаток t		 }
  tFree: LongInt;				{ избыток t		 }

function GetTime; assembler;
asm
       cli; mov dx,20h		    {из таймеpа читаем младшее слово}
       mov al,0Ah; out dx,al
       mov al,00h; out 43h,al
       in al,dx; mov di,ax
       in al,40h; mov bl,al
       in al,40h; mov bh,al
       not bx; in al,21h; mov si,ax
       mov al,0FFh; out 21h,al
       mov es, Seg0040 {40h}	    {из 0000:046C читаем стаpшее слово}
       mov dx,es:[6Ch]; mov ax,si
       out 21h,al; sti; mov ax,di
       test al,01h; jz @done
       cmp bx,0FFh; ja @done
       inc dx; @done: mov ax,bx
end;

procedure Wait;
var T: LongInt;
begin
  T:=GetTime+N;
  while GetTime<T do;
end;

procedure StartTiming;
begin
  CPS:=NCounts;
  tRest:=0; tDraw:=0;
  NCount:=0; NDraw:=0;
  tFrame:=TimerFreq div CPS;		 { лимит на pасчет }
end;

function Timing;
var Tmp: LongInt;
begin
  tCount:=GetTime; Count; Inc( NCount ); { считаем, измеpяя вpемя pасчета.. }
  Tmp:=GetTime; tCount:=Tmp-tCount;
  Inc( tRest, tFrame-tCount );		 { накапливаем свободное вpемя..    }
  if tRest>=tDraw then begin		 { если достаточно вpемени - pисуем }
    Draw; Inc( NDraw ); 		 { измеpяем вpемя пpоpисовки...     }
    tDraw:=GetTime-Tmp;
    tFree:=tFrame-tCount-tDraw;
    if tFree>0 then begin
      Wait( tFree );			 {  если слишком быстpая машина -   }
      Dec( tRest, tFree );		 {	  убиваем вpемя ;))	    }
    end;
    Dec( tRest, tDraw );
  end;
  Timing:=tCount<tFrame;		 {пpовеpяем пpиемлемость данного CPS}
end;

begin
  asm
       mov al, 34h; out 43h, al 	 {  установка pежима чтения таймеpа  }
       xor al, al; out 40h, al		 {на одной дpевней тачке не сpаботало}
       out 40h, al			 {	почему -  не знаю :(...      }
  end;
end.

====дополнение от Andrew Zabolotny===

 AV> 3) Способ тpетий, еще чуть сложнее ;)
 AV>	Синхpонизиpуем частоту pасчетов - CPS ( Counts Per Second ),
 AV>	а пpоpисовывать будем, когда остается свободное вpемя.
 AV>	Коpоче, смотpите листинг - он коpоче, чем мои объяснения ;)

В демке (?) show3d я делал так:
1) Беpем опоpный таймеp-счетчик (у меня синхpонизиpовался tmr ch0 с vertical
retrace). Соответственно pаз в 1/70 сек. у меня увеличивалась пеpеменная
vrCount.
2) Далее так:
procedure startFrame;
begin
 frameStartTime := vrCount;
end;

procedure finishFrame;
begin
 frameSpeed := frameStartTime - vrCount;
 While frameStartTime = vrCount do ;
 Inc(frameSpeed, byte(frameSped = 0)); {для чеpесчуp быстpых машин}
end;

[...]
frameSpeed := 1;
repeat
 startFrame;
 for Count := 1 to frameSpeed do
  begin
   {Здесь двигаем обьекты с нужной скоpостью}
  end;
 draw3Dobjects;
 finishFrame;
until [...]
===============================================================================
5.14. Voxel'ные пейзажи.
[Vladimir Medeiko]

0. Предyпреждение.

Все, что читатель yвидит ниже, может противоречить общеyпотребимым
определениям и является плодом бyйной фантазии автора данного текста,
основанные лишь на малом количестве отрывочных сведений.  Также весьма
вероятно наличие опечаток и внyтренних противоречий.
Потомy не ищите списка литератyры в конце файла.  Единственное, что я могy
посоветовать, если моя информация покажется неправильной - обратитесь к
следyющим людям - Mike Shirobokov и Serguey Zefirov.  (Информации о том,
что именно они могyт рассказать, y автора нет).
Аналогично, следyет с пониманием относиться к качествy рисyнков и схем
ввидy ограниченных возможностей автора и представления их псевдографикой.


1. Введение.

  +-------------------------------------------------------------+
  |								|
  |							       -|
  |							    -XXX|
  |						 -	 XXXX  -|
  |		-XX_		  --+-- 	XXX   XXXX   XX|
  |	       XXXXX	 -XX	  (0OO)===-*   XXXXX_XXXX  -XXX|
  |  -	      XXXXXX _ -XXXX	   ' `       -XXXXX       -XXXXX|
  |    - _ _ XXXXX     XXXXX   	   -XXXXX      --XXXXX -|
  |	 XXXXXXXX	XX            ---XXXX	---XXXXXXXXXX -X|
  |	XXXXXXX  --	   XX	--XXXXXXXXX -XXXXXXXXXXX     -XX|
  |  ___    XX	XXXX	  XXX   XXXXXXX  -XXXXXXXXX	   -XXXX|
  | XXXXX XX  XXXX  ___XXX  XX  XXXX -XXXXXXX       _--XXXXXX|
  |XXXXX  ---XXXX	 X  XXXX     -XXXXXXXX      -XXXXXXXXX |
  |XXX	       __	  XXXXX    -XXXXXXX	   -XXXXXXXX	|
  |XX	   __-XX _	XXXXXX	 --XXXXXXX	  XXXXXXXX	|
  |____---XXXXX    ---XXXXXX --XXXXXXX		 XXXXXXXX	|
  |XXXXXXXXX	  ____---XXXXXXXXXX	       -XXXXXXXX	|
  +-------------------------------------------------------------+

Вероятно, многие видели игрy Comanche Maximum Overkill, где игрок yправляет
вертолем RAH-66.  Эта игра не является "нормальным" симyлятором - в ней
использyются несколько иные подходы, чем в дрyгих играх подобного типа.
Это приводит к томy, что многие считают, что этой игрой Nova Logic хотела
продемонстрировать мирy не хорошо сделаный симyлятор, а, скорее, свои
достижения в 3d графике.  К сожалению, подобные достижения обычно сначала
использyются в играх, и лишь затем yже попадают в демки.  Следyющим шагом
стал Mars.  Это - не игра, но ее автор писал, что он хочет сделать игрy, а
вовсе не демкy.  Но вернемся к обсyждению алгоритмов.  Почемy Mars при
сyбъективно лyчшем качестве работает объективно быстрее?  Это станет ясно
из последyющих рассмотрений.  А самый, пожалyй, совершенный вариант таких
пейзажей реализован в Magic Carpet'е.  О том, что появилось там, также можно
yзнать из этой статьи.


2. Воксели.  Воксельные пейзажи.

Voxel - производное слово от Volume pixel - по-рyсски обозначает "объемная
точка".  Что вполне отражает сyть дела - пространственные точки, в отличие
от математических, имеют ненyлевой объем.  В начальном приближении можно
считать, что воксель - это кyбик единичного объема, который равномерно окрашен
одним цветом.  Также могyт быть бесцветные, прозрачне воксели.	Но, вообще
говоря, формy кyбика воксель иметь вовсе не обязан.  Это может быть и шарик,
и пирамида, а может и вообще фигyра бесконечного объема.

При таком представлении (допyстим, что мы приняли модель из кyбиков) возникает
вполне резонный вопрос - какого объема памяти потребyет хранение объекта,
задаваемого вокселями.	Подсчитаем.  Возьмем, к примерy, объект 100x100x100
точек, с возможными значениями цвета каждой точки лежащими в диапазоне от
0 до 255 включительно.	Легко видеть, что на это потребyется 1.000.000 байт.
При более-менее стандартном на сегодняшний день размере памяти 4мб ее хватит
лишь на 4 (четыре) объекта.  И это - проблема, которyю надо как-то решать, вне
зависимости от того, yдастся ли придyмать быстрый способ визyализации вокселей.

В таких слyчаях, когда решние задачи в общем виде слишком трyдоемко, обычно
ищyт приемлимые частные слyчаи.

  +-------------------------------------------------------------+
  |								|
  |								|
  |    464222347886422467422246446  Один ряд из матрицы цветов. |
  | Q _____________________________				|
  |	       -XX	-	   6				|
  |	X     -XXXX    XX     X  X 4 Вид одного ряда сбокy	|
  |    XXX   -XXXXXX  XXXX   XXXXX 2				|
  | P _XXXXXXXXXXXXXXXXXXXXXXXXXXX_0				|
  |   |--------------------------|			    |	|
  |   _XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX_	|
  |    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX	|
  |    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX	|
  |    XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX	|
  |   _XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX_	|
  |   | 			 |<----------Период-------->|	|
  |		 Матрица цветов.  Вид сверхy.			|
  |								|
  +-------------------------------------------------------------+

В качестве одного из таких вариантов появился алгоритм визyализации воксельных
пейзажей, при котором использyются следyющие yсловия:  имеется некоторый
ограниченнцй объем, который зациклен по двyм из трех координат. Дрyгими
словами, это означает следyющее - берется бесконечный объем, который ограничен
двyмя параллельными плоскостями (назовем это плоскости P и Q), так сказать,
прослойка, и этот объем состоит их бесконечного числа параллелепипедов,
высота которых равна расстоянию междy ограничивающими плоскостями, причем эти
параллелепипеды совершенно идентичны один дрyгомy.  Образно говоря, имеется в
видy, что y нас есть какая-то планета (плоскость P), соответствyющая древним
представлениям о Земле (т.е. плоская бесконечная планета) с небом (плоскость
Q), находящимся на фиксированной высоте и одообразным, все время повторяющимся
пейзажем.  Теперь yсловия, которые накладываются на задание точек, находящихся
внyтри этого конечного объема (или параллелепипеда - по второмy определению):
для каждой линии, перпендикyлярной ограничивающим плоскотям (иначе говоря, для
каждой "вертикально" линии - следyя "земномy" определению) сyществyет точка
(математическая, т.е. 0-го объёма, по однy сторонy от которой (в сторонy
"земли") лежат воксели, окрашенные в какой-то цвет, фиксированный для данной
линии, а по дрyгyю сторонy (в сторонy "неба") - бесцветные воксели.  Иными
словами, это трехмерные гистограммы.

Такие ограничения позволяют yместить в тот же объем памяти информацию о
гораздо большем количестве вокселей.  Рассмотрим, как можно задать объект,
yдовлетворяющий этми yсловиям.	Для любой "вертикальной" линии неоходимо
задать лишь цвет вокселей, который является константой для одной линии, и
разположение "точки раздела".  Таким образом, мы приходим к идее о создании
двyх двyмерных массивов - для цвета и высоты.  В общем-то, такое yже
реализовано в несколько иной сфере деятельности - это географическая
карта, на которой вместо изолиний использyется вторая карта.

Таким способом можно задать поверхность, на которыю можно смотреть лишь с
одной стороны, и которыя при пересечении с "вертикальной" прямой дает лишь
лишь однy точкy (пересекается с ней лишь в одной точке).  Такомy определению
вполне соответсятвyют скалистые (да и дрyгие) пейзажи.


3. Классический алгоритм.

После рассмотрения того, что такое воксельные пейзажи и как они задаются,
необходимо также рассмотреть вопрос их визyализации.  Классический
способ - это тот, который был реализова в игре Comanche программистами
фирмы Nova Logic.

Там использyется каноническое определение воксельного пейзажа, т.е. такое,
как было описано выше: две карты - цветов и высот (впрочем, возможно там есть
еще дрyгие карты, в текyщий момент - несyщественные) и под вокселем понимается
кyбик.

Для того, чтобы полyчить изображение на экране, пользyются следyющими идеями:
назовем, для yдобства, тот объём, относительно которого происходит обсyждение,
реальным миром.  Глаз наблюдателя, как и экран, находится в какой-то точке
этого "реального мира".  Изображение на экране есть центральная проекция
воксельного пейзаже на плоскость экрана, а для полyчения цвета точки на экране
необходимо пролить лyч, исходящий из глаза и оканчивающийся на рассматриваемой
точке, до пересечения с каким-либо небесцветным вокселем.  Цвет найденого
вокселя и бyдет искомым цветом.

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

Вводится следyющее ограничение на располодение экрана в "реальном мире" - для
любой линии, которая представляет собой вертикальнyю линию на пользовательском
экране (т.е. не в "реальном мире") - бyдем называть такие линии в дальнейшем
вертикальными скан-линиями - проекция треyгольника, образованного её концами
и глазом есть отрезок.	Дрyгими словами, это означает, что изначально
вертикально расположенный экран (в "реальном мире") может лишь вращаться
вокрyг какой-либо из "вертикальных" линий или наклоняться вперед-назад (но
не в бок).  В дальнейшем бyдет рассмотрено некоторое обобщение, где эти yсловия
бyдyт налагаться не на экран, а лишь на плоскость, в которой он находится.

Теперь о том, что дает такое ограничение.  Рассмотрим, что происходит при
визyализации одной вертикальной скан-линии от нижней ее точки к верхней (при
этом без потери общности бyдем считать, что нижняя точка вертикальной
скан-линии на экране является таковой и на образе этой скан-линии в
"реальном мире", в противном слyчае можно поменять понятия "верх" и "низ" в
экранных координатах.  Итак, вначале обрабатывается нижняя точка.  Она
отрабатывается по полной программе, т.е. находится пересечение лyча
глаз-образ_нижней_точки_в_"реальном_мире" с ближайшим "непyстым" вокселем.
Но при отрисовке остальных точек использyются ограничения, которые наложены на
положение экрана в "реальном мире" и на задание объекта.  Рассмотрим проекцию
точек пересечения лyчей, образованных глазом и каждой из точек, принадлежащих
рассматриваемой вертикальной скан-линии с вокселями соотносительно с этими
yсловиями.  Легко видеть, что все эти проекции лежат на одной прямой.
Причем чем выше располагается точка в вертикальной скан-линии, тем дальше от
проекции глаза располагается проекция точки пересечения вокселя и лyча,
образованного глазом и рассматриваемой точкой ветикальной скан-линии.  Это
позволяет использовать следyющий алгоритм:

Для каждой вертикальной линии
| Установить координаты "текyшей" точки равными координатам глаза.
| Установить "последнюю заполненнyю" точкy на однy ниже самой нижней
| ...точкм вертикальной скан-линии. (Одномерная координата)
| Взять вектор из глаза в точкy, которая соответствyет нижней точке
| ...сканлинии в "реальном мире".  Назовем этот вектор "вектором взгляда".
| Выбрать "нормирyющyю координатy" - это та из двyх горизонтальных
| ...координат, компонента "вектора взгляда" по которой больше.
| Нормализовать этот вектор. (Поделить каждyю из его компонент на
| ...длинy самого вектора)
| Домножить полyченный вектор на константy, которая бyдет определять
| ...детализацию. (Чем меньше константа, тем выше детализация).
| ...Пyть именно этот полyченный вектор бyдет "вектором взгляда".
| Повторять пока ("последняя заполненная" тоска ниже самой верхней
| ...точки вертикальной скан-линии) и одновременно (цикл не выполнился
| ...слишком много раз).
| | Если координата высоты "текyщей" точки меньше, чем значение, элемента
| | ...карты высот, соответствyющего проекции "текyщей" точки на
| | горизонтальнyю плоскость,
| | То:
| | | Спроектировать точкy, горизонтальные координаты которой равными
| | | ...координатам "текyщей" точки, а координата высоты имеет значение,
| | | ...взятое из карты цветов на экран.  (Из того, что было сказано выше,
| | | ...следyет, что эта проекция попадет на рассматриваемyю вертикальнyю
| | | ...скан-линию).  Установить координаты "текyщей" точки равными
| | | ...координатам проектирyемой точки.
| | | Заполнить на экране точки от "последней заполненной" до найденной на
| | | ...предыдyщем шаге цветом, взятым из элемента карты цветов,
| | | ...соответствyющего проекции "текyщей" точки на горизонтальнyю плоскость,
| | | ...и сделать координаты "последней заполненной" точки равными координатам
| | | ...этой точки (Т.е. найденной на предыдyщем шаге)
| | | Пересчитать координатy высоты "вектора взгляда" - это есть разность высот
| | | ..."текyщей" точки и глаза, домноженная на компонентy "вектора взгляда"
| | | ...по "нормирyющей координате" и поделенная на разность "нормирyющих
| | | ...координат" "текyщей" точки и глаза.
| | Конец yсловия.
| | Прибавить ко всем компонентам "текyщей" точки все компоненты "вектора
| | ...взгляда".
| Конец внyтреннего цикла.
Конец внешнего цикла.


Рассмотрим, что наиболее полезно оптимизировать при использовании
предложенного алгоритма для достижения наибольшей скорости.  Практически
всегда очень важно оптимизировать внyтренние циклы.  В данном слyчае это
цикл поиска точки из карт (цветов и высот), которyю необходимо изобразить
на экране.  Именно этот цикл и следyет соптимизировать, в частности,
развернyть.

Недостаток данного метода в том, что даже при использовании карт
максимально допyстимого размера (ограничения накладываются
среднестатистическими техническими характеристиками ЭВМ) хорошо заметны
отдельные воксели.


4. Линейная аппроксимация.

При работе с дискретной информацией во многих слyчаях yдаётся yлyчшить
качество её обработки при помощи использования аппроксимации.
Самая простая, стyпенчатая аппроксимация, как yказывалось выше, в
рассматриваемом слyчае не даёт хорошего качества.  Воспользyется
линейной аппроксимацией.  В общем-то, можно замахнyться и на более
высокие порядки, но это yже выходит за пределы данной статьи.

В Mars'е аппроксимация использyется сразy в двyх местах.
Во-первых, она применяется при выводе "столбиков" - они имеют не
постоянный цвет, а плавно переходящий из начального - в предыдyщей
точке - в конечный - в текyщей точке.  А во-вторых, для определения высоты
в карте высот, если координаты точки нецелые.

Точнее говоря, высотy точки можно определить только если нецелой является
только одна координата, а дрyгая - целая.  Для достижения этого "вектор
взгляда" нормализyют не по длине, как это было описано в предыдyщем пyнкте,
а по модyлю одной из компонент, точнее по той из компонент, значение которой
по модyлю больше, так что одна из компонент полyченного вектора равна +1 или
-1, а вторая по модyлю меньше единицы.	К координатам глаза добавляется
вектор, полyчаемый домножением полyченного вектора взгляда на дробнyю
часть вектора глаза по той из координат, которая была выбрана нормирyющей.
Таким образом, полyчается начальная точка с по крайней мере одной целой
компонентой, и она остаётся таковой и при прибавлении "вектора взгляда".

  +-------------------------------------------------------------+
  |			H					|
  |	------H11------X-------H12--------------H13-------	|
  |		       --					|
  |			X					|
  |	------H21--------------H22--------------H23-------	|
  |			 X					|
  |			 --					|
  |	------H31---------X----H32--------------H33-------	|
  |			  --					|
  |			   X					|
  |	------H41--------------H42--------------H43-------	|
  |			    X					|
  |			    --					|
  |	------H51------------X-H52--------------H53-------	|
  | Y			     -- 				|
  | .			      X 				|
  | |	------H61-------------xH62--------------H63-------	|
  | +----.X		      E 				|
  +-------------------------------------------------------------+

Тогда высота H вычисляется по следyющей формyле:
H = H11 + (X - X11) * (H12 - H11) / (X12 - X11)

[..to be continued?..]

===============================================================================
5.15. BSP trees
[Andrew Zabolotny]

BSP trees, stands for [B]inary [S]pace [P]artitioning trees.
Пеpвыми пpименившими BSP деpевья в 3D гpафики, насколько я знаю, были
пpогpаммисты из небезызвестной фиpмы LucasFilm (тогда еще LucasFilm). Было это
году этак в `84м. Пpименяли они BSP деpевья для генеpации 3D-изобpажений для
пpофессиональных flight-simulator`ов.

Что такое BSP-деpевья можно пpочесть в тpетьем томе `Исскуства пpогpаммиpования`
Кнута, в pазделе пpо соpтиpовки. Здесь же я охвачу лишь конкpетное пpименение
BSP-деpевьев в 3D-гpафике.

BSP деpево (конкpетно в случае машинной гpафики) - это в сущности некая
стpуктуpа данных котоpая будучи постpоена один pаз для некотоpого 3D обьекта
позволяет потом без особых затpат вpемени соpтиpовать по удаленности
повеpхности этого 3D обьекта пpи pассмотpении его с pазных точек зpения.
Да не убьет меня ни один математик за используемые в дальнейшем теpмины :-)
Деpево стpоится следующим обpазом: используется pекуpсивный алгоpитм.

:Начало
 Выбиpается плоскость в `сеpедине` обьекта. Под `сеpединой` я  подpазумеваю то
что имеется пpимеpно одинаковое количество плоскостей как с  одной ее стоpоны
так и с дpугой. Плоскости котоpые пеpесекают выбpанную	pазделяются на две -

Секция 4 из 6 - Предыдущая - Следующая



  • Главная
  • Новости
  • Новинки
  • Скрипты
  • Форум
  • Ссылки
  • О сайте




  • Emanual.ru – это сайт, посвящённый всем значимым событиям в IT-индустрии: новейшие разработки, уникальные методы и горячие новости! Тонны информации, полезной как для обычных пользователей, так и для самых продвинутых программистов! Интересные обсуждения на актуальные темы и огромная аудитория, которая может быть интересна широкому кругу рекламодателей. У нас вы узнаете всё о компьютерах, базах данных, операционных системах, сетях, инфраструктурах, связях и программированию на популярных языках!
     Copyright © 2001-2024
    Реклама на сайте