aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/src
diff options
context:
space:
mode:
authorgareth2007-02-28 14:33:10 +0000
committergareth2007-02-28 14:33:10 +0000
commit93da2086a916ef92a680ae211f6ca13ccc7ca1b1 (patch)
tree96ed6cd4cdd8539ff5be3c2ce6e371d051e7c478 /src
parentBrought in other OGS server components and the all-important caffeine script (diff)
downloadopensim-SC-93da2086a916ef92a680ae211f6ca13ccc7ca1b1.zip
opensim-SC-93da2086a916ef92a680ae211f6ca13ccc7ca1b1.tar.gz
opensim-SC-93da2086a916ef92a680ae211f6ca13ccc7ca1b1.tar.bz2
opensim-SC-93da2086a916ef92a680ae211f6ca13ccc7ca1b1.tar.xz
Imported MW's terrain encoder/decoder
Diffstat (limited to '')
-rw-r--r--src/world/TerrainDecoder.cs683
1 files changed, 683 insertions, 0 deletions
diff --git a/src/world/TerrainDecoder.cs b/src/world/TerrainDecoder.cs
new file mode 100644
index 0000000..0f1b733
--- /dev/null
+++ b/src/world/TerrainDecoder.cs
@@ -0,0 +1,683 @@
1/*
2* Copyright (c) OpenSim project, http://sim.opensecondlife.org/
3*
4* Redistribution and use in source and binary forms, with or without
5* modification, are permitted provided that the following conditions are met:
6* * Redistributions of source code must retain the above copyright
7* notice, this list of conditions and the following disclaimer.
8* * Redistributions in binary form must reproduce the above copyright
9* notice, this list of conditions and the following disclaimer in the
10* documentation and/or other materials provided with the distribution.
11* * Neither the name of the <organization> nor the
12* names of its contributors may be used to endorse or promote products
13* derived from this software without specific prior written permission.
14*
15* THIS SOFTWARE IS PROVIDED BY <copyright holder> ``AS IS'' AND ANY
16* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
18* DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
19* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
20* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
21* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
22* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25*
26*/
27
28using System;
29using System.Collections.Generic;
30//using libsecondlife;
31using libsecondlife.Packets;
32
33namespace OpenSim
34{
35 /// <summary>
36 /// Description of TerrainDecoder.
37 /// </summary>
38 public class TerrainDecode
39 {
40
41 public enum LayerType : byte
42 {
43 Land = 0x4C,
44 Water = 0x57,
45 Wind = 0x37,
46 Cloud = 0x38
47 }
48
49 public struct GroupHeader
50 {
51 public int Stride;
52 public int PatchSize;
53 public LayerType Type;
54 }
55
56 public struct PatchHeader
57 {
58 public float DCOffset;
59 public int Range;
60 public int QuantWBits;
61 public int PatchIDs;
62 public uint WordBits;
63 }
64
65 public class Patch
66 {
67 public float[] Heightmap;
68 }
69
70
71 /// <summary>
72 ///
73 /// </summary>
74 /// <param name="simulator"></param>
75 /// <param name="x"></param>
76 /// <param name="y"></param>
77 /// <param name="width"></param>
78 /// <param name="data"></param>
79 // public delegate void LandPatchCallback(Simulator simulator, int x, int y, int width, float[] data);
80
81
82 /// <summary>
83 ///
84 /// </summary>
85 //public event LandPatchCallback OnLandPatch;
86
87 private Random RandomClass = new Random();
88
89 private const byte END_OF_PATCHES = 97;
90 private const int PATCHES_PER_EDGE = 16;
91 private const float OO_SQRT2 = 0.7071067811865475244008443621049f;
92
93 //private SecondLife Client;
94 private Dictionary<ulong, Patch[]> SimPatches = new Dictionary<ulong, Patch[]>();
95 private float[] DequantizeTable16 = new float[16 * 16];
96 private float[] DequantizeTable32 = new float[32 * 32];
97 private float[] ICosineTable16 = new float[16 * 16];
98 private float[] ICosineTable32 = new float[32 * 32];
99 private int[] DeCopyMatrix16 = new int[16 * 16];
100 private int[] DeCopyMatrix32 = new int[32 * 32];
101
102
103 /// <summary>
104 ///
105 /// </summary>
106 /// <param name="client"></param>
107 public TerrainDecode()
108 {
109
110 // Initialize the decompression tables
111 BuildDequantizeTable16();
112 BuildDequantizeTable32();
113 SetupICosines16();
114 SetupICosines32();
115 BuildDecopyMatrix16();
116 BuildDecopyMatrix32();
117
118 }
119
120
121 private void BuildDequantizeTable16()
122 {
123 for (int j = 0; j < 16; j++)
124 {
125 for (int i = 0; i < 16; i++)
126 {
127 DequantizeTable16[j * 16 + i] = 1.0f + 2.0f * (float)(i + j);
128 }
129 }
130 }
131
132 private void BuildDequantizeTable32()
133 {
134 for (int j = 0; j < 32; j++)
135 {
136 for (int i = 0; i < 32; i++)
137 {
138 DequantizeTable32[j * 32 + i] = 1.0f + 2.0f * (float)(i + j);
139 }
140 }
141 }
142
143 private void SetupICosines16()
144 {
145 const float hposz = (float)Math.PI * 0.5f / 16.0f;
146
147 for (int u = 0; u < 16; u++)
148 {
149 for (int n = 0; n < 16; n++)
150 {
151 ICosineTable16[u * 16 + n] = (float)Math.Cos((2.0f * (float)n + 1.0f) * (float)u * hposz);
152 }
153 }
154 }
155
156 private void SetupICosines32()
157 {
158 const float hposz = (float)Math.PI * 0.5f / 32.0f;
159
160 for (int u = 0; u < 32; u++)
161 {
162 for (int n = 0; n < 32; n++)
163 {
164 ICosineTable32[u * 32 + n] = (float)Math.Cos((2.0f * (float)n + 1.0f) * (float)u * hposz);
165 }
166 }
167 }
168
169 private void BuildDecopyMatrix16()
170 {
171 bool diag = false;
172 bool right = true;
173 int i = 0;
174 int j = 0;
175 int count = 0;
176
177 while (i < 16 && j < 16)
178 {
179 DeCopyMatrix16[j * 16 + i] = count++;
180
181 if (!diag)
182 {
183 if (right)
184 {
185 if (i < 16 - 1) i++;
186 else j++;
187
188 right = false;
189 diag = true;
190 }
191 else
192 {
193 if (j < 16 - 1) j++;
194 else i++;
195
196 right = true;
197 diag = true;
198 }
199 }
200 else
201 {
202 if (right)
203 {
204 i++;
205 j--;
206 if (i == 16 - 1 || j == 0) diag = false;
207 }
208 else
209 {
210 i--;
211 j++;
212 if (j == 16 - 1 || i == 0) diag = false;
213 }
214 }
215 }
216 }
217
218 private void BuildDecopyMatrix32()
219 {
220 bool diag = false;
221 bool right = true;
222 int i = 0;
223 int j = 0;
224 int count = 0;
225
226 while (i < 32 && j < 32)
227 {
228 DeCopyMatrix32[j * 32 + i] = count++;
229
230 if (!diag)
231 {
232 if (right)
233 {
234 if (i < 32 - 1) i++;
235 else j++;
236
237 right = false;
238 diag = true;
239 }
240 else
241 {
242 if (j < 32 - 1) j++;
243 else i++;
244
245 right = true;
246 diag = true;
247 }
248 }
249 else
250 {
251 if (right)
252 {
253 i++;
254 j--;
255 if (i == 32 - 1 || j == 0) diag = false;
256 }
257 else
258 {
259 i--;
260 j++;
261 if (j == 32 - 1 || i == 0) diag = false;
262 }
263 }
264 }
265 }
266
267 private void EncodePatchHeader(BitPacker bitpack, PatchHeader header)
268 {
269 bitpack.PackBits(header.QuantWBits,8);
270
271 if (header.QuantWBits == END_OF_PATCHES)
272 return;
273
274 bitpack.PackFloat(header.DCOffset);
275 bitpack.PackBits(header.Range,16);
276 bitpack.PackBits(header.PatchIDs,10);
277
278 }
279
280 public void DCTLine16(float[] In, float[] Out, int line)
281 {
282 int N =16;
283 int lineSize = line * 16;
284
285 for(int k = 0; k < N;k++)
286 {
287 float sum = 0.0f;
288 for(int n = 0; n < N; n++)
289 {
290 float num = (float)(Math.PI*k*(2.0f*n+1)/(2*N));
291 float cosine = (float)Math.Cos(num);
292 float product = In[lineSize +n] * cosine;
293 sum += product;
294 }
295
296 float alpha;
297 if(k == 0)
298 {
299 alpha = (float)(1.0f/Math.Sqrt(2));
300 }
301 else
302 {
303 alpha = 1;
304 }
305 Out[lineSize + k] =(float)( sum * alpha );
306
307 }
308 }
309 public void DCTColumn16(float[] In, float[] Out, int Column)
310 {
311 int N =16;
312 int uSize;
313
314 for(int k = 0; k < N; k++){
315 float sum = 0.0f;
316 for(int n = 0; n < N; n++)
317 {
318 uSize = n * 16;
319 float num = (float)(Math.PI*k*(2.0f*n+1)/(2*N));
320 float cosine = (float)Math.Cos(num);
321 float product = In[uSize + Column] * cosine;
322 sum += product;
323 }
324
325 float alpha;
326 if(k == 0)
327 {
328 alpha = (float)(1.0f/Math.Sqrt(2));
329 }
330 else
331 {
332 alpha = 1;
333 }
334 Out[16 * k + Column] = (float)( sum * alpha * (2.0f /N));
335
336 }
337 }
338
339 private void EncodePatch(int[] patches, BitPacker bitpack, int size)
340 {
341 int lastnum =0;
342 for(int n = 0; n < size * size; n++)
343 {
344 if(patches[n]!=0)
345 lastnum=n;
346 }
347 for (int n = 0; n < lastnum+1; n++)
348 {
349 if(patches[n] != 0)
350 {
351 bitpack.PackBits(1,1); //value or EOB
352 bitpack.PackBits(1,1); //value
353 if(patches[n] > 0)
354 {
355
356 bitpack.PackBits(0,1); // positive
357 bitpack.PackBits(patches[n],13);
358
359 }
360 else
361 {
362 bitpack.PackBits(1,1); // negative
363
364 int temp = patches[n] * -1;
365 bitpack.PackBits(temp,13);
366
367 }
368 }
369 else
370 {
371 bitpack.PackBits(0,1); // no value
372 }
373 }
374
375 bitpack.PackBits(1,1); //value or EOB
376 bitpack.PackBits(0,1); // EOB
377 }
378
379 public int[] CompressPatch(float[] patches)
380 {
381 int size = 16;
382 float[] block = new float[size * size];
383 int[] output = new int[size * size];
384 int prequant = (139 >> 4) + 2;
385 int quantize = 1 << prequant;
386 float ooq = 1.0f / (float)quantize;
387 float mult = ooq * (float)1;
388 float addval = mult * (float)(1 << (prequant - 1)) + 20.4989f;
389
390 if (size == 16)
391 {
392 for (int n = 0; n < 16 * 16; n++)
393 {
394 block[n] = (float)((patches[n] - addval)/ mult);
395 }
396
397 float[] ftemp = new float[32 * 32];
398
399 for (int o = 0; o < 16; o++)
400 this.DCTColumn16(block, ftemp, o);
401 for (int o = 0; o < 16; o++)
402 this.DCTLine16(ftemp, block, o);
403 }
404
405 for (int j = 0; j < block.Length; j++)
406 {
407 output[DeCopyMatrix16[j]] = (int)(block[j] / DequantizeTable16[j]);
408 }
409
410 return output;
411 }
412
413 public Packet CreateLayerPacket(float[] heightmap, int minX, int maxX, int minY, int maxY)
414 {
415 //int minX = 0, maxX = 2, minY = 0, maxY = 1; //these should be passed to this function
416 LayerDataPacket layer = new LayerDataPacket();
417 byte[] Encoded = new byte[2048];
418 layer.LayerID.Type = 76;
419 GroupHeader header = new GroupHeader();
420 header.Stride = 264;
421 header.PatchSize = 16;
422 header.Type = LayerType.Land;
423 BitPacker newpack = new BitPacker(Encoded,0);
424 newpack.PackBits(header.Stride,16);
425 newpack.PackBits(header.PatchSize,8);
426 newpack.PackBits((int)header.Type,8);
427
428
429 float[] height;
430 for(int y = minY; y< maxY; y++)
431 {
432 for(int x = minX ; x < maxX ; x++)
433 {
434 height = new float[256];
435 Array.Copy(heightmap, (4096 *y) +(x *256), height, 0, 256);
436
437 this.CreatePatch(height, newpack, x, y);
438 }
439 }
440
441 PatchHeader headers = new PatchHeader();
442 headers.QuantWBits = END_OF_PATCHES;
443 this.EncodePatchHeader(newpack, headers);
444
445 int lastused=0;
446 for(int i = 0; i < 1024 ; i++)
447 {
448 if(Encoded[i] !=0)
449 lastused = i;
450 }
451
452 byte[] data = new byte[lastused+1];
453 Array.Copy(Encoded, data, lastused+1);
454 layer.LayerData.Data =data;
455
456 return(layer);
457 }
458 public void CreatePatch(float[] heightmap, BitPacker newpack, int x, int y)
459 {
460 PatchHeader header = new PatchHeader();
461 header.DCOffset = 20.4989f;
462 header.QuantWBits = 139;
463 header.Range = 1;
464 header.PatchIDs = (y & 0x1F);
465 header.PatchIDs += x <<5 ;
466
467 this.EncodePatchHeader(newpack, header);
468
469 int[] newpatch = this.CompressPatch(heightmap);
470 this.EncodePatch(newpatch, newpack, 16);
471
472 }
473 }
474
475 //***************************************************
476 public class BitPacker
477 {
478 private const int MAX_BITS = 8;
479
480 private byte[] Data;
481 public int bytePos;
482 public int bitPos;
483
484 /// <summary>
485 /// Default constructor, initialize the bit packer / bit unpacker
486 /// with a byte array and starting position
487 /// </summary>
488 /// <param name="data">Byte array to pack bits in to or unpack from</param>
489 /// <param name="pos">Starting position in the byte array</param>
490 public BitPacker(byte[] data, int pos)
491 {
492 Data = data;
493 bytePos = pos;
494 }
495
496 /// <summary>
497 /// Pack a floating point value in to the data
498 /// </summary>
499 /// <param name="data">Floating point value to pack</param>
500 public void PackFloat(float data)
501 {
502 byte[] input = BitConverter.GetBytes(data);
503 PackBitArray(input, 32);
504 }
505
506 /// <summary>
507 /// Pack part or all of an integer in to the data
508 /// </summary>
509 /// <param name="data">Integer containing the data to pack</param>
510 /// <param name="totalCount">Number of bits of the integer to pack</param>
511 public void PackBits(int data, int totalCount)
512 {
513 byte[] input = BitConverter.GetBytes(data);
514 PackBitArray(input, totalCount);
515 }
516
517 /// <summary>
518 /// Unpacking a floating point value from the data
519 /// </summary>
520 /// <returns>Unpacked floating point value</returns>
521 public float UnpackFloat()
522 {
523 byte[] output = UnpackBitsArray(32);
524
525 if (!BitConverter.IsLittleEndian) Array.Reverse(output);
526 return BitConverter.ToSingle(output, 0);
527 }
528
529 /// <summary>
530 /// Unpack a variable number of bits from the data in to integer format
531 /// </summary>
532 /// <param name="totalCount">Number of bits to unpack</param>
533 /// <returns>An integer containing the unpacked bits</returns>
534 /// <remarks>This function is only useful up to 32 bits</remarks>
535 public int UnpackBits(int totalCount)
536 {
537 byte[] output = UnpackBitsArray(totalCount);
538
539 if (!BitConverter.IsLittleEndian) Array.Reverse(output);
540 return BitConverter.ToInt32(output, 0);
541 }
542
543 private void PackBitArray(byte[] data, int totalCount)
544 {
545 int count = 0;
546 int curBytePos = 0;
547 int curBitPos = 0;
548
549 while (totalCount > 0)
550 {
551 if (totalCount > (MAX_BITS ))
552 {
553 count = MAX_BITS ;
554 totalCount -= MAX_BITS ;
555 }
556 else
557 {
558 count = totalCount;
559 totalCount = 0;
560 }
561
562 while (count > 0)
563 {
564 switch(count)
565 {
566 case 1:
567 if ((data[curBytePos] & (0x01)) != 0)
568 {
569 Data[bytePos] |= (byte)(0x80 >> bitPos);
570 }
571 break;
572 case 2:
573 if ((data[curBytePos] & (0x02)) != 0)
574 {
575 Data[bytePos] |= (byte)(0x80 >> bitPos);
576 }
577 break;
578 case 3:
579 if ((data[curBytePos] & (0x04)) != 0)
580 {
581 Data[bytePos] |= (byte)(0x80 >> bitPos);
582 }
583 break;
584 case 4:
585 if ((data[curBytePos] & (0x08)) != 0)
586 {
587 Data[bytePos] |= (byte)(0x80 >> bitPos);
588 }
589 break;
590 case 5:
591 if ((data[curBytePos] & (0x10)) != 0)
592 {
593 Data[bytePos] |= (byte)(0x80 >> bitPos);
594 }
595 break;
596 case 6:
597 if ((data[curBytePos] & (0x20)) != 0)
598 {
599 Data[bytePos] |= (byte)(0x80 >> bitPos);
600 }
601 break;
602 case 7:
603 if ((data[curBytePos] & (0x40)) != 0)
604 {
605 Data[bytePos] |= (byte)(0x80 >> bitPos);
606 }
607 break;
608 case 8:
609 if ((data[curBytePos] & (0x80)) != 0)
610 {
611 Data[bytePos] |= (byte)(0x80 >> bitPos);
612 }
613 break;
614 }
615
616 bitPos++;
617 --count;
618 ++curBitPos;
619
620 if (bitPos >= MAX_BITS)
621 {
622 bitPos = 0;
623 ++bytePos;
624 }
625 if (curBitPos >= MAX_BITS)
626 {
627 curBitPos = 0;
628 ++curBytePos;
629 }
630 }
631 }
632 }
633
634
635 private byte[] UnpackBitsArray(int totalCount)
636 {
637 int count = 0;
638 byte[] output = new byte[4];
639 int curBytePos = 0;
640 int curBitPos = 0;
641
642 while (totalCount > 0)
643 {
644 if (totalCount > MAX_BITS)
645 {
646 count = MAX_BITS;
647 totalCount -= MAX_BITS;
648 }
649 else
650 {
651 count = totalCount;
652 totalCount = 0;
653 }
654
655 while (count > 0)
656 {
657 // Shift the previous bits
658 output[curBytePos] <<= 1;
659
660 // Grab one bit
661 if ((Data[bytePos] & (0x80 >> bitPos++)) != 0)
662 ++output[curBytePos];
663
664 --count;
665 ++curBitPos;
666
667 if (bitPos >= MAX_BITS)
668 {
669 bitPos = 0;
670 ++bytePos;
671 }
672 if (curBitPos >= MAX_BITS)
673 {
674 curBitPos = 0;
675 ++curBytePos;
676 }
677 }
678 }
679
680 return output;
681 }
682 }
683}