Jump to content
The Dark Mod Forums
Sign in to follow this  
grayman

DR and its shifting planes

Recommended Posts

I can't find any worldspawn brushes that wandered off grid in In the North. (Not much left to look at, though, after filtering out all the func_statics and patches. Which, I guess, is how it's supposed to be.)

 

Func_static plane variables stored in the map file are based on the func_static's origin, so if there's some error introduced by moving back and forth between func_static origin and world origin, then that's a great find and supports the theory that the error accumulates over time.

 

Woo-hoo!!

Share this post


Link to post
Share on other sites

There is more evidence. I'm holding the camera stationary and I'm vigorously hitting the save button. Behold the pink caulk line:

E1Gxu.png

bwVhR.png

LcuZi.png

 

It grows thicker and thicker for the func_static, but nothing happens to the worldspawn.

 

I think this is evidence enough that worldspawn is untouched.

 

In this experiment, I'm NOT loading the mission. Just repeatably saving it. That means the corruption happens in saving, not loading, right?


Clipper

-The mapper's best friend.

Share this post


Link to post
Share on other sites

Non-worldspawn brushes only would certainly be consistent with earlier posts in this thread about the problem occurring on detail work, as well as the fact that users aren't reporting world leaks by the dozen, which would surely be expected if worldspawn was being corrupted.

 

Good point.

Share this post


Link to post
Share on other sites

I think this is evidence enough that worldspawn is untouched.

 

Oooh, that's a good test.

 

That would be worse than my theory, which was that it took a re-read of the data to cause the error.

 

If you're just hitting repeated Saves and seeing this, that would be a strange design (one wouldn't expect it to tickle the original data after putting it through a shift for write purposes).

Share this post


Link to post
Share on other sites
In this experiment, I'm NOT loading the mission. Just repeatably saving it. That means the corruption happens in saving, not loading, right?

 

Correct. This is consistent with my analysis of the code so far.

 

If you're just hitting repeated Saves and seeing this, that would be a strange design (one wouldn't expect it to tickle the original data after putting it through a shift for write purposes).

 

Agreed, saving a map should not result in any modifications to its canonical representation in memory. However, even if this change was only made in the exporter itself, the problem would still occur when the map is reloaded and it rebuilds the geometry from the modified version. So I think there must be some mathematical issue which results in these progressive errors that is not simply due to floating point inaccuracies.

 

I think the Correct solution would be to avoid this mismatch between the map and the DR representation, and make DR store the brushes local to their func_static origin all the time rather than just when saving (this is how any other 3D app would do it). I have no idea how much work would be involved to achieve this though.

Share this post


Link to post
Share on other sites

If this problem only accours to func_static that have a size in any direction that is not not a power of two, then this could even be a simple rounding error bug, as the center of the func_static which mostly serves as its origin then maybe cannot be described exactly. :unsure:

 

If you can post the formulas used for the coordinate transformation here, I'm maybe able to tell you what goes wrong.


FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites

I think the Correct solution would be to avoid this mismatch between the map and the DR representation, and make DR store the brushes local to their func_static origin all the time rather than just when saving (this is how any other 3D app would do it). I have no idea how much work would be involved to achieve this though.

 

What about saving plane equations that are based on (0,0,0), just like the world brushes? If that's how they're stored internally, just skip the write-time mapping to the local func_static origin (and reverse read-time mapping back to (0,0,0)). A plane is a plane is a plane, regardless of where the world origin is.

Share this post


Link to post
Share on other sites
If you can post the formulas used for the coordinate transformation here, I'm maybe able to tell you what goes wrong.

 

I don't have enough knowledge of the maths to be able to identify actual formulae. I know that a brush is defined by a series of planes, and each plane is defined by a 3-component normal vector and a distance, which I guess would satisfy the plane equation ax + by + cz + d = 0, but I couldn't be certain how the values are derived.

 

