Quake III Arena: code/bspc/tetrahedron.c File Reference

01200 {
01201     int edgenum, side;
01202 
01203     edgenum = aasworld.edgeindex[face->firstedge + index];
01204     side = edgenum < 0;
01205     VectorCopy(aasworld.vertexes[aasworld.edges[abs(edgenum)].v[side]], vertex);
01206 } //end of the function TH_AASFaceVertex

01364 {
01365     th_triangle_t *triangles, *tri, *lasttri;
01366     int cnt;
01367 
01368     if (!AAS_LoadAASFile(filename, 0, 0))
01369         Error("couldn't load %s\n", filename);
01370 
01371     //
01372     TH_InitMaxTH();
01373     //create a triangle mesh from the solid faces in the AAS file
01374     triangles = TH_AASToTriangleMesh();
01375     //
01376     cnt = 0;
01377     lasttri = NULL;
01378     for (tri = triangles; tri; tri = tri->next)
01379     {
01380         cnt++;
01381         if (tri->prev != lasttri) Log_Print("BAH\n");
01382         lasttri = tri;
01383     } //end for
01384     Log_Print("%6d triangles\n", cnt);
01385     //create a tetrahedral decomposition of the world bounded by triangles
01386     TH_TetrahedralDecomposition(triangles);
01387     //
01388     TH_FreeMaxTH();
01389 } //end of the function TH_AASToTetrahedrons

01323 {
01324     int i, j, facenum, otherareanum;
01325     aas_face_t *face;
01326     th_triangle_t *tri, *nexttri, *triangles;
01327 
01328     triangles = NULL;
01329     for (i = 1; i < aasworld.numareas; i++)
01330     {
01331         //if (!(aasworld.areasettings[i].presencetype & PRESENCE_NORMAL)) continue;
01332         for (j = 0; j < aasworld.areas[i].numfaces; j++)
01333         {
01334             facenum = abs(aasworld.faceindex[aasworld.areas[i].firstface + j]);
01335             face = &aasworld.faces[facenum];
01336             //only convert solid faces into triangles
01337             if (!(face->faceflags & FACE_SOLID))
01338             {
01339                 /*
01340                 if (face->frontarea == i) otherareanum = face->backarea;
01341                 else otherareanum = face->frontarea;
01342                 if (aasworld.areasettings[otherareanum].presencetype & PRESENCE_NORMAL) continue;
01343                 */
01344                 continue;
01345             } //end if
01346             //
01347             tri = TH_CreateAASFaceTriangles(face);
01348             for (; tri; tri = nexttri)
01349             {
01350                 nexttri = tri->next;
01351                 TH_AddTriangleToList(&triangles, tri);
01352             } //end for
01353         } //end if
01354     } //end for
01355     return triangles;
01356 } //end of the function TH_AASToTriangleMesh

00631 {
00632     int hashvalue;
00633 
00634     hashvalue = (edge->v[0] + edge->v[1]) & (EDGEHASH_SIZE-1);
00635     edge->hashnext = thworld.edgehash[hashvalue];
00636     thworld.edgehash[hashvalue] = edge;
00637 } //end of the function TH_AddEdgeToHash

00466 {
00467     th_edge_t *edge;
00468 
00469     edge = &thworld.edges[abs(edgenum)];
00470     //increase edge user count
00471     edge->usercount++;
00472     //increase vertex user count as well
00473     thworld.vertexes[edge->v[0]].usercount++;
00474     thworld.vertexes[edge->v[1]].usercount++;
00475 } //end of the function TH_AddEdgeUser

00308 {
00309     int hash;
00310 
00311     hash = (int)fabs(p->dist) / 8;
00312     hash &= (PLANEHASH_SIZE-1);
00313 
00314     p->hashnext = thworld.planehash[hash];
00315     thworld.planehash[hash] = p;
00316 } //end of the function TH_AddPlaneToHash

00707 {
00708     int hashvalue;
00709 
00710     hashvalue = (abs(tri->edges[0]) + abs(tri->edges[1]) + abs(tri->edges[2])) & (TRIANGLEHASH_SIZE-1);
00711     tri->hashnext = thworld.trianglehash[hashvalue];
00712     thworld.trianglehash[hashvalue] = tri;
00713 } //end of the function TH_AddTriangleToHash

00941 {
00942     tri->prev = NULL;
00943     tri->next = *trianglelist;
00944     if (*trianglelist) (*trianglelist)->prev = tri;
00945     *trianglelist = tri;
00946 } //end of the function TH_AddTriangleToList

