/* ** 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 . */ /*********************************************************************************************** *** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S *** *********************************************************************************************** * * * Project Name : LevelEdit * * * * $Archive:: /Commando/Code/wwphys/floodfillgrid.cpp $* * * * Author:: Patrick Smith * * * * $Modtime:: 6/16/00 11:51a $* * * * $Revision:: 3 $* * * *---------------------------------------------------------------------------------------------* * Functions: * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ #include "floodfillgrid.h" //#include "utils.h" #include "aabox.h" #include "colmath.h" #include "colmathaabox.h" /////////////////////////////////////////////////////////////////////// // // FloodfillGridClass // /////////////////////////////////////////////////////////////////////// FloodfillGridClass::FloodfillGridClass (void) : m_Grid (NULL), m_BoxExtent (0, 0, 0), m_CellSize (0, 0), m_CellsX (0), m_CellsY (0), m_WorldMin (0, 0), m_WorldMax (0, 0) { return ; } /////////////////////////////////////////////////////////////////////// // // ~FloodfillGridClass // /////////////////////////////////////////////////////////////////////// FloodfillGridClass::~FloodfillGridClass (void) { Reset (); return ; } /////////////////////////////////////////////////////////////////////// // // Reset // /////////////////////////////////////////////////////////////////////// void FloodfillGridClass::Reset (void) { if (m_Grid != NULL) { delete [] m_Grid; m_Grid = NULL; } m_CellsX = 0; m_CellsY = 0; m_CellSize.X = 0; m_CellSize.Y = 0; return ; } /////////////////////////////////////////////////////////////////////// // // Initialize // /////////////////////////////////////////////////////////////////////// void FloodfillGridClass::Initialize ( const Vector3 &box_extents, const Vector3 &min_extents, const Vector3 &max_extents ) { Reset (); m_BoxExtent = box_extents; m_WorldMin.X = min_extents.X; m_WorldMin.Y = min_extents.Y; m_WorldMax.X = max_extents.X; m_WorldMax.Y = max_extents.Y; // // Modify the min and max so they are multiples of the box extents // Vector3 box_size = box_extents * 2.0F; m_WorldMin.X = (int(m_WorldMin.X / box_size.X) * box_size.X) - box_extents.X; m_WorldMin.Y = (int(m_WorldMin.Y / box_size.Y) * box_size.Y) - box_extents.Y; m_WorldMax.X = (int(m_WorldMax.X / box_size.X) * box_size.X) + box_extents.X; m_WorldMax.Y = (int(m_WorldMax.Y / box_size.Y) * box_size.Y) + box_extents.Y; // // Calcuate the grid dimensions // m_CellSize.X = box_extents.X * 32; m_CellSize.Y = box_extents.Y * 32; m_CellsX = ((m_WorldMax.X - m_WorldMin.X) / m_CellSize.X) + 1; m_CellsY = ((m_WorldMax.Y - m_WorldMin.Y) / m_CellSize.Y) + 1; // // Allocate the grid // m_Grid = new FloodfillBoxClass *[m_CellsX * m_CellsY]; ::memset (m_Grid, 0, sizeof (FloodfillBoxClass *) * m_CellsX * m_CellsY); return ; } /////////////////////////////////////////////////////////////////////// // // Collect_Boxes // /////////////////////////////////////////////////////////////////////// void FloodfillGridClass::Collect_Boxes (const AABoxClass &vol) { int min_cell_x = 0; int min_cell_y = 0; int max_cell_x = 0; int max_cell_y = 0; Point_To_Cell ((vol.Center - vol.Extent), &min_cell_x, &min_cell_y); Point_To_Cell ((vol.Center + vol.Extent), &max_cell_x, &max_cell_y); AABoxClass bounding_box; bounding_box.Extent = m_BoxExtent; m_CollectionList.Delete_All (); // // Loop over all the cells this volume touches // for (int cell_y = min_cell_y; cell_y <= max_cell_y; cell_y ++) { for (int cell_x = min_cell_x; cell_x <= max_cell_x; cell_x ++) { // // Loop over all the objects in this cell // FloodfillBoxClass *curr_box = m_Grid[cell_y * m_CellsX + cell_x]; for (; curr_box != NULL; curr_box = curr_box->Get_Grid_Link ()) { bounding_box.Center = curr_box->Get_Position (); // // Does this box overlap the collection volume? // if (CollisionMath::Overlap_Test (vol, bounding_box) != CollisionMath::OUTSIDE) { m_CollectionList.Add (curr_box); } } } } return ; } /////////////////////////////////////////////////////////////////////// // // Find_Box // /////////////////////////////////////////////////////////////////////// FloodfillBoxClass * FloodfillGridClass::Find_Box (const Vector3 &pos) { int index = Get_Cell_Index (pos); FloodfillBoxClass *box = NULL; AABoxClass bounding_box; bounding_box.Extent = m_BoxExtent; // // Loop over all the objects in this cell (looking for one inside the given point) // for ( FloodfillBoxClass *curr_box = m_Grid[index]; curr_box != NULL && box == NULL; curr_box = curr_box->Get_Grid_Link ()) { bounding_box.Center = curr_box->Get_Position (); // // Is the point inside this box? // if ( (WWMath::Fabs(pos.X - bounding_box.Center.X) <= bounding_box.Extent.X) && (WWMath::Fabs(pos.Y - bounding_box.Center.Y) <= bounding_box.Extent.Y) && (WWMath::Fabs(pos.Z - bounding_box.Center.Z) <= bounding_box.Extent.Z)) { box = curr_box; } } return box; } /////////////////////////////////////////////////////////////////////// // // Convert_To_AABox - converts a floodfill box into an AABox // /////////////////////////////////////////////////////////////////////// AABoxClass FloodfillGridClass::Convert_To_AABox(FloodfillBoxClass * floodbox) { return AABoxClass(floodbox->Get_Position(),m_BoxExtent); } /////////////////////////////////////////////////////////////////////// // // Compute_Box_Count - counts the number of boxes that overlap into // the specified AABox // /////////////////////////////////////////////////////////////////////// int FloodfillGridClass::Compute_Box_Count(const AABoxClass & vol) { int min_cell_x = 0; int min_cell_y = 0; int max_cell_x = 0; int max_cell_y = 0; Point_To_Cell ((vol.Center - vol.Extent), &min_cell_x, &min_cell_y); Point_To_Cell ((vol.Center + vol.Extent), &max_cell_x, &max_cell_y); AABoxClass bounding_box; bounding_box.Extent = m_BoxExtent; int count = 0; // // Loop over all the cells this volume touches // for (int cell_y = min_cell_y; cell_y <= max_cell_y; cell_y ++) { for (int cell_x = min_cell_x; cell_x <= max_cell_x; cell_x ++) { // // Loop over all the objects in this cell // FloodfillBoxClass *curr_box = m_Grid[cell_y * m_CellsX + cell_x]; for (; curr_box != NULL; curr_box = curr_box->Get_Grid_Link ()) { bounding_box.Center = curr_box->Get_Position (); // // Does this box overlap the collection volume? // if (CollisionMath::Overlap_Test (vol, bounding_box) != CollisionMath::OUTSIDE) { count++; } } } } return count; }