Skip to content

Instantly share code, notes, and snippets.

@blueforesticarus

blueforesticarus/intersection.html

Last active October 23, 2015 20:16
Show Gist options
  • Save blueforesticarus/a3eea494ef26d4d1616f to your computer and use it in GitHub Desktop.
Save blueforesticarus/a3eea494ef26d4d1616f to your computer and use it in GitHub Desktop.
Download ZIP
Creates two three.js geometries and highlights all the intersections between them.
Raw
intersection.html
<!DOCTYPE html>
<html lang="en">
<head>
<title>three.js webgl - geometry - cube</title>
<meta charset="utf-8">
<style>
body {
margin: 0px;
background-color: #000000;
overflow: hidden;
}
</style>
</head>
<body>
<script src="three.min.js"></script>
<script src="FlyControls.js"></script>
<script src="CurveExtras.js"></script>
<script>
var camera, scene, renderer;
var mesh;
// scene size
var WIDTH = window.innerWidth;
var HEIGHT = window.innerHeight;
// camera
var VIEW_ANGLE = 45;
var ASPECT = WIDTH / HEIGHT;
var NEAR = 1;
var FAR = 50000;
var time = 0;
function init() {
renderer = new THREE.WebGLRenderer();
renderer.setSize( window.innerWidth, window.innerHeight );
renderer.setClearColor( 0x333333, 1 );
document.body.appendChild( renderer.domElement );
// camera
camera = new THREE.PerspectiveCamera(VIEW_ANGLE, ASPECT, NEAR, FAR);
camera.position.set( 0,10000,0);
camera.rotation.x = -Math.PI/2;
cameraControls = new THREE.FlyControls( camera );
cameraControls.movementSpeed = 5000;
cameraControls.domElement = renderer.domElement;
cameraControls.rollSpeed = Math.PI / 3;
cameraControls.autoForward = false;
cameraControls.dragToLook = false;
scene = new THREE.Scene();
var directionalLight = new THREE.DirectionalLight( 0xffffff, .7 );
directionalLight.position.set( 0, .1, .1 );
scene.add( directionalLight );
var directionalLight = new THREE.DirectionalLight( 0xffffff, .4 );
directionalLight.position.set( 0, -10, 0 );
scene.add( directionalLight );
var light = new THREE.AmbientLight( 0x333333 ); // soft white light
scene.add( light );
window.addEventListener( 'resize', onWindowResize, false );
}
function onWindowResize() {
camera.aspect = window.innerWidth / window.innerHeight;
camera.updateProjectionMatrix();
renderer.setSize( window.innerWidth, window.innerHeight );
}
function animate() {
time+=1/60;
requestAnimationFrame( animate );
cameraControls.update( 1/60);
renderer.render( scene, camera );
}
function C(max, min){
return R(max,min,true)*R(max,min,true)*R(max,min,true);
}
function R(max, min, step){
var r = Math.random() * (max-min) + min;
if(step){
r = Math.floor(r);
}
return r;
}
function S(t, f, max, min, s){
return ( (s?-1:1) * Math.sin(t*f) + 1) * (max-min)/2 + min;
}
function Path(){
sphere = new THREE.SphereGeometry(4000,20,20);
sphere.mergeVertices();
sphere.vertices.forEach(function (v){v.multiplyScalar(R(1.1,.9))});
sphere.computeFaceNormals();
sphere.computeVertexNormals();
var geometry = new THREE.TubeGeometry(new THREE.Curves.DecoratedTorusKnot5c(), 300, 2, 4, true);
trans = new THREE.Matrix4();
trans.makeRotationX(Math.PI/2);
trans.scale(new THREE.Vector3(150,150,150));
geometry.applyMatrix(trans);
/*
//uncomment for a simpler test geometry
var sphere = new THREE.BoxGeometry(1000,1000,1000);
var geometry = new THREE.CylinderGeometry( 500,0,2000,8 );
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
geometry.faces.pop();
*/
//delimit(geometry,3600,4300);
intersect(geometry, sphere);
var mesh = THREE.SceneUtils.createMultiMaterialObject( sphere, [
new THREE.MeshLambertMaterial({
color: C(200,250),
side:THREE.DoubleSide,
transparent:true,
opacity: .7
}),
new THREE.MeshBasicMaterial({
color: 0x000000,
opacity: 0.3,
wireframe: true,
transparent: true
})]);
scene.add(mesh);
tubeMesh = THREE.SceneUtils.createMultiMaterialObject( geometry, [
new THREE.MeshLambertMaterial({
color: C(200,250),
side:THREE.DoubleSide,
shading: THREE.FlatShading,
transparent:true,
opacity: .7
}),
new THREE.MeshBasicMaterial({
color: 0x000000,
opacity: 0.3,
wireframe: true,
transparent: true
})]);
scene.add(tubeMesh);
}
//takes two geometries and finds intersections
function intersect(gM,gN){
var faces = [];
for(var iM = 0 ; iM < gM.faces.length ; iM++){
for(var iN = 0 ; iN < gN.faces.length ; iN++){
if(canIntersect(gM,iM,gN,iN) && doesIntersect(gM, iM, gN, iN) && faces.indexOf(iN) == -1){
faces.push(iN);
}
}
}
for(var i = 0 ; i<faces.length ; i++){
faces[i] = gN.faces[faces[i]];
}
console.log(faces.length + "/" + gN.faces.length);
//gN.faces = faces;
}
function doesIntersect(g1, i1, g2, i2){
//get triangles from geometries
t1 = {
a: g1.vertices[g1.faces[i1].a],
b: g1.vertices[g1.faces[i1].b],
c: g1.vertices[g1.faces[i1].c],
ia: g1.faces[i1].a,
ib: g1.faces[i1].b,
ic: g1.faces[i1].c,
i: i1 };
t2 = {
a: g2.vertices[g2.faces[i2].a],
b: g2.vertices[g2.faces[i2].b],
c: g2.vertices[g2.faces[i2].c],
ia: g2.faces[i2].a,
ib: g2.faces[i2].b,
ic: g2.faces[i2].c,
i: i2 };
//first planes from triangles ([a,b,c,d] for ax+by+cz=d)
p1 = getPlane(t1.a,t1.b,t1.c);
p2 = getPlane(t2.a,t2.b,t2.c);
//get some itercepts
ab_p1 = intercept(p1.a, p1.b, p1.c, p1.d, t2.a, t2.b);
ac_p1 = intercept(p1.a, p1.b, p1.c, p1.d, t2.a, t2.c);
bc_p1 = intercept(p1.a, p1.b, p1.c, p1.d, t2.b, t2.c);
ab_p2 = intercept(p2.a, p2.b, p2.c, p2.d, t1.a, t1.b);
ac_p2 = intercept(p2.a, p2.b, p2.c, p2.d, t1.a, t1.c);
bc_p2 = intercept(p2.a, p2.b, p2.c, p2.d, t1.b, t1.c);
//detect if parallel + system check
if(!ab_p1.ex && !ac_p1.ex && !bc_p1.ex){
if(!ab_p2.ex && !ac_p2.ex && !bc_p2.ex){
console.log("triangles parallel");
}else{
console.warn("something went wrong, inconsistant intersection");
}
}
//process intersections 1
if(ab_p1.in && ac_p1.in && bc_p1.in){
console.warn("something went wrong, cannot be three intersections");
return false;
} else if((!ab_p1.in && !ac_p1.in && !bc_p1.in) || (!ab_p2.in && !ac_p2.in && !bc_p2.in)){
console.log("triangles do not intersect");
return false;
}
i1 = ab_p1.in ? (ac_p1.in ? {m: ab_p1, n: ac_p1} : {m: ab_p1, n: bc_p1} ) : {m: ac_p1, n: bc_p1};
if(!i1.m || !i1.n){
console.warn("something went wrong, cannot be only one intersection");
return false;
}
//process intersections 2
if(ab_p2.in && ac_p2.in && bc_p2.in){
console.warn("something went wrong, cannot be three intersections");
return false;
} else if((!ab_p2.in && !ac_p2.in && !bc_p2.in) || (!ab_p2.in && !ac_p2.in && !bc_p2.in)){
console.log("triangles do not intersect 2");
return false;
}
i2 = ab_p2.in ? (ac_p2.in ? {m: ab_p2, n: ac_p2} : {m: ab_p2, n: bc_p2} ) : {m: ac_p2, n: bc_p2};
if(!i2.m || !i2.n){
console.warn("something went wrong, cannot be only one intersection");
return false;
}
//get intersection of intersections
//assume i2 and i1 are co-linear
//determine which value to test
if(!equals(i1.m.x , i2.n.x)){
i1.m.v = i1.m.x;
i1.n.v = i1.n.x;
i2.m.v = i2.m.x;
i2.n.v = i2.n.x;
}else if(!equals(i1.m.y , i2.n.y)){
i1.m.v = i1.m.y;
i1.n.v = i1.n.y;
i2.m.v = i2.m.y;
i2.n.v = i2.n.y;
}else if(!equals(i1.m.z , i2.n.z)){
i1.m.v = i1.m.z;
i1.n.v = i1.n.z;
i2.m.v = i2.m.z;
i2.n.v = i2.n.z;
}else{
//intercept of length zero
return false;
}
//determine which is max, which is min
i1.max = i1.m.v > i1.n.v ? i1.m : i1.n;
i1.min = i1.m.v < i1.n.v ? i1.m : i1.n;
i2.max = i2.m.v > i2.n.v ? i2.m : i2.n;
i2.min = i2.m.v < i2.n.v ? i2.m : i2.n;
var inner;
//no intersection if lines are disconnected
if(i1.max.v <= i2.min.v || i2.max.v <= i1.min.v ){
return false;
}
//handle four possible layouts
if(i1.min.v < i2.min.v && i2.max.v < i1.max.v){
//if i2 is fully within i1
inner = {a:i2.min,b:i2.max};
}else if(i2.min.v < i1.min.v && i1.max.v < i2.max.v){
//if i1 is fully within i2
inner = {a:i1.min,b:i1.max};
}else if(i2.min.v < i1.min.v && i2.max.v < i1.max.v){
//i1 and i2 over lap
inner = {a:i1.min,b:i2.max};
}else if(i1.min.v < i2.min.v && i1.max.v < i2.max.v){
//i1 and i2 over lap
inner = {a:i2.min,b:i1.max};
}else{
console.log("something is wrong");
return false;
}
var geometry = new THREE.Geometry();
geometry.vertices.push(inner.a, inner.b);
var line = new THREE.Line( geometry, new THREE.LineBasicMaterial({
color: 0x00ff00,
linewidth:7
}));
scene.add( line );
return inner;
}
function equals(a,b,e){
if(!e){
e = .0000000001
}
return Math.abs(a-b) < e;
}
function printtt(a,p1){
console.log(a.x * p1.a + a.y * p1.b + a.z * p1.c - p1.d);
}
function intercept (a,b,c,d,p1,p2){
var bottom = (a*(p2.x-p1.x) + b*(p2.y-p1.y) + c*(p2.z-p1.z));
if(equals(bottom,0)){
return {ex:false, in:false};
}
var t = (d - a*p1.x - b*p1.y - c*p1.z) / bottom;
return {
x: (p2.x-p1.x)*t + p1.x,
y: (p2.y-p1.y)*t + p1.y,
z: (p2.z-p1.z)*t + p1.z,
in: (t >= 0 && t<=1),
ex: true,
t:t
};
}
function getPlane(a,b,c){
//get the vectors from a to b and a to c
var ab = {
x: b.x-a.x,
y: b.y-a.y,
z: b.z-a.z
};
var ac = {
x: c.x-a.x,
y: c.y-a.y,
z: c.z-a.z
};
//the normal vector is the cross product
var n = {
x: ab.y*ac.z - ab.z*ac.y,
y: ab.z*ac.x - ab.x*ac.z,
z: ab.x*ac.y - ab.y*ac.x
}
//normal vector components are preportional to plane coefficients
//use this along with an origional point to calculate "d" (Ax + By + Cz = D)
var d = n.x*c.x + n.y*c.y + n.z*c.z;
var p1 ={a:n.x, b:n.y, c: n.z, d:d};
//console.log(n);
//console.log(d);
return p1;
}
function canIntersect(gM, iM, gN, iN){
var stats = {M:{},N:{}};
stats.M.x = faceStat(gM,iM,"x");
stats.N.x = faceStat(gN,iN,"x");
if(stats.M.x.max < stats.N.x.min || stats.N.x.max < stats.M.x.min){
//console.log("x too far");
return false;
}
stats.M.y = faceStat(gM,iM,"y");
stats.N.y = faceStat(gN,iN,"y");
if(stats.M.y.max < stats.N.y.min || stats.N.y.max < stats.M.y.min){
//console.log("y too far");
return false;
}
stats.M.z = faceStat(gM,iM,"z");
stats.N.z = faceStat(gN,iN,"z");
if(stats.M.z.max < stats.N.z.min || stats.N.z.max < stats.M.z.min){
//console.log("z too far");
return false;
}
return true;
}
function faceStat(geometry, index, value){
var face = geometry.faces[index];
return stat([geometry.vertices[face.a],geometry.vertices[face.b],geometry.vertices[face.c]], value)
}
function stat(objects, value){
var max = objects[0][value];
var min = objects[0][value];
for(var i = 1 ; i < objects.length ; i++){
if(objects[i][value] < min){
min = objects[i][value];
}
else if(objects[i][value] > max){
max = objects[i][value];
}
}
return {max: max, min:min};
}
function delimit(g,min ,max){
console.log(g);
var minSq = min * min;
var maxSq = max * max;
for(var i =0; i< g.faces.length ; i++){
var face = g.faces[i];
if(g.vertices[face.a].lengthSq() < minSq &&
g.vertices[face.b].lengthSq() < minSq &&
g.vertices[face.c].lengthSq() < minSq){
g.faces[i] = 0;
}else if(g.vertices[face.a].lengthSq() > maxSq &&
g.vertices[face.b].lengthSq() > maxSq &&
g.vertices[face.c].lengthSq() > maxSq){
g.faces[i] = -1;
}
}
var faces = []
for(var i =0; i< g.faces.length ; i++){
if(g.faces[i] != 0 && g.faces[i] != -1){
faces.push(g.faces[i]);
}
}
g.faces = faces;
g.computeFaceNormals();
g.computeVertexNormals();
}
init();
Path();
animate();
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment