Panda3D
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 ////////////////////////////////////////////////////////////////////
27 CPT(CullPlanes) CullPlanes::
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 ////////////////////////////////////////////////////////////////////
47 CPT(CullPlanes) CullPlanes::
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 ////////////////////////////////////////////////////////////////////
89 CPT(CullPlanes) CullPlanes::
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
bool has_off_plane(const NodePath &plane) const
Returns true if the indicated plane is disabled by the attrib, false otherwise.
A base class for any number of different kinds of lenses, linear and otherwise.
Definition: lens.h:45
NodePath get_on_plane(int n) const
Returns the nth plane enabled by the attribute, sorted in render order.
This collects together the pieces of data that are accumulated for each node while walking the scene ...
const Lens * get_lens() const
Returns the particular Lens used for rendering.
Definition: sceneSetup.I:164
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
This represents the set of clip planes and/or occluders that are definitely in effect for the current...
Definition: cullPlanes.h:46
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:579
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
bool project(const LPoint3 &point3d, LPoint3 &point2d) const
Given a 3-d point in space, determine the 2-d point this maps to, in the range (-1,1) in both dimensions, where (0,0) is the center of the lens and (-1,-1) is the lower-left corner.
Definition: lens.I:168
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
NodePath find(const string &path) const
Searches for a node below the referenced node that matches the indicated string.
Definition: nodePath.cxx:434
int get_num_on_planes() const
Returns the number of planes that are enabled by the attribute.
This is a 4-by-4 transform matrix.
Definition: lmatrix.h:451
const LPlane & get_plane() const
Returns the plane represented by the PlaneNode.
Definition: planeNode.I:65
This functions similarly to a LightAttrib or ClipPlaneAttrib.
NodePath get_on_occluder(int n) const
Returns the nth occluder enabled by the effectute, sorted in render order.
int get_num_vertices() const
Returns the number of vertices in the occluder polygon.
Definition: occluderNode.I:41
LPoint3 get_pos() const
Retrieves the translation component of the transform.
Definition: nodePath.cxx:1178
void ref() const
Explicitly increments the reference count.
This represents a unique collection of RenderAttrib objects that correspond to a particular renderabl...
Definition: renderState.h:53
int get_ref_count() const
Returns the current reference count.
float length() const
Returns the length of the vector, by the Pythagorean theorem.
Definition: lvecBase3.h:766
const NodePath & get_cull_center() const
Returns the point from which the culling operations will be performed.
Definition: sceneSetup.I:203
PandaNode * node() const
Returns the referenced node of the path.
Definition: nodePath.I:284
SceneSetup * get_scene() const
Returns the SceneSetup object.
Definition: cullTraverser.I:43
int get_num_on_occluders() const
Returns the number of occluders that are enabled by the effectute.
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
bool is_double_sided()
Is this occluder double-sided.
Definition: occluderNode.I:70
void draw_bounding_volume(const BoundingVolume *vol, const TransformState *internal_transform) const
Draws an appropriate visualization of the indicated bounding volume.
const TransformState * get_transform(Thread *current_thread=Thread::get_current_thread()) const
Returns the complete transform object set on this node.
Definition: nodePath.cxx:925
This object holds the camera position, etc., and other general setup information for rendering a part...
Definition: sceneSetup.h:35
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
PN_stdfloat get_far() const
Returns the position of the far plane (or cylinder, sphere, whatever).
Definition: lens.I:522
A node that contains a plane.
Definition: planeNode.h:39
This defines a bounding convex hexahedron.
const LPoint3 & get_vertex(int n) const
Returns the nth vertex of the occluder polygon.
Definition: occluderNode.I:51