Sunday, November 28, 2010

Creating random fractals in Java with Java2D

I thought it would be a fun exercise to write a fractal generator. Here is some code that creates simple tree fractals using Java. The algorithm is highly randomized and the current output looks more like some outer space blob than an actual tree.



Here is the source code. Copy & paste into eclipse, run, and see for yourself.
 import java.awt.BasicStroke;  
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.util.Random;

import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JScrollPane;
import javax.swing.SwingUtilities;

/**
* Program that generates a random fractal pattern
*
* @author brad
*
*/
public class MainPanel extends JLabel {

public static void main(String args[]) {

SwingUtilities.invokeLater(new Runnable() {

public void run() {

JFrame frame = new JFrame();
frame.setMinimumSize(new Dimension(800, 600));
frame.setContentPane(new JScrollPane(new MainPanel()));
frame.setVisible(true);
}

});
}

public MainPanel() {

BufferedImage newFrameImg = new BufferedImage(1920, 1200,
BufferedImage.TYPE_INT_ARGB);
this.setIcon(new ImageIcon(newFrameImg));

Graphics2D g2d = (Graphics2D) newFrameImg.getGraphics();
g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, // Anti-alias!
RenderingHints.VALUE_ANTIALIAS_ON);

g2d.setColor(Color.black);
g2d.fillRect(0, 0, 1920, 1200);
generateTreeFractal(g2d, 1920 / 2, 1200 / 2, 10, 200);
// generateTreeFractal(g2d, 1920/2, 1200/2,6 , 60);

}

private static Color brightness(Color c, double scale) {
int r = Math.min(255, (int) (c.getRed() * scale));
int g = Math.min(255, (int) (c.getGreen() * scale));
int b = Math.min(255, (int) (c.getBlue() * scale));
return new Color(r, g, b);
}

private void generateTreeFractal(Graphics2D g2d, double x, double y,
double lineWidth, double lineLength) {

// multipliers for recursion. Must be between 0 and 1
// WARNING: the closer these are to 1 the longer the run time will be
final double LINE_WIDTH_MULTILIER = .80;
final double LINE_LENGTH_MULTIPLIER = .85;

// base case - we need to stop somewhere
// or else we'll get a stack overflow
if (lineWidth <= 1 || lineLength <= 2) {
return;
}

Random rand = new Random();

// compute random number of lines to draw. Play with this.
int numOfLinesToDraw = 1 + rand.nextInt(4);

BasicStroke bs = new BasicStroke((float) lineWidth,
BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND);
g2d.setStroke(bs);
g2d.setColor(Color.gray);

// mess with the color
Color c = g2d.getColor();
// need a number from 0-1 to scale the color... I made this equation up
// it gives a cool shaded almost 3d effect. This should be played with
// to get better looking effects
c = brightness(
c,
Math.abs(Math.cos(x * x + y * y + lineWidth * lineWidth
+ lineLength * lineLength)));
g2d.setColor(c);

// draw lines
for (int i = 0; i < numOfLinesToDraw; i++) {
// first calculate random positive vector
double x1 = rand.nextDouble() - .5;
double y1 = rand.nextDouble() - .5;

// divide by magnitude so we get a unit vector
double mag = Math.sqrt(x1 * x1 + y1 * y1);
x1 = x1 / mag;
y1 = y1 / mag;

// scale by lineLength
x1 = x1 * lineLength;
y1 = y1 * lineLength;

// move to center
x1 = x1 + x;
y1 = y1 + y;

// now (x1,y1) represents point on circle with radius lineLength and
// centered around (x,y)
g2d.drawLine((int) x, (int) y, (int) x1, (int) y1);

// now recurse
generateTreeFractal(g2d, x1, y1, lineWidth * LINE_WIDTH_MULTILIER,
lineLength * LINE_LENGTH_MULTIPLIER);

}

}

}

ray tracing

I was looking through my inbox and I stumbled across an old ray tracing program (C++) I created for a homework assignment. I managed to get the 6+ year old project to compile and here's what it looks like:



Here is the source code. Compiles with g++ and SDL library
 #include <stdlib.h>  
#if defined(_MSC_VER)
#include "SDL.h"
#else
#include "SDL/SDL.h"
#endif


#include <math.h>
#include <queue>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
bool rayTracingEnabled = true;
bool bidirectionalLighting = false;
bool tumblingEnabled = true;
bool revolvingLight = false;

SDL_Surface *screen;
SDL_Surface *ship;
int SHIP_HEIGHT;
int SHIP_WIDTH;
#define S_WIDTH 640
#define S_HEIGHT 480
void draw_spaceship(int x, int y);
void render();

double lighting_mix = .3;
double zbuffer[640][480];



