Development Blah

All other topics around Descent and D2X-XL

Moderators: Frustikus, simX, Aus-RED-5

User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Visibility Detection

Postby karx11erx » Sat May 28, 2011 1:27 pm

Since the new lightmap calculation is so slow, I have decided to look into Parallax' code for (point to point) visibility detection. Beginning at some start segment (i.e. the segment containing the start point), the legacy code basically recursively walks through all children of the current segment the line from start to endpoint traverses. That code has a bunch of flaws. First of all it suffers from numerical imprecisions. Then it doesn't explore all alternative segment routes to the destination, which can lead to failure in case of the line intersecting with a segments' vertex or edge. Finally, the code to determine whether a line intersects a face is rather slow and inefficient.

To sum it up: The entire code, and also the ideas to accelerate it and to compensate for numerical errors is a big bunch of crap, imvho. :rant:

Line-face intersection the Parallax way. This is a standard method, but a slow one. It works by reducing the problem to a 2D case by ignoring the dimension where the normal has its biggest component (i.e. is closest to being perpendicular to). Since Parallax tried to use quads instead of triangles as often as possible - even where that was a bad idea since the quad's two faces weren't co-planar, they had to use it. It still doesn't work right for quads with two non-planar triangles.

This is the original code:

Code: Select all

//see if a point in inside a face by projecting into 2d
uint check_point_to_face(vms_vector *checkp, side *s,int facenum,int nv,int *vertex_list)
{
   vms_vector_array *checkp_array;
   vms_vector_array norm;
   vms_vector t;
   int biggest;
///
   int i,j,edge;
   uint edgemask;
   fix check_i,check_j;
   vms_vector_array *v0,*v1;

   #ifdef COMPACT_SEGS
      get_side_normal(sp, s-sp->sides, facenum, (vms_vector *)&norm );
   #else
      memcpy( &norm, &s->normals[facenum], sizeof(vms_vector_array));
   #endif
   checkp_array = (vms_vector_array *)checkp;

   //now do 2d check to see if point is in side

   //project polygon onto plane by finding largest component of normal
   t.x = labs(norm.xyz[0]); t.y = labs(norm.xyz[1]); t.z = labs(norm.xyz[2]);

   if (t.x > t.y) if (t.x > t.z) biggest=0; else biggest=2;
   else if (t.y > t.z) biggest=1; else biggest=2;

   if (norm.xyz[biggest] > 0) {
      i = ij_table[biggest][0];
      j = ij_table[biggest][1];
   }
   else {
      i = ij_table[biggest][1];
      j = ij_table[biggest][0];
   }

   //now do the 2d problem in the i,j plane

   check_i = checkp_array->xyz[i];
   check_j = checkp_array->xyz[j];

   for (edge=edgemask=0;edge<nv;edge++) {
      vec2d edgevec,checkvec;
      fix d;

      v0 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+edge]];
      v1 = (vms_vector_array *)&Vertices[vertex_list[facenum*3+((edge+1)%nv)]];

      edgevec.i = v1->xyz[i] - v0->xyz[i];
      edgevec.j = v1->xyz[j] - v0->xyz[j];

      checkvec.i = check_i - v0->xyz[i];
      checkvec.j = check_j - v0->xyz[j];

      d = fixmul(checkvec.i,edgevec.j) - fixmul(checkvec.j,edgevec.i);

      if (d < 0)                    //we are outside of triangle
         edgemask |= (1<<edge);
   }

   return edgemask;

}


:vomit: :clue:

This is the same code, but has been streamlined substantially by me:

Code: Select all

