# How VMF Stores Solids

I’ve been working on a program that derives brushes from VMF files, and in order to avoid having to find this information yourself, I decided to put it all together. Bear with me if any of this information is incorrect as I still haven’t finished my program yet.
Now you’d think the brushes would be stored as the vertices for each face, but they actually aren’t. Instead, Valve decided to store the faces as infinite planes derived from 3 selected vertices on each face.
Here’s the algorithm I have thought up that determines the vertices of each face. All the in between math is done by normals, which must be computed in the correct order, cross products, and solving sets of equations with two variables.

I dont know how much I can help you out with this, or find a use for it myself, but I did notice that you said concave faces, and surely you mean convex faces?

This wasn’t really for help. More just as a resource, and yea I meant convex, not concave. I haven’t brushed up on my geometry in some time but I’m figuring it out.
I actually wrote all this up really quick just to show it to a friend, and since I already had it, I thought I might as well post it here.

Care to post the code you’re using to get from “plane” “(x[SUB]1[/SUB] y[SUB]1[/SUB] z[SUB]1[/SUB]) (x[SUB]2[/SUB] y[SUB]2[/SUB] z[SUB]2[/SUB]) (x[SUB]3[/SUB] y[SUB]3[/SUB] z[SUB]3[/SUB])” to a table / two-dimensional array of all the vertex coordinates for the solid?

Still working on it I’m afraid.

Alright then, I’ll be following this thread.

Not to steal your thunder, but I’ve solved this problem a few months ago. Have some poorly documented code.

``````

glm::vec3 VMF::normalFromPoints( const glm::vec3 &p1 , const glm::vec3 &p2 , const glm::vec3 &p3 )
{
return glm::normalize( glm::cross( p2 - p1 , p3 - p1 ) );
}

bool VMF::intersectionOfBundle( glm::vec3 &point , const glm::vec3 &p1p1 , const glm::vec3 &p1p2 , const glm::vec3 &p1p3 , const glm::vec3 &p2p1 , const glm::vec3 &p2p2 , const glm::vec3 &p2p3 , const glm::vec3 &p3p1 , const glm::vec3 &p3p2 , const glm::vec3 &p3p3 )
{
glm::vec3 normals[ 3 ];
normals[ 0 ] = normalFromPoints( p1p1 , p1p2 , p1p3 );
normals[ 1 ] = normalFromPoints( p2p1 , p2p2 , p2p3 );
normals[ 2 ] = normalFromPoints( p3p1 , p3p2 , p3p3 );

glm::mat3x3 normalMat = glm::mat3x3( normals[ 0 ] , normals[ 1 ] , normals[ 2 ] );
float determinant = glm::determinant( normalMat );

if( determinant )
{
point = ( glm::dot( p1p1 , normals[ 0 ] ) * glm::cross( normals[ 1 ] , normals[ 2 ] ) + glm::dot( p2p1 , normals[ 1 ] ) * glm::cross( normals[ 2 ] , normals[ 0 ] ) + glm::dot( p3p1 , normals[ 2 ] ) * glm::cross( normals[ 0 ] , normals[ 1 ] ) );
point *= ( 1.0 / determinant ); // Single call doesn't work

return true;
}

return false;
}

bool VMF::pointAbovePlane( const glm::vec3 &point , const glm::vec3 &normal , const glm::vec3 &pointOnPlane )
{
return 0.5 < glm::dot( normal , point - pointOnPlane );
//return 0.0 < glm::dot( normal , point - pointOnPlane );
}

