Panda3D
geomTristrips.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 geomTristrips.cxx
10  * @author drose
11  * @date 2005-03-08
12  */
13 
14 #include "geomTristrips.h"
15 #include "geomTriangles.h"
16 #include "geomVertexRewriter.h"
17 #include "pStatTimer.h"
18 #include "bamReader.h"
19 #include "bamWriter.h"
21 #include "geomTristripsAdjacency.h"
22 
23 using std::map;
24 
25 TypeHandle GeomTristrips::_type_handle;
26 
27 /**
28  *
29  */
30 GeomTristrips::
31 GeomTristrips(GeomTristrips::UsageHint usage_hint) :
32  GeomPrimitive(usage_hint)
33 {
34 }
35 
36 /**
37  *
38  */
39 GeomTristrips::
40 GeomTristrips(const GeomTristrips &copy) :
41  GeomPrimitive(copy)
42 {
43 }
44 
45 /**
46  *
47  */
48 GeomTristrips::
49 ~GeomTristrips() {
50 }
51 
52 /**
53  *
54  */
55 PT(GeomPrimitive) GeomTristrips::
56 make_copy() const {
57  return new GeomTristrips(*this);
58 }
59 
60 /**
61  * Returns the fundamental rendering type of this primitive: whether it is
62  * points, lines, or polygons.
63  *
64  * This is used to set up the appropriate antialiasing settings when
65  * AntialiasAttrib::M_auto is in effect; it also implies the type of primitive
66  * that will be produced when decompose() is called.
67  */
68 GeomPrimitive::PrimitiveType GeomTristrips::
69 get_primitive_type() const {
70  return PT_polygons;
71 }
72 
73 /**
74  * Returns the set of GeomRendering bits that represent the rendering
75  * properties required to properly render this primitive.
76  */
77 int GeomTristrips::
78 get_geom_rendering() const {
79  if (is_indexed()) {
80  return GR_triangle_strip | GR_indexed_other;
81  } else {
82  return GR_triangle_strip;
83  }
84 }
85 
86 /**
87  * Adds adjacency information to this primitive. May return null if this type
88  * of geometry does not support adjacency information.
89  */
90 CPT(GeomPrimitive) GeomTristrips::
91 make_adjacency() const {
92  using std::make_pair;
93 
94  Thread *current_thread = Thread::get_current_thread();
96  CPTA_int ends = get_ends();
97 
98  GeomPrimitivePipelineReader from(this, current_thread);
99  int num_vertices = from.get_num_vertices();
100  const int num_unused = 2;
101 
102  // First, build a map of each triangle's halfedges to its opposing vertices.
103  map<std::pair<int, int>, int> edge_map;
104 
105  int vi = -num_unused;
106  int li = 0;
107  while (li < (int)ends.size()) {
108  // Skip unused vertices between tristrips.
109  vi += num_unused;
110  int end = ends[li];
111  nassertr(vi + 2 <= end, nullptr);
112 
113  int v0 = from.get_vertex(vi++);
114  int v1 = from.get_vertex(vi++);
115  int v2 = from.get_vertex(vi);
116  edge_map[make_pair(v0, v1)] = v2;
117 
118  while (true) {
119  v2 = from.get_vertex(vi++);
120  edge_map[make_pair(v2, v0)] = v1;
121 
122  if (vi >= end) {
123  // Edge at the end of the strip
124  edge_map[make_pair(v1, v2)] = v0;
125  break;
126  }
127 
128  v0 = v1;
129  v1 = v2;
130  v2 = from.get_vertex(vi++);
131  edge_map[make_pair(v0, v2)] = v1;
132 
133  if (vi >= end) {
134  // Edge at the end of the strip
135  edge_map[make_pair(v2, v1)] = v0;
136  break;
137  }
138 
139  v0 = v1;
140  v1 = v2;
141  }
142  ++li;
143  }
144  nassertr(vi == num_vertices, nullptr);
145 
146  // Now build up the new vertex data. For each edge, we insert the
147  // appropriate connecting vertex.
148  vi = -num_unused;
149  li = 0;
150  while (li < (int)ends.size()) {
151  // Skip unused vertices between tristrips.
152  vi += num_unused;
153  int end = ends[li];
154  nassertr(vi + 2 <= end, nullptr);
155 
156  int v0 = from.get_vertex(vi++);
157  int v1 = from.get_vertex(vi++);
158  int v2;
159  adj->add_vertex(v0);
160 
161  // Get the third vertex of the triangle adjoining this edge.
162  auto it = edge_map.find(make_pair(v1, v0));
163  if (it != edge_map.end()) {
164  adj->add_vertex(it->second);
165  } else {
166  // Um, no adjoining triangle? Just repeat the vertex, I guess.
167  adj->add_vertex(v0);
168  }
169  adj->add_vertex(v1);
170 
171  while (true) {
172  v2 = from.get_vertex(vi++);
173  it = edge_map.find(make_pair(v0, v2));
174  if (it != edge_map.end()) {
175  adj->add_vertex(it->second);
176  } else {
177  adj->add_vertex(v1);
178  }
179  adj->add_vertex(v2);
180 
181  if (vi >= end) {
182  // Edge at the end of the strip
183  it = edge_map.find(make_pair(v2, v1));
184  if (it != edge_map.end()) {
185  adj->add_vertex(it->second);
186  } else {
187  adj->add_vertex(v2);
188  }
189  break;
190  }
191 
192  v0 = v1;
193  v1 = v2;
194  v2 = from.get_vertex(vi++);
195  it = edge_map.find(make_pair(v2, v0));
196  if (it != edge_map.end()) {
197  adj->add_vertex(it->second);
198  } else {
199  adj->add_vertex(v1);
200  }
201  adj->add_vertex(v2);
202 
203  if (vi >= end) {
204  // Edge at the end of the strip
205  it = edge_map.find(make_pair(v1, v2));
206  if (it != edge_map.end()) {
207  adj->add_vertex(it->second);
208  } else {
209  adj->add_vertex(v1);
210  }
211  break;
212  }
213 
214  v0 = v1;
215  v1 = v2;
216  }
217  adj->close_primitive();
218  ++li;
219  }
220  nassertr(vi == num_vertices, nullptr);
221 
222  return adj;
223 }
224 
225 /**
226  * Returns the minimum number of vertices that must be added before
227  * close_primitive() may legally be called.
228  */
229 int GeomTristrips::
230 get_min_num_vertices_per_primitive() const {
231  return 3;
232 }
233 
234 /**
235  * Returns the number of vertices that are added between primitives that
236  * aren't, strictly speaking, part of the primitives themselves. This is
237  * used, for instance, to define degenerate triangles to connect otherwise
238  * disconnected triangle strips.
239  */
240 int GeomTristrips::
241 get_num_unused_vertices_per_primitive() const {
242  return 2;
243 }
244 
245 /**
246  * Calls the appropriate method on the GSG to draw the primitive.
247  */
248 bool GeomTristrips::
250  bool force) const {
251  return gsg->draw_tristrips(reader, force);
252 }
253 
254 /**
255  * Decomposes a complex primitive type into a simpler primitive type, for
256  * instance triangle strips to triangles, and returns a pointer to the new
257  * primitive definition. If the decomposition cannot be performed, this might
258  * return the original object.
259  *
260  * This method is useful for application code that wants to iterate through
261  * the set of triangles on the primitive without having to write handlers for
262  * each possible kind of primitive type.
263  */
264 CPT(GeomPrimitive) GeomTristrips::
265 decompose_impl() const {
266  PT(GeomTriangles) triangles = new GeomTriangles(get_usage_hint());
267  triangles->set_shade_model(get_shade_model());
268  CPTA_int ends = get_ends();
269 
270  int num_vertices = get_num_vertices();
271  int num_unused = get_num_unused_vertices_per_primitive();
272 
273  // We need a slightly different algorithm for SM_flat_first_vertex than for
274  // SM_flat_last_vertex, to preserve the key vertex in the right place. The
275  // remaining shade models can use either algorithm.
276  if (get_shade_model() == SM_flat_first_vertex) {
277  // Preserve the first vertex of each component triangle as the first
278  // vertex of each generated triangle.
279  int vi = -num_unused;
280  int li = 0;
281  while (li < (int)ends.size()) {
282  // Skip unused vertices between tristrips.
283  vi += num_unused;
284  int end = ends[li];
285  nassertr(vi + 2 <= end, nullptr);
286  int v0 = get_vertex(vi);
287  ++vi;
288  int v1 = get_vertex(vi);
289  ++vi;
290  bool reversed = false;
291  while (vi < end) {
292  int v2 = get_vertex(vi);
293  ++vi;
294  if (reversed) {
295  if (v0 != v1 && v0 != v2 && v1 != v2) {
296  triangles->add_vertex(v0);
297  triangles->add_vertex(v2);
298  triangles->add_vertex(v1);
299  triangles->close_primitive();
300  }
301  reversed = false;
302  } else {
303  if (v0 != v1 && v0 != v2 && v1 != v2) {
304  triangles->add_vertex(v0);
305  triangles->add_vertex(v1);
306  triangles->add_vertex(v2);
307  triangles->close_primitive();
308  }
309  reversed = true;
310  }
311  v0 = v1;
312  v1 = v2;
313  }
314  ++li;
315  }
316  nassertr(vi == num_vertices, nullptr);
317 
318  } else {
319  // Preserve the last vertex of each component triangle as the last vertex
320  // of each generated triangle.
321  int vi = -num_unused;
322  int li = 0;
323  while (li < (int)ends.size()) {
324  // Skip unused vertices between tristrips.
325  vi += num_unused;
326  int end = ends[li];
327  nassertr(vi + 2 <= end, nullptr);
328  int v0 = get_vertex(vi);
329  ++vi;
330  int v1 = get_vertex(vi);
331  ++vi;
332  bool reversed = false;
333  while (vi < end) {
334  int v2 = get_vertex(vi);
335  if (reversed) {
336  if (v0 != v1 && v0 != v2 && v1 != v2) {
337  triangles->add_vertex(v1);
338  triangles->add_vertex(v0);
339  triangles->add_vertex(v2);
340  triangles->close_primitive();
341  }
342  reversed = false;
343  } else {
344  if (v0 != v1 && v0 != v2 && v1 != v2) {
345  triangles->add_vertex(v0);
346  triangles->add_vertex(v1);
347  triangles->add_vertex(v2);
348  triangles->close_primitive();
349  }
350  reversed = true;
351  }
352  ++vi;
353  v0 = v1;
354  v1 = v2;
355  }
356  ++li;
357  }
358  nassertr(vi == num_vertices, nullptr);
359  }
360 
361  return triangles;
362 }
363 
364 /**
365  * The virtual implementation of doubleside().
366  */
367 CPT(GeomPrimitive) GeomTristrips::
368 doubleside_impl() const {
369  // TODO: implement this properly as triangle strips, without requiring a
370  // decompose operation first.
371  return decompose_impl()->doubleside();
372 }
373 
374 /**
375  * The virtual implementation of reverse().
376  */
377 CPT(GeomPrimitive) GeomTristrips::
378 reverse_impl() const {
379  // TODO: implement this properly as triangle strips, without requiring a
380  // decompose operation first.
381  return decompose_impl()->reverse();
382 }
383 
384 /**
385  * The virtual implementation of do_rotate().
386  */
387 CPT(GeomVertexArrayData) GeomTristrips::
388 rotate_impl() const {
389  // To rotate a triangle strip with an even number of vertices, we just
390  // reverse the vertices. But if we have an odd number of vertices, that
391  // doesn't work--in fact, nothing works (without also changing the winding
392  // order), so we don't allow an odd number of vertices in a flat-shaded
393  // tristrip.
394  CPTA_int ends = get_ends();
395 
396  PT(GeomVertexArrayData) new_vertices = make_index_data();
397  new_vertices->set_num_rows(get_num_vertices());
398 
399  if (is_indexed()) {
400  CPT(GeomVertexArrayData) vertices = get_vertices();
401  GeomVertexReader from(vertices, 0);
402  GeomVertexWriter to(new_vertices, 0);
403 
404  int begin = 0;
405  int last_added = 0;
406  CPTA_int::const_iterator ei;
407  for (ei = ends.begin(); ei != ends.end(); ++ei) {
408  int end = (*ei);
409  int num_vertices = end - begin;
410 
411  if (begin != 0) {
412  // Copy in the unused vertices between tristrips.
413  to.set_data1i(last_added);
414  from.set_row_unsafe(end - 1);
415  to.set_data1i(from.get_data1i());
416  begin += 2;
417  }
418 
419  // If this assertion is triggered, there was a triangle strip with an
420  // odd number of vertices, which is not allowed.
421  nassertr((num_vertices & 1) == 0, nullptr);
422  for (int vi = end - 1; vi >= begin; --vi) {
423  from.set_row_unsafe(vi);
424  last_added = from.get_data1i();
425  to.set_data1i(last_added);
426  }
427 
428  begin = end;
429  }
430 
431  nassertr(to.is_at_end(), nullptr);
432 
433  } else {
434  // Nonindexed case.
435  int first_vertex = get_first_vertex();
436  GeomVertexWriter to(new_vertices, 0);
437 
438  int begin = 0;
439  int last_added = 0;
440  CPTA_int::const_iterator ei;
441  for (ei = ends.begin(); ei != ends.end(); ++ei) {
442  int end = (*ei);
443  int num_vertices = end - begin;
444 
445  if (begin != 0) {
446  // Copy in the unused vertices between tristrips.
447  to.set_data1i(last_added);
448  to.set_data1i(end - 1 + first_vertex);
449  begin += 2;
450  }
451 
452  // If this assertion is triggered, there was a triangle strip with an
453  // odd number of vertices, which is not allowed.
454  nassertr((num_vertices & 1) == 0, nullptr);
455  for (int vi = end - 1; vi >= begin; --vi) {
456  last_added = vi + first_vertex;
457  to.set_data1i(last_added);
458  }
459 
460  begin = end;
461  }
462 
463  nassertr(to.is_at_end(), nullptr);
464  }
465  return new_vertices;
466 }
467 
468 /**
469  * Should be redefined to return true in any primitive that implements
470  * append_unused_vertices().
471  */
472 bool GeomTristrips::
473 requires_unused_vertices() const {
474  return true;
475 }
476 
477 /**
478  * Called when a new primitive is begun (other than the first primitive), this
479  * should add some degenerate vertices between primitives, if the primitive
480  * type requires that. The second parameter is the first vertex that begins
481  * the new primitive.
482  */
483 void GeomTristrips::
484 append_unused_vertices(GeomVertexArrayData *vertices, int vertex) {
485  GeomVertexReader from(vertices, 0);
486  from.set_row_unsafe(vertices->get_num_rows() - 1);
487  int prev = from.get_data1i();
488 
489  GeomVertexWriter to(vertices, 0);
490  to.set_row_unsafe(vertices->get_num_rows());
491 
492  to.add_data1i(prev);
493  to.add_data1i(vertex);
494 }
495 
496 /**
497  * Tells the BamReader how to create objects of type Geom.
498  */
501  BamReader::get_factory()->register_factory(get_class_type(), make_from_bam);
502 }
503 
504 /**
505  * This function is called by the BamReader's factory when a new object of
506  * type Geom is encountered in the Bam file. It should create the Geom and
507  * extract its information from the file.
508  */
509 TypedWritable *GeomTristrips::
510 make_from_bam(const FactoryParams &params) {
511  GeomTristrips *object = new GeomTristrips(UH_unspecified);
512  DatagramIterator scan;
513  BamReader *manager;
514 
515  parse_params(params, scan, manager);
516  object->fillin(scan, manager);
517 
518  return object;
519 }
GeomVertexArrayData
This is the data for one array of a GeomVertexData structure.
Definition: geomVertexArrayData.h:58
GeomPrimitive::get_first_vertex
int get_first_vertex() const
Returns the first vertex number referenced by the primitive.
Definition: geomPrimitive.I:98
DatagramIterator
A class to retrieve the individual data elements previously stored in a Datagram.
Definition: datagramIterator.h:27
BamReader
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:110
geomTristripsAdjacency.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pStatTimer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GeomVertexWriter
This object provides a high-level interface for quickly writing a sequence of numeric values from a v...
Definition: geomVertexWriter.h:55
ConstPointerToArray
Similar to PointerToArray, except that its contents may not be modified.
Definition: pointerToArray.h:250
GeomVertexReader
This object provides a high-level interface for quickly reading a sequence of numeric values from a v...
Definition: geomVertexReader.h:47
BamReader::get_factory
static WritableFactory * get_factory()
Returns the global WritableFactory for generating TypedWritable objects.
Definition: bamReader.I:177
bamReader.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GeomPrimitive::get_vertex
get_vertex
Returns the ith vertex index in the table.
Definition: geomPrimitive.h:99
TypedWritable
Base class for objects that can be written to and read from Bam files.
Definition: typedWritable.h:35
Thread::get_current_thread
get_current_thread
Returns a pointer to the currently-executing Thread object.
Definition: thread.h:109
TypeHandle
TypeHandle is the identifier used to differentiate C++ class types.
Definition: typeHandle.h:81
FactoryParams
An instance of this class is passed to the Factory when requesting it to do its business and construc...
Definition: factoryParams.h:36
GeomVertexArrayData::get_num_rows
int get_num_rows() const
Returns the number of rows stored in the array, based on the number of bytes and the stride.
Definition: geomVertexArrayData.I:47
GeomPrimitive::get_num_vertices
get_num_vertices
Returns the number of indices used by all the primitives in this object.
Definition: geomPrimitive.h:99
GeomTristripsAdjacency
Defines a series of triangle strips with adjacency information.
Definition: geomTristripsAdjacency.h:25
geomVertexRewriter.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
geomTriangles.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GeomPrimitive::get_shade_model
get_shade_model
Returns the ShadeModel hint for this primitive.
Definition: geomPrimitive.h:77
Factory::register_factory
void register_factory(TypeHandle handle, CreateFunc *func, void *user_data=nullptr)
Registers a new kind of thing the Factory will be able to create.
Definition: factory.I:73
PT
PT(GeomPrimitive) GeomTristrips
Returns the fundamental rendering type of this primitive: whether it is points, lines,...
Definition: geomTristrips.cxx:55
GeomTriangles
Defines a series of disconnected triangles.
Definition: geomTriangles.h:23
GeomTristrips::register_with_read_factory
static void register_with_read_factory()
Tells the BamReader how to create objects of type Geom.
Definition: geomTristrips.cxx:500
GeomTristrips
Defines a series of triangle strips.
Definition: geomTristrips.h:23
geomTristrips.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
GraphicsStateGuardianBase
This is a base class for the GraphicsStateGuardian class, which is itself a base class for the variou...
Definition: graphicsStateGuardianBase.h:110
GeomPrimitive::get_ends
CPTA_int get_ends() const
Returns a const pointer to the primitive ends array so application code can read it directly.
Definition: geomPrimitive.I:314
GeomPrimitivePipelineReader
Encapsulates the data from a GeomPrimitive, pre-fetched for one stage of the pipeline.
Definition: geomPrimitive.h:352
GeomPrimitive::is_indexed
bool is_indexed() const
Returns true if the primitive is indexed, false otherwise.
Definition: geomPrimitive.I:86
bamWriter.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
graphicsStateGuardianBase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
Thread
A thread; that is, a lightweight process.
Definition: thread.h:46
GeomPrimitive::get_usage_hint
get_usage_hint
Returns the usage hint for this primitive.
Definition: geomPrimitive.h:81
parse_params
void parse_params(const FactoryParams &params, DatagramIterator &scan, BamReader *&manager)
Takes in a FactoryParams, passed from a WritableFactory into any TypedWritable's make function,...
Definition: bamReader.I:275
GeomPrimitive
This is an abstract base class for a family of classes that represent the fundamental geometry primit...
Definition: geomPrimitive.h:56