/* ** Command & Conquer Renegade(tm) ** Copyright 2025 Electronic Arts Inc. ** ** This program is free software: you can redistribute it and/or modify ** it under the terms of the GNU General Public License as published by ** the Free Software Foundation, either version 3 of the License, or ** (at your option) any later version. ** ** This program is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. ** ** You should have received a copy of the GNU General Public License ** along with this program. If not, see . */ #include "sortingrenderer.h" #include "dx8vertexbuffer.h" #include "dx8indexbuffer.h" #include "dx8wrapper.h" #include "vertmaterial.h" #include "texture.h" #include "d3d8.h" #include "D3dx8math.h" #include "statistics.h" #include bool SortingRendererClass::_EnableTriangleDraw=true; struct ShortVectorIStruct { unsigned short i; unsigned short j; unsigned short k; ShortVectorIStruct(unsigned short i_,unsigned short j_,unsigned short k_) : i(i_),j(j_),k(k_) {} ShortVectorIStruct() {} }; struct TempIndexStruct { ShortVectorIStruct tri; unsigned short idx; TempIndexStruct() {} TempIndexStruct(const ShortVectorIStruct& tri_, unsigned short idx_) : tri(tri_), idx(idx_) { } }; // ---------------------------------------------------------------------------- // // InsertionSort (T* array, K *keys, int l, int r) // Performs insertion sort on array 'array' elements [l-r]. Uses values from array // 'keys' as sort keys. // // ---------------------------------------------------------------------------- template void InsertionSort ( T* array, // array to sort K* keys, // sort keys int l, // first item int r) // last item { for (int i = l+1; i < r; i++) { K v=keys[i]; T tv=array[i]; int j=i; while (keys[j-1] > v) { keys[j]=keys[j-1]; array[j]=array[j-1]; j--; if (j == l) break; }; keys[j]=v; array[j]=tv; } } // ---------------------------------------------------------------------------- // // QuickSort (T* array, K* a, int l, int r) // // Performs quicksort on array 'array'. Uses values from array 'keys' as sort keys. // // Once the length of the array to be sorted is less than 8, the routine calls // InsertionSort() to perform the actual sorting work. // // ---------------------------------------------------------------------------- template void QuickSort ( T* array, // array to sort K* keys, // sort keys int l, // first element int r) // last element { if (r-l <= 8) { InsertionSort(array,keys,l,r+1); return; } K t; K v=keys[r]; T ttemp; int i=l-1; int j=r; do { do { i++; } while (i0 && keys[j]>v); WWASSERT(j>=0); WWASSERT(i<=r); ttemp=array[i]; array[i]=array[j]; array[j]=ttemp; t=keys[i]; keys[i]=keys[j]; keys[j]=t; } while (j>i); array[j]=array[i]; array[i]=array[r]; array[r]=ttemp; keys[j]=keys[i]; keys[i]=keys[r]; keys[r]=t; if (i-1>l) QuickSort(array,keys,l,i-1); if (r>i+1) QuickSort(array,keys,i+1,r); } // ---------------------------------------------------------------------------- // // Sorts and array. Uses values from array 'keys' as sort keys. // // ---------------------------------------------------------------------------- template void Sort ( T* array, // array to sort K *keys, // sort keys int count) // array element count { bool do_insertion = false; if (count<=1) return; // only one element.. return.. int c=0; // count number of rise pairs int i; for (i = 1; i < count; i++) if (keys[i] >= keys[i-1]) c++; if (c+1 == count) return; // array already sorted if (c<50) do_insertion=true; // array smaller than 50 should use insertion sort if (c { RenderStateStruct sorting_state; SphereClass bounding_sphere; Vector3 transformed_center; unsigned short start_index; // First index used in the ib unsigned short polygon_count; // Polygon count to process (3 indices = one polygon) unsigned short min_vertex_index; // First index used in the vb unsigned short vertex_count; // Number of vertices used in vb }; static DLListClass sorted_list; static DLListClass clean_list; static unsigned total_sorting_vertices; static SortingNodeStruct* Get_Sorting_Struct() { SortingNodeStruct* state=clean_list.Head(); if (state) { state->Remove(); return state; } state=new SortingNodeStruct(); return state; } // ---------------------------------------------------------------------------- // // Temporary arrays for the sorting system // // ---------------------------------------------------------------------------- static float* vertex_z_array; static float* polygon_z_array; static unsigned * node_id_array; static unsigned * sorted_node_id_array; static ShortVectorIStruct* polygon_index_array; static unsigned vertex_z_array_count; static unsigned polygon_z_array_count; static unsigned node_id_array_count; static unsigned sorted_node_id_array_count; static unsigned polygon_index_array_count; TempIndexStruct* temp_index_array; unsigned temp_index_array_count; static TempIndexStruct* Get_Temp_Index_Array(unsigned count) { if (count>temp_index_array_count) { delete[] temp_index_array; temp_index_array=new TempIndexStruct[count]; temp_index_array_count=count; } return temp_index_array; } static float* Get_Vertex_Z_Array(unsigned count) { if (count>vertex_z_array_count) { delete[] vertex_z_array; vertex_z_array=new float[count]; vertex_z_array_count=count; } return vertex_z_array; } static float* Get_Polygon_Z_Array(unsigned count) { if (count>polygon_z_array_count) { delete[] polygon_z_array; polygon_z_array=new float[count]; polygon_z_array_count=count; } return polygon_z_array; } static unsigned * Get_Node_Id_Array(unsigned count) { if (count>node_id_array_count) { delete[] node_id_array; node_id_array=new unsigned[count]; node_id_array_count=count; } return node_id_array; } static unsigned * Get_Sorted_Node_Id_Array(unsigned count) { if (count>sorted_node_id_array_count) { delete[] sorted_node_id_array; sorted_node_id_array=new unsigned[count]; sorted_node_id_array_count=count; } return sorted_node_id_array; } static ShortVectorIStruct* Get_Polygon_Index_Array(unsigned count) { if (count>polygon_index_array_count) { delete[] polygon_index_array; polygon_index_array=new ShortVectorIStruct[count]; polygon_index_array_count=count; } return polygon_index_array; } // ---------------------------------------------------------------------------- // // Insert triangles to the sorting system. // // ---------------------------------------------------------------------------- void SortingRendererClass::Insert_Triangles( const SphereClass& bounding_sphere, unsigned short start_index, unsigned short polygon_count, unsigned short min_vertex_index, unsigned short vertex_count) { if (!WW3D::Is_Sorting_Enabled()) { DX8Wrapper::Draw_Triangles(start_index,polygon_count,min_vertex_index,vertex_count); return; } DX8_RECORD_SORTING_RENDER(polygon_count,vertex_count); SortingNodeStruct* state=Get_Sorting_Struct(); DX8Wrapper::Get_Render_State(state->sorting_state); WWASSERT( ((state->sorting_state.index_buffer_type==BUFFER_TYPE_SORTING || state->sorting_state.index_buffer_type==BUFFER_TYPE_DYNAMIC_SORTING) && (state->sorting_state.vertex_buffer_type==BUFFER_TYPE_SORTING || state->sorting_state.vertex_buffer_type==BUFFER_TYPE_DYNAMIC_SORTING))); state->bounding_sphere=bounding_sphere; state->start_index=start_index; state->polygon_count=polygon_count; state->min_vertex_index=min_vertex_index; state->vertex_count=vertex_count; SortingVertexBufferClass* vertex_buffer=static_cast(state->sorting_state.vertex_buffer); WWASSERT(vertex_buffer); WWASSERT(state->vertex_count<=vertex_buffer->Get_Vertex_Count()); // Transform the center point to view space for sorting D3DXMATRIX mtx=(D3DXMATRIX&)state->sorting_state.world*(D3DXMATRIX&)state->sorting_state.view; D3DXVECTOR3 vec=(D3DXVECTOR3&)state->bounding_sphere.Center; D3DXVECTOR4 transformed_vec; D3DXVec3Transform( &transformed_vec, &vec, &mtx); state->transformed_center=Vector3(transformed_vec[0],transformed_vec[1],transformed_vec[2]); SortingNodeStruct* node=sorted_list.Head(); while (node) { if (state->transformed_center.Z>node->transformed_center.Z) { if (sorted_list.Head()==sorted_list.Tail()) sorted_list.Add_Head(state); else state->Insert_Before(node); break; } node=node->Succ(); } if (!node) sorted_list.Add_Tail(state); #ifdef WWDEBUG unsigned short* indices=NULL; SortingIndexBufferClass* index_buffer=static_cast(state->sorting_state.index_buffer); WWASSERT(index_buffer); indices=index_buffer->index_buffer; WWASSERT(indices); indices+=state->start_index; indices+=state->sorting_state.iba_offset; for (int i=0;ipolygon_count;++i) { unsigned short idx1=indices[i*3]-state->min_vertex_index; unsigned short idx2=indices[i*3+1]-state->min_vertex_index; unsigned short idx3=indices[i*3+2]-state->min_vertex_index; WWASSERT(idx1vertex_count); WWASSERT(idx2vertex_count); WWASSERT(idx3vertex_count); } #endif } // ---------------------------------------------------------------------------- // // Insert triangles to the sorting system, with no bounding information. // // ---------------------------------------------------------------------------- void SortingRendererClass::Insert_Triangles( unsigned short start_index, unsigned short polygon_count, unsigned short min_vertex_index, unsigned short vertex_count) { SphereClass sphere(Vector3(0.0f,0.0f,0.0f),0.0f); Insert_Triangles(sphere,start_index,polygon_count,min_vertex_index,vertex_count); } // ---------------------------------------------------------------------------- // // Flush all sorting polygons. // // ---------------------------------------------------------------------------- void Release_Refs(SortingNodeStruct* state) { REF_PTR_RELEASE(state->sorting_state.vertex_buffer); REF_PTR_RELEASE(state->sorting_state.index_buffer); REF_PTR_RELEASE(state->sorting_state.material); for (unsigned i=0;isorting_state.Textures[i]); } } static unsigned overlapping_node_count; static unsigned overlapping_polygon_count; static unsigned overlapping_vertex_count; const unsigned MAX_OVERLAPPING_NODES=4096; static SortingNodeStruct* overlapping_nodes[MAX_OVERLAPPING_NODES]; // ---------------------------------------------------------------------------- void SortingRendererClass::Insert_To_Sorting_Pool(SortingNodeStruct* state) { if (overlapping_node_count>=MAX_OVERLAPPING_NODES) { Release_Refs(state); WWASSERT(0); return; } overlapping_nodes[overlapping_node_count]=state; overlapping_vertex_count+=state->vertex_count; overlapping_polygon_count+=state->polygon_count; overlapping_node_count++; } // ---------------------------------------------------------------------------- static void Apply_Render_State(RenderStateStruct& render_state) { /* state->sorting_state.shader.Apply(); */ DX8Wrapper::Set_Shader(render_state.shader); /* if (render_state.material) render_state.material->Apply(); */ DX8Wrapper::Set_Material(render_state.material); /* if (render_state.Textures[2]) render_state.Textures[2]->Apply(); if (render_state.Textures[3]) render_state.Textures[3]->Apply(); if (render_state.Textures[4]) render_state.Textures[4]->Apply(); if (render_state.Textures[5]) render_state.Textures[5]->Apply(); if (render_state.Textures[6]) render_state.Textures[6]->Apply(); if (render_state.Textures[7]) render_state.Textures[7]->Apply(); */ for (unsigned i=0;ivertex_count); VertexFormatXYZNDUV2* src_verts=NULL; SortingVertexBufferClass* vertex_buffer=static_cast(state->sorting_state.vertex_buffer); WWASSERT(vertex_buffer); src_verts=vertex_buffer->VertexBuffer; WWASSERT(src_verts); src_verts+=state->sorting_state.vba_offset; src_verts+=state->sorting_state.index_base_offset; src_verts+=state->min_vertex_index; D3DXMATRIX d3d_mtx=(D3DXMATRIX&)state->sorting_state.world*(D3DXMATRIX&)state->sorting_state.view; D3DXMatrixTranspose(&d3d_mtx,&d3d_mtx); const Matrix4& mtx=(const Matrix4&)d3d_mtx; for (unsigned i=0;ivertex_count;++i,++src_verts) { vertex_z_array[i] = (mtx[2][0] * src_verts->x + mtx[2][1] * src_verts->y + mtx[2][2] * src_verts->z + mtx[2][3]); // // If you have a crash in here and "dest_verts" points to illegal memory area, // it is because D3D is in illegal state, and the only known cure is rebooting. // This illegal state is usually caused by Quake3-engine powered games such as MOHAA. *dest_verts++=*src_verts; } unsigned short* indices=NULL; SortingIndexBufferClass* index_buffer=static_cast(state->sorting_state.index_buffer); WWASSERT(index_buffer); indices=index_buffer->index_buffer; WWASSERT(indices); indices+=state->start_index; indices+=state->sorting_state.iba_offset; for (i=0;ipolygon_count;++i) { unsigned short idx1=indices[i*3]-state->min_vertex_index; unsigned short idx2=indices[i*3+1]-state->min_vertex_index; unsigned short idx3=indices[i*3+2]-state->min_vertex_index; WWASSERT(idx1vertex_count); WWASSERT(idx2vertex_count); WWASSERT(idx3vertex_count); float z1=vertex_z_array[idx1]; float z2=vertex_z_array[idx2]; float z3=vertex_z_array[idx3]; float z=(z1+z2+z3)/3.0f; unsigned array_index=i+polygon_array_offset; WWASSERT(array_indexmin_vertex_index=vertex_array_offset; polygon_array_offset+=state->polygon_count; vertex_array_offset+=state->vertex_count; } } TempIndexStruct* tis=Get_Temp_Index_Array(overlapping_polygon_count); for (unsigned a=0;a(tis,polygon_z_array,overlapping_polygon_count); DynamicIBAccessClass dyn_ib_access(BUFFER_TYPE_DYNAMIC_DX8,overlapping_polygon_count*3); { DynamicIBAccessClass::WriteLockClass lock(&dyn_ib_access); ShortVectorIStruct* sorted_polygon_index_array=(ShortVectorIStruct*)lock.Get_Index_Array(); for (a=0;asorting_state); DX8Wrapper::Draw_Triangles( start_index*3, count_to_render, state->min_vertex_index, state->vertex_count); count_to_render=0; start_index=i; node_id=tis[i].idx; } count_to_render++; } // Render any remaining polygons... if (count_to_render) { SortingNodeStruct* state=overlapping_nodes[node_id]; Apply_Render_State(state->sorting_state); DX8Wrapper::Draw_Triangles( start_index*3, count_to_render, state->min_vertex_index, state->vertex_count); } // Release all references and return nodes back to the clean list for the frame... for (node_id=0;node_idRemove(); if ((state->sorting_state.index_buffer_type==BUFFER_TYPE_SORTING || state->sorting_state.index_buffer_type==BUFFER_TYPE_DYNAMIC_SORTING) && (state->sorting_state.vertex_buffer_type==BUFFER_TYPE_SORTING || state->sorting_state.vertex_buffer_type==BUFFER_TYPE_DYNAMIC_SORTING)) { Insert_To_Sorting_Pool(state); } else { DX8Wrapper::Set_Render_State(state->sorting_state); DX8Wrapper::Draw_Triangles(state->start_index,state->polygon_count,state->min_vertex_index,state->vertex_count); DX8Wrapper::Release_Render_State(); Release_Refs(state); clean_list.Add_Head(state); } } Flush_Sorting_Pool(); DX8Wrapper::Set_Index_Buffer(0,0); DX8Wrapper::Set_Vertex_Buffer(0); total_sorting_vertices=0; DynamicIBAccessClass::_Reset(false); DynamicVBAccessClass::_Reset(false); DX8Wrapper::Set_Transform(D3DTS_VIEW,old_view); DX8Wrapper::Set_Transform(D3DTS_WORLD,old_world); } // ---------------------------------------------------------------------------- void SortingRendererClass::Deinit() { SortingNodeStruct *head = NULL; // // Flush the sorted list // while ((head = sorted_list.Head ()) != NULL) { sorted_list.Remove_Head (); delete head; } // // Flush the clean list // while ((head = clean_list.Head ()) != NULL) { clean_list.Remove_Head (); delete head; } delete[] vertex_z_array; vertex_z_array=NULL; vertex_z_array_count=0; delete[] polygon_z_array; polygon_z_array=NULL; polygon_z_array_count=0; delete[] node_id_array; node_id_array=NULL; node_id_array_count=0; delete[] sorted_node_id_array; sorted_node_id_array=NULL; sorted_node_id_array_count=0; delete[] polygon_index_array; polygon_index_array=NULL; polygon_index_array_count=0; delete[] temp_index_array; temp_index_array=NULL; temp_index_array_count=0; }