TrinityCore
G3D::ConvexPolygon Class Reference

`#include <ConvexPolyhedron.h>`

## Public Member Functions

ConvexPolygon ()

ConvexPolygon (const Vector3 &v0, const Vector3 &v1, const Vector3 &v2)

ConvexPolygon (const Array< Vector3 > &__vertex)

virtual ~ConvexPolygon ()

const Vector3vertex (int i) const

void setVertex (int i, const Vector3 &v)

int numVertices () const

void setNumVertices (int n)

bool isEmpty () const

void cut (const Plane &plane, ConvexPolygon &above, ConvexPolygon &below, DirectedEdge &newEdge)

void cut (const Plane &plane, ConvexPolygon &above, ConvexPolygon &below)

void removeDuplicateVertices ()

float getArea () const

Vector3 normal () const

ConvexPolygon inverse () const

## Private Attributes

Array< Vector3_vertex

## Friends

class ConvexPolyhedron

## Constructor & Destructor Documentation

 G3D::ConvexPolygon::ConvexPolygon ( )
inline
41 {}
 G3D::ConvexPolygon::ConvexPolygon ( const Vector3 & v0, const Vector3 & v1, const Vector3 & v2 )
24  {
25  _vertex.append(v0, v1, v2);
26 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
 G3D::ConvexPolygon::ConvexPolygon ( const Array< Vector3 > & __vertex )
19  : _vertex(__vertex) {
20  // Intentionally empty
21 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
 virtual G3D::ConvexPolygon::~ConvexPolygon ( )
inlinevirtual
44 {}

## Member Function Documentation

 void G3D::ConvexPolygon::cut ( const Plane & plane, ConvexPolygon & above, ConvexPolygon & below, DirectedEdge & newEdge )

Cuts the polygon at the plane. If the polygon is entirely above or below the plane, one of the returned polygons will be empty.

Parameters
 above The part of the polygon above (on the side the normal points to or in the plane) the plane below The part of the polygon below the plane. newEdge If a new edge was introduced, this is that edge (on the above portion; the below portion is the opposite winding.
60  {
61  above._vertex.resize(0);
62  below._vertex.resize(0);
63
64  if (isEmpty()) {
65  //debugPrintf("Empty\n");
66  return;
67  }
68
69  int v = 0;
70  int length = _vertex.length();
71
72
73  Vector3 polyNormal = normal();
74  Vector3 planeNormal= plane.normal();
75
76  // See if the polygon is *in* the plane.
77  if (planeNormal.fuzzyEq(polyNormal) || planeNormal.fuzzyEq(-polyNormal)) {
78  // Polygon is parallel to the plane. It must be either above,
79  // below, or in the plane.
80
81  double a, b, c, d;
82  Vector3 pt = _vertex[0];
83
84  plane.getEquation(a,b,c,d);
85  float r = (float)(a * pt.x + b * pt.y + c * pt.z + d);
86
87  if (fuzzyGe(r, 0)) {
88  // The polygon is entirely in the plane.
89  //debugPrintf("Entirely above\n");
90  above = *this;
91  return;
92  } else {
93  //debugPrintf("Entirely below (1)\n");
94  below = *this;
95  return;
96  }
97  }
98
99
100  // Number of edges crossing the plane. Used for
101  // debug assertions.
102  int count = 0;
103
104  // True when the last _vertex we looked at was above the plane
105  bool lastAbove = plane.halfSpaceContains(_vertex[v]);
106
107  if (lastAbove) {
108  above._vertex.append(_vertex[v]);
109  } else {
110  below._vertex.append(_vertex[v]);
111  }
112
113  for (v = 1; v < length; ++v) {
114  bool isAbove = plane.halfSpaceContains(_vertex[v]);
115
116  if (lastAbove ^ isAbove) {
117  // Switched sides.
118  // Create an interpolated point that lies
119  // in the plane, between the two points.
120  Line line = Line::fromTwoPoints(_vertex[v - 1], _vertex[v]);
121  Vector3 interp = line.intersection(plane);
122
123  if (! interp.isFinite()) {
124
125  // Since the polygon is not in the plane (we checked above),
126  // it must be the case that this edge (and only this edge)
127  // is in the plane. This only happens when the polygon is
128  // entirely below the plane except for one edge. This edge
129  // forms a degenerate polygon, so just treat the whole polygon
130  // as below the plane.
131  below = *this;
132  above._vertex.resize(0);
133  //debugPrintf("Entirely below\n");
134  return;
135  }
136
137  above._vertex.append(interp);
138  below._vertex.append(interp);
139  if (lastAbove) {
140  newEdge.stop = interp;
141  } else {
142  newEdge.start = interp;
143  }
144  ++count;
145  }
146
147  lastAbove = isAbove;
148  if (lastAbove) {
149  above._vertex.append(_vertex[v]);
150  } else {
151  below._vertex.append(_vertex[v]);
152  }
153  }
154
155  // Loop back to the first point, seeing if an interpolated point is
156  // needed.
157  bool isAbove = plane.halfSpaceContains(_vertex[0]);
158  if (lastAbove ^ isAbove) {
159  Line line = Line::fromTwoPoints(_vertex[length - 1], _vertex[0]);
160  Vector3 interp = line.intersection(plane);
161  if (! interp.isFinite()) {
162  // Since the polygon is not in the plane (we checked above),
163  // it must be the case that this edge (and only this edge)
164  // is in the plane. This only happens when the polygon is
165  // entirely below the plane except for one edge. This edge
166  // forms a degenerate polygon, so just treat the whole polygon
167  // as below the plane.
168  below = *this;
169  above._vertex.resize(0);
170  //debugPrintf("Entirely below\n");
171  return;
172  }
173
174  above._vertex.append(interp);
175  below._vertex.append(interp);
176  debugAssertM(count < 2, "Convex polygons may only intersect planes at two edges.");
177  if (lastAbove) {
178  newEdge.stop = interp;
179  } else {
180  newEdge.start = interp;
181  }
182  ++count;
183  }
184
185  debugAssertM((count == 2) || (count == 0), "Convex polygons may only intersect planes at two edges.");
186 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
#define debugAssertM(exp, message)
Definition: debugAssert.h:161
float length(float v)
Definition: vectorMath.h:208
bool isEmpty() const
Definition: ConvexPolyhedron.cpp:29
bool fuzzyGe(double a, double b)
Definition: g3dmath.h:869
static Line fromTwoPoints(const Vector3 &point1, const Vector3 &point2)
Definition: Line.h:52
Vector3 normal() const
Definition: ConvexPolyhedron.h:100

Here is the call graph for this function:

Here is the caller graph for this function:

 void G3D::ConvexPolygon::cut ( const Plane & plane, ConvexPolygon & above, ConvexPolygon & below )
55  {
56  DirectedEdge edge;
57  cut(plane, above, below, edge);
58 }
void cut(const Plane &plane, ConvexPolygon &above, ConvexPolygon &below, DirectedEdge &newEdge)
Definition: ConvexPolyhedron.cpp:60

Here is the call graph for this function:

 float G3D::ConvexPolygon::getArea ( ) const

O(n) in the number of edges

34  {
35
36  if (_vertex.length() < 3) {
37  return 0;
38  }
39
40  float sum = 0;
41
42  int length = _vertex.length();
43  // Split into triangle fan, compute individual area
44  for (int v = 2; v < length; ++v) {
45  int i0 = 0;
46  int i1 = v - 1;
47  int i2 = v;
48
49  sum += (_vertex[i1] - _vertex[i0]).cross(_vertex[i2] - _vertex[i0]).magnitude() / 2;
50  }
51
52  return sum;
53 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
float magnitude() const
Definition: Vector3.h:746
float length(float v)
Definition: vectorMath.h:208
Vector3 cross(const Vector3 &v1, const Vector3 &v2)
Definition: vectorMath.h:144

Here is the call graph for this function:

Here is the caller graph for this function:

 ConvexPolygon G3D::ConvexPolygon::inverse ( ) const

Returns the same polygon with inverse winding.

189  {
190  ConvexPolygon result;
191  int length = _vertex.length();
192  result._vertex.resize(length);
193
194  for (int v = 0; v < length; ++v) {
195  result._vertex[v] = _vertex[length - v - 1];
196  }
197
198  return result;
199 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
ConvexPolygon()
Definition: ConvexPolyhedron.h:41
float length(float v)
Definition: vectorMath.h:208

Here is the call graph for this function:

Here is the caller graph for this function:

 bool G3D::ConvexPolygon::isEmpty ( ) const

O(n) in the number of edges

29  {
30  return (_vertex.length() == 0) || (getArea() <= fuzzyEpsilon32);
31 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
float getArea() const
Definition: ConvexPolyhedron.cpp:34
#define fuzzyEpsilon32
Definition: g3dmath.h:132

Here is the call graph for this function:

Here is the caller graph for this function:

 Vector3 G3D::ConvexPolygon::normal ( ) const
inline
100  {
101  debugAssert(_vertex.length() >= 3);
102  return (_vertex[1] - _vertex[0]).cross(_vertex[2] - _vertex[0]).direction();
103  }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
#define debugAssert(exp)
Definition: debugAssert.h:160

Here is the call graph for this function:

Here is the caller graph for this function:

 int G3D::ConvexPolygon::numVertices ( ) const
inline

Zero vertices indicates an empty polygon (zero area).

60  {
61  return _vertex.size();
62  }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37

Here is the call graph for this function:

 void G3D::ConvexPolygon::removeDuplicateVertices ( )

When a cut plane grazes a vertex in the polygon, two near-identical vertices may be created. The closeness of these two points can cause a number of problems, such as ConvexPolygon::normal() returning an infinite vector. It should be noted, however, that not all applications are sensitive to near-identical vertices.

removeDuplicateVertices() detects and eliminates redundant vertices.

202  {
203  // Any valid polygon should have 3 or more vertices, but why take chances?
204  if (_vertex.size() >= 2){
205
206  // Remove duplicate vertices.
207  for (int i=0;i<_vertex.size()-1;++i){
208  if (_vertex[i].fuzzyEq(_vertex[i+1])){
209  _vertex.remove(i+1);
210  --i; // Don't move forward.
211  }
212  }
213
214  // Check the last vertex against the first.
215  if (_vertex[_vertex.size()-1].fuzzyEq(_vertex[0])){
216  _vertex.pop();
217  }
218  }
219 }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
bool fuzzyEq(double a, double b)
Definition: g3dmath.h:857

Here is the call graph for this function:

 void G3D::ConvexPolygon::setNumVertices ( int n )
inline
64  {
65  _vertex.resize(n);
66  }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37

Here is the call graph for this function:

 void G3D::ConvexPolygon::setVertex ( int i, const Vector3 & v )
inline
53  {
54  _vertex[i] = v;
55  }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37
 const Vector3& G3D::ConvexPolygon::vertex ( int i ) const
inline

Counter clockwise winding order.

49  {
50  return _vertex[i];
51  }
Array< Vector3 > _vertex
Definition: ConvexPolyhedron.h:37

## Friends And Related Function Documentation

 friend class ConvexPolyhedron
friend

## Member Data Documentation

 Array G3D::ConvexPolygon::_vertex
private

The documentation for this class was generated from the following files: