Logo Search packages:      
Sourcecode: plib version File versions

ssgLoadFLT.cxx

/*
     PLIB - A Suite of Portable Game Libraries
     Copyright (C) 1998,2002  Steve Baker
 
     This library is free software; you can redistribute it and/or
     modify it under the terms of the GNU Library General Public
     License as published by the Free Software Foundation; either
     version 2 of the License, or (at your option) any later version.
 
     This library is distributed in the hope that it will be useful,
     but WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Library General Public License for more details.
 
     You should have received a copy of the GNU Library General Public
     License along with this library; if not, write to the Free Software
     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
 
     For further information visit http://plib.sourceforge.net

     $Id: ssgLoadFLT.cxx 1762 2003-04-17 13:10:12Z stromberg $
*/

//
//  $Id: ssgLoadFLT.cxx 1762 2003-04-17 13:10:12Z stromberg $
//
//
//    OpenFlight loader for SSG
//
//
//  The loading of FLT files can to some degree be controlled by 
//  setting environment variables:
//     
//     FLTNOCLEAN   - if set disables all kinds of scene graph optimisations
//     FLTNOEXT     - ignore external references
//     FLTNOTEX     - disables textures altogether
//     FLTNOMIPMAP  - configure textures for bilinear filtering (no mipmaps)
//
//
//  Some known issues:
//
//  1. The color table in v14.0 and earlier is defined differently and
//     cannot be parsed. It may consist of 16 colours of 16 brightnesses
//     each, and the RGB values are passed as shorts.
//
//  2. Geometry in v11.0 and earlier are defined using obsolete records
//     (opcodes 6, 7, 8 and 9). Need specifications to parse them.
//
//  3. How to find external files properly. Some loaders (most notably 
//     IRIS Performer and MultiGen) uses the variable FLTEXTERNPATH.
//     (MultiGen also uses FLTPATH and TXTPATH I think).
//
//  4. How to do mmap on Mac and PS2.
//
//  5. No optimisations are done on the geometry. New triangle strip
//     generation code planned for SSG, and should be used when ready.
//
//  6. Optimisation done on the scene graph level are minimal. 
//
//
//
/*
 * Another OpenFlight loader for Performer
 * Copyright (C) 1998-2000  Marten Stromberg
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the Free
 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "ssg.h"
#include "ssgLoaderWriterStuff.h"

/* define this to compile against older versions of SSG */
/*#define NO_LOADER_OPTIONS*/

/* debug */
/*#define NO_LIGHTING*/
/*#define NO_TEXTURES*/
/*#define NO_COLORS*/

/* Try to figure out how to do mmap. */
#ifdef UL_WIN32
# define USE_WIN32_MMAP
#else
# include <unistd.h>
# ifdef _POSIX_MAPPED_FILES
#  define USE_POSIX_MMAP
# endif
#endif

#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <stdio.h>
#ifdef UL_IRIX
# include <sys/endian.h>
#endif
#ifdef USE_POSIX_MMAP
# include <time.h>
# include <sys/time.h>   /* Need both for Mandrake 8.0 !! */
# include <sys/stat.h>
# include <sys/mman.h>
#endif
#ifdef UL_MSVC
# include <io.h>
#endif


#ifndef O_BINARY
# define O_BINARY 0
#endif

#ifndef R_OK
# define R_OK 4
#endif

#ifndef ABS
# define ABS(x) ((x)>=0?(x):-(x))
#endif
#ifndef MIN
# define MIN(a,b) ((a)<=(b)?(a):(b))
#endif
#ifndef MAX
# define MAX(a,b) ((a)>=(b)?(a):(b))
#endif
#define MIN3(a,b,c) ((a)<=(b)?MIN(a,c):MIN(b,c))
#define MAX3(a,b,c) ((a)>=(b)?MAX(a,c):MAX(b,c))
#define CLAMP(x,lo,hi) ((x)<=(lo)?(lo):(x)>=(hi)?(hi):(x))

#define template _template /* trams */

typedef unsigned char ubyte;

#ifdef UL_WIN32
typedef unsigned short ushort;
typedef unsigned int uint;
#endif

// 525 = negative identation, 539= did not expect positive identation
//lint -save -e525 -e539

/*
 * byte sex 
 */

/* XXX what about PDP_ENDIAN? */

/* Help! Is this correct? */
#if (!defined(BYTE_ORDER) && defined(UL_WIN32) && !defined(NOT_INTEL_BYTE_ORDER))
# define LITTLE_ENDIAN  1234
# define BIG_ENDIAN     4321
# define BYTE_ORDER     LITTLE_ENDIAN
#endif

/* #undef BYTE_ORDER */

#if !defined(BYTE_ORDER) || BYTE_ORDER != BIG_ENDIAN

#if !defined(BYTE_ORDER)
static void _swab16(const void *src, void *dst, int n)
{
   ushort *s = (ushort *)src;
   ushort *d = (ushort *)dst;
   while (n--) {
      ushort t = *s++;
      *d++ = (((t & 0xff00U) >> 8) |
            ((t & 0x00ffU) << 8));
   }
}
#endif

static void _swab32(const void *src, void *dst, int n)
{
   uint *s = (uint *)src;
   uint *d = (uint *)dst;
   while (n--) {
      uint t = *s++;
      *d++ = (((t & 0xff000000U) >> 24) |
            ((t & 0x00ff0000U) >> 8) |
            ((t & 0x0000ff00U) << 8) |
            ((t & 0x000000ffU) << 24));
   }
}

static void _swab64(const void *src, void *dst, int n)
{
   /* XXX how to check if 64-bit integers are available?? */
   uint *s = (uint *)src;
   uint *d = (uint *)dst;
   while (n--) {
      uint t0 = *s++;
      uint t1 = *s++;
      *d++ = (((t1 & 0xff000000U) >> 24) |
            ((t1 & 0x00ff0000U) >> 8) |
            ((t1 & 0x0000ff00U) << 8) |
            ((t1 & 0x000000ffU) << 24));
      *d++ = (((t0 & 0xff000000U) >> 24) |
            ((t0 & 0x00ff0000U) >> 8) |
            ((t0 & 0x0000ff00U) << 8) |
            ((t0 & 0x000000ffU) << 24));
   }
}

#endif

#if !defined(BYTE_ORDER) || BYTE_ORDER != LITTLE_ENDIAN

static void _copy16(const void *src, void *dst, int n)
{
   memcpy(dst, src, 2*n);
}

static void _copy32(const void *src, void *dst, int n)
{
   memcpy(dst, src, 4*n);
}

static void _copy64(const void *src, void *dst, int n)
{
   memcpy(dst, src, 8*n);
}

#endif


#if defined(BYTE_ORDER) && BYTE_ORDER == BIG_ENDIAN

/* big endian */

inline uint get16u(const void *ptr)
{
   return *(ushort *)ptr;
}

inline uint get32u(const void *ptr)
{
   return *(uint *)ptr;
}

#define get16v _copy16
#define get32v _copy32
#define get64v _copy64

#elif defined(BYTE_ORDER) && BYTE_ORDER == LITTLE_ENDIAN

/* little endian */

inline uint get16u(const void *ptr)
{
   ushort tmp = *(ushort *)ptr;
   return (((tmp & 0xff00U) >> 8) |
         ((tmp & 0x00ffU) << 8));
}

inline uint get32u(const void *ptr)
{
   uint tmp = *(uint *)ptr;
   return (((tmp & 0xff000000U) >> 24) |
         ((tmp & 0x00ff0000U) >> 8) |
         ((tmp & 0x0000ff00U) << 8) |
         ((tmp & 0x000000ffU) << 24));
}

#define get16v _swab16
#define get32v _swab32
#define get64v _swab64

#else

/* any endian */

inline uint get16u(const void *ptr)
{
   ubyte *u = (ubyte *)ptr;
   return (((uint)u[0] << 8) | 
         ((uint)u[1] << 0));
}

inline uint get32u(const void *ptr)
{
   ubyte *u = (ubyte *)ptr;
   return (((uint)u[0] << 24) | 
         ((uint)u[1] << 16) | 
         ((uint)u[2] << 8) | 
         ((uint)u[3] << 0));
}

static void (*get16v)(const void *, void *, int);
static void (*get32v)(const void *, void *, int);
static void (*get64v)(const void *, void *, int);

#define PROBE_ENDIAN 1

#endif

#define get16i(ptr) (short)get16u(ptr)
#define get32i(ptr) (int)get32u(ptr)


/* splay trees
 *
 * for further details, see "Self-adjusting Binary Search Trees"
 * by Sleator and Tarjan, JACM Volume 32, No 3, July 1985, pp 652-686.
 */

struct snode {
   struct snode *left, *right;
   void *key;
   void *data;
};

typedef int (*sfunc)(const void *key1, const void *key2);

static struct snode *splay(struct snode *t, const void *key, sfunc comp)
{
   struct snode N, *l, *r, *y;
     
   if (t == NULL) return t;
   N.left = N.right = NULL;
   l = r = &N;
 
   for (;;) {
      if (comp(key, t->key) < 0) {
       if (t->left == NULL) break;
       if (comp(key, t->left->key) < 0) {
          y = t->left;                           /* rotate right */
          t->left = y->right;
          y->right = t;
          t = y;
          if (t->left == NULL) break;
       }
       r->left = t;                               /* link right */
       r = t;
       t = t->left;
      }
      else if (comp(key, t->key) > 0) {
       if (t->right == NULL) break;
       if (comp(key, t->right->key) > 0) {
          y = t->right;                           /* rotate left */
          t->right = y->left;
          y->left = t;
          t = y;
          if (t->right == NULL) break;
       }
       l->right = t;                              /* link left */
       l = t;
       t = t->right;
      }
      else {
       break;
      }
   }
   
   l->right = t->left;                              /* assemble */
   r->left = t->right;
   t->left = N.right;
   t->right = N.left;
   
   return t;
}

static struct snode *sinsert(struct snode *root, void *key, size_t size, sfunc comp)
{
   struct snode *t, *x;
   t = splay(root, key, comp);
   if (t != NULL && comp(t->key, key) == 0)
      return t;
   //x = (struct snode *)malloc(sizeof(struct snode));
   x = new snode;
   assert( x != NULL );
   if (t == NULL) {
      x->left = x->right = NULL;
   }
   else if (comp(key, t->key) < 0) {
      x->left = t->left;
      x->right = t;
      t->left = NULL;
   }
   else {
      x->right = t->right;
      x->left = t;
      t->right = NULL;
   }
   if (size > 0) {
      //x->key = malloc(size);
      x->key = new ubyte[size];
      memcpy(x->key, key, size);
   }
   else {
      x->key = key;
   }
   x->data = (void *)-1;
   return x;
}

#define S_KEY   1 /* free key */
#define S_DATA  2 /* free data */
#define S_TREE  4 /* delete scene graph (SSG special) */

static void deltree(ssgEntity *node)
{
   if (node->getRef() <= 1 && node->isAKindOf(ssgTypeBranch())) {
      ssgBranch *grp = (ssgBranch *)node;
      int n = grp->getNumKids();
      while (n--) {
       deltree(grp->getKid(n));
       grp->removeKid(n); // delete kid (iff ref == 0)
      }
   }
}

static void sfree(struct snode *x, int flags)
{
   if (x) {      
      sfree(x->left, flags);
      sfree(x->right, flags);
      if ((flags & S_KEY))
       //free(x->key);
       delete [] (ubyte *)x->key;
      if (x->data != (void *)-1 && x->data != 0) {
       if ((flags & S_DATA)) 
          //free(x->data);
          delete [] (ubyte *)x->data;
       if ((flags & S_TREE)) {
          deltree((ssgEntity *)x->data);
          ssgDeRefDelete((ssgEntity *)x->data);
       }
      }
   }
}

static int ptrcmp(const void *key1, const void *key2)
{
   return (const char *)key1 - (const char *)key2;
}


