2 replies to this topic

[Phaetos]

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

[anubis]

Well, if you look at these situations are the points in question very close to the splitting plane ? If they are, numerical stability is likely an issue.

[Phaetos]

Hi!

Here I am again...

Yes, it was a problem regarding the precision of double values. I changed my source to only use ONE method to determine the side a vertex is on a plane. And then, when I calculate the intersection point, I don't check at all whether lambda lies between 0.0 and 1.0, because it has to.

Okay, BSP generation is finished now... lets move on to frustum culling and drawing of the world...

Thanks!
Stefan