1133 lines
35 KiB
C++
1133 lines
35 KiB
C++
// Copyright (C) 2007 Id Software, Inc.
|
|
//
|
|
|
|
#include "../precompiled.h"
|
|
#pragma hdrstop
|
|
|
|
|
|
/*
|
|
=================
|
|
UpdateVertexIndex
|
|
=================
|
|
*/
|
|
ID_INLINE int UpdateVertexIndex( int vertexIndexNum[2], int *vertexRemap, vertIndex_t *vertexCopyIndex, int vertNum ) {
|
|
int s = INTSIGNBITSET( vertexRemap[vertNum] );
|
|
|
|
vertexIndexNum[0] = vertexRemap[vertNum];
|
|
vertexRemap[vertNum] = vertexIndexNum[s];
|
|
vertexIndexNum[1] += s;
|
|
vertexCopyIndex[vertexRemap[vertNum]] = vertNum;
|
|
|
|
return vertexRemap[vertNum];
|
|
}
|
|
|
|
//do away with _alloca calls and replace with range-checked arrays - useful for finding crashes during map compiles, for one
|
|
//#define SD_USE_SURFACE_HEAP
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
#define DEREF_INDEX( index ) (*index)
|
|
#else
|
|
#define DEREF_INDEX( index ) index
|
|
#endif
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
ID_INLINE int UpdateVertexIndex_Debug( int vertexIndexNum[2], idList< int >& vertexRemap, idList< int >& vertexCopyIndex, int vertNum ) {
|
|
int s = INTSIGNBITSET( vertexRemap[vertNum] );
|
|
|
|
vertexIndexNum[0] = vertexRemap[vertNum];
|
|
vertexRemap[vertNum] = vertexIndexNum[s];
|
|
vertexIndexNum[1] += s;
|
|
vertexCopyIndex[vertexRemap[vertNum]] = vertNum;
|
|
|
|
return vertexRemap[vertNum];
|
|
}
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
/*
|
|
=================
|
|
idSurface::Split
|
|
=================
|
|
*/
|
|
int idSurface::Split( const idPlane &plane, const float epsilon, idSurface **front, idSurface **back, int *frontOnPlaneEdges, int *backOnPlaneEdges ) const {
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
sdAutoPtr< float, sdArrayCleanupPolicy< float > > dists;
|
|
sdAutoPtr< byte, sdArrayCleanupPolicy< byte > > sides;
|
|
|
|
dists.Reset( new float[ verts.Num() ], verts.Num() );
|
|
sides.Reset( new byte[ verts.Num() ], verts.Num() );
|
|
#else
|
|
float * dists = (float *) _alloca( verts.Num() * sizeof( float ) );
|
|
byte * sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
#undef UpdateVertexIndex
|
|
#define UpdateVertexIndex UpdateVertexIndex_Debug
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
float f;
|
|
int i;
|
|
int counts[3];
|
|
|
|
counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
|
|
|
|
// determine side for each vertex
|
|
for ( i = 0; i < verts.Num(); i++ ) {
|
|
dists[i] = f = plane.Distance( verts[i].xyz );
|
|
if ( f > epsilon ) {
|
|
sides[i] = SIDE_FRONT;
|
|
} else if ( f < -epsilon ) {
|
|
sides[i] = SIDE_BACK;
|
|
} else {
|
|
sides[i] = SIDE_ON;
|
|
}
|
|
counts[sides[i]]++;
|
|
}
|
|
|
|
*front = *back = NULL;
|
|
|
|
// if coplanar, put on the front side if the normals match
|
|
if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
|
|
|
|
f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
|
|
if ( FLOATSIGNBITSET( f ) ) {
|
|
*back = new idSurface( *this );
|
|
return SIDE_BACK;
|
|
} else {
|
|
*front = new idSurface( *this );
|
|
return SIDE_FRONT;
|
|
}
|
|
}
|
|
// if nothing at the front of the clipping plane
|
|
if ( !counts[SIDE_FRONT] ) {
|
|
*back = new idSurface( *this );
|
|
return SIDE_BACK;
|
|
}
|
|
// if nothing at the back of the clipping plane
|
|
if ( !counts[SIDE_BACK] ) {
|
|
*front = new idSurface( *this );
|
|
return SIDE_FRONT;
|
|
}
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
typedef sdAutoPtr< int, sdArrayCleanupPolicy< int > > intArray_t;
|
|
intArray_t edgeSplitVertex;
|
|
intArray_t onPlaneEdges[2];
|
|
idList< int > vertexRemap[2];
|
|
idList< int > vertexCopyIndex[2];
|
|
|
|
idList< int >* indexPtr[2];
|
|
idList< int >* index;
|
|
#else
|
|
int * edgeSplitVertex;
|
|
int * vertexRemap[2];
|
|
int * onPlaneEdges[2];
|
|
vertIndex_t * vertexCopyIndex[2];
|
|
vertIndex_t * indexPtr[2];
|
|
vertIndex_t * index;
|
|
|
|
#endif
|
|
int numEdgeSplitVertexes;
|
|
int vertexIndexNum[2][2];
|
|
int indexNum[2];
|
|
|
|
int numOnPlaneEdges[2];
|
|
int maxOnPlaneEdges;
|
|
idSurface * surface[2];
|
|
idDrawVert v;
|
|
|
|
// allocate front and back surface
|
|
*front = surface[0] = new idSurface();
|
|
*back = surface[1] = new idSurface();
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
edgeSplitVertex.Reset( new int[ edges.Num() ], edges.Num() );
|
|
#else
|
|
edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
numEdgeSplitVertexes = 0;
|
|
|
|
maxOnPlaneEdges = 4 * counts[SIDE_ON];
|
|
|
|
counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0;
|
|
|
|
// split edges
|
|
for ( i = 0; i < edges.Num(); i++ ) {
|
|
int v0 = edges[i].verts[0];
|
|
int v1 = edges[i].verts[1];
|
|
int sidesOr = ( sides[v0] | sides[v1] );
|
|
|
|
// if both vertexes are on the same side or one is on the clipping plane
|
|
if ( !( sides[v0] ^ sides[v1] ) || ( sidesOr & SIDE_ON ) ) {
|
|
edgeSplitVertex[i] = -1;
|
|
counts[sidesOr & SIDE_BACK]++;
|
|
counts[SIDE_ON] += ( sidesOr & SIDE_ON ) >> 1;
|
|
} else {
|
|
f = dists[v0] / ( dists[v0] - dists[v1] );
|
|
v.LerpAll( verts[v0], verts[v1], f );
|
|
edgeSplitVertex[i] = numEdgeSplitVertexes++;
|
|
surface[0]->verts.Append( v );
|
|
surface[1]->verts.Append( v );
|
|
}
|
|
}
|
|
|
|
// each edge is shared by at most two triangles, as such there can never be more indexes than twice the number of edges
|
|
int surfaceIndexCount[ 2 ];
|
|
|
|
// jrad - there are some cases where this isn't enough, sometimes by a factor of 30%
|
|
// bite the bullet and allocate extra memory rather than corrupting the heap later on...
|
|
surfaceIndexCount[ 0 ] = ( ( counts[SIDE_FRONT] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 );
|
|
surfaceIndexCount[ 1 ] = ( ( counts[SIDE_BACK] + counts[SIDE_ON] ) * 2 ) + ( numEdgeSplitVertexes * 4 );
|
|
|
|
surface[0]->indexes.SetNum( surfaceIndexCount[ 0 ] + ( 3 * numEdgeSplitVertexes ) );
|
|
surface[1]->indexes.SetNum( surfaceIndexCount[ 1 ] + ( 3 * numEdgeSplitVertexes ) );
|
|
|
|
// allocate indexes to construct the triangle indexes for the front and back surface
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
vertexRemap[0].Fill( verts.Num(), -1 );
|
|
vertexRemap[1].Fill( verts.Num(), -1 );
|
|
|
|
vertexCopyIndex[0].SetNum( numEdgeSplitVertexes + verts.Num() );
|
|
vertexCopyIndex[1].SetNum( numEdgeSplitVertexes + verts.Num() );
|
|
|
|
indexPtr[0] = &surface[0]->indexes;
|
|
indexPtr[1] = &surface[1]->indexes;
|
|
|
|
#else
|
|
vertexRemap[0] = (int *) _alloca( verts.Num() * sizeof( int ) );
|
|
memset( vertexRemap[0], -1, verts.Num() * sizeof( int ) );
|
|
|
|
vertexRemap[1] = (int *) _alloca( verts.Num() * sizeof( int ) );
|
|
memset( vertexRemap[1], -1, verts.Num() * sizeof( int ) );
|
|
|
|
vertexCopyIndex[0] = (vertIndex_t *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( vertIndex_t ) );
|
|
vertexCopyIndex[1] = (vertIndex_t *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( vertIndex_t ) );
|
|
|
|
indexPtr[0] = surface[0]->indexes.Begin();
|
|
indexPtr[1] = surface[1]->indexes.Begin();
|
|
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
vertexIndexNum[0][0] = vertexIndexNum[1][0] = 0;
|
|
vertexIndexNum[0][1] = vertexIndexNum[1][1] = numEdgeSplitVertexes;
|
|
|
|
indexNum[0] = 0;
|
|
indexNum[1] = 0;
|
|
|
|
maxOnPlaneEdges += 4 * numEdgeSplitVertexes;
|
|
|
|
// allocate one more in case no triangles are actually split which may happen for a disconnected surface
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
onPlaneEdges[0].Reset( new int[ maxOnPlaneEdges + 1 ], maxOnPlaneEdges + 1 );
|
|
onPlaneEdges[1].Reset( new int[ maxOnPlaneEdges + 1 ], maxOnPlaneEdges + 1 );
|
|
#else
|
|
onPlaneEdges[0] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
|
|
onPlaneEdges[1] = (int *) _alloca( ( maxOnPlaneEdges + 1 ) * sizeof( int ) );
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
numOnPlaneEdges[0] = numOnPlaneEdges[1] = 0;
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
int resizeCount[2];
|
|
resizeCount[0] = resizeCount[1] = 0;
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
// split surface triangles
|
|
for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
|
|
int e0, e1, e2, v0, v1, v2, s, n;
|
|
|
|
e0 = idMath::Abs( edgeIndexes[i+0] );
|
|
e1 = idMath::Abs( edgeIndexes[i+1] );
|
|
e2 = idMath::Abs( edgeIndexes[i+2] );
|
|
|
|
v0 = indexes[i+0];
|
|
v1 = indexes[i+1];
|
|
v2 = indexes[i+2];
|
|
#if 0
|
|
if( indexNum[ 0 ] >= surface[ 0 ]->indexes.Num() ) {
|
|
surface[ 0 ]->indexes.SetNum( indexNum[ 0 ] + 3 );
|
|
resizeCount[0] += 3;
|
|
//assert( 0 );
|
|
}
|
|
if( indexNum[ 1 ] >= surface[ 1 ]->indexes.Num() ) {
|
|
surface[ 1 ]->indexes.SetNum( indexNum[ 1 ] + 3 );
|
|
resizeCount[1] += 3;
|
|
//assert( 0 );
|
|
}
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
#else
|
|
indexPtr[0] = surface[0]->indexes.Begin();
|
|
indexPtr[1] = surface[1]->indexes.Begin();
|
|
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
#endif // 0
|
|
|
|
switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
|
|
case 0: { // no edges split
|
|
if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
|
|
// coplanar
|
|
f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
|
|
s = FLOATSIGNBITSET( f );
|
|
} else {
|
|
s = ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK;
|
|
}
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]] = n;
|
|
numOnPlaneEdges[s] += ( sides[v0] & sides[v1] ) >> 1;
|
|
onPlaneEdges[s][numOnPlaneEdges[s]] = n+1;
|
|
numOnPlaneEdges[s] += ( sides[v1] & sides[v2] ) >> 1;
|
|
onPlaneEdges[s][numOnPlaneEdges[s]] = n+2;
|
|
numOnPlaneEdges[s] += ( sides[v2] & sides[v0] ) >> 1;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 1: { // first edge split
|
|
s = sides[v0] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 2: { // second edge split
|
|
s = sides[v1] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 3: { // first and second edge split
|
|
s = sides[v1] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 4: { // third edge split
|
|
s = sides[v2] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 5: { // first and third edge split
|
|
s = sides[v0] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e0];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
case 6: { // second and third edge split
|
|
s = sides[v2] & SIDE_BACK;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v2 );
|
|
|
|
indexNum[s] = n;
|
|
s ^= 1;
|
|
n = indexNum[s];
|
|
onPlaneEdges[s][numOnPlaneEdges[s]++] = n;
|
|
index = indexPtr[s];
|
|
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e1];
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v0 );
|
|
DEREF_INDEX( index )[n++] = UpdateVertexIndex( vertexIndexNum[s], vertexRemap[s], vertexCopyIndex[s], v1 );
|
|
DEREF_INDEX( index )[n++] = edgeSplitVertex[e2];
|
|
|
|
indexNum[s] = n;
|
|
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
surface[0]->indexes.SetNum( indexNum[0], false );
|
|
surface[1]->indexes.SetNum( indexNum[1], false );
|
|
|
|
// copy vertexes
|
|
surface[0]->verts.SetNum( vertexIndexNum[0][1], false );
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
index = &vertexCopyIndex[0];
|
|
#else
|
|
index = vertexCopyIndex[0];
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
for ( i = numEdgeSplitVertexes; i < surface[0]->verts.Num(); i++ ) {
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
if( DEREF_INDEX( index )[i] >= verts.Num() || DEREF_INDEX( index )[i] < 0 ) {
|
|
assert( 0 );
|
|
idLib::Error( "Invalid index" );
|
|
}
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
surface[0]->verts[i] = verts[DEREF_INDEX( index )[i]];
|
|
}
|
|
|
|
|
|
surface[1]->verts.SetNum( vertexIndexNum[1][1], false );
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
index = &vertexCopyIndex[1];
|
|
#else
|
|
index = vertexCopyIndex[1];
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
for ( i = numEdgeSplitVertexes; i < surface[1]->verts.Num(); i++ ) {
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
if( DEREF_INDEX( index )[i] >= verts.Num() || DEREF_INDEX( index )[i] < 0 ) {
|
|
assert( 0 );
|
|
idLib::Error( "Invalid index" );
|
|
}
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
surface[1]->verts[i] = verts[DEREF_INDEX( index )[i]];
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
for ( i = 0; i < surface[0]->indexes.Num(); i++ ) {
|
|
if( surface[0]->indexes[ i ] >= surface[0]->verts.Num() || surface[0]->indexes[ i ] < 0 ) {
|
|
assert( 0 );
|
|
}
|
|
}
|
|
for ( i = 0; i < surface[1]->indexes.Num(); i++ ) {
|
|
if( surface[1]->indexes[ i ] >= surface[1]->verts.Num() || surface[1]->indexes[ i ] < 0 ) {
|
|
assert( 0 );
|
|
}
|
|
}
|
|
#endif //_DEBUG
|
|
|
|
|
|
// generate edge indexes
|
|
surface[0]->GenerateEdgeIndexes();
|
|
surface[1]->GenerateEdgeIndexes();
|
|
|
|
if ( frontOnPlaneEdges ) {
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
memcpy( frontOnPlaneEdges, onPlaneEdges[0].Get(), numOnPlaneEdges[0] * sizeof( int ) );
|
|
#else
|
|
memcpy( frontOnPlaneEdges, onPlaneEdges[0], numOnPlaneEdges[0] * sizeof( int ) );
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
frontOnPlaneEdges[numOnPlaneEdges[0]] = -1;
|
|
}
|
|
|
|
if ( backOnPlaneEdges ) {
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
memcpy( backOnPlaneEdges, onPlaneEdges[1].Get(), numOnPlaneEdges[1] * sizeof( int ) );
|
|
#else
|
|
memcpy( backOnPlaneEdges, onPlaneEdges[1], numOnPlaneEdges[1] * sizeof( int ) );
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
backOnPlaneEdges[numOnPlaneEdges[1]] = -1;
|
|
}
|
|
|
|
#ifdef SD_USE_SURFACE_HEAP
|
|
if( resizeCount[ 0 ] > 0 ) {
|
|
idLib::Warning( "idSurface::Split: had to resize index list 0 by %i elements", resizeCount[0] );
|
|
assert( 0 );
|
|
}
|
|
if( resizeCount[ 1 ] > 0 ) {
|
|
idLib::Warning( "idSurface::Split: had to resize index list 1 by %i elements", resizeCount[1] );
|
|
assert( 0 );
|
|
}
|
|
#endif // SD_USE_SURFACE_HEAP
|
|
|
|
return SIDE_CROSS;
|
|
}
|
|
|
|
#undef UpdateVertexIndex
|
|
#undef SD_USE_SURFACE_HEAP
|
|
|
|
/*
|
|
=================
|
|
idSurface::ClipInPlace
|
|
=================
|
|
*/
|
|
bool idSurface::ClipInPlace( const idPlane &plane, const float epsilon, const bool keepOn ) {
|
|
if( verts.Num() == 0 ) {
|
|
return false;
|
|
}
|
|
|
|
float * dists;
|
|
float f;
|
|
byte * sides;
|
|
int counts[3];
|
|
int i;
|
|
int * edgeSplitVertex;
|
|
int * vertexRemap;
|
|
int vertexIndexNum[2];
|
|
vertIndex_t * vertexCopyIndex;
|
|
vertIndex_t * indexPtr;
|
|
int indexNum;
|
|
int numEdgeSplitVertexes;
|
|
idDrawVert v;
|
|
idList<idDrawVert> newVerts;
|
|
idList<vertIndex_t> newIndexes;
|
|
|
|
dists = (float *) _alloca( verts.Num() * sizeof( float ) );
|
|
sides = (byte *) _alloca( verts.Num() * sizeof( byte ) );
|
|
|
|
counts[0] = counts[1] = counts[2] = 0;
|
|
|
|
// determine side for each vertex
|
|
for ( i = 0; i < verts.Num(); i++ ) {
|
|
dists[i] = f = plane.Distance( verts[i].xyz );
|
|
if ( f > epsilon ) {
|
|
sides[i] = SIDE_FRONT;
|
|
} else if ( f < -epsilon ) {
|
|
sides[i] = SIDE_BACK;
|
|
} else {
|
|
sides[i] = SIDE_ON;
|
|
}
|
|
counts[sides[i]]++;
|
|
}
|
|
|
|
// if coplanar, put on the front side if the normals match
|
|
if ( !counts[SIDE_FRONT] && !counts[SIDE_BACK] ) {
|
|
|
|
f = ( verts[indexes[1]].xyz - verts[indexes[0]].xyz ).Cross( verts[indexes[0]].xyz - verts[indexes[2]].xyz ) * plane.Normal();
|
|
if ( FLOATSIGNBITSET( f ) ) {
|
|
Clear();
|
|
return false;
|
|
} else {
|
|
return true;
|
|
}
|
|
}
|
|
// if nothing at the front of the clipping plane
|
|
if ( !counts[SIDE_FRONT] ) {
|
|
Clear();
|
|
return false;
|
|
}
|
|
// if nothing at the back of the clipping plane
|
|
if ( !counts[SIDE_BACK] ) {
|
|
return true;
|
|
}
|
|
|
|
edgeSplitVertex = (int *) _alloca( edges.Num() * sizeof( int ) );
|
|
numEdgeSplitVertexes = 0;
|
|
|
|
counts[SIDE_FRONT] = counts[SIDE_BACK] = 0;
|
|
|
|
// split edges
|
|
for ( i = 0; i < edges.Num(); i++ ) {
|
|
int v0 = edges[i].verts[0];
|
|
int v1 = edges[i].verts[1];
|
|
|
|
// if both vertexes are on the same side or one is on the clipping plane
|
|
if ( !( sides[v0] ^ sides[v1] ) || ( ( sides[v0] | sides[v1] ) & SIDE_ON ) ) {
|
|
edgeSplitVertex[i] = -1;
|
|
counts[(sides[v0]|sides[v1]) & SIDE_BACK]++;
|
|
} else {
|
|
f = dists[v0] / ( dists[v0] - dists[v1] );
|
|
v.LerpAll( verts[v0], verts[v1], f );
|
|
edgeSplitVertex[i] = numEdgeSplitVertexes++;
|
|
newVerts.Append( v );
|
|
}
|
|
}
|
|
|
|
// each edge is shared by at most two triangles, as such there can never be
|
|
// more indexes than twice the number of edges
|
|
newIndexes.Resize( ( counts[SIDE_FRONT] << 1 ) + ( numEdgeSplitVertexes << 2 ) );
|
|
|
|
// allocate indexes to construct the triangle indexes for the front and back surface
|
|
vertexRemap = (int *) _alloca( verts.Num() * sizeof( int ) );
|
|
memset( vertexRemap, -1, verts.Num() * sizeof( int ) );
|
|
|
|
vertexCopyIndex = (vertIndex_t *) _alloca( ( numEdgeSplitVertexes + verts.Num() ) * sizeof( vertIndex_t ) );
|
|
|
|
vertexIndexNum[0] = 0;
|
|
vertexIndexNum[1] = numEdgeSplitVertexes;
|
|
|
|
indexPtr = newIndexes.Begin();
|
|
indexNum = newIndexes.Num();
|
|
|
|
// split surface triangles
|
|
for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
|
|
int e0, e1, e2, v0, v1, v2;
|
|
|
|
e0 = idMath::Abs( edgeIndexes[i+0] );
|
|
e1 = idMath::Abs( edgeIndexes[i+1] );
|
|
e2 = idMath::Abs( edgeIndexes[i+2] );
|
|
|
|
v0 = indexes[i+0];
|
|
v1 = indexes[i+1];
|
|
v2 = indexes[i+2];
|
|
|
|
switch( ( INTSIGNBITSET( edgeSplitVertex[e0] ) | ( INTSIGNBITSET( edgeSplitVertex[e1] ) << 1 ) | ( INTSIGNBITSET( edgeSplitVertex[e2] ) << 2 ) ) ^ 7 ) {
|
|
case 0: { // no edges split
|
|
if ( ( sides[v0] | sides[v1] | sides[v2] ) & SIDE_BACK ) {
|
|
break;
|
|
}
|
|
if ( ( sides[v0] & sides[v1] & sides[v2] ) & SIDE_ON ) {
|
|
// coplanar
|
|
if ( !keepOn ) {
|
|
break;
|
|
}
|
|
f = ( verts[v1].xyz - verts[v0].xyz ).Cross( verts[v0].xyz - verts[v2].xyz ) * plane.Normal();
|
|
if ( FLOATSIGNBITSET( f ) ) {
|
|
break;
|
|
}
|
|
}
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
break;
|
|
}
|
|
case 1: { // first edge split
|
|
if ( !( sides[v0] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
} else {
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
}
|
|
break;
|
|
}
|
|
case 2: { // second edge split
|
|
if ( !( sides[v1] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
} else {
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
}
|
|
break;
|
|
}
|
|
case 3: { // first and second edge split
|
|
if ( !( sides[v1] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
} else {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
}
|
|
break;
|
|
}
|
|
case 4: { // third edge split
|
|
if ( !( sides[v2] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
} else {
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
}
|
|
break;
|
|
}
|
|
case 5: { // first and third edge split
|
|
if ( !( sides[v0] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
} else {
|
|
indexPtr[indexNum++] = edgeSplitVertex[e0];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
}
|
|
break;
|
|
}
|
|
case 6: { // second and third edge split
|
|
if ( !( sides[v2] & SIDE_BACK ) ) {
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v2 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
} else {
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e1];
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v0 );
|
|
indexPtr[indexNum++] = UpdateVertexIndex( vertexIndexNum, vertexRemap, vertexCopyIndex, v1 );
|
|
indexPtr[indexNum++] = edgeSplitVertex[e2];
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
newIndexes.SetNum( indexNum, false );
|
|
|
|
// copy vertexes
|
|
newVerts.SetNum( vertexIndexNum[1], false );
|
|
for ( i = numEdgeSplitVertexes; i < newVerts.Num(); i++ ) {
|
|
newVerts[i] = verts[vertexCopyIndex[i]];
|
|
}
|
|
|
|
// copy back to this surface
|
|
indexes = newIndexes;
|
|
verts = newVerts;
|
|
|
|
GenerateEdgeIndexes();
|
|
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
=============
|
|
idSurface::IsConnected
|
|
=============
|
|
*/
|
|
bool idSurface::IsConnected( void ) const {
|
|
int i, j, numIslands, numTris;
|
|
int queueStart, queueEnd;
|
|
int *queue, *islandNum;
|
|
int curTri, nextTri, edgeNum;
|
|
const int *index;
|
|
|
|
numIslands = 0;
|
|
numTris = indexes.Num() / 3;
|
|
islandNum = (int *) _alloca16( numTris * sizeof( int ) );
|
|
memset( islandNum, -1, numTris * sizeof( int ) );
|
|
queue = (int *) _alloca16( numTris * sizeof( int ) );
|
|
|
|
for ( i = 0; i < numTris; i++ ) {
|
|
|
|
if ( islandNum[i] != -1 ) {
|
|
continue;
|
|
}
|
|
|
|
queueStart = 0;
|
|
queueEnd = 1;
|
|
queue[0] = i;
|
|
islandNum[i] = numIslands;
|
|
|
|
for ( curTri = queue[queueStart]; queueStart < queueEnd; curTri = queue[++queueStart] ) {
|
|
|
|
index = &edgeIndexes[curTri * 3];
|
|
|
|
for ( j = 0; j < 3; j++ ) {
|
|
|
|
edgeNum = index[j];
|
|
nextTri = edges[idMath::Abs(edgeNum)].tris[INTSIGNBITNOTSET(edgeNum)];
|
|
|
|
if ( nextTri == -1 ) {
|
|
continue;
|
|
}
|
|
|
|
nextTri /= 3;
|
|
|
|
if ( islandNum[nextTri] != -1 ) {
|
|
continue;
|
|
}
|
|
|
|
queue[queueEnd++] = nextTri;
|
|
islandNum[nextTri] = numIslands;
|
|
}
|
|
}
|
|
numIslands++;
|
|
}
|
|
|
|
return ( numIslands == 1 );
|
|
}
|
|
|
|
/*
|
|
=================
|
|
idSurface::IsClosed
|
|
=================
|
|
*/
|
|
bool idSurface::IsClosed( void ) const {
|
|
for ( int i = 0; i < edges.Num(); i++ ) {
|
|
if ( edges[i].tris[0] < 0 || edges[i].tris[1] < 0 ) {
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
=============
|
|
idSurface::IsPolytope
|
|
=============
|
|
*/
|
|
bool idSurface::IsPolytope( const float epsilon ) const {
|
|
int i, j;
|
|
idPlane plane;
|
|
|
|
if ( !IsClosed() ) {
|
|
return false;
|
|
}
|
|
|
|
for ( i = 0; i < indexes.Num(); i += 3 ) {
|
|
plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
|
|
|
|
for ( j = 0; j < verts.Num(); j++ ) {
|
|
if ( plane.Side( verts[j].xyz, epsilon ) == SIDE_FRONT ) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
/*
|
|
=============
|
|
idSurface::PlaneDistance
|
|
=============
|
|
*/
|
|
float idSurface::PlaneDistance( const idPlane &plane ) const {
|
|
int i;
|
|
float d, min, max;
|
|
|
|
min = idMath::INFINITY;
|
|
max = -min;
|
|
for ( i = 0; i < verts.Num(); i++ ) {
|
|
d = plane.Distance( verts[i].xyz );
|
|
if ( d < min ) {
|
|
min = d;
|
|
if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
|
|
return 0.0f;
|
|
}
|
|
}
|
|
if ( d > max ) {
|
|
max = d;
|
|
if ( FLOATSIGNBITSET( min ) & FLOATSIGNBITNOTSET( max ) ) {
|
|
return 0.0f;
|
|
}
|
|
}
|
|
}
|
|
if ( FLOATSIGNBITNOTSET( min ) ) {
|
|
return min;
|
|
}
|
|
if ( FLOATSIGNBITSET( max ) ) {
|
|
return max;
|
|
}
|
|
return 0.0f;
|
|
}
|
|
|
|
/*
|
|
=============
|
|
idSurface::PlaneSide
|
|
=============
|
|
*/
|
|
int idSurface::PlaneSide( const idPlane &plane, const float epsilon ) const {
|
|
bool front, back;
|
|
int i;
|
|
float d;
|
|
|
|
front = false;
|
|
back = false;
|
|
for ( i = 0; i < verts.Num(); i++ ) {
|
|
d = plane.Distance( verts[i].xyz );
|
|
if ( d < -epsilon ) {
|
|
if ( front ) {
|
|
return SIDE_CROSS;
|
|
}
|
|
back = true;
|
|
continue;
|
|
}
|
|
else if ( d > epsilon ) {
|
|
if ( back ) {
|
|
return SIDE_CROSS;
|
|
}
|
|
front = true;
|
|
continue;
|
|
}
|
|
}
|
|
|
|
if ( back ) {
|
|
return SIDE_BACK;
|
|
}
|
|
if ( front ) {
|
|
return SIDE_FRONT;
|
|
}
|
|
return SIDE_ON;
|
|
}
|
|
|
|
/*
|
|
=================
|
|
idSurface::LineIntersection
|
|
=================
|
|
*/
|
|
bool idSurface::LineIntersection( const idVec3 &start, const idVec3 &end, bool backFaceCull ) const {
|
|
float scale;
|
|
|
|
RayIntersection( start, end - start, scale, false );
|
|
return ( scale >= 0.0f && scale <= 1.0f );
|
|
}
|
|
|
|
/*
|
|
=================
|
|
idSurface::RayIntersection
|
|
=================
|
|
*/
|
|
bool idSurface::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull ) const {
|
|
int i, i0, i1, i2, s0, s1, s2;
|
|
float d, s;
|
|
byte *sidedness;
|
|
idPluecker rayPl, pl;
|
|
idPlane plane;
|
|
|
|
sidedness = (byte *)_alloca( edges.Num() * sizeof(byte) );
|
|
scale = idMath::INFINITY;
|
|
|
|
rayPl.FromRay( start, dir );
|
|
|
|
// ray sidedness for edges
|
|
for ( i = 0; i < edges.Num(); i++ ) {
|
|
pl.FromLine( verts[ edges[i].verts[1] ].xyz, verts[ edges[i].verts[0] ].xyz );
|
|
d = pl.PermutedInnerProduct( rayPl );
|
|
sidedness[ i ] = FLOATSIGNBITSET( d );
|
|
}
|
|
|
|
// test triangles
|
|
for ( i = 0; i < edgeIndexes.Num(); i += 3 ) {
|
|
i0 = edgeIndexes[i+0];
|
|
i1 = edgeIndexes[i+1];
|
|
i2 = edgeIndexes[i+2];
|
|
s0 = sidedness[idMath::Abs(i0)] ^ INTSIGNBITSET( i0 );
|
|
s1 = sidedness[idMath::Abs(i1)] ^ INTSIGNBITSET( i1 );
|
|
s2 = sidedness[idMath::Abs(i2)] ^ INTSIGNBITSET( i2 );
|
|
|
|
if ( s0 & s1 & s2 ) {
|
|
plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
|
|
plane.RayIntersection( start, dir, s );
|
|
if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
|
|
scale = s;
|
|
}
|
|
} else if ( !backFaceCull && !(s0 | s1 | s2) ) {
|
|
plane.FromPoints( verts[indexes[i+0]].xyz, verts[indexes[i+1]].xyz, verts[indexes[i+2]].xyz );
|
|
plane.RayIntersection( start, dir, s );
|
|
if ( idMath::Fabs( s ) < idMath::Fabs( scale ) ) {
|
|
scale = s;
|
|
}
|
|
}
|
|
}
|
|
|
|
if ( idMath::Fabs( scale ) < idMath::INFINITY ) {
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
/*
|
|
=================
|
|
idSurface::GenerateEdgeIndexes
|
|
|
|
Assumes each edge is shared by at most two triangles.
|
|
=================
|
|
*/
|
|
void idSurface::GenerateEdgeIndexes( void ) {
|
|
if( verts.Num() == 0 || indexes.Num() == 0 ) {
|
|
assert( 0 );
|
|
return;
|
|
}
|
|
int i, j, i0, i1, i2, s, v0, v1, edgeNum;
|
|
vertIndex_t* index;
|
|
int *vertexEdges, *edgeChain;
|
|
surfaceEdge_t e[3];
|
|
|
|
// protect against stack overflow
|
|
bool usingStack = true;
|
|
if ( ( verts.Num() * sizeof( int ) ) + ( indexes.Num() * sizeof( int ) ) > 1048576 /*4194304*/ ) {
|
|
usingStack = false;
|
|
vertexEdges = (int *) Mem_AllocAligned( verts.Num() * sizeof( int ), ALIGN_16 );
|
|
memset( vertexEdges, -1, verts.Num() * sizeof( int ) );
|
|
edgeChain = (int *) Mem_AllocAligned( indexes.Num() * sizeof( int ), ALIGN_16 );
|
|
} else {
|
|
vertexEdges = (int *) _alloca16( verts.Num() * sizeof( int ) );
|
|
memset( vertexEdges, -1, verts.Num() * sizeof( int ) );
|
|
edgeChain = (int *) _alloca16( indexes.Num() * sizeof( int ) );
|
|
}
|
|
|
|
edgeIndexes.SetNum( indexes.Num(), true );
|
|
|
|
edges.Clear();
|
|
// jrad - deal with large models more nicely
|
|
edges.SetGranularity( indexes.Num() / 3 );
|
|
|
|
// the first edge is a dummy
|
|
e[0].verts[0] = e[0].verts[1] = e[0].tris[0] = e[0].tris[1] = 0;
|
|
edges.Append( e[0] );
|
|
|
|
for ( i = 0; i < indexes.Num(); i += 3 ) {
|
|
index = indexes.Begin() + i;
|
|
// vertex numbers
|
|
i0 = index[0];
|
|
i1 = index[1];
|
|
i2 = index[2];
|
|
// setup edges each with smallest vertex number first
|
|
s = INTSIGNBITSET(i1 - i0);
|
|
e[0].verts[0] = index[s];
|
|
e[0].verts[1] = index[s^1];
|
|
s = INTSIGNBITSET(i2 - i1) + 1;
|
|
e[1].verts[0] = index[s];
|
|
e[1].verts[1] = index[s^3];
|
|
s = INTSIGNBITSET(i2 - i0) << 1;
|
|
e[2].verts[0] = index[s];
|
|
e[2].verts[1] = index[s^2];
|
|
// get edges
|
|
for ( j = 0; j < 3; j++ ) {
|
|
v0 = e[j].verts[0];
|
|
v1 = e[j].verts[1];
|
|
for ( edgeNum = vertexEdges[v0]; edgeNum >= 0; edgeNum = edgeChain[edgeNum] ) {
|
|
if ( edges[edgeNum].verts[1] == v1 ) {
|
|
break;
|
|
}
|
|
}
|
|
// if the edge does not yet exist
|
|
if ( edgeNum < 0 ) {
|
|
e[j].tris[0] = e[j].tris[1] = -1;
|
|
edgeNum = edges.Append( e[j] );
|
|
edgeChain[edgeNum] = vertexEdges[v0];
|
|
vertexEdges[v0] = edgeNum;
|
|
}
|
|
// update edge index and edge tri references
|
|
if ( index[j] == v0 ) {
|
|
//assert( edges[edgeNum].tris[0] == -1 ); // edge may not be shared by more than two triangles
|
|
edges[edgeNum].tris[0] = i;
|
|
edgeIndexes[i+j] = edgeNum;
|
|
} else {
|
|
//assert( edges[edgeNum].tris[1] == -1 ); // edge may not be shared by more than two triangles
|
|
edges[edgeNum].tris[1] = i;
|
|
edgeIndexes[i+j] = -edgeNum;
|
|
}
|
|
}
|
|
}
|
|
|
|
edges.Resize( edges.Num(), 16 );
|
|
|
|
if ( !usingStack ) {
|
|
Mem_FreeAligned( vertexEdges );
|
|
Mem_FreeAligned( edgeChain );
|
|
}
|
|
}
|
|
|
|
/*
|
|
=================
|
|
idSurface::FindEdge
|
|
=================
|
|
*/
|
|
int idSurface::FindEdge( int v1, int v2 ) const {
|
|
int i, firstVert, secondVert;
|
|
|
|
if ( v1 < v2 ) {
|
|
firstVert = v1;
|
|
secondVert = v2;
|
|
} else {
|
|
firstVert = v2;
|
|
secondVert = v1;
|
|
}
|
|
for ( i = 1; i < edges.Num(); i++ ) {
|
|
if ( edges[i].verts[0] == firstVert ) {
|
|
if ( edges[i].verts[1] == secondVert ) {
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
if ( i < edges.Num() ) {
|
|
return v1 < v2 ? i : -i;
|
|
}
|
|
return 0;
|
|
}
|