static void hexdump(enum ulSeverity severity, const ubyte *buf, int size, int offset)
{
#define COLS 16
   char line[1024], *lp;
   while (size > 0) {
      int i, n = MIN(size, COLS);
      lp = line;
      lp += sprintf(lp, "%04x ", offset);
      for (i = 0; i < n; i++)
       lp += sprintf(lp, " %02x", buf[i]);
      for (; i < COLS; i++)
       lp += sprintf(lp, "   ");
      *lp++ = ' ';
      *lp++ = ' ';
      for (i = 0; i < n; i++)
       *lp++ = (buf[i] & 0x7f) < 0x20 ? '.' : buf[i];
      *lp = 0;
      ulSetError(severity, line);
      buf += COLS;
      offset += COLS;
      size -= COLS;
   }
}



#define MAXDEPTH 256

#define UNPACK_ABGR(dst, src) \
     ((dst)[0] = (1.0f/255.0f)*(src)[3], \
      (dst)[1] = (1.0f/255.0f)*(src)[2], \
      (dst)[2] = (1.0f/255.0f)*(src)[1], \
      (dst)[3] = 1.0f)

#define UNPACK_ABGR2(dst, src, intensity) \
     ((dst)[0] = (1.0f/255.0f/127.0f)*(src)[3]*(intensity), \
      (dst)[1] = (1.0f/255.0f/127.0f)*(src)[2]*(intensity), \
      (dst)[2] = (1.0f/255.0f/127.0f)*(src)[1]*(intensity), \
      (dst)[3] = 1.0f)

/* triangle flags */
#define TRI_COLOR_MATERIAL 0x01  /* --> apply material on vertex colors */
#define TRI_TRANSLUCENT    0x02 
#define TRI_SUBFACE        0x04  /* offset geometry */
#define TRI_BBOARD_AXIAL   0x08
#define TRI_BBOARD_POINT   0x10
/*#define TRI_WIREFRAME      0x20*/
#define TRI_BBOARD (TRI_BBOARD_AXIAL | TRI_BBOARD_POINT)

/* vertex bind */
#define BIND_COLOR        0x01
#define BIND_NORMAL       0x02
#define BIND_TEXCOORD     0x04
#define BIND_FLAT_COLOR   0x08
#define BIND_FLAT_NORMAL  0x10
#define BIND_FLAT (BIND_FLAT_COLOR | BIND_FLAT_NORMAL) 

struct fltTriangle {

   ssgState *state;

   ubyte flags;
   ubyte bind;

#if 0
   short priority; /* affects the ordering within the geoset */
   ushort transparency; /* eventually applied to colors when done */
#endif
   
   int index[3];
   sgVec4 color; /* face color *or* material contributions to vertex colors */

};

struct fltTexture {
   char *file;
   ssgState *state; /* user-defined state */
   ssgTexture *tex;
   int alpha;
};

struct fltState {

   fltState() {
      memset(this, 0, sizeof(*this));  
      notex_state = (ssgState *)-1;
      atris = 256;
      //tris = (fltTriangle *)malloc(sizeof(fltTriangle) * atris);
      tris = new fltTriangle[atris];
   }

   ~fltState() {
      sfree(texs, S_DATA);
      sfree(mtls, S_DATA);
      sfree(refs, S_TREE);
      if (vtab) {
       delete [] offset;
       delete [] bind;
       delete [] coord;
       delete [] color;
       delete [] normal;
       delete [] texcoord;
      }
      //free(tris);
      delete [] tris;
   }

   const char *filename;
   int revision;
   int major;
   int minor;

   /* Vertex Table */
   ubyte *vtab; /* start of vertex table */
   int vnum;
   int *offset; /* chunk offset (used as index) */
   ubyte *bind; /* 1 - color, 2 - normal, 4 - texcoord */
   sgVec3 *coord;
   sgVec4 *color;
   sgVec3 *normal;
   sgVec2 *texcoord;

   /* Other Tables (these may be sparse, that is why arrays are not used) */
   struct snode *mtls; /* index --> float[14] */
   struct snode *texs; /* index --> fltTexture */
   struct snode *refs; /* index --> ssgEntity */
   ubyte (*ctab)[4]; /* packed ABGR color table */
   int cnum;
   ssgState *notex_state; /* special user-defined state if no texture */

   /* Collected Geometry */
   fltTriangle *tris;
   int ntris, atris;
   fltTriangle *temp;
   char *parent_name;
};

struct fltNodeAttr {   

   /* allocated using new/delete for convenience */
   fltNodeAttr() {
      memset(this, 0, sizeof(*this)); 
   }
   ~fltNodeAttr() { 
      if (name) delete name; 
      if (mask_words) delete mask_words; 
   }

   /* properies that are not applied immediately */

   char *name;

   int replicate;
   int transform;
   int islod;

   sgMat4 mat;
   sgVec2 range;
   sgVec3 center;

   /* switch record info */
   int num_masks;
   int num_words;
   uint *mask_words;
   int current_mask;

};

static int Inited = 0;
static int NoTextures = 0;
static int NoMipmaps = 0;
static int NoExternals = 0;
static int NoClean = 0;

#ifndef NO_LOADER_OPTIONS
static ssgLoaderOptions *LoaderOptions;
#endif

static struct snode *TexCache; /* filename --> fltTexture */

static fltTexture *LoadTex(char *fname)
{
   TexCache = sinsert(TexCache, fname, strlen(fname) + 1, (sfunc)strcmp);
   if (TexCache->data == (void *)-1) {
      //fltTexture *tex = (fltTexture *)malloc(sizeof(fltTexture));
      fltTexture *tex = new fltTexture;
      assert ( tex != NULL );
      tex->file = fname;
#ifdef NO_LOADER_OPTIONS
      tex->state = 0;
      tex->tex = new ssgTexture(fname, 1, 1, !NoMipmaps);
#else
      tex->state = LoaderOptions->createState(fname);
      tex->tex = tex->state ? 0 : LoaderOptions->createTexture(fname, 1, 1, !NoMipmaps);
#endif
      tex->alpha = tex->tex ? tex->tex->hasAlpha() : 0;
      TexCache->data = tex;
   }
   return (fltTexture *)TexCache->data;
}

struct StateInfo {
   int cf; /* cull face */
   int tr; /* translucent */
   int cm; /* color material */
   ssgTexture *tex;
   float *mtl;
   float alpha;
};

static int StateCompare(const void *key1, const void *key2)
{
   const StateInfo *s1 = (const StateInfo *)key1;
   const StateInfo *s2 = (const StateInfo *)key2;
   int d;
   d = s1->cf - s2->cf;
   if (d == 0) {
      d = s1->tr - s2->tr;
      if (d == 0) {
       d = s1->cm - s2->cm;
       if (d == 0) {
          d = (char *)s1->tex - (char *)s2->tex;
          if (d == 0) {
             if (s1->mtl == 0 || s2->mtl == 0)
              d = (char *)s1->mtl - (char *)s2->mtl;
             else {
              int i = s1->cm ? 6 : 0;
              for (; i < 12 && d == 0; i++)
                 if (s1->mtl[i] < s2->mtl[i] - 0.01f)
                  d = -1;
                 else if (s1->mtl[i] > s2->mtl[i] + 0.01f)
                  d = 1;
              if (d == 0) {
                 if (s1->alpha < s2->alpha - 0.01f)
                  d = -1;
                 else if (s1->alpha > s2->alpha + 0.01f)
                  d = 1;
              }
             }
          }
       }
      }
   }
   return d;
}

static struct snode *StateCache; /* StateInfo --> ssgSimpleState */

static ssgSimpleState *ConstructState(StateInfo *key)
{
   StateCache = sinsert(StateCache, key, sizeof(StateInfo), StateCompare);
   if (StateCache->data == (void *)-1) {
      ssgSimpleState *s;

      /*ulSetError(UL_DEBUG, "new state --");*/

      s = new ssgSimpleState;

      if (key->cf) {
       s->enable(GL_CULL_FACE);
      }
      else {
       s->disable(GL_CULL_FACE);
       /*ulSetError(UL_DEBUG, "  two-sided");*/
      }

      if (key->tr) {
       s->setTranslucent();
       s->enable(GL_BLEND); /* XXX what about multisampling? */
       /*ulSetError(UL_DEBUG, "  transparent");*/
      }
      else {
       s->setOpaque();
       s->disable(GL_BLEND);
      }
      /* leave the alpha test to the application */

      if (key->mtl) {
       float *m = key->mtl;
       sgVec4 c;
       /*ulSetError(UL_DEBUG, "%.2f %.2f %.2f  %.2f %.2f %.2f  %.2f %.2f %.2f  %.2f %.2f %.2f  %.2f %.2f  %d",
         m[0], m[1], m[2], m[3], m[4], m[5], m[6], m[7], m[8], m[9], m[10], m[11], m[12], m[13], key->cm);*/
       if (key->cm) {
          s->enable(GL_COLOR_MATERIAL);
          s->setColourMaterial(GL_AMBIENT_AND_DIFFUSE);
          //ulSetError(UL_DEBUG, "  color material");
       }
       else {
          s->disable(GL_COLOR_MATERIAL);
          sgSetVec4(c, m[0], m[1], m[2], key->alpha); s->setMaterial(GL_AMBIENT, c);
          sgSetVec4(c, m[3], m[4], m[5], key->alpha); s->setMaterial(GL_DIFFUSE, c);
          //ulSetError(UL_DEBUG, "  ambient   %.2f %.2f %.2f", m[0], m[1], m[2]);
          //ulSetError(UL_DEBUG, "  diffuse   %.2f %.2f %.2f", m[3], m[4], m[5]);
       }
       sgSetVec4(c, m[6], m[7], m[8], key->alpha); s->setMaterial(GL_SPECULAR, c);
       sgSetVec4(c, m[9], m[10], m[11], key->alpha); s->setMaterial(GL_EMISSION, c);
       //ulSetError(UL_DEBUG, "  specular  %.2f %.2f %.2f", m[6], m[7], m[8]);
       //ulSetError(UL_DEBUG, "  emission  %.2f %.2f %.2f", m[9], m[10], m[11]);
       //ulSetError(UL_DEBUG, "  alpha %.2f", key->alpha);
       s->setShininess(m[12]);
       s->enable(GL_LIGHTING);
      }
      else {
       s->disable(GL_LIGHTING);
       /*ulSetError(UL_DEBUG, "  no lighting");*/
      }

      if (key->tex) {    
       s->enable(GL_TEXTURE_2D);
       s->setTexture(key->tex);
       /*ulSetError(UL_DEBUG, "  texture %s", key->tex->getFilename());*/
      }
      else {
       s->disable(GL_TEXTURE_2D);
      }

      s->setShadeModel(GL_SMOOTH);
      
      s->ref();

      StateCache->data = s;
   }
   return (ssgSimpleState *)StateCache->data;
}

static int tricmp(const void *a, const void *b)
{
   /* this comparison is used to sort the list of triangles in order to 
    * generate as few geosets as possible.
    */
   fltTriangle *ta = (fltTriangle *)a;
   fltTriangle *tb = (fltTriangle *)b;
   int d = (char *)ta->state - (char *)tb->state;
   if (d == 0) {
      d = ta->flags - tb->flags;
      if (d == 0)
       d = ta->bind - tb->bind;
   }
   return d;
}

#if 0 /* no longer needed since this is now the default blend equation */
static int PreDrawTranslucent(ssgEntity *)
{
   glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
   return 1;
}
#endif

static int PreDrawSubface(ssgEntity *)
{
#ifdef GL_VERSION_1_1
   glPolygonOffset(-2.0f, -1.0f);
   glEnable(GL_POLYGON_OFFSET_FILL);
#else
   glPolygonOffsetEXT(-0.1f, -0.002f);
   glEnable(GL_POLYGON_OFFSET_EXT);
#endif
   return 1;
}