inline int roundDouble(double x)
{
return ((int)floor(x+.5));
}
struct vector3
{

double x;
double y;
double z;
vector3()
{
x = y = z = 0;
}
vector3(double x1, double y1, double z1)
{
x = x1;
y = y1;
z = z1;
}
double mag()
{
double sum = x*x + y*y + z*z;
return sqrt(sum);
}
void makeUnitVector()
{
double magOfThisShit = mag();
x = x/magOfThisShit;
y = y/magOfThisShit;
z = z/magOfThisShit;
}
};
struct sphere
{
vector3 center;
double radius;
unsigned int color;
sphere()
{
center = vector3(0,0,0);
radius = 0;
color = 0;
}
sphere(double x, double y, double z, double r, unsigned int c)
{
center.x = x;
center.y = y;
center.z = z;
radius = r;
color = c;
}
sphere (vector3 c, double rad, unsigned int co)
{
center = c;
radius = rad;
color = co;
}
};
vector<sphere> scene_sphere;
double scalarProduct(vector3 a, vector3 b)
{
return (a.x*b.x + a.y*b.y + a.z*b.z);
}

vector3 light_dir(-.25/sqrt(1.5),-.25/sqrt(1.5),-1/sqrt(1.5));


/** Subtracts 2 vectors, returning the difference */
vector3 vectorMinus(vector3 &v1, vector3 &v2) {
return vector3(v1.x - v2.x,
v1.y - v2.y,
v1.z - v2.z);
}

vector3 vectorScale(vector3 &v, double a)
{
return vector3(a*v.x, a*v.y, a*v.z);
}
vector3 vectorCross(vector3 a, vector3 b) {
// From Shirley p.27: a x b = (ay*bz - az*by, az*bx - ax*zb, ax*by-ay*bx)
return vector3(a.y*b.z - a.z*b.y,
a.z*b.x - a.x*b.z,
a.x*b.y - a.y*b.x);
}


void printVector(vector3 a)
{
cout << a.x << " " << a.y << " " << a.z << endl;
}
struct triangle
{
vector3 v1;
vector3 v2;
vector3 v3;
unsigned int color;
bool textured;
triangle()
{
color = 0;
}
triangle(vector3 a, vector3 b, vector3 c, unsigned int color1)
{
v1 = a;
v2 = b;
v3 = c;
color = color1;
}
triangle(vector3 a, vector3 b, vector3 c, unsigned int color1, bool istex)
{
textured = istex;
v1 = a;
v2 = b;
v3 = c;
color = color1;
}
void flipNormal()
{
vector3 temp = v2;
v2 = v1;
v1 = temp;
}
vector3 getNormalVector()
{
vector3 a = vectorMinus(v2,v1);
vector3 b = vectorMinus(v3,v1);
vector3 normal = vectorCross(a,b);
normal.makeUnitVector();
return normal;
}

double signedAreaXY()
{
double x1 = v3.x - v1.x;
double y1 = v3.y - v1.y;
double x2 = v2.x - v1.x;
double y2 = v2.y - v1.y;

double crossProd = x2*y1 - x1*y2;
return (crossProd*.5);
}

void baryXY(vector3 v, double &alpha, double &beta, double &gamma)
{
double x1;
double y1;
double x2;
double y2;

// get areaA
double areaB;
x1 = v2.x - v1.x;
y1 = v2.y - v1.y;
x2 = v.x - v1.x;
y2 = v.y - v1.y;

areaB = .5*(x1*y2 - x2*y1);

//get areaB
double areaA;
x1 = v2.x - v.x;
y1 = v2.y - v.y;
x2 = v3.x - v.x;
y2 = v3.y - v.y;
areaA = .5*(x1*y2 - x2*y1);

//get areaY
double areaY;
x1 = v3.x - v.x;
y1 = v3.y - v.y;
x2 = v1.x - v.x;
y2 = v1.y - v.y;
areaY = .5*(x1*y2 - x2*y1);

// get Total area;
double totalArea = signedAreaXY();

alpha = areaA/totalArea;
beta = areaB/totalArea;
gamma = areaY/totalArea;
}

void rasterize()
{
vector3 a[3];
a[0] = v1;
a[1] = v2;
a[2] = v3;

double minx = a[0].x;
double maxx = a[0].x;
double miny = a[0].y;
double maxy = a[0].y;
// get min and max
for (int i = 0; i < 3; i++)
{
if (a[i].x < minx)
{
minx = a[i].x;
}
if (a[i].x > maxx)
{
maxx = a[i].x;
}

if(a[i].y < miny)
{
miny = a[i].y;
}
if (a[i].y > maxy)
{
maxy = a[i].y;
}
}

int min_x = roundDouble(minx);
int max_x = roundDouble(maxx);
int min_y = roundDouble(miny);
int max_y = roundDouble(maxy);
// make sure within screen bounds
if (min_x < 0)
{
min_x = 0;
}
if (max_x >= S_WIDTH)
{
max_x = S_WIDTH -1;
}
if (min_y < 0 )
{
min_y = 0;
}
if (max_y >= S_HEIGHT )
{
max_y = S_HEIGHT - 1;
}

//iterate over screenbounds

bool printed = false;
for (int i = min_x; i <= max_x; i++)
{
for (int j = min_y; j <= max_y; j++)
{
//get bary coord
double alpha;
double beta;
double gamma;
baryXY(vector3(i,j,0),alpha,beta,gamma);

if ((alpha <= 1 && alpha >= 0)
&& (beta <= 1 && beta >= 0)
&& (gamma <= 1 && gamma >= 0)
)
{

double zcoord = alpha*v1.z + gamma*v2.z + beta*v3.z;
if (zbuffer[i][j] > zcoord )
{
vector3 normalHEH = getNormalVector();
double angleBetweenNormalAndLight = scalarProduct(normalHEH,light_dir);


if (angleBetweenNormalAndLight < 0)
{
if (bidirectionalLighting)
{
angleBetweenNormalAndLight = fabs(angleBetweenNormalAndLight);
}
else
{
angleBetweenNormalAndLight = 0;
}
}

double colorscalar = lighting_mix + (1 - lighting_mix)*angleBetweenNormalAndLight;

zbuffer[i][j] = zcoord;
unsigned int mask = 0x00FFFFFF;

unsigned int redChannel = color & mask;
redChannel = redChannel >> 16;
mask = 0x0000FF00;
unsigned int greenChannel = color & mask;

greenChannel = greenChannel >> 8;
mask = 0x000000FF;
unsigned int blueChannel = color & mask;
double nRed = colorscalar*((double)redChannel);
double nGreen = colorscalar*((double)greenChannel);
double nBlue = colorscalar*((double)blueChannel);

redChannel = (unsigned int) nRed;
greenChannel = (unsigned int) nGreen;
blueChannel = (unsigned int) nBlue;

redChannel = redChannel << 16;
greenChannel = greenChannel << 8;

unsigned int colorToAssign = redChannel + greenChannel + blueChannel;

((unsigned int *) screen->pixels)[j*S_WIDTH+i]=colorToAssign;
}
}
}
}
}
};

