summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSimon Howard2006-06-16 17:06:05 +0000
committerSimon Howard2006-06-16 17:06:05 +0000
commit77e5d2063724defc57b60599d27f1e7488463f69 (patch)
treeff1139053cb1debe71635b392f9973d3b05a4916
parent26a2ba193ee3d93421f9fd50f25534031cd0f456 (diff)
downloadchocolate-doom-77e5d2063724defc57b60599d27f1e7488463f69.tar.gz
chocolate-doom-77e5d2063724defc57b60599d27f1e7488463f69.tar.bz2
chocolate-doom-77e5d2063724defc57b60599d27f1e7488463f69.zip
Add hash table for fast texture lookup; refactor P_GroupLines to use an
O(n) rather than O(n^2) algorithm: faster loading maps like sid.wad map03 Subversion-branch: /trunk/chocolate-doom Subversion-revision: 558
-rw-r--r--src/p_setup.c64
-rw-r--r--src/r_data.c68
-rw-r--r--src/w_wad.c6
-rw-r--r--src/w_wad.h4
4 files changed, 113 insertions, 29 deletions
diff --git a/src/p_setup.c b/src/p_setup.c
index ab3847d1..f71202f5 100644
--- a/src/p_setup.c
+++ b/src/p_setup.c
@@ -1,7 +1,7 @@
// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
-// $Id: p_setup.c 432 2006-03-24 16:51:28Z fraggle $
+// $Id: p_setup.c 558 2006-06-16 17:06:05Z fraggle $
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
@@ -45,7 +45,7 @@
//-----------------------------------------------------------------------------
static const char
-rcsid[] = "$Id: p_setup.c 432 2006-03-24 16:51:28Z fraggle $";
+rcsid[] = "$Id: p_setup.c 558 2006-06-16 17:06:05Z fraggle $";
#include <math.h>
@@ -554,27 +554,61 @@ void P_GroupLines (void)
total++;
}
}
-
+
// build line tables for each sector
linebuffer = Z_Malloc (total*sizeof(line_t *), PU_LEVEL, 0);
+
+ for (i=0; i<numsectors; ++i)
+ {
+ // Assign the line buffer for this sector
+
+ sectors[i].lines = linebuffer;
+ linebuffer += sectors[i].linecount;
+
+ // Reset linecount to zero so in the next stage we can count
+ // lines into the list.
+
+ sectors[i].linecount = 0;
+ }
+
+ // Assign lines to sectors
+
+ for (i=0; i<numlines; ++i)
+ {
+ li = &lines[i];
+
+ if (li->frontsector != NULL)
+ {
+ sector = li->frontsector;
+
+ sector->lines[sector->linecount] = li;
+ ++sector->linecount;
+ }
+
+ if (li->backsector != NULL && li->frontsector != li->backsector)
+ {
+ sector = li->backsector;
+
+ sector->lines[sector->linecount] = li;
+ ++sector->linecount;
+ }
+ }
+
+ // Generate bounding boxes for sectors
+
sector = sectors;
for (i=0 ; i<numsectors ; i++, sector++)
{
M_ClearBox (bbox);
- sector->lines = linebuffer;
- li = lines;
- for (j=0 ; j<numlines ; j++, li++)
+
+ for (j=0 ; j<sector->linecount; j++)
{
- if (li->frontsector == sector || li->backsector == sector)
- {
- *linebuffer++ = li;
- M_AddToBox (bbox, li->v1->x, li->v1->y);
- M_AddToBox (bbox, li->v2->x, li->v2->y);
- }
+ li = sector->lines[j];
+
+ M_AddToBox (bbox, li->v1->x, li->v1->y);
+ M_AddToBox (bbox, li->v2->x, li->v2->y);
}
- if (linebuffer - sector->lines != sector->linecount)
- I_Error ("P_GroupLines: miscounted");
-
+
// set the degenmobj_t to the middle of the bounding box
sector->soundorg.x = (bbox[BOXRIGHT]+bbox[BOXLEFT])/2;
sector->soundorg.y = (bbox[BOXTOP]+bbox[BOXBOTTOM])/2;
diff --git a/src/r_data.c b/src/r_data.c
index 3d193c39..52999dac 100644
--- a/src/r_data.c
+++ b/src/r_data.c
@@ -1,7 +1,7 @@
// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
-// $Id: r_data.c 125 2005-09-22 21:42:24Z fraggle $
+// $Id: r_data.c 558 2006-06-16 17:06:05Z fraggle $
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
@@ -58,7 +58,7 @@
static const char
-rcsid[] = "$Id: r_data.c 125 2005-09-22 21:42:24Z fraggle $";
+rcsid[] = "$Id: r_data.c 558 2006-06-16 17:06:05Z fraggle $";
#include "i_system.h"
#include "z_zone.h"
@@ -139,19 +139,29 @@ typedef struct
// A maptexturedef_t describes a rectangular texture,
// which is composed of one or more mappatch_t structures
// that arrange graphic patches.
-typedef struct
+
+typedef struct texture_s texture_t;
+
+struct texture_s
{
// Keep name for switch changing, etc.
char name[8];
short width;
short height;
+
+ // Index in textures list
+
+ int index;
+
+ // Next in hash table chain
+
+ texture_t *next;
// All the patches[patchcount]
// are drawn back to front into the cached texture.
short patchcount;
texpatch_t patches[1];
-
-} texture_t;
+};
@@ -169,6 +179,7 @@ int numspritelumps;
int numtextures;
texture_t** textures;
+texture_t** textures_hashtable;
int* texturewidthmask;
@@ -432,6 +443,32 @@ R_GetColumn
}
+static void GenerateTextureHashTable(void)
+{
+ int i;
+ int key;
+
+ textures_hashtable
+ = Z_Malloc(sizeof(texture_t *) * numtextures, PU_STATIC, 0);
+
+ memset(textures_hashtable, 0, sizeof(texture_t *) * numtextures);
+
+ // Add all textures to hash table
+
+ for (i=0; i<numtextures; ++i)
+ {
+ // Store index
+
+ textures[i]->index = i;
+
+ // Hook into hash table
+
+ key = W_LumpNameHash(textures[i]->name) % numtextures;
+
+ textures[i]->next = textures_hashtable[key];
+ textures_hashtable[key] = textures[i];
+ }
+}
//
@@ -605,6 +642,8 @@ void R_InitTextures (void)
for (i=0 ; i<numtextures ; i++)
texturetranslation[i] = i;
+
+ GenerateTextureHashTable();
}
@@ -726,16 +765,25 @@ int R_FlatNumForName (char* name)
//
int R_CheckTextureNumForName (char *name)
{
- int i;
+ texture_t *texture;
+ int key;
// "NoTexture" marker.
if (name[0] == '-')
return 0;
- for (i=0 ; i<numtextures ; i++)
- if (!strncasecmp (textures[i]->name, name, 8) )
- return i;
-
+ key = W_LumpNameHash(name) % numtextures;
+
+ texture=textures_hashtable[key];
+
+ while (texture != NULL)
+ {
+ if (!strncasecmp (texture->name, name, 8) )
+ return texture->index;
+
+ texture = texture->next;
+ }
+
return -1;
}
diff --git a/src/w_wad.c b/src/w_wad.c
index 5e8816c6..87186645 100644
--- a/src/w_wad.c
+++ b/src/w_wad.c
@@ -1,7 +1,7 @@
// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
-// $Id: w_wad.c 437 2006-03-24 20:39:28Z fraggle $
+// $Id: w_wad.c 558 2006-06-16 17:06:05Z fraggle $
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
@@ -66,7 +66,7 @@
static const char
-rcsid[] = "$Id: w_wad.c 437 2006-03-24 20:39:28Z fraggle $";
+rcsid[] = "$Id: w_wad.c 558 2006-06-16 17:06:05Z fraggle $";
#include <ctype.h>
@@ -146,7 +146,7 @@ static void ExtractFileBase(char *path, char *dest)
// Can be used for any 8-character names.
// by Lee Killough
-static unsigned int W_LumpNameHash(const char *s)
+unsigned int W_LumpNameHash(const char *s)
{
unsigned int hash;
diff --git a/src/w_wad.h b/src/w_wad.h
index 659c0b40..2126ad9a 100644
--- a/src/w_wad.h
+++ b/src/w_wad.h
@@ -1,7 +1,7 @@
// Emacs style mode select -*- C++ -*-
//-----------------------------------------------------------------------------
//
-// $Id: w_wad.h 438 2006-03-24 20:40:08Z fraggle $
+// $Id: w_wad.h 558 2006-06-16 17:06:05Z fraggle $
//
// Copyright(C) 1993-1996 Id Software, Inc.
// Copyright(C) 2005 Simon Howard
@@ -92,6 +92,8 @@ void* W_CacheLumpName (char* name, int tag);
void W_GenerateHashTable(void);
+extern unsigned int W_LumpNameHash(const char *s);
+
#endif
//-----------------------------------------------------------------------------