clray
view src/scene.cc @ 25:58642a8316b7
continuing with the kdtree
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 14 Aug 2010 07:00:04 +0100 |
| parents | 13091c00d7ca |
| children | c740ae431d51 |
line source
1 #include <math.h>
2 #include <float.h>
3 #include "scene.h"
5 #define FEQ(a, b) (fabs((a) - (b)) < 1e-8)
6 bool Face::operator ==(const Face &f) const
7 {
8 for(int i=0; i<3; i++) {
9 for(int j=0; j<3; j++) {
10 if(!FEQ(v[i].pos[j], f.v[i].pos[j])) {
11 return false;
12 }
13 if(!FEQ(v[i].normal[j], f.v[i].normal[j])) {
14 return false;
15 }
16 }
17 if(!FEQ(normal[i], f.normal[i])) {
18 return false;
19 }
20 }
21 return true;
22 }
24 float AABBox::calc_surface_area() const
25 {
26 float area1 = (max[0] - min[0]) * (max[1] - min[1]);
27 float area2 = (max[3] - min[3]) * (max[1] - min[1]);
28 float area3 = (max[0] - min[0]) * (max[3] - min[3]);
30 return 2.0f * (area1 + area2 + area3);
31 }
34 Scene::Scene()
35 {
36 facebuf = 0;
37 num_faces = -1;
38 kdtree = 0;
39 }
41 Scene::~Scene()
42 {
43 delete [] facebuf;
44 }
46 bool Scene::add_mesh(Mesh *m)
47 {
48 // make sure triangles have material ids
49 for(size_t i=0; i<m->faces.size(); i++) {
50 m->faces[i].matid = m->matid;
51 }
53 try {
54 meshes.push_back(m);
55 }
56 catch(...) {
57 return false;
58 }
60 // invalidate facebuffer and count
61 delete [] facebuf;
62 facebuf = 0;
63 num_faces = -1;
65 return true;
66 }
68 int Scene::get_num_meshes() const
69 {
70 return (int)meshes.size();
71 }
73 int Scene::get_num_faces() const
74 {
75 if(num_faces >= 0) {
76 return num_faces;
77 }
79 num_faces = 0;
80 for(size_t i=0; i<meshes.size(); i++) {
81 num_faces += meshes[i]->faces.size();
82 }
83 return num_faces;
84 }
86 int Scene::get_num_materials() const
87 {
88 return (int)matlib.size();
89 }
91 Material *Scene::get_materials()
92 {
93 if(matlib.empty()) {
94 return 0;
95 }
96 return &matlib[0];
97 }
99 const Material *Scene::get_materials() const
100 {
101 if(matlib.empty()) {
102 return 0;
103 }
104 return &matlib[0];
105 }
107 const Face *Scene::get_face_buffer() const
108 {
109 if(facebuf) {
110 return facebuf;
111 }
113 int num_meshes = get_num_meshes();
115 printf("constructing face buffer with %d faces (out of %d meshes)\n", get_num_faces(), num_meshes);
116 facebuf = new Face[num_faces];
117 Face *fptr = facebuf;
119 for(int i=0; i<num_meshes; i++) {
120 for(size_t j=0; j<meshes[i]->faces.size(); j++) {
121 *fptr++ = meshes[i]->faces[j];
122 }
123 }
124 return facebuf;
125 }
127 static int build_kdtree(KDNode *kd);
128 static void free_kdtree(KDNode *node);
130 void Scene::build_kdtree()
131 {
132 const Face *faces = get_face_buffer();
133 int num_faces = get_num_faces();
135 printf("Constructing kd-tree out of %d faces ...\n", num_faces);
137 free_kdtree(kdtree);
138 kdtree = new KDNode;
139 kdtree->left = kdtree->right = 0;
141 /* Start the construction of the kdtree by adding all faces of the scene
142 * to the new root node. At the same time calculate the root's AABB.
143 */
144 kdtree->aabb.min[0] = kdtree->aabb.min[1] = kdtree->aabb.min[2] = FLT_MAX;
145 kdtree->aabb.max[0] = kdtree->aabb.max[1] = kdtree->aabb.max[2] = -FLT_MAX;
147 for(int i=0; i<num_faces; i++) {
148 const Face *face = faces + i;
150 // for each vertex of the face ...
151 for(int j=0; j<3; j++) {
152 const float *pos = face->v[j].pos;
154 // for each element (xyz) of the position vector ...
155 for(int k=0; k<3; k++) {
156 if(pos[k] < kdtree->aabb.min[k]) {
157 kdtree->aabb.min[k] = pos[k];
158 }
159 if(pos[k] > kdtree->aabb.max[k]) {
160 kdtree->aabb.max[k] = pos[k];
161 }
162 }
163 }
165 kdtree->faces.push_back(face); // add the face
166 }
168 // now proceed splitting the root recursively
169 ::build_kdtree(kdtree);
170 }
172 static int build_kdtree(KDNode *kd)
173 {
174 if(kd->faces.empty()) {
175 return 0;
176 }
178 // XXX cont.
179 return -1;
180 }
182 static void free_kdtree(KDNode *node)
183 {
184 if(node) {
185 free_kdtree(node->left);
186 free_kdtree(node->right);
187 delete node;
188 }
189 }