Cycles: Implement unaligned nodes BVH builder

This is a special builder type which is allowed to orient nodes to
strands direction, hence minimizing their surface area in comparison
with axis-aligned nodes. Such nodes are much more efficient for hair
rendering.

Implementation of BVH builder is based on Embree, and generally idea
there is to calculate axis-aligned SAH and oriented SAH and if SAH
of oriented node is smaller than axis-aligned SAH we create unaligned
node.

We store both aligned and unaligned nodes in the same tree (which
seems to be different from what Embree is doing) so we don't have
any any extra calculations needed to set up hair ray for BVH
traversal, hence avoiding any possible negative effect of this new
BVH nodes type.

This new builder is currently not in use, still need to make BVH
traversal code aware of unaligned nodes.

1 files changed, 343 insertions, 93 deletions

diff --git a/intern/cycles/bvh/bvh.cpp b/intern/cycles/bvh/bvh.cpp
index ab4dbe814ab..e92526ac1c4 100644
--- a/intern/cycles/bvh/bvh.cpp
+++ b/intern/cycles/bvh/bvh.cpp
@@ -24,6 +24,7 @@
 #include "bvh_build.h"
 #include "bvh_node.h"
 #include "bvh_params.h"
+#include "bvh_unaligned.h"
 
 #include "util_debug.h"
 #include "util_foreach.h"