static int PostDrawSubface(ssgEntity *)
{
#ifdef GL_VERSION_1_1
   glDisable(GL_POLYGON_OFFSET_FILL);
#else
   glDisable(GL_POLYGON_OFFSET_EXT);
#endif
   return 1;
}

/* convert a list of triangles to geosets using the pfdMesher
 * need a seperate geostate for each comb of tex/mtl/bind
 */
static ssgEntity *Build(fltState *state)
{
   /*const char t[9] = "plsTQSfFP";*/
   ssgBranch *grp = 0;
   ssgCutout *bboard1 = 0;
   ssgCutout *bboard2 = 0;
   ssgLeaf *leaf = 0;
   fltTriangle *arr;
   int num, i, j, k, m, n;

   //int *index;
   //int *vertex;

   arr = state->tris;
   num = state->ntris;
   state->ntris = 0;
   if (num == 0)
      return 0;

   /* sort the triangles (put them in bins according to their attributes)
    * one geoset will be generated for each such bin
    */
   qsort(arr, num, sizeof(fltTriangle), tricmp);

   int *index = new int [ state->vnum ];
   int *vertex = new int [ 32768 ];
   
   for (i = 0; i < num; ) {

      ssgVertexArray *va;
      ssgColourArray *ca = 0;
      ssgNormalArray *na = 0;
      ssgTexCoordArray *ta = 0;
      ssgVtxTable *geom;

      int flags = arr[i].flags;
      int bind = arr[i].bind;

      /* see how many tris that belong to this group */
      for (j = i + 1; (j < num && 
                       arr[j].state == arr[i].state && 
                       arr[j].flags == flags &&
                   arr[j].bind == bind
                       ); j++)
         ;
      /*fprintf(stderr, " %d", j - i);*/
      
      /* simply construct a triangle soup */
      /* XXX fixme! */

      if ((bind & BIND_FLAT) || (flags & TRI_COLOR_MATERIAL)) {

       n = 3*(j - i);

       va = new ssgVertexArray(n);
       for (k = i; k < j; k++) {
          va->add(state->coord[arr[k].index[0]]);
          va->add(state->coord[arr[k].index[1]]);
          va->add(state->coord[arr[k].index[2]]);
       }
       
       if ((bind & BIND_FLAT_COLOR)) {
          ca = new ssgColourArray(n);
          for (k = i; k < j; k++) {
             ca->add(arr[k].color);
             ca->add(arr[k].color);
             ca->add(arr[k].color);
          }
       }
       else if ((bind & BIND_COLOR)) {
          ca = new ssgColourArray(n);
          if ((flags & TRI_COLOR_MATERIAL)) {
             for (k = i; k < j; k++) {
              for (m = 0; m < 3; m++) {
                 sgVec4 color;
                 float *mtl_color = arr[k].color;
                 float *vtx_color = state->color[arr[k].index[m]];
                 color[0] = mtl_color[0] * vtx_color[0];
                 color[1] = mtl_color[1] * vtx_color[1];
                 color[2] = mtl_color[2] * vtx_color[2];
                 color[3] = mtl_color[3] * vtx_color[3];
                 ca->add(color);
              }
             }
          }
          else {
             for (k = i; k < j; k++) {
              ca->add(state->color[arr[k].index[0]]);
              ca->add(state->color[arr[k].index[1]]);
              ca->add(state->color[arr[k].index[2]]);
             }
          }
       }
       else if ((flags & TRI_TRANSLUCENT)) {
          ca = new ssgColourArray(1);
          ca->add(arr[i].color);
       }

       if ((bind & BIND_FLAT_NORMAL)) {
          na = new ssgNormalArray(n);
          for (k = i; k < j; k++) {
             sgVec3 a, b, normal;
             int *w = arr[k].index;
             sgSubVec3(a, state->coord[w[1]], state->coord[w[0]]);
             sgSubVec3(b, state->coord[w[2]], state->coord[w[0]]);
             sgVectorProductVec3(normal, a, b);
             sgNormalizeVec3(normal);
             na->add(normal);
             na->add(normal);
             na->add(normal);
          }
       }
       else if ((bind & BIND_NORMAL)) {
          na = new ssgNormalArray(n);
          for (k = i; k < j; k++) {
             na->add(state->normal[arr[k].index[0]]);
             na->add(state->normal[arr[k].index[1]]);
             na->add(state->normal[arr[k].index[2]]);
          }
       }

       if ((bind & BIND_TEXCOORD)) {
          ta = new ssgTexCoordArray(n);
          for (k = i; k < j; k++) {
             ta->add(state->texcoord[arr[k].index[0]]);
             ta->add(state->texcoord[arr[k].index[1]]);
             ta->add(state->texcoord[arr[k].index[2]]);
          }
       }

       geom = new ssgVtxTable(GL_TRIANGLES, va, na, ta, ca);

      }
      else {

       ssgIndexArray *ia = new ssgIndexArray(3*(j - i));
       
       memset(index, -1, sizeof(index[0]) * state->vnum);
       n = 0;
       for (k = i; k < j; k++) {
          int *tri = arr[k].index;
          int save = n;
          for (m = 0; m < 3; m++) {
             if (index[tri[m]] == -1) {
              if (n == 65536) {
                 ulSetError(UL_DEBUG, "[flt] More than 65536 vertices, split forced.");
                 n = save;
                 j = k;
                 //goto hopp;
                 break;
              }
              vertex[n] = tri[m];
              index[tri[m]] = n++;
             }
             ia->add((short)index[tri[m]]);
          }
          if (m < 3) break;
       }
       //hopp:
       
       va = new ssgVertexArray(n);
       for (k = 0; k < n; k++)
          va->add(state->coord[vertex[k]]);
       
       if ((bind & BIND_COLOR)) {
          ca = new ssgColourArray(n);
          for (k = 0; k < n; k++)
             ca->add(state->color[vertex[k]]);
       }
       else if ((flags & TRI_TRANSLUCENT)) {
          ca = new ssgColourArray(1);
          ca->add(arr[i].color);
       }
       
       if ((bind & BIND_NORMAL)) {
          na = new ssgNormalArray(n);
          for (k = 0; k < n; k++)
             na->add(state->normal[vertex[k]]);
       }
       
       if ((bind & BIND_TEXCOORD)) {
          ta = new ssgTexCoordArray(n);
          for (k = 0; k < n; k++)
             ta->add(state->texcoord[vertex[k]]);
       }

       if (n == 3*(j - i)) {

          delete ia;

          geom = new ssgVtxTable(GL_TRIANGLES, va, na, ta, ca);
       }
       else {

          geom = new ssgVtxArray(GL_TRIANGLES, va, na, ta, ca, ia);
       }

      }

      geom->setState(arr[i].state);
      
      /*ulSetError(UL_DEBUG, "build: [%d..%d] %02x %d indices, %d vertices",
           i, j - 1, bind,
           3*(j - i), n);*/
      
      if (leaf) {
       if (grp == 0)
          grp = new ssgBranch;
       grp->addKid(leaf);
      }

      leaf = geom;
      
#if 0
      if ((flags & TRI_TRANSLUCENT)) {
       leaf->setCallback(SSG_CALLBACK_PREDRAW, PreDrawTranslucent);
      }
      else 
#endif
      if ((flags & TRI_SUBFACE)) {
       leaf->setCallback(SSG_CALLBACK_PREDRAW, PreDrawSubface);
       leaf->setCallback(SSG_CALLBACK_POSTDRAW, PostDrawSubface);
      }
      
#ifndef NO_LOADER_OPTIONS
      leaf = LoaderOptions->createLeaf(leaf, state->parent_name);
#endif
      
      if ((flags & TRI_BBOARD)) {
       if ((flags & TRI_BBOARD_AXIAL)) {
          if (bboard1 == 0)
             bboard1 = new ssgCutout(0);
          bboard1->addKid(leaf);        
       }
       else {
          if (bboard2 == 0)
             bboard2 = new ssgCutout(1);
          bboard2->addKid(leaf);
       }
       leaf = 0;
      }

      i = j;
   }

   delete [] vertex;
   delete [] index;

   if (((leaf != 0) + (bboard1 != 0) + (bboard2 != 0)) > 1 && !grp) //lint !e514 Lint warning "unusual use of a boolean"
      grp = new ssgBranch;

   if (grp) {
      if (bboard1) 
       grp->addKid(bboard1);
      if (bboard2)
       grp->addKid(bboard2);
      if (leaf) 
       grp->addKid(leaf);
      return grp;
   }

   if (bboard1)
      return bboard1;

   if (bboard2)
      return bboard2;

   return leaf;
}

/* add a triangle */
static void AddTri(fltState *state, int v0, int v1, int v2)
{
   fltTriangle *tri;
   if (state->ntris == state->atris) {
      state->atris += state->atris;
      //state->tris = (fltTriangle *)realloc(state->tris, sizeof(fltTriangle) * state->atris);
      fltTriangle *old = state->tris;
      state->tris = new fltTriangle[state->atris];
      memcpy(state->tris, old, sizeof(fltTriangle) * state->atris / 2);
      delete [] old;
   }
   tri = state->tris + state->ntris++;
   memcpy(tri, state->temp, sizeof(fltTriangle));
   tri->index[0] = v0;
   tri->index[1] = v1;
   tri->index[2] = v2;
}

static void Triangulate(int *w, int n, fltState *state)
{
   int buf[3 * (16 - 2)];
   int *tris = (n > 16) ? new int [ 3 * (n - 2) ] : buf;
   int num_tris = _ssgTriangulate(state->coord, w, n, tris);
   for (int i = 0; i < num_tris; i++)
      AddTri(state, tris[3*i + 0], tris[3*i + 1], tris[3*i + 2]);
   if (tris != buf)
     delete [] tris;
}

static int ObsoleteFlag;
static int NotImplementedFlag;

static void Obsolete(int op)
{
   if (!ObsoleteFlag) {
      ulSetError(UL_WARNING, "[flt] This file is probably rather old (obsolete opcodes ignored).");
      ObsoleteFlag = 1;
   }
   //printf("op %d obsolete\n", op);
}

static void NotImplemented(int op)
{
   if (!NotImplementedFlag) {
      ulSetError(UL_WARNING, "[flt] This file contains opcodes that are not implemented.");
      NotImplementedFlag = 1;
   }
   //printf("op %d not implemented\n", op);
}

static void ReportBadChunk(const ubyte *ptr, const char *name)
{
   int op = get16u(ptr);
   int len = get16u(ptr + 2);
   ulSetError(UL_WARNING, "[flt] Bad record, opcode %d (%s), length %d:", op, name, len);
   hexdump(UL_WARNING, ptr, len, 0);
   ulSetError(UL_WARNING, "Please report this, either at http://plib.sourceforge.net/,");
   ulSetError(UL_WARNING, "or by email to plib-devel@lists.sourceforge.net. Thanks.");
}

#define BAD_CHUNK(ptr, name)\
   do {\
      static int first = 1;\
      if (first) {\
       ReportBadChunk(ptr, name);\
       first = 0;\
      }\
   } while (0)

static int intcmp(const void *a, const void *b)
{
   return *(int *)a - *(int *)b;
}

