View Issue Details

IDProjectCategoryView StatusLast Update
0004853The Dark ModPhysicspublic30.06.2018 09:10
ReporterstgatilovAssigned Tostgatilov 
PrioritynormalSeveritymajorReproducibilitysometimes
Status resolvedResolutionfixed 
Product VersionTDM 2.06 
Target VersionTDM 2.07Fixed in VersionTDM 2.07 
Summary0004853: Player gets stuck on edge between two slanted polygons (Volta2)
DescriptionWhen player moves on the high edge with two adjacent slanted surfaces, he often gets stuck on this edge.
A lot of such issues happen in Volta 2 FM. In 2.05, the problems do not appear, but in 2.06 there are a lot of them.
Steps To Reproduce1. Start "Volta 2: Cauldron of the Gods" FM.
2. Teleport somehow to (11280 -5664 -6108), also shown here:
  http://forums.thedarkmod.com/topic/19510-cauldron-clipping-issues/page-2#entry423832
3. Move over the edge repeateadly.

At some moment you get stuck (rather fast) and can only get away via mantling or noclipping
Additional InformationForum discussion here:
  http://forums.thedarkmod.com/topic/19510-cauldron-clipping-issues/
(note: great read there)
Tagsprecision

Relationships

related to 0004435 closedduzenko Investigate fp-precision related issues 

Activities

stgatilov

stgatilov

27.06.2018 17:37

developer   ~0010591

Last edited: 28.06.2018 03:57

View 2 revisions

Now the fun facts.

If I take 32-bit version and disable SSE2 floating point math (/arch:IA32), then the issue does not happen.

EDIT: "The issue happens in Debug build." --- this was wrong, I simply forgot to set appropriate setting to debug confugiration.

So I think this is a precision issue which did not happen in Release builds before 2.06 because of 80-bit intermediate precision. When we switched to SSE, this intermediate precision was gone, so now some expressions are not so precise as they were.
Most likely, the problem is caused by collision detection code.

stgatilov

stgatilov

28.06.2018 02:53

developer   ~0010595

Last edited: 28.06.2018 02:54

View 2 revisions

I think the problem is happening in idCollisionModelManagerLocal::TranslateTrmEdgeThroughPolygon.

Here we see this code:
    // create plane with normal vector orthogonal to both the polygon edge and the trm edge
    start = tw->model->vertices[edge->vertexNum[0]].p;
    end = tw->model->vertices[edge->vertexNum[1]].p;
    tw->trace.c.normal = ( end - start ).Cross( trmEdge->end - trmEdge->start );
    tw->trace.c.normal.Normalize();
    tw->trace.c.dist = tw->trace.c.normal * start;
    // make sure the collision plane faces the trace model
    if ( tw->trace.c.normal * trmEdge->start - tw->trace.c.dist < 0.0f ) {
        tw->trace.c.normal = -tw->trace.c.normal;
        tw->trace.c.dist = -tw->trace.c.dist;
    }

So when edge-edge contact is detected, the code tries to check relative position of colliding edges at start moment. This is done like this:
  normal = normalize(cross(e1 - s1, e2 - s2))
  dist = dot(normal, s2) * dot(normal, s1)
  dist < 0 => reverse normal
Depending on sign of this distance, normal vector of collision is reversed.

Suppose that all edge endpoints are large, but the angle between them is small. Then normal will be quite imprecise (given 32-bit floats). Now we need to compare two dot products, which are quite large again but differ only slightly. Due to low precision of normal, this check gives arbitrary results.
Oh, my dear ID, this is so careless of you =)

What we see is that normals of edge-edge contacts are easily reverted when coordinates are large. The player's movement code searches for a displacement in a cone bounded by several planes, including the planes of collision contants. When collision returns reversed normal, it makes it impossible for the movement code to "unglue" the player from this collision. This is how he gets stuck.

stgatilov

stgatilov

28.06.2018 03:18

developer   ~0010596

Last edited: 28.06.2018 03:47

View 2 revisions

Considering this particular example:

There is a world edge:
     edge->vertexNum = {14069, 14071}
[s1] start (11296.0000, -5856.00000, -6056.00000)
[e1] end (11504.0000, -5664.44629, -6175.71045)
[s2] trmEdge->start (11349.4990, -5792.92920, -6092.93262)
[e2] trmEdge->end (11360.8125, -5797.61572, -6092.93262)