struct mat3h
{
double matrix[4][4];
mat3h()
{
}
void zero()
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
matrix[i][j] = 0;
}
}
}
void identity()
{
zero();
for(int i = 0; i < 4; i++)
{
matrix[i][i] = 1;
}
}
};

mat3h mat3hMult(mat3h a, mat3h b)
{
mat3h result;
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
double sum = 0;
for (int k = 0; k < 4; k++)
{
sum = sum + a.matrix[k][j]*b.matrix[i][k];
}
result.matrix[i][j] = sum;
}
}
return result;
}

vector3 matMult(mat3h a, vector3 v)
{
double result[3];
double homovector[4];
homovector[0] = v.x;
homovector[1] = v.y;
homovector[2] = v.z;
homovector[3] = 1;

for (int i = 0; i < 3; i++)
{
double sum = 0;
for (int j = 0; j < 4; j++)
{
sum = sum + homovector[j]*a.matrix[i][j];
}
result[i] = sum;
}
vector3 res(result[0], result[1], result[2]);
return res;
}

mat3h rot3hX(double theta)
{
mat3h result;
result.identity();
result.matrix[1][1] = cos(theta);
result.matrix[1][2] = -sin(theta);
result.matrix[2][1] = sin(theta);
result.matrix[2][2] = cos(theta);
return result;
}
mat3h rot3hY(double theta)
{
mat3h result;
result.identity();
result.matrix[0][0] = cos(theta);
result.matrix[0][2] = sin(theta);
result.matrix[2][0] = -sin(theta);
result.matrix[2][2] = cos(theta);
return result;

}
mat3h rot3hZ(double theta)
{
mat3h result;
result.identity();
result.matrix[0][0] = cos(theta);
result.matrix[0][1] = -sin(theta);
result.matrix[1][0] = sin(theta);
result.matrix[1][1] = cos(theta);
return result;
}
inline bool checkBounds(int x, int y)
{
if (x >= 0 && x < S_WIDTH && y >=0 && y < S_HEIGHT)
return true;
else
return false;
}
// no comment
void render()
{

// Ask SDL for the time in milliseconds
//int tick = SDL_GetTicks();

// Lock surface if needed
if (SDL_MUSTLOCK(screen))
if (SDL_LockSurface(screen) < 0)
return;

// Unlock if needed
if (SDL_MUSTLOCK(screen))
SDL_UnlockSurface(screen);

// Tell SDL to update the whole screen
SDL_UpdateRect(screen, 0, 0, 640, 480);
}

vector<triangle> scene;
vector3 eyePosition(0,0,-2);
vector3 screenPosition(0,0,-1);
double screenxwidth = 2;
double screenywidth = 1.5;
unsigned int backgroundcolor = 0;