/* polygon chunks */
static int GeomChunks(ubyte *ptr0, ubyte *end, fltState *state, ssgEntity **nodep, int objflags, int objtrans)
{
   ubyte *ptr = ptr0;
   int sp = 0, op, len, done = 0, triflg = 0;
   int w[512]; /* enough? */
   fltTriangle tri;
   StateInfo info;
   int subface = 0;
   char long_id[256] = {0};

   state->temp = &tri;
   memset(&tri, 0, sizeof(tri));
   
   /* read as many polygon chunks as possible. 
    * can be done since objects may not contain groups.
    * color table etc should also be defined before any polygon.
    * (the purpose is to keep the switch(op) relatively small to speed up this "inner loop")
    */

   do {

      if (ptr + 4 > end)
         break;
      op = get16u(ptr);
      len = get16u(ptr+2);
      if (len < 4 || (len & 3) != 0 || ptr + len > end)
         break;
      
      switch (op) {
      
      case 5: { /* Face (appearence) */

         /*
          * Face Record Format           
          *
          * Int         0  2  Face Opcode 5 
          * Unsigned    2  2  Length of the record 
          * Char        4  8  7 char ASCII ID; 0 terminates 
          * Int        12  4  IR color code 
          * Int        16  2  Relative priority 
          * Int        18  1  Draw type 
          *                      0 = Draw solid with backface culling 
          *                      1 = Draw solid, no backface culling
          *                      2 = Draw wireframe 
          *                      3 = Draw wireframe and close 
          *                      4 = Surround with wireframe in alternate color 
          *                      8 = Omnidirectional light 
          *                      9 = Unidirectional light 
          *                      10 = Bidirectional light 
          * Int        19  1  Texture white = if TRUE, draw textured face white
          * Unsigned   20  2  Color name index 
          * Unsigned   22  2  Alternate color name index 
          * Int        24  1  Reserved 
          * Int        25  1  Template (billboard)
          *                      0 = Fixed, no alpha blending 
          *                      1 = Fixed, alpha blending 
          *                      2 = Axial rotate 
          *                      4 = Point rotate 
          * Int        26  2  Detail texture pattern index, -1 if none 
          * Int        28  2  Texture pattern index, -1 if none 
          * Int        30  2  Material index, -1 if none 
          * Int        32  2  Surface material code (for DFAD) 
          * Int        34  2  Feature ID (for DFAD)
          * Int        36  4  IR material code 
          * Unsigned   40  2  Transparency 0 = Opaque 65535 = Totally clear 
          * Unsigned   42  1  LOD generation control 
          * Unsigned   43  1  Line style index 
          * Boolean    44  4  Flags (bits from left to right) 
          *                      0 = Terrain 
          *                      1 = No color 
          *                      2 = No alternate color 
          *                      3 = Packed color 
          *                      4 = Terrain culture cutout (footprint) 
          *                      5 = Hidden, not drawn 
          *                      6-31 = Spare 
          * Unsigned   48  1  Light mode 
          *                      0 = Use face color, not illuminated 
          *                      1 = Use vertex colors, not illuminated 
          *                      2 = Use face color and vertex normal 
          *                      3 = Use vertex color and vertex normal 
          * Unsigned   49  1  Reserved 
          * Unsigned   50  2  Reserved 
          * Boolean    52  4  Reserved
          * Unsigned   56  4  Packed color, primary (A, B, G, R) 
          * Unsigned   60  4  Packed color, alternate (A, B, G, R)
          * Int        64  2  Texture mapping index 
          * Int        66  2  Reserved 
          * Unsigned   68  4  Primary color index 
          * Unsigned   72  4  Alternate color index 
          * Int        76  2  Reserved 
          * Int        78  2  Reserved 
          *
          */

       static float default_mtl[14] = {
          1.0f, 1.0f, 1.0f,
          1.0f, 1.0f, 1.0f,
          0.0f, 0.0f, 0.0f,
          0.0f, 0.0f, 0.0f,
          8.0f, 1.0f
       };
         int flags = len < 48 ? 0 : get32i(ptr + 44);
       int drawtype = ptr[18];

         if (drawtype > 4 || (flags & (1 << 5)) || len < 32) {
            triflg = 0;
         }
         else {
            int index;
          struct snode *t;
          int tex_alpha = 0;

          tri.state = 0;
          tri.flags = 0;

#ifdef NO_TEXTURES
          info.tex = 0;
#else
            /* texture */
          info.tex = 0;
            index = get16i(ptr + 28); /* texture index */
          t = 0;
          if (index != -1) {
             state->texs = t = splay(state->texs, (void *)index, ptrcmp);
             if (t == 0 || t->key != (void *)index) {
              /*ulSetError(UL_DEBUG, "[flt] undefined texture %d", index);*/
              t = 0;
             }
          }
          if (t) {
             fltTexture *tex = (fltTexture *)t->data;
             if (tex->state == (ssgState *)-1) {
              fltTexture *tmp = LoadTex(tex->file);
              tex->state = tmp->state;
              tex->tex = tmp->tex;
              tex->alpha = tmp->alpha;
             }
             tri.state = tex->state;
             info.tex = tex->tex;
             tex_alpha = tex->alpha;
          }
#ifndef NO_LOADER_OPTIONS
          else {
             if (state->notex_state == (ssgState *)-1)
              state->notex_state = LoaderOptions->createState(0);
             tri.state = state->notex_state;
          }
#endif
#endif

          if (tri.state) {

             tri.bind = BIND_COLOR | BIND_NORMAL | BIND_TEXCOORD;

          }
          else {
          
             int template = ptr[25];
             int white = ptr[19] || template > 1; /* OK ?? */
             int lmode = len >= 49 ? ptr[48] : 3;
             int trans = get16u(ptr + 40);

             //ulSetError(UL_DEBUG, "light mode %d", lmode);

             /*lmode = 0;*/
          
             /* wireframe */
             /*tri.wireframe = (drawtype > 1);*/

             /* backface culling */
             info.cf = (drawtype == 0);
             
             /* alpha component */
#if 0
             if (state->major >= 15) {
              /* this is according to the spec, but it sure is suspicious */
              int a = trans >> 1;
              int b = objtrans >> 1;
              info.alpha = 1.0f - 1.0f/(32767*32767) * (a * b);
             }
             else 
#endif
               {
              info.alpha = 1.0f - 1.0f/65535.0f * trans;
             }
             sgSetVec4(tri.color, 1, 1, 1, info.alpha);
             
#ifdef NO_LIGHTING
             info.mtl = 0;
#else
             /* material */
             if (/*lmode < 2 ||*/ /* (objflags & (1 << 3)) || */ white) {
              info.mtl = 0;
             }
             else {
              index = get16i(ptr + 30); /* material index */
              state->mtls = t = splay(state->mtls, (void *)index, ptrcmp);
              if (t && t->key == (void *)index) {
                 info.mtl = (float *)t->data;
              }
              else {
                 info.mtl = default_mtl;
              }
              info.alpha *= info.mtl[13];
              tri.color[3] = 1.0f;
             }
#endif

             /* transparency */
             info.tr = (tex_alpha > 0 || info.alpha < 0.999f); /* && template > 0 */
             if (info.tr)
              tri.flags |= TRI_TRANSLUCENT;

             /* initial bindings */
             tri.bind = 0;
             if ((lmode & 1) && !white)
              tri.bind |= BIND_COLOR;
             if (info.mtl) {
              tri.bind |= BIND_NORMAL;
              if (!(lmode & 2) || (objflags & (1 << 4)))
                 tri.bind |= BIND_FLAT_NORMAL;
             }
             if (info.tex)
              tri.bind |= BIND_TEXCOORD;

#ifdef NO_COLORS
             tri.bind &= ~BIND_COLOR;
#else

             /* face color */
             if (!(lmode & 1) && !(flags & 2) && !white && state->major >= 14) { /* will probably not work with old files */
              if ((flags & 8) && len >= 60) {
                 UNPACK_ABGR(tri.color, ptr + 56); /* packed ABGR */
                 tri.bind |= BIND_FLAT_COLOR;
              }
              else if (state->revision > 1400) {
                 int color;
                 if (state->revision > 1500 && len >= 72)
                  color = get32i(ptr + 68);
                 else {
                  color = get16u(ptr + 20);
                  if (color == 65535)
                     color = -1;
                 }
                 int index = color / 128;
                 int intensity = color % 128;
                 if (color >= 0 && state->ctab && index < state->cnum) {
                  UNPACK_ABGR2(tri.color, state->ctab[index], intensity);
                  tri.bind |= BIND_FLAT_COLOR;          
                 }
                 else if (color != -1)
                  ulSetError(UL_DEBUG, "[flt] Bad face color %d.", color);
              }
              tri.color[3] = info.alpha;
             }
#endif

             /*
             if (tri.bind & BIND_COLOR) 
               ulSetError(UL_DEBUG, "use vertex colors");
             if (tri.bind & BIND_FLAT_COLOR)
               ulSetError(UL_DEBUG, "face color %.2f %.2f %.2f", 
                        tri.color[0], tri.color[1], tri.color[2]);
              */

             /* billboard */
             if (template == 4)
              tri.flags |= TRI_BBOARD_POINT;
             else if (template == 2)
              tri.flags |= TRI_BBOARD_AXIAL;

             /* cannot create the state yet,
            * need to know the vertex bindings. */
          }
             
            triflg = 1;
         }            
         ptr += len;
         break;
      }

      case 72: /* Vertex List (aka polygon) */
         if (triflg) {
            int i, n = (len - 4) >> 2;
            if (state->vtab && n > 2 && n < 512) { /* silently ignore if suspicious.. */
             int bind = tri.bind;
               ubyte *p = ptr + 4;
               for (i = 0; i < n; ++i) {
              /* could this be done any faster? */
              /* it is tempting to reparse the vertex at the given offset */
                  int offset = get32i(p), *ptr;
              ptr = (int *)bsearch(&offset, state->offset, state->vnum, 
                               sizeof(int), intcmp);
                  if (!ptr) {
                 ulSetError(UL_DEBUG, "[flt] Bad vertex offset %i.", offset);
                 break;
              }
                  w[i] = ptr - state->offset;
              bind &= state->bind[w[i]] | BIND_FLAT;
                  p += 4;
               }
               if (i == n) {

              tri.bind = bind;

              if (subface)
                 tri.flags |= TRI_SUBFACE;
              else
                 tri.flags &= ~TRI_SUBFACE;

              if (tri.state) {

                 Triangulate(w, n, state);

              }
              else {
                 /* finalize state */
                 
                 /* setup color material */
                 if ((bind & (BIND_COLOR | BIND_FLAT_COLOR)) &&
                   (bind & (BIND_NORMAL | BIND_FLAT_NORMAL))) {
                  sgVec4 color;
                  color[0] = 0.2f*info.mtl[0] + 0.8f*info.mtl[3];
                  color[1] = 0.2f*info.mtl[1] + 0.8f*info.mtl[4];
                  color[2] = 0.2f*info.mtl[2] + 0.8f*info.mtl[5];
                  color[3] = info.alpha;
                  if ((tri.bind & BIND_FLAT_COLOR)) {
                     tri.color[0] *= color[0];
                     tri.color[1] *= color[1];
                     tri.color[2] *= color[2];
                     tri.color[3] *= color[3];
                  }
                  else {
                     sgCopyVec4(tri.color, color); /* apply to vertex colors */
                  }
                  info.cm = 1;
                  tri.flags |= TRI_COLOR_MATERIAL;
                 }
                 else {
                  info.cm = 0;
                  tri.flags &= ~TRI_COLOR_MATERIAL;
                 }
                 
                 tri.state = ConstructState(&info);

                 Triangulate(w, n, state);

                 tri.state = 0;
              }
               }
            }
         }
         ptr += len;
         break;

      case 89: /* Morph Vertex List */
         ptr += len;
         break;
          
      case 10: /* Push */
         sp++;
         ptr += len;
         break;
       
      case 11: /* Pop */
         if (sp == 0) {
            done = 1;
            break;
         }
         sp--;
         ptr += len;
         /*if (sp == 0)
         done = 1;*/
         break;

      case 19: /* Push Subface */
       subface++;
         ptr += len;
         break;

      case 20: /* Pop Subface */
       subface--;
         ptr += len;
         break;

      case 33: /* Long ID */
         if (long_id[0] == 0) {
            int n = CLAMP(len - 4, 0, 255);
            memcpy(long_id, ptr + 4, n);
            long_id[n] = 0;
         }
         ptr += len;
         break;

      case 31: /* Text Comment */
      case 50: /* Vector (for light points) */
      case 21: /* Push Extension */
      case 22: /* Pop Extension */
      case 97: /* Line Style Record */
      case 122: /* Push Attribute */
      case 123: /* Pop Attribute */
         ptr += len;
         break;

      case 6: /* Vertex with ID (obsolete) */
      case 7: /* Short Vertex (obsolete) */
      case 8: /* Vertex with Color (obsolete) */
      case 9: /* Vertex with Color and Normal (obsolete) */
       Obsolete(op);
       ptr += len;
       break;

      default:
         if (sp == 0) { /* you never know what this might be. better let someone else take car of it. */
            done = 1;
            break;
         }
       NotImplemented(op);
         ptr += len;
      }

   } while (!done);
   
   *nodep = Build(state);

   if (long_id[0] != 0 && *nodep != NULL)
     (*nodep)->setName(long_id);

   return ptr - ptr0;
}

