X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=tools%2Fquake3%2Fq3map2%2Fmap.c;h=12892573c354fd9c8b6e5b0349703117b2e75686;hb=5c97bccbf609eaa1928c9058d3d6b099397656a0;hp=d61f51be26e60237469ee828c37579ba0dc28bad;hpb=bc2185ec9485c3bb60f6a3d3f6df8d802de7357b;p=xonotic%2Fnetradiant.git diff --git a/tools/quake3/q3map2/map.c b/tools/quake3/q3map2/map.c index d61f51be..12892573 100644 --- a/tools/quake3/q3map2/map.c +++ b/tools/quake3/q3map2/map.c @@ -59,9 +59,6 @@ PlaneEqual() ydnar: replaced with variable epsilon for djbob */ -#define NORMAL_EPSILON 0.00001 -#define DIST_EPSILON 0.01 - qboolean PlaneEqual( plane_t *p, vec3_t normal, vec_t dist ) { float ne, de; @@ -72,10 +69,14 @@ qboolean PlaneEqual( plane_t *p, vec3_t normal, vec_t dist ) de = distanceEpsilon; /* compare */ - if( fabs( p->dist - dist ) <= de && - fabs( p->normal[ 0 ] - normal[ 0 ] ) <= ne && - fabs( p->normal[ 1 ] - normal[ 1 ] ) <= ne && - fabs( p->normal[ 2 ] - normal[ 2 ] ) <= ne ) + // We check equality of each component since we're using '<', not '<=' + // (the epsilons may be zero). We want to use '<' intead of '<=' to be + // consistent with the true meaning of "epsilon", and also because other + // parts of the code uses this inequality. + if ((p->dist == dist || fabs(p->dist - dist) < de) && + (p->normal[0] == normal[0] || fabs(p->normal[0] - normal[0]) < ne) && + (p->normal[1] == normal[1] || fabs(p->normal[1] - normal[1]) < ne) && + (p->normal[2] == normal[2] || fabs(p->normal[2] - normal[2]) < ne)) return qtrue; /* different */ @@ -152,12 +153,73 @@ int CreateNewFloatPlane (vec3_t normal, vec_t dist) /* SnapNormal() -snaps a near-axial normal vector +Snaps a near-axial normal vector. +Returns qtrue if and only if the normal was adjusted. */ -void SnapNormal( vec3_t normal ) +qboolean SnapNormal( vec3_t normal ) { +#if Q3MAP2_EXPERIMENTAL_SNAP_NORMAL_FIX int i; + qboolean adjusted = qfalse; + + // A change from the original SnapNormal() is that we snap each + // component that's close to 0. So for example if a normal is + // (0.707, 0.707, 0.0000001), it will get snapped to lie perfectly in the + // XY plane (its Z component will be set to 0 and its length will be + // normalized). The original SnapNormal() didn't snap such vectors - it + // only snapped vectors that were near a perfect axis. + + for (i = 0; i < 3; i++) + { + if (normal[i] != 0.0 && -normalEpsilon < normal[i] && normal[i] < normalEpsilon) + { + normal[i] = 0.0; + adjusted = qtrue; + } + } + + if (adjusted) + { + VectorNormalize(normal, normal); + return qtrue; + } + return qfalse; +#else + int i; + + // I would suggest that you uncomment the following code and look at the + // results: + + /* + Sys_Printf("normalEpsilon is %f\n", normalEpsilon); + for (i = 0;; i++) + { + normal[0] = 1.0; + normal[1] = 0.0; + normal[2] = i * 0.000001; + VectorNormalize(normal, normal); + if (1.0 - normal[0] >= normalEpsilon) { + Sys_Printf("(%f %f %f)\n", normal[0], normal[1], normal[2]); + Error("SnapNormal: test completed"); + } + } + */ + + // When the normalEpsilon is 0.00001, the loop will break out when normal is + // (0.999990 0.000000 0.004469). In other words, this is the vector closest + // to axial that will NOT be snapped. Anything closer will be snaped. Now, + // 0.004469 is close to 1/225. The length of a circular quarter-arc of radius + // 1 is PI/2, or about 1.57. And 0.004469/1.57 is about 0.0028, or about + // 1/350. Expressed a different way, 1/350 is also about 0.26/90. + // This means is that a normal with an angle that is within 1/4 of a degree + // from axial will be "snapped". My belief is that the person who wrote the + // code below did not intend it this way. I think the person intended that + // the epsilon be measured against the vector components close to 0, not 1.0. + // I think the logic should be: if 2 of the normal components are within + // epsilon of 0, then the vector can be snapped to be perfectly axial. + // We may consider adjusting the epsilon to a larger value when we make this + // code fix. for( i = 0; i < 3; i++ ) { @@ -165,15 +227,17 @@ void SnapNormal( vec3_t normal ) { VectorClear( normal ); normal[ i ] = 1; - break; + return qtrue; } if( fabs( normal[ i ] - -1 ) < normalEpsilon ) { VectorClear( normal ); normal[ i ] = -1; - break; + return qtrue; } } + return qfalse; +#endif } @@ -192,18 +256,70 @@ void SnapPlane( vec3_t normal, vec_t *dist, vec3_t center ) SnapPlane reenabled by namespace because of multiple reports of q3map2-crashes which were triggered by this patch. */ - // div0: ensure the point "center" stays on the plane (actually, this - // rotates the plane around the point center). - // if center lies on the plane, it is guaranteed to stay on the plane by - // this fix. - vec_t centerDist = DotProduct(normal, center); SnapNormal( normal ); - *dist += (DotProduct(normal, center) - centerDist); + + // TODO: Rambetter has some serious comments here as well. First off, + // in the case where a normal is non-axial, there is nothing special + // about integer distances. I would think that snapping a distance might + // make sense for axial normals, but I'm not so sure about snapping + // non-axial normals. A shift by 0.01 in a plane, multiplied by a clipping + // against another plane that is 5 degrees off, and we introduce 0.1 error + // easily. A 0.1 error in a vertex is where problems start to happen, such + // as disappearing triangles. + + // Second, assuming we have snapped the normal above, let's say that the + // plane we just snapped was defined for some points that are actually + // quite far away from normal * dist. Well, snapping the normal in this + // case means that we've just moved those points by potentially many units! + // Therefore, if we are going to snap the normal, we need to know the + // points we're snapping for so that the plane snaps with those points in + // mind (points remain close to the plane). + + // I would like to know exactly which problems SnapPlane() is trying to + // solve so that we can better engineer it (I'm not saying that SnapPlane() + // should be removed altogether). Fix all this snapping code at some point! if( fabs( *dist - Q_rint( *dist ) ) < distanceEpsilon ) *dist = Q_rint( *dist ); } +/* +SnapPlaneImproved() +snaps a plane to normal/distance epsilons, improved code +*/ +void SnapPlaneImproved(vec3_t normal, vec_t *dist, int numPoints, const vec3_t *points) +{ + int i; + vec3_t center; + vec_t distNearestInt; + + if (SnapNormal(normal)) + { + if (numPoints > 0) + { + // Adjust the dist so that the provided points don't drift away. + VectorClear(center); + for (i = 0; i < numPoints; i++) + { + VectorAdd(center, points[i], center); + } + for (i = 0; i < 3; i++) { center[i] = center[i] / numPoints; } + *dist = DotProduct(normal, center); + } + } + + if (VectorIsOnAxis(normal)) + { + // Only snap distance if the normal is an axis. Otherwise there + // is nothing "natural" about snapping the distance to an integer. + distNearestInt = Q_rint(*dist); + if (-distanceEpsilon < *dist - distNearestInt && *dist - distNearestInt < distanceEpsilon) + { + *dist = distNearestInt; + } + } +} + /* @@ -221,16 +337,15 @@ int FindFloatPlane( vec3_t innormal, vec_t dist, int numPoints, vec3_t *points ) int pidx; plane_t *p; vec_t d; - vec3_t centerofweight; vec3_t normal; - VectorClear(centerofweight); - for(i = 0; i < numPoints; ++i) - VectorMA(centerofweight, 1.0 / numPoints, points[i], centerofweight); - - /* hash the plane */ VectorCopy(innormal, normal); - SnapPlane( normal, &dist, centerofweight ); +#if Q3MAP2_EXPERIMENTAL_SNAP_PLANE_FIX + SnapPlaneImproved(normal, &dist, numPoints, (const vec3_t *) points); +#else + SnapPlane( normal, &dist ); +#endif + /* hash the plane */ hash = (PLANE_HASHES - 1) & (int) fabs( dist ); /* search the border bins as well */ @@ -251,9 +366,15 @@ int FindFloatPlane( vec3_t innormal, vec_t dist, int numPoints, vec3_t *points ) /* ydnar: test supplied points against this plane */ for( j = 0; j < numPoints; j++ ) { + // NOTE: When dist approaches 2^16, the resolution of 32 bit floating + // point number is greatly decreased. The distanceEpsilon cannot be + // very small when world coordinates extend to 2^16. Making the + // dot product here in 64 bit land will not really help the situation + // because the error will already be carried in dist. d = DotProduct( points[ j ], p->normal ) - p->dist; - if( fabs( d ) > distanceEpsilon ) - break; + d = fabs(d); + if (d != 0.0 && d >= distanceEpsilon) + break; // Point is too far from plane. } /* found a matching plane */ @@ -273,15 +394,12 @@ int FindFloatPlane( vec3_t innormal, vec_t dist, int numPoints, vec3_t *points ) plane_t *p; vec3_t normal; - - vec3_t centerofweight; - - VectorClear(centerofweight); - for(i = 0; i < numPoints; ++i) - VectorMA(centerofweight, 1.0 / numPoints, points[i], centerofweight); - VectorCopy(innormal, normal); - SnapPlane( normal, &dist, centerofweight ); +#if Q3MAP2_EXPERIMENTAL_SNAP_PLANE_FIX + SnapPlaneImproved(normal, &dist, numPoints, (const vec3_t *) points); +#else + SnapPlane( normal, &dist ); +#endif for( i = 0, p = mapplanes; i < nummapplanes; i++, p++ ) { if( !PlaneEqual( p, normal, dist ) ) @@ -301,6 +419,9 @@ int FindFloatPlane( vec3_t innormal, vec_t dist, int numPoints, vec3_t *points ) /* found a matching plane */ if( j >= numPoints ) return i; + // TODO: Note that the non-USE_HASHING code does not compute epsilons + // for the provided points. It should do that. I think this code + // is unmaintained because nobody sets USE_HASHING to off. } return CreateNewFloatPlane( normal, dist ); @@ -317,6 +438,28 @@ takes 3 points and finds the plane they lie in int MapPlaneFromPoints( vec3_t *p ) { +#if Q3MAP2_EXPERIMENTAL_HIGH_PRECISION_MATH_FIXES + vec3_accu_t paccu[3]; + vec3_accu_t t1, t2, normalAccu; + vec3_t normal; + vec_t dist; + + VectorCopyRegularToAccu(p[0], paccu[0]); + VectorCopyRegularToAccu(p[1], paccu[1]); + VectorCopyRegularToAccu(p[2], paccu[2]); + + VectorSubtractAccu(paccu[0], paccu[1], t1); + VectorSubtractAccu(paccu[2], paccu[1], t2); + CrossProductAccu(t1, t2, normalAccu); + VectorNormalizeAccu(normalAccu, normalAccu); + // TODO: A 32 bit float for the plane distance isn't enough resolution + // if the plane is 2^16 units away from the origin (the "epsilon" approaches + // 0.01 in that case). + dist = (vec_t) DotProductAccu(paccu[0], normalAccu); + VectorCopyAccuToRegular(normalAccu, normal); + + return FindFloatPlane(normal, dist, 3, p); +#else vec3_t t1, t2, normal; vec_t dist; @@ -332,6 +475,7 @@ int MapPlaneFromPoints( vec3_t *p ) /* store the plane */ return FindFloatPlane( normal, dist, 3, p ); +#endif } @@ -346,7 +490,7 @@ void SetBrushContents( brush_t *b ) int contentFlags, compileFlags; side_t *s; int i; - qboolean mixed; + //% qboolean mixed; /* get initial compile flags from first side */ @@ -354,7 +498,7 @@ void SetBrushContents( brush_t *b ) contentFlags = s->contentFlags; compileFlags = s->compileFlags; b->contentShader = s->shaderInfo; - mixed = qfalse; + //% mixed = qfalse; /* get the content/compile flags for every side in the brush */ for( i = 1; i < b->numsides; i++, s++ ) @@ -362,8 +506,8 @@ void SetBrushContents( brush_t *b ) s = &b->sides[ i ]; if( s->shaderInfo == NULL ) continue; - if( s->contentFlags != contentFlags || s->compileFlags != compileFlags ) - mixed = qtrue; + //% if( s->contentFlags != contentFlags || s->compileFlags != compileFlags ) + //% mixed = qtrue; contentFlags |= s->contentFlags; compileFlags |= s->compileFlags; @@ -1052,9 +1196,6 @@ parses a brush out of a map file and sets it up static void ParseBrush( qboolean onlyLights, qboolean noCollapseGroups ) { - brush_t *b; - - /* parse the brush out of the map */ ParseRawBrush( onlyLights ); @@ -1097,7 +1238,7 @@ static void ParseBrush( qboolean onlyLights, qboolean noCollapseGroups ) } /* finish the brush */ - b = FinishBrush(noCollapseGroups); + FinishBrush(noCollapseGroups); } @@ -1462,8 +1603,7 @@ static qboolean ParseMapEntity( qboolean onlyLights, qboolean noCollapseGroups ) } /* range check */ - if( numEntities >= MAX_MAP_ENTITIES ) - Error( "numEntities == MAX_MAP_ENTITIES" ); + AUTOEXPAND_BY_REALLOC(entities, numEntities, allocatedEntities, 32); /* setup */ entitySourceBrushes = 0;