**Homework 2**

Student name: Cédric Hölzl

Sciper number: 257844

Octree construction (50 pts)
============================

We store the following information for each octre node: 
* List of Triangles (inside a vector to be able to add elements easily), 
* List of ChildNodes pointers (inside a fixed size array since we have at most 8 of them), 
* Bounding box of the node 

This structures takes up 112 Bytes for each node, composed as follows: 
* List of Triangles: 24,
* List of ChildNodes: 8*8 = 64,
* Bounding Box: 24,

We could have used three pointers to have a smaller structure of only 24 bytes (3*8), but this would result in more memory overhead. Hence, we chose to use a bit larger stucture.

We collected the following statistics (max_depth=10 and triangle per leaf=8):
* Internal Nodes: 284'253, 
* Leaf Nodes: 1'989'772, 
* Triangles (accumulated from all leafs): 20'526'613, 
* Triangles Per Leaf: 10.3161,
* Construction Time: 1.0s


Ray traversal (25 pts)
======================

As implementation, we just use a queue, where we add recursivly nodes of our Octree, whenever the ray intersects them. If the node is a leaf, we check the intersection with the ray and only keep the closest intersection.

We collected the following statistic (image_size=24x24, samples_per_pixel=32):
* Render Time Default: 8.5min 
* Render Time Octree: 114.0ms (default size took us 4.8s to render)

We can see a speedup of over 4400%.


Improved ray traversal (25 pts)
===============================

From the previous implementation, we replaced the queue with a priority_queue using the distance to push/pop elements from it in the desired order.

We collected the following statistics:
* Render Time: 4.8s
* Render Time Improved: 4.1s

We can see a minor improvement (~16%)

Below you can see the difference between our render and the reference one, it is relativly clear that our changes provided the same results with better performances.

Surface normal visualization of the Ajax bust:
<div class="twentytwenty-container">
    <img src="ajax-normals-ref.png" alt="Reference">
    <img src="ajax-normals.png" alt="Mine">
</div>

Note: <a href="ajax-normals.exr">ajax-normals.exr</a>


Bonus: Improved Octree construction  (10 pts)
=============================================

From the initial version, we parallelized the child node construction up to a certain depth using `parallel_for`. Each internal node will run its 8 child node constructors in parallel.

We collected the following statistics:
* Construction Time: 1.0s
* Construction Time Improved: 422.0ms

We can see a major improvement (~200%).

Feedback
========

Time Spent Breakdown: 
* Designing: ~1h30
* Coding: ~5h (had some minor issues with tbb)
* Testing: ~3h (renders are slow and forgot to disable debug options)

I believed no further advice should have been needed, instructions were clear and helpfull. The difficult part of the assignment was understanding the structure of the provided code in order to know where to do what changes. Maybe having a small doc generate from the headers (doxygen) might improve workflow.

<!-- Slider -->
<script src="https://ajax.googleapis.com/ajax/libs/jquery/3.5.1/jquery.min.js"></script>
<script src="../resources/jquery.event.move.js"></script>
<script src="../resources/jquery.twentytwenty.js"></script>
<link href="../resources/offcanvas.css" rel="stylesheet">
<link href="../resources/twentytwenty.css" rel="stylesheet" type="text/css" />
<script>var markdeepOptions = {onLoad: function() {$(".twentytwenty-container").twentytwenty({default_offset_pct: 0.5, move_slider_on_hover: true});} };</script>
<!-- Markdeep: -->
<script src="https://morgan3d.github.io/markdeep/latest/markdeep.min.js?" charset="utf-8"></script>
<script>window.alreadyProcessedMarkdeep||(document.body.style.visibility="visible")</script>