struct LODInfo {
   ssgTransform *scs;
   ssgRangeSelector *lod;   
};

static int LODCompare(const void *a, const void *b)
{
   float d = ((LODInfo *)a)->lod->getRange(0) - ((LODInfo *)b)->lod->getRange(0);
   return d < 0 ? -1 : d > 0 ? 1 : 0;
}

static void MergeLODs(ssgBranch *grp)
{
   LODInfo info[64];
   int i, j, k, m, n;

   n = grp->getNumKids();
   if (n <= 1)
      return;

   m = 0;   
   for (i = 0; i < n && m < 64; i++) {
      ssgEntity *kid;
      kid = grp->getKid(i);
      info[m].scs = 0;
      if (kid->isA(ssgTypeTransform()) && kid->getNumParents() == 1) {
       info[m].scs = (ssgTransform *)kid;
       if (info[m].scs->getNumKids() != 1)
          continue;
       kid = info[m].scs->getKid(0);
      }
      if (!kid->isA(ssgTypeRangeSelector()) || kid->getNumParents() != 1)
       continue;
      info[m].lod = (ssgRangeSelector *)kid;
      m++;
   }
   
   if (m > 1) {
      
      qsort(info, m, sizeof(info[0]), LODCompare);

      //grp->print();
      
      for (i = 0; i < m; i++) {
       sgMat4 mat1, mat2;            
       float ranges[33], range2;
       int num1, num2;
       int flag = 0;
       
       if (info[i].lod == 0)
          continue;
       
       if (info[i].scs)
          info[i].scs->getTransform(mat1);
       else
          sgMakeIdentMat4(mat1);
       num1 = info[i].lod->getNumKids();
       for (k = 0; k <= num1; k++)
          ranges[k] = info[i].lod->getRange(k);
       
       for (j = i + 1; j < m; j++) {
          
          if (info[j].lod == 0)
             continue;
          
          if (info[j].scs)
             info[j].scs->getTransform(mat2);
          else
             sgMakeIdentMat4(mat2);
          num2 = info[j].lod->getNumKids();
          range2 = info[j].lod->getRange(0);
          
          if (sgDistanceVec3(mat1[3], mat2[3]) > 0.1f * range2) /* XXX */
             continue;
          if (num1 + num2 > 32) /* XXX */
             continue;
          if (ABS(ranges[num1] - range2) > 0.1f * range2) /* XXX */
             continue;
          
          for (k = 0; k < num2; k++) {
             info[i].lod->addKid(info[j].lod->getKid(k));
             ranges[num1 + k + 1] = info[j].lod->getRange(k + 1);
             num1++;
          }
          
          if (info[j].scs == 0 || info[j].scs->getRef() == 1) {
             if (info[j].lod->getRef() == 1) {
              while (num2--)
                 info[j].lod->removeKid(num2);
             }
             if (info[j].scs)
              info[j].scs->removeKid(info[j].lod); // delete info[j].lod
             else
              grp->removeKid(info[j].lod);
          }
          if (info[j].scs)
             grp->removeKid(info[j].scs); // delete info[j].scs

          info[j].lod = 0;       
          flag = 1;
       }

       if (flag) {
          info[i].lod->setRanges(ranges, num1 + 1);
          assert(info[i].scs == 0 || !info[i].scs->isA(0xDeadBeef));
          assert(!info[i].lod->isA(0xDeadBeef));
       }
      }
   }
}

static ssgEntity *PostClean(ssgEntity *node, fltNodeAttr *attr)
{

  if (node && attr && attr->name)
    node->setName(attr->name);

#if 1
   /* remove empty or redundant groups */
   while (!NoClean && node && node->isA(ssgTypeBranch())) {
      ssgBranch *grp = (ssgBranch *)node;
      int num = grp->getNumKids();
      if (num > 1)
       break;
      if (num == 1) {
       ssgEntity *kid = grp->getKid(0);
       if (grp->getName()) {
          if (kid->getName())
             break;
          kid->setName(grp->getName());
       }
       if (grp->getRef() == 0) {
          kid->ref();
          grp->removeKid(0);
          kid->deRef();
          delete grp;
       }
       node = kid;
       assert(!node->isA(0xDeadBeef));
      }
      else {
       if (grp->getRef() == 0)
          delete grp;
       node = 0;
      }
   }
#endif

#if 1
   /* see if we can merge LOD nodes */
   if (node && node->isAKindOf(ssgTypeBranch()) &&
       !node->isAKindOf(ssgTypeSelector())) {
      MergeLODs((ssgBranch *)node);
      assert(!node->isA(0xDeadBeef));
   }
#endif

   /* set limits on animated nodes */
   if (node && node->isA(ssgTypeTimedSelector())) {
      ssgTimedSelector *sw = (ssgTimedSelector *) node;
      if (sw->getNumKids() > 1) {
       sw->setDuration(30.0f);
       sw->setLimits(0, sw->getNumKids() - 1);                
       sw->control(SSG_ANIM_START);
      }
   }

   /* apply node attributes */
   if (node && attr) {

      if (attr->transform) {

       ssgTransform *scs = new ssgTransform;        
       scs->setTransform(attr->mat);
       scs->addKid(node);
       
       if (attr->replicate > 0) {
          ssgBranch *grp;
          sgMat4 mat;
          int i;
          grp = new ssgBranch;
          grp->addKid(scs);
          sgCopyMat4(mat, attr->mat);
#if 0
          ulSetError(UL_DEBUG, "replicating %d times", attr->replicate);
          for (i = 0; i < 4; i++)
             ulSetError(UL_DEBUG, "  %6.2f %6.2f %6.2f %6.2f", mat[i][0], mat[i][1], mat[i][2], mat[i][3]);
#endif
          for (i = 0; i < attr->replicate; ++i) {
             sgPostMultMat4(mat, attr->mat);
             scs = new ssgTransform;
             scs->setTransform(mat);
             scs->addKid(node);
             grp->addKid(scs);
          }
          node = grp; /* there's no point in cleaning this construction */
          /*ulSetError(UL_DEBUG, "[flt] replicated %d times", attr->replicate);*/
       }
       else {
          node = scs; // PostClean(scs, 0);
          /*ulSetError(UL_DEBUG, "[flt] added transformation");*/
       }
      }
      
      /* apply level of detail */
      if (attr->islod) {
       float ranges[2];
       ranges[0] = MIN(attr->range[0], attr->range[1]);
       ranges[1] = MAX(attr->range[0], attr->range[1]);
       if (ranges[1] > MAX(0, ranges[0])) {
          ssgRangeSelector *lod = new ssgRangeSelector;
          lod->setRanges(ranges, 2);

          if (sgLengthVec3(attr->center) > 0.01f) { /* XXX */
             ssgTransform *t1, *t2;
             sgMat4 mat;
             sgMakeTransMat4(mat, attr->center[0], attr->center[1], attr->center[2]);
             t1 = new ssgTransform;
             t1->setTransform(mat);
             sgMakeTransMat4(mat, -attr->center[0], -attr->center[1], -attr->center[2]);
             t2 = new ssgTransform;
             t2->setTransform(mat);
             t1->addKid(lod);
             lod->addKid(t2);
             t2->addKid(node);
             node = t1;
          }
          else {
             lod->addKid(node);
             node = lod;
          }
       }
      }

      /* setup switch records */
      if (attr->num_masks > 0) {
      ssgTimedSelector *sw = new ssgTimedSelector;
      int n = ((ssgBranch *) node) -> getNumKids();
      if (n > 32 * attr->num_words) n = 32 * attr->num_words;
      for (int i = 0; i < attr->num_masks; i++) {
        ssgBranch *br = new ssgBranch;
        for (int j = 0; j < n; j++) {
          if (attr->mask_words[j / 32] & (1u << (j % 32)))
            br -> addKid(((ssgBranch *) node) -> getKid(j));
        }
        sw -> addKid(br);
      }
      if (node->getRef() == 0) {
        ((ssgBranch *) node) -> removeAllKids();
        delete node;
      }
      sw->setMode(SSG_ANIM_SHUTTLE);
      sw->setDuration(30.0f);
      sw->setLimits(0, attr->num_masks - 1);    
      sw->control(SSG_ANIM_START);
      node = sw;
      }
   }

   if (attr)
      delete attr;

   assert(node == 0 || !node->isA(0xDeadBeef));

   return node;
}

/* link nodes while removing crap (post traversal) */
static void PostLink(ssgEntity **stack, fltNodeAttr **attr, 
                 int instance, fltState *state)
{
#if 0
   ulSetError(UL_DEBUG, "PostLink: %s %s <-- %s %s",
           stack[0] ? pfGetTypeName(stack[0]) : "0", stack[0] ? pfGetNodeName(stack[0]) : "0",
           stack[1] ? pfGetTypeName(stack[1]) : "0", stack[1] ? pfGetNodeName(stack[1]) : "0");
#endif

   if (stack[1] == 0) {
      if (attr[1]) {
         delete attr[1];
       attr[1] = 0;
      }
      return;
   }
   assert(!stack[1]->isA(0xDeadBeef));

   stack[1] = PostClean(stack[1], attr[1]);
   
   if (stack[1] && instance >= 0) {
       state->refs = sinsert(state->refs, (void *)instance, 0, ptrcmp);
       if (state->refs->data != (void *)-1) {
         ulSetError(UL_WARNING, "[flt] Instance %d redefined.", instance);
         ssgDeRefDelete((ssgEntity *) state->refs->data);
       }
       state->refs->data = stack[1];
       stack[1]->ref();
   }
   
   if (stack[0] == 0) {
      stack[0] = stack[1];
      if (attr[0]) {
        delete attr[0];
        attr[0] = 0;
      }
   }
   else {
      assert(!stack[0]->isA(0xDeadBeef));
      if (stack[1]) {
         if (stack[0]->isAKindOf(ssgTypeBranch())) {
          ((ssgBranch *)stack[0])->addKid(stack[1]);
       }
       else {
            ssgBranch *grp = new ssgBranch;
            grp->addKid(stack[0]);
            grp->addKid(stack[1]);
            stack[0] = PostClean(grp, 0);
         }
      }
   }

   stack[1] = 0;
   attr[1] = 0;
}