00566 {
00567     int hashvalue;
00568 
00569     hashvalue = TH_HashVec(vertex->v);
00570     vertex->hashnext = thworld.vertexhash[hashvalue];
00571     thworld.vertexhash[hashvalue] = vertex;
00572 } //end of the function TH_AddVertexToHash

01214 {
01215     vec3_t t1, t2, vcross;
01216     float d;
01217     
01218     VectorSubtract(v1, v0, t1);
01219     VectorSubtract(v2, v0, t2);
01220     CrossProduct (t1, t2, vcross);
01221     d = VectorLength( vcross );
01222 
01223     // if cross product is zero point is colinear
01224     if (d < 10)
01225     {
01226         return true;
01227     } //end if
01228     return false;
01229 } //end of the function TH_Colinear

01258 {
01259     int i, first, verts[3], trinum;
01260     vec3_t p0, p1, p2, p3, p4, center;
01261     th_triangle_t *tri, *triangles;
01262 
01263     triangles = NULL;
01264     //find three points that are not colinear
01265     for (i = 0; i < face->numedges; i++)
01266     {
01267         TH_AASFaceVertex(face, (face->numedges + i-2)%face->numedges, p0);
01268         TH_AASFaceVertex(face, (face->numedges + i-1)%face->numedges, p1);
01269         TH_AASFaceVertex(face, (i  )%face->numedges, p2);
01270         if (TH_Colinear(p2, p0, p1)) continue;
01271         TH_AASFaceVertex(face, (i+1)%face->numedges, p3);
01272         TH_AASFaceVertex(face, (i+2)%face->numedges, p4);
01273         if (TH_Colinear(p2, p3, p4)) continue;
01274         break;
01275     } //end for
01276     //if there are three points that are not colinear
01277     if (i < face->numedges)
01278     {
01279         //normal triangulation
01280         first = i; //left and right most point of three non-colinear points
01281         TH_AASFaceVertex(face, first, p0);
01282         verts[0] = TH_FindOrCreateVertex(p0);
01283         for (i = 1; i < face->numedges-1; i++)
01284         {
01285             TH_AASFaceVertex(face, (first+i  )%face->numedges, p1);
01286             TH_AASFaceVertex(face, (first+i+1)%face->numedges, p2);
01287             verts[1] = TH_FindOrCreateVertex(p1);
01288             verts[2] = TH_FindOrCreateVertex(p2);
01289             trinum = TH_CreateTriangle(verts);
01290             tri = &thworld.triangles[trinum];
01291             tri->front = -1;
01292             TH_AddTriangleToList(&triangles, tri);
01293         } //end for
01294     } //end if
01295     else
01296     {
01297         //fan triangulation
01298         TH_FaceCenter(face, center);
01299         //
01300         verts[0] = TH_FindOrCreateVertex(center);
01301         for (i = 0; i < face->numedges; i++)
01302         {
01303             TH_AASFaceVertex(face, (i  )%face->numedges, p1);
01304             TH_AASFaceVertex(face, (i+1)%face->numedges, p2);
01305             if (TH_Colinear(center, p1, p2)) continue;
01306             verts[1] = TH_FindOrCreateVertex(p1);
01307             verts[2] = TH_FindOrCreateVertex(p2);
01308             trinum = TH_CreateTriangle(verts);
01309             tri = &thworld.triangles[trinum];
01310             tri->front = -1;
01311             TH_AddTriangleToList(&triangles, tri);
01312         } //end for
01313     } //end else
01314     return triangles;
01315 } //end of the function TH_CreateAASFaceTriangles

00645 {
00646     th_edge_t *edge;
00647 
00648     if (thworld.numedges == 0) thworld.numedges = 1;
00649     if (thworld.numedges >= MAX_TH_EDGES)
00650         Error("MAX_TH_EDGES");
00651     edge = &thworld.edges[thworld.numedges++];
00652     edge->v[0] = v1;
00653     edge->v[1] = v2;
00654     TH_AddEdgeToHash(edge);
00655     return thworld.numedges-1;
00656 } //end of the function TH_CreateEdge

