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 }
boundingBox.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
BoundingBox
An axis-aligned bounding box; that is, a minimum and maximum coordinate triple.
Definition: boundingBox.h:29
BoundingHexahedron
This defines a bounding convex hexahedron.
Definition: boundingHexahedron.h:32
BoundingPlane
This funny bounding volume is an infinite plane that divides space into two regions: the part behind ...
Definition: boundingPlane.h:28
ClipPlaneAttrib
This functions similarly to a LightAttrib.
Definition: clipPlaneAttrib.h:31
ClipPlaneAttrib::has_off_plane
bool has_off_plane(const NodePath &plane) const
Returns true if the indicated plane is disabled by the attrib, false otherwise.
Definition: clipPlaneAttrib.I:83
ClipPlaneAttrib::get_on_plane
get_on_plane
Returns the nth plane enabled by the attribute, sorted in render order.
Definition: clipPlaneAttrib.h:74
ClipPlaneAttrib::get_num_on_planes
get_num_on_planes
Returns the number of planes that are enabled by the attribute.
Definition: clipPlaneAttrib.h:74
CullPlanes
This represents the set of clip planes and/or occluders that are definitely in effect for the current...
Definition: cullPlanes.h:42
CullTraverserData
This collects together the pieces of data that are accumulated for each node while walking the scene ...
Definition: cullTraverserData.h:40
CullTraverser
This object performs a depth-first traversal of the scene graph, with optional view-frustum culling,...
Definition: cullTraverser.h:45
CullTraverser::draw_bounding_volume
void draw_bounding_volume(const BoundingVolume *vol, const TransformState *internal_transform) const
Draws an appropriate visualization of the indicated bounding volume.
Definition: cullTraverser.cxx:228
CullTraverser::get_scene
SceneSetup * get_scene() const
Returns the SceneSetup object.
Definition: cullTraverser.I:35
GeometricBoundingVolume
This is another abstract class, for a general class of bounding volumes that actually enclose points ...
Definition: geometricBoundingVolume.h:29
Lens
A base class for any number of different kinds of lenses, linear and otherwise.
Definition: lens.h:41
Lens::project
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
Lens::get_far
get_far
Returns the position of the far plane (or cylinder, sphere, whatever).
Definition: lens.h:114
NodePath
NodePath is the fundamental system for disambiguating instances, and also provides a higher-level int...
Definition: nodePath.h:159
NodePath::get_pos
LPoint3 get_pos() const
Retrieves the translation component of the transform.
Definition: nodePath.cxx:1040
NodePath::get_mat
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
NodePath::node
PandaNode * node() const
Returns the referenced node of the path.
Definition: nodePath.I:227
NodePath::get_transform
const TransformState * get_transform(Thread *current_thread=Thread::get_current_thread()) const
Returns the complete transform object set on this node.
Definition: nodePath.cxx:791
OccluderEffect
This functions similarly to a LightAttrib or ClipPlaneAttrib.
Definition: occluderEffect.h:32
OccluderEffect::get_num_on_occluders
get_num_on_occluders
Returns the number of occluders that are enabled by the effectute.
Definition: occluderEffect.h:42
OccluderEffect::get_on_occluder
get_on_occluder
Returns the nth occluder enabled by the effectute, sorted in render order.
Definition: occluderEffect.h:42
OccluderNode
A node in the scene graph that can hold an occluder polygon, which must be a rectangle.
Definition: occluderNode.h:31
OccluderNode::get_num_vertices
get_num_vertices
Returns the number of vertices in the occluder polygon.
Definition: occluderNode.h:59
OccluderNode::get_min_coverage
get_min_coverage
Returns the minimum screen coverage.
Definition: occluderNode.h:62
OccluderNode::is_double_sided
is_double_sided
Is this occluder double-sided.
Definition: occluderNode.h:61
OccluderNode::get_vertex
get_vertex
Returns the nth vertex of the occluder polygon.
Definition: occluderNode.h:59
PlaneNode
A node that contains a plane.
Definition: planeNode.h:36
PlaneNode::get_plane
const LPlane & get_plane() const
Returns the plane represented by the PlaneNode.
Definition: planeNode.I:54
ReferenceCount::ref
void ref() const
Explicitly increments the reference count.
Definition: referenceCount.I:151
ReferenceCount::get_ref_count
get_ref_count
Returns the current reference count.
Definition: referenceCount.h:53
RenderState
This represents a unique collection of RenderAttrib objects that correspond to a particular renderabl...
Definition: renderState.h:47
SceneSetup
This object holds the camera position, etc., and other general setup information for rendering a part...
Definition: sceneSetup.h:32
SceneSetup::get_lens
const Lens * get_lens() const
Returns the particular Lens used for rendering.
Definition: sceneSetup.I:131
SceneSetup::get_cull_center
const NodePath & get_cull_center() const
Returns the point from which the culling operations will be performed.
Definition: sceneSetup.I:161
TransformState
Indicates a coordinate-system transform on vertices.
Definition: transformState.h:54
clipPlaneAttrib.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
CPT
CPT(CullPlanes) CullPlanes
Returns a pointer to an empty CullPlanes object.
Definition: cullPlanes.cxx:27
cullPlanes.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
cullTraverserData.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
cullTraverser.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
occluderEffect.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.