@@ -192,13 +193,13 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 {
 	/* The BVH's for instances are built separately, but for traversal all
 	 * BVH's are stored in global arrays. This function merges them into the
-	 * top level BVH, adjusting indexes and offsets where appropriate. */
-	bool use_qbvh = params.use_qbvh;
-	size_t nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
-	size_t nsize_leaf = (use_qbvh)? BVH_QNODE_LEAF_SIZE: BVH_NODE_LEAF_SIZE;
+	 * top level BVH, adjusting indexes and offsets where appropriate.
+	 */
+	const bool use_qbvh = params.use_qbvh;
 
-	/* adjust primitive index to point to the triangle in the global array, for
-	 * meshes with transform applied and already in the top level BVH */
+	/* Adjust primitive index to point to the triangle in the global array, for
+	 * meshes with transform applied and already in the top level BVH.
+	 */
 	for(size_t i = 0; i < pack.prim_index.size(); i++)
 		if(pack.prim_index[i] != -1) {
 			if(pack.prim_type[i] & PRIMITIVE_ALL_CURVE)
@@ -340,40 +341,51 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 		if(bvh->pack.leaf_nodes.size()) {
 			int4 *leaf_nodes_offset = &bvh->pack.leaf_nodes[0];
 			size_t leaf_nodes_offset_size = bvh->pack.leaf_nodes.size();
-			for(size_t i = 0, j = 0; i < leaf_nodes_offset_size; i+=nsize_leaf, j++) {
+			for(size_t i = 0, j = 0;
+			    i < leaf_nodes_offset_size;
+			    i+= BVH_NODE_LEAF_SIZE, j++)
+			{
 				int4 data = leaf_nodes_offset[i];
 				data.x += prim_offset;
 				data.y += prim_offset;
 				pack_leaf_nodes[pack_leaf_nodes_offset] = data;
-				for(int j = 1; j < nsize_leaf; ++j) {
+				for(int j = 1; j < BVH_NODE_LEAF_SIZE; ++j) {
 					pack_leaf_nodes[pack_leaf_nodes_offset + j] = leaf_nodes_offset[i + j];
 				}
-				pack_leaf_nodes_offset += nsize_leaf;
+				pack_leaf_nodes_offset += BVH_NODE_LEAF_SIZE;
 			}
 		}
 
 		if(bvh->pack.nodes.size()) {
-			/* For QBVH we're packing a child bbox into 6 float4,
-			 * and for regular BVH they're packed into 3 float4.
-			 */
-			const size_t nsize_bbox = (use_qbvh)? 7: 3;
 			int4 *bvh_nodes = &bvh->pack.nodes[0];
 			size_t bvh_nodes_size = bvh->pack.nodes.size();
 
-			for(size_t i = 0, j = 0; i < bvh_nodes_size; i+=nsize, j++) {
+			for(size_t i = 0, j = 0; i < bvh_nodes_size; j++) {
+				size_t nsize, nsize_bbox;
+				if(bvh_nodes[i].x & PATH_RAY_NODE_UNALIGNED) {
+					nsize = use_qbvh
+					            ? BVH_UNALIGNED_QNODE_SIZE
+					            : BVH_UNALIGNED_NODE_SIZE;
+					nsize_bbox = (use_qbvh)? 13: 0;
+				}
+				else {
+					nsize = (use_qbvh)? BVH_QNODE_SIZE: BVH_NODE_SIZE;
+					nsize_bbox = (use_qbvh)? 7: 0;
+				}
+
 				memcpy(pack_nodes + pack_nodes_offset,
 				       bvh_nodes + i,
 				       nsize_bbox*sizeof(int4));
 
-				/* modify offsets into arrays */
+				/* Modify offsets into arrays */
 				int4 data = bvh_nodes[i + nsize_bbox];
 
-				data.x += (data.x < 0)? -noffset_leaf: noffset;
-				data.y += (data.y < 0)? -noffset_leaf: noffset;
+				data.z += (data.z < 0)? -noffset_leaf: noffset;
+				data.w += (data.w < 0)? -noffset_leaf: noffset;
 
 				if(use_qbvh) {
-					data.z += (data.z < 0)? -noffset_leaf: noffset;
-					data.w += (data.w < 0)? -noffset_leaf: noffset;
+					data.x += (data.x < 0)? -noffset_leaf: noffset;
+					data.y += (data.y < 0)? -noffset_leaf: noffset;
 				}
 
 				pack_nodes[pack_nodes_offset + nsize_bbox] = data;
@@ -386,6 +398,7 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 				       sizeof(int4) * (nsize - (nsize_bbox+1)));
 
 				pack_nodes_offset += nsize;
+				i += nsize;
 			}
 		}
 
@@ -397,12 +410,20 @@ void BVH::pack_instances(size_t nodes_size, size_t leaf_nodes_size)
 
 /* Regular BVH */
 
+static bool node_bvh_is_unaligned(const BVHNode *node)
+{
+	const BVHNode *node0 = node->get_child(0),
+	              *node1 = node->get_child(1);
+	return node0->is_unaligned() || node1->is_unaligned();
+}
+
 RegularBVH::RegularBVH(const BVHParams& params_, const vector<Object*>& objects_)
 : BVH(params_, objects_)
 {
 }
 
-void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
+void RegularBVH::pack_leaf(const BVHStackEntry& e,
+                           const LeafNode *leaf)
 {
 	float4 data[BVH_NODE_LEAF_SIZE];
 	memset(data, 0, sizeof(data));
@@ -424,41 +445,112 @@ void RegularBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 	memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_NODE_LEAF_SIZE);
 }
 
-void RegularBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry& e0, const BVHStackEntry& e1)
+void RegularBVH::pack_inner(const BVHStackEntry& e,
+                            const BVHStackEntry& e0,
+                            const BVHStackEntry& e1)
+{
+	if (e0.node->is_unaligned() || e1.node->is_unaligned()) {
+		pack_unaligned_inner(e, e0, e1);
+	} else {
+		pack_aligned_inner(e, e0, e1);
+	}
+}
+
+void RegularBVH::pack_aligned_inner(const BVHStackEntry& e,
+                                    const BVHStackEntry& e0,
+                                    const BVHStackEntry& e1)
 {
-	pack_node(e.idx, e0.node->m_bounds, e1.node->m_bounds, e0.encodeIdx(), e1.encodeIdx(), e0.node->m_visibility, e1.node->m_visibility);
+	pack_aligned_node(e.idx,
+	                  e0.node->m_bounds, e1.node->m_bounds,
+	                  e0.encodeIdx(), e1.encodeIdx(),
+	                  e0.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED,
+	                  e1.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED);
 }
 
-void RegularBVH::pack_node(int idx, const BoundBox& b0, const BoundBox& b1, int c0, int c1, uint visibility0, uint visibility1)
+void RegularBVH::pack_aligned_node(int idx,
+                                   const BoundBox& b0,
+                                   const BoundBox& b1,
+                                   int c0, int c1,
+                                   uint visibility0, uint visibility1)
 {
 	int4 data[BVH_NODE_SIZE] =
 	{
+		make_int4(visibility0, visibility1, c0, c1),
 		make_int4(__float_as_int(b0.min.x), __float_as_int(b1.min.x), __float_as_int(b0.max.x), __float_as_int(b1.max.x)),
 		make_int4(__float_as_int(b0.min.y), __float_as_int(b1.min.y), __float_as_int(b0.max.y), __float_as_int(b1.max.y)),
 		make_int4(__float_as_int(b0.min.z), __float_as_int(b1.min.z), __float_as_int(b0.max.z), __float_as_int(b1.max.z)),
-		make_int4(c0, c1, visibility0, visibility1)
 	};
 
 	memcpy(&pack.nodes[idx], data, sizeof(int4)*BVH_NODE_SIZE);
 }
 
-void RegularBVH::pack_nodes(const BVHNode *root)
+void RegularBVH::pack_unaligned_inner(const BVHStackEntry& e,
+                                      const BVHStackEntry& e0,
+                                      const BVHStackEntry& e1)
 {
-	size_t tot_node_size = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
-	size_t leaf_node_size = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
-	size_t node_size = tot_node_size - leaf_node_size;
+	pack_unaligned_node(e.idx,
+	                    e0.node->get_aligned_space(),
+	                    e1.node->get_aligned_space(),
+	                    e0.node->m_bounds,
+	                    e1.node->m_bounds,
+	                    e0.encodeIdx(), e1.encodeIdx(),
+	                    e0.node->m_visibility, e1.node->m_visibility);
+}
 
-	/* resize arrays */
-	pack.nodes.clear();
+void RegularBVH::pack_unaligned_node(int idx,
+                                     const Transform& aligned_space0,
+                                     const Transform& aligned_space1,
+                                     const BoundBox& bounds0,
+                                     const BoundBox& bounds1,
+                                     int c0, int c1,
+                                     uint visibility0, uint visibility1)
+{
+	float4 data[BVH_UNALIGNED_NODE_SIZE];
+	Transform space0 = BVHUnaligned::compute_node_transform(bounds0,
+	                                                        aligned_space0);
+	Transform space1 = BVHUnaligned::compute_node_transform(bounds1,
+	                                                        aligned_space1);
+	data[0] = make_float4(__int_as_float(visibility0 | PATH_RAY_NODE_UNALIGNED),
+	                      __int_as_float(visibility1 | PATH_RAY_NODE_UNALIGNED),
+	                      __int_as_float(c0),
+	                      __int_as_float(c1));
+
+	data[1] = space0.x;
+	data[2] = space0.y;
+	data[3] = space0.z;
+	data[4] = space1.x;
+	data[5] = space1.y;
+	data[6] = space1.z;
+
+	memcpy(&pack.nodes[idx], data, sizeof(float4)*BVH_UNALIGNED_NODE_SIZE);
+}
 
-	/* for top level BVH, first merge existing BVH's so we know the offsets */
+void RegularBVH::pack_nodes(const BVHNode *root)
+{
+	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_NODE_COUNT);
+	const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
+	assert(num_leaf_nodes <= num_nodes);
+	const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
+	size_t node_size;
+	if(params.use_unaligned_nodes) {
+		const size_t num_unaligned_nodes =
+		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_COUNT);
+		node_size = (num_unaligned_nodes * BVH_UNALIGNED_NODE_SIZE) +
+		            (num_inner_nodes - num_unaligned_nodes) * BVH_NODE_SIZE;
+	}
+	else {
+		node_size = num_inner_nodes * BVH_NODE_SIZE;
+	}
+	/* Resize arrays */
+	pack.nodes.clear();
+	pack.leaf_nodes.clear();
+	/* For top level BVH, first merge existing BVH's so we know the offsets. */
 	if(params.top_level) {
-		pack_instances(node_size*BVH_NODE_SIZE,
-		               leaf_node_size*BVH_NODE_LEAF_SIZE);
+		pack_instances(node_size, num_leaf_nodes*BVH_NODE_LEAF_SIZE);
 	}
 	else {
-		pack.nodes.resize(node_size*BVH_NODE_SIZE);
-		pack.leaf_nodes.resize(leaf_node_size*BVH_NODE_LEAF_SIZE);
+		pack.nodes.resize(node_size);
+		pack.leaf_nodes.resize(num_leaf_nodes*BVH_NODE_LEAF_SIZE);
 	}
 
 	int nextNodeIdx = 0, nextLeafNodeIdx = 0;
@@ -470,7 +562,9 @@ void RegularBVH::pack_nodes(const BVHNode *root)
 	}
 	else {
 		stack.push_back(BVHStackEntry(root, nextNodeIdx));
-		nextNodeIdx += BVH_NODE_SIZE;
+		nextNodeIdx += node_bvh_is_unaligned(root)
+		                       ? BVH_UNALIGNED_NODE_SIZE
+		                       : BVH_NODE_SIZE;
 	}
 
 	while(stack.size()) {
@@ -479,7 +573,7 @@ void RegularBVH::pack_nodes(const BVHNode *root)
 
 		if(e.node->is_leaf()) {
 			/* leaf node */
-			const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
+			const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
 			pack_leaf(e, leaf);
 		}
 		else {
@@ -491,7 +585,9 @@ void RegularBVH::pack_nodes(const BVHNode *root)
 				}
 				else {
 					idx[i] = nextNodeIdx;
-					nextNodeIdx += BVH_NODE_SIZE;
+					nextNodeIdx += node_bvh_is_unaligned(e.node->get_child(i))
+					                       ? BVH_UNALIGNED_NODE_SIZE
+					                       : BVH_NODE_SIZE;
 				}
 			}
 
