/src/assimp/code/Common/PolyTools.h

Source (jump to first uncovered line)
/*
Open Asset Import Library (assimp)
----------------------------------------------------------------------

Copyright (c) 2006-2024, assimp team

All rights reserved.

Redistribution and use of this software in source and binary forms,
with or without modification, are permitted provided that the
following conditions are met:

* Redistributions of source code must retain the above
  copyright notice, this list of conditions and the
  following disclaimer.

* Redistributions in binary form must reproduce the above
  copyright notice, this list of conditions and the
  following disclaimer in the documentation and/or other
  materials provided with the distribution.

* Neither the name of the assimp team, nor the names of its
  contributors may be used to endorse or promote products
  derived from this software without specific prior
  written permission of the assimp team.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

----------------------------------------------------------------------
*/

/** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */

#pragma once
#ifndef AI_POLYTOOLS_H_INCLUDED
#define AI_POLYTOOLS_H_INCLUDED

#include <assimp/material.h>
#include <assimp/ai_assert.h>

namespace Assimp {

// -------------------------------------------------------------------------------
/** Compute the signed area of a triangle.
 *  The function accepts an unconstrained template parameter for use with
 *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
template <typename T>
inline double GetArea2D(const T& v1, const T& v2, const T& v3) {
    return 0.5 * (v1.x * ((double)v3.y - v2.y) + v2.x * ((double)v1.y - v3.y) + v3.x * ((double)v2.y - v1.y));
}

// -------------------------------------------------------------------------------
/** Test if a given point p2 is on the left side of the line formed by p0-p1.
 *  The function accepts an unconstrained template parameter for use with
 *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
template <typename T>
inline int OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2) {
    double area = GetArea2D(p0,p2,p1);
    if(std::abs(area) < ai_epsilon)
        return 0;
    else if(area > 0)
        return 1;
    else
        return -1;
}

// -------------------------------------------------------------------------------
/** Test if a given point is inside a given triangle in R2.
 * The function accepts an unconstrained template parameter for use with
 *  both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
template <typename T>
inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp) {
    // pp should be left side of the three triangle side, by ccw arrow
    int c1 = OnLeftSideOfLine2D(p0, p1, pp);
    int c2 = OnLeftSideOfLine2D(p1, p2, pp);
    int c3 = OnLeftSideOfLine2D(p2, p0, pp);
    return (c1 >= 0) && (c2 >= 0) && (c3 >= 0);
}


// -------------------------------------------------------------------------------
/** Check whether the winding order of a given polygon is counter-clockwise.
 *  The function accepts an unconstrained template parameter, but is intended
 *  to be used only with aiVector2D and aiVector3D (z axis is ignored, only
 *  x and y are taken into account).
 * @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++
 */
template <typename T>
inline bool IsCCW(T* in, size_t npoints) {
    double aa, bb, cc, b, c, theta;
    double convex_turn;
    double convex_sum = 0;

    ai_assert(npoints >= 3);

    for (size_t i = 0; i < npoints - 2; i++) {
        aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) +
            ((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y));

        bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) +
            ((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y));

        cc = ((in[i+2].x - in[i+1].x) *
            (in[i+2].x - in[i+1].x)) +
            ((-in[i+2].y + in[i+1].y) *
            (-in[i+2].y + in[i+1].y));

        b = std::sqrt(bb);
        c = std::sqrt(cc);
        theta = std::acos((bb + cc - aa) / (2 * b * c));