uint CSide::PointToFaceRelation (CFixVector& intersection, short iFace, CFixVector vNormal)
{
   CFixVector    t;
   int           h, i, j, nEdge, nVerts, projPlane;
   uint          nEdgeMask;
   CFixVector*   v0, *v1;
   CFixVector2D  vEdge, vCheck, vRef;

//project polygon onto plane by finding largest component of Normal
t.Set (labs (vNormal.v.coord.x), labs (vNormal.v.coord.y), labs (vNormal.v.coord.z));
if (t.v.coord.x > t.v.coord.y)
   projPlane = (t.v.coord.x > t.v.coord.z) ? 0 : 2;
else
   projPlane = (t.v.coord.y > t.v.coord.z) ? 1 : 2;
if (vNormal.v.vec [projPlane] > 0) {
    i = ijTable [projPlane][0];
    j = ijTable [projPlane][1];
   }
else {
    i = ijTable [projPlane][1];
    j = ijTable [projPlane][0];
   }
//now do the 2d problem in the projection plane
vRef.i = intersection.v.vec [i];
vRef.j = intersection.v.vec [j];
nVerts = 5 - m_nFaces;
h = iFace * 3;
v1 = VERTICES + m_vertices [h + nEdge];
for (nEdge = 1, nEdgeMask = 0; nEdge <= nVerts; nEdge++) {
   v0 = v1;
   v1 = VERTICES + m_vertices [h + nEdge % nVerts];
   vEdge.i = v1->v.vec [i] - v0->v.vec [i];
   vEdge.j = v1->v.vec [j] - v0->v.vec [j];
   vCheck.i = vRef.i - v0->v.vec [i];
   vCheck.j = vRef.j - v0->v.vec [j];
   if (FixMul64 (vCheck.i, vEdge.j) - FixMul64 (vCheck.j, vEdge.i) < 0)   //we are outside of triangle
      nEdgeMask |= (1 << (nEdge - 1));
   }
return nEdgeMask;
}


This is a faster and more elegant method (Barycentric method, courtesy the internets). Basically it expresses the reference point relative to a triangle corner, using two triangle edges: P = A + u * (C - A) + v * (B - A), where P is the reference point (intersection of the line with the triangle's plane), and A,B,C are the triangle vertices. The point is inside the triangle if (u >= 0 && v > 0 && u + v <= 1). You can also easily tell "behind" which edges of the triangle the reference point is when it's outside the triangle. All segment sides need to be split into triangles for this method, but this doesn't hurt anymore, given the speed and amount of memory even low-end computers have these days.

Code: Select all

// return 0 if point inside triangle, otherwise bit-wise coded edges the point is behind as seen from inside the triangle
ubyte PointIsOutsideFace (CFloatVector* refP, CFloatVector vNormal, CFloatVector* vertices, short nVerts)
{
CFloatVector v0 = vertices [2] - vertices [0];
CFloatVector v1 = vertices [1] - vertices [0];
CFloatVector v2 = *refP - vertices [0];
float dot00 = CFloatVector::Dot (v0, v0);
float dot11 = CFloatVector::Dot (v1, v1);
float dot01 = CFloatVector::Dot (v0, v1);
float dot02 = CFloatVector::Dot (v0, v2);
float dot12 = CFloatVector::Dot (v1, v2);
float invDenom = 1.0f / (dot00 * dot11 - dot01 * dot01);
float u = (dot11 * dot02 - dot01 * dot12) * invDenom;
float v = (dot00 * dot12 - dot01 * dot02) * invDenom;
return (int (u < -0.001f)) + ((int (v < -0.001f)) << 1) + ((int (u + v > 1.001f)) << 2); // compensate for numerical errors
}


I wonder how many more problems and flaws (i.e. robots penetrating walls) would suddenly and miraculously disappear if this math would be done right.

In my book, "Parallax" stands for "Painful Programing" already. :rofl:
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Lightmaps improved, again

Postby karx11erx » Mon May 30, 2011 1:27 am

After having toiled through the path finding and visibility detection code for hours and hours again, I have managed to improve both lightmap quality and calculation speed. The render menu has a new setting in expert mode allowing to adjust lightmap precision (that's how much effort D2X-XL invests in detecting which areas are actually visible to a light source, and which aren't). The standard setting is the medium one, which works sufficiently fast (for me :mrgreen: ). If lightmap calculation is too slow on your system, you can try to use basic precision. You may also want to try and decrease lightmap quality, since that directly relates to lightmap size and hence btw. also to memory consumption. So please don't try to produce lightmaps at the highest settings for Anthology or so on such a machine: Even if you have the patience, the resulting lightmaps will probably not fit into your computer's graphics memory. :P

One disclaimer: Since the new math is more precise than the previous one, flaws in level design (like minimally distorted faces or adjacent faces not laying in the same plane) may be relentlessly revealed by the lightmap calculation. Don't bother posting bug reports for that.

Btw, the last few D2X-XL OpenMP releases for Windows seem to have been delivered w/o fully optimized code, so you might be delighted by a certain speed boost with the next version (which I will publish tomorrow). ;)

