2016年6月24日 星期五

3D scanner based on Arduino and Processing




Basically, we are looking for distance, between rotation axle and a point marked red by laser ("ro" on the picture)


To found this, we have to measure how many pixels are between optical axle of camera and laser-marked point. On picture, this distance is marked as "b". When we get that information, we have to convert it into millimeter (how many pixels are in one millimeter). Angle between laser and camera axle is constant and equals "alpha"

Using simple trigonometry, we can calculate "ro":
sin(alpha) = b / ro, which means that ro = b / sin(alpha)


Let's move to second picture.
Previous operations gave us coordinates in polar coordinates system. In polar system, every point look something like that:
P = (distance from Z axis, angle between point and X axis, Z) which is P = (ro, fi, z).
Ro is our distance, measured in previous operation. Fi is an angle of rotating platform. It grows an constant amount, every time platform rotate. This constant amount in equal 360 degree / number of operation
I.e. for 120 profiles around object, platform moves about  360deg / 120 = 3 deg. So after first move, fi = 3, after second fi = 6, after third fi = 9 etc.
Z value is the same value as Z in Cartesian system.

Conversion from polar to Cartesian is very simple:
x = ro * cos( fi )
y = ro * sin( fi )
z = z


Step 3: Motor

It is 4-connector bipolar stepper motor from an old OKI printer. It has 48 steps per revolution (7,5 deg per step), driven by 3,7V power supply. Integrated gear has 6:1 ratio, which means i had  6*48 steps on the output. It takes 200-250mA when moving.
I soldered 4 wires to connectors of stepper motor. To another ends of wires i have soldered single gold pin. Now it is very easy to connect it with driver.
I attached Lego pulley to the integrated gear. I took it out and drill 6 holes. Holes has same size and arrangement as holes on Lego pulley. Pulley and gear are joined together with „3-long” shafts.


Step 4: Motor driver and power supply


Step 6: Webcam



I used very primitive Creative Webcam Vista. It's rather old, it has poor sensor (640x480), it has poor optics (plastic lenses). But it has one advantage. I have already had it. It is also attached to rotating platform (little to low, need to change that soon).


Step 7: Linear laser





Poor quality (~1$) laser pointer is attached to cylindrical lens made from glass rod. This kind of glass rods are used in chemistry labs. Laser and lens is cased in Lego case (cased in case; thank you Captain Obvious...). Laser is turned on by rotating it a little bit, button is pushed by Lego. Also attached to platform. Angle between optical axle of camera and laser are around 30 degree.

Step 8: Arduino + IDE

I owe Arduino Leonardo only, so it was only choice i've got.
It has simple code, which causes rotate stepper when got command from Procesing. Commands are sent by Serial.
I chose 4 steps per phase, which means i got 120 photos and 120 profiles around object, every 12 degree. Less steps causes mistakes because of elasticity of rubber band.
It is using arduino's standard stepper library.

#include <Stepper.h>
Stepper oki(48,8,9); //see stepper tutorial in arduino.cc for info about that
const int ledPin = 13; // the pin that the LED is attached to
int incomingByte;      // a variable to read incoming serial data into

void setup() {
  // initialize serial communication:
  Serial.begin(9600);
  // initialize the LED pin as an output:
  pinMode(ledPin, OUTPUT);
  oki.setSpeed(60);
}

void loop() {
  // see if there's incoming serial data:
  if (Serial.available() > 0) {
    // read the oldest byte in the serial buffer:
    incomingByte = Serial.read();
    // if it's a capital H (ASCII 72), turn on the LED:
    if (incomingByte == 'S') {
      digitalWrite(ledPin, HIGH);
      oki.step(4);
    }
    // if it's an L (ASCII 76) turn off the LED:
    if (incomingByte == 'K') {
      digitalWrite(ledPin, LOW);
    }
  }
}


Why Processing? Because it is easy to use, with big reference and tutorial base. Also it is very similar to arduino. That means the probability of mistake during code writing decrease. Libraries are well documented also.

