Hi everyone,

currently I'm pretty desperate in figuring out how to translate planes from map files (quake/half-life) into (indexed) triangles.

Most of the information about map files I got from Valve Developer Community [1]. I'm also aware of Stefan Hajnoczi's documentation [2], but it is not well written enough for me to understand. I have freshen up my linear algebra knowledge about planes from Points, lines, and planes [3] and Wikipedia [4] and I got a pretty good understanding about how to transform three points into a plane, to get 

Ax + By + Cz + D = 0

where (A B C) is the vector normal of the plane and D is the distance from the origin. I also know how to calculate the intersection of two / three planes. I used a similar code like Stefan to achieve this.

bool Plane::GetIntersection(const Plane& a, const Plane&b, glm::vec3& out_Vector)
{
	float d = glm::dot(m_vNormal, glm::cross(a.GetNormal(), b.GetNormal()));

	if (std::fabs(d) < cEpsilon) return false;

	out_Vector =
		(
			(glm::cross(a.GetNormal(), b.GetNormal()) * -m_fDistance) -
			(glm::cross(b.GetNormal(), m_vNormal) * a.GetDistance()) -
			(glm::cross(m_vNormal, a.GetNormal()) * b.GetDistance())
		) / d;
	return true;
}

The thing with Stefan's code is, that I am trying to achieve a different approach not by using linked lists (that's what he's using). I want to solve this problem in my coding convention and fully understand the mathematical problem in order to implement it correctly (and be able to modify/optimize it).

I thought of a similar procedure as it says on Valve's documentation (see figure [5]).

What am I missing in order to build the cube? What are the single steps to achieve this?

I think I only need a little poke to get me in the right direction. Any further sources are greatly appreciated. I looked up source code from e.g. Trenchbroom and other projects on github, but I just want a simple solution to get more into detail like texture mapping etc.

Best regards,
Daniel

References
[1] https://developer.valvesoftware.com/wiki/Valve_Map_Format
[2] https://github.com/stefanha/map-files
[3] http://paulbourke.net/geometry/pointlineplane/
[4] https://en.wikipedia.org/wiki/Plane_(geometry)
[5] https://developer.valvesoftware.com/w/images/0/0d/Brush_planes.gif

Use a hash-based lookup table to identify previously created vertices matching on all attributes of the vertex:  Position, normal, texcoord (and its implied texture!), and optionally color.  e.g.:

class MeshBuilder:
    def __init__(self):
        self.index_buffer = []
        self.vertex_buffer = []
        self.vertex_lookup = {}


    def index_for_vertex(self, x, y, z, nx, ny, texid, tx, ty):
        vertex = x, y, z, nx, ny, texid, tx, ty

        ix = self.vertex_lookup.get(vertex, None)
        if ix is None:
            ix = len(self.vertex_buffer)
            self.vertex_buffer.append(vertex)
            self.vertex_lookup[vertex] = ix

        return ix


    def add_triangle(self, a, b, c):
        ix_a = self.index_for_vertex(*a)
        ix_b = self.index_for_vertex(*b)
        ix_c = self.index_for_vertex(*c)

        self.index_buffer += [ix_a, ix_b, ix_c]

Afterward, use the lookup table to get or create a vertex index to use in your index buffer.

In the cube example, the 6 planes will build 6 faces (polygons). Triangulating the polygons will make 12 triangles and 36 vertices.  The `MeshBuilder` example will reuse indices for the 12 duplicate vertices.  The end result is a vertex buffer with 24 unique vertices, and a index buffer with 36 indices.

This could help a bit, it doesnt load every map file but somehow i managed to load few basic maps with it