        if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1]) == 1) {
            //  if (convex(in[i].x, in[i].y,
            //      in[i+1].x, in[i+1].y,
            //      in[i+2].x, in[i+2].y)) {
            convex_turn = AI_MATH_PI_F - theta;
            convex_sum += convex_turn;
        } else {
            convex_sum -= AI_MATH_PI_F - theta;
        }
    }
    aa = ((in[1].x - in[npoints-2].x) *
        (in[1].x - in[npoints-2].x)) +
        ((-in[1].y + in[npoints-2].y) *
        (-in[1].y + in[npoints-2].y));

    bb = ((in[0].x - in[npoints-2].x) *
        (in[0].x - in[npoints-2].x)) +
        ((-in[0].y + in[npoints-2].y) *
        (-in[0].y + in[npoints-2].y));

    cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) +
        ((-in[1].y + in[0].y) * (-in[1].y + in[0].y));

    b = std::sqrt(bb);
    c = std::sqrt(cc);
    theta = std::acos((bb + cc - aa) / (2 * b * c));

    //if (convex(in[npoints-2].x, in[npoints-2].y,
    //  in[0].x, in[0].y,
    //  in[1].x, in[1].y)) {
    if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0]) == 1) {
        convex_turn = AI_MATH_PI_F - theta;
        convex_sum += convex_turn;
    } else {
        convex_sum -= AI_MATH_PI_F - theta;
    }

    return convex_sum >= (2 * AI_MATH_PI_F);
}

// -------------------------------------------------------------------------------
/** Compute the normal of an arbitrary polygon in R3.
 *
 *  The code is based on Newell's formula, that is a polygons normal is the ratio
 *  of its area when projected onto the three coordinate axes.
 *
 *  @param out Receives the output normal
 *  @param num Number of input vertices
 *  @param x X data source. x[ofs_x*n] is the n'th element.
 *  @param y Y data source. y[ofs_y*n] is the y'th element
 *  @param z Z data source. z[ofs_z*n] is the z'th element
 *
 *  @note The data arrays must have storage for at least num+2 elements. Using
 *  this method is much faster than the 'other' NewellNormal()
 */
template <int ofs_x, int ofs_y, int ofs_z, typename TReal>
inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z) {
    // Duplicate the first two vertices at the end
    x[(num+0)*ofs_x] = x[0];
    x[(num+1)*ofs_x] = x[ofs_x];

    y[(num+0)*ofs_y] = y[0];
    y[(num+1)*ofs_y] = y[ofs_y];

    z[(num+0)*ofs_z] = z[0];
    z[(num+1)*ofs_z] = z[ofs_z];

    TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0;

    TReal *xptr = x +ofs_x, *xlow = x, *xhigh = x + ofs_x*2;
    TReal *yptr = y +ofs_y, *ylow = y, *yhigh = y + ofs_y*2;
    TReal *zptr = z +ofs_z, *zlow = z, *zhigh = z + ofs_z*2;

    for (int tmp=0; tmp < num; tmp++) {
        sum_xy += (*xptr) * ( (*yhigh) - (*ylow) );
        sum_yz += (*yptr) * ( (*zhigh) - (*zlow) );
        sum_zx += (*zptr) * ( (*xhigh) - (*xlow) );

        xptr  += ofs_x;
        xlow  += ofs_x;
        xhigh += ofs_x;

        yptr  += ofs_y;
        ylow  += ofs_y;
        yhigh += ofs_y;

        zptr  += ofs_z;
        zlow  += ofs_z;
        zhigh += ofs_z;
    }
    out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy);
}

} // ! namespace Assimp

#endif // AI_POLYTOOLS_H_INCLUDED

Coverage Report

Created: 2024-08-02 07:04

