Adaptative Octree Algorithm for 3D volumetric representation of spheres using spatial enumeration
I achieved this during the course named "Geometrical Modelisation". We most of the time work on rendering shapes and models in 3D and then apply algorithm to them. It can range from calculating vertices, triangles and normals to render a model, to mesh simplification and subdivision.
GitHub repository of the project
Bounding Boxes
This method generates a bounding box for a given sphere in 3D space. A bounding box is the smallest axis-aligned rectangular box that completely encloses the sphere, useful for optimizing collision detection and spatial queries in 3D applications. The method takes a Sphere object as input, which includes the sphere'ws center (sphere.position) and its radius (sphere.radius).
How It Works
To calculate the bounding box, the method determines two key points: the minimum and maximum corners of the box. The minimum corner is calculated by subtracting the sphere's radius from its center in all directions, ensuring the corner lies one radius below the center. Similarly, the maximum corner is calculated by adding the radius to the center, ensuring it extends one radius above. These calculations provide the bounding box's exact dimensions, tightly enclosing the sphere.
The function constructs a BoundingBox object using these corners and returns it. In practical applications, this bounding box can significantly optimize performance. For example, it simplifies collision detection by allowing initial checks with a box rather than performing complex sphere-object calculations. Additionally, it is useful for spatial partitioning, grouping objects into manageable regions for faster processing in rendering or physics simulations.
Generating First X Cubes
The process is divided into two methods: GenerateGlobalRepresentation and GenerateSphere. This code is part of a system for generating 3D representations of spheres within defined bounding boxes, using smaller cubes to approximate their volume. The primary purpose is to efficiently visualize or process intersections, unions, or other spatial relationships between spheres and bounding volumes.
GenerateGlobalRepresentation acts as the entry point for the system. It iterates through a predefined number of spheres (nOS) and generates individual representations for each one. The method calls GenerateSphere, passing both the sphere and its corresponding bounding box to perform the detailed calculations and cube generation.
GenerateSphere is responsible for generating the 3D cube representation for a specific sphere. It begins by calculating the size of each cube (referred to as step) by dividing the width of the bounding box by a resolution value. This ensures the cubes are appropriately sized and distributed within the bounding volume.
The method then performs a triple nested loop to iterate through all possible positions within the bounding box grid. For each grid position, it calculates a Vector3 representing the current cube's location. Using this vector, the method evaluates whether various corners of the cube, as well as its center, intersect with the sphere. These checks are crucial for determining if the cube lies entirely within the sphere, partially intersects, or is outside.
If all corners and the center of the cube are within the sphere, the method creates a visual cube using the Instantiate function. The cube is centered at the current position, adjusted by half the cube's size (step / 2) to align it correctly, and is scaled to match the cube's dimensions. For more complex cases involving unions or intersections of multiple spheres, the method leverages additional logic to process these relationships.
In cases where only part of the cube intersects the sphere, the method recursively subdivides the cube into smaller parts by calling SphereDivision, enabling a finer level of detail and ensuring accurate representation of the sphere's boundary.
Recursive Cube Subdivision
The recursion begins with a cube defined by a Vector3 position and a size (step). The method evaluates whether the cube lies entirely within, partially overlaps, or is outside the sphere. Based on this evaluation, it either generates a cube or subdivides further into smaller cubes.
The method first checks if the current division has reached the maximum number of subdivisions. At this point, if the union flag is enabled, it evaluates whether the cube overlaps other geometries to avoid duplicate renderings. For unions and intersections, specialized processing is delegated to UnionSpheres or IntersectSpheres. If neither is required, the method generates a cube centered at the current position, scaled appropriately, and colored based on the recursion level (currentDivision).
If further subdivision is required, the cube is divided into eight smaller cubes by halving the size (step / 2) and iterating through all combinations of offsets (0 or newStep) for the x, y, and z axes. For each smaller cube, the method performs sphere intersection tests on its corners and center. This ensures accurate representation of the sphere's boundaries, even at finer resolutions.
The method also handles multiple spheres by incrementing a counter whenever a cube's center intersects with a sphere. This allows it to account for overlapping regions in union or intersection operations. When all corners and the center of a cube are within the sphere, a cube is generated or further divided depending on the current mode (union, intersect, or default rendering).
By recursively subdividing cubes and evaluating sphere intersections at each level, this method achieves high precision while minimizing redundant calculations. It dynamically adjusts detail based on the sphere's geometry and the current recursion depth, ensuring efficient and accurate representation.
Challenges and Solutions
One of the main challenges encountered in this implementation was avoiding overlapping cube renderings, especially at the edges of spheres where rounding errors or small gaps could occur. To solve this, a Physics.OverlapSphere check was introduced at the final recursion level to detect and prevent redundant cube generation. Another challenge was ensuring smooth and visually consistent transitions between intersecting spheres. This was addressed by dynamically adjusting the recursion depth and ensuring that intersections involved more than one sphere before proceeding with further subdivision.
Additionally, handling partial overlaps of cubes with spheres required precise testing of all cube corners and its center against the sphere. This was implemented by performing intersection tests at every recursive step, balancing performance with accuracy.
Skills Gained
This project provided valuable experience in designing and implementing recursive algorithms for spatial subdivision. It enhanced my understanding of 3D geometry and mathematical modeling, particularly in the context of sphere and cube interactions.
Through debugging and optimizing the subdivision logic, I developed strong skills in problem-solving and performance optimization. Moreover, the process of dynamically managing recursion depth and handling edge cases strengthened my proficiency in writing robust and scalable code for 3D environments. This experience also deepened my knowledge of graphics rendering pipelines and how spatial partitioning techniques can enhance real-time rendering and simulation efficiency.