/* group/object ancillary chunks */
static int AttrChunks(ubyte *ptr0, ubyte *end, fltNodeAttr **attrp)
{
   ubyte *ptr = ptr0;
   int op, len, done = 0;
   fltNodeAttr *attr;

   attr = *attrp;

   while (!done) {
      
      if (ptr + 4 > end)
         break;
      op = get16u(ptr);
      len = get16u(ptr + 2);
      if (len < 4 || (len & 3) != 0 || ptr + len > end)
         break;

      switch (op) {

      case 31: /* Comment */
         ptr += len;
         break;

      case 33: { /* Long ID */
       int n = len - 4;
       if (n > 0 && n < 256) {
          if (attr == 0) 
             attr = new fltNodeAttr;
          //attr->name = (char *)malloc(n + 1);
          attr->name = new char[n + 1];
          memcpy(attr->name, ptr + 4, n);
          attr->name[n] = 0;
       }
         ptr += len;
         break;
      }

      case 60: { /* Replicate */
       if (attr == 0)
          attr = new fltNodeAttr;
       attr->replicate = get16u(ptr + 4);
         ptr += len;
         break;
      }

      case 49: { /* Transfomation Matrix */
       sgMat4 mat;
       int i, j;
       get32v(ptr + 4, mat, 16);
       for (i = 0; i < 4; i++) {
          for (j = 0; j < 4; j++) {
             float d = mat[i][j] - (i == j ? 1.0f : 0.0f);
             if (ABS(d) > 0.001f)
              break;
          }
          if (j < 4)
             break;
       }
       if (i < 4) {
          if (attr == 0)
             attr = new fltNodeAttr;
          attr->transform = 1;
          sgCopyMat4(attr->mat, mat);
       }
         ptr += len;
         break;
      }

      case 12: /* Translate (obsolete) */
      case 40: /* Translate (obsolete) */
      case 41: /* Rotate about Point (obsolete) */
      case 42: /* Rotate about Edge (obsolete) */
      case 43: /* Scale (obsolete) */
      case 44: /* Translate (obsolete) */
      case 45: /* Scale (obsolete) */
      case 46: /* Rotate about Point (obsolete) */
      case 47: /* Rotate and/or Scale about Point (obsolete) */
      case 48: /* Put Transform (obsolete) */
      case 51: /* Bounding Box (obsolete) */
      case 77: /* Scale (obsolete) */
      case 110: /* Histogram Bounding Volume (obsolete) */
       Obsolete(op);
       ptr += len;
       break;

      case 74: /* Bounding Box */
      case 76: /* Rotate about Edge */
      case 78: /* Translate */
      case 79: /* Scale */
      case 80: /* Rotate about Point */
      case 81: /* Rotate and/or Scale */
      case 82: /* Put */
      case 88: /* Road Zone */
      case 94: /* General Matrix */
      case 100: /* Extension Attribute */
      case 105: /* Bounding Sphere */
      case 106: /* Bounding Cylinder */
      case 108: /* Bounding Volume Center */
      case 109: /* Bounding Volume Orientation */
      case 116: /* CAT Data */
       /* these are safe to ignore */
         ptr += len;
         break;

      default:
         done = 1;
         break;
      }
   }

   *attrp = attr;

   return ptr - ptr0;
}

static ssgEntity *LoadFLT(const char *path);

/* object hierarchy chunks */
static ssgEntity *HierChunks(ubyte *ptr, ubyte *end, fltState *state)
{
   ssgEntity *stack[MAXDEPTH + 1];
   fltNodeAttr *attr[MAXDEPTH + 1];
   int instance[MAXDEPTH + 1];
   int sp, op, len, k;

   stack[0] = new ssgBranch;
   stack[0]->setName("reserved");
   attr[0] = 0;
   instance[0] = -1;
   stack[1] = 0;
   attr[1] = 0;
   instance[1] = -1;
   sp = 1;

   for (;;) {

      if (ptr + 4 > end)
         break;
      op = get16u(ptr);
      if (op < 1 || op > 150)
         break;
      len = get16u(ptr + 2);
      if (len < 4 || (len & 3) != 0 || ptr + len > end)
         break;

#if 0
      for (int i = 0; i < sp; i++)
        putchar('\t');
      printf("op %d\n", op);
#endif
      
      switch (op) {

      case 10: /* Push */
         if (stack[sp] && !stack[sp]->isAKindOf(ssgTypeBranch())) {
            /* shouldn't happen */
            ulSetError(UL_DEBUG, "[flt] Objects are not allowed to contain other objects or groups.");
            PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
          instance[sp] = -1;
         }
       if (sp >= MAXDEPTH) {
          ulSetError(UL_WARNING, "[flt] Stack overflow.");
       }
       else {
          sp++;
          stack[sp] = 0;
          attr[sp] = 0;
          instance[sp] = -1;
       }
       ptr += len;
         break;
         
      case 11: /* Pop */
         if (sp == 1) 
            ulSetError(UL_WARNING, "[flt] Stack underflow.");
         else {
            PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
            sp--;
         }
         ptr += len;
         break;

      case 4: { /* Object */

         /*
          * Object Record Format 
          *
          * Int        0  2  Object Opcode 4 
          * Unsigned   2  2  Length of the record 
          * Char       4  8  7 char ASCII ID; 0 terminates 
          * Boolean   12  4  Flags (bits from to right) 
          *                     0 = Don't display in daylight 
          *                     1 = Don't display at dusk 
          *                     2 = Don't display at night 
          *                     3 = Don't illuminate 
          *                     4 = Flat shaded 
          *                     5 = Group's shadow object 
          *                     6-31 = Spare 
          * Int       16  2  Relative priority 
          * Unsigned  18  2  Transparency
          *                     0 = Opaque 
          *                     65535 = Totally clear 
          * Int       20  2  Special effect ID1 - application defined 
          * Int       22  2  Special effect ID2 - application defined 
          * Int       24  2  Significance 
          * Int       26  2  Spare
          *
          */

       int flags = get32i(ptr + 12);
       int trans = get16u(ptr + 18);
         PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
       instance[sp] = -1;
         ptr += len;
         ptr += AttrChunks(ptr, end, &attr[sp]);
       state->parent_name = (char *)ptr + 4; /* OK?? */
         ptr += GeomChunks(ptr, end, state, &stack[sp], flags, trans);
       state->parent_name = 0;
       if (stack[sp] && stack[sp]->getName() == 0 && ptr[4])
          stack[sp]->setName((char *)ptr + 4);
         break;
      }

      case 5: /* Face */
         /* polygons are not allowed to be outside objects, but this rule is not always respected */
       //ulSetError(UL_DEBUG, "[flt] Implicit object.");
         PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
       instance[sp] = -1;
         ptr += GeomChunks(ptr, end, state, &stack[sp], 0, 0);
         break;

      case 2: /* Group */
      case 14: /* Degree of Freedom */
      case 73: /* Level of Detail */
      case 96: /* Switch */
      case 98: /* Clip Region */

         PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
       instance[sp] = -1;

       switch (op) {

       case 2: { /* Group */
#if 0 /* group animation - seems wrong... */
          int flags = (len >= 20) ? get32i(ptr + 16) : 0;
          if ((flags & 3) != 0) {
             ssgTimedSelector *sw = new ssgTimedSelector;
             sw->setMode((flags & 2) ? SSG_ANIM_SWING : SSG_ANIM_SHUTTLE);
             stack[sp] = sw;
          }
          else 
#endif
            {
             stack[sp] = new ssgBranch;
          }
          break;
       }

       case 14: { /* Degree of Freedom */
          stack[sp] = new ssgTransform; 
          break;
       }

       case 73: { /* Level of Detail */
          fltNodeAttr *a;
          double v[3];
          attr[sp] = a = new fltNodeAttr;
          a->islod = 1;
          get64v(ptr + 16, v, 2);
          sgSetVec2(a->range, (float)v[0], (float)v[1]);
          get64v(ptr + 40, v, 3);
          sgSetVec3(a->center, (float)v[0], (float)v[1], (float)v[2]);
            stack[sp] = new ssgBranch;
          break;
       }

       case 96: { /* Switch */
          int num_words = (len > 28) ? get32i(ptr + 20) : -1;
          int num_masks = (len > 28) ? get32i(ptr + 24) : -1;
          if (num_words <= 0 || num_masks <= 0 || len < 28 + 4 * num_words * num_masks) {
             ulSetError(UL_DEBUG, "[flt] Incomplete switch record.");
          }
          else {
             fltNodeAttr *a = new fltNodeAttr;
             a->current_mask = get32i(ptr + 16);
             a->num_masks = num_masks;
             a->num_words = num_words;
             a->mask_words = new uint [ num_masks * num_words ];
             get32v(ptr + 28, a->mask_words, num_masks * num_words);
             attr[sp] = a;
          }
          stack[sp] = new ssgBranch;
          break;
       }

       default: { /* Others (i.e. 98 Clip Region) */
          stack[sp] = new ssgBranch;
          break;
       }

         }

       if (ptr[4])
          stack[sp]->setName((char *)ptr + 4);

         ptr += len;
         ptr += AttrChunks(ptr, end, &attr[sp]);

         break;

      case 61: /* Instance Reference */
         k = get16u(ptr + 6);
       if (k != instance[sp]) { // current instance inserted by default
           PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
           instance[sp] = -1;
           if (state->refs) {
             state->refs = splay(state->refs, (void *)k, ptrcmp);
             if (state->refs->key == (void *)k) {
                 stack[sp] = (ssgEntity *)state->refs->data;
             }
           }
       }
       ptr += len;
         ptr += AttrChunks(ptr, end, &attr[sp]);
         break;

      case 62: /* Instance Definition */
         k = get16u(ptr + 6);
#if 0  
         if (stack[sp]) {
          state->refs = sinsert(state->refs, (void *)k, 0, ptrcmp);
          if (state->refs->data == (void *)-1) {
             state->refs->data = stack[sp];
             stack[sp]->ref();
          }
       }
       else 
       {
           ulSetError(UL_DEBUG, "[flt] yeah, but the node is empty!");
       }
#else  
       instance[sp] = k;
#endif
         ptr += len;
         break;

      case 63: /* External Reference */
         /*ulSetError(UL_DEBUG, "external reference %s", ptr + 4);*/
         PostLink(stack + sp - 1, attr + sp - 1, instance[sp], state);
       instance[sp] = -1;
         if (!NoExternals) {
            char *file = (char *)ptr + 4, *p;
          if ((p = strrchr(file, '/')))
            file = p + 1;
          //stack[sp] = LoadFLT(file);
          stack[sp] = ssgLoad (file);
         }
         ptr += len;
         ptr += AttrChunks(ptr, end, &attr[sp]);
         break;

      case 31: /* Text Comment */
      case 21: /* Push Extension */
      case 22: /* Pop Extension */
      case 55: /* Binary Separating Plane */
      case 87: /* Road Segment */
      case 90: /* Linkage */
      case 91: /* Sound Bead */
      case 92: /* Path Bead */
      case 95: /* Text */
      case 101: /* Light Source Bead */
      case 122: /* Push Attribute */
      case 123: /* Pop Attribute */
      //printf("op %d ignored\n", op);
       ptr += len;
       break;

      case 3:  /* Level of Detail (obsolete) */
      case 13: /* Degree of Freedom (obsolete) */
      case 16: /* Instance Reference (obsolete) */
      case 17: /* Instance Definition (obsolete) */
       Obsolete(op);
         ptr += len;
         break;

      default:
       NotImplemented(op);
         ptr += len;
      }
   }

   /* pop stack (expected one iteration but may be more for incomplete databases) */
   while (sp-- > 0)
      PostLink(stack + sp, attr + sp, -1, 0);
   
   if (stack[0])
      stack[0] = PostClean(stack[0], attr[0]);
   else if (attr[0])
      delete attr[0]; // possible?

   return stack[0];
}