Line	Count	Source (jump to first uncovered line)
1		/*
2		Open Asset Import Library (assimp)
3		----------------------------------------------------------------------
4
5		Copyright (c) 2006-2024, assimp team
6
7		All rights reserved.
8
9		Redistribution and use of this software in source and binary forms,
10		with or without modification, are permitted provided that the
11		following conditions are met:
12
13		* Redistributions of source code must retain the above
14		copyright notice, this list of conditions and the
15		following disclaimer.
16
17		* Redistributions in binary form must reproduce the above
18		copyright notice, this list of conditions and the
19		following disclaimer in the documentation and/or other
20		materials provided with the distribution.
21
22		* Neither the name of the assimp team, nor the names of its
23		contributors may be used to endorse or promote products
24		derived from this software without specific prior
25		written permission of the assimp team.
26
27		THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28		"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29		LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30		A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31		OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32		SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33		LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34		DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35		THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36		(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37		OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38
39		----------------------------------------------------------------------
40		*/
41
42		/** @file PolyTools.h, various utilities for our dealings with arbitrary polygons */
43
44		#pragma once
45		#ifndef AI_POLYTOOLS_H_INCLUDED
46		#define AI_POLYTOOLS_H_INCLUDED
47
48		#include <assimp/material.h>
49		#include <assimp/ai_assert.h>
50
51		namespace Assimp {
52
53		// -------------------------------------------------------------------------------
54		/** Compute the signed area of a triangle.
55		* The function accepts an unconstrained template parameter for use with
56		* both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
57		template <typename T>
58	0	inline double GetArea2D(const T& v1, const T& v2, const T& v3) {
59	0	return 0.5 * (v1.x * ((double)v3.y - v2.y) + v2.x * ((double)v1.y - v3.y) + v3.x * ((double)v2.y - v1.y));
60	0	}
61
62		// -------------------------------------------------------------------------------
63		/** Test if a given point p2 is on the left side of the line formed by p0-p1.
64		* The function accepts an unconstrained template parameter for use with
65		* both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
66		template <typename T>
67	0	inline int OnLeftSideOfLine2D(const T& p0, const T& p1,const T& p2) {
68	0	double area = GetArea2D(p0,p2,p1);
69	0	if(std::abs(area) < ai_epsilon)
70	0	return 0;
71	0	else if(area > 0)
72	0	return 1;
73	0	else
74	0	return -1;
75	0	}
76
77		// -------------------------------------------------------------------------------
78		/** Test if a given point is inside a given triangle in R2.
79		* The function accepts an unconstrained template parameter for use with
80		* both aiVector3D and aiVector2D, but generally ignores the third coordinate.*/
81		template <typename T>
82	0	inline bool PointInTriangle2D(const T& p0, const T& p1,const T& p2, const T& pp) {
83		// pp should be left side of the three triangle side, by ccw arrow
84	0	int c1 = OnLeftSideOfLine2D(p0, p1, pp);
85	0	int c2 = OnLeftSideOfLine2D(p1, p2, pp);
86	0	int c3 = OnLeftSideOfLine2D(p2, p0, pp);
87	0	return (c1 >= 0) && (c2 >= 0) && (c3 >= 0);
88	0	}
89
90
91		// -------------------------------------------------------------------------------
92		/** Check whether the winding order of a given polygon is counter-clockwise.
93		* The function accepts an unconstrained template parameter, but is intended
94		* to be used only with aiVector2D and aiVector3D (z axis is ignored, only
95		* x and y are taken into account).
96		* @note Code taken from http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html and translated to C++
97		*/
98		template <typename T>
99		inline bool IsCCW(T* in, size_t npoints) {
100		double aa, bb, cc, b, c, theta;
101		double convex_turn;
102		double convex_sum = 0;
103
104		ai_assert(npoints >= 3);
105
106		for (size_t i = 0; i < npoints - 2; i++) {
107		aa = ((in[i+2].x - in[i].x) * (in[i+2].x - in[i].x)) +
108		((-in[i+2].y + in[i].y) * (-in[i+2].y + in[i].y));
109
110		bb = ((in[i+1].x - in[i].x) * (in[i+1].x - in[i].x)) +
111		((-in[i+1].y + in[i].y) * (-in[i+1].y + in[i].y));
112
113		cc = ((in[i+2].x - in[i+1].x) *
114		(in[i+2].x - in[i+1].x)) +
115		((-in[i+2].y + in[i+1].y) *
116		(-in[i+2].y + in[i+1].y));
117
118		b = std::sqrt(bb);
119		c = std::sqrt(cc);
120		theta = std::acos((bb + cc - aa) / (2 * b * c));
121
122		if (OnLeftSideOfLine2D(in[i],in[i+2],in[i+1]) == 1) {
123		// if (convex(in[i].x, in[i].y,
124		// in[i+1].x, in[i+1].y,
125		// in[i+2].x, in[i+2].y)) {
126		convex_turn = AI_MATH_PI_F - theta;
127		convex_sum += convex_turn;
128		} else {
129		convex_sum -= AI_MATH_PI_F - theta;
130		}
131		}
132		aa = ((in[1].x - in[npoints-2].x) *
133		(in[1].x - in[npoints-2].x)) +
134		((-in[1].y + in[npoints-2].y) *
135		(-in[1].y + in[npoints-2].y));
136
137		bb = ((in[0].x - in[npoints-2].x) *
138		(in[0].x - in[npoints-2].x)) +
139		((-in[0].y + in[npoints-2].y) *
140		(-in[0].y + in[npoints-2].y));
141
142		cc = ((in[1].x - in[0].x) * (in[1].x - in[0].x)) +
143		((-in[1].y + in[0].y) * (-in[1].y + in[0].y));
144
145		b = std::sqrt(bb);
146		c = std::sqrt(cc);
147		theta = std::acos((bb + cc - aa) / (2 * b * c));
148
149		//if (convex(in[npoints-2].x, in[npoints-2].y,
150		// in[0].x, in[0].y,
151		// in[1].x, in[1].y)) {
152		if (OnLeftSideOfLine2D(in[npoints-2],in[1],in[0]) == 1) {
153		convex_turn = AI_MATH_PI_F - theta;
154		convex_sum += convex_turn;
155		} else {
156		convex_sum -= AI_MATH_PI_F - theta;
157		}
158
159		return convex_sum >= (2 * AI_MATH_PI_F);
160		}
161
162		// -------------------------------------------------------------------------------
163		/** Compute the normal of an arbitrary polygon in R3.
164		*
165		* The code is based on Newell's formula, that is a polygons normal is the ratio
166		* of its area when projected onto the three coordinate axes.
167		*
168		* @param out Receives the output normal
169		* @param num Number of input vertices
170		* @param x X data source. x[ofs_x*n] is the n'th element.
171		* @param y Y data source. y[ofs_y*n] is the y'th element
172		* @param z Z data source. z[ofs_z*n] is the z'th element
173		*
174		* @note The data arrays must have storage for at least num+2 elements. Using
175		* this method is much faster than the 'other' NewellNormal()
176		*/
177		template <int ofs_x, int ofs_y, int ofs_z, typename TReal>
178	0	inline void NewellNormal (aiVector3t<TReal>& out, int num, TReal* x, TReal* y, TReal* z) {
179		// Duplicate the first two vertices at the end
180	0	x[(num+0)*ofs_x] = x[0];
181	0	x[(num+1)*ofs_x] = x[ofs_x];
182
183	0	y[(num+0)*ofs_y] = y[0];
184	0	y[(num+1)*ofs_y] = y[ofs_y];
185
186	0	z[(num+0)*ofs_z] = z[0];
187	0	z[(num+1)*ofs_z] = z[ofs_z];
188
189	0	TReal sum_xy = 0.0, sum_yz = 0.0, sum_zx = 0.0;
190
191	0	TReal xptr = x +ofs_x, xlow = x, xhigh = x + ofs_x2;
192	0	TReal yptr = y +ofs_y, ylow = y, yhigh = y + ofs_y2;
193	0	TReal zptr = z +ofs_z, zlow = z, zhigh = z + ofs_z2;
194
195	0	for (int tmp=0; tmp < num; tmp++) {
196	0	sum_xy += (xptr) ( (yhigh) - (ylow) );
197	0	sum_yz += (yptr) ( (zhigh) - (zlow) );
198	0	sum_zx += (zptr) ( (xhigh) - (xlow) );
199
200	0	xptr += ofs_x;
201	0	xlow += ofs_x;
202	0	xhigh += ofs_x;
203
204	0	yptr += ofs_y;
205	0	ylow += ofs_y;
206	0	yhigh += ofs_y;
207
208	0	zptr += ofs_z;
209	0	zlow += ofs_z;
210	0	zhigh += ofs_z;
211	0	}
212	0	out = aiVector3t<TReal>(sum_yz,sum_zx,sum_xy);
213	0	} Unexecuted instantiation: void Assimp::NewellNormal<3, 3, 3, double>(aiVector3t<double>&, int, double, double, double) Unexecuted instantiation: void Assimp::NewellNormal<4, 4, 4, double>(aiVector3t<double>&, int, double, double, double) Unexecuted instantiation: void Assimp::NewellNormal<3, 3, 3, float>(aiVector3t<float>&, int, float, float, float*)
214
215		} // ! namespace Assimp
216
217		#endif // AI_POLYTOOLS_H_INCLUDED