00324 {
00325     th_plane_t *p, temp;
00326 
00327     if (VectorLength(normal) < 0.5)
00328         Error ("FloatPlane: bad normal");
00329     // create a new plane
00330     if (thworld.numplanes+2 > MAX_TH_PLANES)
00331         Error ("MAX_TH_PLANES");
00332 
00333     p = &thworld.planes[thworld.numplanes];
00334     VectorCopy (normal, p->normal);
00335     p->dist = dist;
00336     p->type = (p+1)->type = TH_PlaneTypeForNormal (p->normal);
00337     p->signbits = TH_PlaneSignBits(p->normal);
00338 
00339     VectorSubtract (vec3_origin, normal, (p+1)->normal);
00340     (p+1)->dist = -dist;
00341     (p+1)->signbits = TH_PlaneSignBits((p+1)->normal);
00342 
00343     thworld.numplanes += 2;
00344 
00345     // allways put axial planes facing positive first
00346     if (p->type < 3)
00347     {
00348         if (p->normal[0] < 0 || p->normal[1] < 0 || p->normal[2] < 0)
00349         {
00350             // flip order
00351             temp = *p;
00352             *p = *(p+1);
00353             *(p+1) = temp;
00354 
00355             TH_AddPlaneToHash(p);
00356             TH_AddPlaneToHash(p+1);
00357             return thworld.numplanes - 1;
00358         } //end if
00359     } //end if
00360 
00361     TH_AddPlaneToHash(p);
00362     TH_AddPlaneToHash(p+1);
00363     return thworld.numplanes - 2;
00364 } //end of the function TH_CreateFloatPlane

00775 {
00776     th_tetrahedron_t *tetrahedron;
00777     int i;
00778 
00779     if (thworld.numtetrahedrons == 0) thworld.numtetrahedrons = 1;
00780     if (thworld.numtetrahedrons >= MAX_TH_TETRAHEDRONS)
00781         Error("MAX_TH_TETRAHEDRONS");
00782     tetrahedron = &thworld.tetrahedrons[thworld.numtetrahedrons++];
00783     for (i = 0; i < 4; i++)
00784     {
00785         tetrahedron->triangles[i] = triangles[i];
00786         if (thworld.triangles[abs(triangles[i])].front)
00787         {
00788             thworld.triangles[abs(triangles[i])].back = thworld.numtetrahedrons-1;
00789         } //end if
00790         else
00791         {
00792             thworld.triangles[abs(triangles[i])].front = thworld.numtetrahedrons-1;
00793         } //end else
00794     } //end for
00795     tetrahedron->volume = 0;
00796     return thworld.numtetrahedrons-1;
00797 } //end of the function TH_CreateTetrahedron

00740 {
00741     th_triangle_t *tri;
00742     int i;
00743 
00744     if (thworld.numtriangles == 0) thworld.numtriangles = 1;
00745     if (thworld.numtriangles >= MAX_TH_TRIANGLES)
00746         Error("MAX_TH_TRIANGLES");
00747     tri = &thworld.triangles[thworld.numtriangles++];
00748     for (i = 0; i < 3; i++)
00749     {
00750         tri->edges[i] = TH_FindOrCreateEdge(verts[i], verts[(i+1)%3]);
00751         TH_AddEdgeUser(abs(tri->edges[i]));
00752     } //end for
00753     tri->front = 0;
00754     tri->back = 0;
00755     tri->planenum = TH_PlaneFromPoints(verts[0], verts[1], verts[2]);
00756     tri->prev = NULL;
00757     tri->next = NULL;
00758     tri->hashnext = NULL;
00759     TH_CreateTrianglePlanes(verts, &thworld.planes[tri->planenum], tri->planes);
00760     TH_AddTriangleToHash(tri);
00761     ClearBounds(tri->mins, tri->maxs);
00762     for (i = 0; i < 3; i++)
00763     {
00764         AddPointToBounds(thworld.vertexes[verts[i]].v, tri->mins, tri->maxs);
00765     } //end for
00766     return thworld.numtriangles-1;
00767 } //end of the function TH_CreateTriangle

00721 {
00722     int i;
00723     vec3_t dir;
00724 
00725     for (i = 0; i < 3; i++)
00726     {
00727         VectorSubtract(thworld.vertexes[verts[(i+1)%3]].v, thworld.vertexes[verts[i]].v, dir);
00728         CrossProduct(dir, triplane->normal, planes[i].normal);
00729         VectorNormalize(planes[i].normal);
00730         planes[i].dist = DotProduct(thworld.vertexes[verts[i]].v, planes[i].normal);
00731     } //end for
00732 } //end of the function TH_CreateTrianglePlanes