First thing to do in processing is installation of GSVideo library. Download and installation instructions are there: http://gsvideo.sourceforge.net/
So basically program sequence looks something like that, but it is divided into 2 loops (make photos and the rest):
make photo => find brightest pixel in every row => save picture of representation brightest pixels => find distance between middle of picture and brightest pixel in every row => convert gathered polar coordinates to kartesian XYZ  => save ASC file with point cloud.

Explanation can be found in comments in code.
First thing must be done preety soon is setting where Z-value is equal 0. Now Z=0 is set not on the center of platform, but on the first row of photo. This causes that output point cloud is upside-down.

code:
import codeanticode.gsvideo.*;
import processing.serial.*;

//objects
PFont f;
GSCapture cam;
Serial myPort;
PrintWriter output;

//colors
color black=color(0);
color white=color(255);

//variables
int itr; //iteration
float pixBright;
float maxBright=0;
int maxBrightPos=0;
int prevMaxBrightPos;
int cntr=1;
int row;
int col;

//scanner parameters
float odl = 210;  //distance between webcam and turning axle, [milimeter], not used yet
float etap = 120;  //number of phases profiling per revolution
float katLaser = 25*PI/180;  //angle between laser and camera [radian]
float katOperacji=2*PI/etap;  //angle between 2 profiles [radian]

//coordinates
float x, y, z;  //cartesian cords., [milimeter]
float ro;  //first of polar coordinate, [milimeter]
float fi; //second of polar coordinate, [radian]
float b; //distance between brightest pixel and middle of photo [pixel]
float pxmmpoz = 5; //pixels per milimeter horizontally 1px=0.2mm
float pxmmpion = 5; //pixels per milimeter vertically 1px=0.2mm

//================= CONFIG ===================

void setup() {
  size(800, 600);
  strokeWeight(1);
  smooth();
  background(0);

  //fonts
  f=createFont("Arial",16,true);
  
  //camera conf.
  String[] avcams=GSCapture.list();
  if (avcams.length==0){
    println("There are no cameras available for capture.");
    textFont(f,12);
    fill(255,0,0);
    text("Camera not ready",680,32);
  }
  else{
    println("Available cameras:");
    for (int i = 0; i < avcams.length; i++) {
      println(avcams[i]);
    }
    textFont(f,12);
    fill(0,255,0);
    text("Camera ready",680,32);
    cam=new GSCapture(this, 640, 480,avcams[0]);
    cam.start();
  }

  //Serial (COM) conf.
  println(Serial.list());
  myPort=new Serial(this, Serial.list()[0], 9600);

  //output file
  output=createWriter("skan.asc");  //plik wynikowy *.asc



}

//============== MAIN PROGRAM =================

void draw() {

  PImage zdjecie=createImage(cam.width,cam.height,RGB);
  cam.read();
  delay(2000);
  for (itr=0;itr<etap;itr++) {
    cam.read();
    zdjecie.loadPixels();
    cam.loadPixels();
    for (int n=0;n<zdjecie.width*zdjecie.height;n++){
      zdjecie.pixels[n]=cam.pixels[n];
    }
    zdjecie.updatePixels();
    set(20,20,cam);
    String nazwaPliku="zdjecie-"+nf(itr+1, 3)+".png";
    zdjecie.save(nazwaPliku);
    obroc();
    delay(500);
  }
  obroc();
  licz();
  noLoop();

}

