LoopBlinnLocalTriangulator.cpp [plain text]
#include "config.h"
#if ENABLE(ACCELERATED_2D_CANVAS)
#include "LoopBlinnLocalTriangulator.h"
#include "LoopBlinnMathUtils.h"
#include <algorithm>
namespace WebCore {
using LoopBlinnMathUtils::approxEqual;
using LoopBlinnMathUtils::linesIntersect;
using LoopBlinnMathUtils::pointInTriangle;
bool LoopBlinnLocalTriangulator::Triangle::contains(LoopBlinnLocalTriangulator::Vertex* v)
{
return indexForVertex(v) >= 0;
}
LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* current, bool traverseCounterClockwise)
{
int index = indexForVertex(current);
ASSERT(index >= 0);
if (traverseCounterClockwise)
++index;
else
--index;
if (index < 0)
index += 3;
else
index = index % 3;
return m_vertices[index];
}
int LoopBlinnLocalTriangulator::Triangle::indexForVertex(LoopBlinnLocalTriangulator::Vertex* vertex)
{
for (int i = 0; i < 3; ++i)
if (m_vertices[i] == vertex)
return i;
return -1;
}
void LoopBlinnLocalTriangulator::Triangle::makeCounterClockwise()
{
FloatPoint3D point0(m_vertices[0]->xyCoordinates());
FloatPoint3D point1(m_vertices[1]->xyCoordinates());
FloatPoint3D point2(m_vertices[2]->xyCoordinates());
FloatPoint3D crossProduct = (point1 - point0).cross(point2 - point0);
if (crossProduct.z() < 0)
std::swap(m_vertices[1], m_vertices[2]);
}
LoopBlinnLocalTriangulator::LoopBlinnLocalTriangulator()
{
reset();
}
void LoopBlinnLocalTriangulator::reset()
{
m_numberOfTriangles = 0;
m_numberOfInteriorVertices = 0;
for (int i = 0; i < 4; ++i) {
m_interiorVertices[i] = 0;
m_vertices[i].resetFlags();
}
}
void LoopBlinnLocalTriangulator::triangulate(InsideEdgeComputation computeInsideEdges, LoopBlinnConstants::FillSide sideToFill)
{
triangulateHelper(sideToFill);
if (computeInsideEdges == ComputeInsideEdges) {
Vertex* v = &m_vertices[0];
addInteriorVertex(v);
int numSteps = 0;
while (!v->end() && numSteps < 4) {
bool gotNext = false;
for (int i = 0; i < numberOfTriangles() && !gotNext; ++i) {
Triangle* tri = getTriangle(i);
if (tri->contains(v)) {
Vertex* next = tri->nextVertex(v, sideToFill == LoopBlinnConstants::RightSide);
if (!next->marked() && !isSharedEdge(v, next) && (!next->interior() || next->end())) {
addInteriorVertex(next);
v = next;
gotNext = true;
}
}
}
++numSteps;
}
if (!v->end()) {
addInteriorVertex(&m_vertices[3]);
}
}
}
void LoopBlinnLocalTriangulator::triangulateHelper(LoopBlinnConstants::FillSide sideToFill)
{
reset();
m_vertices[3].setEnd(true);
for (int i = 0; i < 4; ++i) {
for (int j = i + 1; j < 4; ++j) {
if (approxEqual(m_vertices[i].xyCoordinates(), m_vertices[j].xyCoordinates())) {
int indices[3] = { 0 };
int index = 0;
for (int k = 0; k < 4; ++k)
if (k != j)
indices[index++] = k;
addTriangle(&m_vertices[indices[0]],
&m_vertices[indices[1]],
&m_vertices[indices[2]]);
return;
}
}
}
for (int i = 0; i < 4; ++i) {
int indices[3] = { 0 };
int index = 0;
for (int j = 0; j < 4; ++j)
if (i != j)
indices[index++] = j;
if (pointInTriangle(m_vertices[i].xyCoordinates(),
m_vertices[indices[0]].xyCoordinates(),
m_vertices[indices[1]].xyCoordinates(),
m_vertices[indices[2]].xyCoordinates())) {
for (int j = 0; j < 3; ++j)
addTriangle(&m_vertices[indices[j % 3]],
&m_vertices[indices[(j + 1) % 3]],
&m_vertices[i]);
m_vertices[i].setInterior(true);
return;
}
}
if (linesIntersect(m_vertices[0].xyCoordinates(),
m_vertices[2].xyCoordinates(),
m_vertices[1].xyCoordinates(),
m_vertices[3].xyCoordinates())) {
if ((m_vertices[2].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() <
(m_vertices[3].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) {
addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]);
addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]);
} else {
addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]);
addTriangle(&m_vertices[1], &m_vertices[2], &m_vertices[3]);
}
} else if (linesIntersect(m_vertices[0].xyCoordinates(),
m_vertices[3].xyCoordinates(),
m_vertices[1].xyCoordinates(),
m_vertices[2].xyCoordinates())) {
if ((m_vertices[3].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() <
(m_vertices[2].xyCoordinates() - m_vertices[1].xyCoordinates()).diagonalLengthSquared()) {
addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]);
addTriangle(&m_vertices[0], &m_vertices[3], &m_vertices[2]);
} else {
addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[2]);
addTriangle(&m_vertices[2], &m_vertices[1], &m_vertices[3]);
}
} else {
if ((m_vertices[1].xyCoordinates() - m_vertices[0].xyCoordinates()).diagonalLengthSquared() <
(m_vertices[3].xyCoordinates() - m_vertices[2].xyCoordinates()).diagonalLengthSquared()) {
addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[1]);
addTriangle(&m_vertices[0], &m_vertices[1], &m_vertices[3]);
} else {
addTriangle(&m_vertices[0], &m_vertices[2], &m_vertices[3]);
addTriangle(&m_vertices[3], &m_vertices[2], &m_vertices[1]);
}
}
}
void LoopBlinnLocalTriangulator::addTriangle(Vertex* v0, Vertex* v1, Vertex* v2)
{
ASSERT(m_numberOfTriangles < 3);
m_triangles[m_numberOfTriangles++].setVertices(v0, v1, v2);
}
void LoopBlinnLocalTriangulator::addInteriorVertex(Vertex* v)
{
ASSERT(m_numberOfInteriorVertices < 4);
m_interiorVertices[m_numberOfInteriorVertices++] = v;
v->setMarked(true);
}
bool LoopBlinnLocalTriangulator::isSharedEdge(Vertex* v0, Vertex* v1)
{
bool haveEdge01 = false;
bool haveEdge10 = false;
for (int i = 0; i < numberOfTriangles(); ++i) {
Triangle* tri = getTriangle(i);
if (tri->contains(v0) && tri->nextVertex(v0, true) == v1)
haveEdge01 = true;
if (tri->contains(v1) && tri->nextVertex(v1, true) == v0)
haveEdge10 = true;
}
return haveEdge01 && haveEdge10;
}
}
#endif