PA3—discussion, Octave Tree
Marco Leung
Construct the Octave Tree
A
A
B1
B2
B3
B4
A
B1 B2 B3 B4
struct Node { …
bool isLeaf; Node* child[4]; …
}
// Internal node? Leaf?
A
BoundingBox2f bboxA;
A
A
BoundingBox2f bboxA; BoundingBox2f bboxB[4]; …
A
midpoint
BoundingBox2f bboxA; BoundingBox2f bboxB[4];
…
Point2f midpoint = bboxA.getCenter();
A
corner
midpoint
BoundingBox2f bboxA; BoundingBox2f bboxB[4];
…
Point2f midpoint = bboxA.getCenter(); Point2f corner = bboxA.getCorner(0);
A
corner
max
min
midpoint
BoundingBox2f bboxA; BoundingBox2f bboxB[4];
…
Point2f midpoint = bboxA.getCenter(); Point2f corner = bboxA.getCorner(0);
(corner, midpoint)à(min, max)
A
max
B1
min
A
B1
BoundingBox2f bboxA; BoundingBox2f bboxB[4];
…
Point2f midpoint = bboxA.getCenter(); Point2f corner = bboxA.getCorner(0);
(corner, midpoint)à(min, max) bboxB[0] = BoundingBox2f(min, max);
B1
B2
B3
B4
A
B1 B2 B3 B4
BoundingBox2f bboxA; BoundingBox2f bboxB[4];
…
Point2f midpoint = bboxA.getCenter(); Point2f corner = bboxA.getCorner(0);
(corner, midpoint)à(min, max) bboxB[0] = BoundingBox2f(min, max);
C1
C2
B2
C3
C4
B3
B4
A
B2 B3 B4
C1 C2 C3 C4
B1
Node *build(BoundingBox2f bbox, …) { …
build(bbox, …);
}
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
int n = mesh->getTriangleCount();
𝑡𝑟𝑖𝑎𝑛𝑙𝑔𝑒𝑖𝑛𝑑𝑒𝑥 ∈[0,𝑛)
Node *build(BoundingBox2f bbox, std::vector
if (no triangles) return nullptr;
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list list[4];
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list list[4];
// Divide Bounding Box
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list list[4];
// Divide Bounding Box
for (every triangle) {
tribox = mesh.getBoundingBox(triangle);
}
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list trilist[4]; // Divide Bounding Box
for (every triangle) {
tribox = mesh.getBoundingBox(triangle);
for (every sub-bounding-box) { if (tribox overlaps sub-bbox[i])
add to list[i]; }
}
…
build(bbox, triangles); }
C1
C2
B2
C3
C4
B3
B4
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list trilist[4]; boundingbox_list boxlist[4];
// Divide Bounding Box
for (every triangle) {
tribox = mesh.getBoundingBox(triangle);
for (every sub-bounding-box) { if (tribox overlaps sub-bbox[i])
add to list[i]; }
}
Node *node = new Node();
return node
C1
C2
B2
C3
C4
B3
B4
}
Node *build(BoundingBox2f bbox, std::vector
return nullptr;
if (only few triangles)
return new leaf node with triangles;
triangle_list trilist[4]; boundingbox_list boxlist[4];
// Divide Bounding Box
for (every triangle) {
tribox = mesh.getBoundingBox(triangle);
for (every sub-bounding-box) { if (tribox overlaps sub-bbox[i])
add to list[i]; }
}
Node *node = new Node();
for (every sub-node i)
node.child[i] = build(bounding box of sub-node i, list[i]);
return node }
C1
C2
B2
C3
C4
B3
B4
Corner Cases
Triangle’s bounding box
Corner Cases
Sub bounding box inside triangle’s bounding box
Corner Cases
Sub bounding box’s center on triangle’s bounding box surface
Corner Cases
Limit tree’s depth
Sub bounding box’s center on triangle’s bounding box surface
Tree Travelsal — Depth-first search
#include
Satck
A
A
Ray
Tree Travelsal — Depth-first search
#include
Satck
B1
B2
B3
B4
B4
B2
B1
Ray
Tree Travelsal — Depth-first search
#include
Satck
B1
B2
B4
B2
B1
B3
B4
Ray
Tree Travelsal — Depth-first search
Satck
C1
C2
B2
C3
C4
B3
B4
B4
B2
C4
C2
C1
Ray
Tree Travelsal — Depth-first search
if (node.isLeaf) {
for (every triangle) {
find ray intersection }
}
Satck
C1
C2
B2
C3
C4
B3
B4
B4
B2
C4
C2
C1
Ray