#include "config.h"
#include "cc/CCLayerSorter.h"
#include "LoopBlinnMathUtils.h"
#include "RenderSurfaceChromium.h"
#include "TransformationMatrix.h"
#include <limits.h>
using namespace std;
#define LOG_CHANNEL_PREFIX Log
#define SHOW_DEBUG_LOG 0
#if !defined( NDEBUG )
#if SHOW_DEBUG_LOG
static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOn };
#else
static WTFLogChannel LogCCLayerSorter = { 0x00000000, "", WTFLogChannelOff };
#endif
#endif
namespace WebCore {
using LoopBlinnMathUtils::pointInTriangle;
inline static float perpProduct(const FloatSize& u, const FloatSize& v)
{
return u.width() * v.height() - u.height() * v.width();
}
inline static float innerProduct(const FloatSize& u, const FloatSize& v)
{
return u.width() * v.width() + u.height() * v.height();
}
inline static bool pointInColinearEdge(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b)
{
if (a.x() != b.x())
return (p.x() >= min(a.x(), b.x()) && p.x() <= max(a.x(), b.x()));
return (p.y() >= min(a.y(), b.y()) && p.y() <= max(a.y(), b.y()));
}
static bool edgeEdgeTest(const FloatPoint& a, const FloatPoint& b, const FloatPoint& c, const FloatPoint& d, FloatPoint& r)
{
FloatSize u = b - a;
FloatSize v = d - c;
FloatSize w = a - c;
float denom = perpProduct(u, v);
if (!denom) {
if (perpProduct(u, w) || perpProduct(v, w))
return false;
if (pointInColinearEdge(a, c, d)) {
r = a;
return true;
}
if (pointInColinearEdge(b, c, d)) {
r = b;
return true;
}
if (pointInColinearEdge(c, a, b)) {
r = c;
return true;
}
if (pointInColinearEdge(d, a, b)) {
r = d;
return true;
}
return false;
}
float s = perpProduct(v, w) / denom;
if (s < 0 || s > 1)
return false;
float t = perpProduct(u, w) / denom;
if (t < 0 || t > 1)
return false;
u.scale(s);
r = a + u;
return true;
}
CCLayerSorter::LayerIntersector::LayerIntersector(GraphNode* nodeA, GraphNode* nodeB, float earlyExitThreshold)
: nodeA(nodeA)
, nodeB(nodeB)
, zDiff(0)
, earlyExitThreshold(earlyExitThreshold)
{
}
void CCLayerSorter::LayerIntersector::go()
{
(triangleTriangleTest(nodeA->c1, nodeA->c2, nodeA->c3, nodeB->c1, nodeB->c2, nodeB->c3)
|| triangleTriangleTest(nodeA->c3, nodeA->c4, nodeA->c1, nodeB->c1, nodeB->c2, nodeB->c3)
|| triangleTriangleTest(nodeA->c1, nodeA->c2, nodeA->c3, nodeB->c3, nodeB->c4, nodeB->c1)
|| triangleTriangleTest(nodeA->c3, nodeA->c4, nodeA->c1, nodeB->c3, nodeB->c4, nodeB->c1));
}
bool CCLayerSorter::LayerIntersector::edgeTriangleTest(const FloatPoint& p, const FloatPoint& q, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)
{
FloatPoint r;
if ((edgeEdgeTest(p, q, a, b, r) && checkZDiff(r))
|| (edgeEdgeTest(p, q, a, c, r) && checkZDiff(r))
|| (edgeEdgeTest(p, q, b, c, r) && checkZDiff(r)))
return true;
return false;
}
bool CCLayerSorter::LayerIntersector::triangleTriangleTest(const FloatPoint& a1, const FloatPoint& b1, const FloatPoint& c1, const FloatPoint& a2, const FloatPoint& b2, const FloatPoint& c2)
{
if (edgeTriangleTest(a1, b1, a2, b2, c2)
|| edgeTriangleTest(a1, c1, a2, b2, c2)
|| edgeTriangleTest(b1, c1, a2, b2, c2))
return true;
if ((pointInTriangle(a1, a2, b2, c2) && checkZDiff(a1))
|| (pointInTriangle(b1, a2, b2, c2) && checkZDiff(b1))
|| (pointInTriangle(c1, a2, b2, c2) && checkZDiff(c1)))
return true;
if ((pointInTriangle(a2, a1, b1, c1) && checkZDiff(a2))
|| (pointInTriangle(b2, a1, b1, c1) && checkZDiff(b2))
|| (pointInTriangle(c2, a1, b1, c1) && checkZDiff(c2)))
return true;
return false;
}
bool CCLayerSorter::LayerIntersector::checkZDiff(const FloatPoint& p)
{
float za = layerZFromProjectedPoint(nodeA, p);
float zb = layerZFromProjectedPoint(nodeB, p);
float diff = za - zb;
float absDiff = fabsf(diff);
if ((absDiff) > fabsf(zDiff)) {
intersectionPoint = p;
zDiff = diff;
}
if (absDiff > earlyExitThreshold)
return true;
return false;
}
float CCLayerSorter::LayerIntersector::layerZFromProjectedPoint(GraphNode* layer, const FloatPoint& p)
{
const FloatPoint3D zAxis(0, 0, 1);
FloatPoint3D w = FloatPoint3D(p.x(), p.y(), 0) - layer->origin;
float d = layer->normal.dot(zAxis);
float n = -layer->normal.dot(w);
if (!d)
return layer->origin.z();
return n / d;
}
CCLayerSorter::CCLayerSorter()
: m_zRange(0)
{
}
CCLayerSorter::ABCompareResult CCLayerSorter::checkOverlap(GraphNode* a, GraphNode* b)
{
if (!a->boundingBox.intersects(b->boundingBox))
return None;
float exitThreshold = m_zRange * 0.01;
LayerIntersector intersector(a, b, exitThreshold);
intersector.go();
if (intersector.zDiff > 0)
return BBeforeA;
if (intersector.zDiff < 0)
return ABeforeB;
return None;
}
void CCLayerSorter::createGraphNodes(LayerList::iterator first, LayerList::iterator last)
{
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Creating graph nodes:\n");
#endif
float minZ = FLT_MAX;
float maxZ = -FLT_MAX;
for (LayerList::const_iterator it = first; it < last; it++) {
m_nodes.append(GraphNode(it->get()));
GraphNode& node = m_nodes.at(m_nodes.size() - 1);
RenderSurfaceChromium* renderSurface = node.layer->renderSurface();
if (!node.layer->drawsContent() && !renderSurface)
continue;
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Layer %d (%d x %d)\n", node.layer->debugID(), node.layer->bounds().width(), node.layer->bounds().height());
#endif
TransformationMatrix drawTransform;
float layerWidth, layerHeight;
if (renderSurface) {
drawTransform = renderSurface->drawTransform();
layerWidth = 0.5 * renderSurface->contentRect().width();
layerHeight = 0.5 * renderSurface->contentRect().height();
} else {
drawTransform = node.layer->drawTransform();
layerWidth = 0.5 * node.layer->bounds().width();
layerHeight = 0.5 * node.layer->bounds().height();
}
FloatPoint3D c1 = drawTransform.mapPoint(FloatPoint3D(-layerWidth, layerHeight, 0));
FloatPoint3D c2 = drawTransform.mapPoint(FloatPoint3D(layerWidth, layerHeight, 0));
FloatPoint3D c3 = drawTransform.mapPoint(FloatPoint3D(layerWidth, -layerHeight, 0));
FloatPoint3D c4 = drawTransform.mapPoint(FloatPoint3D(-layerWidth, -layerHeight, 0));
node.normal = (c2 - c1).cross(c3 - c1);
node.c1 = FloatPoint(c1.x(), c1.y());
node.c2 = FloatPoint(c2.x(), c2.y());
node.c3 = FloatPoint(c3.x(), c3.y());
node.c4 = FloatPoint(c4.x(), c4.y());
node.origin = c1;
node.boundingBox.fitToPoints(node.c1, node.c2, node.c3, node.c4);
maxZ = max(c4.z(), max(c3.z(), max(c2.z(), max(maxZ, c1.z()))));
minZ = min(c4.z(), min(c3.z(), min(c2.z(), min(minZ, c1.z()))));
}
if (last - first)
m_zRange = fabsf(maxZ - minZ);
}
void CCLayerSorter::createGraphEdges()
{
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Edges:\n");
#endif
for (unsigned na = 0; na < m_nodes.size(); na++) {
GraphNode& nodeA = m_nodes[na];
if (!nodeA.layer->drawsContent() && !nodeA.layer->renderSurface())
continue;
for (unsigned nb = na + 1; nb < m_nodes.size(); nb++) {
GraphNode& nodeB = m_nodes[nb];
if (!nodeB.layer->drawsContent() && !nodeB.layer->renderSurface())
continue;
ABCompareResult overlapResult = checkOverlap(&nodeA, &nodeB);
GraphNode* startNode = 0;
GraphNode* endNode = 0;
if (overlapResult == ABeforeB) {
startNode = &nodeA;
endNode = &nodeB;
} else if (overlapResult == BBeforeA) {
startNode = &nodeB;
endNode = &nodeA;
}
if (startNode) {
#if !defined( NDEBUG )
LOG(CCLayerSorter, "%d -> %d\n", startNode->layer->debugID(), endNode->layer->debugID());
#endif
m_edges.append(GraphEdge(startNode, endNode));
}
}
}
for (unsigned i = 0; i < m_edges.size(); i++) {
GraphEdge& edge = m_edges[i];
m_activeEdges.add(&edge, &edge);
edge.from->outgoing.append(&edge);
edge.to->incoming.append(&edge);
}
}
void CCLayerSorter::removeEdgeFromList(GraphEdge* edge, Vector<GraphEdge*>& list)
{
size_t edgeIndex = list.find(edge);
ASSERT(edgeIndex != notFound);
if (list.size() == 1) {
ASSERT(!edgeIndex);
list.clear();
return;
}
if (edgeIndex != list.size() - 1)
list[edgeIndex] = list[list.size() - 1];
list.removeLast();
}
void CCLayerSorter::sort(LayerList::iterator first, LayerList::iterator last)
{
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Sorting start ----\n");
#endif
createGraphNodes(first, last);
createGraphEdges();
Vector<GraphNode*> sortedList;
Vector<GraphNode*> noIncomingEdgeNodeList;
for (NodeList::iterator la = m_nodes.begin(); la < m_nodes.end(); la++) {
if (!la->incoming.size())
noIncomingEdgeNodeList.append(la);
}
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Sorted list: ");
#endif
while (m_activeEdges.size() || noIncomingEdgeNodeList.size()) {
while (noIncomingEdgeNodeList.size()) {
GraphNode* fromNode = noIncomingEdgeNodeList[noIncomingEdgeNodeList.size() - 1];
noIncomingEdgeNodeList.removeLast();
sortedList.append(fromNode);
#if !defined( NDEBUG )
LOG(CCLayerSorter, "%d, ", fromNode->layer->debugID());
#endif
for (unsigned i = 0; i < fromNode->outgoing.size(); i++) {
GraphEdge* outgoingEdge = fromNode->outgoing[i];
m_activeEdges.remove(outgoingEdge);
removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming);
if (!outgoingEdge->to->incoming.size())
noIncomingEdgeNodeList.append(outgoingEdge->to);
}
fromNode->outgoing.clear();
}
if (!m_activeEdges.size())
break;
unsigned minIncomingEdgeCount = UINT_MAX;
GraphNode* nextNode = 0;
for (unsigned i = 0; i < m_nodes.size(); i++) {
if (m_nodes[i].incoming.size() && (m_nodes[i].incoming.size() < minIncomingEdgeCount)) {
minIncomingEdgeCount = m_nodes[i].incoming.size();
nextNode = &m_nodes[i];
}
}
ASSERT(nextNode);
for (unsigned e = 0; e < nextNode->incoming.size(); e++) {
GraphEdge* incomingEdge = nextNode->incoming[e];
m_activeEdges.remove(incomingEdge);
removeEdgeFromList(incomingEdge, incomingEdge->from->outgoing);
}
nextNode->incoming.clear();
noIncomingEdgeNodeList.append(nextNode);
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Breaking cycle by cleaning up %d edges from %d\n", minIncomingEdgeCount, nextNode->layer->debugID());
#endif
}
int count = 0;
for (LayerList::iterator it = first; it < last; it++)
*it = sortedList[count++]->layer;
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Sorting end ----\n");
#endif
m_nodes.clear();
m_edges.clear();
m_activeEdges.clear();
}
}