LOD.rar_LOD_dirext_四叉树 lod 地形_四叉树 地形_ＬＯＤ地形

#include "StdAfx.h" #include "ZQuadTree.h" // 最初循环节点创建者 ZQuadTree::ZQuadTree( int cx, int cy ) { int i; m_pParent = NULL; for( i = 0 ; i < 4 ; i++ ) { m_pChild[i] = NULL; m_pNeighbor[i] = NULL; } // 设置循环节点的4个角值 m_nCorner[CORNER_TL] = 0; m_nCorner[CORNER_TR] = cx - 1; m_nCorner[CORNER_BL] = cx * ( cy - 1 ); m_nCorner[CORNER_BR] = cx * cy - 1; m_nCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; m_bCulled = FALSE; m_fRadius = 0.0f; } // 下层子节点创建者 ZQuadTree::ZQuadTree( ZQuadTree* pParent ) { int i; m_pParent = pParent; m_nCenter = 0; for( i = 0 ; i < 4 ; i++ ) { m_pChild[i] = NULL; m_pNeighbor[i] = NULL; m_nCorner[i] = 0; } m_bCulled = FALSE; m_fRadius = 0.0f; } // 删除者 ZQuadTree::~ZQuadTree() { _Destroy(); } // 在存储器中删除四叉树. void ZQuadTree::_Destroy() { // 删除子节点. for( int i = 0 ; i < 4 ; i++ ) { SAFE_DELETE( m_pChild[i] ); } } // 设置4个角值. BOOL ZQuadTree::_SetCorners( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ) { m_nCorner[CORNER_TL] = nCornerTL; m_nCorner[CORNER_TR] = nCornerTR; m_nCorner[CORNER_BL] = nCornerBL; m_nCorner[CORNER_BR] = nCornerBR; m_nCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; return TRUE; } // 添加子节点. ZQuadTree* ZQuadTree::_AddChild( int nCornerTL, int nCornerTR, int nCornerBL, int nCornerBR ) { ZQuadTree* pChild; pChild = new ZQuadTree( this ); pChild->_SetCorners( nCornerTL, nCornerTR, nCornerBL, nCornerBR ); return pChild; } // 使用4个下层对四叉树进行再分割（subdivide）. BOOL ZQuadTree::_SubDivide() { int nTopEdgeCenter; int nBottomEdgeCenter; int nLeftEdgeCenter; int nRightEdgeCenter; int nCentralPoint; // 上边中间 nTopEdgeCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] ) / 2; // 下边中间 nBottomEdgeCenter = ( m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 2; // 左边中间 nLeftEdgeCenter = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_BL] ) / 2; // 右边中间 nRightEdgeCenter = ( m_nCorner[CORNER_TR] + m_nCorner[CORNER_BR] ) / 2; // 正中央 nCentralPoint = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] + m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 4; // 不能进行再分割了？那么SubDivide() 结束 if( (m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL]) <= 1 ) { return FALSE; } // 添加4个子节点 m_pChild[CORNER_TL] = _AddChild( m_nCorner[CORNER_TL], nTopEdgeCenter, nLeftEdgeCenter, nCentralPoint ); m_pChild[CORNER_TR] = _AddChild( nTopEdgeCenter, m_nCorner[CORNER_TR], nCentralPoint, nRightEdgeCenter ); m_pChild[CORNER_BL] = _AddChild( nLeftEdgeCenter, nCentralPoint, m_nCorner[CORNER_BL], nBottomEdgeCenter ); m_pChild[CORNER_BR] = _AddChild( nCentralPoint, nRightEdgeCenter, nBottomEdgeCenter, m_nCorner[CORNER_BR] ); return TRUE; } // 创建输出多边形的索引. int ZQuadTree::_GenTriIndex( int nTris, LPVOID pIndex, TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum, float fLODRatio ) { // 如果是剔除的节点，直接返回 if( m_bCulled ) { m_bCulled = FALSE; return nTris; } //#ifdef _USE_INDEX16 // LPWORD p = ((LPWORD)pIndex) + nTris * 3; //#else // LPDWORD p = ((LPDWORD)pIndex) + nTris * 3; //#endif LPWORD p = ((LPWORD)pIndex) + nTris * 3; // 当前节点必须输出? if( IsVisible( pHeightMap, pFrustum->GetPos(), fLODRatio ) ) { // 如果是最下层的节点，不能进行再分割（subdivide）的话，直接输出并返回. if( m_nCorner[CORNER_TR] - m_nCorner[CORNER_TL] <= 1 ) { *p++ = m_nCorner[0]; *p++ = m_nCorner[1]; *p++ = m_nCorner[2]; nTris++; *p++ = m_nCorner[2]; *p++ = m_nCorner[1]; *p++ = m_nCorner[3]; nTris++; return nTris; } BOOL b[4]={false,false,false,false}; // 上方邻近节点（neightbor node）可以输出? if( m_pNeighbor[EDGE_UP] ) b[EDGE_UP] = m_pNeighbor[EDGE_UP]->IsVisible( pHeightMap, pFrustum->GetPos(), fLODRatio ); // 下方邻近节点（neightbor node）可以输出? if( m_pNeighbor[EDGE_DN] ) b[EDGE_DN] = m_pNeighbor[EDGE_DN]->IsVisible( pHeightMap, pFrustum->GetPos(), fLODRatio ); // 左方邻近节点（neightbor node）可以输出? if( m_pNeighbor[EDGE_LT] ) b[EDGE_LT] = m_pNeighbor[EDGE_LT]->IsVisible( pHeightMap, pFrustum->GetPos(), fLODRatio ); // 右方邻近节点（neightbor node）可以输出? if( m_pNeighbor[EDGE_RT] ) b[EDGE_RT] = m_pNeighbor[EDGE_RT]->IsVisible( pHeightMap, pFrustum->GetPos(), fLODRatio ); // 所有的邻近节点都可以输出的话，当前节点和邻近节点就是同一个LOD // 就不需要进行再分割. if( b[EDGE_UP] && b[EDGE_DN] && b[EDGE_LT] && b[EDGE_RT] ) { *p++ = m_nCorner[0]; *p++ = m_nCorner[1]; *p++ = m_nCorner[2]; nTris++; *p++ = m_nCorner[2]; *p++ = m_nCorner[1]; *p++ = m_nCorner[3]; nTris++; return nTris; } int n; if( !b[EDGE_UP] ) // 需要上方再分割 { n = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_TR] ) / 2; *p++ = m_nCenter; *p++ = m_nCorner[CORNER_TL]; *p++ = n; nTris++; *p++ = m_nCenter; *p++ = n; *p++ = m_nCorner[CORNER_TR]; nTris++; } else // 不需要上方再分割的情况 { *p++ = m_nCenter; *p++ = m_nCorner[CORNER_TL]; *p++ = m_nCorner[CORNER_TR]; nTris++; } if( !b[EDGE_DN] ) // 需要下方再分割 { n = ( m_nCorner[CORNER_BL] + m_nCorner[CORNER_BR] ) / 2; *p++ = m_nCenter; *p++ = m_nCorner[CORNER_BR]; *p++ = n; nTris++; *p++ = m_nCenter; *p++ = n; *p++ = m_nCorner[CORNER_BL]; nTris++; } else // 不需要下方再分割的情况 { *p++ = m_nCenter; *p++ = m_nCorner[CORNER_BR]; *p++ = m_nCorner[CORNER_BL]; nTris++; } if( !b[EDGE_LT] ) // 需要左侧再分割 { n = ( m_nCorner[CORNER_TL] + m_nCorner[CORNER_BL] ) / 2; *p++ = m_nCenter; *p++ = m_nCorner[CORNER_BL]; *p++ = n; nTris++; *p++ = m_nCenter; *p++ = n; *p++ = m_nCorner[CORNER_TL]; nTris++; } else // 不需要左侧再分割的情况 { *p++ = m_nCenter; *p++ = m_nCorner[CORNER_BL]; *p++ = m_nCorner[CORNER_TL]; nTris++; } if( !b[EDGE_RT] ) // 需要右侧再分割 { n = ( m_nCorner[CORNER_TR] + m_nCorner[CORNER_BR] ) / 2; *p++ = m_nCenter; *p++ = m_nCorner[CORNER_TR]; *p++ = n; nTris++; *p++ = m_nCenter; *p++ = n; *p++ = m_nCorner[CORNER_BR]; nTris++; } else // 不需要右侧再分割的情况 { *p++ = m_nCenter; *p++ = m_nCorner[CORNER_TR]; *p++ = m_nCorner[CORNER_BR]; nTris++; } return nTris; // 由于该节点下的子节点没有检索的必要，返回! } // 检索子节点 if( m_pChild[CORNER_TL] ) nTris = m_pChild[CORNER_TL]->_GenTriIndex( nTris, pIndex, pHeightMap, pFrustum, fLODRatio ); if( m_pChild[CORNER_TR] ) nTris = m_pChild[CORNER_TR]->_GenTriIndex( nTris, pIndex, pHeightMap, pFrustum, fLODRatio ); if( m_pChild[CORNER_BL] ) nTris = m_pChild[CORNER_BL]->_GenTriIndex( nTris, pIndex, pHeightMap, pFrustum, fLODRatio ); if( m_pChild[CORNER_BR] ) nTris = m_pChild[CORNER_BR]->_GenTriIndex( nTris, pIndex, pHeightMap, pFrustum, fLODRatio ); return nTris; } // 当前节点包含在平截头体? int ZQuadTree::_IsInFrustum( TERRAINVERTEX* pHeightMap, ZFrustum* pFrustum ) { BOOL b[4]; BOOL bInSphere; // 在边界球体内? bInSphere = pFrustum->IsInSphere( (D3DXVECTOR3*)(pHeightMap+m_nCenter), m_fRadius ); // 不在边界球体内的话，可以省略点单位的平截头体的测试，返回 if( !bInSphere ) return FRUSTUM_OUT; // 四叉数的4组边界平截头体的测试 b[0] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[0]) ); b[1] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[1]) ); b[2] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[2]) ); b[3] = pFrustum->IsIn( (D3DXVECTOR3*)(pHeightMap+m_nCorner[3]) ); // 4个都在平截头体内部 if( (b