/* parse the vertex table */
static int VertexTable(ubyte *ptr0, ubyte *end, fltState *state)
{
   int len, size, num, i;
   ubyte *ptr = ptr0;

   assert(get16u(ptr) == 67); /* vtx tab op code */
   len = get16u(ptr + 2);

   size = get32i(ptr + 4);
   /*ulSetError(UL_DEBUG, "vertex table header len %d, total size %d", len, size);*/
   num = (size - len)/40; /* max # of vertices */
   if (num <= 0 || state->vtab) {
      if (state->vtab)
       ulSetError(UL_WARNING, "[flt] Multiple vertex tables not allowed.");
      return size;
   }
   state->vtab = ptr;
   end = MIN(end, ptr + size);
   ptr += len;

   state->offset   = new int [num];
   state->bind     = new ubyte [num];
   state->coord    = new sgVec3 [num];
   state->color    = new sgVec4 [num];
   state->normal   = new sgVec3 [num];
   state->texcoord = new sgVec2 [num];

   for (i = 0; i < num && ptr + 40 <= end; ++i) {
      double tmp[3];
      ubyte *p = ptr;
      int op = get16u(p);
      int len = get16u(p + 2);
      int flags = get16u(p + 6);
      int bind = 0;
      if (ptr + len > end)
         break;
      state->offset[i] = ptr - ptr0;
      get64v(p + 8, tmp, 3);
      sgSetVec3(state->coord[i], (float)tmp[0], (float)tmp[1], (float)tmp[2]);
      sgSetVec4(state->color[i], 1, 1, 1, 1);
      sgSetVec3(state->normal[i], 0, 0, 1);
      sgSetVec2(state->texcoord[i], 0, 0);
      p += 32;
      if (op == 69 || op == 70) {
       get32v(p, state->normal[i], 3);
       sgNormalizeVec3(state->normal[i]);
       p += 12;
       bind |= BIND_NORMAL;
      }
      if (op == 70 || op == 71) {
         get32v(p, state->texcoord[i], 2);
         p += 8;
         bind |= BIND_TEXCOORD;
      }
      if (!(flags & 4)) {
       if ((flags & 8) && p + 4 <= ptr + len) {
          UNPACK_ABGR(state->color[i], p);
          //ulSetError(UL_DEBUG, "packed ABGR: %d %d %d %d", p[0], p[1], p[2], p[3]);
          bind |= BIND_COLOR;
       }
       else if (state->revision > 1400) {
          int color;
          if (state->revision > 1500 && p + 8 <= ptr + len) {
             color = get32i(p + 4);
          }
          else {
             color = get16u(ptr + 4);
             if (color == 65535)
              color = -1;
          }
          int index = color / 128;
          int intensity = color % 128;
          if (color >= 0 && state->ctab && index < state->cnum) {
             //ulSetError(UL_DEBUG, "colour %d: index %d, intensity %d", color, index, intensity);
             UNPACK_ABGR2(state->color[i], state->ctab[index], intensity);
             bind |= BIND_COLOR;
          }
       }
      }
      /*
       if (bind & BIND_COLOR)
       ulSetError(UL_DEBUG, "vertex #%d color %.2f %.2f %.2f", i,
            state->color[i][0],
            state->color[i][1],
            state->color[i][2]);
      */
      state->bind[i] = bind;
      ptr += len;      
   }
   /*ulSetError(UL_DEBUG, "got %d vertices", i);*/

   state->vnum = i;

   return size;
}

/* header ancillary chunks */
static int TableChunks(ubyte *ptr0, ubyte *end, fltState *state)
{
   ubyte *ptr = ptr0;
   int op, len, index, done = 0;

   while (!done) {
      
      if (ptr + 4 > end)
         break;
      op = get16u(ptr);
      len = get16u(ptr + 2);
      if (len < 4 || (len & 3) != 0 || ptr + len > end)
         break;

      switch (op) {

      case 32: /* Color Table */
       if (len < 132 + 4 * 512) {
          /* note: in older files it appears that the
           * color table is stored as 16-bit integers.
           * i have no documentation on this.
           * maybe 16 x 16 colors (rather than 512 or 1024 x 128).
           */
          if (state->revision <= 1400) {
             ulSetError(UL_WARNING, "[flt] Color table ignored (unknown format).");
             /*hexdump(UL_DEBUG, ptr, len, 0);*/
          }
          else
             BAD_CHUNK(ptr, "Color Table");
       }
       else  if (state->ctab == 0) {
          int max = (len - 132) / 4;
            state->ctab = (ubyte (*)[4])(ptr + 132);
          state->cnum = MIN(state->revision > 1500 ? 1024 : 512, max);
#if 0
          int i;
          for (i = 0; i < state->cnum; i++)
             ulSetError(UL_DEBUG, "%d %02x %02x %02x %02x", i, 
                                state->ctab[i][0], state->ctab[i][1], 
                                state->ctab[i][2], state->ctab[i][3]);
#endif
       }
       else {
          ulSetError(UL_WARNING, "[flt] Multiple color tables are not allowed.");
       }
         ptr += len;
         break;

      case 64: /* Texture Reference */
         if (!NoTextures) {
          if (len == 96 || len == 216) {
             char *file = (char *)ptr + 4, *p;
             if ((p = strrchr(file, '/')))
              file = p + 1;
             index = get32i(ptr + len - 12);
             state->texs = sinsert(state->texs, (void *)index, 0, ptrcmp);
             if (state->texs->data == (void *)-1) {
              //fltTexture *tex = (fltTexture *)malloc(sizeof(fltTexture));
              fltTexture *tex = new fltTexture;
              assert ( tex != NULL );
              tex->file = file;
              tex->state = (ssgState *)-1;
              tex->tex = (ssgTexture *)-1;
              state->texs->data = tex;
             }
          }
          else {
             BAD_CHUNK(ptr, "Texture Reference");
          }
       }
         ptr += len;
         break;

      case 66: /* Material Table */
       if ((len - 4) % 184 != 0) {
          BAD_CHUNK(ptr, "Material Table");
       }
       else if (state->mtls == 0) {
          ubyte *p = ptr + 4;
            int i, j, n = (len - 4) / 184;
            for (i = 0; i < n; ++i) {
             float *mtl;
             state->mtls = sinsert(state->mtls, (void *)i, 0, ptrcmp);
             //state->mtls->data = malloc(sizeof(float)*14);
             state->mtls->data = new float[14];
             mtl = (float *)state->mtls->data;
               get32v(p, mtl, 14);
             for (j = 0; j < 12; j++)
              mtl[j] = CLAMP(mtl[j], 0, 1);
             mtl[12] = CLAMP(mtl[12], 8, 128);
             mtl[13] = CLAMP(mtl[13], 0, 1);
#if 0
             float r, g, b, s;
             r = mtl[0] + mtl[3] + mtl[6] + mtl[9];
             g = mtl[1] + mtl[4] + mtl[7] + mtl[10];
             b = mtl[2] + mtl[5] + mtl[8] + mtl[11];
             s = MAX3(r, g, b);
             if (s > 1.0f) {
              s = 1.0f/s;
              for (j = 0; j < 12; j++)
                 mtl[j] *= s;
             }
#endif
               p += 184;
            }
         }
       else {
          ulSetError(UL_WARNING, "[flt] Multiple material tables are not allowed");
       }
       ptr += len;
         break;

      case 67: /* Vertex Table (header) */
         ptr += VertexTable(ptr, end, state);
         break;

      case 113: /* Material */
       index = get32i(ptr + 4);
       state->mtls = sinsert(state->mtls, (void *)index, 0, ptrcmp);
       if (state->mtls->data == (void *)-1) {
          float *mtl;
          int i;
          //state->mtls->data = malloc(sizeof(float)*14);
          state->mtls->data = new float[14];
          mtl = (float *)state->mtls->data;
          get32v(ptr + 24, mtl, 14);
          for (i = 0; i < 12; i++)
             mtl[i] = CLAMP(mtl[i], 0, 1);
          mtl[12] = CLAMP(mtl[12], 8, 128);
          mtl[13] = CLAMP(mtl[13], 0, 1);
#if 0
          float r, g, b, s;
          r = mtl[0] + mtl[3] + mtl[6] + mtl[9];
          g = mtl[1] + mtl[4] + mtl[7] + mtl[10];
          b = mtl[2] + mtl[5] + mtl[8] + mtl[11];
          s = MAX3(r, g, b);
          if (s > 1.0f) {
             s = 1.0f/s;
             for (i = 0; i < 12; i++)
              mtl[i] *= s;
          }
#endif
       }
         ptr += len;
         break;         

      case 65: /* Eyepoint Palette (obsolete) */
       Obsolete(op);
       ptr += len;
       break;

      case 31: /* Text Comment */
      case 83: /* Eyepoint and Trackplane */
      case 90: /* Linkage Palette */
      case 93: /* Sound Palette */
      case 97: /* Line Style Palette */
      case 102: /* Light Source Palette */
      case 103: /* Reserved */
      case 104: /* Reserved */
      case 112: /* Texture Mapping */
      case 114: /* Name Table */
       /* these are safe to ignore */
       ptr += len;
       break;

      default:
      //printf("op %d: end of table chunks\n", op);
         done = 1;
      }
   }

   return ptr - ptr0;
}

static int CheckHeader(ubyte *ptr, ubyte *end, fltState *state)
{
   /*const char *unit[9] = {"meters", "kilometers", "", "", "feet", "inches", "", "", "nautical miles"};*/
   int len, k;
   if (get16u(ptr) != 1) {
      ulSetError(UL_WARNING, "[flt] Wrong header opcode (%d).", get16i(ptr));
      return -1;
   }
   len = get16u(ptr + 2);
   if (len < 128 || len > 1024) {      
      ulSetError(UL_WARNING, "[flt] Suspicious header record length (%d).", len);
      return -1;
   }
   k = get32i(ptr + 12);
   if (k < 100) {
      state->revision = 100 * k;
      state->major = k;
      state->minor = 0;
   }
   else {
      state->revision = k;
      state->major = k / 100;
      state->minor = k % 100;
   }
   if (state->major < 11 || state->major > 16) {
      ulSetError(UL_WARNING, "[flt] Suspicious format revision number (%d).", k);
      return -1;
   }
/*
   ulSetError(UL_DEBUG, "[flt] Loading %s %sFlight v%d.%d",
         state->filename,
         state->major > 13 ? "Open" : "",
         state->major,
         state->minor);
*/
   return len;
}

#if 0
struct snode *refs;
static int nrefs;

static void ptree(ssgEntity *node, FILE *f, int d)
{
   int i;   
   for (i = 0; i < d; ++i)
      fprintf(f, "   ");
   {
      const char *p = node->getName();
      fprintf(f, "%s \"%s\"", node->getTypeName(), p ? p : "");
   }
   if (node->getNumParents() > 1) {
      refs = sinsert(refs, node, 0, ptrcmp);
      if (refs->data == (void *)-1) {
         fprintf(f, " (%d)", nrefs);
       refs->data = (void *)nrefs++;
      }
      else {
         fprintf(f, " (%d) ...\n", (int)refs->data);
         return;
      }
   }
   assert(!node->isA(0xDeadBeef));
   if (node->isAKindOf(ssgTypeLeaf())) {
      ssgLeaf *leaf = (ssgLeaf *)node;
      ssgState *st = leaf->getState();
      fprintf(f, " %d tris", leaf->getNumTriangles());
      if (st && st->isAKindOf(ssgTypeSimpleState())) {
       ssgSimpleState *ss = (ssgSimpleState *)st;
       char *file = ss->getTextureFilename();
       if (file) {
          char *p;
          if ((p = strrchr(file, '/'))) 
             file = p + 1;
          fprintf(f, " %s", file);
       }
      }
   }
   if (node->isAKindOf(ssgTypeTransform())) {
      sgMat4 mat;
      ((ssgTransform *)node)->getTransform(mat);
      fprintf(f, " pos %.2f %.2f %.2f", mat[3][0], mat[3][1], mat[3][2]);
   }
   if (node->isAKindOf(ssgTypeRangeSelector())) {
      ssgRangeSelector *lod = (ssgRangeSelector *)node;
      fprintf(f, " ranges");
      for (i = 0; i <= lod->getNumKids(); i++)
       fprintf(f, " %.2f", lod->getRange(i));
   }
   putc('\n', f);
   if (node->isAKindOf(ssgTypeBranch())) {
      ssgBranch *grp = (ssgBranch *)node;
      int n = grp->getNumKids();
      for (i = 0; i < n; ++i)
       ptree(grp->getKid(i), f, d+1);
   }
}
#endif

static const char *FindFile(const char *file)
{
   /* XXX fixme! */
   static char path[1024];

   if (ulFileExists((char *)file))
      return file;

   ssgGetCurrentOptions () -> makeModelPath ( path, file ) ;
   if (ulFileExists(path))
      return path;
   
   ulSetError(UL_WARNING, "[flt] %s not found.", file);
   
   return 0;
}

static struct snode *FltCache;

#ifdef UL_WIN32

