White Morph wrote:
Hi Kelvin,
Thank you for the reply. Theoretically, my algorithm is correct, right? If
the vector is not between 2 edge vector, the dot produce should be -1,
otherwise, it should be 1. I don't know why the 2 other cases don't get
value close to 1 or -1.
As mention in previous mail it is because after
v1.cross(v1, v2);
v3.cross(v2, v3);
one of v1 and v3 is close to zero in the 2 other cases
so normalization fail and can't produce result 1 or -1.
I would change this :
eps = v1.dot(v3);
System.out.println("eps = " + eps);
if (eps < 0 && (eps + TOL) < 0) <===== reductant SAME as
(eps < -TOL)
return true;
to
eps = v1.dot(v3);
System.out.println("eps = " + eps);
if ((eps > -1 - TOL) && (eps < -1 + TOL))
return true
if ((eps > 1 + TOL) || (eps < 1 - TOL)) {
System.out.println("This algorithm fail !!");
exit(1);
}
Note that in the next v1.3.1 beta release
4712222 - PickRay computation is not numerically stable
is fixed by re-implement point in triangle test for PickResult
and the core using Solution 3 of
http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly
which is more robust.
So when beta release please check out the utility source code
of PickResult.
The good thing about utility that you can freely modify and
suit your need such as handle this kind of corner case which
Java3D may not handle quite well.
- Kelvin
----------------
Java 3D Team
Sun Microsystems Inc.
Since we found the vector (V1) of the intersected point to Vertex 0 is between its 2 edge vectors, because its dot produce is 1. So I change my code to calculate the intersection between the vectors V1 and V2(Vertex1 to Vertex2) and then I compute the proportional factor to see if it is between 0 and 1. my test shows it's 1, so it is on the edge of Vertex1 and Vertex2,
and my conclusion is still that: the intersected point is inside the triangle.
Could you check this for me? Thanks much.
The code to test if the point is inside a triangle:
private boolean isOutofTriangle() {
if (isOnPlane()) {
Vector3d v1 = new Vector3d();
Vector3d v2 = new Vector3d();
Vector3d v3 = new Vector3d();
v1.sub(primitiveCoordinatesVW[1], primitiveCoordinatesVW[0]);
v2.sub(pointCoordinatesVW, primitiveCoordinatesVW[0]);
v3.sub(primitiveCoordinatesVW[2], primitiveCoordinatesVW[0]);
v1.normalize(); v2.normalize(); v3.normalize();
v1.cross(v1, v2);
v3.cross(v2, v3);
v1.normalize(); v3.normalize();
double eps;
eps = v1.dot(v3);
System.out.println("eps = " + eps);
if (eps < 0 && (eps + TOL) < 0)
return true;
v1.sub(primitiveCoordinatesVW[2], primitiveCoordinatesVW[1]);
v1.normalize();
double a1 = (v1.y*primitiveCoordinatesVW[1].x - v1.x*primitiveCoordinatesVW[1].y) -
(v1.y*primitiveCoordinatesVW[0].x - v1.x*primitiveCoordinatesVW[0].y);
double b1 = (v2.x*v1.y - v2.y*v1.x);
double k = a1/b1;
double x, y, z;
x = v2.x*k + primitiveCoordinatesVW[0].x;
y = v2.y*k + primitiveCoordinatesVW[0].y;
z = v2.z*k + primitiveCoordinatesVW[0].z;
double t1 = (pointCoordinatesVW.x - primitiveCoordinatesVW[0].x)/
(x - primitiveCoordinatesVW[0].x);
double t2= (pointCoordinatesVW.y - primitiveCoordinatesVW[0].y)/
(y - primitiveCoordinatesVW[0].y);
double t3 = (pointCoordinatesVW.z - primitiveCoordinatesVW[0].z)/
(z - primitiveCoordinatesVW[0].z);
if (t1 < 0 && (t1 + TOL) < 0)
return true;
if (t1 > 1 && (t1 - TOL) > 1)
return true;
return false;
}
return true;
}
More info. on this...
In the test for same vectors, given
v1, v2, v3 are coplanar vectors it uses 3 check
with each one similar to the following,
v1.cross(v1, v2);
v2.cross(v2, v3);
double eps = v1.dot(v2);
if (eps < 0 && (eps + TOL) < 0)
return true;
to return true when point out of triangle.
(i) There is a missing v1.normalize() and v2.normalize() after computing
the cross product.
(ii) The test
if (eps < 0 && (eps + TOL) < 0)
is same as
if (eps < 0 && (eps < - 1.0e-5)
which is equal to
if (eps < -1.0e-5)
Theoretically, eps return is either 1 or -1 (after v1, v2 normalize in
step 1) given the 3 input vectors are coplaner.
So the checking is not correct.
In this particular examples, I got
0.9999999999999998
0.2636325256261517
0.2622153128979992
In the other two cases it doesn't return a value close
to 1 or -1 as expected. A close look show that in the last
two case on of the vector is ~ 0 so normalization fail.
As a result the algorithm is not robust numerically.
- Kelvin
----------------
Java 3D Tam
Sun Microsystems Inc.
Kelvin Chung wrote:
Hi White,
The algorithm isOutofTriangle() you use is not quite correct.
A ------------ B
\ /
\ /
\ /
\ / x D
\ /
\ /
C
It will report D inside triangle if A,B,C,D are coplanar.
Since it computes the vector ADxAB which is perpendicular to the
plane ABC, then computes the vector ACXAB which is also
perpendicular to the plane. The dot produce of them is zero
and the algoirthm return true which is not correct.
The utility in the case throw RuntimException
Interp point outside triangle
as expected.
- Kelvin
-------------
Java 3D Team
Sun Microsystems Inc.
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
===========================================================================
To unsubscribe, send email to [EMAIL PROTECTED] and include in the body
of the message "signoff JAVA3D-INTEREST". For general help, send email to
[EMAIL PROTECTED] and include in the body of the message "help".
