Differential D4501 Diff 14697 extern/draco/dracoenc/src/draco/mesh/mesh_stripifier.h

Changeset View

Standalone View

extern/draco/dracoenc/src/draco/mesh/mesh_stripifier.h

This file was added.

				// Copyright 2017 The Draco Authors.
				//
				// Licensed under the Apache License, Version 2.0 (the "License");
				// you may not use this file except in compliance with the License.
				// You may obtain a copy of the License at
				//
				// http://www.apache.org/licenses/LICENSE-2.0
				//
				// Unless required by applicable law or agreed to in writing, software
				// distributed under the License is distributed on an "AS IS" BASIS,
				// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
				// See the License for the specific language governing permissions and
				// limitations under the License.
				//
				#ifndef DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_
				#define DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_

				#include "draco/mesh/mesh_misc_functions.h"

				namespace draco {

				// Class that generates triangle strips from a provided draco::Mesh data
				// structure. The strips represent a more memory efficient storage of triangle
				// connectivity that can be used directly on the GPU (see
				// https://en.wikipedia.org/wiki/Triangle_strip ). In general, a mesh needs to
				// be represented by several triangle strips and it has been proven that finding
				// the optimal set of triangle strips is an NP-complete problem. The algorithm
				// implemented by this class finds this set of triangle strips based on a greedy
				// heuristic that always selects the longest available strip that covers the
				// next unprocessed face. The longest strip is found by analyzing all strips
				// that can cover the given face (three strips corresponding to three
				// directions).
				class MeshStripifier {
				public:
				MeshStripifier()
				: mesh_(nullptr),
				num_strips_(0),
				num_encoded_faces_(0),
				last_encoded_point_(kInvalidPointIndex) {}

				// Generate triangle strips for a given mesh and output them to the output
				// iterator \|out_it\|. In most cases \|out_it\| stores the values in a buffer
				// that can be used directly on the GPU. Note that the algorithm can generate
				// multiple strips to represent the whole mesh. In such cases multiple strips
				// are separated using a so called primitive restart index that is specified
				// by the \|primitive_restart_index\| (usually defined as the maximum allowed
				// value for the given type).
				// https://www.khronos.org/opengl/wiki/Vertex_Rendering#Primitive_Restart
				template <typename OutputIteratorT, typename IndexTypeT>
				bool GenerateTriangleStripsWithPrimitiveRestart(
				const Mesh &mesh, IndexTypeT primitive_restart_index,
				OutputIteratorT out_it);

				// The same as above but disjoint triangle strips are separated by degenerate
				// triangles instead of the primitive restart index. Degenerate triangles are
				// zero area triangles that are automatically discarded by the GPU. Using
				// degenerate triangles usually results in a slightly longer output indices
				// array compared to the similar triangle strips that use primitive restart
				// index. The advantage of this method is that it is supported by all hardware
				// and all relevant APIs (including WebGL 1.0).
				template <typename OutputIteratorT>
				bool GenerateTriangleStripsWithDegenerateTriangles(const Mesh &mesh,
				OutputIteratorT out_it);

				// Returns the number of strips generated by the last call of the
				// GenerateTriangleStrips() method.
				int num_strips() const { return num_strips_; }

				private:
				bool Prepare(const Mesh &mesh) {
				mesh_ = &mesh;
				num_strips_ = 0;
				num_encoded_faces_ = 0;
				// TODO(ostava): We may be able to avoid computing the corner table if we
				// already have it stored somewhere.
				corner_table_ = CreateCornerTableFromPositionAttribute(mesh_);
				if (corner_table_ == nullptr)
				return false;

				// Mark all faces as unvisited.
				is_face_visited_.assign(mesh.num_faces(), false);
				return true;
				}

				// Returns local id of the longest strip that can be created from the given
				// face \|fi\|.
				int FindLongestStripFromFace(FaceIndex fi) {
				// There are three possible strip directions that can contain the provided
				// input face. We try all of them and select the direction that result in
				// the longest strip.
				const CornerIndex first_ci = corner_table_->FirstCorner(fi);
				int longest_strip_id = -1;
				int longest_strip_length = 0;
				for (int i = 0; i < 3; ++i) {
				GenerateStripsFromCorner(i, first_ci + i);
				if (strip_faces_[i].size() > longest_strip_length) {
				longest_strip_length = static_cast<int>(strip_faces_[i].size());
				longest_strip_id = i;
				}
				}
				return longest_strip_id;
				}

				// Generates strip from the data stored in \|strip_faces_\| and
				// \|strip_start_start_corners_\| and stores it to \|out_it\|.
				template <typename OutputIteratorT>
				void StoreStrip(int local_strip_id, OutputIteratorT out_it) {
				++num_strips_;

				const int num_strip_faces = strip_faces_[local_strip_id].size();
				CornerIndex ci = strip_start_corners_[local_strip_id];
				for (int i = 0; i < num_strip_faces; ++i) {
				const FaceIndex fi = corner_table_->Face(ci);
				is_face_visited_[fi] = true;
				++num_encoded_faces_;

				if (i == 0) {
				// Add the start face (three indices).
				*out_it++ = CornerToPointIndex(ci).value();
				*out_it++ = CornerToPointIndex(corner_table_->Next(ci)).value();
				last_encoded_point_ = CornerToPointIndex(corner_table_->Previous(ci));
				*out_it++ = last_encoded_point_.value();
				} else {
				// Store the point on the newly reached corner.
				last_encoded_point_ = CornerToPointIndex(ci);
				*out_it++ = last_encoded_point_.value();

				// Go to the correct source corner to proceed to the next face.
				if (i & 1) {
				ci = corner_table_->Previous(ci);
				} else {
				ci = corner_table_->Next(ci);
				}
				}
				ci = corner_table_->Opposite(ci);
				}
				}

				PointIndex CornerToPointIndex(CornerIndex ci) const {
				return mesh_->CornerToPointId(ci);
				}

				// Returns the opposite corner in case the opposite triangle does not lie
				// across an attribute seam. Otherwise return kInvalidCornerIndex.
				CornerIndex GetOppositeCorner(CornerIndex ci) const {
				const CornerIndex oci = corner_table_->Opposite(ci);
				if (oci < 0)
				return kInvalidCornerIndex;
				// Ensure the point ids are same on both sides of the shared edge between
				// the triangles.
				if (CornerToPointIndex(corner_table_->Next(ci)) !=
				CornerToPointIndex(corner_table_->Previous(oci)))
				return kInvalidCornerIndex;
				if (CornerToPointIndex(corner_table_->Previous(ci)) !=
				CornerToPointIndex(corner_table_->Next(oci)))
				return kInvalidCornerIndex;
				return oci;
				}

				void GenerateStripsFromCorner(int local_strip_id, CornerIndex ci);

				const Mesh *mesh_;
				std::unique_ptr<CornerTable> corner_table_;

				// Store strip faces for each of three possible directions from a given face.
				std::vector<FaceIndex> strip_faces_[3];
				// Start corner for each direction of the strip containing the processed face.
				CornerIndex strip_start_corners_[3];
				IndexTypeVector<FaceIndex, bool> is_face_visited_;
				// The number of strips generated by this method.
				int num_strips_;
				// The number of encoded triangles.
				int num_encoded_faces_;
				// Last encoded point.
				PointIndex last_encoded_point_;
				};

				template <typename OutputIteratorT, typename IndexTypeT>
				bool MeshStripifier::GenerateTriangleStripsWithPrimitiveRestart(
				const Mesh &mesh, IndexTypeT primitive_restart_index,
				OutputIteratorT out_it) {
				if (!Prepare(mesh))
				return false;

				// Go over all faces and generate strips from the first unvisited one.
				for (FaceIndex fi(0); fi < mesh.num_faces(); ++fi) {
				if (is_face_visited_[fi])
				continue;

				const int longest_strip_id = FindLongestStripFromFace(fi);

				// Separate triangle strips with the primitive restart index.
				if (num_strips_ > 0) {
				*out_it++ = primitive_restart_index;
				}

				StoreStrip(longest_strip_id, out_it);
				}

				return true;
				}

				template <typename OutputIteratorT>
				bool MeshStripifier::GenerateTriangleStripsWithDegenerateTriangles(
				const Mesh &mesh, OutputIteratorT out_it) {
				if (!Prepare(mesh))
				return false;

				// Go over all faces and generate strips from the first unvisited one.
				for (FaceIndex fi(0); fi < mesh.num_faces(); ++fi) {
				if (is_face_visited_[fi])
				continue;

				const int longest_strip_id = FindLongestStripFromFace(fi);

				// Separate triangle strips by degenerate triangles. There will be either
				// three or four degenerate triangles inserted based on the number of
				// triangles that are already encoded in the output strip (three degenerate
				// triangles for even number of existing triangles, four degenerate
				// triangles for odd number of triangles).
				if (num_strips_ > 0) {
				// Duplicate last encoded index (first degenerate face).
				*out_it++ = last_encoded_point_.value();

				// Connect it to the start point of the new triangle strip (second
				// degenerate face).
				const CornerIndex new_start_corner =
				strip_start_corners_[longest_strip_id];
				const PointIndex new_start_point = CornerToPointIndex(new_start_corner);
				*out_it++ = new_start_point.value();
				num_encoded_faces_ += 2;
				// If we have previously encoded number of faces we need to duplicate the
				// point one more time to preserve the correct orientation of the next
				// strip.
				if (num_encoded_faces_ & 1) {
				*out_it++ = new_start_point.value();
				num_encoded_faces_ += 1;
				}
				// The last degenerate face will be added implicitly in the StoreStrip()
				// function below as the first point index is going to be encoded there
				// again.
				}

				StoreStrip(longest_strip_id, out_it);
				}

				return true;
				}

				} // namespace draco

				#endif // DRACO_SRC_DRACO_MESH_MESH_STRIPIFIER_H_