LoopBlinnPathProcessor.cpp [plain text]
#include "config.h"
#include "LoopBlinnPathProcessor.h"
#include "FloatPoint.h"
#include "FloatRect.h"
#include "LoopBlinnClassifier.h"
#include "LoopBlinnConstants.h"
#include "LoopBlinnLocalTriangulator.h"
#include "LoopBlinnMathUtils.h"
#include "LoopBlinnPathCache.h"
#include "LoopBlinnTextureCoords.h"
#include "PODArena.h"
#include "PODIntervalTree.h"
#include "Path.h"
#include "internal_glu.h"
#include <algorithm>
#include <wtf/Assertions.h>
#include <wtf/FastMalloc.h>
#include <wtf/UnusedParam.h>
#if USE(SKIA)
#include "SkGeometry.h"
#include "SkPath.h"
#include "SkScalar.h"
#else
#endif
namespace WebCore {
using LoopBlinnMathUtils::XRay;
using LoopBlinnMathUtils::chopCubicAt;
using LoopBlinnMathUtils::numXRayCrossingsForCubic;
using LoopBlinnMathUtils::trianglesOverlap;
using LoopBlinnMathUtils::xRayCrossesLine;
using LoopBlinnPathProcessorImplementation::Contour;
using LoopBlinnPathProcessorImplementation::Segment;
namespace {
#ifndef NDEBUG
String valueToString(const FloatRect& arg)
{
StringBuilder builder;
builder.append("[FloatRect x=");
builder.append(String::number(arg.x()));
builder.append(" y=");
builder.append(String::number(arg.y()));
builder.append(" maxX=");
builder.append(String::number(arg.maxX()));
builder.append(" maxY=");
builder.append(String::number(arg.maxY()));
builder.append("]");
return builder.toString();
}
#endif
struct SweepData;
}
namespace LoopBlinnPathProcessorImplementation {
class Segment;
}
#ifndef NDEBUG
template <>
struct ValueToString<float> {
static String string(const float& value)
{
return String::number(value);
}
};
template <>
struct ValueToString<SweepData*> {
static String string(SweepData* const& value)
{
return String::format("0x%p", value);
}
};
template <>
struct ValueToString<LoopBlinnPathProcessorImplementation::Segment*> {
static String string(LoopBlinnPathProcessorImplementation::Segment* const& value)
{
return String::format("0x%p", value);
}
};
#endif
namespace LoopBlinnPathProcessorImplementation {
class Segment {
WTF_MAKE_NONCOPYABLE(Segment);
public:
enum Kind {
Cubic,
Line
};
Segment()
: m_arena(0)
, m_kind(Cubic)
, m_prev(0)
, m_next(0)
, m_contour(0)
, m_triangulator(0)
, m_markedForSubdivision(false)
{
}
void setup(PODArena* arena,
Contour* contour,
FloatPoint cp0,
FloatPoint cp1,
FloatPoint cp2,
FloatPoint cp3)
{
m_arena = arena;
m_contour = contour;
m_kind = Cubic;
m_points[0] = cp0;
m_points[1] = cp1;
m_points[2] = cp2;
m_points[3] = cp3;
computeBoundingBox();
}
void setup(PODArena* arena,
Contour* contour,
FloatPoint p0,
FloatPoint p1)
{
m_arena = arena;
m_contour = contour;
m_kind = Line;
m_points[0] = p0;
m_points[1] = p1;
computeBoundingBox();
}
Kind kind() const { return m_kind; }
const FloatPoint& getPoint(int i)
{
ASSERT(i >= 0 && i < 4);
return m_points[i];
}
Segment* next() const { return m_next; }
Segment* prev() const { return m_prev; }
void setNext(Segment* next) { m_next = next; }
void setPrev(Segment* prev) { m_prev = prev; }
Contour* contour() const { return m_contour; }
Segment* subdivide(float param)
{
FloatPoint dst[7];
chopCubicAt(m_points, dst, param);
Segment* left = m_arena->allocateObject<Segment>();
Segment* right = m_arena->allocateObject<Segment>();
left->setup(m_arena, m_contour, dst[0], dst[1], dst[2], dst[3]);
right->setup(m_arena, m_contour, dst[3], dst[4], dst[5], dst[6]);
left->setNext(right);
right->setPrev(left);
if (prev()) {
left->setPrev(prev());
prev()->setNext(left);
}
Segment* n = next();
if (n) {
right->setNext(n);
n->setPrev(right);
}
setNext(left);
return left;
}
Segment* subdivide() { return subdivide(0.5f); }
const FloatRect& boundingBox() const { return m_boundingBox; }
int numCrossingsForXRay(const XRay& xRay, bool& ambiguous) const
{
if (m_kind == Cubic)
return numXRayCrossingsForCubic(xRay, m_points, ambiguous);
return xRayCrossesLine(xRay, m_points, ambiguous) ? 1 : 0;
}
void triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges,
const LoopBlinnTextureCoords::Result* texCoords);
int numberOfTriangles() const
{
if (!m_triangulator)
return 0;
return m_triangulator->numberOfTriangles();
}
LoopBlinnLocalTriangulator::Triangle* getTriangle(int index)
{
ASSERT(m_triangulator);
return m_triangulator->getTriangle(index);
}
int numberOfInteriorVertices() const
{
if (m_kind == Cubic) {
if (m_triangulator)
return m_triangulator->numberOfInteriorVertices();
return 0;
}
return 2;
}
FloatPoint getInteriorVertex(int index) const
{
ASSERT(index >= 0 && index < numberOfInteriorVertices());
if (m_kind == Cubic) {
FloatPoint res;
if (m_triangulator) {
LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getInteriorVertex(index);
if (vertex)
res.set(vertex->xyCoordinates().x(), vertex->xyCoordinates().y());
}
return res;
}
return m_points[index];
}
bool markedForSubdivision() const { return m_markedForSubdivision; }
void setMarkedForSubdivision(bool markedForSubdivision) { m_markedForSubdivision = markedForSubdivision; }
#ifndef NDEBUG
String toString() const
{
StringBuilder builder;
builder.append("[Segment kind=");
builder.append(kind() == Line ? "line" : "cubic");
builder.append(" boundingBox=");
builder.append(valueToString(boundingBox()));
builder.append(" contour=0x");
builder.append(String::format("%p", contour()));
builder.append(" markedForSubdivision=");
builder.append(markedForSubdivision() ? "true" : "false");
builder.append("]");
return builder.toString();
}
#endif
private:
void computeBoundingBox()
{
switch (m_kind) {
case Cubic:
m_boundingBox.fitToPoints(m_points[0], m_points[1], m_points[2], m_points[3]);
break;
case Line:
m_boundingBox.fitToPoints(m_points[0], m_points[1]);
break;
}
}
PODArena* m_arena;
Kind m_kind;
FloatPoint m_points[4];
Segment* m_prev;
Segment* m_next;
Contour* m_contour;
FloatRect m_boundingBox;
LoopBlinnLocalTriangulator* m_triangulator;
bool m_markedForSubdivision;
};
class Contour {
WTF_MAKE_NONCOPYABLE(Contour);
public:
Contour()
{
m_first = &m_sentinel;
m_first->setNext(m_first);
m_first->setPrev(m_first);
m_isOrientedCounterClockwise = true;
m_boundingBoxDirty = false;
m_fillSide = LoopBlinnConstants::RightSide;
}
void add(Segment* segment)
{
if (m_first == &m_sentinel) {
segment->setNext(m_first);
segment->setPrev(m_first);
m_first->setNext(segment);
m_first->setPrev(segment);
m_first = segment;
} else {
ASSERT(m_first->prev() == &m_sentinel);
Segment* last = m_sentinel.prev();
last->setNext(segment);
segment->setPrev(last);
segment->setNext(&m_sentinel);
m_sentinel.setPrev(segment);
}
m_boundingBoxDirty = true;
}
Segment* subdivide(Segment* segment, float param)
{
Segment* left = segment->subdivide(param);
if (m_first == segment)
m_first = left;
return left;
}
Segment* subdivide(Segment* segment)
{
Segment* left = segment->subdivide();
if (m_first == segment)
m_first = left;
return left;
}
Segment* begin() const { return m_first; }
Segment* end()
{
ASSERT(m_first->prev() == &m_sentinel);
return &m_sentinel;
}
bool isOrientedCounterClockwise() const { return m_isOrientedCounterClockwise; }
void setIsOrientedCounterClockwise(bool isOrientedCounterClockwise) { m_isOrientedCounterClockwise = isOrientedCounterClockwise; }
const FloatRect& boundingBox()
{
if (m_boundingBoxDirty) {
bool first = true;
for (Segment* cur = begin(); cur != end(); cur = cur->next()) {
if (first)
m_boundingBox = cur->boundingBox();
else
m_boundingBox.unite(cur->boundingBox());
first = false;
}
m_boundingBoxDirty = false;
}
return m_boundingBox;
}
LoopBlinnConstants::FillSide fillSide() const
{
return m_fillSide;
}
void setFillSide(LoopBlinnConstants::FillSide fillSide)
{
m_fillSide = fillSide;
}
private:
Segment* m_first;
Segment m_sentinel;
bool m_isOrientedCounterClockwise;
FloatRect m_boundingBox;
bool m_boundingBoxDirty;
LoopBlinnConstants::FillSide m_fillSide;
};
void Segment::triangulate(LoopBlinnLocalTriangulator::InsideEdgeComputation computeInsideEdges,
const LoopBlinnTextureCoords::Result* texCoords)
{
ASSERT(m_kind == Cubic);
if (!m_triangulator)
m_triangulator = m_arena->allocateObject<LoopBlinnLocalTriangulator>();
m_triangulator->reset();
for (int i = 0; i < 4; i++) {
LoopBlinnLocalTriangulator::Vertex* vertex = m_triangulator->getVertex(i);
if (texCoords) {
vertex->set(getPoint(i).x(),
getPoint(i).y(),
texCoords->klmCoordinates[i].x(),
texCoords->klmCoordinates[i].y(),
texCoords->klmCoordinates[i].z());
} else {
vertex->set(getPoint(i).x(),
getPoint(i).y(),
0, 0, 0);
}
}
m_triangulator->triangulate(computeInsideEdges, contour()->fillSide());
}
}
LoopBlinnPathProcessor::LoopBlinnPathProcessor()
: m_arena(PODArena::create())
#ifndef NDEBUG
, m_verboseLogging(false)
#endif
{
}
LoopBlinnPathProcessor::LoopBlinnPathProcessor(PassRefPtr<PODArena> arena)
: m_arena(arena)
#ifndef NDEBUG
, m_verboseLogging(false)
#endif
{
}
LoopBlinnPathProcessor::~LoopBlinnPathProcessor()
{
}
void LoopBlinnPathProcessor::process(const Path& path, LoopBlinnPathCache& cache)
{
buildContours(path);
subdivideCurves();
determineSidesToFill();
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
if (seg->kind() == Segment::Cubic) {
LoopBlinnClassifier::Result classification = LoopBlinnClassifier::classify(seg->getPoint(0),
seg->getPoint(1),
seg->getPoint(2),
seg->getPoint(3));
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("Classification: %d", (int) classification.curveType);
#endif
LoopBlinnTextureCoords::Result texCoords =
LoopBlinnTextureCoords::compute(classification, cur->fillSide());
if (texCoords.hasRenderingArtifact) {
cur->subdivide(seg);
} else {
if (!texCoords.isLineOrPoint) {
seg->triangulate(LoopBlinnLocalTriangulator::ComputeInsideEdges, &texCoords);
for (int i = 0; i < seg->numberOfTriangles(); i++) {
LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i);
for (int j = 0; j < 3; j++) {
LoopBlinnLocalTriangulator::Vertex* vert = triangle->getVertex(j);
cache.addVertex(vert->xyCoordinates().x(),
vert->xyCoordinates().y(),
vert->klmCoordinates().x(),
vert->klmCoordinates().y(),
vert->klmCoordinates().z());
}
}
#ifdef LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES
for (int i = 1; i < seg->numberOfInteriorVertices(); i++) {
FloatPoint vert = seg->getInteriorVertex(i);
FloatPoint prev = seg->getInteriorVertex(i - 1);
cache.addInteriorEdgeVertex(prev.x(), prev.y());
cache.addInteriorEdgeVertex(vert.x(), vert.y());
}
#endif // LOOP_BLINN_PATH_CACHE_DEBUG_INTERIOR_EDGES
}
}
}
}
}
tessellateInterior(cache);
}
void LoopBlinnPathProcessor::buildContours(const Path& path)
{
m_contours.clear();
#if USE(SKIA)
SkPath::Iter iter(*path.platformPath(), false);
SkPoint points[4];
SkPath::Verb verb;
Contour* contour = 0;
SkPoint curPoint = { 0 };
SkPoint moveToPoint = { 0 };
do {
verb = iter.next(points);
if (verb != SkPath::kMove_Verb) {
if (!contour) {
contour = m_arena->allocateObject<Contour>();
m_contours.append(contour);
}
}
switch (verb) {
case SkPath::kMove_Verb: {
contour = m_arena->allocateObject<Contour>();
m_contours.append(contour);
curPoint = points[0];
moveToPoint = points[0];
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("MoveTo (%f, %f)", points[0].fX, points[0].fY);
#endif
break;
}
case SkPath::kLine_Verb: {
Segment* segment = m_arena->allocateObject<Segment>();
if (iter.isCloseLine()) {
segment->setup(m_arena.get(), contour, curPoint, points[1]);
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("CloseLineTo (%f, %f), (%f, %f)", curPoint.fX, curPoint.fY, points[1].fX, points[1].fY);
#endif
contour->add(segment);
contour = 0;
} else {
segment->setup(m_arena.get(), contour, points[0], points[1]);
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("LineTo (%f, %f), (%f, %f)", points[0].fX, points[0].fY, points[1].fX, points[1].fY);
#endif
contour->add(segment);
curPoint = points[1];
}
break;
}
case SkPath::kQuad_Verb: {
SkPoint cubic[4];
SkConvertQuadToCubic(points, cubic);
Segment* segment = m_arena->allocateObject<Segment>();
segment->setup(m_arena.get(), contour,
cubic[0], cubic[1], cubic[2], cubic[3]);
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("Quad->CubicTo (%f, %f), (%f, %f), (%f, %f), (%f, %f)", cubic[0].fX, cubic[0].fY, cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY);
#endif
contour->add(segment);
curPoint = cubic[3];
break;
}
case SkPath::kCubic_Verb: {
Segment* segment = m_arena->allocateObject<Segment>();
segment->setup(m_arena.get(), contour, points[0], points[1], points[2], points[3]);
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("CubicTo (%f, %f), (%f, %f), (%f, %f), (%f, %f)", points[0].fX, points[0].fY, points[1].fX, points[1].fY, points[2].fX, points[2].fY, points[3].fX, points[3].fY);
#endif
contour->add(segment);
curPoint = points[3];
break;
}
case SkPath::kClose_Verb: {
Segment* segment = m_arena->allocateObject<Segment>();
segment->setup(m_arena.get(), contour, curPoint, moveToPoint);
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("Close (%f, %f) -> (%f, %f)", curPoint.fX, curPoint.fY, moveToPoint.fX, moveToPoint.fY);
#endif
contour->add(segment);
contour = 0;
}
case SkPath::kDone_Verb:
break;
}
} while (verb != SkPath::kDone_Verb);
#else // !USE(SKIA)
UNUSED_PARAM(path);
ASSERT_NOT_REACHED();
#endif
}
#ifndef NDEBUG
Vector<Segment*> LoopBlinnPathProcessor::allSegmentsOverlappingY(Contour* queryContour, float x, float y)
{
Vector<Segment*> res;
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
const FloatRect& boundingBox = seg->boundingBox();
if (boundingBox.y() <= y && y <= boundingBox.maxY())
res.append(seg);
}
}
return res;
}
#endif
void LoopBlinnPathProcessor::determineSidesToFill()
{
PODIntervalTree<float, Segment*> tree(m_arena);
typedef PODIntervalTree<float, Segment*>::IntervalType IntervalType;
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
determineOrientation(cur);
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
const FloatRect& boundingBox = seg->boundingBox();
tree.add(tree.createInterval(boundingBox.y(), boundingBox.maxY(), seg));
}
}
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
bool ambiguous = true;
int numCrossings = 0;
for (Segment* seg = cur->begin();
ambiguous && seg != cur->end();
seg = seg->next()) {
numCrossings = 0;
Vector<IntervalType> overlaps = tree.allOverlaps(tree.createInterval(seg->getPoint(0).y(),
seg->getPoint(0).y(),
0));
#if defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG)
Vector<Segment*> slowOverlaps = allSegmentsOverlappingY(cur, seg->getPoint(0).x(), seg->getPoint(0).y());
if (overlaps.size() != slowOverlaps.size()) {
LOG_ERROR("For query point (%f, %f) on contour 0x%p:", seg->getPoint(0).x(), seg->getPoint(0).y(), cur);
LOG_ERROR(" overlaps:");
for (size_t i = 0; i < overlaps.size(); i++)
LOG_ERROR(" %d: %s", i+1, overlaps[i].data()->toString().ascii().data());
LOG_ERROR(" slowOverlaps:");
for (size_t i = 0; i < slowOverlaps.size(); i++)
LOG_ERROR(" %d: %s", (i+1) slowOverlaps[i]->toString());
LOG_ERROR("Interval tree:");
tree.dump();
}
ASSERT(overlaps.size() == slowOverlaps.size());
#endif // defined(GPU_PATH_PROCESSOR_DEBUG_ORIENTATION) && !defined(NDEBUG)
for (Vector<IntervalType>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) {
const IntervalType& interval = *iter;
Segment* querySegment = interval.data();
if (querySegment->contour() != cur) {
const FloatRect& boundingBox = querySegment->contour()->boundingBox();
if (seg->getPoint(0).x() >= boundingBox.x()
&& seg->getPoint(0).x() <= boundingBox.maxX()) {
numCrossings += querySegment->numCrossingsForXRay(seg->getPoint(0),
ambiguous);
if (ambiguous) {
#ifndef NDEBUG
if (m_verboseLogging) {
LOG_ERROR("Ambiguous intersection query at point (%f, %f)", seg->getPoint(0).x(), seg->getPoint(0).y());
LOG_ERROR("Query segment: %s", querySegment->toString().ascii().data());
}
#endif
break; }
}
}
}
}
cur->setFillSide((cur->isOrientedCounterClockwise() ^ (numCrossings & 1)) ? LoopBlinnConstants::LeftSide : LoopBlinnConstants::RightSide);
}
}
void LoopBlinnPathProcessor::determineOrientation(Contour* contour)
{
float signedArea = 0;
for (Segment* seg = contour->begin();
seg != contour->end();
seg = seg->next()) {
int limit = (seg->kind() == Segment::Cubic) ? 4 : 2;
for (int i = 1; i < limit; i++) {
const FloatPoint& prevPoint = seg->getPoint(i - 1);
const FloatPoint& point = seg->getPoint(i);
float curArea = prevPoint.x() * point.y() - prevPoint.y() * point.x();
#ifndef NDEBUG
if (m_verboseLogging)
LOG_ERROR("Adding to signed area (%f, %f) -> (%f, %f) = %f", prevPoint.x(), prevPoint.y(), point.x(), point.y(), curArea);
#endif
signedArea += curArea;
}
}
if (signedArea > 0)
contour->setIsOrientedCounterClockwise(true);
else
contour->setIsOrientedCounterClockwise(false);
}
namespace {
struct SweepData {
SweepData()
: triangle(0)
, segment(0)
{
}
LoopBlinnLocalTriangulator::Triangle* triangle;
Segment* segment;
};
typedef PODIntervalTree<float, SweepData*> SweepTree;
typedef SweepTree::IntervalType SweepInterval;
class SweepEvent {
public:
SweepEvent()
: m_x(0)
, m_entry(false)
, m_interval(0, 0, 0)
{
}
void setup(float x, bool entry, SweepInterval interval)
{
m_x = x;
m_entry = entry;
m_interval = interval;
}
float x() const { return m_x; }
bool entry() const { return m_entry; }
const SweepInterval& interval() const { return m_interval; }
bool operator<(const SweepEvent& other) const
{
return m_x < other.m_x;
}
private:
float m_x;
bool m_entry;
SweepInterval m_interval;
};
bool trianglesOverlap(LoopBlinnLocalTriangulator::Triangle* t0,
LoopBlinnLocalTriangulator::Triangle* t1)
{
return trianglesOverlap(t0->getVertex(0)->xyCoordinates(),
t0->getVertex(1)->xyCoordinates(),
t0->getVertex(2)->xyCoordinates(),
t1->getVertex(0)->xyCoordinates(),
t1->getVertex(1)->xyCoordinates(),
t1->getVertex(2)->xyCoordinates());
}
}
void LoopBlinnPathProcessor::subdivideCurves()
{
Vector<Segment*> curSegments;
Vector<Segment*> nextSegments;
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
if (seg->kind() == Segment::Cubic) {
seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0);
curSegments.append(seg);
}
}
}
const int MaxIterations = 5;
Vector<SweepInterval> overlaps;
for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) {
if (!curSegments.size())
break;
Vector<SweepEvent> events;
SweepTree tree(m_arena);
for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) {
Segment* seg = *iter;
ASSERT(seg->kind() == Segment::Cubic);
for (int i = 0; i < seg->numberOfTriangles(); i++) {
LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i);
FloatRect boundingBox;
boundingBox.fitToPoints(triangle->getVertex(0)->xyCoordinates(),
triangle->getVertex(1)->xyCoordinates(),
triangle->getVertex(2)->xyCoordinates());
if (boundingBox.maxX() > boundingBox.x()) {
SweepData* data = m_arena->allocateObject<SweepData>();
data->triangle = triangle;
data->segment = seg;
SweepInterval interval = tree.createInterval(boundingBox.y(), boundingBox.maxY(), data);
SweepEvent event;
event.setup(boundingBox.x(), true, interval);
events.append(event);
event.setup(boundingBox.maxX(), false, interval);
events.append(event);
}
}
}
std::sort(events.begin(), events.end());
#ifndef NDEBUG
for (size_t ii = 1; ii < events.size(); ++ii)
ASSERT(events[ii - 1].x() <= events[ii].x());
#endif
for (Vector<SweepEvent>::iterator iter = events.begin(); iter != events.end(); ++iter) {
SweepEvent event = *iter;
if (event.entry()) {
if (!event.interval().data()->segment->markedForSubdivision()) {
overlaps.clear();
tree.allOverlaps(event.interval(), overlaps);
for (Vector<SweepInterval>::iterator iter = overlaps.begin(); iter != overlaps.end(); ++iter) {
SweepInterval overlap = *iter;
if (event.interval().data()->segment != overlap.data()->segment) {
if (trianglesOverlap(event.interval().data()->triangle,
overlap.data()->triangle)) {
Segment* seg = event.interval().data()->segment;
conditionallySubdivide(seg, nextSegments);
seg = overlap.data()->segment;
conditionallySubdivide(seg, nextSegments);
}
}
}
}
tree.add(event.interval());
} else {
tree.remove(event.interval());
}
}
curSegments.swap(nextSegments);
nextSegments.clear();
}
}
void LoopBlinnPathProcessor::conditionallySubdivide(Segment* seg, Vector<Segment*>& nextSegments)
{
if (!seg->markedForSubdivision()) {
seg->setMarkedForSubdivision(true);
Segment* next = seg->contour()->subdivide(seg);
next->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0);
next->next()->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0);
nextSegments.append(next);
nextSegments.append(next->next());
}
}
#ifndef NDEBUG
void LoopBlinnPathProcessor::subdivideCurvesSlow()
{
Vector<Segment*> curSegments;
Vector<Segment*> nextSegments;
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
if (seg->kind() == Segment::Cubic) {
seg->triangulate(LoopBlinnLocalTriangulator::DontComputeInsideEdges, 0);
curSegments.append(seg);
}
}
}
const int MaxIterations = 5;
for (int currentIteration = 0; currentIteration < MaxIterations; ++currentIteration) {
if (!curSegments.size())
break;
for (Vector<Segment*>::iterator iter = curSegments.begin(); iter != curSegments.end(); ++iter) {
Segment* seg = *iter;
ASSERT(seg->kind() == Segment::Cubic);
for (Vector<Segment*>::iterator iter2 = curSegments.begin();
iter2 != curSegments.end();
iter2++) {
Segment* seg2 = *iter2;
ASSERT(seg2->kind() == Segment::Cubic);
if (seg != seg2) {
for (int i = 0; i < seg->numberOfTriangles(); i++) {
LoopBlinnLocalTriangulator::Triangle* triangle = seg->getTriangle(i);
for (int j = 0; j < seg2->numberOfTriangles(); j++) {
LoopBlinnLocalTriangulator::Triangle* triangle2 = seg2->getTriangle(j);
if (trianglesOverlap(triangle, triangle2)) {
conditionallySubdivide(seg, nextSegments);
conditionallySubdivide(seg2, nextSegments);
}
}
}
}
}
}
curSegments.swap(nextSegments);
nextSegments.clear();
}
}
#endif
namespace {
struct TessellationState {
TessellationState(LoopBlinnPathCache& inputCache)
: cache(inputCache) { }
LoopBlinnPathCache& cache;
Vector<void*> allocatedPointers;
};
static void vertexCallback(void* vertexData, void* data)
{
TessellationState* state = static_cast<TessellationState*>(data);
GLdouble* location = static_cast<GLdouble*>(vertexData);
state->cache.addInteriorVertex(static_cast<float>(location[0]),
static_cast<float>(location[1]));
}
static void combineCallback(GLdouble coords[3], void* vertexData[4],
GLfloat weight[4], void** outData,
void* polygonData)
{
UNUSED_PARAM(vertexData);
UNUSED_PARAM(weight);
TessellationState* state = static_cast<TessellationState*>(polygonData);
GLdouble* outVertex = static_cast<GLdouble*>(fastMalloc(3 * sizeof(GLdouble)));
state->allocatedPointers.append(outVertex);
outVertex[0] = coords[0];
outVertex[1] = coords[1];
outVertex[2] = coords[2];
*outData = outVertex;
}
static void edgeFlagCallback(GLboolean)
{
}
}
void LoopBlinnPathProcessor::tessellateInterior(LoopBlinnPathCache& cache)
{
Vector<GLdouble> vertexData;
Vector<size_t> contourEndings;
float curX = 0, curY = 0;
for (Vector<Contour*>::iterator iter = m_contours.begin(); iter != m_contours.end(); ++iter) {
Contour* cur = *iter;
bool first = true;
for (Segment* seg = cur->begin(); seg != cur->end(); seg = seg->next()) {
int numberOfInteriorVertices = seg->numberOfInteriorVertices();
for (int i = 0; i < numberOfInteriorVertices - 1; i++) {
FloatPoint point = seg->getInteriorVertex(i);
if (first) {
first = false;
vertexData.append(point.x());
vertexData.append(point.y());
vertexData.append(0);
curX = point.x();
curY = point.y();
} else if (point.x() != curX || point.y() != curY) {
vertexData.append(point.x());
vertexData.append(point.y());
vertexData.append(0);
curX = point.x();
curY = point.y();
}
}
}
contourEndings.append(vertexData.size());
}
GLUtesselator* tess = internal_gluNewTess();
TessellationState state(cache);
internal_gluTessCallback(tess, GLU_TESS_VERTEX_DATA,
reinterpret_cast<GLvoid (*)()>(vertexCallback));
internal_gluTessCallback(tess, GLU_TESS_COMBINE_DATA,
reinterpret_cast<GLvoid (*)()>(combineCallback));
internal_gluTessCallback(tess, GLU_TESS_EDGE_FLAG,
reinterpret_cast<GLvoid (*)()>(edgeFlagCallback));
internal_gluTessBeginPolygon(tess, &state);
internal_gluTessBeginContour(tess);
GLdouble* base = vertexData.data();
int contourIndex = 0;
for (size_t i = 0; i < vertexData.size(); i += 3) {
if (i == contourEndings[contourIndex]) {
internal_gluTessEndContour(tess);
internal_gluTessBeginContour(tess);
++contourIndex;
}
internal_gluTessVertex(tess, &base[i], &base[i]);
}
internal_gluTessEndContour(tess);
internal_gluTessEndPolygon(tess);
for (size_t i = 0; i < state.allocatedPointers.size(); i++)
fastFree(state.allocatedPointers[i]);
internal_gluDeleteTess(tess);
}
}