// RAY TRACING FUNCTIONS
bool ray_sphere_intersect(vector3 &eye, vector3 &dir, sphere &S, double t0, double t1, double &new_t)
{
double dis = scalarProduct(dir, vectorMinus(eye, S.center));
dis = dis*dis;
dis = dis - scalarProduct(dir,dir)*( scalarProduct(vectorMinus(eye,S.center),vectorMinus(eye,S.center)) - S.radius*S.radius);

if (dis < 0)
{

return false;
}
dis = sqrt(dis);

double shitTerm = scalarProduct(vectorScale(dir, -1), vectorMinus(eye, S.center));
double bottomTerm = scalarProduct(dir,dir);

double time_1 = (shitTerm - dis)/bottomTerm;
double time_2 = (shitTerm + dis)/bottomTerm;
if (time_1 < 0 && time_2 < 0)
{
return false;
}
else if (time_1 < 0)
{
new_t = time_2;
}
else if (time_2 < 0)
{
new_t = time_1;
}
else
{
if (time_1 < time_2)
{
new_t = time_1;
}
else
{
new_t = time_2;
}
}
if (new_t < t0 || new_t > t1)
{
return false;
}

return true;
}
bool ray_triangle_intersect(vector3 eye, vector3 dir, triangle T, double t0, double t1,
double &new_beta, double &new_gamma,double &new_t)
{
vector3 v_a = T.v1;
vector3 v_b = T.v2;
vector3 v_c = T.v3;

double a = v_a.x - v_b.x;
double b = v_a.y - v_b.y;
double c = v_a.z - v_b.z;
double d = v_a.x - v_c.x;
double e = v_a.y - v_c.y;
double f = v_a.z - v_c.z;
double g = dir.x;
double h = dir.y;
double i = dir.z;

double j = v_a.x - eye.x;
double k = v_a.y - eye.y;
double l = v_a.z - eye.z;

//compute M
double M = a*(e*i - h*f) + b*(g*f -d*i) + c*(d*h - e*g);
//compute t
double t = (-1*(f*(a*k - j*b) +e*(j*c - a*l) + d*(b*l - k*c)))/M;

if (t < t0 || t > t1)
{
return false;
}

//compute gamma
double gamma = (i*(a*k - j*b)+ h*(j*c -a*l) + g*(b*l - k*c))/M;

if (gamma < 0 || gamma > 1)
{
return false;
}
//compute beta
double beta = (j*(e*i - h*f) + k*(g*f - d*i) + l*(d*h - e*g))/M;

if (beta < 0 || beta > 1-gamma)
{
return false;
}

new_t = t;
new_gamma = gamma;
new_beta = beta;
return true;



}
bool ray_hits_any_shape(bool &isTriangle, triangle &vis_tri, sphere &vis_sphere, vector3 eye, vector3 dir,
double &new_beta, double &new_gamma, double &new_t)
{
double tempBeta;
double tempGamma;
double t0 = .0001;
double t1 = INT_MAX; //switch this to max float
bool hit = false;
// check triangles
for (int i = 0; i < scene.size(); i++)
{
if (ray_triangle_intersect(eye, dir, scene[i], t0, t1, tempBeta, tempGamma,new_t))
{
new_beta = tempBeta;
new_gamma = tempGamma;
t1 = new_t;
hit = true;
vis_tri = scene[i];
isTriangle = true;
}
}
// check spheres
for (int i = 0; i < scene_sphere.size(); i++)
{
if (ray_sphere_intersect(eye, dir, scene_sphere[i], t0, t1, new_t))
{
t1 = new_t;
hit = true;
vis_sphere = scene_sphere[i];
isTriangle = false;
}
}
return hit;
}

bool in_shadow(vector3 hitpoint)
{
triangle vis_tri;
sphere vis_sphere;
double new_beta;
double new_gamma;
double new_t;
bool isTriangle;

return ray_hits_any_shape(isTriangle,vis_tri,vis_sphere,hitpoint,light_dir,
new_beta, new_gamma, new_t);
}
void ray_trace()
{
vector3 normalish = scene[0].getNormalVector();
normalish = scene[1].getNormalVector();
double xstart = -1*screenxwidth/2;
double xend = screenxwidth/2;
double ystart = -1*screenywidth/2;
double yend = screenywidth/2;
double xincrement = screenxwidth/S_WIDTH;
double yincrement = screenywidth/S_HEIGHT;

for (int x = 0; x < S_WIDTH; x++)
{
for (int y = 0; y < S_HEIGHT; y++)
{
vector3 screenpoint(xstart + x*xincrement, ystart + y*yincrement, screenPosition.z);
vector3 d = vectorMinus(screenpoint,eyePosition);
triangle vis_tri;
double beta;
double gamma;
double t;
bool isTriangle;
sphere vis_sphere;
if (ray_hits_any_shape(isTriangle,vis_tri,vis_sphere,eyePosition, d, beta, gamma, t))
{
vector3 intersectLoc(eyePosition.x + t*d.x, eyePosition.y + t*d.y, eyePosition.z + t*d.z);
vector3 normalToShape;
unsigned int color;

if (isTriangle)
{
//cout << "triangle" << endl;
color = vis_tri.color;
if (vis_tri.textured == true)
{
int xcoord = (int)intersectLoc.x;
int zcoord = (int)intersectLoc.z;
double d = 15;
int c = (int)ceil(xcoord/d);
if (c %2 == 0)
{
color = 0;
c = (int)ceil(zcoord/d);
if (c %2 == 1)
{
color = vis_tri.color;
}

}
else
{
c = (int)ceil(zcoord/d);
if (c %2 == 1)
{
color = 0;
}
}



}
normalToShape = vis_tri.getNormalVector();
}
else
{
color = vis_sphere.color;

normalToShape = vectorMinus(intersectLoc, vis_sphere.center);
normalToShape.x = normalToShape.x/vis_sphere.radius;
normalToShape.y = normalToShape.y/vis_sphere.radius;
normalToShape.z = normalToShape.z/vis_sphere.radius;
}

double alpha = 1 - beta - gamma;


////
double angleBetweenNormalAndLight = scalarProduct(normalToShape,light_dir);

if (angleBetweenNormalAndLight < 0)
{
if (bidirectionalLighting)
{
angleBetweenNormalAndLight = fabs(angleBetweenNormalAndLight);
}
else
{
angleBetweenNormalAndLight = 0;
}
}

if (in_shadow(intersectLoc)) //use just ambient light
{
//cout << "in shadow =)" << endl;
//cout << "intersectLoc = " << intersectLoc.x << " " << intersectLoc.y << " " << intersectLoc.z << endl;
angleBetweenNormalAndLight = 0;
}

double colorscalar = lighting_mix + (1 - lighting_mix)*angleBetweenNormalAndLight;

unsigned int mask = 0x00FFFFFF;
unsigned int redChannel = color & mask;
redChannel = redChannel >> 16;

mask = 0x0000FF00;
unsigned int greenChannel = color & mask;

greenChannel = greenChannel >> 8;

mask = 0x000000FF;
unsigned int blueChannel = color & mask;
//cout << "blue channel " << blueChannel << endl;
double nRed = colorscalar*((double)redChannel);
double nGreen = colorscalar*((double)greenChannel);
double nBlue = colorscalar*((double)blueChannel);

redChannel = (unsigned int) nRed;
greenChannel = (unsigned int) nGreen;
blueChannel = (unsigned int) nBlue;

redChannel = redChannel << 16;
greenChannel = greenChannel << 8;

unsigned int colorToAssign = redChannel + greenChannel + blueChannel;
((unsigned int *) screen->pixels)[y*S_WIDTH+x]=colorToAssign;
}
else //color it the background color
{
//cout << " !!!! didnt hit" << endl;
((unsigned int *) screen->pixels)[y*S_WIDTH+x]=backgroundcolor;
}
}
}
}