Edit:

I have been creating lightmaps for a few of my levels now, and I am really happy about what I am seeing there. The new lightmap code is a big leap in the right direction. The levels look just marvellous with the new lightmaps, and there are no ugly, exaggerated saturation effects. Enjoying the fruit of hard work is such a satisfying experience.

:laola:
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Lightmap fixes

Postby karx11erx » Tue May 31, 2011 12:27 am

Oh well, when trying to enjoy the fruit of my hard work, I promptly stumbled over flaws in my hard work. :roll:

:lol:

Looking at some levels with more sophisticated structure (like, cough, Boiling Point) it became rather obvious that something went rather wrong with lightmap calculation in certain spots, like let's say behind light sources. Many doors (even in not so sophisticated levels, like Descent 2's first level) also had a funny triangle pattern with quite a disturbing effect when being frequently watched.

Fortunately I managed to pin down and fix the causes of these flaws.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Tue May 31, 2011 7:18 pm

During my testing the new lightmap code I noticed a flickering caused by light from dynamic light sources (e.g. from objects or destructible lights) that depending on level structure and visible area could become extremely annoying. This flickering only happened when multi threading was used. Actually I had thought that I had adressed that problem in the proper way long time ago, but looking at the code and pondering a bit on what multiple threads of it would do it became clear very soon that this wasn't the case. So I improved my solution, and it looks like the problem is (as good as) gone. Some slight light variation due to different normals used for computing the light at a vertex may still happen, but as far as I could see it is negligible, if it can be noticed at all.

A nice side effect of all my recent work is that the light calculation code has been streamlined quite a bit and is more efficient and correct than it was before.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

More lightmap improvements

Postby karx11erx » Wed Jun 01, 2011 12:17 pm

There had been a few quirks left in lightmap calculation which I have tackled today. One of them was dark artifacts at face edges, and another one was faces adjacent to light sources being too light or too dark. I could fix both of these issues (one of them was caused by numerical errors). I also found the new dynamic lighting code producing too harsh transitions between faces, so I replaced it with a physically less correct, but better looking approximation. Ambient light intensity has also been reduced and now equals OpenGL's standard value (0.2).

The real deal however was to add blur to lightmaps, resulting in beautiful shadows with nice, soft edges. This also makes low resolution lightmaps look at least acceptable now. Please don't ask me to add contact hardening though. :P

Image

(The shadows cast by the steel applications on the walls are not produced by D2X-XL, but have been baked into the texture)

I will need to look into a few compiler issues Darklord42 has with the OS X version, and once these will have been removed, v.221 will be released.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Wed Jun 01, 2011 11:42 pm

Bleh, when I thought that everything was finally fine and dandy, another bug cropped up, causing weird lighting flaws with dynamic lights (like gun shots or flares). Fortunately it turned out that it was simply caused by a line of test code I had forgotten to remove. I had at least been smart enough to add a comment "// test!" to it, so when the debugger hit that line, I immediately realized what was going wrong.


I would like to take the opportunity to say a big thank you to Darklord42 who has taken it upon him to bring the outdated XCode project for the Mac OS X build of D2X-XL up to scratch and is very quickly and reliably providing the OS X D2X-XL community with program updates. Wonderful - thank you, man! :cheers:
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Fri Jun 03, 2011 7:16 pm

Today I have fixed another small glitch in D2X-XL's lighting (which is actually owed more to Descent's level structure than to D2X-XL light calculation). Since in Descent lights are just overlay textures slapped onto a segment's side, D2X-XL can't but consider the entire side a light emitter, making it fully bright. This caused a sharp brightness gradient to adjacent faces where the regular light calculation depending on face direction (normal) and light direction kicked in. I have made a small adjustment to the code to create a smooth brightness gradient in such cases, which compensates quite nicely for this level structure induced flaw.

The proper way to create lights in new levels would of course be to fit the side the light sits on as tightly to the light texture as possible. With DLE-XP's automatic segment splitting function this isn't a hard thing to do.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Wed Jun 22, 2011 6:02 pm

