Алгоритм распространения света

Алгоритм освещения на двумерной карте клеток. Распространение света. Плавные тени. Слабые тени.

Родилось из обсуждения с Death и просмотра информации об освещении в майнкрафте, где для распространения света использовалось сложное окто-дерево, FIFO очередь, потом отдельно считали максимальное значение света, причём так криво, что у меня кровь из глаз потекла.
  1. //Вычисляет значение света в точке (x,y) на двумерной карте в зависимости от соседних блоков
  2. //Возвращает float [-∞ ... 1]
  3. // -∞ - min
  4. //ВНИМАНИЕ!!!
  5. //Отрицательное значение света нужно для выхода из рекурсии!!!
  6. // 1 - max
  7. public float getLight(int x, int y){
  8.  //Кэшируем значение поглощения света текущего блока
  9.  // float [0 ... 1] 0 - min, 1 - max
  10.  float ABSORT=getABSORT(x,y);
  11.  //Ищем максимальное значение света у
  12.  //диагональных блоков
  13.  float f1 =Math.max(
  14.   Math.max(getLP(x-1,y-1),getLP(x+1,y-1)),
  15.   Math.max(getLP(x+1,y+1),getLP(x-1,y+1))
  16.  );
  17.  //Ищем максимальное значение света у смежных блоков
  18.  float f2 = Math.max(
  19.   Math.max(getLP(x,y-1),getLP(x+1,y)),
  20.   Math.max(getLP(x,y+1),getLP(x-1, y))
  21.  );
  22.  //Если боковое освещение лучше чем диагональное, то расчитываем свет по смежному
  23. if(f2>=f1){
  24.  f1=f2-ABSORT;//для бокового освещения
  25.  } else {
  26.   f1=f1-ABSORT*Math.sqrt(2);//для смежного, корень из двух
  27.   //Можно корень вычислить заранее, подставив константу
  28.  }
  29.  return f1;
  30. }
  1. //В точке x,y источник света, и для этого источника обновляет
  2. // Рекурсивный алгоритм обрабатывает только клетки с нулевым значением света
  3. public void updateLight(x,y){
  4. float light = getLight(x,y);
  5.  //Если освещение для клетки отрицательно, выходим из рекурсии
  6.  if(light<0) return;
  7. //Если вычисленный свет меньше или равен, чем уже есть, выходим из рекурсии
  8. //Таким образом свет от нескольких источников не складывается.
  9. //Таким образом рекурсия уже не уходит на ранее вычисленные значения.
  10. //Не нужна FIFO очередь и прочие навороты.
  11.  if(light<=getLP) return;
  12.  setLP(x,y, light);
  13.  updateLight(x,y-1);
  14.  updateLight(x+1,y);
  15.  updateLight(x,y+1);
  16.  updateLight(x-1,y);
  17. }//Надеюсь, что верно составил рекурсию.
  1. int w, h;
  2. //Массив клеток карты
  3. Cell[] cells =new Cell[w*h];
  4.  
  5. public float getLP(int x, int y){
  6.  return cells[x+y*w].LIGHT;
  7. }
  8. public void setLP(int x, int y, float l){
  9.  cells[x+y*w].LIGHT=l;
  10. }
  11. public float getABSORT(int x, int y){
  12.  return cells[x+y*w].ABSORT;
  13. }
  14. public class Cell{
  15.  public float LIGHT=0.0f;
  16.  public float GLIHGT=1.0f;//Это уже глобальное освещение, расчитывается отдельно.
  17.  public float ABSORT=0.1f;
  18. }

Мы в соцсетях

vk tw tg yt

Пожертвования

Аноним2850 р.
Freddy1700 р.
riseremi1611 р.
NaruTrey800 р.
vlavolk637 р.
  © aNNiMON (Melnik Software)