Portfolio
日本語版はここ 1. Door Placement Optimization Based on Flow Simulation | | Highlights Developed a door placement optimization program in Python for floor plan optimization Built a 2D navigation mesh (half-edge mesh, A* pathfinding, funnel algorithm) from scratch to simulate large-scale pedestrian flow Designed a runtime optimization system using dynamic mesh split/merge operations and history tracking Applied Data-Oriented Design (DOD) for high-speed processing Demo Results Challenges ▶ Dynamic Mesh Processing Relevant Code: u_geometry.py, g_mesh.py, s_door_system.py Implemented two basic operations on the half–edge structure: Splitting and **merging edges**. Maintaining the structure and preserving original mesh info during updates was critical. Use of Half–edge Structure: Embedded optimization-friendly info in each edge (e.g., face, opposite vertex). Assigned IDs to geometry for easier management and debug drawing. History Functionality: Enabled retention of original edges through sequences of updates. Introduced history tracking to monitor geometry changes. History stored initial edge and position (0–1) to manage updates. 🔼 In debug mode, the door component dynamically moves clockwise along edges, while the mesh is **split/merged**, yet the initial geometry is preserved. Noteworthy Features ▶ Navigation Mesh Implementation Relevant Code: u_cdt.py, u_path_finding.py, g_navmesh.py Implemented a custom navigation mesh from scratch to ensure flexibility. This involved mesh construction, A\* search, and the funnel algorithm—all with technical challenges. In particular, the funnel algorithm had many edge cases, making debugging difficult. Implementation Steps: 2D Mesh Construction Used Python bindings for CDT (Constrained Delaunay Triangulation). Converted resulting mesh into a half-edge structure and annotated edges with types and flags to enable efficient subsequent optimization. A* Pathfinding Found shortest path through triangles (faces) on the mesh. Funnel Algorithm Used to calculate optimal movement path based on the triangle route. ▶ Runtime Optimization Algorithm Relevant Code: u*loader.py, s*\*\*\*.py, o_optimizer.py, f_layout.py This program aims to optimize floor layouts considering flow lines by simulating human movement from sampling points. The main goal is to optimize door positions by minimizing the average travel distance as a loss function. Optimization Procedure: Load Initial Settings Door setup, room connection requirements, and optimization parameters are described in a TOML file and loaded. The Flood Algorithm detects enclosed regions on the mesh and auto-generates room connectivity. Optimization Process Initial door positions are auto-generated based on connection rules. Then, door positions are dynamically adjusted using the MCMC (Markov Chain Monte Carlo) algorithm. Finalize Optimal Configuration & Manage History Once optimal door positions are determined, the mesh data is updated to reflect the result. Changes are tracked using the history management system to maintain optimal layouts. Presentation Slides Slides for Master’s Thesis Presentation (Revised) ...