// Entry point
int main(int argc, char *argv[])
{

vector3 v1(1,2,3);
vector3 v2(3,2,1);
vector3 v3 = vectorMinus(v1,v2);
srand(static_cast<unsigned>(time(0)));
mat3h mat1;
mat3h mat2;
mat1.identity();
mat2.identity();
mat3h mat3 = mat3hMult(mat1,mat2);
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
cout << mat3.matrix[i][j] << " ";
}
cout << endl;
}
vector3 haha = matMult(mat3, vector3(1,2,3));
cout << "test = " << haha.x << " " << haha.y << " " << haha.z << endl;


// test this shit
vector3 c(0,0,20);
vector3 b(100,0,20);
vector3 a(50,100,0);

vector3 c1(0,100,20);
vector3 b1(100,100,20);
vector3 a1(50,0,0);


vector3 output = vectorCross(a,b);
//cout << "output is: " << output.x << " " << output.y << " " << output.z << endl;

triangle crap(c,b,a,0xffffff);

triangle crapass(c1,b1,a1,0xffff00);
cout << "area = " << crapass.signedAreaXY() << endl;
double alpha;
double beta;
double gamma;
vector3 v(50,50,0);
crapass.baryXY(v, alpha, beta, gamma);
cout << "printing bary coords: " << endl;
cout << "a = " << alpha << " b = " << beta << " y = " << gamma << endl;



// Initialize SDL's subsystems - in this case, only video.
if ( SDL_Init(SDL_INIT_VIDEO) < 0 )
{
fprintf(stderr, "Unable to init SDL: %s\n", SDL_GetError());
exit(1);
}

// Register SDL_Quit to be called at exit; makes sure things are
// cleaned up when we quit.
atexit(SDL_Quit);

// Attempt to create a 640x480 window with 32bit pixels.
screen = SDL_SetVideoMode(640, 480, 32, SDL_SWSURFACE);

// If we fail, return error.
if ( screen == NULL )
{
fprintf(stderr, "Unable to set 640x480 video: %s\n", SDL_GetError());
exit(1);
}



vector3 cubeLocation(0,0,50);



// define icosahedron
vector3 figurepoints[12];
figurepoints[0] = vector3(-0.692,0,0.427);
figurepoints[1] = vector3(0.0,0.427,-0.692);
figurepoints[2] = vector3(0.0,0.427,0.692);
figurepoints[3] = vector3(0.692,0.0,-0.427);
figurepoints[4] = vector3(-0.427,-0.692,0.0);
figurepoints[5] = vector3(-0.427,0.692,0.0);
figurepoints[6] = vector3(0.0,-0.427,0.692);
figurepoints[7] = vector3(0.427,0.692,0.0);
figurepoints[8] = vector3(0.0,-0.427,-0.692);
figurepoints[9] = vector3(0.692,0.0,0.427);
figurepoints[10] = vector3(0.427,-0.692,0.0);
figurepoints[11] = vector3(-0.692,0.0,-0.427);
double scaleFactor = 20;
for (int i = 0 ; i < 12; i++)
{
figurepoints[i].x = figurepoints[i].x * scaleFactor;
figurepoints[i].y = figurepoints[i].y * scaleFactor;
figurepoints[i].z = figurepoints[i].z * scaleFactor;
}

