root/OpenSceneGraph/trunk/src/osg/ShadowVolumeOccluder.cpp @ 13041

Revision 13041, 11.2 kB (checked in by robert, 2 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13#include <osg/ShadowVolumeOccluder>
14#include <osg/CullStack>
15
16#include <osg/Group>
17#include <osg/Geode>
18
19using namespace osg;
20
21
22
23typedef std::pair<unsigned int,Vec3>    Point; // bool=true signifies a newly created point, false indicates original point.
24typedef std::vector<Point>      PointList;
25typedef std::vector<Vec3>       VertexList;
26
27
28// copyVertexListToPointList a vector for Vec3 into a vector of Point's.
29void copyVertexListToPointList(const VertexList& in,PointList& out)
30{
31    out.reserve(in.size());
32    for(VertexList::const_iterator itr=in.begin();
33        itr!=in.end();
34        ++itr)
35    {
36        out.push_back(Point(0,*itr));
37    }
38}
39
40void copyPointListToVertexList(const PointList& in,VertexList& out)
41{
42    out.reserve(in.size());
43    for(PointList::const_iterator itr=in.begin();
44        itr!=in.end();
45        ++itr)
46    {
47        out.push_back(itr->second);
48    }
49}
50
51// clip the convex hull 'in' to plane to generate a clipped convex hull 'out'
52// return true if points remain after clipping.
53unsigned int clip(const Plane& plane,const PointList& in, PointList& out,unsigned int planeMask)
54{
55    std::vector<float> distance;
56    distance.reserve(in.size());
57    for(PointList::const_iterator itr=in.begin();
58        itr!=in.end();
59        ++itr)
60    {
61        distance.push_back(plane.distance(itr->second));
62    }
63
64    out.clear();
65
66    for(unsigned int i=0;i<in.size();++i)
67    {
68        unsigned int i_1 = (i+1)%in.size(); // do the mod to wrap the index round back to the start.
69
70        if (distance[i]>=0.0f)
71        {
72            out.push_back(in[i]);
73
74
75            if (distance[i_1]<0.0f)
76            {
77                unsigned int mask = (in[i].first & in[i_1].first) | planeMask;
78                float r = distance[i_1]/(distance[i_1]-distance[i]);
79                out.push_back(Point(mask,in[i].second*r+in[i_1].second*(1.0f-r)));
80            }
81
82        }
83        else if (distance[i_1]>0.0f)
84        {
85            unsigned int mask = (in[i].first & in[i_1].first) | planeMask;
86            float r = distance[i_1]/(distance[i_1]-distance[i]);
87            out.push_back(Point(mask,in[i].second*r+in[i_1].second*(1.0f-r)));
88        }
89    }
90
91    return out.size();
92}
93
94// clip the convex hull 'in' to planeList to generate a clipped convex hull 'out'
95// return true if points remain after clipping.
96unsigned int clip(const Polytope::PlaneList& planeList,const VertexList& vin,PointList& out)
97{
98    PointList in;
99    copyVertexListToPointList(vin,in);
100
101    unsigned int planeMask = 0x1;
102    for(Polytope::PlaneList::const_iterator itr=planeList.begin();
103        itr!=planeList.end();
104        ++itr)
105    {
106        if (!clip(*itr,in,out,planeMask)) return false;
107        in.swap(out);
108        planeMask <<= 1;
109    }
110
111    in.swap(out);
112
113    return out.size();
114}
115
116void transform(PointList& points,const osg::Matrix& matrix)
117{
118    for(PointList::iterator itr=points.begin();
119        itr!=points.end();
120        ++itr)
121    {
122        itr->second = itr->second*matrix;
123    }
124}
125
126void transform(const PointList& in,PointList& out,const osg::Matrix& matrix)
127{
128    for(PointList::const_iterator itr=in.begin();
129        itr!=in.end();
130        ++itr)
131    {
132        out.push_back(Point(itr->first,itr->second * matrix));
133    }
134}
135
136void pushToFarPlane(PointList& points)
137{
138    for(PointList::iterator itr=points.begin();
139        itr!=points.end();
140        ++itr)
141    {
142        itr->second.z() = 1.0f;
143    }
144}
145
146void computePlanes(const PointList& front, const PointList& back, Polytope::PlaneList& planeList)
147{
148    for(unsigned int i=0;i<front.size();++i)
149    {
150        unsigned int i_1 = (i+1)%front.size(); // do the mod to wrap the index round back to the start.
151        if (!(front[i].first & front[i_1].first))
152        {
153            planeList.push_back(Plane(front[i].second,front[i_1].second,back[i].second));
154        }
155    }
156}
157
158Plane computeFrontPlane(const PointList& front)
159{
160    return Plane(front[2].second,front[1].second,front[0].second);
161}
162
163// compute the volume between the front and back polygons of the occluder/hole.
164float computePolytopeVolume(const PointList& front, const PointList& back)
165{
166    float volume = 0.0f;
167    Vec3 frontStart = front[0].second;
168    Vec3 backStart = back[0].second;
169    for(unsigned int i=1;i<front.size()-1;++i)
170    {
171        volume += computeVolume(frontStart, front[i].second, front[i+1].second,
172                                backStart, back[i].second, back[i+1].second);
173    }
174    return volume;
175}
176
177bool ShadowVolumeOccluder::computeOccluder(const NodePath& nodePath,const ConvexPlanarOccluder& occluder,CullStack& cullStack,bool /*createDrawables*/)
178{
179
180
181//    std::cout<<"    Computing Occluder"<<std::endl;
182
183    CullingSet& cullingset = cullStack.getCurrentCullingSet();
184
185    const RefMatrix& MV = *cullStack.getModelViewMatrix();
186    const RefMatrix& P = *cullStack.getProjectionMatrix();
187
188    // take a reference to the NodePath to this occluder.
189    _nodePath = nodePath;
190
191    // take a reference to the projection matrix.
192    _projectionMatrix = &P;
193
194    // initialize the volume
195    _volume = 0.0f;
196
197
198    // compute the inverse of the projection matrix.
199    Matrix invP;
200    invP.invert(P);
201
202    float volumeview = cullStack.getFrustumVolume();
203
204
205    // compute the transformation matrix which takes form local coords into clip space.
206    Matrix MVP(MV*P);
207
208    // for the occluder polygon and each of the holes do
209    //     first transform occluder polygon into clipspace by multiple it by c[i] = v[i]*(MV*P)
210    //     then push to coords to far plane by setting its coord to c[i].z = -1.
211    //     then transform far plane polygon back into projection space, by p[i]*inv(P)
212    //     compute orientation of front plane, if normal.z()<0 then facing away from eye pont, so reverse the polygons, or simply invert planes.
213    //     compute volume (quality) betwen front polygon in projection space and back polygon in projection space.
214
215
216    const VertexList& vertices_in = occluder.getOccluder().getVertexList();
217
218    PointList points;
219
220    if (clip(cullingset.getFrustum().getPlaneList(),vertices_in,points)>=3)
221    {
222        // compute the points on the far plane.
223        PointList farPoints;
224        farPoints.reserve(points.size());
225        transform(points,farPoints,MVP);
226        pushToFarPlane(farPoints);
227        transform(farPoints,invP);
228
229        // move the occlude points into projection space.
230        transform(points,MV);
231
232        // use the points on the front plane as reference vertices on the _occluderVolume
233        // so that the vertices can later by used to test for occlusion of the occluder itself.
234        copyPointListToVertexList(points,_occluderVolume.getReferenceVertexList());
235
236        // create the front face of the occluder
237        Plane occludePlane = computeFrontPlane(points);
238        _occluderVolume.add(occludePlane);
239
240        // create the sides of the occluder
241        computePlanes(points,farPoints,_occluderVolume.getPlaneList());
242
243        _occluderVolume.setupMask();
244
245        // if the front face is pointing away from the eye point flip the whole polytope.
246        if (occludePlane[3]>0.0f)
247        {
248            _occluderVolume.flip();
249        }
250
251        _volume = computePolytopeVolume(points,farPoints)/volumeview;
252
253
254        for(ConvexPlanarOccluder::HoleList::const_iterator hitr=occluder.getHoleList().begin();
255            hitr!=occluder.getHoleList().end();
256            ++hitr)
257        {
258            PointList points;
259            if (clip(cullingset.getFrustum().getPlaneList(),hitr->getVertexList(),points)>=3)
260            {
261                _holeList.push_back(Polytope());
262                Polytope& polytope = _holeList.back();
263
264                // compute the points on the far plane.
265                PointList farPoints;
266                farPoints.reserve(points.size());
267                transform(points,farPoints,MVP);
268                pushToFarPlane(farPoints);
269                transform(farPoints,invP);
270
271                // move the occlude points into projection space.
272                transform(points,MV);
273
274                // use the points on the front plane as reference vertices on the _occluderVolume
275                // so that the vertices can later by used to test for occlusion of the occluder itself.
276                copyPointListToVertexList(points,polytope.getReferenceVertexList());
277
278                // create the front face of the occluder
279                Plane occludePlane = computeFrontPlane(points);
280
281                // create the sides of the occluder
282                computePlanes(points,farPoints,polytope.getPlaneList());
283
284                polytope.setupMask();
285
286                // if the front face is pointing away from the eye point flip the whole polytope.
287                if (occludePlane[3]>0.0f)
288                {
289                    polytope.flip();
290                }
291
292                // remove the hole's volume from the occluder volume.
293                _volume -= computePolytopeVolume(points,farPoints)/volumeview;
294            }
295
296        }
297
298        //std::cout << "final volume = "<<_volume<<std::endl;
299
300        return true;
301    }
302    return false;
303}
304
305bool ShadowVolumeOccluder::contains(const std::vector<Vec3>& vertices)
306{
307    if (_occluderVolume.containsAllOf(vertices))
308    {
309        for(HoleList::iterator itr=_holeList.begin();
310            itr!=_holeList.end();
311            ++itr)
312        {
313            PointList points;
314            if (clip(itr->getPlaneList(),vertices,points)>=3) return false;
315        }
316        return true;
317    }
318    return false;
319}
320
321bool ShadowVolumeOccluder::contains(const BoundingSphere& bound)
322{
323    //std::cout << "Sphere testing occluder "<<this<<" mask="<<_occluderVolume.getCurrentMask();
324    if (_occluderVolume.containsAllOf(bound))
325    {
326        for(HoleList::iterator itr=_holeList.begin();
327            itr!=_holeList.end();
328            ++itr)
329        {
330            if (itr->contains(bound))
331            {
332                //std::cout << " - not in occluder"<<std::endl;
333                return false;
334            }
335        }
336        //std::cout << " - in occluder ******"<<std::endl;
337        return true;
338    }
339    //std::cout << " - not in occluder"<<std::endl;
340    return false;
341}
342
343bool ShadowVolumeOccluder::contains(const BoundingBox& bound)
344{
345    //std::cout << "Box testing occluder "<<this<<" mask="<<_occluderVolume.getCurrentMask();
346    if (_occluderVolume.containsAllOf(bound))
347    {
348        for(HoleList::iterator itr=_holeList.begin();
349            itr!=_holeList.end();
350            ++itr)
351        {
352            if (itr->contains(bound))
353            {
354                //std::cout << " + not in occluder"<<std::endl;
355                return false;
356            }
357        }
358        //std::cout << "+ in occluder ********"<<std::endl;
359        return true;
360    }
361    //std::cout << "+ not in occluder"<<std::endl;
362    return false;
363}
Note: See TracBrowser for help on using the browser.