QVector< glm::vec2 > VMF::sortPoints2DCounterClockwise( const QVector< glm::vec2 > points , const glm::vec2 origin )
{
QVector< glm::vec2 > sortedPoints;
QVector< CKeyvalue< float , glm::vec2 > > positivePoints , negativePoints;
sortedPoints.reserve( points.size() );

glm::vec2 tempPoint;

for( int index = 0 ; index < points.size() ; index++ )
{
tempPoint = points[ index ] - origin;

if( tempPoint.y > 0.0 )
positivePoints.append( CKeyvalue< float , glm::vec2 >( tempPoint.x / tempPoint.y , points.at( index ) ) );
else if( tempPoint.y < 0.0 )
negativePoints.append( CKeyvalue< float , glm::vec2 >( tempPoint.x / tempPoint.y , points.at( index ) ) );
else
{
if( tempPoint.x < 0.0 )
negativePoints.append( CKeyvalue< float , glm::vec2 >( INFINITY , points.at( index ) ) );
else
positivePoints.append( CKeyvalue< float , glm::vec2 >( INFINITY , points.at( index ) ) );
}
}

qSort( positivePoints );
qSort( negativePoints );

for( int index = positivePoints.size() - 1 ; index >= 0 ; index-- )
sortedPoints.append( positivePoints.at( index ).value );

for( int index = negativePoints.size() - 1 ; index >= 0 ; index-- )
sortedPoints.append( negativePoints.at( index ).value );

#if 0
QString data;

for( int index = 0 ; index < sortedPoints.size() ; index++ )
data.append( QString( "( %1 , %2 )" ).arg( sortedPoints.at( index ).x ).arg( sortedPoints.at( index ).y ) + "
" );

QMessageBox::information( NULL , "" , data );
#endif

return sortedPoints;
}

QVector< glm::vec3 > VMF::sortPoints3DCounterClockwise( const QVector< glm::vec3 > points , const glm::vec3 normal )
{
QVector< glm::vec3 > sortedPoints;
QVector< glm::vec2 > orientedPoints;
QVector< CKeyvalue< float , glm::vec3 > > positivePoints , negativePoints;
sortedPoints.reserve( points.size() );
orientedPoints.reserve( points.size() );

// Compute rotation

float xRot = glm::atan( normal.y , glm::sqrt( normal.z * normal.z + normal.x * normal.x ) ) , yRot = 1.5 * M_PI - glm::atan( normal.z , normal.x );
float sinA = glm::sin( xRot ) , sinB = glm::sin( yRot ) , cosA = glm::cos( xRot ) , cosB = glm::cos( yRot );

// Apply rotation

glm::vec2 origin , orientedPoint;

for( int pointIndex = 0 ; pointIndex < points.size() ; pointIndex++ )
{
origin.x += orientedPoint.x = cosB * points.at( pointIndex ).x - sinB * points.at( pointIndex ).z;
origin.y += orientedPoint.y = sinA * sinB * points.at( pointIndex ).x + cosA * points.at( pointIndex ).y + sinA * cosB * points.at( pointIndex ).z;
//orientedPoint.z = cosA * sinB * points.at( pointIndex ).x - sinA * points.at( pointIndex ).y + cosA * cosB * points.at( pointIndex ).z;

orientedPoints.append( orientedPoint );
}

origin /= (float)( orientedPoints.size() );

// Sort counter-clockwise

for( int index = 0 ; index < orientedPoints.size() ; index++ )
{
orientedPoint = orientedPoints[ index ] - origin;

if( orientedPoint.y > 0.0 )
positivePoints.append( CKeyvalue< float , glm::vec3 >( orientedPoint.x / orientedPoint.y , points.at( index ) ) );
else if( orientedPoint.y < 0.0 )
negativePoints.append( CKeyvalue< float , glm::vec3 >( orientedPoint.x / orientedPoint.y , points.at( index ) ) );
else
{
if( orientedPoint.x < 0.0 )
negativePoints.append( CKeyvalue< float , glm::vec3 >( INFINITY , points.at( index ) ) );
else
positivePoints.append( CKeyvalue< float , glm::vec3 >( INFINITY , points.at( index ) ) );
}
}

qSort( positivePoints );
qSort( negativePoints );

for( int index = positivePoints.size() - 1 ; index >= 0 ; index-- )
sortedPoints.append( positivePoints.at( index ).value );

for( int index = negativePoints.size() - 1 ; index >= 0 ; index-- )
sortedPoints.append( negativePoints.at( index ).value );

#if 0
QString data;

for( int index = 0 ; index < sortedPoints.size() ; index++ )
data.append( QString( "( %1 , %2 )" ).arg( sortedPoints.at( index ).x ).arg( sortedPoints.at( index ).y ) + "
" );

QMessageBox::information( NULL , "" , data );
#endif

return sortedPoints;
}

VGL::Brush* VMF::meshFromBrush( const CFileVMF::solid *brush )
{
if( brush )
{
//QFile raid( "raid.txt" );
//raid.open( QIODevice::WriteOnly );
//QTextStream stream( &raid );

// Collect points

QString string;
QStringList stringList;
QVector< QVector< glm::vec3 > > planePoints;
planePoints.resize( brush->sideArray.size() );

for( int index = 0 ; index < planePoints.size() ; index++ )
{
string = brush->sideArray.at( index ).plane;
string.remove( '(' );
string.remove( ')' );

//QMessageBox::information( NULL , "" , string );
stringList = string.simplified().split( ' ' , QString::SkipEmptyParts );

if( stringList.length() == 9 )
{
//QMessageBox::information( NULL , "" , QString( "(%1 %2 %3) (%4 %5 %6) (%7 %8 %9)" ).arg( stringList.at( 0 ) ).arg( stringList.at( 1 ) ).arg( stringList.at( 2 ) ).arg( stringList.at( 3 ) ).arg( stringList.at( 4 ) ).arg( stringList.at( 5 ) ).arg( stringList.at( 6 ) ).arg( stringList.at( 7 ) ).arg( stringList.at( 8 ) ) );

for( int index2 = 0 ; index2 < 9 ; index2 += 3 )
{
// Swap Y and Z
planePoints[ index ].append( glm::vec3( stringList.at( index2 ).toFloat( NULL ) , stringList.at( index2 + 2 ).toFloat( NULL ) , stringList.at( index2 + 1 ).toFloat( NULL ) ) );

// Fix inaccurate vertices

float fract = 0.0;

fract = glm::fract( glm::abs( planePoints[ index ].last().x ) );
if( fract < 0.05 )
planePoints[ index ].last().x = glm::trunc( planePoints[ index ].last().x );
else if( fract >= 0.95 )
planePoints[ index ].last().x = glm::round( planePoints[ index ].last().x );

fract = glm::fract( glm::abs( planePoints[ index ].last().y ) );
if( fract < 0.05 )
planePoints[ index ].last().y = glm::trunc( planePoints[ index ].last().y );
else if( fract >= 0.95 )
planePoints[ index ].last().y = glm::round( planePoints[ index ].last().y );

fract = glm::fract( glm::abs( planePoints[ index ].last().z ) );
if( fract < 0.05 )
planePoints[ index ].last().z = glm::trunc( planePoints[ index ].last().z );
else if( fract >= 0.95 )
planePoints[ index ].last().z = glm::round( planePoints[ index ].last().z );

//QMessageBox::information( NULL , "" , QString( "%1 , %2 , %3" ).arg( planePoints[ index ].last().x ).arg( planePoints[ index ].last().y ).arg( planePoints[ index ].last().z ) );
}
}
else
return NULL;
}

// Solve vertices

QVector< glm::vec3 > points;
QVector< QVector< glm::vec3 > > brushSideVertices;
brushSideVertices.resize( brush->sideArray.size() );

int index1 , index2 , index3;
glm::vec3 point;

for( index1 = 0 ; index1 < planePoints.size() - 2 ; index1++ )
for( index2 = index1 + 1 ; index2 < planePoints.size() - 1 ; index2++ )
for( index3 = index2 + 1 ; index3 < planePoints.size() ; index3++ )
if( VMF::intersectionOfBundle( point , planePoints[index1][0] , planePoints[index1][1] , planePoints[index1][2] , planePoints[index2][0] , planePoints[index2][1] , planePoints[index2][2] , planePoints[index3][0] , planePoints[index3][1] , planePoints[index3][2] ) )
{
// Check for duplicates

// Check everything seperately. Points may be unique to a side, but not to the complete list
int index4 = 0;
for( ; index4 < points.size() ; index4++ )
if( qFuzzyCompare( point.x , points.at( index4 ).x ) && qFuzzyCompare( point.y , points.at( index4 ).y ) && qFuzzyCompare( point.z , points.at( index4 ).z ) )
break;

if( index4 == points.size() )
points.append( point );

for( index4 = 0 ; index4 < brushSideVertices[ index1 ].size() ; index4++ )
if( qFuzzyCompare( point.x , brushSideVertices[ index1 ].at( index4 ).x ) && qFuzzyCompare( point.y , brushSideVertices[ index1 ].at( index4 ).y ) && qFuzzyCompare( point.z , brushSideVertices[ index1 ].at( index4 ).z ) )
break;

if( index4 == brushSideVertices[ index1 ].size() )
brushSideVertices[ index1 ].append( point );

for( index4 = 0 ; index4 < brushSideVertices[ index2 ].size() ; index4++ )
if( qFuzzyCompare( point.x , brushSideVertices[ index2 ].at( index4 ).x ) && qFuzzyCompare( point.y , brushSideVertices[ index2 ].at( index4 ).y ) && qFuzzyCompare( point.z , brushSideVertices[ index2 ].at( index4 ).z ) )
break;

if( index4 == brushSideVertices[ index2 ].size() )
brushSideVertices[ index2 ].append( point );

for( index4 = 0 ; index4 < brushSideVertices[ index3 ].size() ; index4++ )
if( qFuzzyCompare( point.x , brushSideVertices[ index3 ].at( index4 ).x ) && qFuzzyCompare( point.y , brushSideVertices[ index3 ].at( index4 ).y ) && qFuzzyCompare( point.z , brushSideVertices[ index3 ].at( index4 ).z ) )
break;

if( index4 == brushSideVertices[ index3 ].size() )
brushSideVertices[ index3 ].append( point );
}

//QMessageBox::information( NULL , "" , QString::number( points.size() ) );

// Filter extraneous vertices

for( int index = 0 ; index < planePoints.size() ; index++ )
for( int index2 = 0 ; index2 < points.size() ; index2++ )
if( VMF::pointAbovePlane( points.at( index2 ) , VMF::normalFromPoints( planePoints[ index ][0] , planePoints[ index ][1] , planePoints[ index ][2] ) , planePoints[ index ][0] ) )
{
for( int removeIndex = 0 , brushSideIndex = 0 ; brushSideIndex < brushSideVertices.size() ; brushSideIndex++ )
{
removeIndex = brushSideVertices[ brushSideIndex ].indexOf( points.at( index2 ) );

if( removeIndex != -1 )
brushSideVertices[ brushSideIndex ].remove( removeIndex );
}

points.remove( index2 );
index2--;
}

// Construct brush

VGL::BrushSide *mesh = NULL;
VGL::Brush *cglBrush = new VGL::Brush;

glm::vec3 brushColorVector( qrand() / (float)RAND_MAX , qrand() / (float)RAND_MAX , qrand() / (float)RAND_MAX );
brushColorVector = glm::normalize( brushColorVector );

// Construct sides

//QMessageBox::information( NULL , "" , QString::number( points.size() ) );

for( int sideIndex = 0 ; sideIndex < brushSideVertices.size() ; sideIndex++ )
{
QVector< glm::vec3 > finalPoints = sortPoints3DCounterClockwise( brushSideVertices.at( sideIndex ) , VMF::normalFromPoints( planePoints.at( sideIndex ).at( 0 ) , planePoints.at( sideIndex ).at( 2 ) , planePoints.at( sideIndex ).at( 1 ) ) );

#if 0
if( finalPoints.size() )
{
glm::vec3 otherNormal , normal = VMF::normalFromPoints( finalPoints.at( 0 ) , finalPoints.at( 1 ) , finalPoints.at( 2 ) );

for( int index = 1 ; index < finalPoints.size() - 2 ; index++ )
{
otherNormal = normalFromPoints( finalPoints.at( index ) , finalPoints.at( index + 1 ) , finalPoints.at( index + 2 ) );

if( ( M_PI / 4.0 ) < glm::acos( ( glm::dot( normal , otherNormal ) ) / ( glm::length( normal ) * glm::length( otherNormal ) ) ) )
{
QMessageBox::information( NULL , "" , QString( "Brush %1, side %2 has multiple normals!" ).arg( brush->id ).arg( brush->sideArray.at( sideIndex ).id ) );
break;
}
}
}

#endif

if( finalPoints.size() != brushSideVertices.at( sideIndex ).size() )
{
//stream.flush();
QMessageBox::information( NULL , "" , QString( "Brush %1, side %2 has %3/%4 points!" ).arg( brush->id ).arg( brush->sideArray.at( sideIndex ).id ).arg( finalPoints.size() ).arg( brushSideVertices.at( sideIndex ).size() ) );
}

// Finalize side

mesh = new VGL::BrushSide;
mesh->setPrimitive( CGL::Triangle_Fan );

mesh->setVertices( new CGL::VertexBuffer( CGL::Float , finalPoints.data() , finalPoints.size() * 3 , CGL::StaticDraw ) , 3 );
mesh->setColor( brushColorVector.x , brushColorVector.y , brushColorVector.z , 0.0 );

#if 1
if( brush->sideArray.at( sideIndex ).dispdata )
{
QByteArray start = brush->sideArray.at( sideIndex ).dispdata->startposition;
QList< QByteArray > startFloats = start.mid( 1 , start.length() - 2 ).split( ' ' );

glm::vec3 startVertex;
startVertex.x = startFloats.at( 0 ).toFloat( NULL );
startVertex.y = startFloats.at( 2 ).toFloat( NULL );
startVertex.z = startFloats.at( 1 ).toFloat( NULL );

float tempDistance = 0.0 , distance = glm::distance( startVertex , finalPoints.at( 0 ) );
glm::vec3 bottomLeftVertex = finalPoints.at( 0 );
int bottomLeftIndex = 0;

for( int index = 1 ; index < finalPoints.size() ; index++ )
{
tempDistance = glm::distance( startVertex , finalPoints.at( index ) );

if( tempDistance < distance )
{
distance = tempDistance;
bottomLeftVertex = finalPoints.at( index );
bottomLeftIndex = index;
}
}

int rowItems = ( 2 << ( (int)brush->sideArray.at( sideIndex ).dispdata->power - 1 ) ) + 1;
glm::vec3 bottomRightVertex = finalPoints.at( ( bottomLeftIndex + 1 ) % 4 );
glm::vec3 topRightVertex = finalPoints.at( ( bottomLeftIndex + 2 ) % 4 );
glm::vec3 topLeftVertex = finalPoints.at( ( bottomLeftIndex + 3 ) % 4 );

topLeftVertex = bottomLeftVertex;
bottomLeftVertex = finalPoints.at( ( bottomLeftIndex + 1 ) % 4 );
bottomRightVertex = finalPoints.at( ( bottomLeftIndex + 2 ) % 4 );
topRightVertex = finalPoints.at( ( bottomLeftIndex + 3 ) % 4 );

VGL::Displacement *displacement = mesh->displacement = new VGL::Displacement;
displacement->initializePower( (VGL::Displacement::Power_t)brush->sideArray.at( sideIndex ).dispdata->power );
displacement->vertices[ 0 ] = topLeftVertex;
displacement->vertices[ rowItems - 1 ] = topRightVertex;
displacement->vertices[ rowItems * ( rowItems - 1 ) ] = bottomLeftVertex;
displacement->vertices[ ( rowItems * rowItems ) - 1 ] = bottomRightVertex;

// Compute left edge vertices
glm::vec3 lineDelta = ( topLeftVertex - bottomLeftVertex ) / (float)( rowItems - 1 );

for( int index = 1 ; index < rowItems ; index++ )
displacement->vertices[ index * rowItems ] = displacement->vertices[ ( index - 1 ) * rowItems ] - lineDelta;

// Compute right edge vertices
lineDelta = ( topRightVertex - bottomRightVertex ) / (float)( rowItems - 1 );

for( int index = 1 ; index < rowItems ; index++ )
displacement->vertices[ ( index * rowItems ) + ( rowItems - 1 ) ] = displacement->vertices[ ( ( index - 1 ) * rowItems ) + ( rowItems - 1 ) ] - lineDelta;

// Compute all other vertices
for( int row = 0 ; row < rowItems ; row++ )
{
lineDelta = ( displacement->vertices[ row * rowItems ] - displacement->vertices[ row * rowItems + ( rowItems - 1 ) ] ) / (float)( rowItems - 1 );

for( int column = 1 ; column < rowItems ; column++ )
displacement->vertices[ row * rowItems + column ] = displacement->vertices[ row * rowItems + ( column - 1 ) ] - lineDelta;
}

// Acquire normals

QList< QByteArray > numbers;

for( int index = 0 ; index < rowItems ; index++ )
numbers.append( brush->sideArray.at( sideIndex ).dispdata->normals.at( index ).split( ' ' ) );

for( int index = 0 ; index < numbers.size() ; index += 3 )
displacement->normals[ index / 3 ] = glm::vec3( numbers.at( index ).toFloat( NULL ) , numbers.at( index + 2 ).toFloat( NULL ) , numbers.at( index + 1 ).toFloat( NULL ) );

numbers.clear();

for( int index = 0 ; index < rowItems ; index++ )
numbers.append( brush->sideArray.at( sideIndex ).dispdata->distances.at( index ).split( ' ' ) );

for( int index = 0 ; index < ( rowItems * rowItems ) ; index++ )
displacement->distances[ index ] = numbers.at( index ).toFloat( NULL );

numbers.clear();

for( int index = 0 ; index < rowItems ; index++ )
numbers.append( brush->sideArray.at( sideIndex ).dispdata->offsets.at( index ).split( ' ' ) );

for( int index = 0 ; index < numbers.size() ; index += 3 )
displacement->offsets[ index / 3 ] = glm::vec3( numbers.at( index ).toFloat( NULL ) , numbers.at( index + 2 ).toFloat( NULL ) , numbers.at( index + 1 ).toFloat( NULL ) );

numbers.clear();

for( int index = 0 ; index < rowItems ; index++ )
numbers.append( brush->sideArray.at( sideIndex ).dispdata->alphas.at( index ).split( ' ' ) );

for( int index = 0 ; index < ( rowItems * rowItems ) ; index++ )
displacement->alphas[ index ] = numbers.at( index ).toUInt( NULL );

displacement->updateVertices();
displacement->setPrimitive( CGL::Points );
}
#endif

// Texture coordinates

QList< QByteArray > textureAxisInfo = brush->sideArray.at( sideIndex ).uaxis.split( ' ' );

if( textureAxisInfo.length() > 4 )
{
textureAxisInfo[ 0 ].remove( 0 , 1 );
textureAxisInfo[ 3 ].chop( 1 );

mesh->ux = textureAxisInfo.at( 0 ).toFloat();
mesh->uz = textureAxisInfo.at( 1 ).toFloat(); // Swap y and z
mesh->uy = textureAxisInfo.at( 2 ).toFloat();
mesh->uo = textureAxisInfo.at( 3 ).toFloat();
mesh->us = textureAxisInfo.at( 4 ).toFloat();

//stream << QString( "uaxis: %1 %2 %3 %4 %5
" ).arg( mesh->ux ).arg( mesh->uy ).arg( mesh->uz ).arg( mesh->uo ).arg( mesh->us );
}

textureAxisInfo = brush->sideArray.at( sideIndex ).vaxis.split( ' ' );

if( textureAxisInfo.length() > 4 )
{
textureAxisInfo[ 0 ].remove( 0 , 1 );
textureAxisInfo[ 3 ].chop( 1 );

mesh->vx = textureAxisInfo.at( 0 ).toFloat();
mesh->vz = textureAxisInfo.at( 1 ).toFloat(); // Swap y and z
mesh->vy = textureAxisInfo.at( 2 ).toFloat();
mesh->vo = textureAxisInfo.at( 3 ).toFloat();
mesh->vs = textureAxisInfo.at( 4 ).toFloat();

//stream << QString( "uaxis: %1 %2 %3 %4 %5
" ).arg( mesh->vx ).arg( mesh->vy ).arg( mesh->vz ).arg( mesh->vo ).arg( mesh->vs );
}

//stream << "

";

cglBrush->sides.append( mesh );
}

//QMessageBox::information( NULL , "" , QString::number( points.size() ) );

return cglBrush;
}

return NULL;
}

``````

Any questions?

No thunder stolen. This is a resource to help people.
I can’t believe how similar your code is to mine though. What libraries did you use?

GLM for vector math and Qt for everything else.

Picture

Finally finished MY program, at least the planes to mesh part of it. I still may need to optimize it more.
Also, I put comments in it, unlike Terrenteller!
http://pastebin.com/fW94NimL

http://puu.sh/3tY1G.png