I am just looking into some visibility culling related code, and I have come across this:

Code: Select all

#define WID_FLY_FLAG      1
#define WID_RENDER_FLAG     2
#define WID_RENDPAST_FLAG     4
#define WID_EXTERNAL_FLAG   8
#define WID_CLOAKED_FLAG   16

#define WID_WALL                          2   // 0/1/0   wall
#define WID_TRANSPARENT_WALL    6   // 0/1/1   transparent wall
#define WID_ILLUSORY_WALL           3   // 1/1/0   illusory wall
#define WID_TRANSILLUSORY_WALL 7   // 1/1/1   transparent illusory wall
#define WID_NO_WALL                     5   // 1/0/1   no wall, can fly through

The Parallax coders had been wildly mixing these defines when using them, without adding any meaningful comment about what they're doing there. You have to guess it all from the code. I am not going to comment this any further.

A better way to implement this would have been

Code: Select all

#define WID_PASSABLE_FLAG   1
#define WID_VISIBLE_FLAG   2
#define WID_SEETHRU_FLAG   4
#define WID_EXTERNAL_FLAG   8
#define WID_CLOAKED_FLAG   16

#define WID_SOLID_WALL            WID_VISIBLE_FLAG
#define WID_TRANSPARENT_WALL      (WID_VISIBLE_FLAG | WID_SEETHRU_FLAG)
#define WID_ILLUSORY_WALL         (WID_PASSABLE_FLAG | WID_VISIBLE_FLAG)
#define WID_TRANSILLUSORY_WALL    (WID_ILLUSORY_WALL | WID_SEETHRU_FLAG)
#define WID_NO_WALL               (WID_PASSABLE_FLAG | WID_SEETHRU_FLAG)

That way the second set of flags would immediately have been discernable as a meaningful combination of basic portal visibility/passability properties.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

SDL

Postby karx11erx » Thu Jul 21, 2011 11:56 pm

Today I have read that SDL (a library to simplify device access) was developed by Sam Lantinga during his time as lead developer for Loki software. Sam Lantinga is now working for Blizzard, but is also still a main contributor to SDL.

Man, the SDL code is a badly programmed mess. If somebody coding like that can be a lead dev for a game company, and can work for Blizzard, what quality standards are such companies up to?

I know this may sound arrogant, but I don't envy the guy's success, and SDL really is a badly programmed mess. Just take a look into it yourself.

:wallbash:

And please don't take D2X-XL as a measuring rod for my programming skills and style. It is not. I was always limited by my approach of tidying and expanding on what was there. If I'd write it from scratch, it would have a completely different structure and architecture.
Frustikus
D2X-XL Team
D2X-XL Team
Posts: 778
Joined: Mon Oct 22, 2007 3:06 pm
Location: Germany

Re: SDL

Postby Frustikus » Fri Jul 22, 2011 11:19 pm

karx11erx wrote: ...If I'd write it from scratch, it would have a completely different structure and architecture.


Maybe the goal for d2x-xl 2.0.0.0 ? :-P

Maybe SDL was his first project in early days and he doesn´t want to write it completely new ? Maybe it is not representative for his skills today ?
But I agree that some game developing companys do have a problem with quality management. The long list of unplayable games after their releases is a bad fact. That may be a result of unskilled leaders.
Intel Q9550 (E0) @ 3420 MHz and standard voltage with Sonic Tower Rev.2, Geforce GTX 260 (896 MB), Asus P5Q Deluxe, 6 GB GSkill DDR2-1066, 2x500 GB Seagate @ Raid 0, Soundblaster XFi, Sharkoon Rebel12 Case, Teufel Concept Magnum 5:1, Samsung 2494 SW , Genius Navigator 535, Logitech Wingman FF, Windows 7 Ultimate 64 bit
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Sat Jul 23, 2011 6:43 am

SDL isn't that old (about 10 years). They are rewriting it currently, but what I have seen from the SDL 1.3 code didn't convince me.
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

A look back on v1.15

Postby karx11erx » Thu Jul 28, 2011 9:45 am

