#include "config.h"
#include "cc/CCLayerSorter.h"
#include "TransformationMatrix.h"
#include "cc/CCMathUtil.h"
#include "cc/CCRenderSurface.h"
#include <limits.h>
#include <wtf/Deque.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 {
inline static float perpProduct(const FloatSize& u, const FloatSize& v)
{
return u.width() * v.height() - u.height() * v.width();
}
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)
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::ABCompareResult CCLayerSorter::checkOverlap(LayerShape* a, LayerShape* b, float zThreshold, float& weight)
{
weight = 0;
if (!a->projectedBounds.intersects(b->projectedBounds))
return None;
FloatPoint aPoints[4] = {a->projectedQuad.p1(), a->projectedQuad.p2(), a->projectedQuad.p3(), a->projectedQuad.p4() };
FloatPoint bPoints[4] = {b->projectedQuad.p1(), b->projectedQuad.p2(), b->projectedQuad.p3(), b->projectedQuad.p4() };
Vector<FloatPoint> overlapPoints;
for (int i = 0; i < 4; ++i) {
if (a->projectedQuad.containsPoint(bPoints[i]))
overlapPoints.append(bPoints[i]);
if (b->projectedQuad.containsPoint(aPoints[i]))
overlapPoints.append(aPoints[i]);
}
FloatPoint r;
for (int ea = 0; ea < 4; ++ea)
for (int eb = 0; eb < 4; ++eb)
if (edgeEdgeTest(aPoints[ea], aPoints[(ea + 1) % 4],
bPoints[eb], bPoints[(eb + 1) % 4],
r))
overlapPoints.append(r);
if (!overlapPoints.size())
return None;
float maxPositive = 0;
float maxNegative = 0;
for (unsigned o = 0; o < overlapPoints.size(); o++) {
float za = a->layerZFromProjectedPoint(overlapPoints[o]);
float zb = b->layerZFromProjectedPoint(overlapPoints[o]);
float diff = za - zb;
if (diff > maxPositive)
maxPositive = diff;
if (diff < maxNegative)
maxNegative = diff;
}
float maxDiff = (fabsf(maxPositive) > fabsf(maxNegative) ? maxPositive : maxNegative);
if (maxPositive > zThreshold && maxNegative < -zThreshold)
weight = 0;
else
weight = fabsf(maxDiff);
if (maxDiff <= 0)
return ABeforeB;
return BBeforeA;
}
CCLayerSorter::LayerShape::LayerShape(float width, float height, const TransformationMatrix& drawTransform)
{
FloatQuad layerQuad(FloatPoint(-width * 0.5, height * 0.5),
FloatPoint(width * 0.5, height * 0.5),
FloatPoint(width * 0.5, -height * 0.5),
FloatPoint(-width * 0.5, -height * 0.5));
FloatPoint clippedQuad[8];
int numVerticesInClippedQuad;
CCMathUtil::mapClippedQuad(drawTransform, layerQuad, clippedQuad, numVerticesInClippedQuad);
if (numVerticesInClippedQuad < 3) {
projectedBounds = FloatRect();
return;
}
projectedBounds = CCMathUtil::computeEnclosingRectOfVertices(clippedQuad, numVerticesInClippedQuad);
projectedQuad.setP1(clippedQuad[0]);
projectedQuad.setP2(clippedQuad[1]);
projectedQuad.setP3(clippedQuad[2]);
if (numVerticesInClippedQuad >= 4)
projectedQuad.setP4(clippedQuad[3]);
else
projectedQuad.setP4(clippedQuad[2]);
FloatPoint3D c1 = drawTransform.mapPoint(FloatPoint3D(0, 0, 0));
FloatPoint3D c2 = drawTransform.mapPoint(FloatPoint3D(0, 1, 0));
FloatPoint3D c3 = drawTransform.mapPoint(FloatPoint3D(1, 0, 0));
FloatPoint3D c12 = c2 - c1;
FloatPoint3D c13 = c3 - c1;
layerNormal = c13.cross(c12);
transformOrigin = c1;
}
float CCLayerSorter::LayerShape::layerZFromProjectedPoint(const FloatPoint& p) const
{
const FloatPoint3D zAxis(0, 0, 1);
FloatPoint3D w = FloatPoint3D(p) - transformOrigin;
float d = layerNormal.dot(zAxis);
float n = -layerNormal.dot(w);
if (!d)
return 0;
return n / d;
}
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));
GraphNode& node = m_nodes.at(m_nodes.size() - 1);
CCRenderSurface* renderSurface = node.layer->renderSurface();
if (!node.layer->drawsContent() && !renderSurface)
continue;
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Layer %d (%d x %d)\n", node.layer->id(), node.layer->bounds().width(), node.layer->bounds().height());
#endif
TransformationMatrix drawTransform;
float layerWidth, layerHeight;
if (renderSurface) {
drawTransform = renderSurface->drawTransform();
layerWidth = renderSurface->contentRect().width();
layerHeight = renderSurface->contentRect().height();
} else {
drawTransform = node.layer->drawTransform();
layerWidth = node.layer->bounds().width();
layerHeight = node.layer->bounds().height();
}
node.shape = LayerShape(layerWidth, layerHeight, drawTransform);
maxZ = max(maxZ, node.shape.transformOrigin.z());
minZ = min(minZ, node.shape.transformOrigin.z());
}
m_zRange = fabsf(maxZ - minZ);
}
void CCLayerSorter::createGraphEdges()
{
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Edges:\n");
#endif
const float zThresholdFactor = 0.01;
float zThreshold = m_zRange * zThresholdFactor;
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;
float weight = 0;
ABCompareResult overlapResult = checkOverlap(&nodeA.shape, &nodeB.shape, zThreshold, weight);
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->id(), endNode->layer->id());
#endif
m_edges.append(GraphEdge(startNode, endNode, weight));
}
}
}
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);
edge.to->incomingEdgeWeight += edge.weight;
}
}
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;
Deque<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.takeFirst();
sortedList.append(fromNode);
#if !defined( NDEBUG )
LOG(CCLayerSorter, "%d, ", fromNode->layer->id());
#endif
for (unsigned i = 0; i < fromNode->outgoing.size(); i++) {
GraphEdge* outgoingEdge = fromNode->outgoing[i];
m_activeEdges.remove(outgoingEdge);
removeEdgeFromList(outgoingEdge, outgoingEdge->to->incoming);
outgoingEdge->to->incomingEdgeWeight -= outgoingEdge->weight;
if (!outgoingEdge->to->incoming.size())
noIncomingEdgeNodeList.append(outgoingEdge->to);
}
fromNode->outgoing.clear();
}
if (!m_activeEdges.size())
break;
float minIncomingEdgeWeight = FLT_MAX;
GraphNode* nextNode = 0;
for (unsigned i = 0; i < m_nodes.size(); i++) {
if (m_nodes[i].incoming.size() && m_nodes[i].incomingEdgeWeight < minIncomingEdgeWeight) {
minIncomingEdgeWeight = m_nodes[i].incomingEdgeWeight;
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();
nextNode->incomingEdgeWeight = 0;
noIncomingEdgeNodeList.append(nextNode);
#if !defined( NDEBUG )
LOG(CCLayerSorter, "Breaking cycle by cleaning up incoming edges from %d (weight = %f)\n", nextNode->layer->id(), minIncomingEdgeWeight);
#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();
}
}