What about saving plane equations that are based on (0,0,0), just like the world brushes? If that's how they're stored internally, just skip the write-time mapping to the local func_static origin (and reverse read-time mapping back to (0,0,0)). A plane is a plane is a plane, regardless of where the world origin is.

 

But won't that result in the brushes being in the wrong place when loaded into the game? I can disable the translation code and confirm that the results are identical on every save, but the distance values of each plane are different,e.g.

 

( 1 0 0 76 ) ( ( 0 -0.015625 3.3125 ) ( 0.015625 0 243.5615081787109 ) ) "textures/darkmod/wood/boards/old_worn_black" 0 0 0

 

becomes

 

( 1 0 0 -11820 ) ( ( 0 -0.015625 3.3125 ) ( 0.015625 0 243.5615081787109 ) ) "textures/darkmod/wood/boards/old_worn_black" 0 0 0

 

The numbers in the first parentheses are the normal vector followed by the distance, and we can see that the distance has changed substantially. I assume that the code transforms the planes into local object space because that is how Doom 3 is going to interpret them.

 

Or are you suggesting that the planes should be left in world space and the func_static origin set to (0, 0, 0)? I guess that would give the same end result, but the func_static's local origin would be lost when the map is reloaded, and mappers might be relying on this for something.

Share this post


Link to post
Share on other sites

As you said correctly d in the equation you'Ve posted is the distance (to the origin of the chosen coordinate system). The question is how the code derives the distance to the new origin (the origin of the func_static) from the distance to the old origin (the point (0,0,0)) If this is done in an unlucky way it can cause errors.

 

The good way:

- You take the vector pointing from the func_static origin to any point of your plane and multiply it with the normal of this plane. The value you get is -d

 

The bad way:

- You take a point out of the plane like above and the origin of the func_static and calculate the distance

 

The first method means you have three multiplications which results you some up. The latter means you have three multiplications (quadrations) which you sum up and then take the square root out of.

 

I have identified a problem whereby the map saving code is actually modifying all of the brushes before export in order to subtract the func_static's origin (presumably to make the brushes relative to the func_static instead of the world origin), and then adding it back afterwards, which results in a small change to the value

This is the peace of code I'm referring to.


FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites

Or are you suggesting that the planes should be left in world space and the func_static origin set to (0, 0, 0)? I guess that would give the same end result, but the func_static's local origin would be lost when the map is reloaded, and mappers might be relying on this for something.

 

No, you can't change the origin.

 

If DR is doing this:

 

func_static internal data->apply some translation function->write->apply the reverse of the translation function->func_static internal data

 

then the internal data is shifting each time a write occurs.

 

So the translation function is probably just (-originx, -originy, -originz) applied to each plane, to bring the func_static's origin back to zero. Then, when the data is read, it applies the reverse translation function (+originx, +originy, +originz) to put the func_static back to its original location.

 

Just skip the translation function on each write, and then skip its reverse on each read.

Share this post


Link to post
Share on other sites
The question is how the code derives the distance to the new origin (the origin of the func_static) from the distance to the old origin (the point (0,0,0)) If this is done in an unlucky way it can cause errors.

 

The current process works by constructing a 4x4 matrix to represent the translation to the origin, then transforming each of the planes making up a brush by this matrix. The code to transform a plane by a matrix is currently as follows:

 

Plane3 Matrix4::transform(const Plane3& plane) const
{
   Plane3 transformed;
   transformed.normal().x() = _m[0] * plane.normal().x() + _m[4] * plane.normal().y() + _m[8] * plane.normal().z();
   transformed.normal().y() = _m[1] * plane.normal().x() + _m[5] * plane.normal().y() + _m[9] * plane.normal().z();
   transformed.normal().z() = _m[2] * plane.normal().x() + _m[6] * plane.normal().y() + _m[10] * plane.normal().z();
   transformed.dist() = -(    (-plane.dist() * transformed.normal().x() + _m[12]) * transformed.normal().x() +
				    (-plane.dist() * transformed.normal().y() + _m[13]) * transformed.normal().y() +
				    (-plane.dist() * transformed.normal().z() + _m[14]) * transformed.normal().z());
   return transformed;
}

 