static void win32_perror(const char *s)
{
   LPVOID lpMsgBuf;
   FormatMessage(
        FORMAT_MESSAGE_ALLOCATE_BUFFER |
        FORMAT_MESSAGE_FROM_SYSTEM |
        FORMAT_MESSAGE_IGNORE_INSERTS,
        NULL,
        GetLastError(),
        MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT),
        (LPTSTR) &lpMsgBuf,
        0,
        NULL
    );
    fprintf(stderr, "%s: %s\n", s, lpMsgBuf);
    LocalFree( lpMsgBuf );
}

#endif

static ssgEntity *LoadFLT(const char *file)
{
   struct snode *cache;
   cache = FltCache = sinsert(FltCache, (void *)file, strlen(file) + 1, (sfunc)strcmp);
   if (cache->data == (void *)-1) {
      cache->data = NULL; /* avoid looping */
      
      fltState *state = 0;
      int size = 0, len;
      ubyte *ptr = 0, *end;
      ssgEntity *node = 0;

#ifdef USE_WIN32_MMAP

      HANDLE fd = INVALID_HANDLE_VALUE;
      HANDLE map = 0;

#else

      int fd = -1;
#ifdef USE_POSIX_MMAP
      struct stat st;
#else
      ubyte buf[256];
#endif

#endif
      
      do { /* dummy loop */

       const char *path, *name;

       path = FindFile(file);
       if (path == 0)
          break;

#ifdef USE_WIN32_MMAP
       
       fd = CreateFile(path, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 
                   FILE_ATTRIBUTE_NORMAL, 0);
       if (fd == INVALID_HANDLE_VALUE) {
          win32_perror(path);
          break;
       }
       
       size = GetFileSize(fd, NULL);
       if (size < 256)
          break;

       map = CreateFileMapping(fd, NULL, PAGE_READONLY, 0, size, NULL);
       if (map == 0) {
          win32_perror(path);
          break;
       }

       ptr = (ubyte *)MapViewOfFile(map, FILE_MAP_READ, 0, 0, 0);
       if (ptr == 0) {
          win32_perror(path);
          break;
       }

#else /* USE_WIN32_MAP */

       if ((fd = open(path, O_RDONLY|O_BINARY)) == -1) {
          perror(path);
          break;
       }

#ifdef USE_POSIX_MMAP
       if (fstat(fd, &st)) {
          perror(file);
          break;
       }
       size = st.st_size;
       if (size < 256)
          break;
       ptr = (ubyte *)mmap(0, size, PROT_READ, MAP_SHARED, fd, 0);
       if (ptr == (ubyte *)-1) {
          perror(file);
          break;
       }
       close(fd);
       fd = -1;
#else /* USE_POSIX_MMAP */
       if (read(fd, buf, 256) != 256) {
          perror(file);
          break;
       }
       ptr = buf;
#endif /* ! USE_POSIX_MMAP */

#endif /* ! USE_WIN32_MMAP */
       
       /*putc('\n', stderr);*/

       name = strrchr(file, '/');
       if (name)
          name++;
       else
          name = file;

       state = new fltState;
       state->filename = name;
       
       len = CheckHeader(ptr, ptr + 256, state);
       if (len == -1)
          break;
       
#if !defined(USE_POSIX_MMAP) && !defined(USE_WIN32_MMAP)

       if ((size = lseek(fd, 0, SEEK_END)) == -1) {
          perror(file);
          break;
       }
       //ptr = (ubyte *)malloc(size);
       ptr = new ubyte[size];
       lseek(fd, 0, SEEK_SET);
       if (read(fd, ptr, size) != size) {
          perror(file);
          break;
       }
       close(fd);
       fd = -1;

#endif
       
       end = ptr + size;
       len += TableChunks(ptr + len, end, state);
       node = HierChunks(ptr + len, end, state);
       
       if (node)
          node->setName((char *)name);
       
      } while (0);

      delete state;

#ifdef USE_WIN32_MMAP
      
      if (ptr) 
       UnmapViewOfFile(ptr);
      if (map)
       CloseHandle(map);
      if (fd != INVALID_HANDLE_VALUE)
       CloseHandle(fd);

#else /* USE_WIN32_MMAP */
      
      if (fd != -1)
       close(fd);
      
#ifdef USE_POSIX_MMAP
      if (ptr != 0 && ptr != (ubyte *)-1)
       munmap((char *)ptr, size);
#else
      if (ptr != 0 && ptr != buf)
       //free(ptr);
       delete [] ptr;
#endif

#endif /* ! USE_WIN32_MMAP */
      
      cache->data = node;
      if (node) node->ref();
   }

   return (ssgEntity *)cache->data;
}

#if 0
static struct snode *Flattened;

static ssgEntity *Flatten(ssgEntity *node, float (*mat)[4])
{
   if (node == 0)
      return 0;

   assert(!node->isA(0xDeadBeef));

   /* some nodes cannot be flattened. only types that may be 
    * generated by the loader are considered here.
    */
   if (node->getRef() > 0 || 
       node->isAKindOf(ssgTypeRangeSelector()) ||
       node->isAKindOf(ssgTypeCutout())) {
      if (node->isAKindOf(ssgTypeBranch())) {
       /* see if we have flattened beyond this node already */
       int completed = 0;
       if (node->getNumParents() > 0) {
          Flattened = sinsert(Flattened, node, 0, ptrcmp);
          if (Flattened->data == (void *)-1) {
             Flattened->data = 0;
          }
          else {
             completed = 1;
          }
       }
       if (!completed) {
          /* traverse */
          ssgBranch *grp = (ssgBranch *)node;
          int i, n = grp->getNumKids();
          if (n > 0) {
             ssgEntity *kids[32];
             for (i = n; i--;) {
              kids[i] = grp->getKid(i);
              kids[i]->ref(); grp->removeKid(i); kids[i]->deRef();
              kids[i] = Flatten(kids[i], 0);
              assert(kids[i] == 0 || !kids[i]->isA(0xDeadBeef));
             }
             for (i = 0; i < n; i++)
              if (kids[i])
                 grp->addKid(kids[i]);
             grp->recalcBSphere();
          }
       }
      }
      /* insert a transform if required */
      if (mat) {
       ssgTransform *scs = new ssgTransform;
       scs->setTransform(mat);
       scs->addKid(node);
       node = scs;
      }
      return node;
   }

   assert(node->getNumParents() == 0);

   /* accumulate transformations */
   if (node->isAKindOf(ssgTypeTransform())) {
      ssgTransform *scs = (ssgTransform *)node;
      int i, n = scs->getNumKids();
      if (n <= 0) {
       delete scs;
       return 0;
      }
      else {
       sgMat4 tmp;
       scs->getTransform(tmp);
       if (mat)
          sgPostMultMat4(tmp, mat);
       if (n == 1) {
          node = scs->getKid(0);
          node->ref(); scs->removeKid(0); node->deRef();
          delete scs;
          assert(!node->isA(0xDeadBeef));
          return Flatten(node, tmp);
       }
       else {
          ssgBranch *grp = new ssgBranch;
          grp->setName(scs->getName());
          for (i = 0; i < n; i++)
             grp->addKid(scs->getKid(i));
          while (n--)
             scs->removeKid(n);
          delete scs;
          return Flatten(grp, tmp);
       }
      }
   }

   /* recurse the scene graph */
   if (node->isAKindOf(ssgTypeBranch())) {
      ssgBranch *grp = (ssgBranch *)node;
      int i, n = grp->getNumKids();
      if (n <= 0) {
       delete grp;
       return 0;
      }
      else if (n == 1 && grp->isA(ssgTypeBranch())) {
       ssgEntity *kid = grp->getKid(0);
       kid->ref(); grp->removeKid(0); kid->deRef();
       delete grp;
       assert(!kid->isA(0xDeadBeef));
       return Flatten(kid, mat);
      }
      else {
       ssgEntity *kids[32];
       for (i = n; i--;) {
          kids[i] = grp->getKid(i);
          kids[i]->ref(); grp->removeKid(i); kids[i]->deRef();
          kids[i] = Flatten(kids[i], mat);
          assert(kids[i] == 0 || !kids[i]->isA(0xDeadBeef));
       }
       assert(!grp->isA(0xDeadBeef));
       for (i = 0; i < n; i++) {
          if (kids[i]) {
             assert(!kids[i]->isA(0xDeadBeef));
             grp->addKid(kids[i]);
          }
       }
       grp->recalcBSphere();
       return grp;
      }
   }

   /* transform geometry */
   if (node->isAKindOf(ssgTypeVtxTable()) && mat) {
      ssgVtxTable *g = (ssgVtxTable *)node;
      sgVec3 *a;
      int i, n;
      n = g->getNumVertices();
      if (n > 0) {
       g->getVertexList((void **)&a);
       for (i = 0; i < n; i++)
          sgXformPnt3(a[i], a[i], mat);
      }
      n = g->getNumNormals();
      if (n > 0) {
       g->getNormalList((void **)&a);
       for (i = 0; i < n; i++)
          sgXformVec3(a[i], a[i], mat);
      }
      g->recalcBSphere();
   }
   assert(!node->isA(0xDeadBeef));
   return node;
}
#endif

static void Init(void)
{
   if (Inited)
      return;
   Inited = 1;

#if !defined(USE_POSIX_MMAP) && !defined(USE_WIN32_MMAP)
   ulSetError(UL_DEBUG, "[flt] Memory mapped files not enabled, please check source code.");
#endif

#ifdef PROBE_ENDIAN
   {
      short tmp = 42;
      if (*(char *)&tmp == 42) {
         /* little endian */
         get16v = _swab16;
         get32v = _swab32;
         get64v = _swab64;
       ulSetError(UL_DEBUG, "[flt] Little endian architecture.");
      }
      else {
         /* big endian */
         get16v = _copy16;
         get32v = _copy32;
         get64v = _copy64;
       ulSetError(UL_DEBUG, "[flt] Big endian architecture.");
      }
   }
#endif

   if (getenv("FLTNOTEX"))    NoTextures = 1;
   if (getenv("FLTNOMIPMAP")) NoMipmaps = 1;
   if (getenv("FLTNOEXT"))    NoExternals = 1;
   if (getenv("FLTNOCLEAN"))  NoClean = 1;

   return;
}

ssgEntity *ssgLoadFLT(const char *filename, 
#ifdef NO_LOADER_OPTIONS
                  ssgHookFunc
#else
                  const ssgLoaderOptions *options
#endif
                  )
{
   static int depth = 0;
   ssgEntity *node;

   if (depth == 0) {

      Init();
     
      ObsoleteFlag = 0;
      NotImplementedFlag = 0;
      
      TexCache = 0;
      StateCache = 0;
      FltCache = 0;

#ifndef NO_LOADER_OPTIONS
      ssgSetCurrentOptions ( (ssgLoaderOptions*)options ) ;
      LoaderOptions = ssgGetCurrentOptions () ;
#endif

   }

   // no longjmp()'s please! (or this recursion test will fail)

   depth++;

   node = LoadFLT(filename);

   depth--;

   if (depth == 0) {
     
     sfree(TexCache, S_KEY | S_DATA);
     sfree(StateCache, S_KEY);

     if (node) node->ref(); // prevent this node from being deleted!
     sfree(FltCache, S_KEY | S_TREE);
     if (node) node->deRef();

   }

#if 0
   if (node && !NoClean) {
      Flattened = 0;
      node = Flatten(node, 0);
      sfree(Flattened, 0);
   }
#endif

#if 0 /* debug */
   if (node && getenv("FLTDUMP")) {
      const char *file = "/tmp/tree.txt";
      FILE *f = fopen(file, "w");
      if (f == 0)
       perror(file);
      else {
       refs = 0;
       nrefs = 0;
       ptree(node, f, 0);
       sfree(refs, 0);
       fclose(f);
       ulSetError(UL_DEBUG, "wrote %s", file);
      }
   }
#endif

   return node;
}
//lint -restore

Generated by  Doxygen 1.6.0   Back to index