Engine patch. Better curves tesselation.

[divVerent]

I just checked q3map2 source code for the "-patchmeta" option for when it considers two patches to be part of the same LOD group: it assumes they're together when they have a vertex that's - in X, Y and Z - less than 1 qu away from the other (not absolutely equal, like your code requires).

Maybe you should do the same in your code. Sometimes mappers simply don't manage to get the vertices ENTIRELY on top of each other, e.g. if the patch has been affected by a scale or rotate operation in radiant.

As for the tesselation:

Currently, at tolerance 4 (default), a bestsquareddeviation of 16 or higher is needed to get 1.0 tesselation. I simply think that the specific patch gets a lower deviation there. Maybe the 1/2 "tesselation" should simply be entirely avoided unless the patch is REALLY mostly planar (i.e. in your bestsquareddeviation < 0.01f case)?

[Asraniel]

great stuff going on here

[someone]

Sorry for not answering for a long time.
I see, my patch was partially applied. But some planar patches are tesselated badly anyway. Here's a quick fix:

Code: Select all

Index: curves.c
===================================================================
--- curves.c   (revision 8812)
+++ curves.c   (working copy)
@@ -160,18 +160,35 @@
{
   int c, x, y;
   const float *patch;
-   float deviation, squareddeviation, bestsquareddeviation;
+   float deviation, bestsquareddeviation;
   bestsquareddeviation = 0;
   for (y = 0;y < patchheight;y++)
   {
      for (x = 0;x < patchwidth-1;x += 2)
      {
-         squareddeviation = 0;
+         float squareddeviation = 0, aa_dp = 0, bb_dp = 0, ab_dp = 0;
+
         for (c = 0, patch = in + ((y * patchwidth) + x) * components;c < components;c++, patch++)
         {
+            float d1 = patch[2*components]-patch[0], d2 = patch[components]  -patch[0];
+            aa_dp += d1*d1;
+            bb_dp += d2*d2;
+            ab_dp += d1*d2;
+
            deviation = patch[components] * 0.5f - patch[0] * 0.25f - patch[2*components] * 0.25f;
            squareddeviation += deviation*deviation;
         }
+
+         // Special check for "planarity" of the curve
+         if (aa_dp < 0.01f)
+         {
+            squareddeviation = 0;
+         } else
+         if (bb_dp - ab_dp*ab_dp / aa_dp < 0.01f)
+         {
+            squareddeviation = 0;
+         }
+
         if (bestsquareddeviation < squareddeviation)
            bestsquareddeviation = squareddeviation;
      }
@@ -184,18 +201,34 @@
{
   int c, x, y;
   const float *patch;
-   float deviation, squareddeviation, bestsquareddeviation;
+   float deviation, bestsquareddeviation;
   bestsquareddeviation = 0;
   for (y = 0;y < patchheight-1;y += 2)
   {
      for (x = 0;x < patchwidth;x++)
      {
-         squareddeviation = 0;
+         float squareddeviation = 0, aa_dp = 0, bb_dp = 0, ab_dp = 0;
         for (c = 0, patch = in + ((y * patchwidth) + x) * components;c < components;c++, patch++)
         {
+            float d1 = patch[2*patchwidth*components]-patch[0], d2 = patch[patchwidth*components]  -patch[0];
+            aa_dp += d1*d1;
+            bb_dp += d2*d2;
+            ab_dp += d1*d2;
+
            deviation = patch[patchwidth*components] * 0.5f - patch[0] * 0.25f - patch[2*patchwidth*components] * 0.25f;
            squareddeviation += deviation*deviation;
         }
+
+         // Special check for "planarity" of the curve
+         if (aa_dp < 0.01f)
+         {
+            squareddeviation = 0;
+         } else
+         if (bb_dp - ab_dp*ab_dp / aa_dp < 0.01f)
+         {
+            squareddeviation = 0;
+         }
+
         if (bestsquareddeviation < squareddeviation)
            bestsquareddeviation = squareddeviation;
      }


I'll explain what it does a bit later (forgot my password to nn image hosting) so that you can change variables' names to something more meaningful. My english is too bad for this. (aa_dp, for example, now means "dot_product(a,a)". What is "a" will be clear from the image)

[divVerent]

This is exactly the change I refuse to apply, as I really don't understand it. Please keep out that "optimizing" and make it readable, like the previous code.

Especially as I can easily find a counterexample for your code: a 3x3 patch that's entirely planar, except that the midpoint is elevated. Your code will treat this patch as entirely planar, as the first check will always hit (dp_all will be zero).

On the other hand, if a patch is planar, the existing code will return a squared deviation near zero.

And how "badly" are they tesselated? As we're shortly before release this is URGENT.

[someone]

What this patch does:
1) The squared deviation is calculated for each group of 3 vertices of a big patch independently:

2) From the "side-view" these three vertices look something like this:

"h" is distance from middle vertex to line built on the left and right vertices. if "h"==0 then squared deviation is considered zero.
Sqr(h) = dot(a,a) - dot(a,b)*dot(a,b) / dot(b,b)

3) Why should we treat this case separately? Because the squared deviation calculated by existing code will be non-zero in such cases:

Though the row of vertices is obviously "planar".

This is exactly the change I refuse to apply, as I really don't understand it. Please keep out that "optimizing" and make it readable, like the previous code.

Especially as I can easily find a counterexample for your code: a 3x3 patch that's entirely planar, except that the midpoint is elevated. Your code will treat this patch as entirely planar, as the first check will always hit (dp_all will be zero).

Nope. In this case "h" will be non-zero for one of the rows of vertices => squared deviation will be calculated by already existing code.

On the other hand, if a patch is planar, the existing code will return a squared deviation near zero.

That is wrong. See case above. (Middle vertex shifted along the line connecting two others)

And how "badly" are they tesselated? As we're shortly before release this is URGENT.

Not patched and patched versions:

[tundramagi]

Wow (@ the screenshot.) That's an improvement if there are no bugs.

[divVerent]

Note that treating the part of the patch as planar may very well look worse, texcoord wise.

Still, there ought to be a cleaner, and especially, more symmetric way to do this that works without this weird division.

So maybe it would be better to replace the deviation formula by a READABLE and SYMMETRIC one that does not have this issue. Basically, this means to check how "linearily dependent" the three adjacent control points of the patch are. As "deviation" you could then see the distance of the middle point from the line.

[someone]

So maybe it would be better to replace the deviation formula by a READABLE and SYMMETRIC one that does not have this issue. Basically, this means to check how "linearily dependent" the three adjacent control points of the patch are. As "deviation" you could then see the distance of the middle point from the line.

That is exactly what I had done in my first patch, but it was rejected because it produced tesselation values slightly differrent from what produced existing code.
I'll try to think of another solution.

[divVerent]

Nope, it was rejected because it made many patches planar that should not be (looked very awful on some maps). The cause was that it chose tesselation 0 where the old code chose tesselation 1, probably because the logarithm formula yielded a value < 1.

Also, it was rejected because the code was simply unreadable. I tried hard to figure out what it even does DIFFERENT from the previous one, but could not find it out. And I don't commit code into svn that I cannot read, sorry. If you had put in explanations what you're doing, it might have gotten bugfixed and then applied.

Originally, I intended to wait until you made your promised version "in half a month or a bit more", but after that time was more over, I decided to take over the parts of the patch that I could read, as for all I could know, you've left and won't come back (I was wrong with that, but how could I have known).

So please keep your promise this time instead of letting us hang for ages again, so we can change the tesselation code ONE LAST TIME. Note that changing this code causes client-server differences about tesselation and this really annoys players on servers, so it shouldn't be done too often. Only stable code should be committed in this regard.