Panda3D
|
00001 // Filename: cullPlanes.cxx 00002 // Created by: drose (23Aug05) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 #include "cullPlanes.h" 00016 #include "cullTraverserData.h" 00017 #include "clipPlaneAttrib.h" 00018 #include "occluderEffect.h" 00019 #include "boundingBox.h" 00020 00021 00022 //////////////////////////////////////////////////////////////////// 00023 // Function: CullPlanes::make_empty 00024 // Access: Public, Static 00025 // Description: Returns a pointer to an empty CullPlanes object. 00026 //////////////////////////////////////////////////////////////////// 00027 CPT(CullPlanes) CullPlanes:: 00028 make_empty() { 00029 static CPT(CullPlanes) empty; 00030 if (empty == NULL) { 00031 empty = new CullPlanes; 00032 // Artificially tick the reference count, just to ensure we won't 00033 // accidentally modify this object in any of the copy-on-write 00034 // operations below. 00035 empty->ref(); 00036 } 00037 return empty; 00038 } 00039 00040 //////////////////////////////////////////////////////////////////// 00041 // Function: CullPlanes::xform 00042 // Access: Public 00043 // Description: Returns a pointer to a new CullPlanes object that is 00044 // the same as this one, but with the clip planes 00045 // modified by the indicated transform. 00046 //////////////////////////////////////////////////////////////////// 00047 CPT(CullPlanes) CullPlanes:: 00048 xform(const LMatrix4 &mat) const { 00049 PT(CullPlanes) new_planes; 00050 if (get_ref_count() == 1) { 00051 new_planes = (CullPlanes *)this; 00052 } else { 00053 new_planes = new CullPlanes(*this); 00054 } 00055 00056 for (Planes::iterator pi = new_planes->_planes.begin(); 00057 pi != new_planes->_planes.end(); 00058 ++pi) { 00059 if ((*pi).second->get_ref_count() != 1) { 00060 (*pi).second = DCAST(BoundingPlane, (*pi).second->make_copy()); 00061 } 00062 (*pi).second->xform(mat); 00063 } 00064 00065 for (Occluders::iterator oi = new_planes->_occluders.begin(); 00066 oi != new_planes->_occluders.end(); 00067 ++oi) { 00068 if ((*oi).second->get_ref_count() != 1) { 00069 (*oi).second = DCAST(BoundingHexahedron, (*oi).second->make_copy()); 00070 } 00071 (*oi).second->xform(mat); 00072 } 00073 00074 return new_planes; 00075 } 00076 00077 //////////////////////////////////////////////////////////////////// 00078 // Function: CullPlanes::apply_state 00079 // Access: Public 00080 // Description: Returns a pointer to a new CullPlanes object that is 00081 // the same as this one, but with the indicated 00082 // attributes applied to the state. 00083 // 00084 // In particular, any new ClipPlanes given in 00085 // net_attrib, if it is not NULL, will be added to the 00086 // state, unless those ClipPlanes are also listed in 00087 // off_attrib. 00088 //////////////////////////////////////////////////////////////////// 00089 CPT(CullPlanes) CullPlanes:: 00090 apply_state(const CullTraverser *trav, const CullTraverserData *data, 00091 const ClipPlaneAttrib *net_attrib, 00092 const ClipPlaneAttrib *off_attrib, 00093 const OccluderEffect *node_effect) const { 00094 if (net_attrib == (ClipPlaneAttrib *)NULL && node_effect == (OccluderEffect *)NULL) { 00095 return this; 00096 } 00097 00098 PT(CullPlanes) new_planes; 00099 if (get_ref_count() == 1) { 00100 new_planes = (CullPlanes *)this; 00101 } else { 00102 new_planes = new CullPlanes(*this); 00103 } 00104 00105 CPT(TransformState) net_transform = NULL; 00106 00107 if (net_attrib != (ClipPlaneAttrib *)NULL) { 00108 int num_on_planes = net_attrib->get_num_on_planes(); 00109 for (int i = 0; i < num_on_planes; ++i) { 00110 NodePath clip_plane = net_attrib->get_on_plane(i); 00111 Planes::const_iterator pi = new_planes->_planes.find(clip_plane); 00112 if (pi == new_planes->_planes.end()) { 00113 if (!off_attrib->has_off_plane(clip_plane)) { 00114 // Here's a new clip plane; add it to the list. For this we 00115 // need the net transform to this node. 00116 if (net_transform == (TransformState *)NULL) { 00117 net_transform = data->get_net_transform(trav); 00118 } 00119 00120 PlaneNode *plane_node = DCAST(PlaneNode, clip_plane.node()); 00121 CPT(TransformState) new_transform = 00122 net_transform->invert_compose(clip_plane.get_net_transform()); 00123 00124 LPlane plane = plane_node->get_plane() * new_transform->get_mat(); 00125 new_planes->_planes[clip_plane] = new BoundingPlane(-plane); 00126 } 00127 } 00128 } 00129 } 00130 00131 if (node_effect != (OccluderEffect *)NULL) { 00132 CPT(TransformState) center_transform = NULL; 00133 // We'll need to know the occluder's frustum in cull-center 00134 // space. 00135 SceneSetup *scene = trav->get_scene(); 00136 const Lens *lens = scene->get_lens(); 00137 00138 int num_on_occluders = node_effect->get_num_on_occluders(); 00139 for (int i = 0; i < num_on_occluders; ++i) { 00140 NodePath occluder = node_effect->get_on_occluder(i); 00141 Occluders::const_iterator oi = new_planes->_occluders.find(occluder); 00142 if (oi == new_planes->_occluders.end()) { 00143 // Here's a new occluder; consider adding it to the list. 00144 OccluderNode *occluder_node = DCAST(OccluderNode, occluder.node()); 00145 nassertr(occluder_node->get_num_vertices() == 4, new_planes); 00146 00147 CPT(TransformState) occluder_transform = occluder.get_transform(scene->get_cull_center()); 00148 00149 // And the transform from cull-center space into the current 00150 // node's coordinate space. 00151 if (center_transform == (TransformState *)NULL) { 00152 if (net_transform == (TransformState *)NULL) { 00153 net_transform = data->get_net_transform(trav); 00154 } 00155 00156 center_transform = net_transform->invert_compose(scene->get_cull_center().get_net_transform()); 00157 } 00158 00159 // Compare the occluder node's bounding volume to the view 00160 // frustum. We construct a new bounding volume because (a) 00161 // the node's existing bounding volume is in the coordinate 00162 // space of its parent, which isn't what we have here, and (b) 00163 // we might as well make a BoundingBox, which is as tight as 00164 // possible, and creating one isn't any less efficient than 00165 // transforming the existing bounding volume. 00166 PT(BoundingBox) occluder_gbv; 00167 // Get a transform from the occluder directly to this node's 00168 // space for comparing with the current view frustum. 00169 CPT(TransformState) composed_transform = center_transform->compose(occluder_transform); 00170 const LMatrix4 &composed_mat = composed_transform->get_mat(); 00171 LPoint3 ccp[4]; 00172 ccp[0] = occluder_node->get_vertex(0) * composed_mat; 00173 ccp[1] = occluder_node->get_vertex(1) * composed_mat; 00174 ccp[2] = occluder_node->get_vertex(2) * composed_mat; 00175 ccp[3] = occluder_node->get_vertex(3) * composed_mat; 00176 00177 LPoint3 ccp_min(min(min(ccp[0][0], ccp[1][0]), 00178 min(ccp[2][0], ccp[3][0])), 00179 min(min(ccp[0][1], ccp[1][1]), 00180 min(ccp[2][1], ccp[3][1])), 00181 min(min(ccp[0][2], ccp[1][2]), 00182 min(ccp[2][2], ccp[3][2]))); 00183 LPoint3 ccp_max(max(max(ccp[0][0], ccp[1][0]), 00184 max(ccp[2][0], ccp[3][0])), 00185 max(max(ccp[0][1], ccp[1][1]), 00186 max(ccp[2][1], ccp[3][1])), 00187 max(max(ccp[0][2], ccp[1][2]), 00188 max(ccp[2][2], ccp[3][2]))); 00189 00190 occluder_gbv = new BoundingBox(ccp_min, ccp_max); 00191 00192 if (data->_view_frustum != (GeometricBoundingVolume *)NULL) { 00193 int occluder_result = data->_view_frustum->contains(occluder_gbv); 00194 if (occluder_result == BoundingVolume::IF_no_intersection) { 00195 // This occluder is outside the view frustum; ignore it. 00196 if (pgraph_cat.is_spam()) { 00197 pgraph_cat.spam() 00198 << "Ignoring occluder " << occluder << ": outside view frustum.\n"; 00199 } 00200 continue; 00201 } 00202 } 00203 00204 // Get the occluder geometry in cull-center space. 00205 const LMatrix4 &occluder_mat = occluder_transform->get_mat(); 00206 LPoint3 points_near[4]; 00207 points_near[0] = occluder_node->get_vertex(0) * occluder_mat; 00208 points_near[1] = occluder_node->get_vertex(1) * occluder_mat; 00209 points_near[2] = occluder_node->get_vertex(2) * occluder_mat; 00210 points_near[3] = occluder_node->get_vertex(3) * occluder_mat; 00211 LPlane plane(points_near[0], points_near[1], points_near[2]); 00212 00213 if (plane.get_normal().dot(LVector3::forward()) >= 0.0) { 00214 if (occluder_node->is_double_sided()) { 00215 swap(points_near[0], points_near[3]); 00216 swap(points_near[1], points_near[2]); 00217 plane = LPlane(points_near[0], points_near[1], points_near[2]); 00218 } else { 00219 // This occluder is facing the wrong direction. Ignore it. 00220 if (pgraph_cat.is_spam()) { 00221 pgraph_cat.spam() 00222 << "Ignoring occluder " << occluder << ": wrong direction.\n"; 00223 } 00224 continue; 00225 } 00226 } 00227 00228 PN_stdfloat near_clip = lens->get_near(); 00229 if (plane.dist_to_plane(LPoint3::zero()) <= near_clip) { 00230 // This occluder is behind the camera's near plane. Ignore it. 00231 if (pgraph_cat.is_spam()) { 00232 pgraph_cat.spam() 00233 << "Ignoring occluder " << occluder << ": behind near plane.\n"; 00234 } 00235 continue; 00236 } 00237 00238 PN_stdfloat d0 = points_near[0].dot(LVector3::forward()); 00239 PN_stdfloat d1 = points_near[1].dot(LVector3::forward()); 00240 PN_stdfloat d2 = points_near[2].dot(LVector3::forward()); 00241 PN_stdfloat d3 = points_near[3].dot(LVector3::forward()); 00242 00243 if (d0 <= near_clip && d1 <= near_clip && d2 <= near_clip && d3 <= near_clip) { 00244 // All four corners of the occluder are behind the camera's 00245 // near plane. Ignore it. 00246 if (pgraph_cat.is_spam()) { 00247 pgraph_cat.spam() 00248 << "Ignoring occluder " << occluder << ": behind near plane (test 2).\n"; 00249 } 00250 continue; 00251 } 00252 00253 // TODO: it's possible for part of the occlusion polygon to 00254 // intersect the camera's y = 0 plane. If this happens, the 00255 // frustum will go insane and the occluder won't work. The 00256 // proper fix for this is to clip the polygon against the near 00257 // plane, producing a smaller polygon, and use that to 00258 // generate the frustum. But maybe it doesn't matter. In 00259 // lieu of this, we just toss out any occluder with *any* 00260 // corner behind the y = 0 plane. 00261 if (d0 <= 0.0 || d1 <= 0.0 || d2 <= 0.0 || d3 <= 0.0) { 00262 // One of the corners is behind the y = 0 plane. We can't 00263 // handle this case. Ignore it. 00264 if (pgraph_cat.is_spam()) { 00265 pgraph_cat.spam() 00266 << "Ignoring occluder " << occluder << ": partly behind zero plane.\n"; 00267 } 00268 continue; 00269 } 00270 00271 if (occluder_node->get_min_coverage()) { 00272 LPoint3 coords[4]; 00273 lens->project(points_near[0], coords[0]); 00274 lens->project(points_near[1], coords[1]); 00275 lens->project(points_near[2], coords[2]); 00276 lens->project(points_near[3], coords[3]); 00277 coords[0][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[0][0])); 00278 coords[0][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[0][1])); 00279 coords[1][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[1][0])); 00280 coords[1][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[1][1])); 00281 coords[2][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[2][0])); 00282 coords[2][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[2][1])); 00283 coords[3][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[3][0])); 00284 coords[3][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[3][1])); 00285 PN_stdfloat coverage = ((coords[0] - coords[1]).cross(coords[0] - coords[2]).length() 00286 + (coords[3] - coords[1]).cross(coords[3] - coords[2]).length()) 00287 * 0.125; 00288 if (coverage < occluder_node->get_min_coverage()) { 00289 // The occluder does not cover enough screen space. Ignore it. 00290 if (pgraph_cat.is_spam()) { 00291 pgraph_cat.spam() 00292 << "Ignoring occluder " << occluder << ": coverage less than minimum.\n"; 00293 } 00294 continue; 00295 } 00296 } 00297 00298 // Also check if the new occluder is completely within any of 00299 // our existing occluder volumes. 00300 bool is_enclosed = false; 00301 Occluders::const_iterator oi; 00302 for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) { 00303 int occluder_result = (*oi).second->contains(occluder_gbv); 00304 if ((occluder_result & BoundingVolume::IF_all) != 0) { 00305 is_enclosed = true; 00306 break; 00307 } 00308 } 00309 if (is_enclosed) { 00310 // No reason to add this occluder; it's behind an existing 00311 // occluder. 00312 if (pgraph_cat.is_spam()) { 00313 pgraph_cat.spam() 00314 << "Ignoring occluder " << occluder << ": behind another.\n"; 00315 } 00316 continue; 00317 } 00318 // TODO: perhaps we should also check whether any existing 00319 // occluders are fully contained within this new one. 00320 00321 // Project those four lines to the camera's far plane. 00322 PN_stdfloat far_clip = scene->get_lens()->get_far(); 00323 LPlane far_plane(-LVector3::forward(), LVector3::forward() * far_clip); 00324 00325 LPoint3 points_far[4]; 00326 far_plane.intersects_line(points_far[0], LPoint3::zero(), points_near[0]); 00327 far_plane.intersects_line(points_far[1], LPoint3::zero(), points_near[1]); 00328 far_plane.intersects_line(points_far[2], LPoint3::zero(), points_near[2]); 00329 far_plane.intersects_line(points_far[3], LPoint3::zero(), points_near[3]); 00330 00331 // With these points, construct the bounding frustum of the 00332 // occluded region. 00333 PT(BoundingHexahedron) frustum = 00334 new BoundingHexahedron(points_far[1], points_far[2], points_far[3], points_far[0], 00335 points_near[1], points_near[2], points_near[3], points_near[0]); 00336 frustum->xform(center_transform->get_mat()); 00337 00338 new_planes->_occluders[occluder] = frustum; 00339 00340 if (show_occluder_volumes) { 00341 // Draw the frustum for visualization. 00342 nassertr(net_transform != NULL, new_planes); 00343 trav->draw_bounding_volume(frustum, net_transform, 00344 data->get_modelview_transform(trav)); 00345 } 00346 } 00347 } 00348 } 00349 00350 return new_planes; 00351 } 00352 00353 //////////////////////////////////////////////////////////////////// 00354 // Function: CullPlanes::do_cull 00355 // Access: Public 00356 // Description: Tests the indicated bounding volume against all of 00357 // the clip planes in this object. Sets result to an 00358 // appropriate union of 00359 // BoundingVolume::IntersectionFlags, similar to the 00360 // result of BoundingVolume::contains(). 00361 // 00362 // Also, if the bounding volume is completely in front 00363 // of any of the clip planes, removes those planes both 00364 // from this object and from the indicated state, 00365 // returning a new CullPlanes object in that case. 00366 //////////////////////////////////////////////////////////////////// 00367 CPT(CullPlanes) CullPlanes:: 00368 do_cull(int &result, CPT(RenderState) &state, 00369 const GeometricBoundingVolume *node_gbv) const { 00370 result = 00371 BoundingVolume::IF_all | BoundingVolume::IF_possible | BoundingVolume::IF_some; 00372 00373 CPT(ClipPlaneAttrib) orig_cpa = DCAST(ClipPlaneAttrib, state->get_attrib(ClipPlaneAttrib::get_class_slot())); 00374 00375 CPT(CullPlanes) new_planes = this; 00376 00377 if (orig_cpa == (ClipPlaneAttrib *)NULL) { 00378 // If there are no clip planes in the state, the node is completely 00379 // in front of all zero of the clip planes. (This can happen if 00380 // someone directly changes the state during the traversal.) 00381 CullPlanes *planes = new CullPlanes; 00382 planes->_occluders = _occluders; 00383 new_planes = planes; 00384 00385 } else { 00386 CPT(ClipPlaneAttrib) new_cpa = orig_cpa; 00387 00388 Planes::const_iterator pi; 00389 for (pi = _planes.begin(); pi != _planes.end(); ++pi) { 00390 int plane_result = (*pi).second->contains(node_gbv); 00391 if (plane_result == BoundingVolume::IF_no_intersection) { 00392 // The node is completely behind this clip plane and gets 00393 // culled. Short-circuit the rest of the logic; none of the 00394 // other planes matter. 00395 result = plane_result; 00396 return new_planes; 00397 } else if ((plane_result & BoundingVolume::IF_all) != 0) { 00398 // The node is completely in front of this clip plane. We don't 00399 // need to consider this plane ever again for any descendents of 00400 // this node. 00401 new_planes = new_planes->remove_plane((*pi).first); 00402 nassertr(new_planes != this, new_planes); 00403 new_cpa = DCAST(ClipPlaneAttrib, new_cpa->remove_on_plane((*pi).first)); 00404 } 00405 00406 result &= plane_result; 00407 } 00408 00409 if (new_cpa != orig_cpa) { 00410 if (new_cpa->is_identity()) { 00411 state = state->remove_attrib(ClipPlaneAttrib::get_class_slot()); 00412 } else { 00413 state = state->add_attrib(new_cpa); 00414 } 00415 } 00416 } 00417 00418 Occluders::const_iterator oi; 00419 for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) { 00420 int occluder_result = (*oi).second->contains(node_gbv); 00421 if (occluder_result == BoundingVolume::IF_no_intersection) { 00422 // The node is completely in front of this occluder. We don't 00423 // need to consider this occluder ever again for any descendents of 00424 // this node. 00425 00426 // Reverse the sense of the test, because an occluder volume is 00427 // the inverse of a cull plane volume: it describes the volume 00428 // that is to be culled, not the volume that is to be kept. 00429 occluder_result = BoundingVolume::IF_all | BoundingVolume::IF_possible | BoundingVolume::IF_some; 00430 new_planes = new_planes->remove_occluder((*oi).first); 00431 nassertr(new_planes != this, new_planes); 00432 00433 } else if ((occluder_result & BoundingVolume::IF_all) != 0) { 00434 // The node is completely behind this occluder and gets culled. 00435 // Short-circuit the rest of the logic; none of the other 00436 // occluders matter. 00437 result = BoundingVolume::IF_no_intersection; 00438 return new_planes; 00439 } 00440 00441 result &= occluder_result; 00442 } 00443 00444 return new_planes; 00445 } 00446 00447 //////////////////////////////////////////////////////////////////// 00448 // Function: CullPlanes::remove_plane 00449 // Access: Public 00450 // Description: Returns a pointer to a new CullPlanes object that is 00451 // the same as this one, but with the indicated 00452 // clip plane removed. 00453 //////////////////////////////////////////////////////////////////// 00454 CPT(CullPlanes) CullPlanes:: 00455 remove_plane(const NodePath &clip_plane) const { 00456 PT(CullPlanes) new_planes; 00457 if (get_ref_count() == 1) { 00458 new_planes = (CullPlanes *)this; 00459 } else { 00460 new_planes = new CullPlanes(*this); 00461 } 00462 00463 Planes::iterator pi = new_planes->_planes.find(clip_plane); 00464 nassertr(pi != new_planes->_planes.end(), new_planes); 00465 new_planes->_planes.erase(pi); 00466 00467 return new_planes; 00468 } 00469 00470 //////////////////////////////////////////////////////////////////// 00471 // Function: CullPlanes::remove_occluder 00472 // Access: Public 00473 // Description: Returns a pointer to a new CullPlanes object that is 00474 // the same as this one, but with the indicated 00475 // occluder removed. 00476 //////////////////////////////////////////////////////////////////// 00477 CPT(CullPlanes) CullPlanes:: 00478 remove_occluder(const NodePath &occluder) const { 00479 PT(CullPlanes) new_planes; 00480 if (get_ref_count() == 1) { 00481 new_planes = (CullPlanes *)this; 00482 } else { 00483 new_planes = new CullPlanes(*this); 00484 } 00485 00486 Occluders::iterator pi = new_planes->_occluders.find(occluder); 00487 nassertr(pi != new_planes->_occluders.end(), new_planes); 00488 new_planes->_occluders.erase(pi); 00489 00490 return new_planes; 00491 } 00492 00493 //////////////////////////////////////////////////////////////////// 00494 // Function: CullPlanes::write 00495 // Access: Public 00496 // Description: 00497 //////////////////////////////////////////////////////////////////// 00498 void CullPlanes:: 00499 write(ostream &out) const { 00500 out << "CullPlanes (" << _planes.size() << " planes and " 00501 << _occluders.size() << " occluders):\n"; 00502 Planes::const_iterator pi; 00503 for (pi = _planes.begin(); pi != _planes.end(); ++pi) { 00504 out << " " << (*pi).first << " : " << *(*pi).second << "\n"; 00505 } 00506 00507 Occluders::const_iterator oi; 00508 for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) { 00509 out << " " << (*oi).first << " : " << *(*oi).second << "\n"; 00510 } 00511 }