X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=svbsp.c;h=ca6a1cf4dc47e606d572a0c66b51d82871ead170;hb=1419b39a89159cc708cb40a89e494f22c0a50834;hp=ad3fa38baba820011691de57ecc95ecf669980af;hpb=10523a94c80615aeccfa84c81bbffe11335ca4a7;p=xonotic%2Fdarkplaces.git

diff --git a/svbsp.c b/svbsp.c
index ad3fa38b..ca6a1cf4 100644
--- a/svbsp.c
+++ b/svbsp.c
@@ -2,19 +2,34 @@
 // Shadow Volume BSP code written by Forest "LordHavoc" Hale on 2003-11-06 and placed into public domain.
 // Modified by LordHavoc (to make it work and other nice things like that) on 2007-01-24 and 2007-01-25
 
-#ifdef USEMALLOC
-#include "string.h"
-#define Mem_Alloc(p,s) malloc(s)
-#define Mem_Free free
-#else
-#include "quakedef.h"
-#endif
-#include "polygon.h"
+#include <math.h>
+#include <string.h>
 #include "svbsp.h"
+#include "polygon.h"
 
 #define MAX_SVBSP_POLYGONPOINTS 64
 #define SVBSP_CLIP_EPSILON (1.0 / 1024.0)
 
+#define SVBSP_DotProduct(a,b) ((a)[0]*(b)[0]+(a)[1]*(b)[1]+(a)[2]*(b)[2])
+
+static void SVBSP_PlaneFromPoints(double *plane4f, const double *p1, const double *p2, const double *p3)
+{
+	double ilength;
+	// calculate unnormalized plane
+	plane4f[0] = (p1[1] - p2[1]) * (p3[2] - p2[2]) - (p1[2] - p2[2]) * (p3[1] - p2[1]);
+	plane4f[1] = (p1[2] - p2[2]) * (p3[0] - p2[0]) - (p1[0] - p2[0]) * (p3[2] - p2[2]);
+	plane4f[2] = (p1[0] - p2[0]) * (p3[1] - p2[1]) - (p1[1] - p2[1]) * (p3[0] - p2[0]);
+	plane4f[3] = SVBSP_DotProduct(plane4f, p1);
+	// normalize the plane normal and adjust distance accordingly
+	ilength = sqrt(SVBSP_DotProduct(plane4f, plane4f));
+	if (ilength)
+		ilength = 1.0 / ilength;
+	plane4f[0] *= ilength;
+	plane4f[1] *= ilength;
+	plane4f[2] *= ilength;
+	plane4f[3] *= ilength;
+}
+
 void SVBSP_Init(svbsp_t *b, const double *origin, int maxnodes, svbsp_node_t *nodes)
 {
 	memset(b, 0, sizeof(*b));
@@ -105,24 +120,24 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
 	basenum = b->numnodes;
 	for (i = 0, p = numpoints - 1;i < numpoints;p = i, i++)
 	{
+#if 1
 		// see if a parent plane describes this side
 		for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
 		{
-			svbsp_node_t *parentnode = b->nodes + j;
-			if (fabs(DotProduct(b->origin     , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
-			 && fabs(DotProduct(points + p * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
-			 && fabs(DotProduct(points + i * 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
+			double *parentnodeplane = b->nodes[j].plane;
+			if (fabs(SVBSP_DotProduct(b->origin     , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+			 && fabs(SVBSP_DotProduct(points + p * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+			 && fabs(SVBSP_DotProduct(points + i * 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
 				break;
 		}
 		if (j >= 0)
 			continue; // already have a matching parent plane
+#endif
 
 		// create a side plane
 		// anything infront of this is not inside the shadow volume
 		node = b->nodes + b->numnodes++;
-		TriangleNormal(b->origin, points + p * 3, points + i * 3, node->plane);
-		VectorNormalize(node->plane);
-		node->plane[3] = DotProduct(node->plane, b->origin);
+		SVBSP_PlaneFromPoints(node->plane, b->origin, points + p * 3, points + i * 3);
 		// we need to flip the plane if it puts any part of the polygon on the
 		// wrong side
 		// (in this way this code treats all polygons as double sided)
@@ -134,7 +149,7 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
 		// sufficient)
 		for (j = 0;j < numpoints;j++)
 		{
-			double d = DotProduct(points + j * 3, node->plane) - node->plane[3];
+			double d = SVBSP_DotProduct(points + j * 3, node->plane) - node->plane[3];
 			if (d < -SVBSP_CLIP_EPSILON)
 				break;
 			if (d > SVBSP_CLIP_EPSILON)
@@ -155,26 +170,26 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
 		parentnodenumpointer = &node->children[1];
 	}
 
+#if 1
 	// see if a parent plane describes the face plane
 	for (j = parentnodenum;j >= 0;j = b->nodes[j].parent)
 	{
-		svbsp_node_t *parentnode = b->nodes + j;
-		if (fabs(DotProduct(points    , parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
-		 && fabs(DotProduct(points + 3, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON
-		 && fabs(DotProduct(points + 6, parentnode->plane) - parentnode->plane[3]) < SVBSP_CLIP_EPSILON)
+		double *parentnodeplane = b->nodes[j].plane;
+		if (fabs(SVBSP_DotProduct(points    , parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+		 && fabs(SVBSP_DotProduct(points + 3, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON
+		 && fabs(SVBSP_DotProduct(points + 6, parentnodeplane) - parentnodeplane[3]) < SVBSP_CLIP_EPSILON)
 			break;
 	}
 	if (j < 0)
+#endif
 	{
 		// add the face-plane node
 		// infront is empty, behind is shadow
 		node = b->nodes + b->numnodes++;
-		TriangleNormal(points, points + 3, points + 6, node->plane);
-		VectorNormalize(node->plane);
-		node->plane[3] = DotProduct(node->plane, points);
+		SVBSP_PlaneFromPoints(node->plane, points, points + 3, points + 6);
 		// this is a flip check similar to the one above
 		// this one checks if the plane faces the origin, if not, flip it
-		if (DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
+		if (SVBSP_DotProduct(b->origin, node->plane) - node->plane[3] < -SVBSP_CLIP_EPSILON)
 		{
 			node->plane[0] *= -1;
 			node->plane[1] *= -1;
@@ -185,7 +200,7 @@ static void SVBSP_InsertOccluderPolygonNodes(svbsp_t *b, int *parentnodenumpoint
 		node->children[0] = -1; // empty
 		node->children[1] = -2; // shadow
 		// link this child into the tree
-		// (with the addition of this node, queries will now culled by it)
+		// (with the addition of this node, queries will now be culled by it)
 		*parentnodenumpointer = (int)(node - b->nodes);
 	}
 }
@@ -204,9 +219,9 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
 		svbsp_node_t *node = b->nodes + *parentnodenumpointer;
 		parentnodenum = *parentnodenumpointer;
 #if 1
-		if (DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
+		if (SVBSP_DotProduct(points, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON)
 		{
-			for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
+			for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) >= node->plane[3] + SVBSP_CLIP_EPSILON;i++);
 			if (i == numpoints)
 			{
 				// no need to split, just go to one side
@@ -214,9 +229,9 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
 				continue;
 			}
 		}
-		else if (DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
+		else if (SVBSP_DotProduct(points, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON)
 		{
-			for (i = 1;i < numpoints && DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
+			for (i = 1;i < numpoints && SVBSP_DotProduct(points + i * 3, node->plane) <= node->plane[3] - SVBSP_CLIP_EPSILON;i++);
 			if (i == numpoints)
 			{
 				// no need to split, just go to one side
@@ -248,9 +263,9 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
 		for (i = 0;i < numpoints-2;i++)
 		{
 			Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
-			Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 1, 0, 0, 0.25);
-			Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 1, 0, 0, 0.25);
-			Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 1, 0, 0, 0.25);
+			Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0.25, 0, 0, 1);
+			Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0.25, 0, 0, 1);
+			Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0.25, 0, 0, 1);
 			Debug_PolygonEnd();
 		}
 #endif
@@ -276,9 +291,9 @@ static int SVBSP_AddPolygonNode(svbsp_t *b, int *parentnodenumpointer, int paren
 		for (i = 0;i < numpoints-2;i++)
 		{
 			Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
-			Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 1, 0.25);
-			Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 1, 0.25);
-			Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 1, 0.25);
+			Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0, 0.25, 1);
+			Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0, 0.25, 1);
+			Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0, 0.25, 1);
 			Debug_PolygonEnd();
 		}
 #endif
@@ -294,12 +309,13 @@ int SVBSP_AddPolygon(svbsp_t *b, int numpoints, const double *points, int insert
 	if (numpoints < 3)
 		return 0;
 #if 0
+//if (insertoccluder)
 	for (i = 0;i < numpoints-2;i++)
 	{
 		Debug_PolygonBegin(NULL, DRAWFLAG_ADDITIVE, false, 0);
-		Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 1, 0, 0.25);
-		Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 1, 0, 0.25);
-		Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 1, 0, 0.25);
+		Debug_PolygonVertex(points[0], points[1], points[2], 0, 0, 0, 0.25, 0, 1);
+		Debug_PolygonVertex(points[0 + (i + 1) * 3], points[1 + (i + 1) * 3], points[2 + (i + 1) * 3], 0, 0, 0, 0.25, 0, 1);
+		Debug_PolygonVertex(points[0 + (i + 2) * 3], points[1 + (i + 2) * 3], points[2 + (i + 2) * 3], 0, 0, 0, 0.25, 0, 1);
 		Debug_PolygonEnd();
 	}
 #endif