inline void LoadStdGTKRadiantMapFile(AnsiString fname, TachoGLModel<float> * output_model_tree, int & len)
{
	TStringList * s = new TStringList();
	s->LoadFromFile(fname);
	ALOG("loaded file: "+fname+" lines: "+IntToStr(s->Count));

	//begin with counting worlspawns or func_groups //since we treat them as worldspawn too
	bool inEntity = false;
	bool inBrush  = false;

	//First: count brushes in entities and func_groups so we can size output_model_tree, int & len

	int EntityLen = 0;
	int BracketDepth = 0;
	for (int i=0; i < s->Count; i++)
	{
	AnsiString line = LowerCase(s->Strings[i]);
if (  (Pos("classname", line) > 0 ) &&
	((Pos("worldspawn", line) > 0 ) || (Pos("func_group", line) > 0 )) )
{
	BracketDepth = 0;
	ALOG("FOUND WORLDSPAWN OR FUNC_GROUP at line: "+IntToStr(i));
	for (int j=i+1; j < s->Count; j++)
	{
	line = LowerCase(s->Strings[j]);
//	ALOG("j = "+IntToStr(j) +" line: "+line);
	if (Pos("{", line) > 0 )
	{

		BracketDepth = BracketDepth + 1;
		ALOG("FOUND Bracket: depth: "+IntToStr(BracketDepth));
		if (BracketDepth > 0){ 	ALOG("FOUND BRUSH");EntityLen = EntityLen + 1; }
	}


	if (Pos("}", line) > 0 )
	{
		BracketDepth = BracketDepth - 1;
		ALOG("Closing brush: bracket depth: "+IntToStr(BracketDepth));
	}

	if (BracketDepth < 0) {ALOG("Entity closed"); i = j + 1; break; }
	}
}

	}

if (EntityLen == 0) { delete s; return; }
	output_model_tree = new TachoGLModel<float>[EntityLen];
	len = EntityLen;
int EntityIndex = -1;

/*
 * Through all lines in file check if we found { sign and are not in brush
 */


for (int i=0; i < s->Count; i++)
{
AnsiString line = LowerCase(s->Strings[i]);
if ( (Pos("classname", line) > 0 ) &&
((Pos("worldspawn", line) > 0 ) || (Pos("func_group", line) > 0 )) )
{
	BracketDepth = 0;

for (int j=i+1; j < s->Count; j++) //to zakonczyc i = j+1;
{

bool found_brush = false;
line = LowerCase(s->Strings[j]);
if (Pos("{", line) > 0 )
{
	BracketDepth = BracketDepth + 1;
	found_brush = true;
	if (BracketDepth > 0) EntityIndex = EntityIndex + 1;
}


if (Pos("}", line) > 0 )
	BracketDepth = BracketDepth - 1;

if (BracketDepth < 0) continue;

if (Pos("{", line) > 0) continue;
if (Pos("(", line) <= 0) continue;

//we are definetly at (

inBrush = true;
//finally we have our polygon definition ffs

int NumOfFaces = 0;
TPlane<float> * Faces;
TPolygon<float> * Polys;

//count how many faces object has/consists
for (int p=j; p < s->Count; p++)
{
AnsiString str2 = s->Strings[p];
if (Pos("}", str2) > 0) break;
if (Pos("(", str2) > 0) NumOfFaces = NumOfFaces + 1;
}
ALOG("OBJECT CONSISTS OF: "+IntToStr(NumOfFaces));
Faces = new TPlane<float>[ NumOfFaces ];
Polys = new TPolygon<float>[ NumOfFaces ];


int FaceIndex = -1;
for (int p=j; p < s->Count; p++)
{
AnsiString str2 = s->Strings[p];
if (Pos("}", str2) > 0) break;

FaceIndex = FaceIndex + 1;
	/*
	 * 		Receive data from 3 ( x, y, z )
	 */
	vec3 points[3];
	AnsiString	VertexStr = get_text_between2("(", ")", str2);
	for (int iterations=0; iterations < 3; iterations++)
	{

get_all_in_nawias(VertexStr, " ", 0);
points[iterations].x = (float)pstrtoint(w_nawiasie[0][0]);
points[iterations].y = (float)pstrtoint(w_nawiasie[0][1]);
points[iterations].z = (float)pstrtoint(w_nawiasie[0][2]);


// Swap the y and z values, and negate the new z so Y points up.
float tmp 			 =  points[iterations].y;
points[iterations].y =  points[iterations].z;
points[iterations].z = -tmp;

//Reminder: Ax+By+Cz+D=0    => D = -(Ax+By+Cz)  => D = -Ax-By-Cz

	}
	/*
	 * ===============================================================================================
	 * //eof retreiving data from (x y z) (x y z) (x y z) uselesss/text we now have plane definition [3] points
	 */

	Faces[FaceIndex].calc_plane(points[0], points[1], points[2], false);
}


TPolygon<float> output_polygon;
std::vector<TPolygon<float> > OutputModel;
//Test each face against another face then find intersection
	for (int n1=0; n1 < NumOfFaces; n1++)
	{
		for (int n2=0; n2 < NumOfFaces; n2++)
			for (int n3=0; n3 < NumOfFaces; n3++)
				if ( (n1 != n2) && (n1 != n3) && (n2 != n3) )
	{

bool		illegal = false;
vec3 		vertex_result;
bool		newVertex = Get3PlaneIntersection(Faces[n1].n, Faces[n2].n, Faces[n3].n, Faces[n1].D, Faces[n2].D, Faces[n3].D, vertex_result);
if (newVertex)
for (int n4=0; n4 < NumOfFaces; n4++)
		if (Faces[n4].ClassifyPoint(vertex_result) == isFront)	illegal = true;

if (!illegal) output_polygon.AddVertex( vertex_result );
	}

		OutputModel.push_back(output_polygon);
	}

int model_vlen = 0;
int model_flen = OutputModel.size();
for (int p1=0; p1 < model_flen; p1++)
	model_vlen = model_vlen + OutputModel[p1].Count;

for (int p1=0; p1 < model_flen; p1++)
	OutputModel[p1].CalcPlane();


	output_model_tree[ EntityIndex ].header.LENGTH = model_vlen;
	output_model_tree[ EntityIndex ].AOS 		= new TTGLVertex<float,float,float>[model_vlen];
	output_model_tree[ EntityIndex ].FaceLength = model_flen;
	output_model_tree[ EntityIndex ].Matrixarr 	= new tmatrixtype[model_flen];
	output_model_tree[ EntityIndex ].VBO_BE	 	= new tvbofacenfo[model_flen];
	output_model_tree[ EntityIndex ].Textureindex = new int[model_flen];
	for (int fa=0; fa < model_flen; fa++)
	{
			output_model_tree[ EntityIndex ].Matrixarr[fa] 		= mtTriangleFan;
			output_model_tree[ EntityIndex ].Textureindex[fa] 	= 0;
	}



int findex = -1;
int vindex = 0;
		for (int p1=0; p1 < model_flen; p1++)
		{
			findex = findex + 1;
			output_model_tree[ EntityIndex ].VBO_BE[findex].INDEX_START = vindex;
		for (int p2=0; p2 < OutputModel[p1].Count; p2++)
		{
			output_model_tree[ EntityIndex ].AOS[vindex].v = OutputModel[p1].V[p2];
			output_model_tree[ EntityIndex ].AOS[vindex].n = OutputModel[p1].normal;
			vindex = vindex + 1;
		}
		}




		i = j + 1; //skip to next line
		if (i >= s->Count) {delete s; return;}//reached end of file way ago
}//eof for j
}//eof if classname worldspawn of func_group

}//eof for i
delete s;
} //end of function