@@ -501,7 +597,7 @@ void RegularBVH::pack_nodes(const BVHNode *root)
 			pack_inner(e, stack[stack.size()-2], stack[stack.size()-1]);
 		}
 	}
-
+	assert(node_size == nextNodeIdx);
 	/* root index to start traversal at, to handle case of single leaf node */
 	pack.root_index = (root->is_leaf())? -1: 0;
 }
@@ -592,14 +688,14 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
 		leaf_data[0].y = __int_as_float(c1);
 		leaf_data[0].z = __uint_as_float(visibility);
 		leaf_data[0].w = __uint_as_float(data[0].w);
-		memcpy(&pack.leaf_nodes[idx],
+		memcpy(&pack.leaf_nodes[idx * BVH_NODE_LEAF_SIZE],
 		       leaf_data,
 		       sizeof(float4)*BVH_NODE_LEAF_SIZE);
 	}
 	else {
 		int4 *data = &pack.nodes[idx];
-		int c0 = data[3].x;
-		int c1 = data[3].y;
+		int c0 = data[0].z;
+		int c1 = data[0].w;
 		/* refit inner node, set bbox from children */
 		BoundBox bbox0 = BoundBox::empty, bbox1 = BoundBox::empty;
 		uint visibility0 = 0, visibility1 = 0;
@@ -607,7 +703,7 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
 		refit_node((c0 < 0)? -c0-1: c0, (c0 < 0), bbox0, visibility0);
 		refit_node((c1 < 0)? -c1-1: c1, (c1 < 0), bbox1, visibility1);
 
-		pack_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
+		pack_aligned_node(idx, bbox0, bbox1, c0, c1, visibility0, visibility1);
 
 		bbox.grow(bbox0);
 		bbox.grow(bbox1);
@@ -617,6 +713,33 @@ void RegularBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility
 
 /* QBVH */
 
+/* Can we avoid this somehow or make more generic?
+ *
+ * Perhaps we can merge nodes in actual tree and make our
+ * life easier all over the place.
+ */
+static bool node_qbvh_is_unaligned(const BVHNode *node)
+{
+	const BVHNode *node0 = node->get_child(0),
+	              *node1 = node->get_child(1);
+	bool has_unaligned = false;
+	if(node0->is_leaf()) {
+		has_unaligned |= node0->is_unaligned();
+	}
+	else {
+		has_unaligned |= node0->get_child(0)->is_unaligned();
+		has_unaligned |= node0->get_child(1)->is_unaligned();
+	}
+	if(node1->is_leaf()) {
+		has_unaligned |= node1->is_unaligned();
+	}
+	else {
+		has_unaligned |= node1->get_child(0)->is_unaligned();
+		has_unaligned |= node1->get_child(1)->is_unaligned();
+	}
+	return has_unaligned;
+}
+
 QBVH::QBVH(const BVHParams& params_, const vector<Object*>& objects_)
 : BVH(params_, objects_)
 {
@@ -645,11 +768,42 @@ void QBVH::pack_leaf(const BVHStackEntry& e, const LeafNode *leaf)
 	memcpy(&pack.leaf_nodes[e.idx], data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
 }
 
-void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
+void QBVH::pack_inner(const BVHStackEntry& e,
+                      const BVHStackEntry *en,
+                      int num)
+{
+	bool has_unaligned = false;
+	/* Check whether we have to create unaligned node or all nodes are aligned
+	 * and we can cut some corner here.
+	 */
+	if(params.use_unaligned_nodes) {
+		for(int i = 0; i < num; i++) {
+			if(en[i].node->is_unaligned()) {
+				has_unaligned = true;
+				break;
+			}
+		}
+	}
+	if(has_unaligned) {
+		/* There's no unaligned children, pack into AABB node. */
+		pack_unaligned_inner(e, en, num);
+	}
+	else {
+		/* Create unaligned node with orientation transform for each of the
+		 * children.
+		 */
+		pack_aligned_inner(e, en, num);
+	}
+}
+
+void QBVH::pack_aligned_inner(const BVHStackEntry& e,
+                              const BVHStackEntry *en,
+                              int num)
 {
 	float4 data[BVH_QNODE_SIZE];
+	memset(data, 0, sizeof(data));
 
-	data[0].x = __uint_as_float(e.node->m_visibility);
+	data[0].x = __uint_as_float(e.node->m_visibility & ~PATH_RAY_NODE_UNALIGNED);
 	for(int i = 0; i < num; i++) {
 		float3 bb_min = en[i].node->m_bounds.min;
 		float3 bb_max = en[i].node->m_bounds.max;
@@ -683,26 +837,81 @@ void QBVH::pack_inner(const BVHStackEntry& e, const BVHStackEntry *en, int num)
 	memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_QNODE_SIZE);
 }
 
+void QBVH::pack_unaligned_inner(const BVHStackEntry& e,
+                                const BVHStackEntry *en,
+                                int num)
+{
+	float4 data[BVH_UNALIGNED_QNODE_SIZE];
+	memset(data, 0, sizeof(data));
+
+	data[0].x = __uint_as_float(e.node->m_visibility | PATH_RAY_NODE_UNALIGNED);
+
+	for(int i = 0; i < num; i++) {
+		Transform space = BVHUnaligned::compute_node_transform(
+		        en[i].node->m_bounds,
+		        en[i].node->get_aligned_space());
+
+		data[1][i] = space.x.x;
+		data[2][i] = space.x.y;
+		data[3][i] = space.x.z;
+
+		data[4][i] = space.y.x;
+		data[5][i] = space.y.y;
+		data[6][i] = space.y.z;
+
+		data[7][i] = space.z.x;
+		data[8][i] = space.z.y;
+		data[9][i] = space.z.z;
+
+		data[10][i] = space.x.w;
+		data[11][i] = space.y.w;
+		data[12][i] = space.z.w;
+
+		data[13][i] = __int_as_float(en[i].encodeIdx());
+	}
+
+	for(int i = num; i < 4; i++) {
+		/* We store BB which would never be recorded as intersection
+		 * so kernel might safely assume there are always 4 child nodes.
+		 */
+		for(int j = 1; j < 13; ++j) {
+			data[j][i] = 0.0f;
+		}
+		data[13][i] = __int_as_float(0);
+	}
+
+	memcpy(&pack.nodes[e.idx], data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
+}
+
 /* Quad SIMD Nodes */
 
 void QBVH::pack_nodes(const BVHNode *root)
 {
-	size_t tot_node_size = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
-	size_t leaf_node_size = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
-	size_t node_size = tot_node_size - leaf_node_size;
-
-	/* resize arrays */
+	/* Calculate size of the arrays required. */
+	const size_t num_nodes = root->getSubtreeSize(BVH_STAT_QNODE_COUNT);
+	const size_t num_leaf_nodes = root->getSubtreeSize(BVH_STAT_LEAF_COUNT);
+	assert(num_leaf_nodes <= num_nodes);
+	const size_t num_inner_nodes = num_nodes - num_leaf_nodes;
+	size_t node_size;
+	if(params.use_unaligned_nodes) {
+		const size_t num_unaligned_nodes =
+		        root->getSubtreeSize(BVH_STAT_UNALIGNED_INNER_QNODE_COUNT);
+		node_size = (num_unaligned_nodes * BVH_UNALIGNED_QNODE_SIZE) +
+		            (num_inner_nodes - num_unaligned_nodes) * BVH_QNODE_SIZE;
+	}
+	else {
+		node_size = num_inner_nodes * BVH_QNODE_SIZE;
+	}
+	/* Resize arrays. */
 	pack.nodes.clear();
 	pack.leaf_nodes.clear();
-
-	/* for top level BVH, first merge existing BVH's so we know the offsets */
+	/* For top level BVH, first merge existing BVH's so we know the offsets. */
 	if(params.top_level) {
-		pack_instances(node_size*BVH_QNODE_SIZE,
-		               leaf_node_size*BVH_QNODE_LEAF_SIZE);
+		pack_instances(node_size, num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
 	}
 	else {
-		pack.nodes.resize(node_size*BVH_QNODE_SIZE);
-		pack.leaf_nodes.resize(leaf_node_size*BVH_QNODE_LEAF_SIZE);
+		pack.nodes.resize(node_size);
+		pack.leaf_nodes.resize(num_leaf_nodes*BVH_QNODE_LEAF_SIZE);
 	}
 
 	int nextNodeIdx = 0, nextLeafNodeIdx = 0;
@@ -714,7 +923,9 @@ void QBVH::pack_nodes(const BVHNode *root)
 	}
 	else {
 		stack.push_back(BVHStackEntry(root, nextNodeIdx));
-		nextNodeIdx += BVH_QNODE_SIZE;
+		nextNodeIdx += node_qbvh_is_unaligned(root)
+		                       ? BVH_UNALIGNED_QNODE_SIZE
+		                       : BVH_QNODE_SIZE;
 	}
 
 	while(stack.size()) {
@@ -723,19 +934,17 @@ void QBVH::pack_nodes(const BVHNode *root)
 
 		if(e.node->is_leaf()) {
 			/* leaf node */
-			const LeafNode* leaf = reinterpret_cast<const LeafNode*>(e.node);
+			const LeafNode *leaf = reinterpret_cast<const LeafNode*>(e.node);
 			pack_leaf(e, leaf);
 		}
 		else {
-			/* inner node */
+			/* Inner node. */
 			const BVHNode *node = e.node;
 			const BVHNode *node0 = node->get_child(0);
 			const BVHNode *node1 = node->get_child(1);
-
-			/* collect nodes */
+			/* Collect nodes. */
 			const BVHNode *nodes[4];
 			int numnodes = 0;
-
 			if(node0->is_leaf()) {
 				nodes[numnodes++] = node0;
 			}
@@ -743,7 +952,6 @@ void QBVH::pack_nodes(const BVHNode *root)
 				nodes[numnodes++] = node0->get_child(0);
 				nodes[numnodes++] = node0->get_child(1);
 			}
-
 			if(node1->is_leaf()) {
 				nodes[numnodes++] = node1;
 			}
@@ -751,26 +959,26 @@ void QBVH::pack_nodes(const BVHNode *root)
 				nodes[numnodes++] = node1->get_child(0);
 				nodes[numnodes++] = node1->get_child(1);
 			}
-
-			/* push entries on the stack */
-			for(int i = 0; i < numnodes; i++) {
+			/* Push entries on the stack. */
+			for(int i = 0; i < numnodes; ++i) {
 				int idx;
 				if(nodes[i]->is_leaf()) {
 					idx = nextLeafNodeIdx++;
 				}
 				else {
 					idx = nextNodeIdx;
-					nextNodeIdx += BVH_QNODE_SIZE;
+					nextNodeIdx += node_qbvh_is_unaligned(nodes[i])
+					                       ? BVH_UNALIGNED_QNODE_SIZE
+					                       : BVH_QNODE_SIZE;
 				}
 				stack.push_back(BVHStackEntry(nodes[i], idx));
 			}
-
-			/* set node */
+			/* Set node. */
 			pack_inner(e, &stack[stack.size()-numnodes], numnodes);
 		}
 	}
-
-	/* root index to start traversal at, to handle case of single leaf node */
+	assert(node_size == nextNodeIdx);
+	/* Root index to start traversal at, to handle case of single leaf node. */
 	pack.root_index = (root->is_leaf())? -1: 0;
 }
 
@@ -868,13 +1076,18 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
 		leaf_data[0].y = __int_as_float(c.y);
 		leaf_data[0].z = __uint_as_float(visibility);
 		leaf_data[0].w = __uint_as_float(c.w);
-		memcpy(&pack.leaf_nodes[idx],
-		       leaf_data,
-		       sizeof(float4)*BVH_QNODE_LEAF_SIZE);
+		memcpy(&pack.leaf_nodes[idx], leaf_data, sizeof(float4)*BVH_QNODE_LEAF_SIZE);
 	}
 	else {
 		int4 *data = &pack.nodes[idx];
-		int4 c = data[7];
+		bool is_unaligned = (data[0].x & PATH_RAY_NODE_UNALIGNED) != 0;
+		int4 c;
+		if(is_unaligned) {
+			c = data[13];
+		}
+		else {
+			c = data[7];
+		}
 		/* Refit inner node, set bbox from children. */
 		BoundBox child_bbox[4] = {BoundBox::empty,
 		                          BoundBox::empty,
@@ -893,25 +1106,62 @@ void QBVH::refit_node(int idx, bool leaf, BoundBox& bbox, uint& visibility)
 			}
 		}
 
-		float4 inner_data[BVH_QNODE_SIZE];
-		inner_data[0] = make_float4(__int_as_float(data[0].x),
-		                            __int_as_float(data[1].y),
-		                            __int_as_float(data[2].z),
-		                            __int_as_float(data[3].w));
-		for(int i = 0; i < 4; ++i) {
-			float3 bb_min = child_bbox[i].min;
-			float3 bb_max = child_bbox[i].max;
-			inner_data[1][i] = bb_min.x;
-			inner_data[2][i] = bb_max.x;
-			inner_data[3][i] = bb_min.y;
-			inner_data[4][i] = bb_max.y;
-			inner_data[5][i] = bb_min.z;
-			inner_data[6][i] = bb_max.z;
-			inner_data[7][i] = __int_as_float(c[i]);
+		/* TODO(sergey): To be de-duplicated with pack_inner(),
+		 * but for that need some sort of pack_node(). which operates with
+		 * direct data, not stack element.
+		 */
+		if(is_unaligned) {
+			Transform aligned_space = transform_identity();
+			float4 inner_data[BVH_UNALIGNED_QNODE_SIZE];
+			inner_data[0] = make_float4(
+			        __int_as_float(visibility | PATH_RAY_NODE_UNALIGNED),
+			        0.0f,
+			        0.0f,
+			        0.0f);
+			for(int i = 0; i < 4; ++i) {
+				Transform space = BVHUnaligned::compute_node_transform(
+				        child_bbox[i],
+				        aligned_space);
+				inner_data[1][i] = space.x.x;
+				inner_data[2][i] = space.x.y;
+				inner_data[3][i] = space.x.z;
+
+				inner_data[4][i] = space.y.x;
+				inner_data[5][i] = space.y.y;
+				inner_data[6][i] = space.y.z;
+
+				inner_data[7][i] = space.z.x;
+				inner_data[8][i] = space.z.y;
+				inner_data[9][i] = space.z.z;
+
+				inner_data[10][i] = space.x.w;
+				inner_data[11][i] = space.y.w;
+				inner_data[12][i] = space.z.w;
+
+				inner_data[13][i] = __int_as_float(c[i]);
+			}
+			memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_UNALIGNED_QNODE_SIZE);
+		}
+		else {
+			float4 inner_data[BVH_QNODE_SIZE];
+			inner_data[0] = make_float4(
+			        __int_as_float(visibility & ~PATH_RAY_NODE_UNALIGNED),
+			        0.0f,
+			        0.0f,
+			        0.0f);
+			for(int i = 0; i < 4; ++i) {
+				float3 bb_min = child_bbox[i].min;
+				float3 bb_max = child_bbox[i].max;
+				inner_data[1][i] = bb_min.x;
+				inner_data[2][i] = bb_max.x;
+				inner_data[3][i] = bb_min.y;
+				inner_data[4][i] = bb_max.y;
+				inner_data[5][i] = bb_min.z;
+				inner_data[6][i] = bb_max.z;
+				inner_data[7][i] = __int_as_float(c[i]);
+			}
+			memcpy(&pack.nodes[idx], inner_data, sizeof(float4)*BVH_QNODE_SIZE);
 		}
-		memcpy(&pack.nodes[idx],
-		       inner_data,
-		       sizeof(float4)*BVH_QNODE_SIZE);
 	}
 }