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"
20 #include "graphicsStateGuardianBase.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();
95 PT(GeomTristripsAdjacency) adj = new GeomTristripsAdjacency(get_usage_hint());
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::
249 draw(GraphicsStateGuardianBase *gsg, const GeomPrimitivePipelineReader *reader,
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 */
499 void GeomTristrips::
500 register_with_read_factory() {
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 }
bamReader.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
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
bamWriter.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
BamReader
This is the fundamental interface for extracting binary objects from a Bam file, as generated by a Ba...
Definition: bamReader.h:110
BamReader::get_factory
static WritableFactory * get_factory()
Returns the global WritableFactory for generating TypedWritable objects.
Definition: bamReader.I:177
ConstPointerToArray
Similar to PointerToArray, except that its contents may not be modified.
Definition: pointerToArray.h:252
DatagramIterator
A class to retrieve the individual data elements previously stored in a Datagram.
Definition: datagramIterator.h:27
FactoryParams
An instance of this class is passed to the Factory when requesting it to do its business and construc...
Definition: factoryParams.h:36
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
GeomPrimitivePipelineReader
Encapsulates the data from a GeomPrimitive, pre-fetched for one stage of the pipeline.
Definition: geomPrimitive.h:352
GeomPrimitive
This is an abstract base class for a family of classes that represent the fundamental geometry primit...
Definition: geomPrimitive.h:56
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
GeomPrimitive::get_vertex
get_vertex
Returns the ith vertex index in the table.
Definition: geomPrimitive.h:99
GeomPrimitive::get_usage_hint
get_usage_hint
Returns the usage hint for this primitive.
Definition: geomPrimitive.h:81
GeomPrimitive::get_num_vertices
get_num_vertices
Returns the number of indices used by all the primitives in this object.
Definition: geomPrimitive.h:99
GeomPrimitive::get_first_vertex
int get_first_vertex() const
Returns the first vertex number referenced by the primitive.
Definition: geomPrimitive.I:98
GeomPrimitive::get_shade_model
get_shade_model
Returns the ShadeModel hint for this primitive.
Definition: geomPrimitive.h:77
GeomPrimitive::is_indexed
bool is_indexed() const
Returns true if the primitive is indexed, false otherwise.
Definition: geomPrimitive.I:86
GeomTriangles
Defines a series of disconnected triangles.
Definition: geomTriangles.h:23
GeomTristripsAdjacency
Defines a series of triangle strips with adjacency information.
Definition: geomTristripsAdjacency.h:25
GeomTristrips
Defines a series of triangle strips.
Definition: geomTristrips.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
GeomVertexArrayData
This is the data for one array of a GeomVertexData structure.
Definition: geomVertexArrayData.h:58
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
GeomVertexReader
This object provides a high-level interface for quickly reading a sequence of numeric values from a v...
Definition: geomVertexReader.h:47
GeomVertexWriter
This object provides a high-level interface for quickly writing a sequence of numeric values from a v...
Definition: geomVertexWriter.h:55
GraphicsStateGuardianBase
This is a base class for the GraphicsStateGuardian class, which is itself a base class for the variou...
Definition: graphicsStateGuardianBase.h:110
Thread
A thread; that is, a lightweight process.
Definition: thread.h:46
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
TypedWritable
Base class for objects that can be written to and read from Bam files.
Definition: typedWritable.h:35
geomTriangles.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
geomTristripsAdjacency.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PT
PT(GeomPrimitive) GeomTristrips
Returns the fundamental rendering type of this primitive: whether it is points, lines,...
Definition: geomTristrips.cxx:55
geomTristrips.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
geomVertexRewriter.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
graphicsStateGuardianBase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pStatTimer.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.