Intro:During last weekend I've decided to try implementing texture generation algorithm, where texture is being generated from example (photo or something else). I've got several interesting results, and a couple of problems. The attempt was inspired by
this paper(PDF link), but I decided to try simple bruteforce before trying to use "jumpmaps".
Links:
- Steve Zelinka's publications(includes couple of interesting material, like "Interactive Texture Synthesis on Surfaces Using Jump Maps.", "Mesh Modelling With Curve Analogies". Definitely worth checking out, however, I was only interested in texture generation at the moment.
- Jump maps on surfaces (pdf, Steve Zelinka and Michael Garland)
Results:Here is the example pattern I used:
And here is the result I got:
Algorithm:
- Fill destination image with black, and make every pixel transparent.
- Copy any pixel from pattern image into top-left corner of destination image.
- For every transparent pixel of destination image (i.e. alpha == 0) with non-transparent neighbors within search distance, replace it with pixel from pattern image where non-transparent pixels in neighborhood most closely resemble non-transparent pixels in destination image's neighborhood of current pixel. Best matching pixel found by bruteforce search (yes, it is slow). Repeat until there are no more transparent pixels left.
How neighborhoods are compared:
There are several ways to do this:
- Compute distance(within search distance) for every non-transparent pixel in current neighborhood, add distances up, divide sum by number of non-transparent pixels. Find pixel in pattern image with the smallest distance.
- Add up (into rgb vector) all non-transparent pixel within search distance in destination surface into one vector, Add up up all non-transparent pixels within search distance from candidate pixel in pattern surface, compute distance between them. Find surface with smallest distance.
Things to keep in mind:
- When calculating differences, watch out for transparency. DO not use pixels at offsets (from candidate) where source or pattern pixel are transparent.
- Destination surface should be tileable, so pixel operations wrap around. Pattern is no tileable, so pixels near the border should not used.
Good things:
- Tileable (well, you can see some repeating patterns, bot no obvious seams)
- Looks great/realistic.
Problems:
- It is incredibly slow. Example image took at least one hour (or more) to be finished. Cannot be used in realtime.
- I've run into problems when I tried to do same thing using OpenGL/GLSL and DirectX/HLSL (to see if it will work faster):
- In DirectX HLSL shader could not be compiled. D3DXCompileShaderFromFile simply hung during compilation, and I wasn't in the mood for assembly.
- In OpenGL, it looks like there is no way to select mip level from within GLSL fragment shader. So, I can say farewell to cheap search optimization.
- In OpenGL, I hit weird problem - entire system becomes unusable (stops responding, etc) when current frame is being rendered. And because one frame takes several seconds, this means, you can't do anything else on the system while application is running.
Perhaps it makes sense to try another algorithm or reimplement this thing on CUDA. Maybe I'll do it some other time, maybe not.
Code:Code is free to use/redistribute for non-commercial purposes.
Code didn't completely fit into window, and I'm not in the mood for template hacking right now. If you want to see everything, select, copy and paste code into notepad (or kedit/jedit or whatever).
sdl versionmain.cpp:
#include <SDL/SDL.h>
#include <SDL/SDL_image.h>
#include <common/timer.h>
#include <common/keyboard.h>
#include <wchar.h>
#include <math.h>
using Keyboard::keyPressed;
static Timer timer;
static int texPowX = 9;
static int texPowY = 9;
static int texWidth = 1 << texPowX;
static int texHeight = 1 << texPowY;
static int scrWidth = texWidth;
static int scrHeight = texHeight;
static int texMaskX = texWidth - 1;
static int texMaskY = texHeight - 1;
static int searchWidth = 3;
static int searchHeight = 3;
struct Dist{
unsigned long r, g, b;
};
size_t numPatternPixels = 0;
Dist* precomputedDist = 0;
struct Pixel{
unsigned char b, g, r, a;
};
void fillPixel(int x, int y, SDL_Surface* dst, SDL_Surface* src, int dstMaskX, int dstMaskY){
Pixel& dstPix = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*x + dst->pitch*y));
int xMin = x + texWidth - searchWidth;
int xMax = xMin + searchWidth*2;
int yMin = y + texHeight - searchHeight;
int yMax = yMin + searchHeight*2;
int numFilled = 0;
for (int curY = yMin; curY < yMax; curY++)
for (int curX = xMin; curX < xMax; curX++){
Pixel& cur = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*(curX & texMaskX) + dst->pitch*(curY & texMaskY)));
if (cur.a != 0)
numFilled++;
}
if (numFilled == 0){
int srcX = rand() % src->w;
int srcY = rand() % src->h;
dstPix = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*srcX + src->pitch*srcY));
dstPix.a = 0xFF;
return;
}
int storedSrcX = rand() % src->w;
int storedSrcY = rand() % src->h;
float lastDifference = 3.40282347e+37F;
//unsigned char mask =
for (int srcY = searchHeight; srcY < (src->h - searchHeight); srcY++)
for (int srcX = searchWidth; srcX < (src->w - searchWidth); srcX++){
float curDifference = 0;
int numPixels = 0;
for (int tmpY = -searchHeight; tmpY < searchHeight; tmpY++)
for(int tmpX = -searchWidth; tmpX < searchWidth; tmpX++){
Pixel& tmpSrc = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*(srcX+tmpX) + src->pitch*(srcY+tmpY)));
Pixel& tmpDst = *((Pixel*)((char*)(dst->pixels) + sizeof(Pixel)*((x + dst->w + tmpX) & dstMaskX) + dst->pitch*((y + dst->h + tmpY) & dstMaskY)));
if (tmpDst.a){
numPixels++;
int dr = tmpSrc.r - tmpDst.r;
int dg = tmpSrc.g - tmpDst.g;
int db = tmpSrc.g - tmpDst.g;
curDifference += dr*dr + dg*dg + db*db;
}
}
if (numPixels)
curDifference /= (float)numPixels;
if (curDifference < lastDifference){
lastDifference = curDifference;
storedSrcX = srcX;
storedSrcY = srcY;
}
}
dstPix = *((Pixel*)((char*)(src->pixels) + sizeof(Pixel)*storedSrcX + src->pitch*storedSrcY));
dstPix.a = 0xFF;
}
int main(int argc, char** argv){
SDL_Init(SDL_INIT_VIDEO);
SDL_GL_SetAttribute(SDL_GL_RED_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_GREEN_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_BLUE_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_DEPTH_SIZE, 16);
SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);
Keyboard::init();
timer.reset();
timer.setMaxFps(100);
timer.setMinFps(5);
SDL_Surface* screen = SDL_SetVideoMode(scrWidth, scrHeight, 32, SDL_SWSURFACE);
SDL_Surface *texture = SDL_CreateRGBSurface(SDL_SWSURFACE, scrWidth, scrHeight, 32, 0x00FF0000, 0x0000FF00, 0x000000FF, 0xFF000000);
if (screen == 0){
fprintf(stderr, "couldn't set mode %dx%d!\n", 640, 480);
SDL_Quit();
return -1;
}
SDL_Surface *image = IMG_Load("example.png");
SDL_Surface *example = SDL_CreateRGBSurface(SDL_SWSURFACE, image->w, image->h, 32, 0x00FF0000, 0x0000FF00, 0x000000FF, 0xFF000000);
SDL_BlitSurface(image, 0, example, 0);
SDL_FreeSurface(image);
SDL_LockSurface(example);
numPatternPixels = example->w * example->h;
precomputedDist = new Dist[numPatternPixels * 256];
memset(precomputedDist, 0, sizeof(Dist)*numPatternPixels*256);
for (int mask = 0; mask < 256; mask++){
printf("processing mask %d", mask);
for (int y = 0; y < example->h; y++)
for (int x = 0; x < example->w; x++){
Dist& curDist = precomputedDist[x + y*example->h + mask*numPatternPixels];
}
}
size_t numPixels = scrWidth*scrHeight;
SDL_LockSurface(texture);
for (int y = 0; y <scrHeight; y++)
for (int x = 0; x < scrWidth; x++){
Pixel& cur = *((Pixel*)((char*)(texture->pixels) + sizeof(Pixel)*x + texture->pitch*y));
cur.r = cur.g = cur.b = 0xFF;
cur.a = 0;
}
SDL_UnlockSurface(texture);
int x = 0;
int y = 0;
bool running = true;
while (running){
SDL_Event event;
if (SDL_PollEvent(&event)){
switch(event.type){
case SDL_QUIT:
running = false;
break;
};
}
timer.update();
Keyboard::update();
SDL_LockSurface(texture);
for (int i = 0; (i < 100) && (y < scrHeight); i++){
/*Pixel& cur = *((Pixel*)((char*)(texture->pixels) + sizeof(Pixel)*x + texture->pitch*y));
cur.r = rand() & 0xFF;
cur.g = rand() & 0xFF;
cur.b = rand() & 0xFF;
cur.a = 0xFF;*/
fillPixel(x, y, texture, example, texMaskX, texMaskY);
x++;
if (x >= scrWidth){
x = 0;
y++;
}
}
SDL_UnlockSurface(texture);
static bool saved = false;
if ((y >= scrHeight) && !saved){
SDL_SaveBMP(texture, "result.bmp");
saved = true;
}
if (keyPressed(SDLK_ESCAPE))
running = false;
SDL_BlitSurface(texture, 0, screen, 0);
SDL_UpdateRect(screen, 0, 0, scrWidth, scrHeight);
}
delete[] precomputedDist;
SDL_UnlockSurface(example);
SDL_FreeSurface(example);
SDL_FreeSurface(texture);
SDL_Quit();
return 0;
}
OpenGL version:
#include <SDL/SDL.h>
#include <glee/glee.h>
#include <GL/gl.h>
#include <GL/glu.h>
#include <common/glutils.h>
#include <common/Framebuffer.h>
#include <common/textures.h>
#include <common/timer.h>
#include <common/keyboard.h>
#include <FTGL/FTGL.h>
#include <FTGL/FTGLPixmapFont.h>
#include <wchar.h>
#include <math.h>
using Keyboard::keyPressed;
static Timer timer;
static const int texSize = 128;
static int scrWidth = texSize;
static int scrHeight = texSize;
static const int searchSize = 3;
static const char* vsText =
"varying vec2 texCoords;\n"
" const float gridSize = 10.0;\n"
"void main(void){\n"
" gl_Position = ftransform();\n"
" texCoords = gl_MultiTexCoord0;\n"
"}\n";
static const char* fsText =
"varying vec2 texCoords;\n"
"uniform sampler2D srcTex;\n"
"uniform sampler2D patternTex;\n"
"uniform vec2 srcTextureSize;\n"
"uniform vec2 srcPixelSize;\n"
"uniform vec2 patternTextureSize;\n"
"uniform vec2 patternPixelSize;\n"
"uniform vec2 searchSize;\n"
"void main(void){\n"
" vec2 uv = texCoords;\n"
" vec4 thisColor = texture2D(srcTex, uv);\n"
" gl_FragColor = thisColor;\n"
" if (thisColor.a > 0.0)\n"
" return;\n"
" vec4 leftColor = texture2D(srcTex, uv - vec2(srcPixelSize.x, 0.0));\n"
" vec4 topColor = texture2D(srcTex, uv - vec2(0.0, srcPixelSize.y));\n"
/*" vec4 rightColor = texture2D(srcTex, uv + vec2(srcPixelSize.x, 0.0));\n"
" vec4 bottomColor = texture2D(srcTex, uv + vec2(0.0, srcPixelSize.y));\n"
" if ((leftColor.a == 0.0)&&(topColor.a == 0.0)&&(rightColor.a == 0.0)&&(bottomColor.a == 0.0))\n"*/
" if ((leftColor.a == 0.0)&&(topColor.a == 0.0))\n"
" return;\n"
" float lastDistance = 0.0;\n"
" bool first = true;\n"
" vec2 lastCoords = vec2(0.0);\n"
" vec2 patEndCoords = (patternTextureSize - searchSize - vec2(0.5))*patternPixelSize;\n"
" vec2 patStartCoords = (searchSize + vec2(0.5))*patternPixelSize;\n"
" vec2 patCoords = patStartCoords;\n"
" for(patCoords.y = patStartCoords.y; patCoords.y < patEndCoords.y; patCoords.y += patternPixelSize.y){\n"
" for(patCoords.x = patStartCoords.x; patCoords.x < patEndCoords.x; patCoords.x += patternPixelSize.x){\n"
" vec2 tmpCoords = vec2(0.0);\n"
" float distance = 0.0;\n"
" for(tmpCoords.y = -searchSize.y; tmpCoords.y <= searchSize.y; tmpCoords.y += 1.0){\n"
" for(tmpCoords.x = -searchSize.x; tmpCoords.x <= searchSize.x; tmpCoords.x += 1.0){\n"
" vec4 srcColor = texture2D(srcTex, (tmpCoords*srcPixelSize) + uv);\n"
" vec4 patternColor = texture2D(patternTex, (tmpCoords*patternPixelSize) + patCoords);\n"
" if (srcColor.a > 0.0){\n"
" vec3 dist = srcColor.xyz - patternColor.xyz;\n"
" distance += dot(dist, dist);\n"
" }\n"
" }\n"
" }\n"
" if (first||(distance < lastDistance)){\n"
" lastDistance = distance;\n"
" lastCoords = patCoords;\n"
" first = false;\n"
" }\n"
" }\n"
" }\n"
" gl_FragColor = texture2D(patternTex, lastCoords);\n"
" gl_FragColor.a = 1.0;\n"
"}\n";
void textureRect(float x, float y, float width, float height){
float x1 = x, y1 = y, x2 = x1 + width, y2 = y1 + height;
glBegin(GL_TRIANGLE_FAN);
glTexCoord2f(0, 0);
glVertex2f(x1, y1);
glTexCoord2f(1, 0);
glVertex2f(x2, y1);
glTexCoord2f(1, 1);
glVertex2f(x2, y2);
glTexCoord2f(0, 1);
glVertex2f(x1, y2);
glEnd();
}
int main(int argc, char** argv){
srand(GetTickCount());
SDL_Init(SDL_INIT_VIDEO);
SDL_GL_SetAttribute(SDL_GL_RED_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_GREEN_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_BLUE_SIZE, 8);
SDL_GL_SetAttribute(SDL_GL_DEPTH_SIZE, 16);
SDL_GL_SetAttribute(SDL_GL_DOUBLEBUFFER, 1);
SDL_GL_SetAttribute(SDL_GL_SWAP_CONTROL, 0);
Keyboard::init();
timer.reset();
/*timer.setMaxFps(100);
timer.setMinFps(5);*/
if (scrWidth <= 128){
scrWidth = texSize * 4;
scrHeight = texSize * 4;
}
if (SDL_SetVideoMode(scrWidth, scrHeight, 32, SDL_OPENGL) == 0){
fprintf(stderr, "couldn't set mode %dx%d!\n", scrWidth, scrHeight);
SDL_Quit();
return -1;
}
FTGLPixmapFont font("DejaVuSans.ttf");
font.CharMap(ft_encoding_unicode);
font.FaceSize(10);
FTGLPixmapFont largeFont("DejaVuSans.ttf");
largeFont.CharMap(ft_encoding_unicode);
largeFont.FaceSize(40);
SDL_ShowCursor(SDL_DISABLE);
glClearColor(0, 0, 0, 0);
glClearDepth(1.0);
Framebuffer *framebuffers[2] = {0, 0};
framebuffers[0] = new Framebuffer();
framebuffers[1] = new Framebuffer();
for (int i = 0; i < 2; i++)
framebuffers[i]->setSize(texSize, texSize);
int currentFramebuffer = 0;
Texture* texture = new Texture("example3.png", GL_LINEAR_MIPMAP_LINEAR, GL_LINEAR_MIPMAP_LINEAR);
glEnable(GL_DEPTH_TEST);
glEnable(GL_TEXTURE_2D);
GLuint filterProgram = 0;
filterProgram = createProgram(vsText, fsText);
checkGlError();
GLuint srcSamplerUniform = glGetUniformLocation(filterProgram, "srcTex");
GLuint patternSamplerUniform = glGetUniformLocation(filterProgram, "patternTex");
GLuint srcTextureSizeUniform = glGetUniformLocation(filterProgram, "srcTextureSize");
GLuint srcPixelSizeUniform = glGetUniformLocation(filterProgram, "srcPixelSize");
GLuint patternTextureSizeUniform = glGetUniformLocation(filterProgram, "patternTextureSize");
GLuint patternPixelSizeUniform = glGetUniformLocation(filterProgram, "patternPixelSize");
GLuint searchSizeUniform = glGetUniformLocation(filterProgram, "searchSize");
bool running = true;
while (running){
SDL_Event event;
if (SDL_PollEvent(&event)){
switch(event.type){
case SDL_QUIT:
running = false;
break;
};
}
timer.update();
Keyboard::update();
currentFramebuffer = currentFramebuffer ^ 1;
Framebuffer* src = framebuffers[currentFramebuffer];
Framebuffer* dst = framebuffers[currentFramebuffer ^ 1];
if (keyPressed(SDLK_ESCAPE))
running = false;
glDisable(GL_DEPTH_TEST);
/*
framebuffer rendering
*/
dst->begin();
glClearColor(0, 0, 0, 0);
glClear(GL_COLOR_BUFFER_BIT);
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, dst->width, 0, dst->height);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glActiveTexture(GL_TEXTURE0);
glBindTexture(GL_TEXTURE_2D, src->renderTexture);
glEnable(GL_ALPHA_TEST);
glAlphaFunc(GL_GREATER, 0);
float f = 1.0f/ 9.1f;
/*glEnable(GL_BLEND);
glBlendFunc(GL_ONE, GL_ONE);*/
static bool first = true;
textureRect(0, 0, (float)(src->width), (float)(src->height));
bool justFinished = false;
if (first){
glActiveTexture(GL_TEXTURE0);
glBindTexture(GL_TEXTURE_2D, texture->tex);
float s = (float)(rand() % texture->width)/(float)texture->width;
float t = (float)(rand() % texture->height)/(float)texture->height;
glTexCoord2f(s, t);
glBegin(GL_POINTS);
glVertex2f(0, 0);
glEnd();
glRasterPos2i(10, 20);
//textureRect((float)(rand() % dst->width), (float)(rand() % dst->height), (float)(texture->width), (float)(texture->height));
//textureRect(0, 0, (float)(texture->width), (float)(texture->height));
first = false;
}
else{
textureRect(0, 0, (float)src->width, (float)src->height);
static int x = 0;
static int y = 0;
static const int tileSize = texSize;
static int xSize = texSize/tileSize;
static int ySize = texSize/tileSize;
static int counter = -tileSize;
if (y < ySize){
glActiveTexture(GL_TEXTURE1);
glBindTexture(GL_TEXTURE_2D, texture->tex);
glUseProgram(filterProgram);
if(filterProgram){
glUniform1i(srcSamplerUniform, 0);
glUniform1i(patternSamplerUniform, 1);
glUniform2f(srcTextureSizeUniform, (float)src->width, (float)src->height);
glUniform2f(srcPixelSizeUniform, 1.0f/(float)src->width, 1.0f/(float)src->height);
glUniform2f(patternTextureSizeUniform, (float)texture->width, (float)texture->height);
glUniform2f(patternPixelSizeUniform, 1.0f/(float)texture->width, 1.0f/(float)texture->height);
glUniform2f(searchSizeUniform, (float)searchSize, (float)searchSize);
}
float x1 = (float)(x * tileSize);
float s1 = x1/(float)(src->width);
float x2 = (float)((x+1) * tileSize);
float s2 = x2/(float)(src->width);
float y1 = (float)(y * tileSize);
float t1 = y1/(float)(src->height);
float y2 = (float)((y+1) * tileSize);
float t2 = y2/(float)(src->height);
glBegin(GL_TRIANGLE_FAN);
glTexCoord2f(s1, t1);
glVertex2f(x1, y1);
glTexCoord2f(s2, t1);
glVertex2f(x2, y1);
glTexCoord2f(s2, t2);
glVertex2f(x2, y2);
glTexCoord2f(s1, t2);
glVertex2f(x1, y2);
glEnd();
counter++;
if (counter >= tileSize){
counter = 0;
x++;
if (x >= xSize){
x = 0;
y++;
if (y >= ySize){
//save texture
justFinished = true;
}
}
}
}
//textureRect(0, 0, (float)src->width, (float)src->height);
}
glUseProgram(0);
glActiveTexture(GL_TEXTURE0);
dst->end();
if (justFinished){
SDL_Surface* tmp = SDL_CreateRGBSurface(SDL_SWSURFACE, dst->width, dst->height, 32, 0x00FF0000, 0x0000FF00, 0x000000FF, 0xFF000000);
SDL_LockSurface(tmp);
glBindTexture(GL_TEXTURE_2D, dst->renderTexture);
glGetTexImage(GL_TEXTURE_2D, 0, GL_BGRA, GL_UNSIGNED_BYTE, tmp->pixels);
SDL_UnlockSurface(tmp);
SDL_SaveBMP(tmp, "result.bmp");
SDL_FreeSurface(tmp);
}
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
gluOrtho2D(0, scrWidth, scrHeight, 0);
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glClearColor(0, 0, 0.5f, 0);
glClear(GL_COLOR_BUFFER_BIT);
glBindTexture(GL_TEXTURE_2D, dst->renderTexture);
//textureRect(0, 0, (float)dst->width, (float)dst->height);
textureRect(0, 0, (float)scrWidth, (float)scrHeight);
glBindTexture(GL_TEXTURE_2D, 0);
wchar_t buf[256];
swprintf(buf, 256, L"fps: %.2f", timer.getFps());
glRasterPos2i(10, 20);
font.Render(buf);
glFlush();
SDL_GL_SwapBuffers();
}
if (glIsProgram(filterProgram))
glDeleteProgram(filterProgram);
delete texture;
for (int i = 0; i < 2; i++)
delete framebuffers[i];
SDL_Quit();
return 0;
}
