how to find where a line's crossing a box

Programming Questions

bluurryy

how to find where a line's crossing a box

in Programming Questions • 3 years ago

I'm programming a little 3d-software and have got lines there. I want them to be shown as long as the points are in a "virtual" box. So I can find the intersection points of the line and this box. (6 planes) this is no problem and I can display these points. But there's the problem that the lines have more than two intersection points, so you can't say which are the "true" ones. I 'm looking for these points that really are intersection points of this box and not with the whole plane..

so is there an easy idea? I solved the problem of finding the points (easily) with the coordinate equation but now I'm stuck..

thanks for your answers..

Replies(7)

ignivome

Re: how to find where a line's crossing a box

3 years ago

maybe this could help
You'll need toxiclibscore (a library)

kooogy

Re: how to find where a line's crossing a box

3 years ago

don't you have to clip to ALL planes anyway?

if you clip to front and then to left and then to top (say) then you'll end up with the correct point. and that's true whichever order you do it in.

cohen-sutherland is the 2d version of this, and it expands into 3d easily enough.

bluurryy

Re: Re: how to find where a line's crossing a box

3 years ago

could you explain this a little bit "better"..?

so I have for example 3 points where a line crosses the planes.. so I have to chose two of them to draw a line between them..

I can't take all this three points? or not?

ignivome

Re: Re: how to find where a line's crossing a box

3 years ago

1 strait line cross 3 points in a plane ... looks pretty impossible :)
anyways, look there

kooogy

Re: Re: how to find where a line's crossing a box

3 years ago

> could you explain this a little bit "better"..?

doubtful 8)

taking the diagram on that cohen-sutherland page, the tic tac toe grid...

if you have a line that starts in the middle of the 0001 and ends at the middle of the 1010 box then it crosses both the top line and the right line. clip it using the right line and you now have a line starts in 0001 and ends at the left hand side of the 1010 box. THEN you have to clip THAT line using the top to end up with the correct endpoint, which is what i mean by having to clip everywhere. (if, however, you clip against the top first then there's no need to clip to the right as the resultant line no longer intersects it. but you don't know this until you've done the test).

as for what's inside and what's outside, C-S handles that. it's a dot product thing.

(i vaguely remember doing C-S clipping at university, but that was 22 years ago...)

> 1 strait line cross 3 points in a plane ... looks pretty impossible :)

there are 6 planes, 6 intersections. but that's ok. C-S will quickly let you discard cases that are wholly outside and make it obvious which planes you need to clip to.

kooogy

Re: how to find where a line's crossing a box

3 years ago