00580 {
00581     if (thworld.numvertexes == 0) thworld.numvertexes = 1;
00582     if (thworld.numvertexes >= MAX_TH_VERTEXES)
00583         Error("MAX_TH_VERTEXES");
00584     VectorCopy(v, thworld.vertexes[thworld.numvertexes].v);
00585     thworld.vertexes[thworld.numvertexes].usercount = 0;
00586     TH_AddVertexToHash(&thworld.vertexes[thworld.numvertexes]);
00587     thworld.numvertexes++;
00588     return


Data Structures
struct	th_edge_s
struct	th_plane_s
struct	th_s
struct	th_tetrahedron_s
struct	th_triangle_s
struct	th_vertex_s
Defines
#define	DIST_EPSILON 0.1
#define	EDGEHASH_SIZE 1024
#define	INTEGRAL_EPSILON 0.01
#define	MAX_TH_EDGES 512000
#define	MAX_TH_PLANES 128000
#define	MAX_TH_TETRAHEDRONS 12800
#define	MAX_TH_TRIANGLES 51200
#define	MAX_TH_VERTEXES 128000
#define	NORMAL_EPSILON 0.0001
#define	PLANEHASH_SIZE 1024
#define	Sign(x) (x < 0 ? 1 : 0)
#define	TRIANGLEHASH_SIZE 1024
#define	VERTEX_EPSILON 0.01
#define	VERTEXHASH_SHIFT 7
#define	VERTEXHASH_SIZE ((MAX_MAP_BOUNDS>>(VERTEXHASH_SHIFT-1))+1)
Typedefs
typedef th_edge_s	th_edge_t
typedef th_plane_s	th_plane_t
typedef th_s	th_t
typedef th_tetrahedron_s	th_tetrahedron_t
typedef th_triangle_s	th_triangle_t
typedef th_vertex_s	th_vertex_t
Functions
void	TH_AASFaceVertex (aas_face_t *face, int index, vec3_t vertex)
void	TH_AASToTetrahedrons (char *filename)
th_triangle_t *	TH_AASToTriangleMesh (void)
void	TH_AddEdgeToHash (th_edge_t *edge)
void	TH_AddEdgeUser (int edgenum)
void	TH_AddPlaneToHash (th_plane_t *p)
void	TH_AddTriangleToHash (th_triangle_t *tri)
void	TH_AddTriangleToList (th_triangle_t *trianglelist, th_triangle_t tri)
void	TH_AddVertexToHash (th_vertex_t *vertex)
int	TH_Colinear (float v0, float v1, float *v2)
th_triangle_t *	TH_CreateAASFaceTriangles (aas_face_t *face)
int	TH_CreateEdge (int v1, int v2)
int	TH_CreateFloatPlane (vec3_t normal, vec_t dist)
int	TH_CreateTetrahedron (int triangles[4])
int	TH_CreateTriangle (int verts[3])
void	TH_CreateTrianglePlanes (int verts[3], th_plane_t triplane, th_plane_t planes)
int	TH_CreateVertex (vec3_t v)
void	TH_FaceCenter (aas_face_t *face, vec3_t center)
int	TH_FindEdge (int v1, int v2)
int	TH_FindFloatPlane (vec3_t normal, vec_t dist)
int	TH_FindOrCreateEdge (int v1, int v2)
int	TH_FindOrCreateVertex (vec3_t v)
int	TH_FindTetrahedron1 (th_triangle_t tri, int triangles)
int	TH_FindTetrahedron2 (th_triangle_t tri, int triangles)
int	TH_FindTriangle (int verts[3])
int	TH_FindVertex (vec3_t v)
void	TH_FreeMaxTH (void)
void	TH_FreeTriangleEdges (th_triangle_t *tri)
unsigned	TH_HashVec (vec3_t vec)
void	TH_InitMaxTH (void)
int	TH_IntersectTrianglePlanes (int v1, int v2, th_plane_t triplane, th_plane_t planes)
int	TH_OutsideBoundingBox (int v1, int v2, vec3_t mins, vec3_t maxs)
qboolean	TH_PlaneEqual (th_plane_t *p, vec3_t normal, vec_t dist)
int	TH_PlaneFromPoints (int v1, int v2, int v3)
int	TH_PlaneSignBits (vec3_t normal)
int	TH_PlaneTypeForNormal (vec3_t normal)
void	TH_RemoveEdgeUser (int edgenum)
void	TH_RemoveTriangleFromList (th_triangle_t *trianglelist, th_triangle_t tri)
void	TH_SnapPlane (vec3_t normal, vec_t *dist)
void	TH_SnapVector (vec3_t normal)
void	TH_TetrahedralDecomposition (th_triangle_t *triangles)
float	TH_TetrahedronVolume (th_tetrahedron_t *tetrahedron)
float	TH_TriangleArea (th_triangle_t *tri)
int	TH_TryEdge (int v1, int v2)
int	TH_TryTriangle (int verts[3])
Variables
th_t	thworld

tetrahedron.c File Reference

Data Structures

Defines

Typedefs

Functions

Variables

Define Documentation

Typedef Documentation

Function Documentation