Hi there. First, i'd like to thank you all for making such a good game! It became my favourite fps.
Second, i have made a patch that fixes some bugs and improves performance of rendering curved surfaces while the quality stays the same.
Originally, DarkPlaces used too many excess polygons for curves tesselation:

Fixed that.

Moreover, fixed a bug with incorrect degenerate triangle detection (Under certain circumstances holes could appear in curved surfaces). And finally made lower LOD for collision detection purposes work. (Though corresponding cvars "r_subdivision_collision_*" existed, it actually didn't work because of a typo in model_brush.c)

It makes rendering of "mentalspace" map 7% faster on my machine. (If collision detection is taken in account, it is even more). And 11% of "hookrace".

There is actually no "patch", just already patched source files. They are compatible with latest svn version of DP. Just replace and compile. Here: ftp://194.88.211.162/publicprojects/nexpatch.7z
It will be there for a couple of days.

The old "holes-between-patches" bug was fixed in svn some weeks back. I havn't seen a hole since then...

The part about fewer polygons sounds interesting though

Very nice work

morfar wrote:The old "holes-between-patches" bug was fixed in svn some weeks back. I havn't seen a hole since then...

The part about fewer polygons sounds interesting though

There was not only holes-between-patches but also holes-IN-patches bug. It was very rare.

torus wrote:Very nice work

Thanks.

Please test it for bugs. I don't have many "heavily curved" maps and enough time.

Very good job!

As for testing, this might help ya:
http://maps.nexuizninjaz.com/Theta_v1r2.pk3

Really need this in proper patch form and not single source files that may be based on ANYTHING, and with explanation WHAT you are changing, as it is very likely that this breaks OTHER maps.

The current code in DP SVN (no idea if you even tried that one, or if you worked on the 2.4.2 sources) matches what q3map2 -patchmeta and Quake 3 Arena do, and should perhaps be the best thing to do. It would need LOTS of testing to accept this, as this might tear NEW holes on other maps that look fine in Q3A.

In case you did base it on a svn revision, please state the revision number so we know what to diff against.

divVerent wrote:Really need this in proper patch form and not single source files that may be based on ANYTHING, and with explanation WHAT you are changing, as it is very likely that this breaks OTHER maps.

The current code in DP SVN (no idea if you even tried that one, or if you worked on the 2.4.2 sources) matches what q3map2 -patchmeta and Quake 3 Arena do, and should perhaps be the best thing to do. It would need LOTS of testing to accept this, as this might tear NEW holes on other maps that look fine in Q3A.

In case you did base it on a svn revision, please state the revision number so we know what to diff against.

It is based on DP svn revision 8670 (latest at this time).
I decided to publish it now for testing purposes, because i think it will be very useful for people that have not so powerful machines. Final version (commented and heavily tested) will come in half a month or a bit more because i need to pass some exams first. Some optimizations are not implemented but it is completely usabe by now. The new code is poorly commented at this point though.
It breaks no standard maps (tested on farewell, skyway, reslimed, darkzone, downer, ruiner, bluesky, basement, bloodprison, evilspace, slimepit, soylent, warfare) and some additional (theta, hookrace, mentalspace, racetrack_v2, facing_worlds, streetrace). I'll do more testing later.

Add: it was my mistake to post second screenshot pair where one of them was from 2.4.2. In 2.4svn seam is really fixed.
Add2: i find the patch useful (20% faster on "theta" map) enough to be merged to trunk so more people can test it. Any bugs that will possibly be found will be fixed by me. Anyway, it may be reverted at any time.

This fix might be related to clueless newbie's report of having holes in his map.

Neither I nor LordHavoc really have any idea what you did to Q3PatchTesselationOnX and Q3PatchTesselateFloat.

But they certainly cause bad (too low) tesselation of mikeeusa's map tundramagi at the default tolerance:

http://emptyset.endoftheinternet.org/~r ... 95efad.jpg

Apparently, it gets tesselation 0 in the "hallway", which is totally wrong, as you see. Looks like the decision for the tesselation 0 needs to be done another way.

And why isn't this patch welded to the trim, like previously?

And really: don't waste time on "optimizing". It's done at map load ONLY. Who cares if that takes a millisecond longer? Better make the code readable, it's currently a horrible mess and hard to decipher.

The wrong usage of the collision cvars, and the triangle degenerate check, is now fixed in svn. Thanks for pointing to it.

> Neither I nor LordHavoc really have any idea what you did to Q3PatchTesselationOnX and Q3PatchTesselateFloat.
I'll make a description of what I have done later.

> But they certainly cause bad (too low) tesselation of mikeeusa's map tundramagi at the default tolerance:
New Q3PatchTesselationOnX/Y take care of one curious case when old ones generated completely useless polygons. It computes a bit different squared deviation. A linear factor can be guessed so that the results of old and new ones will nor differ in 99% of cases. Though, it can be easily reverted and patched to take the possibility of 1/2 tesselation in acount. I'll do that.

> Apparently, it gets tesselation 0 in the "hallway", which is totally wrong, as you see. Looks like the decision for the tesselation 0 needs to be done another way.
It's totally right for the "long" dimension, I think. There is no need to split it in two equal parts. And for the other dimension it is > 0.

> And why isn't this patch welded to the trim, like previously?
Because the two not-welded patches do not have common vertices. That is ok, Quake3 does the same:

(It cannot load such huge level so I cut a piece of it and made a small room) As you see, it does not care about welding these two patches, contrary to "vertex-touching" patches.

> And really: don't waste time on "optimizing". It's done at map load ONLY. Who cares if that takes a millisecond longer? Better make the code readable, it's currently a horrible mess and hard to decipher.
Ok, I'll try my best to make it more readable next time.

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)?

great stuff going on here

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)

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.

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:

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

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.

divVerent wrote: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.

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.