// 3D Cohen-Sutherland
// acd (c)2010
import peasy.*;
static int SIZE = 100;
PeasyCam cam;
PVector a, b;
PVector ca, cb; // clipped points
int abits, bbits;
static int U = 0x0000001; // up
static int D = 0x0000010; // down
static int L = 0x0000100; // left
static int R = 0x0001000; // right
static int F = 0x0010000; // front
static int B = 0x0100000; // back
void setup() {
size(400, 400, P3D);
cam = new PeasyCam(this, 500);
calc();
}
// whether this is outside and in which direction
int categorise(PVector p) {
int v = 0; // value
if (p.x > SIZE) {
v |= U;
}
if (p.x < -SIZE) {
v |= D;
}
if (p.y > SIZE) {
v |= L;
}
if (p.y < -SIZE) {
v |= R;
}
if (p.z > SIZE) {
v |= F;
}
if (p.z < -SIZE) {
v |= B;
}
return v;
}
void calc() {
// random line ends
a = new PVector();
a.x = random(-SIZE * 2, SIZE * 2);
a.y = random(-SIZE * 2, SIZE * 2);
a.z = random(-SIZE * 2, SIZE * 2);
b = new PVector();
b.x = random(-SIZE * 2, SIZE * 2);
b.y = random(-SIZE * 2, SIZE * 2);
b.z = random(-SIZE * 2, SIZE * 2);
// categorise endpoints
abits = categorise(a);
bbits = categorise(b);
println("A: " + binary(abits, 6));
println("B: " + binary(bbits, 6));
// clip
ca = new PVector(a.x, a.y, a.z);
cb = new PVector(b.x, b.y, b.z);
while (true) {
if (abits == 0 && bbits == 0) {
// both inside - done
println("Both inside");
break;
} else if ((abits & bbits) != 0) {
// both outside (in same direction) - reject
ca = null;
cb = null;
println("Both outside");
break;
} else {
PVector t = new PVector(); // tmp
float ratio;
// something needs clipping
// use a if it's a, b if it's b
int codeout = (abits != 0) ? abits : bbits;
if (codeout == abits) {
println("Clipping Point A");
} else {
println("Clipping Point B");
}
if ((codeout & U) != 0) {
println("Clipping U");
ratio = (SIZE - ca.x) / (cb.x - ca.x);
t.x = SIZE;
t.y = lerp(ca.y, cb.y, ratio);
t.z = lerp(ca.z, cb.z, ratio);
} else if ((codeout & D) != 0) {
println("Clipping D");
ratio = (-SIZE - ca.x) / (cb.x - ca.x);
t.x = -SIZE;
t.y = lerp(ca.y, cb.y, ratio);
t.z = lerp(ca.z, cb.z, ratio);
} else if ((codeout & L) != 0) {
println("Clipping L");
ratio = (SIZE - ca.y) / (cb.y - ca.y);
t.x = lerp(ca.x, cb.x, ratio);
t.y = SIZE;
t.z = lerp(ca.z, cb.z, ratio);
} else if ((codeout & R) != 0) {
println("Clipping R");
ratio = (-SIZE - ca.y) / (cb.y - ca.y);
t.x = lerp(ca.x, cb.x, ratio);
t.y = -SIZE;
t.z = lerp(ca.z, cb.z, ratio);
} else if ((codeout & F) != 0) {
println("Clipping F");
ratio = (SIZE - ca.z) / (cb.z - ca.z);
t.x = lerp(ca.x, cb.x, ratio);
t.y = lerp(ca.y, cb.y, ratio);
t.z = SIZE;
} else if ((codeout & B) != 0) {
println("Clipping B");
ratio = (-SIZE - ca.z) / (cb.z - ca.z);
t.x = lerp(ca.x, cb.x, ratio);
t.y = lerp(ca.y, cb.y, ratio);
t.z = -SIZE;
}
// do the other point, if necessary
if (codeout == abits) {
ca.x = t.x;
ca.y = t.y;
ca.z = t.z;
abits = categorise(ca);
} else {
cb.x = t.x;
cb.y = t.y;
cb.z = t.z;
bbits = categorise(cb);
}
}
}
}
void draw() {
background(255);
// clipping box (black)
stroke(0);
fill(128, 128, 128, 128);
box(SIZE * 2, SIZE * 2, SIZE * 2);
// complete line (green)
stroke(0, 255, 0);
line(a.x, a.y, a.z, b.x, b.y, b.z);
// endpoints (red and blue)
noStroke();
fill(255, 0, 0);
pushMatrix();
translate(a.x, a.y, a.z);
sphere(5);
popMatrix();
fill(0, 0, 255);
pushMatrix();
translate(b.x, b.y, b.z);
sphere(5);
popMatrix();
// clipped line (if exists) (thick black)
if (ca != null) {
strokeWeight(4);
stroke(0);
line(ca.x, ca.y, ca.z, cb.x, cb.y, cb.z);
strokeWeight(1);
}
}
void keyPressed() {
calc();
}

needs PeasyCam library. press a key to change the line.

kooogy

Re: Re: how to find where a line's crossing a box

3 years ago

applet version uploaded to openprocessing.org here:

http://openprocessing.org/visuals/?visualID=12028

Top Reply