Delaynay delaynay;
void setup(){
size(512, 512, P3D);
smooth();
noLoop();
PImage image = loadImage("lena.jpg");
image(image, 0, 0);
ArrayList<Point> points = new ArrayList<Point>();
color[][] imagePixels = new color[width][height];
loadPixels();
for(int x = 0; x < width; x += 1){
for(int y = 0; y < height; y += 1){
color c = pixels[y * width + x];
imagePixels[x][y] = c;
float gray = 0.3 * red(c) + 0.59 * green(c) + 0.11 * blue(c);
float p = ((255.0 - gray) / 255.0) * 0.03;
if(random(1) < p){
points.add(new Point(x + map(random(1), 0, 1, 0.0, 0.1), y + map(random(1), 0, 1, 0.0, 0.1)));
}
}
}
delaynay = new Delaynay(points);
background(64);
translate(0, 0, -150);
lights();
noStroke();
for(Triangle triangle: delaynay.triangles){
Point p1 = triangle.points[0];
Point p2 = triangle.points[1];
Point p3 = triangle.points[2];
if(!delaynay.outerPoints.contains(p1) && !delaynay.outerPoints.contains(p2) && !delaynay.outerPoints.contains(p3)){
float red = (red(imagePixels[floor(p1.x)][floor(p1.y)]) +
red(imagePixels[floor(p2.x)][floor(p2.y)]) +
red(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;
float green = (green(imagePixels[floor(p1.x)][floor(p1.y)]) +
green(imagePixels[floor(p2.x)][floor(p2.y)]) +
green(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;
float blue = (blue(imagePixels[floor(p1.x)][floor(p1.y)]) +
blue(imagePixels[floor(p2.x)][floor(p2.y)]) +
blue(imagePixels[floor(p3.x)][floor(p3.y)])) / 3.0;
float p1z = (max(red(imagePixels[floor(p1.x)][floor(p1.y)]),
green(imagePixels[floor(p1.x)][floor(p1.y)]),
blue(imagePixels[floor(p1.x)][floor(p1.y)])) / 255) * 200;
float p2z = (max(red(imagePixels[floor(p2.x)][floor(p2.y)]),
green(imagePixels[floor(p2.x)][floor(p2.y)]),
blue(imagePixels[floor(p2.x)][floor(p2.y)])) / 255) * 200;
float p3z = (max(red(imagePixels[floor(p3.x)][floor(p3.y)]),
green(imagePixels[floor(p3.x)][floor(p3.y)]),
blue(imagePixels[floor(p3.x)][floor(p3.y)])) / 255) * 200;
fill(red, green, blue);
beginShape();
vertex(p1.x, p1.y, p1z);
vertex(p2.x, p2.y, p2z);
vertex(p3.x, p3.y, p3z);
endShape(CLOSE);
}
}
}
class Delaynay {
ArrayList<Point> points;
ArrayList<Point> outerPoints;
ArrayList<Triangle> triangles;
Delaynay(ArrayList<Point> _points){
points = new ArrayList<Point>();
outerPoints = new ArrayList<Point>();
triangles = new ArrayList<Triangle>();
Point op1 = new Point(width / 2 - 100000, -1000);
Point op2 = new Point(width / 2 + 100000, -1000);
Point op3 = new Point(width / 2, height / 2 + 100000);
outerPoints.add(op1);
outerPoints.add(op2);
outerPoints.add(op3);
points.add(op1);
points.add(op2);
points.add(op3);
Triangle outerTriangle = new Triangle(op1, op2, op3);
triangles.add(outerTriangle);
ArrayList<Point> shuffledPoints = new ArrayList<Point>();
for(int i = 0; i < _points.size(); i++){
Point p = _points.get(i);
shuffledPoints.add((int)random(shuffledPoints.size() + 1) ,p);
}
for(Point p: shuffledPoints){
add(p);
}
}
void add(Point p){
for(Point point: points){
if(point.x == p.x && point.y == p.y){
return;
}
}
points.add(p);
Triangle dividedTriangle = null;
for(Triangle triangle: triangles){
if(triangle.contains(p)){
dividedTriangle = triangle;
}
}
triangles.remove(dividedTriangle);
ArrayList<Triangle> leagalizedTQueue = new ArrayList<Triangle>();
ArrayList<Side> leagalizedSQueue = new ArrayList<Side>();
leagalizedTQueue.add(new Triangle(dividedTriangle.points[0], dividedTriangle.points[1], p));
leagalizedTQueue.add(new Triangle(dividedTriangle.points[0], dividedTriangle.points[2], p));
leagalizedTQueue.add(new Triangle(dividedTriangle.points[1], dividedTriangle.points[2], p));
leagalizedSQueue.add(new Side(dividedTriangle.points[0], dividedTriangle.points[1]));
leagalizedSQueue.add(new Side(dividedTriangle.points[0], dividedTriangle.points[2]));
leagalizedSQueue.add(new Side(dividedTriangle.points[1], dividedTriangle.points[2]));
while(!leagalizedTQueue.isEmpty()){
Triangle leagalizedT = leagalizedTQueue.remove(0);
Side leagalizedS = leagalizedSQueue.remove(0);
Triangle triangle = getTriangleWith(leagalizedS);
if(triangle == null){
triangles.add(leagalizedT);
} else {
Point point = triangle.getPointNotOn(leagalizedS);
if(leagalizedT.circumcircle.contains(point)){
triangles.remove(triangle);
leagalizedTQueue.add(new Triangle(p, point, leagalizedS.points[0]));
leagalizedSQueue.add(new Side(point, leagalizedS.points[0]));
leagalizedTQueue.add(new Triangle(p, point, leagalizedS.points[1]));
leagalizedSQueue.add(new Side(point, leagalizedS.points[1]));
} else {
triangles.add(leagalizedT);
}
}
}
}
Triangle getTriangleWith(Side side){
for(Triangle triangle: triangles){
if(triangle.has(side)){
return triangle;
}
}
return null;
}
void display(){
for(Triangle triangle: triangles){
Point p1 = triangle.points[0];
Point p2 = triangle.points[1];
Point p3 = triangle.points[2];
if(!outerPoints.contains(p1) && !outerPoints.contains(p2) && !outerPoints.contains(p3)){
triangle.display();
}
}
}
}
static class Point extends PVector {
Point(float x, float y){
super(x, y);
}
}
class Side {
Point[] points;
Side(Point p1, Point p2){
points = new Point[2];
points[0] = p1;
points[1] = p2;
}
}
class Triangle {
Point[] points;
Circumcircle circumcircle;
Triangle(Point p1, Point p2, Point p3){
points = new Point[3];
points[0] = p1;
points[1] = p2;
points[2] = p3;
circumcircle = new Circumcircle(this);
}
boolean contains(Point p){
float c1 = (points[2].x - points[1].x) * (p.y - points[1].y) - (points[2].y - points[1].y) * (p.x - points[1].x);
float c2 = (points[0].x - points[2].x) * (p.y - points[2].y) - (points[0].y - points[2].y) * (p.x - points[2].x);
float c3 = (points[1].x - points[0].x) * (p.y - points[0].y) - (points[1].y - points[0].y) * (p.x - points[0].x);
return (c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0);
}
Point getPointNotOn(Side side){
for(Point p: points){
if(p != side.points[0] && p != side.points[1]){
return p;
}
}
return null;
}
boolean has(Side side){
return has(side.points[0]) && has(side.points[1]);
}
boolean has(Point point){
for(Point p: points){
if(point == p){
return true;
}
}
return false;
}
void display(){
triangle(points[0].x, points[0].y, points[1].x, points[1].y, points[2].x, points[2].y);
}
}
class Circumcircle{
PVector center;
float radious;
Circumcircle(Triangle triangle){
Point p1 = triangle.points[0];
Point p2 = triangle.points[1];
Point p3 = triangle.points[2];
float c = 2.0 * ((p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x));
float x = ((p3.y - p1.y) * (sq(p2.x) - sq(p1.x) + sq(p2.y) - sq(p1.y)) +
(p1.y - p2.y) * (sq(p3.x) - sq(p1.x) + sq(p3.y) - sq(p1.y))) / c;
float y = ((p1.x - p3.x) * (sq(p2.x) - sq(p1.x) + sq(p2.y) - sq(p1.y)) +
(p2.x - p1.x) * (sq(p3.x) - sq(p1.x) + sq(p3.y) - sq(p1.y))) / c;
center = new Point(x, y);
radious = p1.dist(center);
}
boolean contains(Point p){
return p.dist(center) < radious;
}
}