void licz(){
  for (itr=0; itr<etap; itr++){
  
    String nazwaPliku="zdjecie-"+nf(itr+1, 3)+".png";
    PImage skan=loadImage(nazwaPliku);
    String nazwaPliku2="odzw-"+nf(itr+1, 3)+".png";
    PImage odwz=createImage(skan.width, skan.height, RGB);
    skan.loadPixels();
    odwz.loadPixels();
    int currentPos;
   
fi=itr*katOperacji;
    println(fi);

   
for(row=0; row<skan.height; row++){  //starting row analysis
    maxBrightPos=0;
    maxBright=0;
      for(col=0; col<skan.width; col++){
        currentPos = row * skan.width + col;
        pixBright=brightness(skan.pixels[currentPos]);
        if(pixBright>maxBright){ // 找最亮的點....
          maxBright=pixBright;
          maxBrightPos=currentPos;
        }

        odwz.pixels[currentPos]=black; //setting all pixels black
      }  //  end of 
for(col=0; col<skan.width; col++){
     
      odwz.pixels[maxBrightPos]=white; //setting brightest pixel white
     

/*
float pxmmpoz = 5; //pixels per milimeter horizontally 1px=0.2mm
float pxmmpion = 5; //pixels per milimeter vertically 1px=0.2mm

*/
//  影像的中心點....
      b=((maxBrightPos+1-row*skan.width)-skan.width/2)/pxmmpoz;
      ro=b/sin(katLaser);
      //output.println(b + ", " + prevMaxBrightPos + ", " + maxBrightPos); //I used this for debugging
     
      x=ro * cos(fi);  //changing polar coords to kartesian
      y=ro * sin(fi);
      z=row/pxmmpion;
     
      if( (ro>=-30) && (ro<=60) ){ //printing coordinates
        output.println(x + "," + y + "," + z);
      }
     
    }//end of row analysis
   
    odwz.updatePixels();
    odwz.save(nazwaPliku2);
   

  }
  output.flush();
  output.close();
}

void obroc() {  //sending command to turn
  myPort.write('S');
  delay(50);
  myPort.write('K');
}


Step 10: Scanning

Best scans are made when there is no lightning, so closing scanner in some enclosure will be good idea. If you don't have any, wait till evening, like I.
Turn on the power supply, turn on the laser, hit Run in Processing IDE. Wait till scanning is ready. You will get *.asc file, which contains Cartesian coordinates of every point.

Step 11: Point cloud




Download Meshlab (http://meshlab.sourceforge.net/) or use some other software to manage 3D point clouds. Import your *.asc file, simple by drag and drop method. Uncheck triangulation and hit OK. You will get see cloud points of scanned object! Success!
I cannot do almost anything more in Meshlab, because it is crashing a lot. Don't know why, I'll be fighting with this. But if you get stable version (is there any?) you can turn cloud into solid and exporting it as stereolitography *.stl file. And this can be printed on any 3D printer!

Step 12: Fighting with Meshlab


I've made something like that:
  1. Filters => Remeshing... => Surface reconstruction: Poisson; attributes 10, 8, 1, 1 (it is quite possible you will have to experiment with another values)
  2. Filters => Normals... => Invert face orientation
  3. Filters => Smoothing... => Taubin Smooth
  4. Filters => Vertex attribute transfer; mark "transfer geometry", "transfer normals"; source "another owl - good quality.asc"; target "poisson mesh"
As in previous step, there are attached 2 files with double extension. Delete last one(pdf), and you wil get *.asc file, directly from scanner and *.ply: solid made in meshlab (before another crash ofc).


Ref : http://www.instructables.com/id/Lets-cook-3D-scanner-based-on-Arduino-and-Proces/step2/Principle-of-operation/#

Ref : https://github.com/jwcrawley/3D-scanner

2016年6月18日 星期六

2016年6月17日 星期五

3D Scan and Print Yourself using FREE software

http://www.instructables.com/id/3D-Scan-and-Print-Yourself-using-FREE-software/

3D scan






 Encoding in Temporal Domain

A projector P with resolution Presx , Presy , will result in Ncols = log2 (Presx )e encoded patterns representing the columns, and in Nrows = log2 (Presy )e encoded patterns representing the rows. For example a projector with resolution 1024x768 will result in Ncols = 10 and Nrows = 10 i.e. a total of 20 patterns.

Gray-code Encoding

 however it ensures that there is only one bit different between consecutive patterns

When using Gray codes the value of the least significant bit changes after two consecutive stripes, in contrast to the Binary codes where the value changes at every pattern

Firstly, the choice of the colors to be used in the patterns. The patterns can have any two colors, although traditionally black and white has been used. In any case, each pixel must have an intensity value which will be used as a threshold to determine the value of the pixel i.e. 1 or 0. Therefore, it is imperative to take this into account when choosing the two colors and choose colors which will result in large intensity differences. A poor choice on colors, can otherwise jeopardize the entire process by failing to distinguish a pixel’s value later on in the process. For this reason and to overcome this limitation, it is preferable to project a pattern followed by a projection of its color-inverted pattern. Inverted pattern images are images with the same structure as the original but with inverted colors. This provides an effective method for easily determining the intensity value of each pixel when it is lit (highest value) and when it is not lit (lowest value). The threshold for the intensity value of a pixel p with a highest value ph and a lowest value pl can then be computed as the average τp = (ph − pl)/2.

Secondly, identifying shadow regions. The cameras observe the object from different angles than the projector, hence quite often there will be a viewing areas which lies in shadow regions. Thus, it is preferable that pixels falling under a shadow region are removed at the early stages of the process. This can be achieved by projecting a white and then black image on the object and capturing the images. By evaluating the intensity value of the pixels in the images, one can determine which pixels fall under a shadow region by identifying cases where the intensity values in the two captured images are very similar. A "shadow mask" can then be created which leaves only the pixels which do not fall under shadow regions. This can considerably reduce computational processing time. Section 0.7.1 explains how to compute the shadow mask.

Thus, the final projection sequence contains the column and row pattern sequences encoded using Gray-code, their inverted patterns, as well as two images of solid colors, one for each used color. The patterns are projected in sequence as follows: first the two solid color images, then interchangeably the column and its inverted sequence, followed by interchangeably the row and its inverted sequence



Decoding of Captured Images

1.Computing the shadow mask

The goal of this process is to determine which pixels in a camera’s image fall under shadow regions


2.Decoding the patterns
     The cameras capture images of the encoded projected patterns. The next step is to decode each pixel in the captured images into their corresponding decimal number representing the column and the row. This provides a mapping between the pixels in the cameras i.e. pixels in the captured images which correspond to the same projector pixel as shown in Figure 11

More specifically, the decoding is performed as follows:
• Determine whether a pixel p is lit or not (1 or 0) in the images capturing the projected sequence of patterns encoding the columns.
• Calculate its binary form Bp.
• Convert the binary form Bp into the equivalent decimal number x.

Ref : http://arxiv.org/pdf/1406.6595v1.pdf

2016年6月11日 星期六

III專題 06/11



Home 點 距離   右上corner 的珠子的距離為 (27,0) mm

珠子的直徑大概11 mm...

目前第一步是會先移到到左上角的第一顆.....然後藉由演算法算出來的座標去移動

然後最後在移動回左上角的第一顆的位置....再回到home....


G code 的 格式

  • G0 is rapid move. It moves the machine to the given coordinates, with the expectation that no machining takes place during the move (tool not in contact with the stock). Unless the mode is changed by other G-code commands, the coordinates are absolute: G0 X10 moves to X=10, G0 X10 again does nothing because you're already at X=10. If coordinates for two or more axes are given, the machine moves in a straight line to the specified point. Starting from X=0, Y=0, the command G0 X10 Y10 moves diagonally to X=10, Y=10. Even if the axes have different maximum speeds and accelerations, the machine still moves them in a coordinated fashion, so that the move is linear. Only the axes specified move; the others do not change position.
  • G1 is linear move. It moves the machine to the given coordinates, with the expectation that the tool would be cutting. It's exactly like G0, except it has an extra parameter, F, that gives the feed rate (the speed at which to move). The speed is expressed in units per minute (mm per minute or inches per minute, depending on mode -- default mm/min). So, with the machine at X=0, Y=0, the command G1 X100 Y100 F200 moves it diagonally to X=100, Y=100, a distance of about 141 mm, at 200 mm/min, so it takes about 43 seconds to get there.

  • G2 and G3 are arc moves (clockwise and counter-clockwise), and they're described very well here. I would use only the I J form and not even bother with the R form.[2]

我目前是採用  G91...  相對的模式....
G90Switch to absolute distance modeCoordinates are now relative to the origin of the currently active coordinate system, as opposed to the current position. G0 X-10 Y5 will move to the position 10 units to the left and 5 above the origin X0,Y0. cf. G91 below.All Grbl versions
G91Switch to incremental distance modeCoordinates are now relative to the current position, with no consideration for machine origin. G0 X-10 Y5 will move to the position 10 units to the left and 5 above the current position. cf. G90 above.All Grbl versions











2016年6月7日 星期二

3D scan code study , step 5

import numpy as np
import cv2
import math
def camxyzparam(pxpy):
    ##################################################### function for calculating X,Y, and Z of points
    fcl=0.00269816   #pixel size for left camera Focal Length
    fcr=0.00269816  #pixel size for right camera
    tetl=0.26179938779914943653855361527329  
                                #left camera rotation angle around Y axis (15 deg)
    tetr=-0.26179938779914943653855361527329    #right camera rotation angle
    phil=0     #left camera rotation angle around X axis
    phir=0
    x0l=250     # left camera translation in X direction
    x0r=-250
    y0l=0      # right camera translation in Y direction
    y0r=0
    z0l=0  
    z0r=0
    ccddr=3.67    #focal lenght right camera mm
    ccddl=3.67    #focal lenght left camera
    ###################################################
    x0=x0r 
    y0=y0r 
    z0=z0r 
    x1=-(pxpy[0]-960)*fcr   #px1  ,  960 為  1920/2,  fcr 為right focus length
    y1=(pxpy[1]-540)*fcr   #py1     , 540 為  1080/2,  fcl 為left focus length
    z1=ccddr
    alfa=tetr
    beta=phir
    gama=0
    Rright = np.array([[math.cos(gama), -math.sin(gama), 0],[math.sin(gama), math.cos(gama), 0],[   0, 0, 1]])
    Rright = Rright.dot(np.array([[1 ,0 ,0 ], [0 ,math.cos(beta), -math.sin(beta)] , [0 ,math.sin(beta), math.cos(beta)]]))
    Rright = Rright.dot(np.array([[math.cos(alfa),0 ,-math.sin(alfa)], [0, 1, 0], [math.sin(alfa), 0, math.cos(alfa)]]))
    XA=np.array(Rright.dot(([[x1],[y1],[z1]]))+([[x0],[ y0],[ z0]]))
    x1=XA[0]   
    y1=XA[1]   
    z1=XA[2] 
    x2=x0l
    y2=y0l
    z2=z0l
    xh3=-(pxpy[2]-960)*fcl   #px2
    yh3=(pxpy[3]-540)*fcl   #py2
    zh3=ccddl
    alfa=tetl
    beta=phil
    gama=0
    Rleft = np.array([[math.cos(gama), -math.sin(gama), 0],[math.sin(gama), math.cos(gama), 0],[   0, 0, 1]])
    Rleft = Rleft.dot(np.array([[1 ,0 ,0 ], [0 ,math.cos(beta), -math.sin(beta)] , [0 ,math.sin(beta), math.cos(beta)]]))
    Rleft = Rleft.dot(np.array([[math.cos(alfa),0 ,-math.sin(alfa)], [0, 1, 0], [math.sin(alfa), 0, math.cos(alfa)]]))
    XB=np.array(Rleft.dot(([[xh3],[yh3],[zh3]]))+([[x2],[y2],[z2]]))
    x3=XB[0]   
    y3=XB[1]   
    z3=XB[2]
    u=[float(x1)-x0,float(y1)-y0,float(z1)-z0]
    v=[float(x3-x2),float(y3-y2),float(z3-z2)]
    p=[x0,y0,z0]
    q=[x2,y2,z2]
    w=np.subtract(p,q)
    denomst=np.inner(v,u)*np.inner(v,u)-np.inner(v,v)*np.inner(u,u)
    s=(np.inner(w,u)*np.inner(v,v)-np.inner(v,u)*np.inner(w,v))/denomst
    t=(np.inner(v,u)*np.inner(w,u)-np.inner(u,u)*np.inner(w,v))/denomst
    xyz=np.divide((np.add(p,np.multiply(s,u))+np.add(q,np.multiply(t,v))),2)
    abdist=np.add(p,np.multiply(s,u))-np.add(q,np.multiply(t,v))
    return xyz,abdist

###
numpy.inner(a, b)
Inner product of two arrays.
####
w = p − q (11)



XYZ,abdist=camxyzparam([960,540,960,540]) # test function
print XYZ

#==================================================================
ii=0
rightcod=[]
import csv

with open('rightcod', 'rb') as csvfile:
     xyreader = csv.reader(csvfile, delimiter=',', quotechar='|')
     for row in xyreader:
         rightcod.append([int(row[0]),int(row[1]),int(row[2])])


##  rightcod 的內容
167461 (亮度值), 0(xx), 0 (yy)
39489, 0, 1
7685, 0, 2
2049, 0, 3
4098, 0, 4
##

a = np.array(rightcod)
aa=a[a[:,0].argsort(),]
aaa, right_idx=np.unique(aa[:,0],return_index=True)

m=aaa.size
print 'Total points from right camera= ',m
rightcodmean=np.zeros([m,3])

for ii in range(0,m-1):
    rightcodmean[ii]=[aaa[ii],np.mean(aa[right_idx[ii]:right_idx[ii+1],1]),np.mean(aa[right_idx[ii]:right_idx[ii+1],2])]

#


numpy.mean(a, axis=None, dtype=None, out=None, keepdims=False)[source]
Compute the arithmetic mean along the specified axis.

csvfile.close()
#==================================================================
ii=0
leftcod=[]
with open('leftcod', 'rb') as csvfile:
     xyreader = csv.reader(csvfile, delimiter=',', quotechar='|')
     for row in xyreader:
         leftcod.append([int(row[0]),int(row[1]),int(row[2])])

a = np.array(leftcod)
aa=a[a[:,0].argsort(),]
aaa, left_idx=np.unique(aa[:,0],return_index=True)

m=aaa.size
print 'Total points left= ',m
leftcodmean=np.zeros([m,3])

for ii in range(0,m-1):
    leftcodmean[ii]=[aaa[ii],np.mean(aa[left_idx[ii]:left_idx[ii+1],1]),np.mean(aa[left_idx[ii]:left_idx[ii+1],2])]

codes=np.append(rightcodmean[:,0],leftcodmean[:,0])  #  左邊和右邊的 gray code 亮度
unicod=np.unique(codes[:])


##


numpy.unique(ar, return_index=False, return_inverse=False, return_counts=False)[source]
Find the unique elements of an array.

Examples
>>>
>>> np.unique([1, 1, 2, 2, 3, 3])
array([1, 2, 3])
>>> a = np.array([[1, 1], [2, 3]])
>>> np.unique(a)
array([1, 2, 3])


maskright=np.in1d(unicod,rightcodmean[:,0])
###


numpy.in1d(ar1, ar2, assume_unique=False, invert=False)[source]
Test whether each element of a 1-D array is also present in a second array.
Returns a boolean array the same length as ar1 that is True where an element of ar1 is inar2 and False otherwise.



maskrightindex=np.searchsorted(rightcodmean[:,0],unicod)

####


numpy.searchsorted(a, v, side='left', sorter=None)[source]
Find indices where elements should be inserted to maintain order.
Find the indices into a sorted array a such that, if the corresponding elements in v were inserted before the indices, the order of a would be preserved.

Examples
>>>
>>> np.searchsorted([1,2,3,4,5], 3)
2
>>> np.searchsorted([1,2,3,4,5], 3, side='right')
3
>>> np.searchsorted([1,2,3,4,5], [-10, 10, 2, 3])
array([0, 5, 1, 2])

maskleft=np.in1d(unicod,leftcodmean[:,0])
maskleftindex=np.searchsorted(leftcodmean[:,0],unicod)


camrcolor=cv2.imread("CAMR/CAM001.png");
camrcolol=cv2.imread("CAML/CAM101.png");



kk=0
m=unicod.size
print 'Total points on left and right cameras= ',m
matchpixels =  np.zeros([4])
xyz=np.zeros([m,3])
xyzcolor=np.zeros([m,3],dtype=np.uint8)
# finding common points between two cameras and calculating XYZ
for ii in range(0,m-1):
    if (maskleft[ii] and maskright[ii]):
        matchpixels[0]=rightcodmean[maskrightindex[ii],1]
        matchpixels[1]=rightcodmean[maskrightindex[ii],2]
        matchpixels[2]=leftcodmean[maskleftindex[ii],1]
        matchpixels[3]=leftcodmean[maskleftindex[ii],2]
        # 找到 相同點....然後達到這點在左右camera 的x,y 座標
        xyzdata,abdist=camxyzparam([matchpixels[0],matchpixels[1],matchpixels[2],matchpixels[3]])
        #check if the points is in specified limit and distance between rays less than some values
        if ((np.linalg.norm(abdist)<20) and (xyzdata[2]>400 and xyzdata[2]<2000 and xyzdata[0]>-500 and xyzdata[0]<500)):
           xyz[kk,0]= -xyzdata[0]
           xyz[kk,1]= -xyzdata[1]
           xyz[kk,2]= -xyzdata[2]
           # color info from average of image from both cameras
           xyzcolor[kk,0]= (camrcolor[int(matchpixels[1]),int(matchpixels[0]),2]/2+camrcolol[int(matchpixels[3]),int(matchpixels[2]),2]/2)
           xyzcolor[kk,1]= (camrcolor[int(matchpixels[1]),int(matchpixels[0]),1]/2+camrcolol[int(matchpixels[3]),int(matchpixels[2]),1]/2)
           xyzcolor[kk,2]= (camrcolor[int(matchpixels[1]),int(matchpixels[0]),0]/2+camrcolol[int(matchpixels[3]),int(matchpixels[2]),0]/2)
           kk=kk+1




print 'Total points = ',kk-1

# open a PLY file to save the XYZ and colors of point cloud
ff=open(captdirect+"/"+"pointcloud.ply","w")
ff.write('ply\n')
ff.write('format ascii 1.0\n')
ff.write('comment PCL generated\n')
ff.write('element vertex %d\n'%(kk-1))
ff.write('property float x\n')
ff.write('property float y\n')
ff.write('property float z\n')
ff.write('property uchar red\n')
ff.write('property uchar green\n')
ff.write('property uchar blue\n')
ff.write('end_header\n')


for ii in range(0,kk-1):
    ff.write(str(xyz[ii,0])+" "+str(xyz[ii,1])+" "+str(xyz[ii,2])+" "+str(xyzcolor[ii,0])+" "+str(xyzcolor[ii,1])+" "+str(xyzcolor[ii,2])+"\n")    

ff.close()
print 'calcxyzcolor Done!'


===================================================
paper  :

0.8.2 Ray Triangulation Given one pixel in image I1 and its corresponding pixel in image I2, two rays are formed as described above, and their intersection is computed. In practice, the triangulation of two rays in 3D space can be considered as an ill-posed problem since quite often the two rays do not intersect ’exactly’ but rather pass by one another in close proximity. In order to overcome this limitation, the segment perpendicular to the two rays with the shorted distance is computed, and the middle point of the segment is considered to be the intersection point. Figure 12 shows an example where the segment ab is the shortest line connecting the two rays A and B. The mid-point p is considered to be the intersection point.

Computation of the Intersection Point: Consider two lines in 3D space A and B passing through points p and q, with direction vectors ~u and ~v respectively, and let the two closest points on the lines be a and b, as defined in Equation 5 and Equation 6, where s and t are scalar values.  The segment connecting a and b is perpendicular to the lines, hence the dot product of their vectors is equal to 0 as follows, 


a = p + s ∗ ~u (5)
b = q + t ∗ ~v (6)
The segment connecting a and b is perpendicular to the lines, hence the dot product of their vectors is equal to 0 as follows,
(a − b).~u = 0 (7)
 (a − b).~v = 0 (8) 

and with Equations 5 and 6, the Equations 7 and 8 become,
~w.~u + s ∗ ~u.~u − t ∗ ~v.~u = 0 (9)
 ~w.~v + s ∗ ~v.~u − t ∗ ~v.~v = 0 (10)

w = p − q (11)




Ref : http://arxiv.org/pdf/1406.6595v1.pdf

八皇后的演算法



#include <stdio.h>
#include <stdlib.h>

void queens(int x);
void print(void);

unsigned int n, num;
char** checkerboard;
int* column;
int* right;
int* left;

假設n 為 4....

int main(void)
{
    int i, j;

    printf("請輸入 n 的大小: ");
    scanf("%d", &n);

    // 動態分配記憶體
    column = malloc(sizeof(int) * n);
    right = malloc(sizeof(int) * (2 * n - 1));
    left = malloc(sizeof(int) * (2 * n - 1));
    checkerboard = malloc(sizeof(char*) * n);

    // 變數初始化
    num = 0;
    for (i = 0; i < n; i++)
    {
        column[i] = 1;

        checkerboard[i] = malloc(sizeof(char) * n);
        for (j = 0; j < n; j++)
        {
            checkerboard[i][j] = 'x';
        }
    }

    for (i = 0; i < 2 * n - 1; i++)  //  i從  0 到 6 
    {
        right[i] = left[i] = 1;   //  先初始化為1
    }

    queens(0);   // 先排一個皇后

    printf("\n總共有 %d 種排法\n\n", num);

    // 釋放記憶體空間
    for (i = 0; i < n; i++)
    {
        free(checkerboard[i]);
    }

    free(checkerboard);
    free(column);
    free(right);
    free(left);

    system("pause");
}

void queens(int x)   // 一開始x 為 0 ,  下次進來會變成  1, 2, 3
{
    if (x < n)  //  n 為 4
    {
        int i;
        for (i = 0; i < n; i++) //  0 到 3
        {
            int j = i - x + n - 1;  // 右邊的x 座標, i為0,  x為0,  就是3
            int k = i + x;          // 左邊的x 座標, i為0,  x為0,  就是0
                                    // 右邊的x 座標, i為1,  x為0,  就是4
                                    // 左邊的x 座標, i為1,  x為0,  就是1

                                    // 右邊的x 座標, i為2,  x為0,  就是5
                                    // 左邊的x 座標, i為2,  x為0,  就是2

                                    // 右邊的x 座標, i為3,  x為0,  就是6
                                    // 左邊的x 座標, i為3,  x為0,  就是3

// 右邊的x 座標, i為0, x為1, 就是2
                                    // 左邊的x 座標, i為0,  x為1,  就是1
                                    // 右邊的x 座標, i為1,  x為1,  就是3
                                    // 左邊的x 座標, i為1,  x為1,  就是2

                                    // 右邊的x 座標, i為2,  x為1,  就是4
                                    // 左邊的x 座標, i為2,  x為1,  就是3

                                    // 右邊的x 座標, i為3,  x為1,  就是5
                                    // 左邊的x 座標, i為3,  x為1,  就是4

// 他使用 left 和 right array 來排除 左下角和 右下角的case
 //   假設   (col, row) -> (i,x) 
 // example 1 :  (1,2) 和 (2,1)   就是相衝突...
  //            兩個(i,x)帶進去算出來的k 都是 3  -> 所以這次的 left[k] 就已經被清成0
  //             不會成立
 // example 2 :  (1,2) 和 (2,3)   就是相衝突...
  //            兩個(i,x)帶進去算出來的j 都是 2  -> 所以這次的 right[j] 就已經被清成0
  //    


            if (column[i] && right[j] && left[k])
            {
                // 標記皇后位置, 並遞迴放置下一個
                column[i] = right[j] = left[k] = 0;
                checkerboard[x][i] = 'Q';

                queens(x + 1);

                column[i] = right[j] = left[k] = 1;
                checkerboard[x][i] = 'x';
            }
        }
    }
    else
    {
        // 輸出棋盤
        print();
        num++;
    }
}

void print(void)
{
    int i, j;

    printf("\n");
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%c", checkerboard[i][j]);
        }

        printf("\n");
    }
}