Send reply to:    <@one.net.au>
From:             "M&V Cairns" <cairns@one.net.au>
To:               <lebe@geocities.com>
Subject:          3D Foundation Classes help questions
Date sent:        Sat, 25 Jul 1998 07:31:27 +1000

Hi Leandro,

I saw your page from the 3D Engines List and thought I might help a little
with your questions.
I am interested in the concept of portal rendering, it seems to be a very
efficient way of solving
the VSD (visible surface determination) problem, the main thing stopping me
using it is how to
get sector information. I have a few ideas:

First, I know of no 3D editor that will make convex sectors from an
arbitrary scene.
But I have this idea which requires processing the 3D editor's polygon list
before using the data in your program. It goes like this:
1) build a temporary 3D BSP tree. A side effect of BSP creation is that it
divides space into
some convex subspaces (bounded by convex polygons).
2) Once the tree is built, you can traverse it and store portal information
between sectors.
3) Then you can discard the BSP heirarchy info, it's done its job.
This can all be done off-line by a separate program, no need to slow down
the engine :)
I haven't tried this idea yet, but it sounds good. The difficult part might
be working out which
sector is next to which inthe tree, and also working out the portal
polygons (might not need to do this).
For info on 3D BSP creation, see the article by Mike Abrash linked in the
3D Engines List,
and explained in his 'Zen of Graphics' or 'Black Book'. Also id Software's
site contains the
code for their BSP builder they used to make Quake. (i think the module is
called QBSP).

Second, collision detection. I haven't looked at your code so you might be
doing this already?
To detect collision of a sphere with a plane: take the dot product of the
sphere center (in world
space) with the plane's normal. compare this value with the sphere's
radius. If the dot product
is less than the radius, the sphere has intersected with the plane, and the
difference is how far
into the plane it went. Maybe you do this already.
What I don't know is how to handle collisions with more than 1 ploy at the
same time. If you
do the above algorithm once for each poly, it will work for non-acute and
right-angled corners,
but not for acute corners (less than 90 degrees). If you solve this
problem, please let me know...

Third, subdivision texture mapping is great! I have written some code that
uses it (see below).
The idea is that affine tmap looks good up to about 16 pixels, then it
starts to bow and 
twist if you look at a big poly from the side. The idea is to perspective
correct the affine span every 16
(or 8 or whatever) pixels. The full perspective correct tmap is extremely
slow, but doing it every 16 pixels
is a good trade-off for better texture quality. Some people say you can do
a floating point divide (for perspective)
in parallel with your integer code (the FPU is a separate device on intel
CPUs) but i find fixed point integer
code fast enough. First scan convert the poly into a table of spans, then
for each span:

#define SPANDIV 16                 // span perspective correction interval

// output a texture mapped span using affine tmap perspective corrected
every SPANDIV pixels.
// pass in screen row (y) and start column (sx) and end column (ex)
void outspan(int y, int sx, int ex) { // draw a texture span
  float u0, v0, w0, u1, v1, w1;
  fix_t fu0, fv0, fdu, fdv;
  int len, e, last = 0;

  // calculate address of the start pixel in the frame buffer
  char* dest = &vid_frame[y][sx];

  // work out the texture coordinates at this point
  // nb: don't have to this if you pass in U and V, but still have to
divide by Z.
  w0 = 1 / (sx * texw.x + y * texw.y + texw.z);
  u0 = (sx * texu.x + y * texu.y + texu.z) * w0;
  v0 = (sx * texv.x + y * texv.y + texv.z) * w0;

  // chop up the span into SPANDIV pixel subspans
  while ((len = ex - sx) > 0) {
    if (len > SPANDIV)
      len = SPANDIV;
    else
      last = 1;
    e = sx + len - last;   // we don't draw the last pixel so polys fit
together

    // work out the texture coordinates at the end of the subspan
    w1 = 1 / (e * texw.x + y * texw.y + texw.z);
    u1 = (e * texu.x + y * texu.y + texu.z) * w1;
    v1 = (e * texv.x + y * texv.y + texv.z) * w1;

    // turn the texture start point into fixed point format
    fu0 = (fix_t)(65536 * u0);
    fv0 = (fix_t)(65536 * v0);

    // work out the fixed point delta per pixel
    fdu = ((fix_t)(65536 * u1) - fu0) / len;
    fdv = ((fix_t)(65536 * v1) - fv0) / len;

    // prepare for the next subspan
    sx += len;
    u0 = u1;
    v0 = v1;

    // output the affine span component
    do {
      *dest++ = texrows[fv0 >> 16][fu0 >> 16];
      fu0 += fdu;
      fv0 += fdv;
      } while (--len);
    }
}

There it is. With a little work I'm sure it can be made faster.
If you don't use a screen space to texture space matrix (texu, texv, texw)
you can do it
with u and v coordinates passed in. You then have to divide them by the
pixel depth (w) which is also passed
in. The inner loop is a standard affine tmap.

Hope this all gives you some ideas,
Cheers.

-- Matt Cairns cairns@one.net.au

