CSG Result Analysis
Introduction
This notebook is a breakdown of results gathered from running tests on the implementation of the Combinatorial Geometry method in the OpenRT library. The following sections breakdown the way the tests were conducted and also the flow of the rest of this notebook.
The 3 Operations
By definition, constructive solid geometry is a method which allows to construct complex geometries using primitive operation and boolean set operations (Union, Difference, Intersection). Therefore, every test requires us to test each of these operations on the same exact load. In theory, the operation itself shouldn't have a drastic impact on the performance of the algorithm.
The 3 Algorithms
There are 3 variants of the CSG method implemented in OpenRT. The first is the naive and brute force implementation which we refer to as NaiCSG. The second is a variant that uses a Binary Space Partition tree in order to solve the visible surface problem but still naivly finds intersections inside the combinatorial geometry, which we will refer to as BinCSG. Lastly, we'll introduce our optimized algorithm which uses a binary space partition tree on the outside (solving the visible surface problem) and also inside each composite geometry in order to direct the rays towards the correct geometries, which we will refer to as OptiCSG. Every algorithm is checked for each operation - meaning a total of 9 simulations are conducted per test type.
The 3 Tests
We conduct 3 main tests. First, we check how the rendering time develops with respect to the complexity of the geometry. In this case, the complexity of the geometry is the number of polygons in the sphere meshes. The second tests are based on the reaction of the different algorithms to a different number of nested geometries while maitaining a relevantly similar viewport fill rate (how much of the image actually contains geometries). The third test gives us an idea of how the spatial distribution of the scene (how much of the viewport is actually filled) affects the times for each of the algorithms. This helps us grasp how much the view port fill percentage affects each of these algorithms individually; therefore, either confirming or denying our hypothesis.
Notebook Breakdown
There are a total of 4 sections (the first being this introduction). Section 2 focuses entirely on extracting data for each alogrithm and only comparing the time of the different operations. Section 3 is focused on processing the data and comparing the mean time of each algorithm to the other. The last section works on modeling the time complexities to close representations and finally drawing conclusion on the performance.
Hardware Specifications
All tests were ran on a Macbook Pro 13" 2017
- Processor: 2,3 GHz Dual-Core Intel Core i5
- Memory: 8 GB 2133 MHz LPDDR3
- Graphics Card: Intel Iris Plus Graphics 640 1536 MB
Geometry Complexity & Rendering Times
NaiCSG
The naive algorithm essentially brute-forces its way through the hidden surface problem. For each ray, it iterates over all geometries in the scene and picks the closest intersection. Therefore if a scene contains 100 geometries and we have a 2000x2000px image (not a lot by today standards). A total of 400.000.000 intersections will be checked before the image is finally rendered.
