VisibilityOptimizer.cpp
Go to the documentation of this file.
1 /*
2  This file is part of the VRender library.
3  Copyright (C) 2005 Cyril Soler (Cyril.Soler@imag.fr)
4  Version 1.0.0, released on June 27, 2005.
5 
6  http://artis.imag.fr/Members/Cyril.Soler/VRender
7 
8  VRender is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 2 of the License, or
11  (at your option) any later version.
12 
13  VRender is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with VRender; if not, write to the Free Software Foundation, Inc.,
20  51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
21 */
22 
23 /****************************************************************************
24 
25  Copyright (C) 2002-2013 Gilles Debunne. All rights reserved.
26 
27  This file is part of the QGLViewer library version 2.4.0.
28 
29  http://www.libqglviewer.com - contact@libqglviewer.com
30 
31  This file may be used under the terms of the GNU General Public License
32  versions 2.0 or 3.0 as published by the Free Software Foundation and
33  appearing in the LICENSE file included in the packaging of this file.
34  In addition, as a special exception, Gilles Debunne gives you certain
35  additional rights, described in the file GPL_EXCEPTION in this package.
36 
37  libQGLViewer uses dual licensing. Commercial/proprietary software must
38  purchase a libQGLViewer Commercial License.
39 
40  This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
41  WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
42 
43 *****************************************************************************/
44 
45 #include <vector>
46 #include "VRender.h"
47 #include "Optimizer.h"
48 #include "Primitive.h"
49 #include "gpc.h"
50 #include "math.h"
51 
52 using namespace vrender ;
53 using namespace std ;
54 
55 #ifdef A_FAIRE
56 void VisibilityOptimizer::optimize(vector<PtrPrimitive>& primitives,float& percentage_finished,string& message)
57 #else
58 void VisibilityOptimizer::optimize(vector<PtrPrimitive>& primitives,VRenderParams& vparams)
59 #endif
60 {
61 #ifdef DEBUG_VO
62  cout << "Optimizing visibility." << endl ;
63 #endif
64  unsigned int N = primitives.size()/200 + 1 ;
65 
66 #ifdef DEBUG_EPSRENDER__SHOW1
67 // cout << "Showing viewer." << endl ;
68 // myViewer viewer ;
69 // viewer.show();
70  double minx = FLT_MAX ;
71  double miny = FLT_MAX ;
72  double maxx = -FLT_MAX ;
73  double maxy = -FLT_MAX ;
74  for(unsigned int i=0;i<primitives.size();++i)
75  for(int j=0;j<primitives[i]->nbVertices();++j)
76  {
77  if(maxx < primitives[i]->vertex(j).x()) maxx = primitives[i]->vertex(j).x() ;
78  if(maxy < primitives[i]->vertex(j).y()) maxy = primitives[i]->vertex(j).y() ;
79  if(minx > primitives[i]->vertex(j).x()) minx = primitives[i]->vertex(j).x() ;
80  if(miny > primitives[i]->vertex(j).y()) miny = primitives[i]->vertex(j).y() ;
81  }
82 
83  glMatrixMode(GL_PROJECTION) ;
84  glLoadIdentity() ;
85  glOrtho(minx,maxx,miny,maxy,-1,1) ;
86  glMatrixMode(GL_MODELVIEW) ;
87  glLoadIdentity() ;
88 
89  cout << "Window set to " << minx << " " << maxx << " " << miny << " " << maxy << endl ;
90  glClear(GL_DEPTH_BUFFER_BIT | GL_COLOR_BUFFER_BIT) ;
91  glLineWidth(3.0) ;
92 #endif
93 
94  int nb_culled = 0 ;
95 
96  // Ca serait pas mal mieux avec une interface c++...
97 
98  gpc_polygon cumulated_union ;
99  cumulated_union.num_contours = 0 ;
100  cumulated_union.hole = NULL ;
101  cumulated_union.contour = NULL ;
102  int nboptimised = 0 ;
103 
104  for(int pindex = (int)(primitives.size()) - 1; pindex >= 0;--pindex,++nboptimised)
105  if(primitives[pindex] != NULL)
106  {
107 #ifdef A_FAIRE
108  percentage_finished = pindex / (float)primitives.size() ;
109 #endif
110 
111  if(primitives[pindex]->nbVertices() > 1)
112  {
113 #ifdef DEBUG_VO
114  if(pindex%50==0)
115  {
116  char buff[500] ;
117  sprintf(buff,"Left: % 6ld - Culled: % 6ld", (long)pindex,(long)nb_culled) ;
118  fprintf(stdout,buff);
119 
120  for(unsigned int j=0;j<strlen(buff);++j)
121  fprintf(stdout,"\b") ;
122 
123  fflush(stdout) ;
124  }
125 #endif
126 
127  try
128  {
129  PtrPrimitive p(primitives[pindex]) ;
130  gpc_polygon difference ;
131  gpc_polygon new_poly ;
132  gpc_polygon new_poly_reduced ;
133  new_poly.num_contours = 0 ;
134  new_poly.hole = NULL ;
135  new_poly.contour = NULL ;
136  new_poly_reduced.num_contours = 0 ;
137  new_poly_reduced.hole = NULL ;
138  new_poly_reduced.contour = NULL ;
139 
140  // 1 - creates a gpc_polygon corresponding to the current primitive
141 
142  gpc_vertex_list *new_poly_verts = new gpc_vertex_list ;
143  gpc_vertex_list *new_poly_reduced_verts = new gpc_vertex_list ;
144 
145  double mx = 0.0 ;
146  double my = 0.0 ;
147 
148  if(p->nbVertices() == 2)
149  {
150  new_poly_verts->num_vertices = 4 ;
151  new_poly_verts->vertex = new gpc_vertex[4] ;
152  new_poly_reduced_verts->num_vertices = 4 ;
153  new_poly_reduced_verts->vertex = new gpc_vertex[4] ;
154 
155  double deps = 0.001 ;
156  double du = p->vertex(1).y()-p->vertex(0).y() ;
157  double dv = p->vertex(1).x()-p->vertex(0).x() ;
158  double n = sqrt(du*du+dv*dv) ;
159  du *= deps/n ;
160  dv *= deps/n ;
161  new_poly_verts->vertex[0].x = p->vertex(0).x() + du ;
162  new_poly_verts->vertex[0].y = p->vertex(0).y() + dv ;
163  new_poly_verts->vertex[1].x = p->vertex(1).x() + du ;
164  new_poly_verts->vertex[1].y = p->vertex(1).y() + dv ;
165  new_poly_verts->vertex[2].x = p->vertex(1).x() - du ;
166  new_poly_verts->vertex[2].y = p->vertex(1).y() - dv ;
167  new_poly_verts->vertex[3].x = p->vertex(0).x() - du ;
168  new_poly_verts->vertex[3].y = p->vertex(0).y() - dv ;
169 
170  new_poly_reduced_verts->vertex[0].x = p->vertex(0).x() + du ;
171  new_poly_reduced_verts->vertex[0].y = p->vertex(0).y() + dv ;
172  new_poly_reduced_verts->vertex[1].x = p->vertex(1).x() + du ;
173  new_poly_reduced_verts->vertex[1].y = p->vertex(1).y() + dv ;
174  new_poly_reduced_verts->vertex[2].x = p->vertex(1).x() - du ;
175  new_poly_reduced_verts->vertex[2].y = p->vertex(1).y() - dv ;
176  new_poly_reduced_verts->vertex[3].x = p->vertex(0).x() - du ;
177  new_poly_reduced_verts->vertex[3].y = p->vertex(0).y() - dv ;
178  }
179  else
180  {
181  new_poly_verts->num_vertices = p->nbVertices() ;
182  new_poly_verts->vertex = new gpc_vertex[p->nbVertices()] ;
183 
184  for(unsigned int i=0;i<p->nbVertices();++i)
185  {
186  new_poly_verts->vertex[i].x = p->vertex(i).x() ;
187  new_poly_verts->vertex[i].y = p->vertex(i).y() ;
188  mx += p->vertex(i).x() ;
189  my += p->vertex(i).y() ;
190  }
191  mx /= p->nbVertices() ;
192  my /= p->nbVertices() ;
193 
194  new_poly_reduced_verts->num_vertices = p->nbVertices() ;
195  new_poly_reduced_verts->vertex = new gpc_vertex[p->nbVertices()] ;
196 
197  for(unsigned int j=0;j<p->nbVertices();++j)
198  {
199  new_poly_reduced_verts->vertex[j].x = mx + (p->vertex(j).x() - mx)*0.999 ;
200  new_poly_reduced_verts->vertex[j].y = my + (p->vertex(j).y() - my)*0.999 ;
201  }
202  }
203  gpc_add_contour(&new_poly,new_poly_verts,false) ;
204  gpc_add_contour(&new_poly_reduced,new_poly_reduced_verts,false) ;
205 
206  // 2 - computes the difference between this polygon, and the union of the
207  // preceeding ones.
208 
209  gpc_polygon_clip(GPC_DIFF,&new_poly_reduced,&cumulated_union,&difference) ;
210 
211  // 3 - checks the difference. If void, the primitive is not visible: skip it
212  // and go to next primitive.
213 
214  if(difference.num_contours == 0)
215  {
216  ++nb_culled ;
217  delete p ;
218  primitives[pindex] = NULL ;
219  continue ;
220  }
221 
222  // 4 - The primitive is visible. Let's add it to the cumulated union of
223  // primitives.
224 
225  if(p->nbVertices() > 2)
226  {
227  gpc_polygon cumulated_union_tmp ;
228  cumulated_union_tmp.num_contours = 0 ;
229  cumulated_union_tmp.hole = NULL ;
230  cumulated_union_tmp.contour = NULL ;
231 
232  gpc_polygon_clip(GPC_UNION,&new_poly,&cumulated_union,&cumulated_union_tmp) ;
233 
234  gpc_free_polygon(&cumulated_union) ;
235  cumulated_union = cumulated_union_tmp ;
236  }
237 
238  gpc_free_polygon(&new_poly) ;
239  gpc_free_polygon(&new_poly_reduced) ;
240  gpc_free_polygon(&difference) ;
241 #ifdef DEBUG_EPSRENDER__SHOW1
242  glClear(GL_DEPTH_BUFFER_BIT | GL_COLOR_BUFFER_BIT) ;
243 
244  glColor3f(1.0,0.0,0.0) ;
245 
246  for(int i=0;i<cumulated_union.num_contours;++i)
247  {
248  glBegin(GL_LINE_LOOP) ;
249  for(int j=0;j<cumulated_union.contour[i].num_vertices;++j)
250  glVertex2f(cumulated_union.contour[i].vertex[j].x,cumulated_union.contour[i].vertex[j].y) ;
251  glEnd() ;
252  }
253 
254  glFlush() ;
255  glXSwapBuffers(glXGetCurrentDisplay(),glXGetCurrentDrawable()) ;
256 #endif
257  }
258  catch(exception& )
259  {
260  ; // std::cout << "Could not treat primitive " << pindex << ": internal gpc error." << endl ;
261  }
262  }
263 
264  if(nboptimised%N==0)
265  vparams.progress(nboptimised/(float)primitives.size(), QGLViewer::tr("Visibility optimization")) ;
266  }
267 
268 #ifdef DEBUG_VO
269  cout << nb_culled << " primitives culled over " << primitives.size() << "." << endl ;
270 #endif
271 
272  gpc_free_polygon(&cumulated_union) ;
273 }
274 
275 
gpc_vertex::y
double y
Definition: gpc.h:114
FLT_MAX
#define FLT_MAX
Definition: Vector3.h:51
vrender::VisibilityOptimizer::optimize
virtual void optimize(std::vector< PtrPrimitive > &, VRenderParams &)
Definition: VisibilityOptimizer.cpp:58
GPC_DIFF
Definition: gpc.h:105
gpc_polygon::contour
gpc_vertex_list * contour
Definition: gpc.h:127
gpc_vertex_list
Definition: gpc.h:117
gpc_polygon_clip
void gpc_polygon_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip, gpc_polygon *result)
Definition: gpc.cpp:1192
vrender::Vector3::x
double x() const
Definition: Vector3.h:81
vrender::VRenderParams::progress
void progress(float, const QString &)
Definition: VRender.cpp:255
gpc_polygon
Definition: gpc.h:123
gpc_vertex_list::vertex
gpc_vertex * vertex
Definition: gpc.h:120
vrender::Vector3::y
double y() const
Definition: Vector3.h:82
gpc_polygon::num_contours
int num_contours
Definition: gpc.h:125
gpc_polygon::hole
int * hole
Definition: gpc.h:126
gpc_vertex
Definition: gpc.h:111
gpc_vertex_list::num_vertices
int num_vertices
Definition: gpc.h:119
vrender::Primitive::vertex
virtual const Vector3 & vertex(int) const =0
gpc_free_polygon
void gpc_free_polygon(gpc_polygon *p)
Definition: gpc.cpp:1093
GPC_UNION
Definition: gpc.h:108
vrender::Primitive::nbVertices
virtual unsigned int nbVertices() const =0
gpc_add_contour
void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *new_contour, int hole)
Definition: gpc.cpp:1152
gpc_vertex::x
double x
Definition: gpc.h:113

octovis
Author(s): Kai M. Wurm , Armin Hornung
autogenerated on Mon Jun 10 2019 14:00:25