Panda3D
 All Classes Functions Variables Enumerations
cullPlanes.cxx
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 }
 All Classes Functions Variables Enumerations