unsigned int tempcolor = 0x8a4b2c;
scene.push_back(triangle(figurepoints[9],figurepoints[2],figurepoints[6],tempcolor));
scene.push_back(triangle(figurepoints[1],figurepoints[5],figurepoints[11],tempcolor));
scene.push_back(triangle(figurepoints[11],figurepoints[1],figurepoints[8],tempcolor));
scene.push_back(triangle(figurepoints[0],figurepoints[11],figurepoints[4],tempcolor));
scene.push_back(triangle(figurepoints[3],figurepoints[7],figurepoints[1],tempcolor));
scene.push_back(triangle(figurepoints[3],figurepoints[1],figurepoints[8],tempcolor));
scene.push_back(triangle(figurepoints[9],figurepoints[3],figurepoints[7],tempcolor));
scene.push_back(triangle(figurepoints[0],figurepoints[2],figurepoints[6],tempcolor));
scene.push_back(triangle(figurepoints[4],figurepoints[6],figurepoints[10],tempcolor));
scene.push_back(triangle(figurepoints[1],figurepoints[7],figurepoints[5],tempcolor));
scene.push_back(triangle(figurepoints[7],figurepoints[2],figurepoints[5],tempcolor));
scene.push_back(triangle(figurepoints[8],figurepoints[10],figurepoints[3],tempcolor));

scene.push_back(triangle(figurepoints[4],figurepoints[11],figurepoints[8],tempcolor));
scene.push_back(triangle(figurepoints[9],figurepoints[2],figurepoints[7],tempcolor));
scene.push_back(triangle(figurepoints[10],figurepoints[6],figurepoints[9],tempcolor));
scene.push_back(triangle(figurepoints[0],figurepoints[11],figurepoints[5],tempcolor));
scene.push_back(triangle(figurepoints[0],figurepoints[2],figurepoints[5],tempcolor));
scene.push_back(triangle(figurepoints[8],figurepoints[10],figurepoints[4],tempcolor));
scene.push_back(triangle(figurepoints[3],figurepoints[9],figurepoints[10],tempcolor));
scene.push_back(triangle(figurepoints[6],figurepoints[4],figurepoints[0],tempcolor));

//get normals to point in right direction
for (int i = 0; i < scene.size(); i++)
{
vector3 fromOriginToTriangle = scene[i].v1;
fromOriginToTriangle.makeUnitVector();
vector3 normal = scene[i].getNormalVector();
if (scalarProduct(normal,fromOriginToTriangle) < 0)
{
//flip two verticies;
vector3 temp = scene[i].v1;
scene[i].v1 = scene[i].v2;
scene[i].v2 = temp;
}
}

// add spheres
scene_sphere.push_back(sphere(0,0,25,5,0x8aafded));


// move objects to center of screen
mat3h moveToCenter;
mat3h moveToOrigin;
moveToCenter.identity();
moveToCenter.matrix[0][3] = cubeLocation.x;
moveToCenter.matrix[1][3] = cubeLocation.y;
moveToCenter.matrix[2][3] = cubeLocation.z;
for (int i = 0; i < scene.size(); i++)
{
//move cube out to screen
scene[i].v1 = matMult(moveToCenter,scene[i].v1);
scene[i].v2 = matMult(moveToCenter,scene[i].v2);
scene[i].v3 = matMult(moveToCenter,scene[i].v3);
}

// add bottom plane
triangle bottom1 = triangle(vector3(-INT_MAX,30,-INT_MAX),vector3(-INT_MAX,30,INT_MAX),vector3(INT_MAX,30,-INT_MAX),0x105C1C, true);
bottom1.flipNormal();

triangle bottom2 = triangle(vector3(INT_MAX,30,-INT_MAX),vector3(-INT_MAX,30,INT_MAX),vector3(INT_MAX,30,INT_MAX),0x105C1C,true);
bottom2.flipNormal();


scene.push_back(bottom1);
scene.push_back(bottom2);

vector3 hitcrap(0,30,25);
if (in_shadow(hitcrap))
{
cout << "hehe hit" << endl;
}



double xMaxIncrement = .01;
double yMaxIncrement = .05;
double zMaxIncrement = .05;


