Phaetos
10-13-2005, 03:45 AM
Hi!
I have a program that creates a BSP tree from a file that contains level data. When creating the tree the program uses heuristics to choose a "good" splitting face. So far so good - I get a working and correct tree, but while creating my program finds a few "situations" like this:
A triangle (A,B,C) has 1 Point behind the splitting plane and 2 points in front of it. The programm classifies this face as one to be splitted. When it now comes to the actual calculation of the intersection point there is only 1 intersection found!
Example: A,B in front and C behind the plane. (This is determined by the scalar product: May p be a point in the plane and n its normal vector, a point x is in front of this plane if (x-p)*n >= 0)
When I then calculate the actual intersection point I find only 1 intersection (which is impossible, isn't it?). Spoken in this example: My intersection finds that A-C intersects the plane, but B-C does not! (but B was in front, and C was behind the plane as just determined by scalar product)
To calculate the intersection I use:
plane: (x-p)n=0
line: x=p1 + lambda(p2-p1)
=> lambda = ((x-p)n-p1) / (p2-p1)
If lambda>=0 and lambda<=1 the line intersects the plane at p1 + lambda * (p2-p1)
If you like I can post source extractions, too (its quite short).
I suppose my problem has something to do with numerical robustness, but I don't see the problem...
Thank you in advance!
Stefan
I have a program that creates a BSP tree from a file that contains level data. When creating the tree the program uses heuristics to choose a "good" splitting face. So far so good - I get a working and correct tree, but while creating my program finds a few "situations" like this:
A triangle (A,B,C) has 1 Point behind the splitting plane and 2 points in front of it. The programm classifies this face as one to be splitted. When it now comes to the actual calculation of the intersection point there is only 1 intersection found!
Example: A,B in front and C behind the plane. (This is determined by the scalar product: May p be a point in the plane and n its normal vector, a point x is in front of this plane if (x-p)*n >= 0)
When I then calculate the actual intersection point I find only 1 intersection (which is impossible, isn't it?). Spoken in this example: My intersection finds that A-C intersects the plane, but B-C does not! (but B was in front, and C was behind the plane as just determined by scalar product)
To calculate the intersection I use:
plane: (x-p)n=0
line: x=p1 + lambda(p2-p1)
=> lambda = ((x-p)n-p1) / (p2-p1)
If lambda>=0 and lambda<=1 the line intersects the plane at p1 + lambda * (p2-p1)
If you like I can post source extractions, too (its quite short).
I suppose my problem has something to do with numerical robustness, but I don't see the problem...
Thank you in advance!
Stefan