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