ray_trace();
while (1)
{
/* //paint screen black
for (int i = 0; i < S_WIDTH; i++)
{
for (int j = 0; j < S_HEIGHT; j++)
{
((unsigned int *) screen->pixels)[j*S_WIDTH+i]=0;
}
}
//initialize zbuffer
for (int i = 0; i < 640; i++)
{
for (int j = 0; j < 480; j++)
{
zbuffer[i][j] = INT_MAX;
}
}

mat3h rotateX;
mat3h rotateY;
mat3h rotateZ;
rotateX.identity();
rotateY.identity();
rotateZ.identity();
if (tumblingEnabled)
{
// update rotations
double xIncrement = ((double)rand()/RAND_MAX)*xMaxIncrement;
double yIncrement = ((double)rand()/RAND_MAX)*yMaxIncrement;
double zIncrement = ((double)rand()/RAND_MAX)*zMaxIncrement;
// get rotation matricies
rotateX = rot3hX(xIncrement);
rotateY = rot3hY(yIncrement);
rotateZ = rot3hZ(zIncrement);
}

double xMaxLightIncrement = 0;
double yMaxLightIncrement = 0;
double zMaxLightIncrement = 0;
// update rotations
double xlIncrement = ((double)rand()/RAND_MAX)*xMaxLightIncrement;
double ylIncrement = ((double)rand()/RAND_MAX)*yMaxLightIncrement;
double zlIncrement = ((double)rand()/RAND_MAX)*zMaxLightIncrement;


mat3h rotateLightX = rot3hX(xlIncrement);
mat3h rotateLightY = rot3hY(ylIncrement);
mat3h rotateLightZ = rot3hZ(zlIncrement);


if (revolvingLight)
{
light_dir = matMult(rotateLightX, light_dir);
light_dir = matMult(rotateLightY, light_dir);
light_dir = matMult(rotateLightZ, light_dir);
}

// rotate, transpose, and rasterize
for (int i = 0; i < scene.size(); i++)
{
//create bring to origin matrix
moveToOrigin.identity();
moveToOrigin.matrix[0][3] = -1*cubeLocation.x;
moveToOrigin.matrix[1][3] = -1*cubeLocation.y;
moveToOrigin.matrix[2][3] = -1*cubeLocation.z;

//bring to origin
scene[i].v1 = matMult(moveToOrigin,scene[i].v1);
scene[i].v2 = matMult(moveToOrigin,scene[i].v2);
scene[i].v3 = matMult(moveToOrigin,scene[i].v3);

//rotate x
scene[i].v1 = matMult(rotateX,scene[i].v1);
scene[i].v2 = matMult(rotateX,scene[i].v2);
scene[i].v3 = matMult(rotateX,scene[i].v3);

// rotate y
scene[i].v1 = matMult(rotateY,scene[i].v1);
scene[i].v2 = matMult(rotateY,scene[i].v2);
scene[i].v3 = matMult(rotateY,scene[i].v3);

// rotate z
scene[i].v1 = matMult(rotateZ,scene[i].v1);
scene[i].v2 = matMult(rotateZ,scene[i].v2);
scene[i].v3 = matMult(rotateZ,scene[i].v3);

// create move to center matrix
moveToCenter.identity();
moveToCenter.matrix[0][3] = cubeLocation.x;
moveToCenter.matrix[1][3] = cubeLocation.y;
moveToCenter.matrix[2][3] = cubeLocation.z;

//move cube out to screen
scene[i].v1 = matMult(moveToCenter,scene[i].v1);
scene[i].v2 = matMult(moveToCenter,scene[i].v2);
scene[i].v3 = matMult(moveToCenter,scene[i].v3);


if (!rayTracingEnabled)
{
scene[i].rasterize();
}

}

// Render shit

if (rayTracingEnabled)
{
ray_trace();
}*/
render();

//set lighting if revolvingLight is on



//temp fix
//xIncrement = 0;
//yIncrement = 0;
//zIncrement = 0;


// Poll for events, and handle the ones we care about.

SDL_Event event;
while (SDL_PollEvent(&event))
{
switch (event.type) {

case SDL_KEYUP:
// determine which key is released
switch (event.key.keysym.sym) {
// If escape is pressed, quit
case SDLK_ESCAPE:
exit(0);
break;
case SDLK_BACKQUOTE:
lighting_mix = .0;
break;
case SDLK_1:
lighting_mix = .1;
break;
case SDLK_2:
lighting_mix = .2;
break;
case SDLK_3:
lighting_mix = .3;
break;
case SDLK_4:
lighting_mix = .4;
break;
case SDLK_5:
lighting_mix = .5;
break;
case SDLK_6:
lighting_mix = .6;
break;
case SDLK_7:
lighting_mix = .7;
break;
case SDLK_8:
lighting_mix = .8;
break;
case SDLK_9:
lighting_mix = .9;
break;
case SDLK_0:
lighting_mix = 1.0;
break;
case SDLK_RETURN:
// toggle between the figure rotating and the light revolving
// (extra credit)
revolvingLight = !revolvingLight;
break;
case SDLK_TAB:
// toggle between bidirectional and unidirectional lighting
bidirectionalLighting = !bidirectionalLighting;
break;
case SDLK_SPACE:
// toggle tumbling
tumblingEnabled = !tumblingEnabled;
break;
}
break;
case SDL_QUIT:
exit(0);
}
}

/* while (SDL_PollEvent(&event))
{

switch (event.type)
{
case SDL_KEYDOWN:
break;
case SDL_KEYUP:
// If escape is pressed, return (and thus, quit)
if (event.key.keysym.sym == SDLK_ESCAPE)
return 0;
break;
case SDL_QUIT:
return(0);
}
}*/
}
return 0;
}

Efficient Circular Buffer in Java

Overwriting Circular buffers are great data structures to use if you would like to operate on a recent window of data. Elements are added and removed FIFO like a Queue, except additions on full buffers will cause the oldest (head of the queue) element to be removed. A concrete example of using such a structure is maintaining a frame rate count for recently generated frames in a multimedia application. For example, you could specify a buffer size of 100, and then after each frame generation insert a timestamp into the queue. Once the queue is full, subsequent additions will cause the oldest frame's timestamp to be removed. At any time you can calculate the average frame rate for up to the last 100 frames as (# elements in buffer) / ((newest timestamp) - ( oldest timestamp))

Here is the source code, feel free to use it and do whatever you'd like with it.

 import java.util.NoSuchElementException;  