template <class T> bool Get3PlaneIntersection(t3dpoint<T> n1, t3dpoint<T> n2, t3dpoint<T> n3,
		T d1, T d2, T d3, t3dpoint<T> &p , T &den)
{

double denom = Dot(n1, vectorcross(n2, n3) );
den = T(denom);
if (betweenorequal(-epsilona,epsilona, denom)) return false; //check if denominator is equal or close to 0
t3dpoint<T> tmp = vectorcross(n2, n3) * -d1;
t3dpoint<T> tmp2 = vectorcross(n3, n1) * -d2;
t3dpoint<T> tmp3 = vectorcross(n1, n2) * -d3;
p = (tmp+tmp2+tmp3) / denom;
return true;
}

get_all_in_nawias is a function that separates a string given a key

Means: if we have a string "88, 66, 33"

And call that func with key ","

It will return a std::vector<std::string> with values

88

66

33

Lol just found that i nowhere store how many vertices each face has, and even with this it loaded data normally... Maybe i was setting it earlier but cant remember its an old code btw

1 hour ago, fastcall22 said:

...

In the cube example, the 6 planes will build 6 faces (polygons). Triangulating the polygons will make 12 triangles and 36 vertices.  The `MeshBuilder` example will reuse indices for the 12 duplicate vertices.  The end result is a vertex buffer with 24 unique vertices, and a index buffer with 36 indices.