D2X-XL v1.15 is around for quite a while now, having gathered over 200 entries in its changelog, and so I thought I write a little retrospect, bringing its main features back into memory. So here's the major additions and improvements v1.15 has brought:

  • Anaglyph stereoscopic rendering
  • Support for three different player ship types
  • Vastly improved lightmaps
  • Realtime glow
  • Rain and snow particle fx
  • External tracker support via XML queries
  • Improved level building and modding support (directed exits, mission configs)
  • Shockwave effect w/ frame postprocessing
  • Much improved explosions with a gorgeous shrapnel effect
  • Improved RADAR
  • Particles are handled more efficiently
  • The game runs much better on low end machines
  • Improved shadow rendering creating soft shadows
  • Better collision handling

Besides these improvements, roughly 300 bug fixes have contributed to making D2X-XL a lot more stable and offer a smooth gaming experience.

I can seeeee you!
Image

The first pico second of a thermonuclear explosion:
Image

No, this isn't Descent 3!
Image

The firy blossom of destruction:
Image
User avatar
Guidebot2
Posts: 49
Joined: Mon Jul 04, 2011 10:48 am
Location: Alba Iulia,Romania
Contact:

Re: Development Blah

Postby Guidebot2 » Thu Jul 28, 2011 10:39 am

WOW! :D :!: :!: :!: :!: :!: :!: :!:
D2X-XL is the best!!!
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Re: Development Blah

Postby karx11erx » Thu Jul 28, 2011 10:57 pm

When playing around with Yokelassence's mission Dimensional Intersect with its truly epic proportions, I noticed ominous crashes when zooming out on the textured automap and rotating it a bit. After a while I found out that the transparency renderer failed to get enough memory for its buffers. This is strange, so I thought, and looked at how much memory it wanted; shouldn't be much according to my guesstimation. I couldn't have been more wrong. The transparency renderer requested a whopping 290 MB. :horror: :crazy:

The reason why it had come to this horrendous value was that the transparency renderer kept 250.000 slots for transparent items, making each slot big enough for the biggest possible item data set (which happened to have 1160 bytes and never appeared more than a few dozen times per frame).

Now the transparency renderer should have handled its out of memory condition quite nicely, but apparently it did not in all cases ... hence it crashed the program. Now this only happened on my machine because I had loaded a huge level and had a bunch of other memory hungry apps running, or I would have never seen it. On computers with low memory, D2X-XL may have crashed as soon as a rocket was fired and the program tried to create its smoke trail. D'uh. :oops:

So I rewrote the memory management of the transparency renderer, reducing the memory footprint to 10 MB (maybe 20 MB if further tests show that more is required).

Edit:

After some tests even 5 MB seem to be plenty. This means a decrease of over 98%!

:cheers:
User avatar
karx11erx
D2X-XL Master
D2X-XL Master
Posts: 8112
Joined: Mon Sep 24, 2007 8:48 pm
Location: Wilferdingen, Germany
Contact:

Precomputed lightmaps

Postby karx11erx » Sun Jul 31, 2011 7:34 pm

Since the lightmap code and data format seems very stable now, I have started to precompute lightmaps for various Descent missions. The main criterion is level complexity (i.e. the maps are so huge that lightmap calculation on any other but a highend computer takes ages), followed by coolness and popularity (it shouldn't surprise you that my own missions are very popular with me, should it? ;)).

The missions currently on my list are:

  • Descent 1: First Strike (Parallax)
  • Descent 2: Counter Strike (Parallax)
  • Descent 2: Vertigo (Parallax)
  • Anthology (Sirius)
  • Year Of The Tiger (Sirius)
  • The Sphere (Yokelassence)
  • Dimensional Intersect (Yokelassence)
  • Kartsal Motivation Demo (Pumo)
  • Boiling Point (me)
  • Warp Shockwave (me)
  • Lunar Outpost Reloaded (me)
  • Descent: The Enemy Within (DarkFlameWolf et. al.)
  • Descent Vignettes (DarkFlameWolf et. al.)
  • Descent: Chaos Theory XL (DarkFlameWolf)

More missions will follow later.

I will precompute the lightmaps at standard quality and pack them with the mission archives, including the proper folders.

Return to “General Discussions”

Who is online

Users browsing this forum: No registered users and 1 guest