Optimized Shadows
back
Source
/* @pjs preload="light.png"; */
import java.util.Collections;
import java.util.Comparator;
PImage lightImage;
PImage lightBitmap;
PGraphics buffer;
int NUMBER_OF_WALLS = 4;
Rectangle[] walls;
PVector[] stageCorners;
boolean rayVisible;
// Setup the example
void setup(){
size(640, 480);
imageMode(CENTER);
lightImage = loadImage("light.png");
lightBitmap = createImage(width, height, RGB);
buffer = createGraphics(width, height, JAVA2D);
walls = new Rectangle[NUMBER_OF_WALLS];
for(int i = 0; i < walls.length; i++){
int x = i * width / walls.length + 50;
int y = floor(random(50, height-200));
walls[i] = new Rectangle(x, y, 100, 100);
}
// An array of the stage corners that we'll use later
stageCorners = new PVector[]{ new PVector(0,0), new PVector(width, 0), new PVector(width, height),new PVector(0, height)};
}
// The draw() method is called every frame
void draw(){
background(#4488cc);
final PVector light = new PVector(mouseX, mouseY);
// Ray casting!
// Cast rays through the corners of each wall towards the stage edge.
// Save all of the intersection points or ray end points if there was no intersection.
ArrayList points = new ArrayList();
PVector end = null;
PVector intersect;
int i;
for(Rectangle wall : walls){
// Create a ray from the light through each corner out to the edge of the stage.
// This array defines points just inside of each corner to make sure we hit each one.
// It also defines points just outside of each corner so we can see to the stage edges.
PVector[] corners = new PVector[]{
new PVector(wall.x + 1, wall.y + 1),
new PVector(wall.x - 1, wall.y - 1),
new PVector(wall.x + 1 + wall.width, wall.y + 1),
new PVector(wall.x - 1 + wall.width, wall.y - 1),
new PVector(wall.x + 1 + wall.width, wall.y + 1 + wall.height),
new PVector(wall.x - 1 + wall.width, wall.y - 1 + wall.height),
new PVector(wall.x + 1, wall.y + 1 + wall.height),
new PVector(wall.x - 1, wall.y - 1 + wall.height),
};
// Calculate rays through each point to the edge of the stage
for(i = 0; i < corners.length; i++){
PVector c = corners[i];
// Here comes the linear algebra.
// The equation for a line is y = slope * x + b
// b is where the line crosses the left edge of the stage
float slope = (c.y - light.y) / (c.x - light.x);
float b = light.y - slope * light.x;
if(c.x == light.x){
// Vertical lines are a special case
if(c.y <= light.y){
end = new PVector(light.x, 0);
}else{
end = new PVector(light.x, height);
}
}else if(c.y == light.y){
// Horizontal lines are a special case
if(c.x <= light.x){
end = new PVector(0, light.y);
}else{
end = new PVector(width, light.y);
}
}else{
// Find the point where the line crosses the stage edge
PVector left = new PVector(0, b);
PVector right = new PVector(width, slope * width + b);
PVector top = new PVector(-b/slope, 0);
PVector bottom = new PVector((height-b)/slope, height);
// Get the actual intersection point
if(c.y <= light.y && c.x >= light.x){
if(top.x >= 0 && top.x <= width){
end = top;
}else{
end = right;
}
}else if(c.y <= light.y && c.x <= light.x){
if(top.x >= 0 && top.x <= width){
end = top;
}else{
end = left;
}
}else if(c.y >= light.y && c.x >= light.x){
if(bottom.x >= 0 && bottom.x <= width){
end = bottom;
}else{
end = right;
}
}else if(c.y >= light.y && c.x <= light.x){
if(bottom.x >= 0 && bottom.x <= width){
end = bottom;
}else{
end = left;
}
}
}
// Check if the ray intersected the wall
intersect = getWallIntersection(light, end);
if(intersect != null){
// This is the front edge of the light blocking object
points.add(intersect);
}else{
// Nothing blocked the ray
points.add(end);
}
}
}
// Shoot rays at each of the stage corners to see if the corner
// of the stage is in shadow. This needs to be done so that
// shadows don't cut the corner.
for(i = 0; i < stageCorners.length; i++){
intersect = getWallIntersection(light, stageCorners[i]);
if(intersect == null){
points.add(stageCorners[i]);
}
}
// Now sort the points clockwise around the light
// Sorting is required so that the points are connected in the right order.
//
// This sorting algorithm was copied from Stack Overflow:
// http://stackoverflow.com/questions/6989100/sort-points-in-clockwise-order
//
// Here's a pseudo-code implementation if you want to code it yourself:
// http://en.wikipedia.org/wiki/Graham_scan
Collections.sort(points, new Comparator(){
public int compare(PVector a, PVector b){
if(a.x - light.x >= 0 && b.x - light.x < 0)
return 1;
if(a.x - light.x < 0 && b.x - light.x >= 0)
return -1;
if(a.x - light.x == 0 && b.x - light.x == 0){
if(a.y - light.y >= 0 || b.y - light.y >= 0)
return 1;
return -1;
}
// Compute the cross product of vectors (center -> a) x (center -> b)
float det = (a.x - light.x) * (b.y - light.y) - (b.x - light.x) * (a.y - light.y);
if(det < 0)
return 1;
if(det > 0)
return -1;
// Points a and b are on the same line from the center
// Check which point is closer to the center
float d1 = (a.x - light.x) * (a.x - light.x) + (a.y - light.y) * (a.y - light.y);
float d2 = (b.x - light.x) * (b.x - light.x) + (b.y - light.y) * (b.y - light.y);
return d1 > d2 ? 1 : 0;
}
});
// Connect the dots and fill in the shape, which are cones of light,
// with a bright white color. When multiplied with the background,
// the white color will allow the full color of the background to
// shine through.
buffer.beginDraw();
buffer.background(100);
buffer.fill(255);
buffer.noStroke();
buffer.beginShape();
for(PVector point : points){
if(point != null)
buffer.vertex(point.x, point.y);
}
buffer.endShape();
buffer.endDraw();
lightBitmap = buffer.get(0, 0, buffer.width, buffer.height);
blend(lightBitmap, 0, 0, width, height, 0, 0, width, height, MULTIPLY);
for(Rectangle wall : walls){
wall.display();
}
image(lightImage, light.x, light.y);
if(rayVisible){
for(PVector point : points){
stroke(255);
line(light.x, light.y, point.x, point.y);
}
}
text((int)frameRate + " FPS", 20, 20);
}
void mousePressed(){
rayVisible = !rayVisible;
}
PVector getWallIntersection(PVector start, PVector end){
float distanceToWall = MAX_FLOAT;
PVector closestIntersection = null;
for(Rectangle wall : walls){
PVector nw, ne, se, sw, intersect;
nw = new PVector(wall.x, wall.y);
ne = new PVector(wall.x + wall.width, wall.y);
sw = new PVector(wall.x, wall.y + wall.height);
se = new PVector(wall.x + wall.width, wall.y + wall.height);
/* top line */
intersect = intersectPLines(start, end, nw, ne);
if(intersect != null){
float distance = dist(start.x, start.y, intersect.x, intersect.y);
if(distance < distanceToWall){
distanceToWall = distance;
closestIntersection = intersect;
}
}
/* left line */
intersect = intersectPLines(start, end, nw, sw);
if(intersect != null){
float distance = dist(start.x, start.y, intersect.x, intersect.y);
if(distance < distanceToWall){
distanceToWall = distance;
closestIntersection = intersect;
}
}
/* right line */
intersect = intersectPLines(start, end, se, ne);
if(intersect != null){
float distance = dist(start.x, start.y, intersect.x, intersect.y);
if(distance < distanceToWall){
distanceToWall = distance;
closestIntersection = intersect;
}
}
/* bottom line */
intersect = intersectPLines(start, end, se, sw);
if(intersect != null){
float distance = dist(start.x, start.y, intersect.x, intersect.y);
if(distance < distanceToWall){
distanceToWall = distance;
closestIntersection = intersect;
}
}
}
return closestIntersection;
}
PVector intersectPLines(PVector v1start, PVector v1end, PVector v2start, PVector v2end){
return intersectLines(v1start.x, v1start.y, v1end.x, v1end.y, v2start.x, v2start.y, v2end.x, v2end.y);
}
/* From: http://processingjs.org/learning/custom/intersect/ */
PVector intersectLines(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4){
float a1, a2, b1, b2, c1, c2;
float r1, r2 , r3, r4;
float denom, offset, num;
PVector ret = null;
// Compute a1, b1, c1, where line joining points 1 and 2
// is "a1 x + b1 y + c1 = 0".
a1 = y2 - y1;
b1 = x1 - x2;
c1 = (x2 * y1) - (x1 * y2);
// Compute r3 and r4.
r3 = ((a1 * x3) + (b1 * y3) + c1);
r4 = ((a1 * x4) + (b1 * y4) + c1);
// Check signs of r3 and r4. If both point 3 and point 4 lie on
// same side of line 1, the line segments do not intersect.
if ((r3 != 0) && (r4 != 0) && same_sign(r3, r4)){
return null;
}
// Compute a2, b2, c2
a2 = y4 - y3;
b2 = x3 - x4;
c2 = (x4 * y3) - (x3 * y4);
// Compute r1 and r2
r1 = (a2 * x1) + (b2 * y1) + c2;
r2 = (a2 * x2) + (b2 * y2) + c2;
// Check signs of r1 and r2. If both point 1 and point 2 lie
// on same side of second line segment, the line segments do
// not intersect.
if ((r1 != 0) && (r2 != 0) && (same_sign(r1, r2))){
return null;
}
//Line segments intersect: compute intersection point.
denom = (a1 * b2) - (a2 * b1);
if (denom == 0) {
return null;
}
if (denom < 0){
offset = -denom / 2;
}
else {
offset = denom / 2 ;
}
// The denom/2 is to get rounding instead of truncating. It
// is added or subtracted to the numerator, depending upon the
// sign of the numerator.
num = (b1 * c2) - (b2 * c1);
ret = new PVector(0,0);
if (num < 0){
ret.x = (num - offset) / denom;
}
else {
ret.x = (num + offset) / denom;
}
num = (a2 * c1) - (a1 * c2);
if (num < 0){
ret.y = ( num - offset) / denom;
}
else {
ret.y = (num + offset) / denom;
}
// lines_intersect
return ret;
}
boolean same_sign(float a, float b){
return (( a * b) >= 0);
}
class Rectangle{
int x;
int y;
int width;
int height;
Rectangle(int x, int y, int width, int height){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
void display(){
noStroke();
rect(x, y, width, height);
}
boolean overlap(int otherX, int otherY, int otherWidth, int otherHeight){
return !(x + width < otherX || x > otherX+otherWidth || y + height < otherY || y > otherY+otherHeight);
}
}