Re: [Algorithms] more plane-poly clipping woes

[Charles B. <cb...@cb...>]

Yep, as Angel has wisely directed me, it was actually just
precision problems I was having.  Let me write up my
understanding on the situation to make sure I'm grasping
what's going on :  

Precision is a big problem in games and 3d in general, because
we have a really pathological case : we have small, detailed
models in 3d, whose vertices are very close together.  On the
other hand, those models sit in very large worlds where you can
have models that are very far apart.  This gives you a big
range in coordinates.

For example, imagine you want the distance between two points
in a model.  If I take those points in model space, v1m and v2m,
then I get a distance

dm = | v1m - v2m |

But what if I instead transform them to world-space first, and
then do the distance.  If my transform is just a translation by w
I get :

dw = | (v1m+w) - (v2m+w) |

Now if dm is very small, and w is very large (which are both
typical in games) then my distance dw is horribly inaccurate.
Floats only have 24 bits of mantissa precision, which you can
use up fast.  Imagine a human on a landscape.  Important verts
on the human model may only be 1 cm apart.  The landscape could
be 10 km square.  The difference is 1 million, or 20 bits, and
suddenly I'm doing math in 4 bits of precision!

You can avoid these precision nightmares most of the time by
never going to world-space.  That is, light in model space, render
using a direction model-to-view transform, etc.  Also, collision
testing between two models should take one model to the space of
another, instead of taking them both into world space.

Unfortunately, this problem cannot be avoided for whole-world
spatial structures like a BSP.  You must take all your models into
world-space when you put their polys in the BSP, since the BSP must
all be in one common space.

The only way to save yourself from nightmares is to make sure your
epsilon is big enough to consistently hide all precision problems.
The epsilon, or plane thickness, is not really fixing your precision
problems, it's just catching them in a consistent way (eg. treating
segments that are too small to handle as just points, and such).
If you have 24 bits of float precision, then you must take your
whole-world size and divide by around 256k (18 bits, leaving 6 for
accuracy), and use that as your epsilon.  This puts a pretty hard
clamp on the size and detail of the world that can be modeled in
floats - a roughly 1 km square area is all you get, if you want
accuracy on the order of human fingers.

At 11:08 AM 9/21/2000 +0200, Angel Popov wrote:
>If I understood you correctly - the newly created split vertex
>does not lie within +/-EPSILON distance from the plane
>that generated it. There are tree reasonable ways to handle
>this:
>1. Increase EPSILON. It MUST be big enough to handle such
>precision errors.
>2. Increase your FP precision by using doubles.
>3. Split polygons with very long edges to smaller polygons.
>I am quite certain that you get such inconsistencies only
>when splitting long edges.

--------------------------------------
Charles Bloom           www.cbloom.com