Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Random train snippets
// brickportals.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <malloc.h>
#include <vector>
#include <map>
#include <set>
class sparebitset
{
std::map<unsigned int, unsigned char> bits;
public:
void set( unsigned int index )
{
bits[index/8] |= (index%8);
}
bool get( unsigned int index )
{
return (bits[index/8] & (index%8)) ? true : false;
}
};
struct brick
{
int version;
int x, y, z;
unsigned char solid[256][256][256/8];
};
void *readfile( const char *filename, int *len = NULL )
{
if ( filename == NULL )
return NULL;
FILE *f = fopen( filename, "rb" );
if ( f )
{
fseek( f, 0, SEEK_END );
int l = ftell( f );
fseek( f, 0, SEEK_SET );
char *mem = (char*)malloc( l + 1 );
fread( mem, l, 1, f );
mem[l] = 0;
fclose( f );
if ( len )
{
*len = l;
}
return mem;
}
else
{
return NULL;
}
}
struct node
{
short box[2][3];
node *kids[2];
int id;
short group;
node()
{
kids[0] = kids[1] = NULL;
}
~node()
{
delete kids[0];
delete kids[1];
}
};
inline int min( int a, int b )
{
return (a<b) ? a : b;
}
inline int max( int a, int b )
{
return (a>b) ? a : b;
}
node* genportals( brick *b, int mnx, int mny, int mnz, int mxx, int mxy, int mxz, int depth, int axis )
{
if ( b == NULL )
{
node *n = new node;
n->box[0][0] = mnx;
n->box[0][1] = mny;
n->box[0][2] = mnz;
n->box[1][0] = mxx;
n->box[1][1] = mxy;
n->box[1][2] = mxz;
n->kids[0] = NULL;
n->kids[1] = NULL;
return n;
}
if ( depth )
{
int mdy = (mny+mxy) / 2;
int mdz = (mnz+mxz) / 2;
node *g0;
node *g1;
if ( axis == 0 )
{
int mdx = (mnx+mxx) / 2;
g0 = genportals( b, mnx, mny, mnz, mdx, mxy, mxz, depth-1, (axis+1)%3 );
g1 = genportals( b, mdx, mny, mnz, mxx, mxy, mxz, depth-1, (axis+1)%3 );
}
else
if ( axis == 1 )
{
int mdy = (mny+mxy) / 2;
g0 = genportals( b, mnx, mny, mnz, mxx, mdy, mxz, depth-1, (axis+1)%3 );
g1 = genportals( b, mnx, mdy, mnz, mxx, mxy, mxz, depth-1, (axis+1)%3 );
}
else
//if ( axis == 2 )
{
int mdz = (mnz+mxz) / 2;
g0 = genportals( b, mnx, mny, mnz, mxx, mxy, mdz, depth-1, (axis+1)%3 );
g1 = genportals( b, mnx, mny, mdz, mxx, mxy, mxz, depth-1, (axis+1)%3 );
}
// both empty combine
if ( g0 && g1 && g0->kids[0] == NULL && g1->kids[1] == NULL )
{
node *n = new node;
n->box[0][0] = mnx;
n->box[0][1] = mny;
n->box[0][2] = mnz;
n->box[1][0] = mxx;
n->box[1][1] = mxy;
n->box[1][2] = mxz;
n->kids[0] = NULL;
n->kids[1] = NULL;
delete g0;
delete g1;
return n;
}
else
if ( g0 == NULL && g1 == NULL )
{
return NULL;
}
else
{
node *n = new node;
n->box[0][0] = mnx;
n->box[0][1] = mny;
n->box[0][2] = mnz;
n->box[1][0] = mxx;
n->box[1][1] = mxy;
n->box[1][2] = mxz;
n->kids[0] = g0;
n->kids[1] = g1;
return n;
}
}
else
{
bool g = false;
for (int z=mnz; z<mxz; z++)
{
for (int y=mny; y<mxy; y++)
{
for (int x=mnx; x<mxx; x++)
{
if ( b->solid[z][y][x/8] & (1<<(x%8)) )
g = true;
}
}
}
if ( g )
{
return NULL;
}
else
{
node *n = new node;
n->box[0][0] = mnx;
n->box[0][1] = mny;
n->box[0][2] = mnz;
n->box[1][0] = mxx;
n->box[1][1] = mxy;
n->box[1][2] = mxz;
n->kids[0] = NULL;
n->kids[1] = NULL;
return n;
}
}
}
void outputleafboxes( FILE *f, node *n )
{
if ( n == NULL )
return;
if ( n->kids[0]==NULL && n->kids[1]==NULL )
{
fprintf( f, "v %d %d %d\n", n->box[0][0], n->box[0][1], n->box[0][2] );
fprintf( f, "v %d %d %d\n", n->box[1][0], n->box[0][1], n->box[0][2] );
fprintf( f, "v %d %d %d\n", n->box[0][0], n->box[1][1], n->box[0][2] );
fprintf( f, "v %d %d %d\n", n->box[1][0], n->box[1][1], n->box[0][2] );
fprintf( f, "v %d %d %d\n", n->box[0][0], n->box[0][1], n->box[1][2] );
fprintf( f, "v %d %d %d\n", n->box[1][0], n->box[0][1], n->box[1][2] );
fprintf( f, "v %d %d %d\n", n->box[0][0], n->box[1][1], n->box[1][2] );
fprintf( f, "v %d %d %d\n", n->box[1][0], n->box[1][1], n->box[1][2] );
fprintf( f, "f -8 -7 -5 -6\n" );
fprintf( f, "f -6 -5 -1 -2\n" );
fprintf( f, "f -8 -6 -2 -4\n" );
fprintf( f, "f -7 -8 -4 -3\n" );
fprintf( f, "f -5 -7 -3 -1\n" );
fprintf( f, "f -1 -2 -4 -3\n" );
}
else
{
outputleafboxes( f, n->kids[0] );
outputleafboxes( f, n->kids[1] );
}
}
void addleaves( std::vector<node*> &leaves, node *n )
{
if ( n == NULL )
return;
if ( n->kids[0]==NULL && n->kids[1]==NULL )
{
leaves.push_back( n );
}
else
{
addleaves( leaves, n->kids[0] );
addleaves( leaves, n->kids[1] );
}
}
bool touching( node *a, node *b )
{
for (int axis=0; axis<3; axis++)
{
if ( a->box[1][axis] < b->box[0][axis] )
return false;
if ( a->box[0][axis] > b->box[1][axis] )
return false;
}
return true;
}
struct quad
{
short v[4][3];
};
quad generatequad( node *n, int face )
{
const static int faceids[6][4] =
{
{ 0, 2, 6, 4 }, // ---, -+-, -++, --+ -x
{ 1, 0, 4, 5 }, // +--, ---, --+, +-+ -y
{ 0, 1, 3, 2 }, // ---, +--, ++-, -+- -z
{ 3, 1, 5, 7 }, // ++-, +--, +-+, +++ +x
{ 2, 3, 7, 6 }, // -+-, ++-, +++, -++ +y
{ 7, 6, 4, 5 }, // +++, -++, --+, +-+ +z
};
quad q;
for (int i=0; i<4; i++)
{
q.v[i][0] = faceids[face][i] & 1 ? n->box[1][0] : n->box[0][0];
q.v[i][1] = faceids[face][i] & 2 ? n->box[1][1] : n->box[0][1];
q.v[i][2] = faceids[face][i] & 4 ? n->box[1][2] : n->box[0][2];
}
return q;
}
quad clipquad( quad q, node *n )
{
quad empty;
memset( &empty, 0, sizeof(empty) );
int bb[2][4];
bb[0][0] = min( q.v[0][0], min( q.v[1][0], min( q.v[2][0], q.v[3][0] ) ) );
bb[0][1] = min( q.v[0][1], min( q.v[1][1], min( q.v[2][1], q.v[3][1] ) ) );
bb[0][2] = min( q.v[0][2], min( q.v[1][2], min( q.v[2][2], q.v[3][2] ) ) );
bb[1][0] = max( q.v[0][0], max( q.v[1][0], max( q.v[2][0], q.v[3][0] ) ) );
bb[1][1] = max( q.v[0][1], max( q.v[1][1], max( q.v[2][1], q.v[3][1] ) ) );
bb[1][2] = max( q.v[0][2], max( q.v[1][2], max( q.v[2][2], q.v[3][2] ) ) );
for (int axis=0; axis<3; axis++)
{
if ( bb[1][axis] < n->box[0][axis] )
return empty;
if ( bb[0][axis] > n->box[1][axis] )
return empty;
}
for (int i=0; i<4; i++)
{
q.v[i][0] = max( n->box[0][0], min( n->box[1][0], q.v[i][0] ) );
q.v[i][1] = max( n->box[0][1], min( n->box[1][1], q.v[i][1] ) );
q.v[i][2] = max( n->box[0][2], min( n->box[1][2], q.v[i][2] ) );
}
return q;
}
bool isvalidquad( quad const &q )
{
int mn[3] = { q.v[0][0], q.v[0][1], q.v[0][2] };
int mx[3] = { q.v[0][0], q.v[0][1], q.v[0][2] };
for (int i=0; i<4; i++)
{
mn[0] = min( mn[0], q.v[i][0] );
mn[1] = min( mn[1], q.v[i][1] );
mn[2] = min( mn[2], q.v[i][2] );
mx[0] = max( mx[0], q.v[i][0] );
mx[1] = max( mx[1], q.v[i][1] );
mx[2] = max( mx[2], q.v[i][2] );
}
int count = 0;
count += (mn[0] == mx[0]) ? 0 : 1;
count += (mn[1] == mx[1]) ? 0 : 1;
count += (mn[2] == mx[2]) ? 0 : 1;
return count == 2;
}
void outputquad( FILE *f, quad const &q )
{
fprintf( f, "v %d %d %d\n", q.v[0][0], q.v[0][1], q.v[0][2] );
fprintf( f, "v %d %d %d\n", q.v[1][0], q.v[1][1], q.v[1][2] );
fprintf( f, "v %d %d %d\n", q.v[2][0], q.v[2][1], q.v[2][2] );
fprintf( f, "v %d %d %d\n", q.v[3][0], q.v[3][1], q.v[3][2] );
fprintf( f, "f -1 -2 -3 -4\n" );
}
node *createbound( int mnx, int mny, int mnz, int mxx, int mxy, int mxz )
{
node *n = new node;
n->box[0][0] = mnx;
n->box[0][1] = mny;
n->box[0][2] = mnz;
n->box[1][0] = mxx;
n->box[1][1] = mxy;
n->box[1][2] = mxz;
n->kids[0] = NULL;
n->kids[1] = NULL;
return n;
}
node *findfreenode( std::vector< node* > const &leaves )
{
for (unsigned int i=0; i<leaves.size(); i++)
{
if ( leaves[i]->group == -1 )
return leaves[i];
}
return NULL;
}
#include <assert.h>
void floodfill( node *n, std::vector< node* > const &leaves, std::map<int,std::set<int>> &connected, int group )
{
assert( n->group == -1 );
n->group = group;
std::set<int>::const_iterator b = connected[n->id].cbegin();
while ( b != connected[n->id].cend() )
{
int c = *b++;
if ( leaves[c]->group == group )
{
continue;
}
floodfill( leaves[c], leaves, connected, group );
}
}
bool canmerge( node *a, node *b )
{
if ( a->group != b->group )
return false;
for (int axis=0; axis<3; axis++)
{
if ( a->box[1][axis] < b->box[0][axis] )
return false;
if ( a->box[0][axis] > b->box[1][axis] )
return false;
int ext0 = (axis+1)%3;
int ext1 = (axis+2)%3;
if ( a->box[0][ext0] == b->box[0][ext0] &&
a->box[0][ext1] == b->box[0][ext1] &&
a->box[1][ext0] == b->box[1][ext0] &&
a->box[1][ext1] == b->box[1][ext1] )
{
return true;
}
}
return false;
}
void merge( node *a, node *b )
{
a->box[0][0] = min( a->box[0][0], b->box[0][0] );
a->box[0][1] = min( a->box[0][1], b->box[0][1] );
a->box[0][2] = min( a->box[0][2], b->box[0][2] );
a->box[1][0] = max( a->box[1][0], b->box[1][0] );
a->box[1][1] = max( a->box[1][1], b->box[1][1] );
a->box[1][2] = max( a->box[1][2], b->box[1][2] );
b->group = -1;
}
struct cellbound
{
short bb[2][3];
int group;
};
struct portal
{
short v[2][3];
short group;
unsigned char other_group;
unsigned char other_cell;
};
struct cell
{
int grid[3];
std::vector< cellbound > bounds;
std::vector< portal > portals;
sparebitset vis;
};
struct plane
{
float n[3];
int loc[3];
};
void fwriteint( FILE *f, int v )
{
fwrite( &v, sizeof(v), 1, f );
}
void fwriteshort( FILE *f, short v )
{
fwrite( &v, sizeof(v), 1, f );
}
int freadint( FILE *f )
{
int v;
fread( &v, sizeof(v), 1, f );
return v;
}
short freadshort( FILE *f )
{
short v;
fread( &v, sizeof(v), 1, f );
return v;
}
void writecell( const char *filename, cell &c )
{
FILE *f = fopen( filename, "wb" );
if ( f )
{
fwriteint( f, 0x100 );
fwriteint( f, c.grid[0] );
fwriteint( f, c.grid[1] );
fwriteint( f, c.grid[2] );
fwriteint( f, c.bounds.size() );
fwriteint( f, c.portals.size() );
for (unsigned int i=0; i<c.bounds.size(); i++)
{
fwriteshort( f, c.bounds[i].bb[0][0] );
fwriteshort( f, c.bounds[i].bb[0][1] );
fwriteshort( f, c.bounds[i].bb[0][2] );
fwriteshort( f, c.bounds[i].bb[1][0] );
fwriteshort( f, c.bounds[i].bb[1][1] );
fwriteshort( f, c.bounds[i].bb[1][2] );
fwriteint( f, c.bounds[i].group );
}
for (unsigned int i=0; i<c.portals.size(); i++)
{
fwriteshort( f, c.portals[i].v[0][0] );
fwriteshort( f, c.portals[i].v[0][1] );
fwriteshort( f, c.portals[i].v[0][2] );
fwriteshort( f, c.portals[i].v[1][0] );
fwriteshort( f, c.portals[i].v[1][1] );
fwriteshort( f, c.portals[i].v[1][2] );
fwriteint( f, c.portals[i].group );
fwriteint( f, c.portals[i].other_cell );
fwriteint( f, c.portals[i].other_group );
}
fclose( f );
}
}
void writeobjofcell( const char *filename, cell *cs, int numcells )
{
FILE *f = fopen( filename, "wb" );
if ( f )
{
for (int n=0; n<numcells; n++)
{
cell &c = cs[n];
for (unsigned int i=0; i<c.portals.size(); i++)
{
portal &p = c.portals[i];
fprintf( f, "v %d %d %d\n", p.v[0][0],p.v[0][1], p.v[0][2] );
fprintf( f, "v %d %d %d\n", p.v[1][0],p.v[0][1], p.v[0][2] );
fprintf( f, "v %d %d %d\n", p.v[0][0],p.v[1][1], p.v[0][2] );
fprintf( f, "v %d %d %d\n", p.v[1][0],p.v[1][1], p.v[0][2] );
fprintf( f, "v %d %d %d\n", p.v[0][0],p.v[0][1], p.v[1][2] );
fprintf( f, "v %d %d %d\n", p.v[1][0],p.v[0][1], p.v[1][2] );
fprintf( f, "v %d %d %d\n", p.v[0][0],p.v[1][1], p.v[1][2] );
fprintf( f, "v %d %d %d\n", p.v[1][0],p.v[1][1], p.v[1][2] );
fprintf( f, "f -8 -7 -5 -6\n" );
fprintf( f, "f -6 -5 -1 -2\n" );
fprintf( f, "f -8 -6 -2 -4\n" );
fprintf( f, "f -7 -8 -4 -3\n" );
fprintf( f, "f -5 -7 -3 -1\n" );
fprintf( f, "f -1 -2 -4 -3\n" );
}
}
fclose( f );
}
}
void offsetcell( cell &c, int ox, int oy, int oz )
{
for (unsigned int i=0; i<c.bounds.size(); i++)
{
c.bounds[i].bb[0][0] += ox;
c.bounds[i].bb[0][1] += oy;
c.bounds[i].bb[0][2] += oz;
c.bounds[i].bb[1][0] += ox;
c.bounds[i].bb[1][1] += oy;
c.bounds[i].bb[1][2] += oz;
}
for (unsigned int i=0; i<c.portals.size(); i++)
{
c.portals[i].v[0][0] += ox;
c.portals[i].v[0][1] += oy;
c.portals[i].v[0][2] += oz;
c.portals[i].v[1][0] += ox;
c.portals[i].v[1][1] += oy;
c.portals[i].v[1][2] += oz;
}
}
bool readcell( cell &c, const char *filename, int ox, int oy, int oz )
{
FILE *f = fopen( filename, "rb" );
if ( f )
{
int version = freadint( f );
assert( version == 0x100 );
c.grid[0] = freadint( f );
c.grid[1] = freadint( f );
c.grid[2] = freadint( f );
c.bounds.resize( freadint( f ) );
c.portals.resize( freadint( f ) );
for (unsigned int i=0; i<c.bounds.size(); i++)
{
c.bounds[i].bb[0][0] = freadshort( f ) + ox;
c.bounds[i].bb[0][1] = freadshort( f ) + oy;
c.bounds[i].bb[0][2] = freadshort( f ) + oz;
c.bounds[i].bb[1][0] = freadshort( f ) + ox;
c.bounds[i].bb[1][1] = freadshort( f ) + oy;
c.bounds[i].bb[1][2] = freadshort( f ) + oz;
c.bounds[i].group = freadint( f );
}
for (unsigned int i=0; i<c.portals.size(); i++)
{
c.portals[i].v[0][0] = freadshort( f ) + ox;
c.portals[i].v[0][1] = freadshort( f ) + oy;
c.portals[i].v[0][2] = freadshort( f ) + oz;
c.portals[i].v[1][0] = freadshort( f ) + ox;
c.portals[i].v[1][1] = freadshort( f ) + oy;
c.portals[i].v[1][2] = freadshort( f ) + oz;
c.portals[i].group = freadint( f );
c.portals[i].other_cell = freadint( f );
c.portals[i].other_group = freadint( f );
}
fclose( f );
return true;
}
return false;
}
void makecell( cell &c, const char *cellfilename, const char *voxelfilename )
{
brick *b = (brick*)readfile( voxelfilename );
node *n = genportals( b, 0, 0, 0, 256, 256, 256, 10, 0 );
c.grid[0] = b ? b->x : 0;
c.grid[1] = b ? b->y : 0;
c.grid[2] = b ? b->z : 0;
free( b );
std::vector< node* > leaves;
addleaves( leaves, n );
{
std::map<int,std::set<int>> connected;
for (unsigned int i=0; i<leaves.size(); i++)
{
leaves[i]->id = i;
leaves[i]->group = -1;
for (unsigned int j=0; j<leaves.size(); j++)
{
if ( i == j )
continue;
if ( !touching( leaves[i], leaves[j] ) )
continue;
for (int face=0; face<6; face++)
{
quad q = clipquad( generatequad( leaves[i], face ), leaves[j] );
if ( isvalidquad( q ) )
{
connected[i].insert(j);
}
}
}
}
int group = 0;
do
{
node *n = findfreenode( leaves );
if ( n == NULL )
break;
floodfill( n, leaves, connected, group );
group++;
} while ( true );
}
{
bool done = false;
while ( !done )
{
done = true;
for (unsigned int i=0; i<leaves.size(); i++)
{
if ( leaves[i]->group == -1 )
continue;
for (unsigned int j=0; j<leaves.size(); j++)
{
if ( i == j )
continue;
if ( leaves[j]->group == -1 )
continue;
if ( canmerge( leaves[i], leaves[j] ) )
{
merge( leaves[i], leaves[j] );
done = false;
}
}
}
}
}
{
std::vector< node* >::iterator b = leaves.begin();
while ( b != leaves.end() )
{
if ( (*b)->group == -1 )
{
b = leaves.erase( b );
}
else
{
b++;
}
}
}
{
std::vector< node* > external;
external.push_back( createbound( 256, 0, 0, 512, 256, 256 ) );
external.push_back( createbound( 0, 256, 0, 256, 512, 256 ) );
external.push_back( createbound( 0, 0, 256, 256, 256, 512 ) );
external.push_back( createbound( -256, 0, 0, 0, 256, 256 ) );
external.push_back( createbound( 0, -256, 0, 256, 0, 256 ) );
external.push_back( createbound( 0, 0, -256, 256, 256, 0 ) );
for (unsigned int i=0; i<leaves.size(); i++)
{
cellbound cb;
cb.group = leaves[i]->group;
cb.bb[0][0] = leaves[i]->box[0][0];
cb.bb[0][1] = leaves[i]->box[0][1];
cb.bb[0][2] = leaves[i]->box[0][2];
cb.bb[1][0] = leaves[i]->box[1][0];
cb.bb[1][1] = leaves[i]->box[1][1];
cb.bb[1][2] = leaves[i]->box[1][2];
c.bounds.push_back( cb );
for (unsigned int j=0; j<external.size(); j++)
{
if ( !touching( leaves[i], external[j] ) )
continue;
for (int face=0; face<6; face++)
{
quad q = clipquad( generatequad( leaves[i], face ), external[j] );
if ( isvalidquad( q ) )
{
portal p;
p.group = leaves[i]->group;
p.other_cell = face;
p.other_group = 255;
p.v[0][0] = min( q.v[0][0], min( q.v[1][0], min( q.v[2][0], q.v[3][0] ) ) );
p.v[0][1] = min( q.v[0][1], min( q.v[1][1], min( q.v[2][1], q.v[3][1] ) ) );
p.v[0][2] = min( q.v[0][2], min( q.v[1][2], min( q.v[2][2], q.v[3][2] ) ) );
p.v[1][0] = max( q.v[0][0], max( q.v[1][0], max( q.v[2][0], q.v[3][0] ) ) );
p.v[1][1] = max( q.v[0][1], max( q.v[1][1], max( q.v[2][1], q.v[3][1] ) ) );
p.v[1][2] = max( q.v[0][2], max( q.v[1][2], max( q.v[2][2], q.v[3][2] ) ) );
c.portals.push_back( p );
}
}
}
}
}
if ( cellfilename )
{
writecell( cellfilename, c );
}
delete n;
}
bool touching( portal const *a, portal const *b )
{
for (int axis=0; axis<3; axis++)
{
if ( a->v[1][axis] < b->v[0][axis] )
return false;
if ( a->v[0][axis] > b->v[1][axis] )
return false;
}
return true;
}
quad generatequad( portal const *n, int face )
{
const static int faceids[6][4] =
{
{ 0, 2, 6, 4 }, // ---, -+-, -++, --+ -x
{ 1, 0, 4, 5 }, // +--, ---, --+, +-+ -y
{ 0, 1, 3, 2 }, // ---, +--, ++-, -+- -z
{ 3, 1, 5, 7 }, // ++-, +--, +-+, +++ +x
{ 2, 3, 7, 6 }, // -+-, ++-, +++, -++ +y
{ 7, 6, 4, 5 }, // +++, -++, --+, +-+ +z
};
quad q;
for (int i=0; i<4; i++)
{
q.v[i][0] = faceids[face][i] & 1 ? n->v[1][0] : n->v[0][0];
q.v[i][1] = faceids[face][i] & 2 ? n->v[1][1] : n->v[0][1];
q.v[i][2] = faceids[face][i] & 4 ? n->v[1][2] : n->v[0][2];
}
return q;
}
quad clipquad( quad q, portal const *n )
{
quad empty;
memset( &empty, 0, sizeof(empty) );
int bb[2][4];
bb[0][0] = min( q.v[0][0], min( q.v[1][0], min( q.v[2][0], q.v[3][0] ) ) );
bb[0][1] = min( q.v[0][1], min( q.v[1][1], min( q.v[2][1], q.v[3][1] ) ) );
bb[0][2] = min( q.v[0][2], min( q.v[1][2], min( q.v[2][2], q.v[3][2] ) ) );
bb[1][0] = max( q.v[0][0], max( q.v[1][0], max( q.v[2][0], q.v[3][0] ) ) );
bb[1][1] = max( q.v[0][1], max( q.v[1][1], max( q.v[2][1], q.v[3][1] ) ) );
bb[1][2] = max( q.v[0][2], max( q.v[1][2], max( q.v[2][2], q.v[3][2] ) ) );
for (int axis=0; axis<3; axis++)
{
if ( bb[1][axis] < n->v[0][axis] )
return empty;
if ( bb[0][axis] > n->v[1][axis] )
return empty;
}
for (int i=0; i<4; i++)
{
q.v[i][0] = max( n->v[0][0], min( n->v[1][0], q.v[i][0] ) );
q.v[i][1] = max( n->v[0][1], min( n->v[1][1], q.v[i][1] ) );
q.v[i][2] = max( n->v[0][2], min( n->v[1][2], q.v[i][2] ) );
}
return q;
}
void intersect( cell &c, cell const *neighbours, int numn )
{
std::vector< portal > src;
std::swap( c.portals, src );
for (unsigned int i=0; i<src.size(); i++)
{
portal srcp = src[i];
for (unsigned int ni=0; ni<numn; ni++)
{
cell const &n = neighbours[ni];
for (unsigned int j=0; j<n.portals.size(); j++)
{
if ( !touching( &srcp, &n.portals[j] ) )
continue;
{
quad q = clipquad( generatequad( &srcp, srcp.other_cell ), &n.portals[j] );
if ( isvalidquad( q ) )
{
portal p;
p.group = srcp.group;
p.other_cell = srcp.other_cell;
p.other_group = n.portals[j].group;
p.v[0][0] = min( q.v[0][0], min( q.v[1][0], min( q.v[2][0], q.v[3][0] ) ) );
p.v[0][1] = min( q.v[0][1], min( q.v[1][1], min( q.v[2][1], q.v[3][1] ) ) );
p.v[0][2] = min( q.v[0][2], min( q.v[1][2], min( q.v[2][2], q.v[3][2] ) ) );
p.v[1][0] = max( q.v[0][0], max( q.v[1][0], max( q.v[2][0], q.v[3][0] ) ) );
p.v[1][1] = max( q.v[0][1], max( q.v[1][1], max( q.v[2][1], q.v[3][1] ) ) );
p.v[1][2] = max( q.v[0][2], max( q.v[1][2], max( q.v[2][2], q.v[3][2] ) ) );
c.portals.push_back( p );
}
}
}
}
}
}
#include <string>
#include <vector>
#include <io.h>
#include <algorithm>
char fixseparator( char c )
{
return ( c == '/' ) ? '\\' : c;
}
void findFiles( std::vector< std::string > &files, const char *pattern )
{
std::string path = pattern;
std::transform( path.begin(), path.end(), path.begin(), fixseparator );
std::string::size_type pos = path.find_last_of( '\\' );
if ( pos != std::string::npos )
{
path = path.substr( 0, pos );
}
else
{
path = ".";
}
_finddata_t fi;
intptr_t fh = _findfirst( pattern, &fi );
if ( fh != -1 )
{
do
{
files.push_back( path + "\\" + fi.name );
}
while ( _findnext( fh, &fi ) == 0 );
_findclose( fh );
}
}
bool readhdr( float bb[2][3], const char *filename )
{
FILE *f = fopen( filename, "rb" );
if ( f )
{
bool failed = false;
failed |= (fscanf( f, "%f,%f,%f\n", &bb[0][0], &bb[0][1], &bb[0][2] ) != 3);
failed |= (fscanf( f, "%f,%f,%f\n", &bb[1][0], &bb[1][1], &bb[1][2] ) != 3);
fclose( f );
return !failed;
}
return false;
}
bool readormakecell( cell &c, const char *filename, int x, int y, int z )
{
if ( readcell( c, filename, x, y, z ) )
return true;
makecell( c, NULL, NULL );
offsetcell( c, x, y, z );
return false;
}
void clipcelltoportals( cell &c, int x, int y, int z )
{
char filename[256];
sprintf( filename, "brick_%d_%d_%d.v.cell", x, y, z );
if ( !readormakecell( c, filename, x*256, y*256, z*256 ) )
return;
int ofs[][3] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 }, { -1, 0, 0 }, { 0, -1, 0 }, { 0, 0, -1 } };
cell n[6];
for (int i=0; i<6; i++)
{
sprintf( filename, "brick_%d_%d_%d.v.cell", x+ofs[i][0], y+ofs[i][1], z+ofs[i][2] );
readormakecell( n[i], filename, (x+ofs[i][0])*256, (y+ofs[i][1])*256, (z+ofs[i][2])*256 );
}
intersect( c, n, 6 );
}
int _tmain(int argc, _TCHAR* argv[])
{
#if 0
std::vector< std::string > files;
findFiles( files, argv[1] );
for (unsigned int i=0; i<files.size(); i++)
{
printf( "cell '%s'\n", files[i].c_str() );
makecell( (files[i]+".cell").c_str(), files[i].c_str() );
}
#endif
#if 1
float bb[2][3];
if ( readhdr( bb, "voxel.hdr" ) )
{
int ibb[2][3];
ibb[0][0] = 85-16;//(int)floorf( bb[0][0] );
ibb[0][1] = -712-16;//(int)floorf( bb[0][1] );
ibb[0][2] = 0-16;//(int)floorf( bb[0][2] );
ibb[1][0] = ibb[0][0]+16;//(int)ceilf( bb[1][0] );
ibb[1][1] = ibb[0][1]+16;//(int)ceilf( bb[1][1] );
ibb[1][2] = ibb[0][2]+16;//(int)ceilf( bb[1][2] );
ibb[0][0] = (int)floorf( bb[0][0] );
ibb[0][1] = (int)floorf( bb[0][1] );
ibb[0][2] = (int)floorf( bb[0][2] );
ibb[1][0] = (int)ceilf( bb[1][0] );
ibb[1][1] = (int)ceilf( bb[1][1] );
ibb[1][2] = (int)ceilf( bb[1][2] );
std::vector< cell > cells;
int w = (ibb[1][0]-ibb[0][0]);
int h = (ibb[1][1]-ibb[0][1]);
int d = (ibb[1][2]-ibb[0][2]);
cells.resize( w*h*d );
for (int z=ibb[0][2]; z<ibb[1][2]; z++)
{
printf("."); fflush(stdout);
int basez = z - ibb[0][2];
for (int y=ibb[0][1]; y<ibb[1][1]; y++)
{
int basey = y - ibb[0][1];
for (int x=ibb[0][0]; x<ibb[1][0]; x++)
{
int basex = x - ibb[0][0];
clipcelltoportals( cells[basex+(basey*w)+(basez*(w*h))], x, y, z );
}
}
}
writeobjofcell( "vis2.obj", &cells[0], cells.size() );
}
#endif
#if 0
makecell( "brick_25_-705_-7.cell", "brick_25_-705_-7.v" );
makecell( "brick_26_-705_-7.cell", "brick_26_-705_-7.v" );
makecell( "brick_25_-704_-7.cell", "brick_25_-704_-7.v" );
makecell( "brick_25_-705_-6.cell", "brick_25_-705_-6.v" );
makecell( "brick_24_-705_-7.cell", "brick_24_-705_-7.v" );
makecell( "brick_25_-706_-7.cell", "brick_25_-706_-7.v" );
makecell( "brick_25_-705_-8.cell", "brick_25_-705_-8.v" );
cell c00;
readcell( c00, "brick_25_-705_-7.cell", 0, 0, 0 );
cell n[6];
readcell( n[0], "brick_26_-705_-7.cell", 256, 0, 0 );
readcell( n[1], "brick_25_-704_-7.cell", 0, 256, 0 );
readcell( n[2], "brick_25_-705_-6.cell", 0, 0, 256 );
readcell( n[3], "brick_24_-705_-7.cell",-256, 0, 0 );
readcell( n[4], "brick_25_-706_-7.cell", 0,-256, 0 );
readcell( n[5], "brick_25_-705_-8.cell", 0, 0,-256 );
intersect( c00, n, 6 );
#endif
#if 0
{
FILE *f = fopen( "inter_portals.obj", "wb" );
if ( f )
{
for (unsigned int i=0; i<leaves.size(); i++)
{
for (unsigned int j=i+1; j<leaves.size(); j++)
{
if ( !touching( leaves[i], leaves[j] ) )
continue;
for (int face=0; face<6; face++)
{
quad q = clipquad( generatequad( leaves[i], face ), leaves[j] );
if ( isvalidquad( q ) )
{
outputquad( f, q );
}
}
}
}
}
}
{
std::vector< node* > external;
external.push_back( createbound( 0, 0, 256, 256, 256, 512 ) );
external.push_back( createbound( 256, 0, 0, 512, 256, 256 ) );
external.push_back( createbound( 0, 256, 0, 256, 512, 256 ) );
external.push_back( createbound( -256, 0, 0, 0, 256, 256 ) );
external.push_back( createbound( 0, -256, 0, 256, 0, 256 ) );
external.push_back( createbound( 0, 0, -256, 256, 256, 0 ) );
FILE *f = fopen( "external_portals.obj", "wb" );
if ( f )
{
for (unsigned int i=0; i<leaves.size(); i++)
{
for (unsigned int j=0; j<external.size(); j++)
{
if ( !touching( leaves[i], external[j] ) )
continue;
for (int face=0; face<6; face++)
{
quad q = clipquad( generatequad( leaves[i], face ), external[j] );
if ( isvalidquad( q ) )
{
outputquad( f, q );
}
}
}
}
}
}
if ( 0 )
{
FILE *f = fopen( "debug.obj", "wb" );
if ( f )
{
outputleafboxes( f, n );
fclose( f );
}
}
#endif
return 0;
}
// compressiondxt.cpp : Defines the entry point for the console application.
//
#define STB_IMAGE_WRITE_IMPLEMENTATION
#include "stdafx.h"
#include "malloc.h"
#include "DDS.h"
#include "DDSTextureLoader.h"
#include "stb_image_write.h"
#include "crn_win32_timer.h"
#include <math.h>
#include <vector>
#include "miniz.h"
#define PARANOID 0
#include <map>
#include <list>
int *k_means( float **data, float *weights, int n, int m, int k, float t, float **centroids)
{
int iter = 50;
/* output cluster label for each data point */
int *labels = (int*)calloc(n, sizeof(int));
int h, i, j; /* loop counters, of course :) */
float *counts = (float*)calloc(k, sizeof(float)); /* size of each cluster */
float old_error, error = FLT_MAX; /* sum of squared euclidean distance */
float **c = centroids ? centroids : (float**)calloc(k, sizeof(float*));
float **c1 = (float**)calloc(k, sizeof(float*)); /* temp centroids */
assert(data && k > 0 && k <= n && m > 0 && t >= 0); /* for debugging */
/****** initialization */
for (h = i = 0; i < k; h += n / k, i++) {
c1[i] = (float*)calloc(m, sizeof(float));
if (!centroids) {
c[i] = (float*)calloc(m, sizeof(float));
}
/* pick k points as initial centroids */
for (j = m; j-- > 0; c[i][j] = data[h][j]);
}
/****** main loop */
do {
/* save error from last step */
old_error = error, error = 0;
/* clear old counts and temp centroids */
for (i = 0; i < k; counts[i++] = 0) {
for (j = 0; j < m; c1[i][j++] = 0);
}
for (h = 0; h < n; h++) {
/* identify the closest cluster */
float min_distance = FLT_MAX;
for (i = 0; i < k; i++) {
float distance = 0.f;
for (j = m; j-- > 0; distance += pow(data[h][j] - c[i][j], 2));
if (distance < min_distance) {
labels[h] = i;
min_distance = distance;
}
}
float w = weights ? weights[h] : 1.f;
/* update size and temp centroid of the destination cluster */
for (j = m; j-- > 0; c1[labels[h]][j] += data[h][j]*w);
counts[labels[h]]+=w;
/* update standard error */
error += min_distance;
}
for (i = 0; i < k; i++) { /* update all centroids */
for (j = 0; j < m; j++) {
c[i][j] = (counts[i]>0.f) ? c1[i][j] / counts[i] : c1[i][j];
}
}
printf("err %f\n", fabs(error - old_error) );
} while (--iter && fabs(error - old_error) > t);
/****
** housekeeping */
for (i = 0; i < k; i++) {
if (!centroids) {
free(c[i]);
}
free(c1[i]);
}
if (!centroids) {
free(c);
}
free(c1);
free(counts);
return labels;
}
struct rc_model
{
unsigned int tot;
unsigned int *pmf;
unsigned int *cdf;
int numSym;
};
static void rc_model_init (rc_model *acm, int nsym, int *ifreq, int adapt)
{
int i;
if ( nsym == 0 )
{
memset( acm, 0, sizeof(rc_model) );
return;
}
acm->numSym = nsym;
acm->pmf = (unsigned int *) (void *) calloc (nsym, sizeof (int));
acm->cdf = (unsigned int *) (void *) calloc (nsym+1, sizeof (int));
acm->tot = 0;
if (ifreq) {
acm->cdf[acm->numSym] = 0;
for (i=acm->numSym-1; i>=0; i--) {
acm->pmf[i] = ifreq[i];
acm->cdf[i] = acm->cdf[i+1] + acm->pmf[i];
}
} else {
for (i=0; i<acm->numSym; i++) {
acm->pmf[i] = 1;
acm->cdf[i] = acm->numSym - i;
}
}
acm->tot = acm->cdf[0];
}
static void rc_model_update(rc_model *acm, int sym)
{
int i;
if (acm->tot==16383) {
acm->cdf[acm->numSym] = 0;
for (i = acm->numSym-1; i>=0; i--) {
acm->pmf[i] = (acm->pmf[i] + 1) / 2;
acm->cdf[i] = acm->cdf[i+1] + acm->pmf[i];
}
acm->tot = acm->cdf[0];
return;
} else
{
acm->pmf[sym]++;
for (i=sym; i>=0; i--) {
acm->cdf[i]++;
}
acm->tot = acm->cdf[0];
}
}
static void rc_model_done (rc_model *acm)
{
free (acm->pmf);
acm->pmf = NULL;
free (acm->cdf);
acm->cdf = NULL;
}
struct rc_context
{
FILE *f;
unsigned char *readbuffer;
unsigned int bufferSize;
unsigned int range;
unsigned int low;
unsigned int code;
unsigned int pos;
unsigned int total_bits;
};
// output most significant byte
static void putbyte ( rc_context *ctx )
{
unsigned char c = ctx->low >> 24;
if ( ctx->f )
{
fwrite( &c, 1, 1, ctx->f );
}
else
{
if ( (ctx->total_bits/8) < ctx->bufferSize )
{
ctx->readbuffer[ctx->total_bits/8] = c;
}
}
ctx->low <<= 8; // shift out top 8 bits
ctx->total_bits += 8;
}
// normalize the range and output data
void rc_normalise_enc ( rc_context *ctx )
{
while ((( ctx->low ^ ( ctx->low + ctx->range )) >> 24) == 0)
{
putbyte( ctx ); // top 8 bits of interval are fixed ;...
ctx->range <<= 8; // ... output them and normalize interval
}
if (( ctx->range >> 16) == 0)
{
putbyte ( ctx ); // top 8 bits are not fixed but range ...
putbyte ( ctx ); // ... is small ; fudge range to avoid ...
ctx->range = (~ctx->low+1);//- ctx->low ; // ... carry and output top 16 bits
}
}
inline unsigned int firstHighBit( unsigned int v )
{
register unsigned int r;
register unsigned int shift;
r = (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3 ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);
return r;
}
// normalize the range and output data
void rc_normalise_dec ( rc_context *ctx )
{
unsigned int bitTest = ctx->low ^ ( ctx->low + ctx->range );
unsigned int bitShift = 24 - ( firstHighBit( bitTest ) & (~0x7) );
unsigned int rangeShift = 16 * ( ctx->range <= ( (unsigned int)0xffff >> bitShift ) );
bitShift += rangeShift;
ctx->pos += bitShift >> 3;
ctx->low <<= bitShift;
ctx->range = rangeShift ? (~ctx->low+1) : (ctx->range<<bitShift);
ctx->code = (((unsigned int)ctx->readbuffer[ctx->pos+0])<<24) |
(((unsigned int)ctx->readbuffer[ctx->pos+1])<<16) |
(((unsigned int)ctx->readbuffer[ctx->pos+2])<<8) |
(((unsigned int)ctx->readbuffer[ctx->pos+3])<<0);
}
void rc_encoder_init( rc_context *rc, FILE *f )
{
rc->f = f;
rc->low = 0;
rc->code = 0;
rc->pos = 0;
rc->range = 0xffffffff;
rc->readbuffer = 0;
rc->bufferSize = 0;
rc->total_bits = 0;
}
void rc_encoder_init( rc_context *rc, unsigned char *buffer, int bufferSize )
{
rc->f = NULL;
rc->low = 0;
rc->code = 0;
rc->pos = 0;
rc->range = 0xffffffff;
rc->readbuffer = buffer;
rc->bufferSize = bufferSize;
rc->total_bits = 0;
}
void rc_encoder_done( rc_context *ctx )
{
for (int n=0; n<4; n++)
{
putbyte( ctx );
}
}
void rc_decoder_init( rc_context *rc, const unsigned char *data )
{
rc->f = NULL;
rc->readbuffer = (unsigned char*)data;
rc->low = 0;
rc->code = 0;
rc->pos = 0;
rc->range = 0xffffffff;
rc->total_bits = 0;
rc->code = (((unsigned int)rc->readbuffer[rc->pos+0])<<24) |
(((unsigned int)rc->readbuffer[rc->pos+1])<<16) |
(((unsigned int)rc->readbuffer[rc->pos+2])<<8) |
(((unsigned int)rc->readbuffer[rc->pos+3])<<0);
}
// encode a symbol s using probability modeling
void rc_encode_symbol ( rc_context *ctx, rc_model * m, unsigned s )
{
if ( m->numSym == 0 )
return;
assert( s < m->numSym );
unsigned int cdf = m->cdf[s] - m->pmf[s];
ctx->range /= m-> tot ; // tot = sum of pmf
if ( ctx->range == 0 )
printf("");
ctx->low += ctx->range * cdf; // cdf = cum . distribution function P(x < s)
ctx->range *= m-> pmf [s ]; // pmf = probability mass function P(x = s)
if ( ctx->range == 0 )
printf("");
rc_model_update(m, s ); // update probabilities
rc_normalise_enc ( ctx ); // normalize interval
}
unsigned rc_decode_symbol ( rc_context *ctx, rc_model * m )
{
ctx->range /= m->tot;
//unsigned freq= ((*(unsigned int*)&ctx->readbuffer[ctx->pos])/*ctx->code*/-ctx->low) / (ctx->range);
unsigned int freq= (ctx->code-ctx->low) / (ctx->range);
assert( freq < m->tot );
unsigned s;
if ( m->numSym < 8 )
{
for (s = 0; m->cdf[s+1]>freq; s++) ;
} else
{
int mn = 0;
int mx = m->numSym;
while ( (mx-mn) > 8 )
{
int md = (mn+mx+1)/2;
if ( m->cdf[md+1] > freq )
{
mn = md;
} else
{
mx = md;
}
}
for (s = mn; m->cdf[s+1]>freq; s++) ;
}
unsigned int cdf = m->cdf[s] - m->pmf[s];
ctx->low += ctx->range * cdf; // cdf = cum . distribution function P(x < s)
ctx->range *= m->pmf[s]; // pmf = probability mass function P(x = s)
rc_model_update(m, s ); // update probabilities
rc_normalise_dec ( ctx ); // normalize interval
return s;
}
static unsigned int makeCtx( unsigned int a, unsigned int b, unsigned int c )
{
return (a<<16)|(b<<8)|c;
}
static int determineMatchSize( const unsigned char *buffer, int buffer_len, int a, int b )
{
int len = 0;
while ( len < 255 && (a+len)<buffer_len && (b+len)<buffer_len && buffer[a+len] == buffer[b+len] )
{
len++;
}
return len;
}
static bool findCode( int &code, int &ofs, const int distances[], int numDistances, int inputDist )
{
for (int i=0; i<numDistances; i++)
{
if ( inputDist >= distances[i] && inputDist < distances[i+1] )
{
code = i;
ofs = inputDist - distances[code];
return true;
}
}
code = numDistances-1;
ofs = inputDist - distances[code];
return true;
}
int zz_compress( unsigned char *outbuffer, unsigned int *out_buffer_len, const unsigned char *buffer, int buffer_len, int numBits )
{
std::map< unsigned int, std::list<unsigned int> > match;
const int lengths[] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 83, 99, 115, 131, 163, 195, 227, 258, 259 };
const int numLengths = (sizeof(lengths) / sizeof(lengths[0]))-1;
const int distances[] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577, 32769 };
const int numDistances = (sizeof(distances) / sizeof(distances[0]))-1;
const int symbols = 1 << numBits;
const int eos = symbols+1;
const int matched = eos+1;
rc_context ctx;
rc_encoder_init( &ctx, outbuffer, *out_buffer_len );
rc_model rc_m_symbol;
rc_model rc_m_distances;
rc_model rc_m_lengths[numLengths];
rc_model rc_m_distancesExtra[numDistances];
rc_model_init( &rc_m_symbol, symbols+1+numLengths, NULL, 1 );
rc_model_init( &rc_m_distances, 30, NULL, 1 );
for (int i=0; i<numLengths; i++)
{
rc_model_init( &rc_m_lengths[i], lengths[i+1]-lengths[i], NULL, 1 );
}
for (int i=0; i<numDistances; i++)
{
rc_model_init( &rc_m_distancesExtra[i], distances[i+1]-distances[i], NULL, 1 );
}
for (int i=0; i<buffer_len;)
{
int matchLen = 0;
int matchLoc = -1;
if ( (i+3) < buffer_len )
{
std::map< unsigned int, std::list<unsigned int> >::iterator f = match.find( makeCtx(buffer[i+0], buffer[i+1], buffer[i+2]) );
if ( f != match.end() )
{
std::list<unsigned int> &matches = f->second;
std::list<unsigned int>::iterator m = matches.begin();
while ( m != matches.end() )
{
unsigned int distance = i - *m;
if ( distance < 32768 )
{
int ml = determineMatchSize( buffer, buffer_len, i, *m );
if ( ml > matchLen )
{
matchLen = ml;
matchLoc = *m;
}
m++;
}
else
{
m = matches.erase( m );
}
}
}
}
int starti = i;
if ( matchLen < 3 )
{
rc_encode_symbol( &ctx, &rc_m_symbol, buffer[i] );
i++;
}
else
{
int distance = i - matchLoc;
int cl, ol;
findCode( cl, ol, lengths, numLengths, matchLen );
rc_encode_symbol( &ctx, &rc_m_symbol, matched+cl );
if ( rc_m_lengths[cl].numSym > 1 )
rc_encode_symbol( &ctx, &rc_m_lengths[cl], ol );
int cd, od;
findCode( cd, od, distances, numDistances, distance );
rc_encode_symbol( &ctx, &rc_m_distances, cd );
if ( rc_m_distancesExtra[cd].numSym > 1 )
rc_encode_symbol( &ctx, &rc_m_distancesExtra[cd], od );
i+=matchLen;
}
unsigned int lastCtx = -1;
while ( starti < i )
{
int ctxLoc = starti-2;
if ( ctxLoc >= 0 )
{
unsigned int newCtx = makeCtx(buffer[ctxLoc+0], buffer[ctxLoc+1], buffer[ctxLoc+2]);
if ( newCtx != lastCtx )
{
match[newCtx].push_back( ctxLoc );
lastCtx = newCtx;
}
}
starti++;
}
}
rc_encode_symbol( &ctx, &rc_m_symbol, eos );
rc_encoder_done( &ctx );
rc_model_done( &rc_m_symbol );
rc_model_done( &rc_m_distances );
for (int i=0; i<numLengths; i++)
{
rc_model_done( &rc_m_lengths[i] );
}
for (int i=0; i<numDistances; i++)
{
rc_model_done( &rc_m_distancesExtra[i] );
}
if ( (*out_buffer_len) > (ctx.total_bits / 8) )
{
*out_buffer_len = ctx.total_bits / 8;
return 0;
}
else
{
return -5;
}
}
int zz_decompress( unsigned char *outbuffer, unsigned int *out_buffer_len, const unsigned char *buffer, int buffer_len, int numBits )
{
const int lengths[] = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 83, 99, 115, 131, 163, 195, 227, 258, 259 };
const int numLengths = (sizeof(lengths) / sizeof(lengths[0]))-1;
const int distances[] = { 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577, 32769 };
const int numDistances = (sizeof(distances) / sizeof(distances[0]))-1;
const int symbols = 1 << numBits;
const int eos = symbols+1;
const int matched = eos+1;
rc_context ctx;
rc_decoder_init( &ctx, buffer );
rc_model rc_m_symbol;
rc_model rc_m_distances;
rc_model rc_m_lengths[numLengths];
rc_model rc_m_distancesExtra[numDistances];
rc_model_init( &rc_m_symbol, symbols+1+numLengths, NULL, 1 );
rc_model_init( &rc_m_distances, 30, NULL, 1 );
for (int i=0; i<numLengths; i++)
{
rc_model_init( &rc_m_lengths[i], lengths[i+1]-lengths[i], NULL, 1 );
}
for (int i=0; i<numDistances; i++)
{
rc_model_init( &rc_m_distancesExtra[i], distances[i+1]-distances[i], NULL, 1 );
}
unsigned int writePos = 0;
while ( 1 )
{
int sym = rc_decode_symbol( &ctx, &rc_m_symbol );
if ( sym == eos )
break;
if ( sym < symbols )
{
outbuffer[writePos++] = sym;
}
else
{
int cl = sym - matched;
int ol = 0;
if ( rc_m_lengths[cl].numSym > 1 )
ol = rc_decode_symbol( &ctx, &rc_m_lengths[cl] );
int cd = rc_decode_symbol( &ctx, &rc_m_distances );
int od = 0;
if ( rc_m_distancesExtra[cd].numSym > 1 )
od = rc_decode_symbol( &ctx, &rc_m_distancesExtra[cd] );
int distance = distances[cd] + od;
int matchLen = lengths[cl] + ol;
int matchLoc = writePos - distance;
for (int i=0; i<matchLen; i++)
{
if ( writePos < *out_buffer_len )
outbuffer[writePos] = outbuffer[matchLoc];
writePos++;
matchLoc++;
}
}
}
rc_model_done( &rc_m_symbol );
rc_model_done( &rc_m_distances );
for (int i=0; i<numLengths; i++)
{
rc_model_done( &rc_m_lengths[i] );
}
for (int i=0; i<numDistances; i++)
{
rc_model_done( &rc_m_distancesExtra[i] );
}
if ( (*out_buffer_len) <= writePos )
{
*out_buffer_len = writePos;
return 0;
}
else
{
return -5;
}
}
static void *readFile( const char *filename, int &len )
{
FILE *f = fopen( filename, "rb" );
if ( f )
{
fseek( f, 0, SEEK_END );
len = ftell( f );
fseek( f, 0, SEEK_SET );
void *m = malloc( len );
fread( m, 1, len, f );
fclose( f );
return m;
}
return NULL;
}
struct dxtrgbblock
{
unsigned char c0[2];
unsigned char c1[2];
unsigned char bits[4];
};
struct bc3block
{
unsigned char a[2];
unsigned char bits[6];
};
struct dxta5block
{
unsigned char a0;
unsigned char a1;
unsigned char a[6];
};
struct dxt5block
{
bc3block a;
dxtrgbblock rgb;
};
void extractRGB565( unsigned char rgb[3], unsigned short colour )
{
rgb[0] = (colour >> ( 5 + 6 )) & ((1<<5)-1);
rgb[1] = (colour >> ( 5 )) & ((1<<6)-1);
rgb[2] = (colour >> ( 0 )) & ((1<<5)-1);
rgb[0] = (rgb[0] << 3) | (rgb[0] >> (5-3));
rgb[1] = (rgb[1] << 2) | (rgb[1] >> (6-2));
rgb[2] = (rgb[2] << 3) | (rgb[2] >> (5-3));
}
void generate4ColourSet( unsigned char rgb2[3], unsigned char rgb3[3], const unsigned char rgb0[3], const unsigned char rgb1[3] )
{
rgb2[0] = (2*(int)rgb0[0] + (int)rgb1[0])/3;
rgb2[1] = (2*(int)rgb0[1] + (int)rgb1[1])/3;
rgb2[2] = (2*(int)rgb0[2] + (int)rgb1[2])/3;
rgb3[0] = ((int)rgb0[0] + 2*(int)rgb1[0])/3;
rgb3[1] = ((int)rgb0[1] + 2*(int)rgb1[1])/3;
rgb3[2] = ((int)rgb0[2] + 2*(int)rgb1[2])/3;
}
void generate3ColourSet( unsigned char rgb2[3], unsigned char rgb3[3], const unsigned char rgb0[3], const unsigned char rgb1[3] )
{
rgb2[0] = ((int)rgb0[0] + (int)rgb1[0])/2;
rgb2[1] = ((int)rgb0[1] + (int)rgb1[1])/2;
rgb2[2] = ((int)rgb0[2] + (int)rgb1[2])/2;
rgb3[0] = 0;
rgb3[1] = 0;
rgb3[2] = 0;
}
int predictGreen( int up, int left, int diag, int &method )
{
int ma = abs(abs(diag-up) - abs(diag-left));
int mb = abs(diag-up);
int mc = abs(diag-left);
if ( ma < 4 && mb < 4 )
{
method = 0;
return left+up-diag;
} else
if ( ma < 10 )
{
method = 1;
return (left+up)/2;
} else
if ( ma < 64 )
{
if ( mb < mc )
{
method = 2;
return (3*left+up)/4;
} else
{
method = 3;
return (3*up+left)/4;
}
} else
{
if ( mb < mc )
{
method = 4;
return left;
} else
{
method = 5;
return up;
}
}
}
int findClosestG( unsigned char blockrgb[4][3], int g )
{
int best = 0;
int besterr = abs( blockrgb[best][1] - g );
for (int i=1; i<4; i++)
{
int err = abs( blockrgb[i][1] - g );
if ( err < besterr )
{
besterr = err;
best = i;
}
}
return best;
}
inline int sqr( int v )
{
return v*v;
}
int findClosestRGB( unsigned char blockrgb[4][3], int r, int g, int b )
{
int best = 0;
int besterr = sqr( blockrgb[best][0] - r ) + sqr( blockrgb[best][1] - g ) + sqr( blockrgb[best][2] - b );
for (int i=1; i<4; i++)
{
int err = sqr( blockrgb[i][0] - r ) + sqr( blockrgb[i][1] - g ) + sqr( blockrgb[i][2] - b );//abs( blockrgb[i][1] - g );
if ( err < besterr )
{
besterr = err;
best = i;
}
}
return best;
}
int findClosestA( unsigned char blocka[8], int a )
{
int best = 0;
int besterr = abs(blocka[best] - a);
for (int i=1; i<8; i++)
{
int err = abs(blocka[i] - a);
if ( err < besterr )
{
besterr = err;
best = i;
}
}
return best;
}
inline unsigned int ZigZag(int word) {
return (word >> 15) ^ (word << 1);
}
inline unsigned int UnZigZag(int word) {
return (word >> 1) ^ (-(word&1));
}
int jpeglsPredictor( int up, int left, int diag, int &method )
{
int mxul = max(up,left);
int mnul = min(up,left);
if ( diag >= mxul )
{
method = 0;
return mnul;
} else
if ( diag <= mnul )
{
method = 1;
return mxul;
}
method = 2;
return up+left-diag;
}
int PaethPredictor(int up, int left, int diag, int &method )
{
int p = left + up - diag;
int pa = abs(p - left);
int pb = abs(p - up);
int pc = abs(p - diag);
// return nearest of left,b,c,
// breaking ties in order left,b,c.
if ( pa <= pb && pa <= pc )
{
method = 0;
return left;
}
if ( pb <= pc )
{
method = 1;
return up;
}
method = 2;
return diag;
}
int iFreq0[] =
{ 53, 1, 24, 8 };
int iFreq1[] =
{ 2, 79, 10, 28 };
int iFreq2[] =
{ 18, 5, 37, 19 };
int iFreq3[] =
{ 6, 26, 31, 58 };
int runLength( dxtrgbblock *blocks, int x, int w )
{
int count = 0;
for (int i=1; i<8 && (x+i)<w; i++)
{
if ( memcmp( &blocks[x], &blocks[x+i], sizeof(dxtrgbblock) ) )
{
break;
}
count++;
}
return count;
}
int runLength( dxt5block *blocks, int x, int w )
{
int count = 0;
for (int i=1; i<8 && (x+i)<w; i++)
{
if ( memcmp( &blocks[x], &blocks[x+i], sizeof(dxt5block) ) )
{
break;
}
count++;
}
return count;
}
int runLength( void *blocks, int blockSize, int x, int w )
{
int count = 0;
for (int i=1; i<8 && (x+i)<w; i++)
{
if ( memcmp( &(((char*)blocks)[i*blockSize]), blocks, blockSize ) )
{
break;
}
count++;
}
return count;
}
static float IndexGradientOrder4[] = { 0.f, 3.f, 1.f, 2.f };
static float IndexGradientOrder3[] = { 1.f, 3.f, 2.f, -10000.f };
static int remap4[] = { 0, 2, 3, 1 };
static int remap3[] = { 3, 0, 2, 1 };
int roundf( float v )
{
return (int)floorf( v + 0.5f );
}
inline int clamp( int v, int mn, int mx )
{
return (v<mn) ? mn : (v>mx) ? mx : v;
}
unsigned int mapSelector( float *v, int *remap )
{
unsigned int bits = 0;
int selectorIndex = 0;
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
int idx = remap[ clamp( roundf( v[selectorIndex++] ), (remap == remap3) ? 1 : 0, 3 ) ];
bits |= idx << (2*(4*i+j));
}
}
return bits;
}
void kmeanstest( const DDSLoadDesc &desc, const D3D11_SUBRESOURCE_DATA * initData )
{
return;
int curw = desc.width;
int curh = desc.height;
int numSelectors = 0;
for (int ml=0; ml<desc.mips; ml++)
{
bool isdxt1 = true;
int blockw = (curw+3)/4;
int blockh = (curh+3)/4;
numSelectors += blockw * blockh;
curw = curw/2;
curh = curh/2;
if (curw == 0)
curw = 1;
if (curh == 0)
curh = 1;
}
float **selectors = (float**)malloc( numSelectors * sizeof( float* ) );
float *weights = (float*)malloc( numSelectors * sizeof( float ) );
float *selectorVectors = (float*)malloc( numSelectors * sizeof( float ) * 16 );
int curSelector = 0;
curw = desc.width;
curh = desc.height;
for (int ml=0; ml<desc.mips; ml++)
{
bool isdxt1 = true;
int blockw = (curw+3)/4;
int blockh = (curh+3)/4;
for (int y=0; y<blockh; y++)
{
dxtrgbblock *blocks = (dxtrgbblock*)((char*)initData[ml].pSysMem + y * initData[ml].SysMemPitch);
for (int x=0; x<blockw; x++)
{
unsigned short colour0 = blocks[x].c0[0] + blocks[x].c0[1] * 256;
unsigned short colour1 = blocks[x].c1[0] + blocks[x].c1[1] * 256;
unsigned int bits = blocks[x].bits[0] + 256 * ((int)blocks[x].bits[1] + 256 * ((int)blocks[x].bits[2] + 256 * (int)blocks[x].bits[3]));
unsigned char blockrgb[2][3];
extractRGB565( blockrgb[0], colour0 );
extractRGB565( blockrgb[1], colour1 );
selectors[curSelector] = &selectorVectors[curSelector*16];
weights[curSelector] = /*sqrtf*/( (((float)blockrgb[0][0]-(float)blockrgb[1][0]) * ((float)blockrgb[0][0]-(float)blockrgb[1][0])) +
(((float)blockrgb[0][1]-(float)blockrgb[1][1]) * ((float)blockrgb[0][1]-(float)blockrgb[1][1])) +
(((float)blockrgb[0][2]-(float)blockrgb[1][2]) * ((float)blockrgb[0][2]-(float)blockrgb[1][2])) );
float *gradient;
if ( (colour0 > colour1) || !isdxt1 )
{
gradient = IndexGradientOrder4;
} else
{
gradient = IndexGradientOrder3;
}
int selectorIndex = 0;
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
selectors[curSelector][selectorIndex] = gradient[ (bits >> (2*(4*i+j))) & 3 ];
selectorIndex++;
}
}
curSelector++;
}
}
curw = curw/2;
curh = curh/2;
if (curw == 0)
curw = 1;
if (curh == 0)
curh = 1;
}
int k = 2048;
float **centroids = (float **)malloc( k * sizeof( float* ) );
float *centroidVector = (float *)malloc( k * sizeof( float ) * 16 );
for (int i=0; i<k; i++)
{
centroids[i] = &centroidVector[ i * 16 ];
}
int *label = k_means( selectors, weights, numSelectors, 16, k, 0.01f, centroids );
curSelector = 0;
curw = desc.width;
curh = desc.height;
for (int ml=0; ml<desc.mips; ml++)
{
bool isdxt1 = true;
int blockw = (curw+3)/4;
int blockh = (curh+3)/4;
for (int y=0; y<blockh; y++)
{
dxtrgbblock *blocks = (dxtrgbblock*)((char*)initData[ml].pSysMem + y * initData[ml].SysMemPitch);
for (int x=0; x<blockw; x++)
{
unsigned short colour0 = blocks[x].c0[0] + blocks[x].c0[1] * 256;
unsigned short colour1 = blocks[x].c1[0] + blocks[x].c1[1] * 256;
unsigned int testbits = blocks[x].bits[0] + 256 * ((int)blocks[x].bits[1] + 256 * ((int)blocks[x].bits[2] + 256 * (int)blocks[x].bits[3]));
unsigned int bits = mapSelector( centroids[ label[curSelector] ], ( (colour0 > colour1) || !isdxt1 ) ? remap4 : remap3 );
blocks[x].bits[0] = bits & 0xff;
blocks[x].bits[1] = (bits>>8) & 0xff;
blocks[x].bits[2] = (bits>>16) & 0xff;
blocks[x].bits[3] = (bits>>24) & 0xff;
curSelector++;
}
}
curw = curw/2;
curh = curh/2;
if (curw == 0)
curw = 1;
if (curh == 0)
curh = 1;
}
}
void compress_bc1_lcct( const char *filename, const DDSLoadDesc &desc, const D3D11_SUBRESOURCE_DATA * initData )
{
static unsigned char imgchunks[2][(4096/4) * (4096/4) * 3 ] = {0};
static unsigned char decompressed[4096 * 4096 * 3] = {0};
// static unsigned char imgindices[2048 * 2048 ] = {0};
// static unsigned char predindices[2048 * 2048 ] = {0};
FILE *f = fopen( filename, "wb" );
fwrite( &desc, 1, sizeof(DDSLoadDesc), f );
rc_context rciindicesEnc;
rc_encoder_init( &rciindicesEnc, f );
rc_model rciindicesModel[3*3*3][4];
for (int i=0; i<(3*3*3); i++)
{
rc_model_init( &rciindicesModel[i][0], 4, iFreq0, 1 );
rc_model_init( &rciindicesModel[i][1], 4, iFreq1, 1 );
rc_model_init( &rciindicesModel[i][2], 4, iFreq2, 1 );
rc_model_init( &rciindicesModel[i][3], 4, iFreq3, 1 );
}
rc_model rcrllModel;
rc_model_init( &rcrllModel, 8, NULL, 1 );
rc_model rcTestModel;
rc_model_init( &rcTestModel, 256, NULL, 1 );
rc_model rccolmodel[6][2][3];
int initialfreq[256*2];
for (int j=0; j<2; j++)
{
for (int c=0; c<3; c++)
{
int bits = c == 1 ? 6 : 5;
for (int i = 0; i<((1<<bits)*2)+1; i++)
{
initialfreq[i] = 1+((1<<bits)/(((i+1)/2)+1));
}
rc_model_init( &rccolmodel[0][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
rc_model_init( &rccolmodel[1][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
rc_model_init( &rccolmodel[2][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
rc_model_init( &rccolmodel[3][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
rc_model_init( &rccolmodel[4][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
rc_model_init( &rccolmodel[5][j][c], ((1<<bits)*2)+1, initialfreq, 1 );
}
}
int rcencodeindexbits = 0;
int rcencodeimagebits[2] = { 0 };
int uncindexbits = 0;
int uncimagebits[2] = { 0 };
int counts[3] = { 0 };
int curw = desc.width;
int curh = desc.height;
for (int ml=0; ml<desc.mips; ml++)
{
bool isdxt1 = true;
int blockw = (curw+3)/4;
int blockh = (curh+3)/4;
for (int y=0; y<blockh; y++)
{
dxtrgbblock *blocks = (dxtrgbblock*)((char*)initData[ml].pSysMem + y * initData[ml].SysMemPitch);
for (int x=0; x<blockw; x++)
{
int indices[4][4];
unsigned short colour0 = blocks[x].c0[0] + blocks[x].c0[1] * 256;
unsigned short colour1 = blocks[x].c1[0] + blocks[x].c1[1] * 256;
unsigned int bits = blocks[x].bits[0] + 256 * ((int)blocks[x].bits[1] + 256 * ((int)blocks[x].bits[2] + 256 * (int)blocks[x].bits[3]));
unsigned char blockrgb[4][3];
extractRGB565( blockrgb[0], colour0 );
extractRGB565( blockrgb[1], colour1 );
if ( (colour0 > colour1) || !isdxt1 )
{
generate4ColourSet( blockrgb[2], blockrgb[3], blockrgb[0], blockrgb[1] );
} else
{
generate3ColourSet( blockrgb[2], blockrgb[3], blockrgb[0], blockrgb[1] );
}
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
indices[i][j] = (bits >> (2*(4*i+j))) & 3;
}
}
int index = (y * blockw + x)*3;
imgchunks[0][index+0] = blockrgb[0][0];
imgchunks[0][index+1] = blockrgb[0][1];
imgchunks[0][index+2] = blockrgb[0][2];
imgchunks[1][index+0] = blockrgb[1][0];
imgchunks[1][index+1] = blockrgb[1][1];
imgchunks[1][index+2] = blockrgb[1][2];
{
int upy = (y-1);
int leftx = (x-1);
int upindex = (upy * blockw + x) * 3;
int leftindex = (y * blockw + leftx) * 3;
int diagindex = (upy * blockw + leftx) * 3;
int curindex = (y * blockw + x) * 3;
for (int r=0; r<2; r++)
{
long rcstartbits = rciindicesEnc.total_bits;
int error = 0;
for (int c=0; c<3; c++)
{
int up = upy >= 0 ? imgchunks[r][upindex+c] : 0;
int left = leftx >= 0 ? imgchunks[r][leftindex+c] : 0;
int diag = (upy >= 0 && leftx >= 0) ? imgchunks[r][diagindex+c] : 0;
int actual = imgchunks[r][curindex+c];
int bits = c == 1 ? 6 : 5;
up >>= (8-bits);
left >>= (8-bits);
diag >>= (8-bits);
actual >>= (8-bits);
int method;
int predict = jpeglsPredictor( up, left, diag, method );
//int predict = predictGreen( up, left, diag, method );
predict += error;
if ( predict < 0 )
{
predict = 0;
}
if ( predict >= (1<<bits) )
{
predict = (1<<bits)-1;
}
int diff = predict - actual;
int zzdiff = ZigZag( diff );
error = -diff;
rc_encode_symbol (&rciindicesEnc, &rccolmodel[method][r][c], zzdiff);
uncimagebits[r] += 16;
}
long rcendbits = rciindicesEnc.total_bits;
rcencodeimagebits[r] += rcendbits - rcstartbits;
}
}
long rcstartbits = rciindicesEnc.total_bits;
#if 1
int errorR = 0;
int errorG = 0;
int errorB = 0;
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
unsigned char zeros[3] = { 0, 0, 0 };
int upy = (y*4+i-1);
int leftx = (x*4+j-1);
int upindex = (upy * (blockw*4) + (x*4+j)) * 3;
int leftindex = ((y*4+i) * (blockw*4) +leftx) * 3;
int diagindex = (upy * (blockw*4) + leftx) * 3;
int curindex = ((y*4+i) * (blockw*4) + (x*4+j)) * 3;
unsigned char* left = leftx >= 0 ? &decompressed[leftindex] : zeros;
unsigned char* up = upy >= 0 ? &decompressed[upindex] : left;//zeros;
unsigned char* diag = (upy >= 0 && leftx >= 0) ? &decompressed[diagindex] : up;//zeros;
int actualIndex = indices[i][j];
int methodr, methodg, methodb;
int pr = predictGreen( up[0], left[0], diag[0], methodr );
int pg = predictGreen( up[1], left[1], diag[1], methodg );
int pb = predictGreen( up[2], left[2], diag[2], methodb );
int pindex = findClosestG( blockrgb, pg );
int methodR, methodG, methodB ;
int predictR = jpeglsPredictor( up[0], left[0], diag[0], methodR );
int predictG = jpeglsPredictor( up[1], left[1], diag[1], methodG );
int predictB = jpeglsPredictor( up[2], left[2], diag[2], methodB );
predictR += errorR;
predictG += errorG;
predictB += errorB;
int pindex2 = findClosestRGB( blockrgb, pr, pg, pb );
int pindex3 = findClosestRGB( blockrgb, predictR, predictG, predictB );
int method = methodg;
method = ((methodR * 3 + methodG)*3 + methodB);// % 6;
assert( method < (3*3*3) );
pindex = pindex3;
counts[0] += pindex == actualIndex;
counts[1] += pindex2 == actualIndex;
counts[2] += pindex3 == actualIndex;
float diffr = ((float)blockrgb[actualIndex][0] - (float)blockrgb[pindex][0]);
float diffg = ((float)blockrgb[actualIndex][1] - (float)blockrgb[pindex][1]);
float diffb = ((float)blockrgb[actualIndex][2] - (float)blockrgb[pindex][2]);
//errorR = diffr;//blockrgb[actualIndex][0] - predictR;
//errorG = diffg;//blockrgb[actualIndex][1] - predictG;
//errorB = diffb;//blockrgb[actualIndex][2] - predictB;
//if ( i || j )
//{
// errorR = blockrgb[actualIndex][0] - predictR;
// errorG = blockrgb[actualIndex][1] - predictG;
// errorB = blockrgb[actualIndex][2] - predictB;
//}
float dist = sqrtf( diffr * diffr + diffg * diffg + diffb * diffb );
if ( (((int)dist)>>3) <= 0.f )
{
//actualIndex = pindex;
}
int diff = pindex - actualIndex;
int zzdiff = ZigZag( diff );
int decindex = ((y*4+i) * (blockw*4) + (x*4+j));
// predindices[decindex] = zzdiff * 16;
rc_encode_symbol (&rciindicesEnc, &rciindicesModel[method][pindex], actualIndex);
decompressed[curindex+0] = blockrgb[actualIndex][0];
decompressed[curindex+1] = blockrgb[actualIndex][1];
decompressed[curindex+2] = blockrgb[actualIndex][2];
}
}
#else
rc_encode_symbol( &rciindicesEnc, &rcTestModel, blocks[x].bits[0] );
rc_encode_symbol( &rciindicesEnc, &rcTestModel, blocks[x].bits[1] );
rc_encode_symbol( &rciindicesEnc, &rcTestModel, blocks[x].bits[2] );
rc_encode_symbol( &rciindicesEnc, &rcTestModel, blocks[x].bits[3] );
#endif
uncindexbits += 2 * 16;
long rcendbits = rciindicesEnc.total_bits;
rcencodeindexbits += rcendbits - rcstartbits;
int rll = runLength( blocks, x, blockw );
rc_encode_symbol (&rciindicesEnc, &rcrllModel, rll);
for (int r=0; r<rll; r++)
{
memcpy( &imgchunks[0][index+(r+1)*3], &imgchunks[0][index+0], 3 );
memcpy( &imgchunks[1][index+(r+1)*3], &imgchunks[1][index+0], 3 );
for (int j=0; j<4; j++)
{
int dstindex = ((y*4+j) * (blockw*4) + (x+r+1)*4) * 3;
int curindex = ((y*4+j) * (blockw*4) + (x*4)) * 3;
memcpy( &decompressed[dstindex], &decompressed[curindex], 4*3 );
}
}
x += rll;
}
}
curw = curw/2;
curh = curh/2;
if (curw == 0)
curw = 1;
if (curh == 0)
curh = 1;
}
rc_encoder_done (&rciindicesEnc);
for (int i=0; i<(3*3*3); i++)
{
rc_model_done (&rciindicesModel[i][0]);
rc_model_done (&rciindicesModel[i][1]);
rc_model_done (&rciindicesModel[i][2]);
rc_model_done (&rciindicesModel[i][3]);
}
for (int j=0; j<2; j++)
{
for (int c=0; c<3; c++)
{
rc_model_done( &rccolmodel[0][j][c] );
rc_model_done( &rccolmodel[1][j][c] );
rc_model_done( &rccolmodel[2][j][c] );
rc_model_done( &rccolmodel[3][j][c] );
rc_model_done( &rccolmodel[4][j][c] );
rc_model_done( &rccolmodel[5][j][c] );
}
}
//printf( "index %f k (%.2f%%) (%.2f%% of original)\n", rcencodeindexbits / (8.f*1024.f), (rcencodeindexbits*100.f)/(rcencodeindexbits), (rcencodeindexbits*100.f)/(uncindexbits) );
printf( "index %f k (%.2f%%) (%.2f%% of original)\n", rcencodeindexbits / (8.f*1024.f), (rcencodeindexbits*100.f)/(rcencodeindexbits+rcencodeimagebits[0]+rcencodeimagebits[1]), (rcencodeindexbits*100.f)/(uncindexbits) );
printf( "rgb0 %f k (%.2f%%) (%.2f%% of original)\n", rcencodeimagebits[0] / (8.f*1024.f), (rcencodeimagebits[0]*100.f)/(rcencodeindexbits+rcencodeimagebits[0]+rcencodeimagebits[1]), (rcencodeimagebits[0]*100.f)/(uncimagebits[0]) );
printf( "rgb1 %f k (%.2f%%) (%.2f%% of original)\n", rcencodeimagebits[1] / (8.f*1024.f), (rcencodeimagebits[1]*100.f)/(rcencodeindexbits+rcencodeimagebits[0]+rcencodeimagebits[1]), (rcencodeimagebits[1]*100.f)/(uncimagebits[1]) );
fclose( f );
}
struct rgba
{
union
{
struct
{
unsigned char r, g, b, a;
};
unsigned char c[4];
};
};
void extractBC1BlockData( unsigned char cols[4][3], int indices[4][4], dxtrgbblock const *block, bool isBC1 )
{
unsigned short colour0 = block->c0[0] + block->c0[1] * 256;
unsigned short colour1 = block->c1[0] + block->c1[1] * 256;
unsigned int bits = block->bits[0] + 256 * ((unsigned int)block->bits[1] + 256 * ((unsigned int)block->bits[2] + 256 * (unsigned int)block->bits[3]));
extractRGB565( cols[0], colour0 );
extractRGB565( cols[1], colour1 );
if ( (colour0 > colour1) || !isBC1 )
{
generate4ColourSet( cols[2], cols[3], cols[0], cols[1] );
} else
{
generate3ColourSet( cols[2], cols[3], cols[0], cols[1] );
}
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
indices[i][j] = (bits >> (2*(4*i+j))) & 3;
}
}
}
static void generate6AlphaSet( unsigned char *a, unsigned char alpha_0, unsigned char alpha_1 )
{
a[0] = alpha_0;
a[1] = alpha_1;
a[2] = (6*alpha_0)/7 + (1*alpha_1)/7; // bit code 010
a[3] = (5*alpha_0)/7 + (2*alpha_1)/7; // bit code 011
a[4] = (4*alpha_0)/7 + (3*alpha_1)/7; // bit code 100
a[5] = (3*alpha_0)/7 + (4*alpha_1)/7; // bit code 101
a[6] = (2*alpha_0)/7 + (5*alpha_1)/7; // bit code 110
a[7] = (1*alpha_0)/7 + (6*alpha_1)/7; // bit code 111
}
static void generate4AlphaSet( unsigned char *a, unsigned char alpha_0, unsigned char alpha_1 )
{
// 4 interpolated alpha values.
a[0] = alpha_0;
a[1] = alpha_1;
a[2] = (4*alpha_0)/5 + (1*alpha_1)/5; // bit code 010
a[3] = (3*alpha_0)/5 + (2*alpha_1)/5; // bit code 011
a[4] = (2*alpha_0)/5 + (3*alpha_1)/5; // bit code 100
a[5] = (1*alpha_0)/5 + (4*alpha_1)/5; // bit code 101
a[6] = 0; // bit code 110
a[7] = 255; // bit code 111
}
void extractBC3BlockData( unsigned char alpha[8], int indices[4][4], bc3block const *block )
{
unsigned __int64 bits;
if ( block == NULL )
{
generate4AlphaSet( alpha, 0, 5 );
bits = 255 + 256 * ((unsigned __int64)255 +
256 * ((unsigned __int64)255 +
256 * ((unsigned __int64)255 +
256 * ((unsigned __int64)255 +
256 * ((unsigned __int64)255
)))));
}
else
{
if ( block->a[0] > block->a[1] )
{
generate6AlphaSet( alpha, block->a[0], block->a[1] );
}
else
{
generate4AlphaSet( alpha, block->a[0], block->a[1] );
}
bits = block->bits[0] + 256 * ((unsigned __int64)block->bits[1] +
256 * ((unsigned __int64)block->bits[2] +
256 * ((unsigned __int64)block->bits[3] +
256 * ((unsigned __int64)block->bits[4] +
256 * ((unsigned __int64)block->bits[5]
)))));
}
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
indices[i][j] = (bits >> (3*(4*i+j))) & 7;
}
}
}
inline int QuantizeGradient( int g )
{
const int T1 = 3;
const int T2 = 7;
const int T3 = 21;
const int NR = 0;
int Q;
if (g <= -T3) Q=-4;
else if (g <= -T2) Q=-3;
else if (g <= -T1) Q=-2;
else if (g < -NR) Q=-1;
else if (g <= NR) Q= 0;
else if (g < T1) Q= 1;
else if (g < T2) Q= 2;
else if (g < T3) Q= 3;
else Q= 4;
return Q;
}
int MergeContext( int &sign, int q1, int q2, int q3 )
{
if ( q1 < 0
|| (q1 == 0 && q2 < 0)
|| (q1 == 0 && q2 == 0 && q3 < 0) ) {
q1=-q1;
q2=-q2;
q3=-q3;
sign=-1; // signifies -ve
}
else {
sign=1; // signifies +ve
}
int q;
if (q1 == 0) {
if (q2 == 0) {
q=360+q3; // fills 360..364
}
else { // Q2 is 1 to 4
q=324+(q2-1)*9+(q3+4); // fills 324..359
}
}
else { // Q1 is 1 to 4
q=(q1-1)*81+(q2+4)*9+(q3+4); // fills 0..323
}
return q;
}
static int clockAdd( int a, int b, int numBits )
{
return (a+b) & ((1<<numBits)-1);
}
static int clockDiff( int a, int b, int numBits )
{
return ((a+(1<<numBits))-b) & ((1<<numBits)-1);
}
void compress_bc3_lcct( const char *filename, const DDSLoadDesc &desc, const D3D11_SUBRESOURCE_DATA * initData )
{
static rgba imgchunks[2][(4096/4) * 2 ] = {0};
static rgba decompressed[4096 * 8] = {0};
const int predictionbits[4] = { 5, 6, 5, 8 };
FILE *f = fopen( filename, "wb" );
fwrite( &desc, 1, sizeof(DDSLoadDesc), f );
rc_context rciindicesEnc;
rc_encoder_init( &rciindicesEnc, f );
rc_model rc_c_iindicesModel[3*3*3][4];
for (int i=0; i<(3*3*3); i++)
{
rc_model_init( &rc_c_iindicesModel[i][0], 4, iFreq0, 1 );
rc_model_init( &rc_c_iindicesModel[i][1], 4, iFreq1, 1 );
rc_model_init( &rc_c_iindicesModel[i][2], 4, iFreq2, 1 );
rc_model_init( &rc_c_iindicesModel[i][3], 4, iFreq3, 1 );
}
rc_model rc_a_iindicesModel[3][8];
for (int i=0; i<(3); i++)
{
rc_model_init( &rc_a_iindicesModel[i][0], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][1], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][2], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][3], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][4], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][5], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][6], 8, NULL, 1 );
rc_model_init( &rc_a_iindicesModel[i][7], 8, NULL, 1 );
}
rc_model rcrllModel;
rc_model_init( &rcrllModel, 8, NULL, 1 );
rc_model rcTestModel;
rc_model_init( &rcTestModel, 256, NULL, 1 );
rc_model rccolmodel[6][2][4];
int initialfreq[256*2+1];
for (int j=0; j<2; j++)
{
for (int c=0; c<4; c++)
{
int bits = predictionbits[c];
for (int i=0; i<(1<<bits); i++)
{
int mid = (1<<bits)/2;
int dist = i < mid ? i : ((1<<bits)-i-1);
initialfreq[i] = ((1<<bits)/(dist+1))+1;
}
rc_model_init( &rccolmodel[0][j][c], 1<<bits, NULL, 1 );
rc_model_init( &rccolmodel[1][j][c], 1<<bits, NULL, 1 );
rc_model_init( &rccolmodel[2][j][c], 1<<bits, NULL, 1 );
rc_model_init( &rccolmodel[3][j][c], 1<<bits, NULL, 1 );
rc_model_init( &rccolmodel[4][j][c], 1<<bits, NULL, 1 );
rc_model_init( &rccolmodel[5][j][c], 1<<bits, NULL, 1 );
}
}
int curw = desc.width;
int curh = desc.height;
for (int ml=0; ml<desc.mips; ml++)
{
bool isdxt1 = true;
int blockw = (curw+3)/4;
int blockh = (curh+3)/4;
for (int y=0; y<blockh; y++)
{
dxt5block *blocks = (dxt5block*)((char*)initData[ml].pSysMem + y * initData[ml].SysMemPitch);
for (int x=0; x<blockw; x++)
{
int indicesrgb[4][4];
unsigned char blockrgb[4][3];
extractBC1BlockData( blockrgb, indicesrgb, &blocks[x].rgb, false );
int indicesa[4][4];
unsigned char blocka[8];
extractBC3BlockData( blocka, indicesa, &blocks[x].a );
int index = ((y%2) * blockw + x);
imgchunks[0][index].r = blockrgb[0][0];
imgchunks[0][index].g = blockrgb[0][1];
imgchunks[0][index].b = blockrgb[0][2];
imgchunks[0][index].a = blocka[0];
imgchunks[1][index].r = blockrgb[1][0];
imgchunks[1][index].g = blockrgb[1][1];
imgchunks[1][index].b = blockrgb[1][2];
imgchunks[1][index].a = blocka[1];
// block end point encode
{
int cury = (y) % 2;
int upy = (y-1) % 2;
int leftx = (x-1);
int upindex = (upy * blockw + x);
int leftindex = (cury * blockw + leftx);
int diagindex = (upy * blockw + leftx);
int curindex = (cury * blockw + x);
int error = 0;
for (int r=0; r<2; r++)
{
for (int c=0; c<4; c++)
{
int left = leftx >= 0 ? imgchunks[r][leftindex].c[c] : 0;
int up = upy >= 0 ? imgchunks[r][upindex].c[c] : 0;
int diag = (upy >= 0 && leftx >= 0) ? imgchunks[r][diagindex].c[c] : 0;
int actual = imgchunks[r][curindex].c[c];
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], actual);
#endif
int bits = predictionbits[c];
up >>= (8-bits);
left >>= (8-bits);
diag >>= (8-bits);
actual >>= (8-bits);
int method;
int predict = jpeglsPredictor( up, left, diag, method );
predict += error;
if ( predict < 0 )
predict = 0;
if ( predict >= (1<<bits) )
predict = (1<<bits)-1;
int diff = predict - actual;
int zzdiff = clockDiff( actual, predict , bits );
int test = clockAdd( predict, zzdiff, bits );
assert( test == actual );
error = -diff;
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], up);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], left);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], diag);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], method);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], predict);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], actual);
#endif
rc_encode_symbol (&rciindicesEnc, &rccolmodel[method][r][c], zzdiff);
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], c);
#endif
}
}
unsigned short colour0 = ((unsigned short)(imgchunks[0][curindex].c[0]>>3) << (5+6)) |
((unsigned short)(imgchunks[0][curindex].c[1]>>2) << (5)) |
((unsigned short)(imgchunks[0][curindex].c[2]>>3));
unsigned short colour1 = ((unsigned short)(imgchunks[1][curindex].c[0]>>3) << (5+6)) |
((unsigned short)(imgchunks[1][curindex].c[1]>>2) << (5)) |
((unsigned short)(imgchunks[1][curindex].c[2]>>3));
assert( (colour0&0xff) == blocks[x].rgb.c0[0] );
assert( ((colour0>>8)&0xff) == blocks[x].rgb.c0[1] );
assert( (colour1&0xff) == blocks[x].rgb.c1[0] );
assert( ((colour1>>8)&0xff) == blocks[x].rgb.c1[1] );
}
if ( 1 )
{
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], blocks[x].rgb.c0[0]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], blocks[x].rgb.c0[1]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], blocks[x].rgb.c1[0]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], blocks[x].rgb.c1[1]);
#endif
for (int i=0; i<4; i++)
{
for (int j=0; j<4; j++)
{
unsigned char zeros[4] = { 0, 0, 0, 0 };
int cury = (y*4+i) % 8;
int upy = (y*4+i-1) % 8;
int leftx = (x*4+j-1);
int upindex = (upy * (blockw*4) + (x*4+j));
int leftindex = (cury * (blockw*4) +leftx);
int diagindex = (upy * (blockw*4) + leftx);
int curindex = (cury * (blockw*4) + (x*4+j));
unsigned char* left = leftx >= 0 ? decompressed[leftindex].c : zeros;
unsigned char* up = upy >= 0 ? decompressed[upindex].c : zeros;
unsigned char* diag = (upy >= 0 && leftx >= 0) ? decompressed[diagindex].c : zeros;
int actualIndex = indicesrgb[i][j];
int methodR, methodG, methodB ;
int predictR = jpeglsPredictor( up[0], left[0], diag[0], methodR );
int predictG = jpeglsPredictor( up[1], left[1], diag[1], methodG );
int predictB = jpeglsPredictor( up[2], left[2], diag[2], methodB );
int pindex = findClosestRGB( blockrgb, predictR, predictG, predictB );
int method = ((methodR * 3 + methodG)*3 + methodB);
assert( method < (3*3*3) );
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], up[0]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], left[0]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], diag[0]);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], methodR);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], predictR);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], method);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], pindex);
#endif
rc_encode_symbol (&rciindicesEnc, &rc_c_iindicesModel[method][pindex], actualIndex);
#if PARANOID
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], i);
rc_encode_symbol (&rciindicesEnc, &rccolmodel[0][0][3], j);
#endif