The first four lines are transforming the plane's normal vector by using the upper-left 3x3 quadrant of the matrix (i.e. without the translation part). The fifth line is changing the distance value by a process I don't fully understand, but it appears to be projecting the original distance value along the original normal vector, adding the translation elements from the 4x4 matrix, and then projecting again along the normal vector (?).

 

The first method means you have three multiplications which results you some up. The latter means you have three multiplications (quadrations) which you sum up and then take the square root out of.

 

Although the plane transformation itself doesn't include any square roots, there is a subsequent step after transforming the planes that re-normalises each of the normal vectors (by calculating Pythagorean length and then dividing by this). This appears to be where the small errors are coming from, because in this case the vectors are already normalised, and it's scaling by values like 0.999999875

 

One way to solve this might be to skip the re-normalisation if the existing length is very close to 1.0, to avoid scaling by these tiny amounts. Another way might be to explicitly add an interface to just translate brush faces, without using a general matrix.

 

Just skip the translation function on each write, and then skip its reverse on each read.

 

From the point of view of DR itself, that works fine. I can write the file with no translation and read it back and end up with the correct result. However, I don't understand how this can still work in Doom 3. If the game engine is expecting func_static brush faces to have the func_static origin subtracted, and DR writes out faces that do not have the origin subtracted, surely the brushes will end up in the wrong place in game?

Share this post


Link to post
Share on other sites

If the normal length is w/in a certain very small margin of error to 1.0, I see no reason to "normalize the normal" and allow the math to corrupt everything else.

 

There's a value named VECTOR_EPSILON that's used in TDM to determine if two vectors are "equivalent". It's value is 0.001. Perhaps we skip the re-normalization if

 

( 1.0 - VECTOR_EPSILON ) < normal length < ( 1.0 + VECTOR_EPSILON )

 

Might be worth an experiment. Apply that, then use Sotha's "rapid saves" method to visualize the results.

 

Apart from that suggestion, the next thing I would be interested in doing is looking at that section of the code myself and running a few func_statics through it to see what the accumulated error looks like.

Share this post


Link to post
Share on other sites

If the normal length is w/in a certain very small margin of error to 1.0, I see no reason to "normalize the normal" and allow the math to corrupt everything else.

 

I agree. Perhaps there should be a "safe" mode which does the check to avoid rounding errors, and a "fast" mode for when the calling code knows the normalisation is required and wants to avoid the performance impact of a check.

 

Apart from that suggestion, the next thing I would be interested in doing is looking at that section of the code myself and running a few func_statics through it to see what the accumulated error looks like.

 

The relevant code path is:

 

Brush::translateDoom3Brush() [radiant/brush/Brush.cpp]
Brush::transform() [radiant/brush/Brush.cpp]
Face::transform() [radiant/brush/Face.cpp]
FacePlane::transform() [radiant/brush/FacePlane.cpp]

 

The FacePlane object is a wrapper for a Plane3 which does the negation of the distance value (something to do with whether the brush face planes are defined "inwards" or "outwards", I guess) and the redundant normalisation step.

 

Oh, and what precision is used in the matrix operations? Double or float?

 

It is currently double, but as Greebo remarked when making the change, the extra precision is only going to scale down the errors, rather than eliminate them. If this issue is fixed it might be worth switching back to float for the performance benefits.

Share this post


Link to post
Share on other sites

There's a value named VECTOR_EPSILON that's used in TDM to determine if two vectors are "equivalent". It's value is 0.001. Perhaps we skip the re-normalization if

 

( 1.0 - VECTOR_EPSILON ) < normal length < ( 1.0 + VECTOR_EPSILON )

 