/**
* Thread safe fixed size circular buffer implementation. Backed by an array.
*
* @author brad
*/
public class ArrayCircularBuffer<T> {
// internal data storage
private T[] data;
// indices for inserting and removing from queue
private int front = 0;
private int insertLocation = 0;
// number of elements in queue
private int size = 0;
/**
* Creates a circular buffer with the specified size.
*
* @param bufferSize
* - the maximum size of the buffer
*/
public ArrayCircularBuffer(int bufferSize) {
data = (T[]) new Object[bufferSize];
}
/**
* Inserts an item at the end of the queue. If the queue is full, the oldest
* value will be removed and head of the queue will become the second oldest
* value.
*
* @param item
* - the item to be inserted
*/
public synchronized void insert(T item) {
data[insertLocation] = item;
insertLocation = (insertLocation + 1) % data.length;
/**
* If the queue is full, this means we just overwrote the front of the
* queue. So increment the front location.
*/
if (size == data.length) {
front = (front + 1) % data.length;
} else {
size++;
}
}
/**
* Returns the number of elements in the buffer
*
* @return int - the number of elements inside this buffer
*/
public synchronized int size() {
return size;
}
/**
* Returns the head element of the queue.
*
* @return T
*/
public synchronized T removeFront() {
if (size == 0) {
throw new NoSuchElementException();
}
T retValue = data[front];
front = (front + 1) % data.length;
size--;
return retValue;
}
/**
* Returns the head of the queue but does not remove it.
*
* @return
*/
public synchronized T peekFront() {
if (size == 0) {
return null;
} else {
return data[front];
}
}
/**
* Returns the last element of the queue but does not remove it.
*
* @return T - the most recently added value
*/
public synchronized T peekLast() {
if (size == 0) {
return null;
} else {
int lastElement = insertLocation - 1;
if (lastElement < 0) {
lastElement = data.length - 1;
}
return data[lastElement];
}
}
}

Saturday, November 27, 2010

How to cheese your way into Starcraft 2 Diamond league

I've taken a few months off from playing but I'm thinking about getting back into this game. Here is an old guide I wrote to the SC2 general forums back in September. It appears as if blizzard doesn't allow google to index their forums so, for the sake of newcomers searching for strategies, I'll post it here:


Hi Everyone,

I thought i'd share to the community how I (a mediocre player) cheesed his way into the Diamond league. I have beaten many a diamond league foe and I believe everyone has the ability to hit diamond so long as they practice and stick to tried and true strategies that work.

I'm by no means an RTS god. When I picked up the game I hadn't played an RTS since 2004 and I initially placed in Silver league. I've viewed my own replays and my APM is ~ 50 which is average and a far cry from the pros who have APM 100+. As I worked my way through the leagues I discovered strategies which generally worked against a certain caliber of player and a certain race.

I believe that provided you have a basic understanding of RTS fundamentals and Starcraft 2 you can be Diamond too. As terran here are the strategies that got me to Diamond. I'm sharing with you the gameplan that I used in virtually EVERY matchup.

TERRAN STRATEGIES FOR REACHING DIAMOND

1) TERRAN VS PROTOSS

My basic strategy vs Protoss even to this day (in Diamond) is to simply mass marines and attack at about the 7 minute mark which typically also corresponds to ~60 supply assuming you have 3 SCV on gas and 16 minerals and the rest on marines.
There are many variants of MM but the variant that I prefer is 3 barracks each with a reactor and pumping straight marines. Typically I don't even upgrade my marines. I just push in early with an overwhelming number. Get reactors up ASAP so you can get as many marines as possible for the 7 minute push! It's very important to attack soon and attack before protoss can obtain units that hard counter your marines: high templars, collosus

ACTION PLAN: Use Mass marines vs Protoss and make sure you attack at the ~7 minute mark. Scan their base before to see what they have. This will work wonders in Platinum or below and work reasonably well in diamond as well.

2) TERRAN VS ZERG
In the lower leagues (Bronze, silver, gold) most Zerg don't know how to effectively use or micro banelings. It seems most in these leagues don't go banelings at all and if they do they either don't have enough or micro them extremely poorly.

ACTION PLAN VS LOWER LEAGUE ZERG: Take advantage of the incompetence of lower league Zerg opponents and go MASS marines. Scan their base and check for banelings next. IF they don't have one, then you can safely mass more units in your base until you think you have the advantage. Other than banelings the only units they have which hard counter marines are broodlords or maybe infestors. But both of those units will come much later. You should have the win long before that. Go for mass marines and you will win most of your matchups vs lower league zerg.

ACTION PLAN VS PLATINUM ZERG: Most platinum zerg I find will indeed go banelings. Sometimes you can out macro them and just pump out too many marines for them to handle but it's a toss up. Typically vs Zerg in Platinum I like to push quick with seige tanks supported by marines. I go 3 rax (no reactor or tech lab initially) 13 gas (saturated once done) 1 factory. Try to get the factory out ASAP and get seige tech researched immediately. Once you have 2 tanks you should have a decent quantity of marines fromt the 3 rax. Push in with your 2 tanks and your marines. It usually is too much for them to handle so early. I also find that in platinum zerg start going fast expand. So this build will really hit them hard and punish them for expanding so early.

http://www.youtube.com/watch?v=PVDhrU1I-HA


Interestingly, my preferred TvT strategy was nerfed by Blizzard. A supply depot is now required to build a barracks, ending BBS builds which have existed since SC1... I'm kind of disappointed that they had to resort to such an extreme measure..


Hoped this helped!

Thursday, November 25, 2010