/* built with Studio Sketchpad:
* https://sketchpad.cc
*
* observe the evolution of this sketch:
* https://studio.sketchpad.cc/sp/pad/view/ro.$YajvKSr1xX/rev.2396
*
* authors:
* Masakazu Matsumoto
*
* license (unless otherwise specified):
* creative commons attribution-share alike 3.0 license.
* https://creativecommons.org/licenses/by-sa/3.0/
*/
// -*- javascript -*-
// This sketch builds on a prior work, "hull5", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.90J5n40eh-tAf/rev.882
// This sketch builds on a prior work, "hull4", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.9We3Kplm-bQ6W/rev.681
// This sketch builds on a prior work, "hull3", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.9$Hd6L5iZ4Ot4/rev.123
// This sketch builds on a prior work, "hull2", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.9etopzTtVrWvr/rev.735
// This sketch builds on a prior work, "Modified clone of 'hull'", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.9LrWM-dHxG6WF/rev.2316
// This sketch builds on a prior work, "hull", created by Masakazu Matsumoto
// http://studio.sketchpad.cc/sp/pad/view/ro.9hhvcmpZ$Xv5K/rev.3095
// Pressing Control-R will render this sketch.
//Convex hull composer.
//The convex hull consists of vertices on a sphere is drawn on an equirectangular map interactively.
//the next step is to develop it.
////////////////////////////////////////////Convex hull
var norm(var v){
float s = 0.0;
for(int dim=0; dim<3; dim++){
s += v[dim]*v[dim];
}
return sqrt(s);
}
var normalize(var v){
float n = 1./norm(v);
var newv = new Array(3);
for(int dim=0; dim<3; dim++){
newv[dim] = v[dim]*n;
}
return newv;
}
var plain(var vertices, var vs){
//println(["vs",vs]);
var v0 = vertices.get(vs[0]);
var v1 = vertices.get(vs[1]);
var v2 = vertices.get(vs[2]);
var v01 = [];
var v02 = [];
for(int dim=0; dim<3; dim++){
v01.push(v1[dim]-v0[dim]);
v02.push(v2[dim]-v0[dim]);
}
//normal vector
var n = [v02[1]*v01[2] - v02[2]*v01[1],
v02[2]*v01[0] - v02[0]*v01[2],
v02[0]*v01[1] - v02[1]*v01[0],];
n = normalize(n);
//plain: nx(x-a)+ny(y-b)+nz(z-c)=0 ==> ax+by+cz+d=0//
n.push(-n[0]*v0[0]-n[1]*v0[1]-n[2]*v0[2]);
if(n[3]>0.0){
return null;
}
return n;
}
void addVertex(var triangles, HashMap vertices, var newv, var nextv){
var edges = {};
var i=0;
while(i<triangles.length){
var s = 0.0;
for(int dim=0;dim<3;dim++){
s += triangles[i][3][dim]*newv[dim];
}
s += triangles[i][3][3];
if(s > 0.0){
edges[triangles[i][0]*1024+triangles[i][1]] = 1;
edges[triangles[i][1]*1024+triangles[i][2]] = 1;
edges[triangles[i][2]*1024+triangles[i][0]] = 1;
triangles.splice(i,1);
}
else{
i += 1;
}
}
for(edge in edges){
var e0 = edge >> 10;
var e1 = edge % 1024;
var egde = e1*1024+e0;
edges[egde] -= 1;
}
var rim = [];
//remove the overlapped edges
for(var edge in edges){
if(edges[edge]==1){
rim.push(edge);
}
}
//add the vertice
vertices.put(nextv, newv);
var vv = nextv;
//println(["Added",vv]);
nextv += 1;
//add the triangles
for(int i=0;i<rim.length;i++){
var edge = rim[i];
var e0 = edge >> 10;
var e1 = edge % 1024;
var t;
t = [e0,e1,vv];
t.push(plain(vertices,t));
triangles.push(t);
}
return nextv;
}
var triangulation(var rim, var veryfirst, var vertices, var tris){
var first = veryfirst;
while(1){
//first triplet
var second = rim[first];
var third = rim[second];
var t = [first,second,third];
//これが酷い選択の場合がありうる。checkを追加する。
//check
var pl = plain(vertices,t);
while ( pl === null ){
first = second;
second = third;
third = rim[third];
if (first == veryfirst){
//println(["RemovalFailed",vv]);
return 1;//err. removal failed.
}
t = [first,second,third];
pl = plain(vertices,t);
}
t.push(pl);
if(rim[third] == first){ //rim is triangle
tris.push(t);
return 0;
}
//まず最初の候補ができた。
//残りの点がすべて裏にあることを確認する。
var next = rim[third];
var isconvex = 1;
while ( next != first ){
var newv = vertices.get(next);
var s = 0.0;
for(int dim=0;dim<3;dim++){
s += t[3][dim]*newv[dim];
}
s += t[3][3];
if(s > 0.0){
isconvex = 0;
break;
}
next = rim[next];
}
if ( isconvex ){
tris.push(t);
rim[first] = third; //skip the second
//recurse
return triangulation(rim, first, vertices, tris);
}
first = second;
if(first == veryfirst){
return 3;
}
}
}
var removeVertex(var triangles, HashMap vertices, var vv){
if ( vv < 0 ){
return 9;
}
//println(["Remove",vv]);
//for(var i in triangles){
// println([i,triangles[i]]);
//}
var rim = {}; // chain of rim vertices.
//look up the triangles having vv
var trash = [];
var i=0;
var first = 0;
for(var i=0;i<triangles.length;i++){
if(triangles[i][0] == vv){
rim[triangles[i][1]] = triangles[i][2];
first = triangles[i][1];
trash.push(i);
}
else if (triangles[i][1] == vv){
rim[triangles[i][2]] = triangles[i][0];
first = triangles[i][2];
trash.push(i);
}
else if (triangles[i][2] == vv){
rim[triangles[i][0]] = triangles[i][1];
first = triangles[i][0];
trash.push(i);
}
}
//for(var i in rim){
// println(["Rim",i,rim[i]]);
//}
//remove the vertex
//hatch the hole.
var hatches = [];
var err = triangulation(rim, first, vertices, hatches);
if ( err ){
return err;
}
//all succeeded
//remove the triangles
while( trash.length > 0 ){
var tri = trash.pop();
triangles.splice(tri,1);
}
//remove the vertex
vertices.remove(vv);
for(var i=0;i<hatches.length;i++){
//println(["hatches",hatches[i]]);
triangles.push(hatches[i]);
}
return 0;//no error
}
/////////////////////////globals and initialization
//initial tetrahedron
HashMap vertices = new HashMap();; // do not reuse the vertex label
vertices.put(0, normalize([-1.,-1.,-1.]));
vertices.put(1, normalize([+1.,+1.,-1.]));
vertices.put(2, normalize([-1.,+1.,+1.]));
vertices.put(3, normalize([+1.,-1.,+1.]));
var nextv = 4;
var triangles = [];
var t;
t = [0,1,2];
t.push(plain(vertices,t));
triangles.push(t);
t = [0,2,3];
t.push(plain(vertices,t));
triangles.push(t);
t = [0,3,1];
t.push(plain(vertices,t));
triangles.push(t);
t = [3,2,1];
t.push(plain(vertices,t));
triangles.push(t);
//test
//newv = [1.,2.,3.];
//newv = normalize(newv);
//nextv = addVertex(triangles, vertices, newv, nextv);
//for(int i=0;i<triangles.length;i++){
// println([triangles[i][0],triangles[i][1],triangles[i][2]]);
//}
//println(vertices.length);
/////////////////////////utility
var pi = 3.14159265359;
var cartesian2euler(var v){
var r = sqrt(v[0]*v[0]+v[1]*v[1]);
var theta = atan(v[2]/r);
var phi = atan(v[1]/v[0]);
if(v[0]<0){
phi += pi;
}
if(phi > pi){
phi -= 2*pi;
}
return [phi,theta];
}
/////////////////////////setup
//PImage online;
void setup() { // this is run once.
// set the background color
background(255);
size(640,640);
//String url = "http://farm4.staticflickr.com/3439/3945563797_840ce46f5b_z.jpg";
//online = loadImage(url, "jpg");
//size(min(screen.width,screen.height),min(screen.width,screen.height));
// smooth edges
smooth();
// limit the number of frames per second
frameRate(24);
// set the width of the line.
//strokeWeight(12);
}
/////////////////////////mouse action
var origin = -1;
var angle = 0; //rotation angle of preview
var mode = 0; //1==equirectangular panel / 2==orthographic panel
var lastx = 0;
var lasty = 0;
var updated = 1;
var addVertexOnTheMap()
{
var phi = mouseX / width * 2*pi - pi;
var theta = mouseY / width * 2*pi - pi/2;
var st = sin(theta);
var ct = cos(theta);
var sp = sin(phi);
var cp = cos(phi);
var x = cp*ct;
var y = sp*ct;
var z = st;
var newv = [x,y,z];
angle = -phi - pi/2;
var target = nextv;
nextv = addVertex(triangles, vertices, newv, nextv);
return target;
}
var addVertexOnPreview(){
//add a new point by default
var zoom = width / 4;
var x = (mouseX - zoom)/zoom;
var z = (mouseY - zoom*3)/zoom;
var d = x*x+z*z;
if ( d < 1.0 ){
var y = -sqrt(1.0-d);
var cosa = cos(angle);
var sina = sin(angle);
var rx = x*cosa + y*sina;
var ry = -x*sina + y*cosa;
var newv = [rx,ry,z];
var euler = cartesian2euler(newv);
var sx = (euler[0]/ (2*pi) + 0.5)*width;
var sy = (euler[1] / pi + 0.5)*width/2;
newv.push(sx);
newv.push(sy);
//angle = -(sx / width * 2*pi) + pi/2;
var target = nextv;
nextv = addVertex(triangles, vertices, newv, nextv);
return target;
}
return -1;
}
void mousePressed() {
origin = -1;
lastx = mouseX;
lasty = mouseY;
if ( mouseY < width/2 ){
//equirectangular panel
mode = 1;
//look up the existing vertices
var candidate = -1;
var mindist = 20*20;
Iterator i = vertices.entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
var x = vtx[3];
var y = vtx[4];
//println([x,y]);
var dx = x - mouseX;
var dy = y - mouseY;
var dd = dx*dx + dy*dy;
if ( dd < mindist ){
candidate = me.getKey();
mindist = dd;
}
}
if ( candidate >= 0 ){
origin = candidate;
angle = -(mouseX / width * 2*pi) + pi/2;
}
//if no correspondence,
if ( origin < 0 ){
//create a new point
origin = addVertexOnTheMap();
}
}
if ( mouseY > width/2 ){
//orthographic panel
mode = 2;
//look up the existing vertices
var candidate = -1;
var mindist = 20*20;
Iterator i = vertices.entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
if ( vtx[7] == 1 ){ //frontside
var x = vtx[5];
var y = vtx[6];
var dx = x - mouseX;
var dy = y - mouseY;
var dd = dx*dx + dy*dy;
if ( dd < mindist ){
candidate = me.getKey();
mindist = dd;
}
}
}
if ( candidate >= 0 ){
origin = candidate;
//angle = -(mouseX / width * 2*pi) + pi/2;
//println([target,x,y,mouseX,mouseY]);
}
if ( origin < 0 ){
origin = addVertexOnPreview();
}
}
//println(target);
updated = 1;
}
void mouseDragged(){
if ( (mode == 2) && (origin < 0) ){
//rotation mode
angle += (mouseX-pmouseX)*0.01;
updated = 1;
return;
}
if ( abs(mouseX - lastx) + abs(mouseY-lasty) < 15 ){
//動きが小さい場合は、削除→追加の順で処理する。
lastx = mouseX;
lasty = mouseY;
//println("Drag: "+mode);
if ( mode == 1 ){
//equirectangular panel
//drag mode;
int err = removeVertex(triangles, vertices, origin);
if ( ! err ){
origin = addVertexOnTheMap();
}
else{
origin = -1;
}
updated = 1;
}
if ( mode == 2 ){
//stereographic panel
//drag mode;
int err = removeVertex(triangles, vertices, origin);
if ( ! err ) {
origin = addVertexOnPreview();
}
else{
origin = -1;
}
updated = 1;
}
}
else{
lastx = mouseX;
lasty = mouseY;
//println("Drag: "+mode);
if ( mode == 1 ){
//equirectangular panel
var target = addVertexOnTheMap();
//drag mode;
removeVertex(triangles, vertices, origin);
origin = target;
updated = 1;
}
if ( mode == 2 ){
//stereographic panel
//drag mode;
var target = addVertexOnPreview();
removeVertex(triangles, vertices, origin);
origin = target;
updated = 1;
}
}
}
void mouseReleased(){
//text("pos"+mouseX+":"+mouseY,10,30);
if ( mode == 1 ){
if ( (origin >=0) && (mouseX < 20 ) && (mouseY < 20 ) ){
//trash the node
int err = removeVertex(triangles, vertices, origin);
}
}
updated = 1;
origin = -1;
mode = 0;
}
/////////////////////////panels
//interpolate
void drawLine(var v1, var v2)
{
var v0 = [v1[0]+v2[0],v1[1]+v2[1],v1[2]+v2[2]];
var L = norm(v0);
var vn = normalize(v0);
if(L < 1.999){
var euler = cartesian2euler(vn);
var x = (euler[0]/ (2*pi) + 0.5)*width;
var y = (euler[1] / pi + 0.5)*width/2;
ellipse(x,y,1,1);
drawLine(v1,vn);
drawLine(vn,v2);
}
}
void interactive_panel(var vertices, var triangles)
{
//image(online,0,0);
//text("Target:"+target,10,10);
//text("Pressd:"+mousePressed,10,20);
//trashbox
fill(#ff0000);
rect(0,0,20,20);
textAlign(LEFT);
text("Trash",22,15);
textAlign(RIGHT);
text("Equirectangular",width-2,10);
//nostroke();
fill(0);
//draw vertices
Iterator i = vertices.entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
var euler = cartesian2euler(vtx);
var x = (euler[0]/ (2*pi) + 0.5)*width;
var y = (euler[1] / pi + 0.5)*width/2;
if(vtx.length == 3){
vtx.push(0);
vtx.push(0);
}
vtx[3] = x;
vtx[4] = y;
if(me.getKey() == origin){
fill(#ff0000);
}
else{
fill(0);
}
rect(x-4,y-4,9,9);
//text(me.getKey(),x,y-5);
}
//draw edges
stroke(192);
for(int i=0; i<triangles.length;i++){
edges = [[triangles[i][0],triangles[i][1]],
[triangles[i][1],triangles[i][2]],
[triangles[i][2],triangles[i][0]]];
for(int e=0;e<3;e++){
if(edges[e][0] < edges[e][1]){
drawLine(vertices.get(edges[e][0]),vertices.get(edges[e][1]));
}
}
}
//draw face id
/*for(int i=0; i<triangles.length;i++){
var euler = cartesian2euler(triangles[i][3]);
var x = (euler[0]/ (2*pi) + 0.5)*width;
var y = (euler[1] / pi + 0.5)*width/2;
text(i,x,y-5);
}*/
}
void preview_panel(var vertices, var triangles)
{
fill(#ff0000);
textAlign(RIGHT);
text("Orthographic",width/2-2,width/2+10);
var cosa = cos(angle);
var sina = sin(angle);
var zoom = width / 4;
fill(0);
ellipse(zoom,zoom*3,zoom*2+15,zoom*2+15);
fill(255);
ellipse(zoom,zoom*3,zoom*2,zoom*2);
//rotate vertices in advance
Iterator i = vertices.entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
vtx.length = 8;
vtx[5] = zoom * ( vtx[0]*cosa - vtx[1]*sina )+zoom;
vtx[6] = zoom * vtx[2] + 3*zoom;
vtx[7] = 0; //backward
}
stroke(0);
for(int i=0; i<triangles.length;i++){
var plane = triangles[i][3];
//rotate normal
var ny = plane[0]*sina + plane[1]*cosa;
if ( ny < 0 ){
fill((int)(255*(-ny)));
beginShape();
for(int j=0;j<3;j++){
var v = vertices.get(triangles[i][j]);
v[7] = 1;
vertex(v[5],v[6]);
}
endShape(CLOSE);
}
}
Iterator i = vertices.entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
if(vtx[7]==1){
if(me.getKey() == origin){
fill(#ff0000);
}
else{
fill(0);
}
rect(vtx[5]-4,vtx[6]-4,9,9);
}
}
}
/////////////////////////development
void distanceMatrix(var vertices, var triangles)
{
var dm = new Array(triangles.length);
for(int i=0;i<dm.length;i++){
dm[i] = new Array(dm.length);
for(int j=0;j<dm.length;j++){
dm[i][j] = 1.0;
}
}
//まず共有辺の表が必要。
var edges = {};
for(int i=0;i<triangles.length;i++){
edges[[triangles[i][0],triangles[i][1]]] = i;
edges[[triangles[i][1],triangles[i][2]]] = i;
edges[[triangles[i][2],triangles[i][0]]] = i;
}
//println("");
for(int i=0;i<triangles.length;i++){
var va = triangles[i][0];
var vb = triangles[i][1];
var j = edges[[vb,va]];
if (i<j){
var s = 0.0;
for(int dim=0;dim<3;dim++){
s += vertices.get(va)[dim] * vertices.get(vb)[dim];
}
dm[i][j] = [s,va,vb];//innerproduct and labels of shared vertices
dm[j][i] = [s,vb,va];
//println([i,j,s]);
}
va = triangles[i][1];
vb = triangles[i][2];
var j = edges[[vb,va]];
if (i<j){
var s = 0.0;
for(int dim=0;dim<3;dim++){
s += vertices.get(va)[dim] * vertices.get(vb)[dim];
}
dm[i][j] = [s,va,vb];
dm[j][i] = [s,vb,va];
//println([i,j,s]);
}
va = triangles[i][2];
vb = triangles[i][0];
var j = edges[[vb,va]];
if (i<j){
var s = 0.0;
for(int dim=0;dim<3;dim++){
s += vertices.get(va)[dim] * vertices.get(vb)[dim];
}
dm[i][j] = [s,va,vb];
dm[j][i] = [s,vb,va];
//println([i,j,s]);
}
}
return dm;
}
var spanningTree(var dm, var triangles)
{
var links = [];
var undone = [];
for(int i=1;i<dm.length;i++){
undone.push(i);
}
var done = [0,];
fill(#00ff00);
//first node is always 0
while ( undone.length > 0 ){
int imax = 0;
int kmax = 0;
int vmax = 1.;
//println(["done",done]);
//println(["undone",undone]);
for(int ki=0;ki<done.length;ki++){
var i = done[ki];
for(int k=0;k<undone.length;k++){
var j = undone[k];
//println(["test",i,j,dm[i][j]]);
if ( dm[i][j][0] < vmax ){
imax = ki;
kmax = k;
vmax = dm[i][j][0]; // innerproduct
}
}
}
var i = done[imax];
var j = undone[kmax];
links.push([i,j,dm[i][j][1],dm[i][j][2]]);//neighboring faces and shared vertices
//println(["Nearest",i,j,dm[i][j]]);
/*
var v0 = triangles[i][3];//normal vector
vat v1 = triangles[j][3];//normal vector
drawLine(v0,v1);
*/
done.push(j);
undone.splice(kmax,1);
}
return links;
}
var norm2(var v){
float s = 0.0;
for(int dim=0; dim<2; dim++){
s += v[dim]*v[dim];
}
return sqrt(s);
}
//determine the position of the third vertex of the triangle.
//vertices are counter-clockwise
//va and vb are 2D vectors.
void thirdvertex(var va, var vb, var Lbc, var Lac)
{
var vab = [vb[0] - va[0], vb[1] - va[1]];
var Lab = norm2(vab);
var vlong = [vab[0]/Lab, vab[1]/Lab];
var Llong = (Lab*Lab + Lac*Lac - Lbc*Lbc) / (2*Lab);
var vlat = [vlong[1], -vlong[0]];
var Llat = sqrt( Lac*Lac - Llong*Llong );
return [ va[0] + Llong * vlong[0] + Llat * vlat[0],
va[1] + Llong * vlong[1] + Llat * vlat[1] ];
}
//distances between three vertices on the sphere
var edgelength(v0,v1,v2)
{
return [norm([v0[0]-v1[0], v0[1]-v1[1], v0[2]-v1[2]]),
norm([v1[0]-v2[0], v1[1]-v2[1], v1[2]-v2[2]]),
norm([v2[0]-v0[0], v2[1]-v0[1], v2[2]-v0[2]])];
}
void develop(var vertices, var triangles, var links)
{
fill(#ff0000);
textAlign(RIGHT);
text("Development",width-2,width/2+10);
var tri0 = links[0][0];
var L = edgelength(vertices.get(triangles[tri0][0]),
vertices.get(triangles[tri0][1]),
vertices.get(triangles[tri0][2]));
var v0 = [0.0, 0.0];
var v1 = [0.0, L[0]];
var v2 = thirdvertex(v0,v1,L[1],L[2]);
var vv =
triangles[tri0][4] = new HashMap();
triangles[tri0][4].put(triangles[tri0][0],v0);
triangles[tri0][4].put(triangles[tri0][1],v1);
triangles[tri0][4].put(triangles[tri0][2],v2);
var com = [v2[0], (v1[1]+v2[1])];
for(var i=0;i<links.length;i++){
var tri0 = links[i][0];
var tri1 = links[i][1];
var sv1 = links[i][2];//shared vertices
var sv0 = links[i][3];
var uv2 = triangles[tri1][0] + triangles[tri1][1] + triangles[tri1][2] - sv0 - sv1; // unshaed vertex of tri1
//println(["linkage",tri0,tri1,sv0,sv1,uv2,triangles[tri1][0],triangles[tri1][1],triangles[tri1][2]]);
var L = edgelength(vertices.get(sv0),
vertices.get(sv1),
vertices.get(uv2));
v0 = triangles[tri0][4].get(sv0);
v1 = triangles[tri0][4].get(sv1);
v2 = thirdvertex(v0,v1,L[1],L[2]);
//println([v0,v1,v2]);
triangles[tri1][4] = new HashMap();
triangles[tri1][4].put(sv0,v0);
triangles[tri1][4].put(sv1,v1);
triangles[tri1][4].put(uv2,v2);
com[0] += v0[0] + v1[0] + v2[0];
com[1] += v0[1] + v1[1] + v2[1];
}
com[0] /= (3*triangles.length);
com[1] /= (3*triangles.length);
var zoom = width/4;
fill(255);
for(int k=0;k<triangles.length;k++){
beginShape();
Iterator i = triangles[k][4].entrySet().iterator(); // Get an iterator
while (i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
vtx = me.getValue();
vertex((vtx[0]-com[0])*zoom/3+zoom*3,(vtx[1]-com[1])*zoom/3+zoom*3);
}
endShape(CLOSE);
}
}
void draw() { // this is run repeatedly.
if ( updated ){
background(255);
fill(200);
rect(0,width/2,width,height-width/2);
updated = 0;
interactive_panel(vertices, triangles);
preview_panel(vertices, triangles);
var dm = distanceMatrix(vertices, triangles);
var links = spanningTree(dm, triangles);
develop(vertices, triangles, links);
}
}