Might be worth an experiment.

If the code really uses double precision I doubt the normal will ever have such a high error. So we could just skip normalization .

 

The current process works by constructing a 4x4 matrix to represent the translation to the origin, then transforming each of the planes making up a brush by this matrix. The code to transform a plane by a matrix is currently as follows:

 

Plane3 Matrix4::transform(const Plane3& plane) const

{

Plane3 transformed;

transformed.normal().x() = _m[0] * plane.normal().x() + _m[4] * plane.normal().y() + _m[8] * plane.normal().z();

transformed.normal().y() = _m[1] * plane.normal().x() + _m[5] * plane.normal().y() + _m[9] * plane.normal().z();

transformed.normal().z() = _m[2] * plane.normal().x() + _m[6] * plane.normal().y() + _m[10] * plane.normal().z();

transformed.dist() = -( (-plane.dist() * transformed.normal().x() + _m[12]) * transformed.normal().x() +

(-plane.dist() * transformed.normal().y() + _m[13]) * transformed.normal().y() +

(-plane.dist() * transformed.normal().z() + _m[14]) * transformed.normal().z());

return transformed;

}

 

The first four lines are transforming the plane's normal vector by using the upper-left 3x3 quadrant of the matrix (i.e. without the translation part). The fifth line is changing the distance value by a process I don't fully understand, but it appears to be projecting the original distance value along the original normal vector, adding the translation elements from the 4x4 matrix, and then projecting again along the normal vector (?).

I just took a rough look but I thought that the only thing happens is to translate the origin of the coordinate system into the origin of the specific func_static. I see no reason why in this case the face normals must be reevaluated. A translation wouldn't touch those at all. Only an rotation would make changes to them. The only thing that should change is the "example point" in the normal form or in your notation the value d.

It seems to me that this is a piece of code that is capable of doing much more then it necessarily have to. :mellow:

 

And yes, I'm pretty sure the normalization causes the errors here. (Maybe this sentence had been enough for an answer :D )

 

Btw.: What does the 4x4-Matrix consist of? :huh:

 

