From ebdaf49bf68dea42787af342c56a0ec636bec707 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Samuel=20R=C3=B8dal?= Date: Fri, 9 Oct 2009 17:12:33 +0200 Subject: Implemented hidden surface removal for projected items. This speeds things up a bit by not painting walls / items that are completely hidden behind other walls. --- entity.cpp | 2 +- mazescene.cpp | 204 +++++++++++++++++++++++++++++++++++++++++++++++++--------- mazescene.h | 11 +++- modelitem.cpp | 15 +++-- 4 files changed, 197 insertions(+), 35 deletions(-) diff --git a/entity.cpp b/entity.cpp index 1c0bb00..cabaae9 100644 --- a/entity.cpp +++ b/entity.cpp @@ -38,7 +38,7 @@ const QImage toAlpha(const QImage &image) } Entity::Entity(const QPointF &pos) - : ProjectedItem(QRectF(-0.3, -0.4, 0.6, 0.9), false) + : ProjectedItem(QRectF(-0.3, -0.4, 0.6, 0.9), false, false) , m_pos(pos) , m_angle(180) , m_walking(false) diff --git a/mazescene.cpp b/mazescene.cpp index 18197d4..6a8821e 100644 --- a/mazescene.cpp +++ b/mazescene.cpp @@ -425,9 +425,11 @@ void MazeScene::addEntity(Entity *entity) m_entities << entity; } -ProjectedItem::ProjectedItem(const QRectF &bounds, bool shadow) +ProjectedItem::ProjectedItem(const QRectF &bounds, bool shadow, bool opaque) : m_bounds(bounds) , m_shadowItem(0) + , m_opaque(opaque) + , m_obscured(false) { if (shadow) { m_shadowItem = new QGraphicsRectItem(bounds, this); @@ -438,6 +440,16 @@ ProjectedItem::ProjectedItem(const QRectF &bounds, bool shadow) m_targetRect = m_bounds; } +void ProjectedItem::setOpaque(bool opaque) +{ + m_opaque = opaque; +} + +bool ProjectedItem::isOpaque() const +{ + return m_opaque; +} + void ProjectedItem::setPosition(const QPointF &a, const QPointF &b) { m_a = a; @@ -489,6 +501,7 @@ WallItem::WallItem(MazeScene *scene, const QPointF &a, const QPointF &b, int typ setImage(book); break; case 2: + setOpaque(false); break; default: setImage(brown); @@ -662,36 +675,48 @@ void ProjectedItem::setImage(const QImage &image) update(); } -void ProjectedItem::updateTransform(const Camera &camera) +void ProjectedItem::setObscured(bool obscured) { - QTransform rotation; - rotation *= QTransform().translate(-camera.pos().x(), -camera.pos().y()); - rotation *= rotatingTransform(camera.yaw()); - QPointF center = (m_a + m_b) / 2; - - QPointF ca = rotation.map(m_a); - QPointF cb = rotation.map(m_b); - - if (ca.y() <= 0 && cb.y() <= 0) { - // hide the item by placing it far outside the scene - // we could use setVisible() but that causes unnecessary - // update to cahced items - QTransform transform; - transform.translate(-1000, -1000); - setTransform(transform); - return; - } + m_obscured = obscured; +} - QMatrix4x4 m; - m = fromRotation(-QLineF(m_b, m_a).angle(), Qt::YAxis) * m; - m = QMatrix4x4().translate(center.x(), 0, center.y()) * m; - m = camera.viewProjectionMatrix() * m; +bool ProjectedItem::isObscured() const +{ + return m_obscured; +} - qreal zm = QLineF(camera.pos(), center).length(); +void ProjectedItem::updateTransform(const Camera &camera) +{ + if (!m_obscured) { + QTransform rotation; + rotation *= QTransform().translate(-camera.pos().x(), -camera.pos().y()); + rotation *= rotatingTransform(camera.yaw()); + QPointF center = (m_a + m_b) / 2; + + QPointF ca = rotation.map(m_a); + QPointF cb = rotation.map(m_b); + + if (ca.y() > 0 || cb.y() > 0) { + QMatrix4x4 m; + m = fromRotation(-QLineF(m_b, m_a).angle(), Qt::YAxis) * m; + m = QMatrix4x4().translate(center.x(), 0, center.y()) * m; + m = camera.viewProjectionMatrix() * m; + + qreal zm = QLineF(camera.pos(), center).length(); + + setVisible(true); + setZValue(-zm); + setTransform(m.toTransform(0)); + return; + } + } - setVisible(true); - setZValue(-zm); - setTransform(m.toTransform(0)); + // hide the item by placing it far outside the scene + // we could use setVisible() but that causes unnecessary + // update to cahced items + QTransform transform; + transform.translate(-1000, -1000); + setTransform(transform); } @@ -822,13 +847,124 @@ bool MazeScene::tryMove(QPointF &pos, const QPointF &delta, Entity *entity) cons return pos != old; } +struct Span +{ + ProjectedItem *item; + + // screen coordinates + float sx1; + float sx2; + + float cy; +}; + +int split(QList &list, float x) +{ + for (int i = 0; i < list.size(); ++i) { + Span &span = list[i]; + if (span.sx2 == x) + return i+1; + + if (span.sx1 <= x && span.sx2 > x) { + Span split = span; + span.sx2 = x; + split.sx1 = x; + list.insert(i+1, split); + return i+1; + } + } + return -1; +} + +bool insertSpan(QList &list, const Span &span, bool checkOnly) +{ + int left = split(list, span.sx1); + int right = split(list, span.sx2); + + bool visible = false; + for (int i = left; i < right; ++i) { + Span &s = list[i]; + if (s.cy > span.cy) { + visible = true; + if (!checkOnly) { + s.item = span.item; + s.cy = span.cy; + } + } + } + return visible; +} + +bool insertProjectedItem(QList &list, ProjectedItem *item, const QTransform &cameraTransform, bool checkOnly) +{ + QPointF ca = cameraTransform.map(item->a()); + QPointF cb = cameraTransform.map(item->b()); + + if (ca.y() <= 0 && cb.y() <= 0) + return false; + + const float clip = 0.0001; + if (ca.y() <= 0) { + float t = (clip - ca.y()) / (cb.y() - ca.y()); + ca.setX(ca.x() + t * (cb.x() - ca.x())); + ca.setY(clip); + } else if(cb.y() <= 0) { + float t = (clip - ca.y()) / (cb.y() - ca.y()); + cb.setX(ca.x() + t * (cb.x() - ca.x())); + cb.setY(clip); + } + + Span span; + span.item = item; + span.sx1 = ca.x() / ca.y(); + span.sx2 = cb.x() / cb.y(); + span.cy = (ca.y() + cb.y()) * 0.5f; + + if (span.sx1 >= span.sx2) + qSwap(span.sx1, span.sx2); + + return insertSpan(list, span, checkOnly); +} + void MazeScene::updateTransforms() { + Span span; + span.item = 0; + span.sx1 = -std::numeric_limits::infinity(); + span.sx2 = std::numeric_limits::infinity(); + span.cy = std::numeric_limits::infinity(); + + QList visibleList; + visibleList << span; + + QTransform rotation; + rotation *= QTransform().translate(-m_camera.pos().x(), -m_camera.pos().y()); + rotation *= rotatingTransform(m_camera.yaw()); + + // first add all opaque items + foreach (ProjectedItem *item, m_projectedItems) { + if (item->isOpaque()) { + item->setObscured(true); + insertProjectedItem(visibleList, item, rotation, false); + } + } + + // mark visible opaque items + for (int i = 0; i < visibleList.size(); ++i) + if (visibleList.at(i).item) + visibleList.at(i).item->setObscured(false); + + // now add all non-opaque items + foreach (ProjectedItem *item, m_projectedItems) { + if (!item->isOpaque()) + item->setObscured(!insertProjectedItem(visibleList, item, rotation, true)); + } + foreach (ProjectedItem *item, m_projectedItems) item->updateTransform(m_camera); foreach (WallItem *item, m_walls) { - if (item->isVisible()) { + if (item->isVisible() && !item->isObscured()) { // embed recursive scene if (QGraphicsProxyWidget *child = item->childItem()) { View *view = qobject_cast(child->widget()); @@ -951,8 +1087,18 @@ void MazeScene::toggleDoors() void MazeScene::moveDoors(qreal value) { - foreach (WallItem *item, m_doors) + bool opaqueStatusChanged = false; + foreach (WallItem *item, m_doors) { item->setAnimationTime(1 - value); + + bool shouldBeOpaque = qFuzzyCompare(value, 1); + if (item->isOpaque() != shouldBeOpaque) { + opaqueStatusChanged = true; + item->setOpaque(shouldBeOpaque); + } + } + if (opaqueStatusChanged) + updateTransforms(); } void MazeScene::toggleRenderer() diff --git a/mazescene.h b/mazescene.h index b0621cf..cfcabe4 100644 --- a/mazescene.h +++ b/mazescene.h @@ -113,13 +113,16 @@ private: class ProjectedItem : public QGraphicsItem { public: - ProjectedItem(const QRectF &bounds, bool shadow = true); + ProjectedItem(const QRectF &bounds, bool shadow = true, bool opaque = true); QPointF a() const { return m_a; } QPointF b() const { return m_b; } virtual void updateTransform(const Camera &camera); + void setOpaque(bool opaque); + bool isOpaque() const; + QRectF boundingRect() const; void setPosition(const QPointF &a, const QPointF &b); @@ -130,6 +133,9 @@ public: void setLightingEnabled(bool enabled); + void setObscured(bool obscured); + bool isObscured() const; + private: QPointF m_a; QPointF m_b; @@ -137,6 +143,9 @@ private: QRectF m_targetRect; QImage m_image; QGraphicsRectItem *m_shadowItem; + + bool m_opaque; + bool m_obscured; }; class WallItem : public ProjectedItem diff --git a/modelitem.cpp b/modelitem.cpp index 9255ad9..4448519 100644 --- a/modelitem.cpp +++ b/modelitem.cpp @@ -38,8 +38,17 @@ #endif #endif +#include + void ModelItem::updateTransform(const Camera &camera) { + QPointF pos(3, 7); + + QVector2D toCamera = QVector2D(camera.pos() - pos).normalized(); + QPointF delta(toCamera.y(), -toCamera.x()); + + setPosition(pos - delta, pos + delta); + ProjectedItem::updateTransform(camera); setTransform(QTransform()); @@ -86,7 +95,7 @@ QMatrix4x4 fromRotation(float angle, Qt::Axis axis); void ModelItem::paint(QPainter *painter, const QStyleOptionGraphicsItem *, QWidget *) { - if (!m_model) + if (!m_model || isObscured()) return; QMatrix4x4 projectionMatrix = QMatrix4x4(painter->transform()) * fromProjection(70); @@ -166,7 +175,7 @@ void ModelItem::paint(QPainter *painter, const QStyleOptionGraphicsItem *, QWidg ModelItem::ModelItem() - : ProjectedItem(QRectF(), false) + : ProjectedItem(QRectF(), false, false) , m_wireframeEnabled(false) , m_normalsEnabled(false) , m_modelColor(153, 255, 0) @@ -178,8 +187,6 @@ ModelItem::ModelItem() , m_program(0) #endif { - QPointF pos(3, 7); - setPosition(pos, pos); setLayout(new QVBoxLayout); m_modelButton = new QPushButton(tr("Load model")); -- cgit v1.2.3