Panda3D
 All Classes Functions Variables Enumerations
cullPlanes.cxx
1 // Filename: cullPlanes.cxx
2 // Created by: drose (23Aug05)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #include "cullPlanes.h"
16 #include "cullTraverser.h"
17 #include "cullTraverserData.h"
18 #include "clipPlaneAttrib.h"
19 #include "occluderEffect.h"
20 #include "boundingBox.h"
21 
22 ////////////////////////////////////////////////////////////////////
23 // Function: CullPlanes::make_empty
24 // Access: Public, Static
25 // Description: Returns a pointer to an empty CullPlanes object.
26 ////////////////////////////////////////////////////////////////////
28 make_empty() {
29  static CPT(CullPlanes) empty;
30  if (empty == NULL) {
31  empty = new CullPlanes;
32  // Artificially tick the reference count, just to ensure we won't
33  // accidentally modify this object in any of the copy-on-write
34  // operations below.
35  empty->ref();
36  }
37  return empty;
38 }
39 
40 ////////////////////////////////////////////////////////////////////
41 // Function: CullPlanes::xform
42 // Access: Public
43 // Description: Returns a pointer to a new CullPlanes object that is
44 // the same as this one, but with the clip planes
45 // modified by the indicated transform.
46 ////////////////////////////////////////////////////////////////////
48 xform(const LMatrix4 &mat) const {
49  PT(CullPlanes) new_planes;
50  if (get_ref_count() == 1) {
51  new_planes = (CullPlanes *)this;
52  } else {
53  new_planes = new CullPlanes(*this);
54  }
55 
56  for (Planes::iterator pi = new_planes->_planes.begin();
57  pi != new_planes->_planes.end();
58  ++pi) {
59  if ((*pi).second->get_ref_count() != 1) {
60  (*pi).second = DCAST(BoundingPlane, (*pi).second->make_copy());
61  }
62  (*pi).second->xform(mat);
63  }
64 
65  for (Occluders::iterator oi = new_planes->_occluders.begin();
66  oi != new_planes->_occluders.end();
67  ++oi) {
68  if ((*oi).second->get_ref_count() != 1) {
69  (*oi).second = DCAST(BoundingHexahedron, (*oi).second->make_copy());
70  }
71  (*oi).second->xform(mat);
72  }
73 
74  return new_planes;
75 }
76 
77 ////////////////////////////////////////////////////////////////////
78 // Function: CullPlanes::apply_state
79 // Access: Public
80 // Description: Returns a pointer to a new CullPlanes object that is
81 // the same as this one, but with the indicated
82 // attributes applied to the state.
83 //
84 // In particular, any new ClipPlanes given in
85 // net_attrib, if it is not NULL, will be added to the
86 // state, unless those ClipPlanes are also listed in
87 // off_attrib.
88 ////////////////////////////////////////////////////////////////////
90 apply_state(const CullTraverser *trav, const CullTraverserData *data,
91  const ClipPlaneAttrib *net_attrib,
92  const ClipPlaneAttrib *off_attrib,
93  const OccluderEffect *node_effect) const {
94  if (net_attrib == (ClipPlaneAttrib *)NULL && node_effect == (OccluderEffect *)NULL) {
95  return this;
96  }
97 
98  PT(CullPlanes) new_planes;
99  if (get_ref_count() == 1) {
100  new_planes = (CullPlanes *)this;
101  } else {
102  new_planes = new CullPlanes(*this);
103  }
104 
105  CPT(TransformState) net_transform = NULL;
106 
107  if (net_attrib != (ClipPlaneAttrib *)NULL) {
108  int num_on_planes = net_attrib->get_num_on_planes();
109  for (int i = 0; i < num_on_planes; ++i) {
110  NodePath clip_plane = net_attrib->get_on_plane(i);
111  Planes::const_iterator pi = new_planes->_planes.find(clip_plane);
112  if (pi == new_planes->_planes.end()) {
113  if (!off_attrib->has_off_plane(clip_plane)) {
114  // Here's a new clip plane; add it to the list. For this we
115  // need the net transform to this node.
116  if (net_transform == (TransformState *)NULL) {
117  net_transform = data->get_net_transform(trav);
118  }
119 
120  PlaneNode *plane_node = DCAST(PlaneNode, clip_plane.node());
121  CPT(TransformState) new_transform =
122  net_transform->invert_compose(clip_plane.get_net_transform());
123 
124  LPlane plane = plane_node->get_plane() * new_transform->get_mat();
125  new_planes->_planes[clip_plane] = new BoundingPlane(-plane);
126  }
127  }
128  }
129  }
130 
131  if (node_effect != (OccluderEffect *)NULL) {
132  CPT(TransformState) center_transform = NULL;
133  // We'll need to know the occluder's frustum in cull-center
134  // space.
135  SceneSetup *scene = trav->get_scene();
136  const Lens *lens = scene->get_lens();
137 
138  int num_on_occluders = node_effect->get_num_on_occluders();
139  for (int i = 0; i < num_on_occluders; ++i) {
140  NodePath occluder = node_effect->get_on_occluder(i);
141  Occluders::const_iterator oi = new_planes->_occluders.find(occluder);
142  if (oi == new_planes->_occluders.end()) {
143  // Here's a new occluder; consider adding it to the list.
144  OccluderNode *occluder_node = DCAST(OccluderNode, occluder.node());
145  nassertr(occluder_node->get_num_vertices() == 4, new_planes);
146 
147  CPT(TransformState) occluder_transform = occluder.get_transform(scene->get_cull_center());
148 
149  // And the transform from cull-center space into the current
150  // node's coordinate space.
151  if (center_transform == (TransformState *)NULL) {
152  if (net_transform == (TransformState *)NULL) {
153  net_transform = data->get_net_transform(trav);
154  }
155 
156  center_transform = net_transform->invert_compose(scene->get_cull_center().get_net_transform());
157  }
158 
159  // Compare the occluder node's bounding volume to the view
160  // frustum. We construct a new bounding volume because (a)
161  // the node's existing bounding volume is in the coordinate
162  // space of its parent, which isn't what we have here, and (b)
163  // we might as well make a BoundingBox, which is as tight as
164  // possible, and creating one isn't any less efficient than
165  // transforming the existing bounding volume.
166  PT(BoundingBox) occluder_gbv;
167  // Get a transform from the occluder directly to this node's
168  // space for comparing with the current view frustum.
169  CPT(TransformState) composed_transform = center_transform->compose(occluder_transform);
170  const LMatrix4 &composed_mat = composed_transform->get_mat();
171  LPoint3 ccp[4];
172  ccp[0] = occluder_node->get_vertex(0) * composed_mat;
173  ccp[1] = occluder_node->get_vertex(1) * composed_mat;
174  ccp[2] = occluder_node->get_vertex(2) * composed_mat;
175  ccp[3] = occluder_node->get_vertex(3) * composed_mat;
176 
177  LPoint3 ccp_min(min(min(ccp[0][0], ccp[1][0]),
178  min(ccp[2][0], ccp[3][0])),
179  min(min(ccp[0][1], ccp[1][1]),
180  min(ccp[2][1], ccp[3][1])),
181  min(min(ccp[0][2], ccp[1][2]),
182  min(ccp[2][2], ccp[3][2])));
183  LPoint3 ccp_max(max(max(ccp[0][0], ccp[1][0]),
184  max(ccp[2][0], ccp[3][0])),
185  max(max(ccp[0][1], ccp[1][1]),
186  max(ccp[2][1], ccp[3][1])),
187  max(max(ccp[0][2], ccp[1][2]),
188  max(ccp[2][2], ccp[3][2])));
189 
190  occluder_gbv = new BoundingBox(ccp_min, ccp_max);
191 
192  if (data->_view_frustum != (GeometricBoundingVolume *)NULL) {
193  int occluder_result = data->_view_frustum->contains(occluder_gbv);
194  if (occluder_result == BoundingVolume::IF_no_intersection) {
195  // This occluder is outside the view frustum; ignore it.
196  if (pgraph_cat.is_spam()) {
197  pgraph_cat.spam()
198  << "Ignoring occluder " << occluder << ": outside view frustum.\n";
199  }
200  continue;
201  }
202  }
203 
204  // Get the occluder geometry in cull-center space.
205  const LMatrix4 &occluder_mat_cull = occluder_transform->get_mat();
206  LPoint3 points_near[4];
207  points_near[0] = occluder_node->get_vertex(0) * occluder_mat_cull;
208  points_near[1] = occluder_node->get_vertex(1) * occluder_mat_cull;
209  points_near[2] = occluder_node->get_vertex(2) * occluder_mat_cull;
210  points_near[3] = occluder_node->get_vertex(3) * occluder_mat_cull;
211  LPlane plane(points_near[0], points_near[1], points_near[2]);
212 
213  if (plane.get_normal().dot(LVector3::forward()) >= 0.0) {
214  if (occluder_node->is_double_sided()) {
215  swap(points_near[0], points_near[3]);
216  swap(points_near[1], points_near[2]);
217  plane = LPlane(points_near[0], points_near[1], points_near[2]);
218  } else {
219  // This occluder is facing the wrong direction. Ignore it.
220  if (pgraph_cat.is_spam()) {
221  pgraph_cat.spam()
222  << "Ignoring occluder " << occluder << ": wrong direction.\n";
223  }
224  continue;
225  }
226  }
227 
228  if (occluder_node->get_min_coverage()) {
229  LPoint3 coords[4];
230  lens->project(points_near[0], coords[0]);
231  lens->project(points_near[1], coords[1]);
232  lens->project(points_near[2], coords[2]);
233  lens->project(points_near[3], coords[3]);
234  coords[0][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[0][0]));
235  coords[0][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[0][1]));
236  coords[1][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[1][0]));
237  coords[1][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[1][1]));
238  coords[2][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[2][0]));
239  coords[2][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[2][1]));
240  coords[3][0] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[3][0]));
241  coords[3][1] = max((PN_stdfloat)-1.0, min((PN_stdfloat)1.0, coords[3][1]));
242  PN_stdfloat coverage = ((coords[0] - coords[1]).cross(coords[0] - coords[2]).length()
243  + (coords[3] - coords[1]).cross(coords[3] - coords[2]).length())
244  * 0.125;
245  if (coverage < occluder_node->get_min_coverage()) {
246  // The occluder does not cover enough screen space. Ignore it.
247  if (pgraph_cat.is_spam()) {
248  pgraph_cat.spam()
249  << "Ignoring occluder " << occluder << ": coverage less than minimum.\n";
250  }
251  continue;
252  }
253  }
254 
255  // Also check if the new occluder is completely within any of
256  // our existing occluder volumes.
257  bool is_enclosed = false;
258  Occluders::const_iterator oi;
259  for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) {
260  int occluder_result = (*oi).second->contains(occluder_gbv);
261  if ((occluder_result & BoundingVolume::IF_all) != 0) {
262  is_enclosed = true;
263  break;
264  }
265  }
266  if (is_enclosed) {
267  // No reason to add this occluder; it's behind an existing
268  // occluder.
269  if (pgraph_cat.is_spam()) {
270  pgraph_cat.spam()
271  << "Ignoring occluder " << occluder << ": behind another.\n";
272  }
273  continue;
274  }
275  // TODO: perhaps we should also check whether any existing
276  // occluders are fully contained within this new one.
277 
278  // Get the occluder coordinates in global space.
279  const LMatrix4 &occluder_mat = occluder.get_net_transform()->get_mat();
280  points_near[0] = occluder_node->get_vertex(0) * occluder_mat;
281  points_near[1] = occluder_node->get_vertex(1) * occluder_mat;
282  points_near[2] = occluder_node->get_vertex(2) * occluder_mat;
283  points_near[3] = occluder_node->get_vertex(3) * occluder_mat;
284 
285  // For the far points, project PAST the far clip of the lens
286  // to ensures we get stuff that might be intersecting the far clip.
287  LPoint3 center = scene->get_cull_center().get_net_transform()->get_pos();
288  PN_stdfloat far_clip = scene->get_lens()->get_far() * 2.0;
289  LPoint3 points_far[4];
290  points_far[0] = normalize(points_near[0] - center) * far_clip + points_near[0];
291  points_far[1] = normalize(points_near[1] - center) * far_clip + points_near[1];
292  points_far[2] = normalize(points_near[2] - center) * far_clip + points_near[2];
293  points_far[3] = normalize(points_near[3] - center) * far_clip + points_near[3];
294 
295  // With these points, construct the bounding frustum of the
296  // occluded region.
297  PT(BoundingHexahedron) frustum =
298  new BoundingHexahedron(points_far[1], points_far[2], points_far[3], points_far[0],
299  points_near[1], points_near[2], points_near[3], points_near[0]);
300 
301  new_planes->_occluders[occluder] = frustum;
302 
303  if (show_occluder_volumes) {
304  // Draw the frustum for visualization.
305  nassertr(net_transform != NULL, new_planes);
306  trav->draw_bounding_volume(frustum, data->get_internal_transform(trav));
307  }
308  }
309  }
310  }
311 
312  return new_planes;
313 }
314 
315 ////////////////////////////////////////////////////////////////////
316 // Function: CullPlanes::do_cull
317 // Access: Public
318 // Description: Tests the indicated bounding volume against all of
319 // the clip planes in this object. Sets result to an
320 // appropriate union of
321 // BoundingVolume::IntersectionFlags, similar to the
322 // result of BoundingVolume::contains().
323 //
324 // Also, if the bounding volume is completely in front
325 // of any of the clip planes, removes those planes both
326 // from this object and from the indicated state,
327 // returning a new CullPlanes object in that case.
328 ////////////////////////////////////////////////////////////////////
329 CPT(CullPlanes) CullPlanes::
330 do_cull(int &result, CPT(RenderState) &state,
331  const GeometricBoundingVolume *node_gbv) const {
332  result =
333  BoundingVolume::IF_all | BoundingVolume::IF_possible | BoundingVolume::IF_some;
334 
335  CPT(ClipPlaneAttrib) orig_cpa = DCAST(ClipPlaneAttrib, state->get_attrib(ClipPlaneAttrib::get_class_slot()));
336 
337  CPT(CullPlanes) new_planes = this;
338 
339  if (orig_cpa == (ClipPlaneAttrib *)NULL) {
340  // If there are no clip planes in the state, the node is completely
341  // in front of all zero of the clip planes. (This can happen if
342  // someone directly changes the state during the traversal.)
343  CullPlanes *planes = new CullPlanes;
344  planes->_occluders = _occluders;
345  new_planes = planes;
346 
347  } else {
348  CPT(ClipPlaneAttrib) new_cpa = orig_cpa;
349 
350  Planes::const_iterator pi;
351  for (pi = _planes.begin(); pi != _planes.end(); ++pi) {
352  int plane_result = (*pi).second->contains(node_gbv);
353  if (plane_result == BoundingVolume::IF_no_intersection) {
354  // The node is completely behind this clip plane and gets
355  // culled. Short-circuit the rest of the logic; none of the
356  // other planes matter.
357  result = plane_result;
358  return new_planes;
359  } else if ((plane_result & BoundingVolume::IF_all) != 0) {
360  // The node is completely in front of this clip plane. We don't
361  // need to consider this plane ever again for any descendents of
362  // this node.
363  new_planes = new_planes->remove_plane((*pi).first);
364  nassertr(new_planes != this, new_planes);
365  new_cpa = DCAST(ClipPlaneAttrib, new_cpa->remove_on_plane((*pi).first));
366  }
367 
368  result &= plane_result;
369  }
370 
371  if (new_cpa != orig_cpa) {
372  if (new_cpa->is_identity()) {
373  state = state->remove_attrib(ClipPlaneAttrib::get_class_slot());
374  } else {
375  state = state->add_attrib(new_cpa);
376  }
377  }
378  }
379 
380  Occluders::const_iterator oi;
381  for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) {
382  int occluder_result = (*oi).second->contains(node_gbv);
383  if (occluder_result == BoundingVolume::IF_no_intersection) {
384  // The node is completely in front of this occluder. We don't
385  // need to consider this occluder ever again for any descendents of
386  // this node.
387 
388  // Reverse the sense of the test, because an occluder volume is
389  // the inverse of a cull plane volume: it describes the volume
390  // that is to be culled, not the volume that is to be kept.
391  occluder_result = BoundingVolume::IF_all | BoundingVolume::IF_possible | BoundingVolume::IF_some;
392  new_planes = new_planes->remove_occluder((*oi).first);
393  nassertr(new_planes != this, new_planes);
394 
395  } else if ((occluder_result & BoundingVolume::IF_all) != 0) {
396  // The node is completely behind this occluder and gets culled.
397  // Short-circuit the rest of the logic; none of the other
398  // occluders matter.
399  result = BoundingVolume::IF_no_intersection;
400  return new_planes;
401  }
402 
403  result &= occluder_result;
404  }
405 
406  return new_planes;
407 }
408 
409 ////////////////////////////////////////////////////////////////////
410 // Function: CullPlanes::remove_plane
411 // Access: Public
412 // Description: Returns a pointer to a new CullPlanes object that is
413 // the same as this one, but with the indicated
414 // clip plane removed.
415 ////////////////////////////////////////////////////////////////////
416 CPT(CullPlanes) CullPlanes::
417 remove_plane(const NodePath &clip_plane) const {
418  PT(CullPlanes) new_planes;
419  if (get_ref_count() == 1) {
420  new_planes = (CullPlanes *)this;
421  } else {
422  new_planes = new CullPlanes(*this);
423  }
424 
425  Planes::iterator pi = new_planes->_planes.find(clip_plane);
426  nassertr(pi != new_planes->_planes.end(), new_planes);
427  new_planes->_planes.erase(pi);
428 
429  return new_planes;
430 }
431 
432 ////////////////////////////////////////////////////////////////////
433 // Function: CullPlanes::remove_occluder
434 // Access: Public
435 // Description: Returns a pointer to a new CullPlanes object that is
436 // the same as this one, but with the indicated
437 // occluder removed.
438 ////////////////////////////////////////////////////////////////////
439 CPT(CullPlanes) CullPlanes::
440 remove_occluder(const NodePath &occluder) const {
441  PT(CullPlanes) new_planes;
442  if (get_ref_count() == 1) {
443  new_planes = (CullPlanes *)this;
444  } else {
445  new_planes = new CullPlanes(*this);
446  }
447 
448  Occluders::iterator pi = new_planes->_occluders.find(occluder);
449  nassertr(pi != new_planes->_occluders.end(), new_planes);
450  new_planes->_occluders.erase(pi);
451 
452  return new_planes;
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: CullPlanes::write
457 // Access: Public
458 // Description:
459 ////////////////////////////////////////////////////////////////////
460 void CullPlanes::
461 write(ostream &out) const {
462  out << "CullPlanes (" << _planes.size() << " planes and "
463  << _occluders.size() << " occluders):\n";
464  Planes::const_iterator pi;
465  for (pi = _planes.begin(); pi != _planes.end(); ++pi) {
466  out << " " << (*pi).first << " : " << *(*pi).second << "\n";
467  }
468 
469  Occluders::const_iterator oi;
470  for (oi = _occluders.begin(); oi != _occluders.end(); ++oi) {
471  out << " " << (*oi).first << " : " << *(*oi).second << "\n";
472  }
473 }
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:31
A base class for any number of different kinds of lenses, linear and otherwise.
Definition: lens.h:45
This collects together the pieces of data that are accumulated for each node while walking the scene ...
PandaNode * node() const
Returns the referenced node of the path.
Definition: nodePath.I:284
This functions similarly to a LightAttrib.
This is a three-component point in space (as opposed to a three-component vector, which represents a ...
Definition: lpoint3.h:99
int contains(const GeometricBoundingVolume *vol) const
Returns the appropriate set of IntersectionFlags to indicate the amount of intersection with the indi...
This represents the set of clip planes and/or occluders that are definitely in effect for the current...
Definition: cullPlanes.h:46
LPoint3f project(const LVecBase3f &onto) const
Returns a new vector representing the projection of this vector onto another one. ...
Definition: lpoint3.h:404
int get_num_vertices() const
Returns the number of vertices in the occluder polygon.
Definition: occluderNode.I:41
A node in the scene graph that can hold an occluder polygon, which must be a rectangle.
Definition: occluderNode.h:35
static LVector3f forward(CoordinateSystem cs=CS_default)
Returns the forward vector for the given coordinate system.
Definition: lvector3.h:565
PN_stdfloat get_min_coverage()
Returns the minimum screen coverage.
Definition: occluderNode.I:91
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:31
float length() const
Returns the length of the vector, by the Pythagorean theorem.
Definition: lvecBase3.h:765
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
This is a 4-by-4 transform matrix.
Definition: lmatrix.h:451
This functions similarly to a LightAttrib or ClipPlaneAttrib.
This represents a unique collection of RenderAttrib objects that correspond to a particular renderabl...
Definition: renderState.h:53
const LPoint3 & get_vertex(int n) const
Returns the nth vertex of the occluder polygon.
Definition: occluderNode.I:51
void ref() const
Explicitly increments the reference count.
bool is_double_sided()
Is this occluder double-sided.
Definition: occluderNode.I:70
This object holds the camera position, etc., and other general setup information for rendering a part...
Definition: sceneSetup.h:35
const LMatrix4 & get_mat() const
Returns the transform matrix that has been applied to the referenced node, or the identity matrix if ...
Definition: nodePath.I:965
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition: nodePath.h:165
This object performs a depth-first traversal of the scene graph, with optional view-frustum culling...
Definition: cullTraverser.h:48
A node that contains a plane.
Definition: planeNode.h:39
This defines a bounding convex hexahedron.