Of course hash map is the answer to almost every problem : ) I will keep that in mind when I got the plane to vertex thing right.

@KKTHXBYE 80% of your code doesn't really relate to my problem. I don't have any problems parsing the map file. My Problem is to get my mind wrapped around the plane to vertex vertices conversion. Just like I mentioned in my post (have a look at the animation). But I will get a closer look at your code when you actually 

//Test each face against another face then find intersection

To be clear, I would like to have a more mathematically/algorithmically explanation to fully understand the problem instead of just let you guys write the code for me

It's been a while since I've done something like this, but I'll offer a few thoughts in addition to what's already been said. I'll assume you're interested in arbitrary convex brushes and not just rectangular prisms.

I've seen a few different methods suggested for this. One is to create a sufficiently large initial polygon lying in each plane in the set, and then clip that polygon to every other plane in the set. Note that vertex positions that should be coincident may differ slightly due to numerical error, so welding may be required. There's some discussion about this here:

https://www.reddit.com/r/gamedev/comments/4vjg1i/valve_map_file_vmf_need_help_on_finding_out_how/

Which links to this, which looks like it might have some useful information:

http://mattn.ufoai.org/files/MAPFiles.pdf

There are other methods as well that involve intersecting the planes in groups of three (as you seem to be doing). For each such intersection that succeeds, the intersection point is part of the brush if it lies on or in front of every plane in the set (using a numerical threshold of course).

I looked at one of the references you linked to, and it looks like each intersection point is added to a polygon corresponding to each of the three planes involved in the intersection. I only took a quick look, so I'm not sure how welding or polygon vertex order is handled in that reference. (There are ways to put unordered polygon vertices in the right order though.)

Another method is to find all the valid intersection points and then compute a convex hull from those points.

I think any general method will probably be subject to numerical error, so that has to be kept in mind.

Your question then is only about the math behind finding the point of intersection of three planes?

The standard form, Ax + By + Cz + D = 0, can also be written as a dot product, `(A,B,C,D) · (x,y,z,1) = 0`, and both can be written as matrix multiplication: `[[A B C D]] * [[x] [y] [z] [1]] = [[0]]`.  For all planes, `(A,B,C,D) · (x,y,z,1)` must be 0, if written as a matrix, we get:

                    [[x]
[[A1 B1 C1 D1]       [y]       [[0]
 [A2 B2 C2 D2]   ×   [z]    =   [0]
 [A3 B3 C3 D3]]      [1]]       [0]]

Expanded:

[[A1x + B1y + C1z + D1]    [[0]
 [A2x + B2y + C2z + D2]  =  [0]
 [A3x + B3y + C3z + D3]]    [0]]

Afterwards, we can solve using systems of linear equations, specifically using Kramer's Rule or row reduction:

[[q*A1x +     0 +     0]    [[-D1]
 [    0 + r*B2y +     0]  =  [-D2]
 [    0 +     0 + s*C3z]]    [-D3]]

Which more or less gives us something like the following:

[[x]    [[-D1/(q*A1)]
 [y]  =  [-D2/(r*B2)]
 [z]]    [-D3/(s*C3)]]

Regarding how to visualize the math behind it, I recommend watching 3Blue1Brown's series on linear algebra.

If you just read the code, there it is, but you know better what code does, without reading it?

48 minutes ago, KKTHXBYE said:

If you just read the code, there it is, but you know better what code does, without reading it?

Oh, sorry. I didn't want to be rude.
No, just like I said there are still 20% which tackle the problem.

@Zakwayda you've made some good points mentioning the error. I didn't had that in mind. I stumbled upon this reddit post as well, but it was very early in my developing stages.

@fastcall22 thanks for the explanation. I will get more into the math regarding the links you've posted. Actually linear algebra isn't the problem  but 3Blue1Brown is still a pretty good youtube channel. Watched all of his DL videos [/offtopic]