Now when we compute cross product for normal, we get (Debug win32):
  tw->trace.c.normal (-561.025818, -1354.34131, -3141.93530)
However, the true normal (considering points to be precise) is:
                       -561.025418, -1354.34417, -3141.93905

After normalization we get in program:
  tw->trace.c.normal (-0.161814392, -0.390627146, -0.906215549)
And the true value is:
                       -0.161814053, -0.390627436, -0.906215436
We see an error about 4e-7 here.
If use theory to estimate this error pessimistically, then it would be about 6e-6, so we are actually lucky here =)

Looking at dot products, they are:
  dot(normal, s2) = 5947.87354
  dot(normal, s1) = 5947.69873
And the true values are:
                    5947.87824164015642313933466787
                    5947.70340622049354756358219651

Damn. Perhaps my hypothesis was wrong.
Perhaps the problem happens earlier (maybe in different place).

UDPATE: tried to rewrite this place using doubles and check if there are different verdicts anywhere --- no luck. Moreover, it is worth noting that subtraction of float numbers of same sign is actually EXACT, so there is nothing bad in subtracting 11360.8125 - 11349.4990. The problem may happen when you compute these numbers, but not when you subtract them.

stgatilov

stgatilov

28.06.2018 05:08

developer   ~0010597

Last edited: 28.06.2018 05:08

View 2 revisions

Ok, I replaced the dangerous normal sign criterion with one based on edge normal.

According to idCollisionModelManagerLocal::CalculateEdgeNormals, edge normal is an average of the outer normals of two neighboring polygons. If there is only one neighboring polygon, then it points out of the polygon in its plane.
Clearly, the edge normal always points outwards of the solid (just as face normals do). So when we collide an edge, the collision contact normal should look into the same direction where the edge's normal looks.

I wonder why ID implemented the original crazy check. For all the other types of contact, they use polygon normals and other reliable information to choose orientation. Only edge-edge collision has this weird sign detection criterion.

Anyway, I'll test physics for some time locally, and then commit it.

stgatilov

stgatilov

30.06.2018 04:46

developer   ~0010614

I did not notice anything bad with physics.

Also I have added two testmaps posted by Jesps here:
  http://forums.thedarkmod.com/topic/19510-cauldron-clipping-issues/page-2#entry423832
  http://forums.thedarkmod.com/topic/19510-cauldron-clipping-issues/page-2#entry424145
as test/4853_stuckTest.map and test/4853_stuckTest2.map (svn rev 15242).

On a small map 4853_stuckTest, I get stuck on original build, but not on the new one with the fix applied.
As for the larger map 4853_stuckTest2, it has five rooms ranging from near-origin room to moved-far-away rooms (the last of which is especially bad). With original build, I easily get stuck in two rooms. With the fix, I don't get stuck at all.

Note that one room also shows an error of going through the wall. It is not related to player movement and collisions, so not relevant here. I guess these problems happen because of dmap issues.
stgatilov

stgatilov

30.06.2018 05:04

developer   ~0010615

Committed the fix in svn rev 7527.

If you notice any problems with collisions or traces, it would be wise to check if locally reverting this commit helps.

Issue History

Date Modified Username Field Change
27.06.2018 17:31 stgatilov New Issue
27.06.2018 17:31 stgatilov Status new => assigned
27.06.2018 17:31 stgatilov Assigned To => stgatilov
27.06.2018 17:37 stgatilov Note Added: 0010591
27.06.2018 17:38 stgatilov Relationship added related to 0004435
28.06.2018 02:53 stgatilov Note Added: 0010595
28.06.2018 02:54 stgatilov Note Edited: 0010595 View Revisions
28.06.2018 03:18 stgatilov Note Added: 0010596
28.06.2018 03:47 stgatilov Note Edited: 0010596 View Revisions
28.06.2018 03:57 stgatilov Note Edited: 0010591 View Revisions
28.06.2018 05:08 stgatilov Note Added: 0010597
28.06.2018 05:08 stgatilov Note Edited: 0010597 View Revisions
30.06.2018 04:46 stgatilov Note Added: 0010614
30.06.2018 05:04 stgatilov Note Added: 0010615
30.06.2018 06:54 stgatilov Status assigned => resolved
30.06.2018 06:54 stgatilov Fixed in Version => TDM 2.07
30.06.2018 06:54 stgatilov Resolution open => fixed
30.06.2018 09:10 stgatilov Tag Attached: precision