Any 3D coordinate transformation has the form: new = rotation*old + translation (in the case of no rotation (new = old + translation)

Edited by Obsttorte

FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites

The point about plane equations is you can translate them by just modifying the distance parameter. Here is how my code in swift does translate brushes around:

 

my $d2 = $d - ($vx * $x + $vy * $y + $vz * $z);

 

$vx, $vy, and $vz are the translation in units in X,Y,Z. $x, $y, $z and $d are the original values and and $d2 is the new distance.

 

So if you have:

 

( X Y Z D ) ...

 

as brush def, replace this with "X Y Z D2" after computing D2 like that above. No matrix etc. nec.

  • Like 1

"The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man." -- George Bernard Shaw (1856 - 1950)

 

"Remember: If the game lets you do it, it's not cheating." -- Xarax

Share this post


Link to post
Share on other sites

OK, so I just wrote it down and see what happens here. The last formula is relatively simple, but written down in an not understandable way. Most of the operations performed there are completely unnecessary. Let me try to explain it. We have

  • n: the OLD normal
  • Q: the rotation matrix
  • t : the translation vector
  • d: the OLD distance

As tels just wrote the new distance is:

d2 = d - t*n

What now stands there is:

d2 = d*(Q*n)*(Q*n) - t*Q*n

the term (Q*n)*(Q*n) is the quadrat of the new normal (that is one as it is a normal)

anyways, as we have no rotation here Q is the identity and can be left away so we replace (Q*n)*(Q*n) with one Q*n with n and get:

d2 = d -t*n

It seems that whoever programmed the code wanted to leave the possibility to rotate the coordinate system (for example if the func_static is rotated itself)

but even then the formula is unnecessary complicated, with rotation it would become

d2 = d-t*(Q*n)

but only if you rotate the system BEFORE you translate it, what makes no sense IMO

rotating the system after the translation lead to the above equation (without the Q)

Edited by Obsttorte

FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites
It seems to me that this is a piece of code that is capable of doing much more then it necessarily have to. :mellow:

 

The point about plane equations is you can translate them by just modifying the distance parameter.

 

Agreed. It seems that "for convenience" the code is using an arbitrary matrix transformation method to do just a translation, which results in redundant and harmful changes happening to the normal vector too. The Plane3 class actually has a special method to do just a translation which updates only the distance parameter, and I think using this method here would eliminate this source of errors.

Share this post


Link to post
Share on other sites

that's goooooooooooooooooood :smile:

 

EDIT: IMO the main error source is the quadratic operation that calculates the length of the new normal.

This is especially strange as said operation results always in the value one. :mellow:

 

 

It seems to me that whoever had programmed this just took a math book and looked up the formula without having any idea what exactly he is doing there. :o

Edited by Obsttorte

FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites
It seems to me that whoever had programmed this just took a math book and looked up the formula without having any idea what exactly he is doing there. :o

 

Note that this method is designed to transform a Plane3 by any arbitrary matrix and is used for other things than just exporting func_statics, so it is correct that it also modifies the normal vector. The problem here is that the calling code is using this matrix-based transformation method when it knows that only a translation is needed, without taking into account the inaccuracies that this will cause.

Share this post


Link to post
Share on other sites

so it is correct that it also modifies the normal vector

You misunderstood me. What I've meant is that the code performs a relative complicated operation that has ALWAYS the same result but causes inaccuracies. So it would have made much more sense to just fill in the result instead of calculating something that you already know. ;)


FM's: Builder Roads, Old Habits, Old Habits Rebuild

WIP's: Several. Although after playing Thief 4 I really wanna make a city mission.

Mapping and Scripting: Apples and Peaches

Sculptris Models and Tutorials: Obsttortes Models

My wiki articles: Obstipedia

Texture Blending in DR: DR ASE Blend Exporter

Share this post


Link to post
Share on other sites

Okay, so it looks like we're zeroing in on the problem. A solution to test would be to use math that does a simple translation, w/o involving a general transformational matrix that handles rotation, which is not needed in this case.

 

Yes? No?

Share this post


Link to post
Share on other sites

Probably an ignorant question, but does DR offer different types of optimization when compiling/saving bsp brushes as seen in the first picture? Most BSP based game engines have optimisation that is intended to reduce the polys etc. for lower performance computers, In the Unreal engine this optimisation usually messes things up with VERY little poly reduction. Anyways I know I have no experience with DR (yet) but an easy fix with the early Unreal engine was to move the offending brush away, rebuild, then move it back and rebuild.

 

 

 

Good luck with this guys..

Edited by VENOM

Share this post


Link to post
Share on other sites
You misunderstood me. What I've meant is that the code performs a relative complicated operation that has ALWAYS the same result but causes inaccuracies. So it would have made much more sense to just fill in the result instead of calculating something that you already know. ;)

 

Fair enough. You're obviously more familiar with the maths than I am, so if you can suggest an improved implementation that gives the correct result with less error we can certainly try using it instead of the old code.

 

Okay, so it looks like we're zeroing in on the problem. A solution to test would be to use math that does a simple translation, w/o involving a general transformational matrix that handles rotation, which is not needed in this case.

 

Yes, that is what I was planning to try first (although you can certainly do your own experiments too). I think for safety it would be a good idea to add the check for normalisation of an already-normalised vector, and to refactor the code so that the transformation is only done in the export/import code rather than in the main scenegraph, but these are secondary to correcting the maths in the first place.

 

Probably an ignorant question, but does DR offer different types of optimization when compiling/saving bsp brushes as seen in the first picture?

 

DR does not do any map or BSP compilation, this is all done by the Doom 3 application itself.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...