diff --git a/Project/Game/Canny.pde b/Project/Game/Canny.pde index 53f7004..0eae538 100644 --- a/Project/Game/Canny.pde +++ b/Project/Game/Canny.pde @@ -1,230 +1,231 @@ import gab.opencv.*; static enum kernelType { scale, blur, gaussian }; class Canny extends PApplet { static final int imageWidth=960;//800; static final int imageHeight=540;//600; final BlobDetection blobDetection=new BlobDetection(); final QuadGraph quadGraph=new QuadGraph(); final HoughTransform houghTransform=new HoughTransform(); int setupPartSize; int resizeX; int resizeY; OpenCV opencv; TwoDThreeD twoD3D; PImage img0; PImage blobDetectionImg; PImage afterScharr; PImage camImage; List corners; int minHThreshold = 100, maxHThreshold =140; int minSThreshold = 80, maxSThreshold = 255; int minBThreshold = 10, maxBThreshold = 170; Canny(int setupPartSize) { this.setupPartSize = setupPartSize; this.resizeX = setupPartSize-20; this.resizeY = resizeX * imageHeight / imageWidth; opencv = new OpenCV(this, 100, 100); twoD3D=new TwoDThreeD(imageWidth, imageHeight, 0); } PVector update(int minHThreshold , int maxHThreshold, int minSThreshold, int maxSThreshold, int minBThreshold , int maxBThreshold) { this.minHThreshold = minHThreshold; this.maxHThreshold = maxHThreshold; this.minSThreshold = minSThreshold; this.maxSThreshold = maxSThreshold; this.minBThreshold = minBThreshold; this.maxBThreshold = maxBThreshold; if (cam.available() == true) { cam.read(); } camImage = cam.get(); img0 = camImage.copy(); camImage.resize(resizeX, resizeY); int I = 100; img0 = thresholdHSB(img0, minHThreshold, maxHThreshold, minSThreshold, maxSThreshold, minBThreshold, maxBThreshold ); img0 = new BlobDetection().findConnectedComponents(img0, true); blobDetectionImg =img0.copy(); blobDetectionImg.resize(resizeX, resizeY); img0 = convolute(img0, kernelType.gaussian); img0 = scharr(img0); img0 = threshold(img0, I, false); afterScharr=img0.copy(); afterScharr.resize(resizeX, resizeY); ArrayList lines= houghTransform.hough(img0, 4); - corners= quadGraph.findBestQuad(lines, imageWidth, imageHeight, imageWidth*imageHeight, 0, false); + int maxArea=imageWidth*imageHeight; + corners= quadGraph.findBestQuad(lines, imageWidth, imageHeight, maxArea, (maxArea>>>3), false); for (PVector c : corners) { c.set(c.x, c.y, 1); } PVector rotation=twoD3D.get3DRotations(corners); rotation.set((rotation.x)/PI*180, (rotation.y)/PI*180, (rotation.z)/PI*180); return rotation; } //if inverted = false take values for 0 to threshol PImage threshold(PImage img, int threshold, boolean inverted) { PImage result = createImage(img.width, img.height, RGB); for (int i = 0; i < img.width * img.height; i++) { result.pixels[i]=brightness(img.pixels[i])>threshold^inverted?color(255):color(0); } return result; } PImage thresholdHSB(PImage img, int minH, int maxH, int minS, int maxS, int minB, int maxB) { PImage result = createImage(img.width, img.height, RGB); for (int i = 0; i < img.width * img.height; i++) { if (hue(img.pixels[i]) max )? value : max; buffer[x+y*img.width] = value; } } // ************************************* for (int y = 1; y < img.height - 1; y++) { // Skip top and bottom edges for (int x = 1; x < img.width - 1; x++) { // Skip left and right int val=(int) ((buffer[y * img.width + x] / max)*255); result.pixels[y * img.width + x]=color(val); } } return result; } PImage convolute(PImage img, kernelType kt) { int N = 3; //kernel size float[][] kernel; float normFactor ; if (kt == kernelType.scale ) { float[][] kernel1 = {{ 0, 0, 0 }, { 0, 2, 0 }, { 0, 0, 0 }}; kernel = kernel1; normFactor = 1f; } else if (kt == kernelType.blur) { float[][] kernel2 = {{ 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 }}; kernel = kernel2; normFactor = 1f; } else { float[][] gaussianKernel = {{ 9, 12, 9 }, { 12, 15, 12 }, { 9, 12, 9 }}; kernel = gaussianKernel; normFactor = 0f; for (int i = 0; i< N; ++i) { for (int j = 0; j getCorners(){ List out = new ArrayList(); - float coef = 1.25; + float coef = 1;//disable coef by putting 1 for (PVector c : corners) { out.add(new PVector(c.x/((float)(imageWidth))*resizeX*coef,c.y/((float)(imageHeight))*resizeY*coef,1)); } return out; } } diff --git a/Project/Game/Game.pde b/Project/Game/Game.pde index 6bfa464..b125fc3 100644 --- a/Project/Game/Game.pde +++ b/Project/Game/Game.pde @@ -1,455 +1,473 @@ import java.text.DecimalFormat; import processing.video.*; Mover mover; //The ball Cylinder cyl; //The basis of all cylinders HScrollbar hs; HScrollbar minH, maxH, minS, maxS, minB, maxB; //Capture cam; Movie cam; Canny canny; PImage img; PShape globe; PShape robot; //The vilain float depth = 2000; //the depth from the box boolean GameOver=false; //Score and histo ArrayList scores; float score; float scoreMalus = -1; int scoreTimer = 0; int prVeloFreq = 20; //The frequency at which the velocity is printed float lastScore; float veloMag; float scoreFactor = 0.5; //lastScore = scoreFactor * lastVelocity; float VilainScoreMultiplier=10;//bonus score given when killing the vilain boolean win = false; int minHistowidth = 1, maxHistowidth = 20, histowidth; float maxScore = 10, minScore=-10; float drawingFactor; // = histoHeight /(maxScore -minScore); int barChartWidth, barChartHeight, bcCubeHeight = 5; boolean mousePermittedToMove=true; //Plate size float plate_w=1000; float plate_t=plate_w/20; float x_coord, y_coord; float mX, mY; //mouse X position float xOnPlane, yOnPlane; //coordinate on 2D on the box PVector oldAngles, newAngles; float rz, rx; //rotate x and rotate z float cameraHeight; float speed=10; float radius=plate_t*4/5; DecimalFormat f = new DecimalFormat("#0.00"); DecimalFormat f2 = new DecimalFormat("#0"); DecimalFormat f3 = new DecimalFormat(""); boolean shiftMod=false; ParticleWin partW; ParticleSystem partSys=null; long previousFrame=0; float timeIntervalParticle=0.5;//seconds int margin = 15; //marge between surface int botPartHeight = 300; int setupWidth = 350; PGraphics setupPart; int topViewMargin=20; int topViewWidth = botPartHeight-2*topViewMargin; PGraphics gameSurface; PGraphics statSurface; PGraphics topView; PGraphics scoreboard; PGraphics barChart; -int farAwayCounter = 0; -int tooMuchTimeAway = 3; +int farAwayCounter = 0;//useless now +int tooMuchTimeAway = 0;//desactivated int OneTimeOutOfFour=-1; PVector NULL_VECTOR=new PVector(0, 0, 0); PVector prevAnglesOfPlate=NULL_VECTOR; PVector anglesOfPlate=null; //SetupPart int scrollMargin = 20; int scrollHeight = 10; int scrollWidth = setupWidth-2*scrollMargin; int scrollTextMargin = 16; int minHId = 80, maxHId =130; - int minSId = 20, maxSId = 242; - int minBId = 60, maxBId = 220; +int minSId = 20, maxSId = 242; +int minBId = 60, maxBId = 220; int minHpos, maxHpos, minSpos, maxSpos, minBpos, maxBpos; void settings() { size(displayWidth, displayHeight-60, P3D); fullScreen(); x_coord=width/2; y_coord=height/2; } void setup() { mover = new Mover(); partW=new ParticleWin(mover); cyl=new Cylinder(); scores = new ArrayList(); oldAngles = new PVector(0, 0, 0); newAngles = new PVector(0, 0, 0); - hs = new HScrollbar(750, height -50, 450, 20,0.5); + hs = new HScrollbar(750, height -50, 450, 20, 0.5); minH = new HScrollbar(width-setupWidth+scrollMargin/2, height - 7 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(minHId))/255); maxH = new HScrollbar(width-setupWidth+scrollMargin/2, height - 6 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(maxHId))/255); minS = new HScrollbar(width-setupWidth+scrollMargin/2, height - 5 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(minSId))/255); maxS = new HScrollbar(width-setupWidth+scrollMargin/2, height - 4 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(maxSId))/255); minB = new HScrollbar(width-setupWidth+scrollMargin/2, height - 3 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(minBId))/255); maxB = new HScrollbar(width-setupWidth+scrollMargin/2, height - 2 * (scrollHeight+scrollMargin/2), scrollWidth, scrollHeight, ((float)(maxBId))/255); img = loadImage("earth.jpg"); globe = createShape(SPHERE, radius); globe.setStroke(false); globe.setTexture(img); img = loadImage("robotnik.png"); robot = loadShape("robotnik.obj"); robot.setTexture(img); gameSurface=createGraphics(width-setupWidth, height-botPartHeight, P3D); setupPart = createGraphics(setupWidth, height, P2D); topView=createGraphics(topViewWidth+2*topViewMargin, topViewWidth+2*topViewMargin, P2D); statSurface=createGraphics(3*botPartHeight, botPartHeight/3, P2D); scoreboard = createGraphics(botPartHeight-2*margin, botPartHeight-2*margin, P2D); barChartWidth = width - (botPartHeight+margin) *2 -setupWidth; barChartHeight = botPartHeight-2*margin-50; barChart = createGraphics(barChartWidth, barChartHeight, P2D); //init camera /*String[] cameras = Capture.list(); - if (cameras.length == 0) { - println("There are no cameras available for capture."); - exit(); - } else { - println("Available cameras:"); - for (int i = 0; i < cameras.length; i++) { - //println(cameras[i]); - } - //If you're using gstreamer0.1 (Ubuntu 16.04 and earlier), - //select your predefined resolution from the list: - //cam = new Capture(this, cameras[21]); - //If you're using gstreamer1.0 (Ubuntu 16.10 and later), - //select your resolution manually instead: - cam = new Capture(this, 640, 480, cameras[0]); - cam.start(); - }*/ + if (cameras.length == 0) { + println("There are no cameras available for capture."); + exit(); + } else { + println("Available cameras:"); + for (int i = 0; i < cameras.length; i++) { + //println(cameras[i]); + } + //If you're using gstreamer0.1 (Ubuntu 16.04 and earlier), + //select your predefined resolution from the list: + //cam = new Capture(this, cameras[21]); + //If you're using gstreamer1.0 (Ubuntu 16.10 and later), + //select your resolution manually instead: + cam = new Capture(this, 640, 480, cameras[0]); + cam.start(); + }*/ //init camera to take a video in input cam = new Movie(this, "C:/Users/match/Documents/InfoVisuGit/Mine/BA4Project/Project/Game/testvideo.avi"); cam.loop(); - canny = new Canny(setupWidth); String []args = {"Image processing window"}; PApplet.runSketch(args, canny); } void draw() { background(181, 65, 2); drawGame(); image(gameSurface, 0, 0); drawStat(); image(statSurface, 0, 0); drawScoreboard(); image(scoreboard, botPartHeight+2*margin, height-botPartHeight+margin); drawBarChart(); image(barChart, 2*botPartHeight+margin, height-botPartHeight+margin); drawTopView(); image(topView, margin, height-botPartHeight); hs.update(); hs.display(); - + OneTimeOutOfFour++; if ((OneTimeOutOfFour%=4)==0) { - PVector newAngles = canny.update(minHpos, maxHpos, minSpos, maxSpos, minBpos, maxBpos); + newAngles = canny.update(minHpos, maxHpos, minSpos, maxSpos, minBpos, maxBpos); if (newAngles.mag() > 0) { newAngles.set((newAngles.x <0)? newAngles.x+180 : newAngles.x -180, newAngles.y, 0);//-179 = 1 ; 179 = -1 +-180 = 0 - float dist = PVector.dist(newAngles, oldAngles); - if (dist > 20) { - farAwayCounter++; - } - if ((dist<20 || farAwayCounter > tooMuchTimeAway)) { - oldAngles = newAngles.copy(); - farAwayCounter =0; - } + /*float dist = PVector.dist(newAngles, oldAngles); + if (dist > 20) { + farAwayCounter++; + } + if ((dist<20 || farAwayCounter > tooMuchTimeAway)) { + oldAngles = newAngles.copy(); + farAwayCounter =0; + }*/ } } + if (newAngles.mag() > 0) { + oldAngles.add(newAngles).mult(0.5); + } + drawSetup(); image(setupPart, width-setupWidth, 0); - - minH.update();minH.display(); - maxH.update();maxH.display(); - minS.update();minS.display(); - maxS.update();maxS.display(); - minB.update();minB.display(); - maxB.update();maxB.display(); + + minH.update(); + minH.display(); + maxH.update(); + maxH.display(); + minS.update(); + minS.display(); + maxS.update(); + maxS.display(); + minB.update(); + minB.display(); + maxB.update(); + maxB.display(); } void drawBarChart() { barChart.beginDraw(); barChart.background(242, 86, 2); barChart.fill(160, 255, 255); histowidth = (int)(hs.getPos()*(maxHistowidth-minHistowidth)+minHistowidth); int maxRect = barChartWidth / histowidth; int start = (scores.size() < maxRect)? 0 : scores.size()-maxRect; for (int i = start; i < scores.size(); ++i) { float zeroInHisto = drawingFactor * (maxScore); float posInHisto = drawingFactor * (-scores.get(i)+maxScore) ; int nbOfCube = (int)(Math.abs( zeroInHisto - posInHisto)/bcCubeHeight); for (int j = 0; j < nbOfCube; ++j) { barChart.rect((i-start)*histowidth, zeroInHisto +(zeroInHisto>posInHisto? -(j+1 ): j)* bcCubeHeight, histowidth, bcCubeHeight); } //float top = (zeroInHistoposInHisto)?zeroInHisto:posInHisto)-top; //barChart.rect((i-start)*histowidth, top, histowidth, bot); } barChart.endDraw(); } void updateScore(float points) { score += points; scores.add(score); minScore = (scoremaxScore)? score : maxScore; drawingFactor = barChartHeight/(maxScore-minScore+2); } void drawSetup() { setupPart.beginDraw(); setupPart.background(242, 86, 2); minHpos = (int)(minH.getPos()*255); maxHpos = (int)(maxH.getPos()*255); minSpos = (int)(minS.getPos()*255); maxSpos = (int)(maxS.getPos()*255); minBpos = (int)(minB.getPos()*255); maxBpos = (int)(maxB.getPos()*255); PImage blobDetection = canny.getBlobDetection(); PImage afterScharr = canny.getAfterScharr(); PImage camImg = canny.getCamImage(); setupPart.fill(0); setupPart.textSize(14); setupPart.text("MinH : "+f3.format(minHpos)+" Ideally its "+f3.format(minHId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+scrollTextMargin); setupPart.text("MaxH : "+f3.format(maxHpos)+" Ideally its "+f3.format(maxHId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+2*scrollTextMargin); setupPart.text("MinS : "+f3.format(minSpos)+" Ideally its "+f3.format(minSId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+3*scrollTextMargin); setupPart.text("MaxS : "+f3.format(maxSpos)+" Ideally its "+f3.format(maxSId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+4*scrollTextMargin); setupPart.text("MinB : "+f3.format(minBpos)+" Ideally its "+f3.format(minBId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+5*scrollTextMargin); setupPart.text("MaxB : "+f3.format(maxBpos)+" Ideally its "+f3.format(maxBId)+"\n", scrollMargin/2, 3*camImg.height+ 4*scrollMargin/2+6*scrollTextMargin); setupPart.image(camImg, scrollMargin/2, scrollMargin/2); - setupPart.image(blobDetection, scrollMargin/2,camImg.height+ 2*scrollMargin/2); + setupPart.image(blobDetection, scrollMargin/2, camImg.height+ 2*scrollMargin/2); setupPart.image(afterScharr, scrollMargin/2, 2*camImg.height+ 3*scrollMargin/2); - + setupPart.pushMatrix(); setupPart.stroke(0); setupPart.fill(0x808080FF); List corners = canny.getCorners(); for (PVector pv : corners) { setupPart.ellipse(scrollMargin/2+pv.x, scrollMargin/2+pv.y, 15, 15); } + setupPart.stroke(255,0,0); + if (!corners.isEmpty()) { + lineBetweenTwoCorners(corners.get(0), corners.get(1)); + lineBetweenTwoCorners(corners.get(1), corners.get(2)); + lineBetweenTwoCorners(corners.get(2), corners.get(3)); + lineBetweenTwoCorners(corners.get(3), corners.get(0)); + } setupPart.popMatrix(); setupPart.endDraw(); } void drawScoreboard() { scoreboard.beginDraw(); scoreboard.background(242, 86, 2); scoreTimer = (scoreTimer%prVeloFreq == prVeloFreq-1) ? 0 : ++scoreTimer; veloMag = (scoreTimer == 0)? mover.velocity.mag():veloMag; scoreboard.fill(0); scoreboard.textSize(25); scoreboard.text("Total Score : \n "+f.format(score), 15, 40); scoreboard.text("Velocity : \n "+f.format(veloMag), 15, 130); scoreboard.text("Last score : \n "+f.format(lastScore), 15, 220); scoreboard.endDraw(); } void drawTopView() { topView.beginDraw(); topView.background(181, 65, 2); topView.fill(255, 230, 0); topView.rect(topViewMargin, topViewMargin, topViewWidth, topViewWidth); topView.fill(255, 255, 255); float topViewCylRad=map(cyl.cylinderBaseSize, 0, plate_w/2, 0, topViewWidth); if (partSys!=null) { for (PVector pv : partSys.cylinders) { float topViewCylX=map(pv.x, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); float topViewCylY=map(pv.y, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); topView.ellipse(topViewCylX, topViewCylY, topViewCylRad, topViewCylRad); } if (partSys.cylinders.contains(partSys.mainCyl)) { topView.fill(255, 0, 0); float topViewCylX=map(partSys.mainCyl.x, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); float topViewCylY=map(partSys.mainCyl.y, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); topView.ellipse(topViewCylX, topViewCylY, topViewCylRad, topViewCylRad); } } topView.fill(0, 0, 0); float topViewBallRad=map(radius, 0, plate_w/2, 0, topViewWidth); float topViewBallX=map(mover.location.x, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); float topViewBallY=map(mover.location.y, -plate_w/2, plate_w/2, topViewMargin, topViewWidth+topViewMargin); topView.ellipse(topViewBallX, topViewBallY, topViewBallRad, topViewBallRad); topView.endDraw(); } void drawStat() { statSurface.beginDraw(); statSurface.background(0, 0, 0, 0); statSurface.fill(160, 255, 200); statSurface.textSize(25); statSurface.text("Rotation X : "+f.format(rx/Math.PI*180)+"° Rotation Z : "+f.format(rz/Math.PI*180)+"° speed: "+f.format(speed/10), 5, 25); statSurface.text("Ball location : ("+f2.format(mover.location.x)+","+f2.format(mover.location.y)+")", 5, 50); statSurface.text("Ball velocity : ("+f2.format(mover.velocity.x)+","+f2.format(mover.velocity.y)+")", 5, 75); statSurface.endDraw(); } void drawGame() { gameSurface.beginDraw(); if (GameOver) { gameSurface.background(50, 65, 200); } else { gameSurface.background(100, 0, 0); } gameSurface.directionalLight(50, 100, 125, 0, 1, 0); gameSurface.ambientLight(102, 102, 102); gameSurface.pointLight(150, 150, 150, 0, -200, 0); if (!shiftMod) { mover.update(); mover.checkEdges(); if (partSys!=null) { GameOver|=mover.checkCylinderCollision(partSys.cylinders, radius, partSys.mainCyl); } //rz = map(x_coord, 0, width, -PI/3, PI/3); //rx = map(y_coord, 0, height, -PI/3, PI/3); float x = Math.max(-60, Math.min(-oldAngles.x, 60)); rx = map(x, -60, 60, -PI/3, PI/3); rz = map(oldAngles.y, -60, 60, -PI/3, PI/3); cameraHeight=400; } else { rz=0; rx=-PI/2; cameraHeight=0; } gameSurface.pushMatrix(); gameSurface.camera(0, -cameraHeight, depth, 0, -100, 0, 0, 1, 1); gameSurface.rotateX(rx); gameSurface.rotateZ(rz); gameSurface.shininess(100); gameSurface.fill(160, 255, 255); gameSurface.box(plate_w, plate_t, plate_w); //particles if (partSys!=null) { if (frameCount-previousFrame>=timeIntervalParticle*frameRate && !shiftMod) { timeIntervalParticle=random(0.2, 1.2); previousFrame=frameCount; partSys.addParticle(); } partSys.run(-(plate_t/2), PI/2); } if (partW!=null && GameOver) { partW.updateNdraw(); } if (shiftMod) { xOnPlane=map(mouseX, gameSurface.screenX(-plate_w/2, 0, 0), gameSurface.screenX(plate_w/2, 0, 0), -plate_w/2, plate_w/2); yOnPlane=map(mouseY, gameSurface.screenY(0, 0, -plate_w/2), gameSurface.screenY(0, 0, plate_w/2), -plate_w/2, plate_w/2); cyl.draw(xOnPlane, yOnPlane, -(plate_t/2), PI/2); } gameSurface.translate(mover.getX(), -(plate_t/2+radius), mover.getY()); gameSurface.fill(255, 100, 100); gameSurface.rotateX(mover.getRotX()); gameSurface.rotateZ(mover.getRotZ()); gameSurface.shape(globe); gameSurface.popMatrix(); //Draw the text gameSurface.pushMatrix(); if (shiftMod) { gameSurface.fill(0); gameSurface.textSize(50); gameSurface.text("[EDIT MOD ON]", 50, 500); } gameSurface.fill(255); gameSurface.popMatrix(); gameSurface.endDraw(); } - +void lineBetweenTwoCorners(PVector a, PVector b) { + setupPart.line(a.x+scrollMargin/2, a.y+scrollMargin/2, b.x+scrollMargin/2, b.y+scrollMargin/2); +} void mouseWheel(MouseEvent event) { float e = event.getCount(); if (e<0) { speed-=speed<=2?0:1; } else { speed+=speed>=15?0:1; } } void mouseDragged() { if (!shiftMod && mousePermittedToMove) { float d=-(mX-mouseX)*speed/10; x_coord=x_coord+d<=0?0:x_coord+d>=width?width:x_coord+d; mX=mouseX; d=(mY-mouseY)*speed/10; y_coord=y_coord+d<=0?0:y_coord+d>=height?height:y_coord+d; mY=mouseY; } } void mousePressed() { if (mouseY>height-botPartHeight) { mousePermittedToMove=false; } else { mousePermittedToMove=true; } mX = mouseX; mY = mouseY; if (shiftMod && -plate_w/2 2*radius || Math.abs(yOnPlane-mover.location.y) > 2*radius)) { partSys=new ParticleSystem(new PVector(xOnPlane, yOnPlane), mover, radius); GameOver=false; } } void keyPressed() { if (keyCode == SHIFT) { shiftMod=true; - }else if(keyCode==RIGHT){ + } else if (keyCode==RIGHT) { cam.play(); - }else if(keyCode==LEFT){ + } else if (keyCode==LEFT) { cam.pause(); } } void keyReleased() { if (keyCode == SHIFT) { shiftMod=false; } } diff --git a/Project/Game/HoughTransform.pde b/Project/Game/HoughTransform.pde index 9c1b579..0a9cf92 100644 --- a/Project/Game/HoughTransform.pde +++ b/Project/Game/HoughTransform.pde @@ -1,156 +1,156 @@ class HoughTransform { float discretizationStepsPhi = 0.06f; float discretizationStepsR = 2.5f; // dimensions of the accumulator int phiDim = (int) (Math.PI / discretizationStepsPhi +1); // pre-compute the sin and cos values float[] tabSin = new float[phiDim]; float[] tabCos = new float[phiDim]; float ang = 0; float inverseR = 1.f / discretizationStepsR; HoughTransform() { for (int accPhi = 0; accPhi < phiDim; ang += discretizationStepsPhi, accPhi++) { // we can also pre-multiply by (1/discretizationStepsR) since we need it in the Hough loop tabSin[accPhi] = (float) (Math.sin(ang) * inverseR); tabCos[accPhi] = (float) (Math.cos(ang) * inverseR); } } void drawLines(ArrayList lines, PImage edgeImg) { for (int idx = 0; idx < lines.size(); idx++) { PVector line=lines.get(idx); float r = line.x; float phi = line.y; // Cartesian equation of a line: y = ax + b // in polar, y = (-cos(phi)/sin(phi))x + (r/sin(phi)) // => y = 0 : x = r / cos(phi) // => x = 0 : y = r / sin(phi) // compute the intersection of this line with the 4 borders of // the image int x0 = 0; int y0 = (int) (r / sin(phi)); int x1 = (int) (r / cos(phi)); int y1 = 0; int x2 = edgeImg.width; int y2 = (int) (-cos(phi) / sin(phi) * x2 + r / sin(phi)); int y3 = edgeImg.width; int x3 = (int) (-(y3 - r / sin(phi)) * (sin(phi) / cos(phi))); // Finally, plot the lines stroke(0, 255, 255); if (y0 > 0) { if (x1 > 0) line(x0, y0, x1, y1); else if (y2 > 0) line(x0, y0, x2, y2); else line(x0, y0, x3, y3); } else { if (x1 > 0) { if (y2 > 0) line(x1, y1, x2, y2); else line(x1, y1, x3, y3); } else line(x2, y2, x3, y3); } } } - int minVotes=50; + int minVotes=20; ArrayList hough(PImage edgeImg, int nLines) { ArrayList bestCandidates=new ArrayList(); //The max radius is the image diagonal, but it can be also negative int rDim = (int) ((sqrt(edgeImg.width*edgeImg.width + edgeImg.height*edgeImg.height) * 2) / discretizationStepsR +1); // our accumulator int[] accumulator = new int[phiDim * rDim]; // Fill the accumulator: on edge points (ie, white pixels of the edge // image), store all possible (r, phi) pairs describing lines going // through the point. for (int y = 0; y < edgeImg.height; y++) { for (int x = 0; x < edgeImg.width; x++) { // Are we on an edge? if (brightness(edgeImg.pixels[y * edgeImg.width + x]) != 0) { // ...determine here all the lines (r, phi) passing through // pixel (x,y), convert (r,phi) to coordinates in the // accumulator, and increment accordingly the accumulator. // Be careful: r may be negative, so you may want to center onto // the accumulator: r += rDim / 2 for (int phi=0; phi minVotes && isMaxOverArea(accumulator, idx, REGION_SIZE, phiDim, rDim)) { bestCandidates.add(idx); } } bestCandidates.sort(new HoughComparator(accumulator)); ArrayList lines=new ArrayList(); for (int i=0; i// } private boolean isMaxOverArea(int[] accumulator, int idx, int REGION_SIZE, int phiDim, int rDim) { int threshold=accumulator[idx]; for (int dx=Math.max(0, idx%rDim-REGION_SIZE); dxthreshold) { return false; } } } return true; } class HoughComparator implements java.util.Comparator { int[] accumulator; public HoughComparator(int[] accumulator) { this.accumulator = accumulator; } @Override public int compare(Integer l1, Integer l2) { if (accumulator[l1] > accumulator[l2] || (accumulator[l1] == accumulator[l2] && l1 < l2)) return -1; return 1; } } } diff --git a/Project/Game/QuadGraph.pde b/Project/Game/QuadGraph.pde index 051132d..b3f87f7 100644 --- a/Project/Game/QuadGraph.pde +++ b/Project/Game/QuadGraph.pde @@ -1,384 +1,384 @@ import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.ArrayList; import java.util.Map; class QuadGraph { boolean verbose=false; List cycles = new ArrayList(); int[][] graph; List findBestQuad(List lines, int width, int height, int max_quad_area, int min_quad_area, boolean verbose) { this.verbose=verbose; - build(lines, width, height); //<>// + build(lines, width, height); findCycles(verbose); ArrayList bestQuad=new ArrayList(); float bestQuadArea=0; for (int [] cy : cycles) { ArrayList quad= new ArrayList(); PVector l1 = lines.get(cy[0]); PVector l2 = lines.get(cy[1]); PVector l3 = lines.get(cy[2]); PVector l4 = lines.get(cy[3]); quad.add(intersection(l1, l2)); quad.add(intersection(l2, l3)); quad.add(intersection(l3, l4)); quad.add(intersection(l4, l1)); quad=sortCorners(quad); PVector c1 = quad.get(0); PVector c2 = quad.get(1); PVector c3 = quad.get(2); PVector c4 = quad.get(3); if (isConvex(c1, c2, c3, c4) && nonFlatQuad(c1, c2, c3, c4)) { float quadArea=validArea(c1, c2, c3, c4, max_quad_area, min_quad_area); if (quadArea>0 && quadArea>bestQuadArea) { bestQuadArea=quadArea; bestQuad=quad; } } } if (bestQuadArea>0) return bestQuad; else return new ArrayList(); } void build(List lines, int width, int height) { int n = lines.size(); // The maximum possible number of edges is n * (n - 1)/2 graph = new int[n * (n - 1)/2][2]; int idx =0; for (int i = 0; i < lines.size(); i++) { for (int j = i + 1; j < lines.size(); j++) { if (intersect(lines.get(i), lines.get(j), width, height)) { graph[idx][0]=i; graph[idx][1]=j; idx++; } } } } /** Returns true if polar lines 1 and 2 intersect * inside an area of size (width, height) */ boolean intersect(PVector line1, PVector line2, int width, int height) { double sin_t1 = Math.sin(line1.y); double sin_t2 = Math.sin(line2.y); double cos_t1 = Math.cos(line1.y); double cos_t2 = Math.cos(line2.y); float r1 = line1.x; float r2 = line2.x; double denom = cos_t2 * sin_t1 - cos_t1 * sin_t2; int x = (int) ((r2 * sin_t1 - r1 * sin_t2) / denom); int y = (int) ((-r2 * cos_t1 + r1 * cos_t2) / denom); if (0 <= x && 0 <= y && width >= x && height >= y) return true; else return false; } PVector intersection(PVector line1, PVector line2) { double sin_t1 = Math.sin(line1.y); double sin_t2 = Math.sin(line2.y); double cos_t1 = Math.cos(line1.y); double cos_t2 = Math.cos(line2.y); float r1 = line1.x; float r2 = line2.x; double denom = cos_t2 * sin_t1 - cos_t1 * sin_t2; int x = (int) ((r2 * sin_t1 - r1 * sin_t2) / denom); int y = (int) ((-r2 * cos_t1 + r1 * cos_t2) / denom); return new PVector(x,y); } void findCycles(boolean verbose) { cycles.clear(); for (int i = 0; i < graph.length; i++) { for (int j = 0; j < graph[i].length; j++) { findNewCycles(new int[] {graph[i][j]}); } } if (verbose) { for (int[] cy : cycles) { String s = "" + cy[0]; for (int i = 1; i < cy.length; i++) { s += "," + cy[i]; } System.out.println(s); } } } void findNewCycles(int[] path) { int n = path[0]; int x; int[] sub = new int[path.length + 1]; for (int i = 0; i < graph.length; i++) for (int y = 0; y <= 1; y++) if (graph[i][y] == n) // edge refers to our current node { x = graph[i][(y + 1) % 2]; if (!visited(x, path)) // neighbor node not on path yet { sub[0] = x; System.arraycopy(path, 0, sub, 1, path.length); // explore extended path findNewCycles(sub); } else if ((path.length == 4) && (x == path[path.length - 1])) // cycle found { int[] p = normalize(path); int[] inv = invert(p); if (isNew(p) && isNew(inv)) { cycles.add(p); } } } } // check of both arrays have same lengths and contents Boolean equals(int[] a, int[] b) { Boolean ret = (a[0] == b[0]) && (a.length == b.length); for (int i = 1; ret && (i < a.length); i++) { if (a[i] != b[i]) { ret = false; } } return ret; } // create a path array with reversed order int[] invert(int[] path) { int[] p = new int[path.length]; for (int i = 0; i < path.length; i++) { p[i] = path[path.length - 1 - i]; } return normalize(p); } // rotate cycle path such that it begins with the smallest node int[] normalize(int[] path) { int[] p = new int[path.length]; int x = smallest(path); int n; System.arraycopy(path, 0, p, 0, path.length); while (p[0] != x) { n = p[0]; System.arraycopy(p, 1, p, 0, p.length - 1); p[p.length - 1] = n; } return p; } // compare path against known cycles // return true, iff path is not a known cycle Boolean isNew(int[] path) { Boolean ret = true; for (int[] p : cycles) { if (equals(p, path)) { ret = false; break; } } return ret; } // return the int of the array which is the smallest int smallest(int[] path) { int min = path[0]; for (int p : path) { if (p < min) { min = p; } } return min; } // check if vertex n is contained in path Boolean visited(int n, int[] path) { Boolean ret = false; for (int p : path) { if (p == n) { ret = true; break; } } return ret; } /** Check if a quad is convex or not. * * Algo: take two adjacent edges and compute their cross-product. * The sign of the z-component of all the cross-products is the * same for a convex polygon. * * See http://debian.fmi.uni-sofia.bg/~sergei/cgsr/docs/clockwise.htm * for justification. * * @param c1 */ boolean isConvex(PVector c1, PVector c2, PVector c3, PVector c4) { PVector v21= PVector.sub(c1, c2); PVector v32= PVector.sub(c2, c3); PVector v43= PVector.sub(c3, c4); PVector v14= PVector.sub(c4, c1); float i1=v21.cross(v32).z; float i2=v32.cross(v43).z; float i3=v43.cross(v14).z; float i4=v14.cross(v21).z; if ( (i1>0 && i2>0 && i3>0 && i4>0) || (i1<0 && i2<0 && i3<0 && i4<0)) return true; else if(verbose) System.out.println("Eliminating non-convex quad"); return false; } /** Compute the area of a quad, and check it lays within a specific range */ float validArea(PVector c1, PVector c2, PVector c3, PVector c4, float max_area, float min_area) { float i1=c1.cross(c2).z; float i2=c2.cross(c3).z; float i3=c3.cross(c4).z; float i4=c4.cross(c1).z; float area = Math.abs(0.5f * (i1 + i2 + i3 + i4)); if (area < max_area && area > min_area){ return area; } return 0; } /** Compute the (cosine) of the four angles of the quad, and check they are all large enough * (the quad representing our board should be close to a rectangle) */ boolean nonFlatQuad(PVector c1, PVector c2, PVector c3, PVector c4) { // cos(70deg) ~= 0.3 float min_cos = 0.5f; PVector v21= PVector.sub(c1, c2); PVector v32= PVector.sub(c2, c3); PVector v43= PVector.sub(c3, c4); PVector v14= PVector.sub(c4, c1); float cos1=Math.abs(v21.dot(v32) / (v21.mag() * v32.mag())); float cos2=Math.abs(v32.dot(v43) / (v32.mag() * v43.mag())); float cos3=Math.abs(v43.dot(v14) / (v43.mag() * v14.mag())); float cos4=Math.abs(v14.dot(v21) / (v14.mag() * v21.mag())); if (cos1 < min_cos && cos2 < min_cos && cos3 < min_cos && cos4 < min_cos) return true; else { if(verbose) System.out.println("Flat quad"); return false; } } ArrayList sortCorners(ArrayList quad) { // 1 - Sort corners so that they are ordered clockwise PVector a = quad.get(0); PVector b = quad.get(2); PVector center = new PVector((a.x+b.x)/2, (a.y+b.y)/2); Collections.sort(quad, new CWComparator(center)); // 2 - Sort by upper left most corner PVector origin = new PVector(0, 0); float distToOrigin = 1000; for (PVector p : quad) { if (p.dist(origin) < distToOrigin) distToOrigin = p.dist(origin); } while (quad.get(0).dist(origin) != distToOrigin) Collections.rotate(quad, 1); return quad; } } class CWComparator implements Comparator { PVector center; public CWComparator(PVector center) { this.center = center; } @Override public int compare(PVector b, PVector d) { if (Math.atan2(b.y-center.y, b.x-center.x)