[dasher] Level-of-detail algorithm maintains LP_NODE_BUDGET extant DasherNode objects.
- From: Patrick Welche <pwelche src gnome org>
- To: svn-commits-list gnome org
- Cc:
- Subject: [dasher] Level-of-detail algorithm maintains LP_NODE_BUDGET extant DasherNode objects.
- Date: Sat, 15 Aug 2009 14:23:38 +0000 (UTC)
commit f10c2a54394fb5f02e6c5e77533ed8d0eeab8782
Author: Alan Lawrence <acl33 inf phy cam ac uk>
Date: Mon Aug 10 11:07:03 2009 +0200
Level-of-detail algorithm maintains LP_NODE_BUDGET extant DasherNode objects.
Use priority queue to select best nodes to expand/collapse, with
too-small off-screen nodes collapsed immediately; multiple expansions
amortized over subsequent/extra frames. OldPush algorithm
(BP_OLD_STYLE_PUSH) removed.
ChangeLog | 6 +-
Src/DasherCore/DasherInterfaceBase.cpp | 39 ++-
Src/DasherCore/DasherInterfaceBase.h | 4 +-
Src/DasherCore/DasherModel.cpp | 129 +++-----
Src/DasherCore/DasherModel.h | 18 +-
Src/DasherCore/DasherNode.cpp | 27 ++-
Src/DasherCore/DasherNode.h | 52 +--
Src/DasherCore/DasherView.cpp | 12 +-
Src/DasherCore/DasherView.h | 7 +-
Src/DasherCore/DasherViewSquare.cpp | 501 +++++++++------------------
Src/DasherCore/DasherViewSquare.h | 11 +-
Src/DasherCore/NodeQueue.h | 92 +++++
Src/DasherCore/Parameters.h | 5 +-
Src/MacOSX/Dasher.xcodeproj/project.pbxproj | 4 +-
14 files changed, 395 insertions(+), 512 deletions(-)
---
diff --git a/ChangeLog b/ChangeLog
index 5210130..e15c7fb 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,9 +5,13 @@
* Alphabet{,Map}: Optimise single byte UTF8 case.
* DasherView{,Square}: Remove b1D/bNonLinearity.
* MacOSX: Remove ZippyCache as DasherViewOpenGL makes no use of it.
- * Remove empty DasherView.inl and move input filters into namespace Dasher.
+ * Remove empty DasherView.inl and move input filters into namespace
+ Dasher.
* Change signatures (e.g. GetSymbols) from pointers to references;
g/c IsMore, GetSymbolsFull, LearnText.
+ * Remove a few unused variables / signedness fixes.
+ * Level-of-detail algorithm maintains LP_NODE_BUDGET extant DasherNode
+ objects.
2009-08-08 Alan Lawrence <acl33 inf phy cam ac uk>
diff --git a/Src/DasherCore/DasherInterfaceBase.cpp b/Src/DasherCore/DasherInterfaceBase.cpp
index 380f28b..b5e623d 100644
--- a/Src/DasherCore/DasherInterfaceBase.cpp
+++ b/Src/DasherCore/DasherInterfaceBase.cpp
@@ -568,10 +568,14 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
m_pDasherView->Screen()->SetCaptureBackground(true);
m_pDasherView->Screen()->SetLoadBackground(true);
}
-
- Redraw((bChanged || m_bLastChanged) || m_bRedrawScheduled || bForceRedraw);
-
- m_bLastChanged = bChanged;
+
+ bForceRedraw |= m_bLastChanged;
+ m_bLastChanged = bChanged; //will also be set in Redraw if any nodes were expanded.
+
+ //limit the number of nodes we expand per frame...
+ LimitedNodeQueue nq(max(1l,(500+GetLongParameter(LP_NODE_BUDGET))/1000)); //amortize over multiple frames
+ Redraw(bChanged || m_bRedrawScheduled || bForceRedraw, nq);
+
m_bRedrawScheduled = false;
// This just passes the time through to the framerate tracker, so we
@@ -582,15 +586,7 @@ void CDasherInterfaceBase::NewFrame(unsigned long iTime, bool bForceRedraw) {
bReentered=false;
}
-// PRLW: this is never called.
-void CDasherInterfaceBase::CheckRedraw() {
- if(m_bRedrawScheduled)
- Redraw(true);
-
- m_bRedrawScheduled = false;
-}
-
-void CDasherInterfaceBase::Redraw(bool bRedrawNodes) {
+void CDasherInterfaceBase::Redraw(bool bRedrawNodes, NodeQueue &nodeQueue) {
// No point continuing if there's nothing to draw on...
if(!m_pDasherView)
return;
@@ -598,7 +594,7 @@ void CDasherInterfaceBase::Redraw(bool bRedrawNodes) {
// Draw the nodes
if(bRedrawNodes) {
m_pDasherView->Screen()->SendMarker(0);
- m_pDasherView->RenderModel(m_pDasherModel);
+ if (m_pDasherModel) m_bLastChanged |= m_pDasherModel->RenderToView(m_pDasherView,nodeQueue);
}
// Draw the decorations
@@ -680,7 +676,14 @@ void CDasherInterfaceBase::ChangeScreen(CDasherScreen *NewScreen) {
}
PositionActionButtons();
- Redraw(true);
+ UnlimitedNodeQueue nq; //maintain budget, but allow arbitrary amount of work.
+ Redraw(true, nq); // (we're assuming resolution changes are occasional, i.e.
+ // we don't need to worry about maintaining the frame rate - so we can do
+ // as much work as necessary. We'll only do *any* if the new Screen somehow
+ // allocates pixels to nodes in a different (rather than strictly more/less
+ // generous) fashion - so this is probably more to do with the View changing
+ // (it's behaviour), rather than the Screen. But I guess it allows for future
+ // Views, and/or the View to behave differently on different aspect ratios...
}
void CDasherInterfaceBase::ChangeView() {
@@ -1146,7 +1149,8 @@ int CDasherInterfaceBase::AddLock(const std::string &strDisplay) {
m_mapCurrentLocks[m_iNextLockID] = sNewLock;
++m_iNextLockID;
- Redraw(false);
+ NoNodeQueue nnq; //don't allow change to expansion state.
+ Redraw(false, nnq);
return (m_iNextLockID - 1);
}
@@ -1161,7 +1165,8 @@ void CDasherInterfaceBase::ReleaseLock(int iLockID) {
m_mapCurrentLocks.erase(it);
}
- Redraw(false);
+ NoNodeQueue nnq; //don't allow changes to expansion state.
+ Redraw(false, nnq);
if(m_mapCurrentLocks.size() == 0)
ChangeState(TR_UNLOCK);
diff --git a/Src/DasherCore/DasherInterfaceBase.h b/Src/DasherCore/DasherInterfaceBase.h
index 1211309..1566ebd 100644
--- a/Src/DasherCore/DasherInterfaceBase.h
+++ b/Src/DasherCore/DasherInterfaceBase.h
@@ -355,8 +355,6 @@ public:
m_bRedrawScheduled = true;
};
- void CheckRedraw();
-
std::string GetContext(int iStart, int iLength);
void SetControlOffset(int iOffset);
@@ -526,7 +524,7 @@ protected:
void ChangeAlphabet();
void ChangeColours();
void ChangeView();
- void Redraw(bool bRedrawNodes);
+ void Redraw(bool bRedrawNodes, NodeQueue &nodeQueue);
void SetupActionButtons();
void DestroyActionButtons();
void PositionActionButtons();
diff --git a/Src/DasherCore/DasherModel.cpp b/Src/DasherCore/DasherModel.cpp
index 043d020..d5fc34e 100644
--- a/Src/DasherCore/DasherModel.cpp
+++ b/Src/DasherCore/DasherModel.cpp
@@ -482,9 +482,6 @@ bool CDasherModel::OneStepTowards(myint miMousex, myint miMousey, unsigned long
// works out next viewpoint
Get_new_root_coords(miMousex, miMousey, iNewMin, iNewMax, iTime);
- if(GetBoolParameter(BP_OLD_STYLE_PUSH))
- OldPush(miMousex, miMousey);
-
return UpdateBounds(iNewMin, iNewMax, iTime, pAdded, pNumDeleted);
}
@@ -519,61 +516,6 @@ void CDasherModel::NewFrame(unsigned long Time) {
pTeacher->NewFrame(Time);
}
-void CDasherModel::OldPush(myint iMousex, myint iMousey) {
- // push node under mouse
- CDasherNode *pUnderMouse = Get_node_under_mouse(iMousex, iMousey);
-
- Push_Node(pUnderMouse);
-
- if(Framerate() > 4) {
- // push node under mouse but with x coord on RHS
- CDasherNode *pRight = Get_node_under_mouse(50, iMousey);
- Push_Node(pRight);
- }
-
- if(Framerate() > 8) {
- // push node under the crosshair
- CDasherNode *pUnderCross = Get_node_under_crosshair();
- Push_Node(pUnderCross);
- }
-
- int iRandom = RandomInt();
-
- if(Framerate() > 8) {
- // add some noise and push another node
- CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
- Push_Node(pRight);
- }
-
- iRandom = RandomInt();
-
- if(Framerate() > 15) {
- // add some noise and push another node
- CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
- Push_Node(pRight);
- }
-
- // only do this if Dasher is flying
- if(Framerate() > 30) {
- for(int i = 1; i < int (Framerate() - 30) / 3; i++) {
-
- int iRandom = RandomInt();
-
- if(Framerate() > 8) {
- // add some noise and push another node
- CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 500 - 250);
- Push_Node(pRight);
- }
-
- iRandom = RandomInt();
- // push at a random node on the RHS
- CDasherNode *pRight = Get_node_under_mouse(50, iMousey + iRandom % 1000 - 500);
- Push_Node(pRight);
-
- }
- }
-}
-
void CDasherModel::RecursiveOutput(CDasherNode *pNode, Dasher::VECTOR_SYMBOL_PROB* pAdded) {
if(pNode->Parent() && (!pNode->Parent()->GetFlag(NF_SEEN)))
RecursiveOutput(pNode->Parent(), pAdded);
@@ -736,18 +678,12 @@ void CDasherModel::Push_Node(CDasherNode *pNode) {
if(pNode->GetFlag(NF_ALLCHILDREN)) {
DASHER_ASSERT(pNode->Children().size() > 0);
- // if there are children just give them a poke
- CDasherNode::ChildMap::iterator i;
- for(i = pNode->Children().begin(); i != pNode->Children().end(); i++)
- (*i)->SetFlag(NF_ALIVE, true);
return;
}
// TODO: Do we really need to delete all of the children at this point?
pNode->Delete_children(); // trial commented out - pconlon
- pNode->SetFlag(NF_ALIVE, true);
-
// Populate children creates two levels at once - the groups and their children.
pNode->m_pNodeManager->PopulateChildren(pNode);
@@ -828,27 +764,20 @@ void CDasherModel::Push_Node(CDasherNode *pNode) {
}
-bool CDasherModel::RenderToView(CDasherView *pView, bool bRedrawDisplay, SLockData *pLockData) {
-
- if(pLockData)
- std::cout << "Rendering locked: " << pLockData->strDisplay << std::endl;
+bool CDasherModel::RenderToView(CDasherView *pView, NodeQueue &nodeQueue) {
DASHER_ASSERT(pView != NULL);
DASHER_ASSERT(m_Root != NULL);
CDasherNode *pOldNode = Get_node_under_crosshair();
- std::vector<CDasherNode *> vNodeList;
- std::vector<CDasherNode *> vDeleteList;
-
- bool bReturnValue;
+ bool bReturnValue = false;
std::vector<std::pair<myint,bool> > vGameTargetY;
// The Render routine will fill iGameTargetY with the Dasher Coordinate of the
// youngest node with NF_GAME set. The model is responsible for setting NF_GAME on
// the appropriate Nodes.
- bReturnValue = pView->Render(m_Root, m_Rootmin + m_iDisplayOffset, m_Rootmax + m_iDisplayOffset, vNodeList, vDeleteList, bRedrawDisplay, &vGameTargetY);
-
+ pView->Render(m_Root, m_Rootmin + m_iDisplayOffset, m_Rootmax + m_iDisplayOffset, nodeQueue, true, &vGameTargetY);
/////////GAME MODE TEMP//////////////
if(m_bGameMode)
@@ -856,20 +785,50 @@ bool CDasherModel::RenderToView(CDasherView *pView, bool bRedrawDisplay, SLockDa
pTeacher->SetTargetY(vGameTargetY);
//////////////////////////////////////
+ //ACL Off-screen nodes (zero collapse cost) will have been collapsed already.
+ //Hence, here we act to maintain the node budget....
+ //(however, note that doing this here will only expand one level per frame,
+ //and won't really take effect until the *next* frame!)
+ int iNodeBudget = GetLongParameter(LP_NODE_BUDGET);
+ //note: the 'number of symbols' is the number of leaves in the subtree created by
+ //expanding a node, i.e. excluding group nodes; it also counts only 1 for both
+ //the node at the root of any control mode group, *and* the same for any conversion node.
+ //So, expanding a node could create significantly more children than this.
+ //Doubling this is arbitrary, but I'm just hoping it's a reasonably upper bound for the
+ //number of descendants that'll actually be created; if expansion creates more nodes than
+ //this, the logic below will perform one more contraction, and expansion, per frame than
+ //we want - a performance issue, but hopefully not a correctness issue ;-).
+ int iExpansion = m_pNodeCreationManager->GetAlphabet()->GetNumberSymbols()*2;
+ //first, make sure we are within our budget (probably only in case the budget's changed)
+ while (nodeQueue.hasNodesToCollapse()
+ && currentNumNodeObjects() > iNodeBudget + iExpansion)
+ {
+ nodeQueue.nodeToCollapse()->Delete_children();
+ nodeQueue.popNodeToCollapse();
+ }
- if(!GetBoolParameter(BP_OLD_STYLE_PUSH)) {
- for(std::vector<CDasherNode *>::iterator it(vNodeList.begin()); it != vNodeList.end(); ++it)
- Push_Node(*it);
+ //ok. Since we're within budget, there's no point in doing anything if there aren't
+ //nodes to expand (as zero-cost collapses have already been performed)
+ while (nodeQueue.hasNodesToExpand())
+ {
+ if (currentNumNodeObjects() < iNodeBudget)
+ {
+ Push_Node(nodeQueue.nodeToExpand());
+ nodeQueue.popNodeToExpand();
+ bReturnValue = true;
+ //...and loop.
+ }
+ else if (nodeQueue.hasNodesToCollapse()
+ && nodeQueue.nodeToCollapse()->m_dCost < nodeQueue.nodeToExpand()->m_dCost)
+ {
+ //make room by performing collapse...
+ nodeQueue.nodeToCollapse()->Delete_children();
+ nodeQueue.popNodeToCollapse();
+ //...and see how much room that makes
+ }
+ else break; //not enough room, nothing to collapse.
}
- // TODO: Fix this
- for(std::vector<CDasherNode *>::iterator it(vDeleteList.begin()); it != vDeleteList.end(); ++it)
- {
- if(!(*it)->GetFlag(NF_SUBNODE))
- (*it)->Delete_children();
-
- }
-
CDasherNode *pNewNode = Get_node_under_crosshair();
// TODO: Fix up stats
diff --git a/Src/DasherCore/DasherModel.h b/Src/DasherCore/DasherModel.h
index a6215f8..e6eb66c 100644
--- a/Src/DasherCore/DasherModel.h
+++ b/Src/DasherCore/DasherModel.h
@@ -36,6 +36,7 @@
#include "DasherTypes.h"
#include "FrameRate.h"
#include "NodeCreationManager.h"
+#include "NodeQueue.h"
namespace Dasher {
class CDasherModel;
@@ -120,10 +121,12 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
/// @{
///
- /// Render the model to a given view
+ /// Render the model to a given view. Return if any nodes were
+ /// expanded, as if so we may want to render *another* frame to
+ /// perform further expansion.
///
- bool RenderToView(CDasherView *pView, bool bRedrawDisplay, SLockData *pLockData);
+ bool RenderToView(CDasherView *pView, NodeQueue &nodeQueue);
/// @}
@@ -274,10 +277,6 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
// Information entered so far in this model
double m_dTotalNats;
- // Number of nodes rendered
- int m_iRenderCount;
-
-
CDasherNode *Get_node_under_mouse(myint smousex, myint smousey);
@@ -328,13 +327,6 @@ class Dasher::CDasherModel:public CFrameRate, private NoClones
bool DeleteCharacters(CDasherNode * newnode, CDasherNode * oldnode, int* pNumDeleted = NULL);
///
- /// Old style drilling down of nodes - optionally can still be
- /// called
- ///
-
- void OldPush(myint iMousex, myint iMousey);
-
- ///
/// Make a child of the root into a new root
///
diff --git a/Src/DasherCore/DasherNode.cpp b/Src/DasherCore/DasherNode.cpp
index 3256859..a8ad1fa 100644
--- a/Src/DasherCore/DasherNode.cpp
+++ b/Src/DasherCore/DasherNode.cpp
@@ -37,6 +37,29 @@ using namespace std;
static char THIS_FILE[] = __FILE__;
#endif
#endif
+static int iNumNodes = 0;
+
+int Dasher::currentNumNodeObjects() {return iNumNodes;}
+
+//TODO this used to be inline - should we make it so again?
+CDasherNode::CDasherNode(CDasherNode *pParent, int iLbnd, int iHbnd, SDisplayInfo *pDisplayInfo) {
+ // TODO: Check that these are disabled for debug builds, and that we're not shipping such a build
+ DASHER_ASSERT(iHbnd >= iLbnd);
+ DASHER_ASSERT(pDisplayInfo != NULL);
+
+ m_pParent = pParent;
+ m_iLbnd = iLbnd;
+ m_iHbnd = iHbnd;
+ m_pDisplayInfo = pDisplayInfo;
+ onlyChildRendered = NULL;
+
+ // Default flags (make a definition somewhere, pass flags to constructor?)
+ m_iFlags = 0;
+
+ m_iRefCount = 0;
+ m_iNumSymbols = 0;
+ iNumNodes++;
+}
// TODO: put this back to being inlined
CDasherNode::~CDasherNode() {
@@ -51,6 +74,7 @@ CDasherNode::~CDasherNode() {
// std::cout << "done." << std::endl;
delete m_pDisplayInfo;
+ iNumNodes--;
}
@@ -83,9 +107,6 @@ bool CDasherNode::NodeIsParent(CDasherNode *oldnode) const {
CDasherNode *const CDasherNode::Get_node_under(int iNormalization, myint miY1, myint miY2, myint miMousex, myint miMousey) {
myint miRange = miY2 - miY1;
- // TODO: Manipulating flags in a 'get' method?
- SetFlag(NF_ALIVE, true);
-
ChildMap::const_iterator i;
for(i = GetChildren().begin(); i != GetChildren().end(); i++) {
CDasherNode *pChild = *i;
diff --git a/Src/DasherCore/DasherNode.h b/Src/DasherCore/DasherNode.h
index 1691d09..0cea8cb 100644
--- a/Src/DasherCore/DasherNode.h
+++ b/Src/DasherCore/DasherNode.h
@@ -24,7 +24,6 @@
#include "../Common/Common.h"
#include "../Common/NoClones.h"
#include "DasherTypes.h"
-#include "DasherModel.h"
#include "NodeManager.h"
// These includes no longer required? - pconlon
@@ -36,20 +35,13 @@
// Node flag constants
#define NF_COMMITTED 1
-#define NF_ACTIVE 2
-#define NF_ALIVE 4
-#define NF_SEEN 8
-#define NF_CONVERTED 16
-#define NF_GAME 32
-#define NF_ALLCHILDREN 64
-#define NF_SUBNODE 128
-#define NF_SUPER 256
-#define NF_END_GAME 512
-
-namespace Dasher {
- class CDasherNode;
- class CDasherModel;
-}
+#define NF_SEEN 2
+#define NF_CONVERTED 4
+#define NF_GAME 8
+#define NF_ALLCHILDREN 16
+#define NF_SUBNODE 32
+#define NF_SUPER 64
+#define NF_END_GAME 128
/// \ingroup Model
/// @{
@@ -75,6 +67,8 @@ class Dasher::CDasherNode:private NoClones {
bool bVisible;
std::string strDisplayText;
};
+ CDasherNode *onlyChildRendered; //cache that only one child was rendered (as it filled the screen)
+ double m_dCost; //to expand or collapse
/// Container type for storing children. Note that it's worth
/// optimising this as lookup happens a lot
@@ -87,7 +81,7 @@ class Dasher::CDasherNode:private NoClones {
/// @param iHbnd Upper bound of node within parent
/// @param pDisplayInfo Struct containing information on how to display the node
///
- inline CDasherNode(CDasherNode *pParent, int iLbnd, int iHbnd, SDisplayInfo *pDisplayInfo);
+ CDasherNode(CDasherNode *pParent, int iLbnd, int iHbnd, SDisplayInfo *pDisplayInfo);
/// @brief Destructor
///
@@ -108,10 +102,6 @@ class Dasher::CDasherNode:private NoClones {
/// NF_COMMITTED - Node is 'above' the root, so corresponding symbol
/// has been added to text box, language model trained etc
///
- /// NF_ACTIVE - Node is a decendent of the root node (TODO: Isnt this everything?)
- ///
- /// NF_ALIVE - Node is large enough to be displayed
- ///
/// NF_SEEN - Node has already been output
///
/// NF_CONVERTED - Node has been converted (eg Japanese mode)
@@ -267,27 +257,17 @@ class Dasher::CDasherNode:private NoClones {
};
/// @}
+namespace Dasher {
+ /// Return the number of CDasherNode objects currently in existence.
+ int currentNumNodeObjects();
+}
+
+
/////////////////////////////////////////////////////////////////////////////
// Inline functions
/////////////////////////////////////////////////////////////////////////////
namespace Dasher {
-inline CDasherNode::CDasherNode(CDasherNode *pParent, int iLbnd, int iHbnd, SDisplayInfo *pDisplayInfo) {
- // TODO: Check that these are disabled for debug builds, and that we're not shipping such a build
- DASHER_ASSERT(iHbnd >= iLbnd);
- DASHER_ASSERT(pDisplayInfo != NULL);
-
- m_pParent = pParent;
- m_iLbnd = iLbnd;
- m_iHbnd = iHbnd;
- m_pDisplayInfo = pDisplayInfo;
-
- // Default flags (make a definition somewhere, pass flags to constructor)
- m_iFlags = NF_ACTIVE | NF_ALIVE;
-
- m_iRefCount = 0;
- m_iNumSymbols = 0;
-}
inline const CDasherNode::SDisplayInfo *CDasherNode::GetDisplayInfo() const {
return m_pDisplayInfo;
diff --git a/Src/DasherCore/DasherView.cpp b/Src/DasherCore/DasherView.cpp
index b9924e0..6051609 100644
--- a/Src/DasherCore/DasherView.cpp
+++ b/Src/DasherCore/DasherView.cpp
@@ -55,19 +55,11 @@ void CDasherView::ChangeScreen(CDasherScreen *NewScreen) {
/////////////////////////////////////////////////////////////////////////////
-void CDasherView::RenderModel(CDasherModel *pModel) {
- if(pModel)
- pModel->RenderToView(this, true, NULL);
-}
-
-
-bool CDasherView::Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY) {
+void CDasherView::Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY) {
m_iRenderCount = 0;
Screen()->SetLoadBackground(false);
- RenderNodes(pRoot, iRootMin, iRootMax, vNodeList, vDeleteList, pvGameTargetY);
-
- return true;
+ RenderNodes(pRoot, iRootMin, iRootMax, nodeQueue, pvGameTargetY);
}
int CDasherView::GetCoordinateCount() {
diff --git a/Src/DasherCore/DasherView.h b/Src/DasherCore/DasherView.h
index 934b4f4..9b7b1eb 100644
--- a/Src/DasherCore/DasherView.h
+++ b/Src/DasherCore/DasherView.h
@@ -17,6 +17,7 @@ namespace Dasher {
#include "DasherTypes.h"
#include "DasherComponent.h"
#include "View/DelayedDraw.h"
+#include "NodeQueue.h"
/// \defgroup View Visualisation of the model
/// @{
@@ -119,11 +120,9 @@ public:
/// Drawing more complex structures, generally implemented by derived class
/// @{
- void RenderModel(CDasherModel *pModel);
-
/// Renders Dasher with mouse-dependent items
/// \todo Clarify relationship between Render functions and probably only expose one
- virtual bool Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY);
+ virtual void Render(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, bool bRedrawDisplay, std::vector<std::pair<myint,bool> >* pvGameTargetY);
/// @}
@@ -194,7 +193,7 @@ private:
CDasherInput *m_pInput; // Input device abstraction
/// Renders the Dasher node structure
- virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList, std::vector<std::pair<myint,bool> > *pvGamePointer) = 0;
+ virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer) = 0;
/// Get the co-ordinates from the input device
diff --git a/Src/DasherCore/DasherViewSquare.cpp b/Src/DasherCore/DasherViewSquare.cpp
index bb064e5..5632d99 100644
--- a/Src/DasherCore/DasherViewSquare.cpp
+++ b/Src/DasherCore/DasherViewSquare.cpp
@@ -108,7 +108,7 @@ void CDasherViewSquare::HandleEvent(Dasher::CEvent *pEvent) {
}
void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax,
- std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList,
+ NodeQueue &nodeQueue,
std::vector<std::pair<myint,bool> > *pvGamePointer) {
DASHER_ASSERT(pRoot != 0);
myint iDasherMinX;
@@ -159,7 +159,8 @@ void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iR
// 0, -1, Nodes1, false, true, 1);
// Render the root node (and children)
- RecursiveRender(pRoot, iRootMin, iRootMax, iDasherMaxX, vNodeList, vDeleteList, pvGamePointer,true,iDasherMaxX,0,0);
+ pRoot->m_dCost = INFINITY;
+ RecursiveRender(pRoot, iRootMin, iRootMax, iDasherMaxX, nodeQueue, pvGamePointer,iDasherMaxX,0,0);
// Labels are drawn in a second parse to get the overlapping right
m_pDelayDraw->Draw(Screen());
@@ -168,13 +169,68 @@ void CDasherViewSquare::RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iR
Crosshair((myint)GetLongParameter(LP_OX));
}
-bool CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2,
- int mostleft, std::vector<CDasherNode *> &vNodeList,
- std::vector<CDasherNode *> &vDeleteList,
- std::vector<std::pair<myint,bool> > *pvGamePointer,
- bool bDraw,myint parent_width,int parent_color, int iDepth)
+//min size in *Dasher co-ordinates* to consider rendering a node
+#define QUICK_REJECT 50
+//min size in *screen* (pixel) co-ordinates to render a node
+#define MIN_SIZE 2
+
+bool CDasherViewSquare::CheckRender(CDasherNode *pRender, myint y1, myint y2,
+ int mostleft, NodeQueue &nodeQueue,
+ std::vector<std::pair<myint,bool> > *pvGamePointer,
+ myint parent_width, int parent_color, int iDepth)
{
+ if (y2-y1 >= QUICK_REJECT)
+ {
+ myint iDasherMinX;
+ myint iDasherMinY;
+ myint iDasherMaxX;
+ myint iDasherMaxY;
+ VisibleRegion(iDasherMinX, iDasherMinY, iDasherMaxX, iDasherMaxY);
+
+ if (y1 <= iDasherMaxY && y2 >= iDasherMinY)
+ {
+ screenint iScreenX1;
+ screenint iScreenY1;
+ screenint iScreenX2;
+ screenint iScreenY2;
+
+ Dasher2Screen(0, std::max(y1, iDasherMinY), iScreenX1, iScreenY1);
+ Dasher2Screen(0, std::min(y2, iDasherMaxY), iScreenX2, iScreenY2);
+
+ Cint32 iHeight = std::max(myint(iScreenY2 - iScreenY1),myint( 0));
+
+ if (iHeight >= MIN_SIZE)
+ {
+ //node should be rendered!
+
+ //hence, is potentially collapsible/expandable - set it's cost
+ dasherint iDasherYDist = (y1 > 2048) ? y1 - 2048 : (y2 < 2048) ? 2048-y2 : 0; //minimum dist - better in pixels...?
+ pRender->m_dCost = (y2-y1) / (iDasherYDist / + 50.0 + iDepth);
+ DASHER_ASSERT(!pRender->Parent() || pRender->m_dCost < pRender->Parent()->m_dCost);
+
+ RecursiveRender(pRender, y1, y2, mostleft, nodeQueue, pvGamePointer, parent_width, parent_color, iDepth);
+ return true;
+ }
+ }
+ }
+ // We get here if the node is too small to render or is off-screen.
+ // So, collapse it immediately.
+ //
+ // In game mode, we get here if the child is too small to draw, but we need the
+ // coordinates - if this is the case then we shouldn't delete any children.
+ //
+ // TODO: Should probably render the parent segment here anyway (or
+ // in the above)
+ if(!pRender->GetFlag(NF_GAME) && !pRender->GetFlag(NF_SUBNODE))
+ pRender->Delete_children();
+ return false;
+}
+void CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2,
+ int mostleft, NodeQueue &nodeQueue,
+ std::vector<std::pair<myint,bool> > *pvGamePointer,
+ myint parent_width,int parent_color, int iDepth)
+{
DASHER_ASSERT_VALIDPTR_RW(pRender);
// if(iDepth == 2)
@@ -189,78 +245,55 @@ bool CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
++m_iRenderCount;
- myint temp_parentwidth=parent_width;
// myint trange = y2 - y1;
- int temp_parentcolor=parent_color;
// Attempt to draw the region to the left of this node inside its parent.
-
- // TODO: Pass displayinfo directly here
- bool bDrewFather = false;
-
// if(iDepth == 2) {
// std::cout << "y1: " << y1 << " y2: " << y2 << std::endl;
-
- bDrewFather = RenderNodeFatherFast(parent_color, y1, y2, mostleft,
- pRender->GetDisplayInfo()->strDisplayText,
- pRender->GetDisplayInfo()->bShove,parent_width,
- pRender->GetDisplayInfo()->bVisible);
-
- // TODO: This should be elsewhere
-
- //if(pRender->GetFlag(NF_GAME))// && !pRender->GetFlag(NF_SUBNODE))
- // {
-
- // pvGamePointer->push_back(std::pair<myint,bool>((y1 + y2) / 2, (bDrewFather&&bDraw)));
- // }
-
-
- if(!bDraw || !bDrewFather)
- {
- // We get here if the node is too small to render, or shouldn't be
- // drawn for some other reason.
- //
- // In game mode, we get here if the child is too small to draw, but we need the
- // coordinates - if this is the case then we shouldn't delete any children.
- //
- // TODO: Should probably render the parent segment here anyway (or
- // in the above)
- if(!pRender->GetFlag(NF_GAME))
- {
- pRender->SetFlag(NF_ALIVE, false);
- vDeleteList.push_back(pRender);
- }
- return false;
- }
// Set the NF_SUPER flag if this node entirely frames the visual
// area.
// TODO: too slow?
// TODO: use flags more rather than delete/reparent lists
- // pRender->SetFlag(NF_SUPER, !IsNodeVisible(y1, y2));
myint iDasherMinX;
myint iDasherMinY;
myint iDasherMaxX;
myint iDasherMaxY;
VisibleRegion(iDasherMinX, iDasherMinY, iDasherMaxX, iDasherMaxY);
+ if(GetLongParameter(LP_TRUNCATION) == 0) { // Regular squares
+ DasherDrawRectangle(std::min(parent_width,iDasherMaxX), std::max(y1,iDasherMinY), std::min(y2-y1,iDasherMaxX), std::min(y2,iDasherMaxY), parent_color, -1, Nodes1, false, true, 1);
+ }
+
+ const std::string &sDisplayText(pRender->GetDisplayInfo()->strDisplayText);
+ if( sDisplayText.size() > 0 )
+ {
+ DasherDrawText(y2-y1, y1, y2-y1, y2, sDisplayText, mostleft, pRender->GetDisplayInfo()->bShove);
+ }
+
+
pRender->SetFlag(NF_SUPER, (y1 < iDasherMinY) && (y2 > iDasherMaxY) && ((y2 - y1) > iDasherMaxX));
// If there are no children then we still need to render the parent
if(pRender->ChildCount() == 0) {
-
- RenderNodePartFast(pRender->GetDisplayInfo()->iColour, y1, y2, mostleft,
- pRender->GetDisplayInfo()->strDisplayText,
- pRender->GetDisplayInfo()->bShove,y2-y1);
- vNodeList.push_back(pRender);
-
- return true; // CHANGED BY IGNAS. I return 1 when the child was rendered and in this case the
- //child was rendered.
+ int iTruncation(GetLongParameter(LP_TRUNCATION)); // Trucation farction times -x100;
+ // int iTruncationType(GetLongParameter(LP_TRUNCATIONTYPE));
+
+ if(iTruncation == 0) { // Regular squares
+ DasherDrawRectangle(std::min(y2-y1,iDasherMaxX), std::min(y2,iDasherMaxY),0, std::max(y1,iDasherMinY), pRender->GetDisplayInfo()->iColour, -1, Nodes1, false, true, 1);
+ }
+ //also allow it to be expanded, it's big enough.
+ nodeQueue.pushNodeToExpand(pRender);
+ return;
}
+ //Node has children. It can therefore be collapsed...
+ if (!pRender->GetFlag(NF_GAME) && !pRender->GetFlag(NF_SUBNODE))
+ nodeQueue.pushNodeToCollapse(pRender);
+
// Render children
int norm = (myint)GetLongParameter(LP_NORMALIZATION);
@@ -269,68 +302,91 @@ bool CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
int id=-1;
// int lower=-1,upper=-1;
- temp_parentwidth=y2-y1;
- if(pRender->GetDisplayInfo()->bVisible)
- temp_parentcolor=pRender->GetDisplayInfo()->iColour;
- else
- temp_parentcolor=parent_color;
+ myint temp_parentwidth=y2-y1;
+ int temp_parentcolor = (pRender->GetDisplayInfo()->bVisible)
+ ? pRender->GetDisplayInfo()->iColour
+ : parent_color;
- // TODO: Is bDraw being handled correctly here? What is it even used for?
-
- for(CDasherNode::ChildMap::const_iterator i = pRender->GetChildren().begin();
- i != pRender->GetChildren().end(); i++) {
- id++;
- CDasherNode *pChild = *i;
-
- myint Range = y2 - y1;
- myint newy1 = y1 + (Range * (myint)pChild->Lbnd()) / (myint)norm;/// norm and lbnd are simple ints
- myint newy2 = y1 + (Range * (myint)pChild->Hbnd()) / (myint)norm;
-
- bool bDrawChild = (newy2 - newy1 > 50) || (pChild->GetFlag(NF_ALIVE));
-
- if(bDrawChild){
-
- pChild->SetFlag(NF_ALIVE, true);
-
- bool bChildRendered = RecursiveRender(pChild, newy1, newy2, mostleft,
- vNodeList, vDeleteList, pvGamePointer,
- bDrawChild, temp_parentwidth,
- temp_parentcolor, iDepth + 1);
-
- // if(iDepth == 1) {
- if (bChildRendered) {
- //std::cout << lasty << " " << newy1 << " " << newy2 << std::endl;
-
- if ((bDraw)&&(lasty<newy1)) {
- //if child has been drawn then the interval between him and the
- //last drawn child should be drawn too.
- //std::cout << "Fill in: " << lasty << " " << newy1 << std::endl;
-
- RenderNodePartFast(temp_parentcolor, lasty, newy1, mostleft,
- pRender->GetDisplayInfo()->strDisplayText,
- pRender->GetDisplayInfo()->bShove,
- temp_parentwidth);
-
+ const int Range(y2 - y1);
+
+ if (CDasherNode *pChild = pRender->onlyChildRendered)
+ {
+ //if child still covers screen, render _just_ it and return
+ myint newy1 = y1 + (Range * (myint)pChild->Lbnd()) / (myint)norm;
+ myint newy2 = y1 + (Range * (myint)pChild->Hbnd()) / (myint)norm;
+ if (newy1 < iDasherMinY && newy2 > iDasherMaxY) //still covers entire screen
+ {
+ bool assertsEnabled = false;
+ DASHER_ASSERT (assertsEnabled = true);
+ if (assertsEnabled)
+ {
+ DASHER_ASSERT (newy2 - newy1 > QUICK_REJECT);
+
+ //draw the node. or at least, draw the part of this node to the left of the child....
+ // (this was the procedure renderFatherFast)
+ screenint iScreenX1;
+ screenint iScreenY1;
+ screenint iScreenX2;
+ screenint iScreenY2;
+
+ Dasher2Screen(0, std::max(newy1, iDasherMinY), iScreenX1, iScreenY1);
+ Dasher2Screen(0, std::min(newy2, iDasherMaxY), iScreenX2, iScreenY2);
+
+ DASHER_ASSERT ((iScreenY2 - iScreenY1 > MIN_SIZE) && //big enough to render?
+ (newy1 <= iDasherMaxY) && (newy2 >= iDasherMinY)); //at least partly onscreen!
+ DASHER_ASSERT(pRender->m_dCost == INFINITY);
+ }
+ pChild->m_dCost = INFINITY;
+ //don't inc iDepth, meaningless when covers the screen
+ RecursiveRender(pChild, newy1, newy2, mostleft,
+ nodeQueue, pvGamePointer,
+ temp_parentwidth, temp_parentcolor, iDepth);
+ //leave pRender->onlyChildRendered set, so remaining children are skipped
}
-
- lasty = newy2;
- }
- }
- // }
+ else
+ pRender->onlyChildRendered = NULL;
}
+
+ if (!pRender->onlyChildRendered)
+ { //render all children...
+ for(CDasherNode::ChildMap::const_iterator i = pRender->GetChildren().begin();
+ i != pRender->GetChildren().end(); i++) {
+ id++;
+ CDasherNode *pChild = *i;
+
+ myint newy1 = y1 + (Range * (myint)pChild->Lbnd()) / (myint)norm;/// norm and lbnd are simple ints
+ myint newy2 = y1 + (Range * (myint)pChild->Hbnd()) / (myint)norm;
+ if (CheckRender(pChild, newy1, newy2, mostleft, nodeQueue,
+ pvGamePointer, temp_parentwidth, temp_parentcolor, iDepth+1))
+ {
+ if (pChild->GetFlag(NF_SUPER)) pRender->onlyChildRendered = pChild;
+
+ if (lasty<newy1) {
+ //if child has been drawn then the interval between him and the
+ //last drawn child should be drawn too.
+ //std::cout << "Fill in: " << lasty << " " << newy1 << std::endl;
+
+ RenderNodePartFast(temp_parentcolor, lasty, newy1, mostleft,
+ pRender->GetDisplayInfo()->strDisplayText,
+ pRender->GetDisplayInfo()->bShove,
+ temp_parentwidth);
+ }
+
+ lasty = newy2;
+ }
+ }
- // Finish off the drawing process
-
- // if(iDepth == 1) {
- if (bDraw) {
- // Theres a chance that we haven't yet filled the entire parent, so finish things off if necessary.
- if(lasty<y2) {
- RenderNodePartFast(temp_parentcolor, lasty, y2, mostleft,
- pRender->GetDisplayInfo()->strDisplayText,
- pRender->GetDisplayInfo()->bShove,
- temp_parentwidth);
- }
-
+ // Finish off the drawing process
+
+ // if(iDepth == 1) {
+ // Theres a chance that we haven't yet filled the entire parent, so finish things off if necessary.
+ if(lasty<y2) {
+ RenderNodePartFast(temp_parentcolor, lasty, y2, mostleft,
+ pRender->GetDisplayInfo()->strDisplayText,
+ pRender->GetDisplayInfo()->bShove,
+ temp_parentwidth);
+ }
+ }
// Draw the outline
if(!(pRender->GetFlag(NF_SUBNODE))) {
RenderNodeOutlineFast(pRender->GetDisplayInfo()->iColour,
@@ -341,12 +397,6 @@ bool CDasherViewSquare::RecursiveRender(CDasherNode *pRender, myint y1, myint y2
// }
}
- // if(iDepth == 2)
- // std::cout << "done." << std::endl;
-
- return true;
-}
-
@@ -488,219 +538,6 @@ int CDasherViewSquare::RenderNodePartFast(const int Color, myint y1, myint y2, i
return 1;
}
-// Render a block of code as far as the child, used when the child is
-// visible. TODO: Merge this with the function above
-int CDasherViewSquare::RenderNodeFatherFast(const int parent_color, myint y1, myint y2, int &mostleft, const std::string &sDisplayText, bool bShove,myint iParentWidth, bool bVisible) {
-
- // Commenting because click mode occasionally fails this assert.
- // I don't know why. -- cjb.
- // Why does this return 1? -- pconlon -- I'm changing it to 0.
- if (!(y2 >= y1)) { return 0; }
-
- // TODO - Get sensible limits here (to allow for non-linearities)
- myint iDasherMinX;
- myint iDasherMinY;
- myint iDasherMaxX;
- myint iDasherMaxY;
-
- VisibleRegion(iDasherMinX, iDasherMinY, iDasherMaxX, iDasherMaxY);
-
- screenint iScreenX1;
- screenint iScreenY1;
- screenint iScreenX2;
- screenint iScreenY2;
-
- Dasher2Screen(0, std::max(y1, iDasherMinY), iScreenX1, iScreenY1);
- Dasher2Screen(0, std::min(y2, iDasherMaxY), iScreenX2, iScreenY2);
-
- Cint32 iHeight = std::max(myint(iScreenY2 - iScreenY1),myint( 0));
- Cint32 iWidth = std::max(myint(iScreenX2 - iScreenX1),myint( 0));
-
- if((iHeight <= 1) && (iWidth <= 1))
- return 0; // We're too small to render
-
- if((y1 > iDasherMaxY) || (y2 < iDasherMinY)){
- return 0; // We're entirely off screen, so don't render.
- }
-
- myint iDasherSize(y2 - y1);
-
- // FIXME - get rid of pointless assignment below
-
- int iTruncation(GetLongParameter(LP_TRUNCATION)); // Trucation farction times 100;
- // int iTruncationType(GetLongParameter(LP_TRUNCATIONTYPE));
-
- if(iTruncation == 0) { // Regular squares
- DasherDrawRectangle(std::min(iParentWidth,iDasherMaxX), std::max(y1,iDasherMinY), std::min(iDasherSize,iDasherMaxX), std::min(y2,iDasherMaxY), parent_color, -1, Nodes1, false, true, 1);
- }
- else { }
- myint iDasherAnchorX(iDasherSize);
- if( sDisplayText.size() > 0 )
- {
- DasherDrawText(iDasherAnchorX, y1, iDasherAnchorX, y2, sDisplayText, mostleft, bShove);
- }
- return 1;
-}
-
-// int CDasherViewSquare::RenderNode(const int Color, myint y1, myint y2, int &mostleft, const std::string &sDisplayText, bool bShove) {
-
-// // Commenting because click mode occasionally fails this assert.
-// // I don't know why. -- cjb.
-// if (!(y2 >= y1)) { return 1; }
-
-// // TODO - Get sensible limits here (to allow for non-linearities)
-// myint iDasherMinX;
-// myint iDasherMinY;
-// myint iDasherMaxX;
-// myint iDasherMaxY;
-
-// VisibleRegion(iDasherMinX, iDasherMinY, iDasherMaxX, iDasherMaxY);
-
-// screenint iScreenX1;
-// screenint iScreenY1;
-// screenint iScreenX2;
-// screenint iScreenY2;
-
-// Dasher2Screen(0, std::max(y1, iDasherMinY), iScreenX1, iScreenY1);
-// Dasher2Screen(0, std::min(y2, iDasherMaxY), iScreenX2, iScreenY2);
-
-// Cint32 iHeight = std::max(myint(iScreenY2 - iScreenY1),myint( 0));
-
-// if(iHeight <= 1)
-// return 0; // We're too small to render
-
-// if((y1 > iDasherMaxY) || (y2 < iDasherMinY)){
-// return 0; // We're entirely off screen, so don't render.
-// }
-
-// myint iDasherSize(y2 - y1);
-
-// // FIXME - get rid of pointless assignment below
-
-// int iTruncation(GetLongParameter(LP_TRUNCATION)); // Trucation farction times 100;
-// // int iTruncationType(GetLongParameter(LP_TRUNCATIONTYPE));
-
-// if(iTruncation == 0) { // Regular squares
-// DasherDrawRectangle(std::min(iDasherSize,iDasherMaxX), std::min(y2,iDasherMaxY), 0, std::max(y1,iDasherMinY), Color, -1, Nodes1, GetBoolParameter(BP_OUTLINE_MODE), true, 1);
-// }
-// else {
-// // TODO: Reimplement
-
-// // int iDasherY((myint)GetLongParameter(LP_MAX_Y));
-
-// // int iSpacing(iDasherY / 128); // FIXME - assuming that this is an integer below
-
-// // int iXStart = 0;
-
-// // switch (iTruncationType) {
-// // case 1:
-// // iXStart = iSize - iSize * iTruncation / 200;
-// // break;
-// // case 2:
-// // iXStart = iSize - iSize * iTruncation / 100;
-// // break;
-// // }
-
-// // int iTipMin((y2 - y1) * iTruncation / (200) + y1);
-// // int iTipMax(y2 - (y2 - y1) * iTruncation / (200));
-
-// // int iLowerMin(((y1 + 1) / iSpacing) * iSpacing);
-// // int iLowerMax(((iTipMin - 1) / iSpacing) * iSpacing);
-
-// // int iUpperMin(((iTipMax + 1) / iSpacing) * iSpacing);
-// // int iUpperMax(((y2 - 1) / iSpacing) * iSpacing);
-
-// // if(iLowerMin < 0)
-// // iLowerMin = 0;
-
-// // if(iLowerMax < 0)
-// // iLowerMax = 0;
-
-// // if(iUpperMin < 0)
-// // iUpperMin = 0;
-
-// // if(iUpperMax < 0)
-// // iUpperMax = 0;
-
-// // if(iLowerMin > iDasherY)
-// // iLowerMin = iDasherY;
-
-// // if(iLowerMax > iDasherY)
-// // iLowerMax = iDasherY;
-
-// // if(iUpperMin > iDasherY)
-// // iUpperMin = iDasherY;
-
-// // if(iUpperMax > iDasherY)
-// // iUpperMax = iDasherY;
-
-// // while(iLowerMin < y1)
-// // iLowerMin += iSpacing;
-
-// // while(iLowerMax > iTipMin)
-// // iLowerMax -= iSpacing;
-
-// // while(iUpperMin < iTipMax)
-// // iUpperMin += iSpacing;
-
-// // while(iUpperMax > y2)
-// // iUpperMax -= iSpacing;
-
-// // int iLowerCount((iLowerMax - iLowerMin) / iSpacing + 1);
-// // int iUpperCount((iUpperMax - iUpperMin) / iSpacing + 1);
-
-// // if(iLowerCount < 0)
-// // iLowerCount = 0;
-
-// // if(iUpperCount < 0)
-// // iUpperCount = 0;
-
-// // int iTotalCount(iLowerCount + iUpperCount + 6);
-
-// // myint *x = new myint[iTotalCount];
-// // myint *y = new myint[iTotalCount];
-
-// // // Weird duplication here is to make truncated squares possible too
-
-// // x[0] = 0;
-// // y[0] = y1;
-// // x[1] = iXStart;
-// // y[1] = y1;
-
-// // x[iLowerCount + 2] = iDasherSize;
-// // y[iLowerCount + 2] = iTipMin;
-// // x[iLowerCount + 3] = iDasherSize;
-// // y[iLowerCount + 3] = iTipMax;
-
-// // x[iTotalCount - 2] = iXStart;
-// // y[iTotalCount - 2] = y2;
-// // x[iTotalCount - 1] = 0;
-// // y[iTotalCount - 1] = y2;
-
-// // for(int i(0); i < iLowerCount; ++i) {
-// // x[i + 2] = (iLowerMin + i * iSpacing - y1) * (iDasherSize - iXStart) / (iTipMin - y1) + iXStart;
-// // y[i + 2] = iLowerMin + i * iSpacing;
-// // }
-
-// // for(int j(0); j < iUpperCount; ++j) {
-// // x[j + iLowerCount + 4] = (y2 - (iUpperMin + j * iSpacing)) * (iDasherSize - iXStart) / (y2 - iTipMax) + iXStart;
-// // y[j + iLowerCount + 4] = iUpperMin + j * iSpacing;
-// // }
-
-// // DasherPolygon(x, y, iTotalCount, Color);
-
-// // delete x;
-// // delete y;
-// }
-
-// myint iDasherAnchorX(iDasherSize);
-
-// if( sDisplayText.size() > 0 )
-// DasherDrawText(iDasherAnchorX, y1, iDasherAnchorX, y2, sDisplayText, mostleft, bShove);
-
-// return 1;
-// }
-
/// Convert screen co-ordinates to dasher co-ordinates. This doesn't
/// include the nonlinear mapping for eyetracking mode etc - it is
/// just the inverse of the mapping used to calculate the screen
diff --git a/Src/DasherCore/DasherViewSquare.h b/Src/DasherCore/DasherViewSquare.h
index f7366d1..a103a73 100644
--- a/Src/DasherCore/DasherViewSquare.h
+++ b/Src/DasherCore/DasherViewSquare.h
@@ -109,15 +109,17 @@ private:
///
/// Render the current state of the model.
///
-
- virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList, std::vector<std::pair<myint,bool> > *pvGamePointer);
-
+ virtual void RenderNodes(CDasherNode *pRoot, myint iRootMin, myint iRootMax, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer);
///
/// Recursively render all nodes in a tree. Responsible for all the Render_node calls
///
- bool RecursiveRender(CDasherNode * Render, myint y1, myint y2, int mostleft, std::vector<CDasherNode *> &vNodeList, std::vector<CDasherNode *> &vDeleteList, std::vector<std::pair<myint,bool> > *pvGamePointer, bool bDraw,myint parent_width,int parent_color, int iDepth);
+ void RecursiveRender(CDasherNode * Render, myint y1, myint y2, int mostleft, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
+
+ ///Check that a node is large enough, and onscreen, to render;
+ ///calls RecursiveRender if so, or collapses the node immediately if not
+ bool CheckRender(CDasherNode * Render, myint y1, myint y2, int mostleft, NodeQueue &nodeQueue, std::vector<std::pair<myint,bool> > *pvGamePointer, myint parent_width,int parent_color, int iDepth);
/// Render a single node
/// \param Color The colour to draw it
@@ -134,7 +136,6 @@ private:
int RenderNodeOutlineFast(const int Color, myint y1, myint y2, int &mostleft, const std::string &sDisplayText, bool bShove);
int RenderNodePartFast(const int Color, myint y1, myint y2, int &mostleft, const std::string &sDisplayText, bool bShove, myint iParentWidth);
- int RenderNodeFatherFast(const int parent_color, myint y1, myint y2, int &mostleft, const std::string &sDisplayText, bool bShove,myint iParentWidth, bool bVisible);
#ifdef _WIN32
///
/// FIXME - couldn't find windows version of round(double) so here's one!
diff --git a/Src/DasherCore/NodeQueue.h b/Src/DasherCore/NodeQueue.h
new file mode 100644
index 0000000..f79a2bf
--- /dev/null
+++ b/Src/DasherCore/NodeQueue.h
@@ -0,0 +1,92 @@
+/*
+ * NodeQueue.h
+ * Dasher
+ *
+ * Created by Alan Lawrence on 03/06/2009.
+ * Copyright 2009 Cavendish Laboratory. All rights reserved.
+ *
+ */
+
+#ifndef __NodeQueue_h__
+#define __NodeQueue_h__
+
+#include <vector>
+#include <queue>
+#include <limits>
+#include "DasherNode.h"
+
+namespace Dasher {
+class NodeQueue
+{
+public:
+ virtual void pushNodeToExpand(CDasherNode *pNode)=0;
+ virtual bool hasNodesToExpand()=0;
+ virtual CDasherNode *nodeToExpand()=0;
+ virtual void popNodeToExpand()=0;
+ virtual void pushNodeToCollapse(CDasherNode *pNode)=0;
+ virtual bool hasNodesToCollapse()=0;
+ virtual CDasherNode *nodeToCollapse()=0;
+ virtual void popNodeToCollapse()=0;
+};
+
+class NoNodeQueue : public NodeQueue
+{
+public:
+ void pushNodeToExpand(CDasherNode *pNode) {}
+ bool hasNodesToExpand() {return false;}
+ CDasherNode *nodeToExpand() {return NULL;}
+ void popNodeToExpand() {}
+ void pushNodeToCollapse(CDasherNode *pNode) {}
+ bool hasNodesToCollapse() {return false;}
+ CDasherNode *nodeToCollapse() {return NULL;}
+ void popNodeToCollapse() {}
+};
+
+class NodeComparator
+{
+public:
+ int operator() (CDasherNode * &x, CDasherNode * &y)
+ {
+ return x->m_dCost < y->m_dCost;
+ }
+};
+
+class ReverseNodeComparator
+{
+public:
+ int operator() (CDasherNode * &x, CDasherNode * &y)
+ {
+ return x->m_dCost > y->m_dCost;
+ }
+};
+
+class UnlimitedNodeQueue : public NodeQueue
+{
+public:
+ void pushNodeToExpand(CDasherNode *pNode) {sExpand.push(pNode);}
+ bool hasNodesToExpand() {return sExpand.size()>0;}
+ CDasherNode *nodeToExpand() {return sExpand.top();}
+ void popNodeToExpand() {sExpand.pop();}
+ void pushNodeToCollapse(CDasherNode *pNode) {sDelete.push(pNode);}
+ bool hasNodesToCollapse() {return sDelete.size()>0;}
+ CDasherNode *nodeToCollapse() {return sDelete.top();}
+ void popNodeToCollapse() {sDelete.pop();}
+protected:
+ std::priority_queue<CDasherNode *,std::vector<CDasherNode * >,NodeComparator> sExpand;
+ std::priority_queue<CDasherNode *, std::vector<CDasherNode *>,ReverseNodeComparator> sDelete;
+};
+
+//limits expansion to a few nodes (per instance i.e. per frame)
+ //(collapsing is at present unlimited, have to test this...)
+class LimitedNodeQueue : public UnlimitedNodeQueue
+{
+public:
+ LimitedNodeQueue(int _budget) : budget(_budget) {}
+ bool hasNodesToExpand() {return budget>0 && UnlimitedNodeQueue::hasNodesToExpand();}
+ CDasherNode *nodeToExpand() {return budget>0 ? UnlimitedNodeQueue::nodeToExpand() : NULL;}
+ void popNodeToExpand() {if (budget>0) {UnlimitedNodeQueue::popNodeToExpand(); budget--;}}
+private:
+ int budget;
+};
+}
+#endif /*defined __NodeQueue_h__*/
diff --git a/Src/DasherCore/Parameters.h b/Src/DasherCore/Parameters.h
index 9100f58..c111d14 100644
--- a/Src/DasherCore/Parameters.h
+++ b/Src/DasherCore/Parameters.h
@@ -42,7 +42,7 @@ enum {
BP_BUTTONMENU, BP_BUTTONPULSING, BP_BUTTONSTEADY,
BP_BUTTONDIRECT, BP_BUTTONFOURDIRECT, BP_BUTTONALTERNATINGDIRECT,
BP_COMPASSMODE, BP_SOCKET_INPUT_ENABLE, BP_SOCKET_DEBUG,
- BP_OLD_STYLE_PUSH, BP_CIRCLE_START, BP_GLOBAL_KEYBOARD,
+ BP_CIRCLE_START, BP_GLOBAL_KEYBOARD,
BP_SMOOTH_OFFSET, BP_CONVERSION_MODE, BP_PAUSE_OUTSIDE, BP_BACKOFF_BUTTON,
BP_TWOBUTTON_REVERSE, BP_2B_INVERT_DOUBLE, BP_SLOW_START, BP_FIXED_MARKERS, END_OF_BPS
};
@@ -56,6 +56,7 @@ enum {
LP_LM_MIXTURE, LP_MOUSE_POS_BOX, LP_NORMALIZATION, LP_LINE_WIDTH,
LP_LM_WORD_ALPHA, LP_USER_LOG_LEVEL_MASK,
LP_ZOOMSTEPS, LP_B, LP_S, LP_Z, LP_R, LP_RIGHTZOOM,
+ LP_NODE_BUDGET,
LP_BOOSTFACTOR, LP_AUTOSPEED_SENSITIVITY, LP_SOCKET_PORT, LP_SOCKET_INPUT_X_MIN, LP_SOCKET_INPUT_X_MAX,
LP_SOCKET_INPUT_Y_MIN, LP_SOCKET_INPUT_Y_MAX, LP_OX, LP_OY, LP_MAX_Y, LP_INPUT_FILTER,
LP_CIRCLE_PERCENT, LP_TWO_BUTTON_OFFSET, LP_HOLD_TIME, LP_MULTIPRESS_TIME,
@@ -154,7 +155,6 @@ static bp_table boolparamtable[] = {
{BP_COMPASSMODE, "ButtonCompassMode", PERS, false, "Compass mode"},
{BP_SOCKET_INPUT_ENABLE, "SocketInputEnable", PERS, false, "Read pointer coordinates from network socket instead of mouse"},
{BP_SOCKET_DEBUG, "SocketInputDebug", PERS, false, "Print information about socket input processing to console"},
- {BP_OLD_STYLE_PUSH, "OldStylePush", PERS, false, "Old style node pushing algorithm"},
{BP_CIRCLE_START, "CircleStart", PERS, false, "Start on circle mode"},
{BP_GLOBAL_KEYBOARD, "GlobalKeyboard", PERS, false, "Whether to assume global control of the keyboard"},
{BP_SMOOTH_OFFSET, "DelayView", !PERS, false, "Smooth dynamic-button-mode jumps over several frames"},
@@ -198,6 +198,7 @@ static lp_table longparamtable[] = {
{LP_Z, "ButtonMenuBackwardsBox", PERS, 1, "Number of back-up boxes for button menu mode"},
{LP_R, "ButtonModeNonuniformity", PERS, 0, "Button mode box non-uniformity"},
{LP_RIGHTZOOM, "ButtonCompassModeRightZoom", PERS, 5120, "Zoomfactor (*1024) for compass mode"},
+ {LP_NODE_BUDGET, "NodeBudget", PERS, 3000, "Target (min) number of node objects to maintain"},
{LP_BOOSTFACTOR, "BoostFactor", !PERS, 100, "Boost/brake factor (multiplied by 100)"},
{LP_AUTOSPEED_SENSITIVITY, "AutospeedSensitivity", PERS, 100, "Sensitivity of automatic speed control (percent)"},
{LP_SOCKET_PORT, "SocketPort", PERS, 20320, "UDP/TCP socket to use for network socket input"},
diff --git a/Src/MacOSX/Dasher.xcodeproj/project.pbxproj b/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
index d5f842c..dc98680 100755
--- a/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
+++ b/Src/MacOSX/Dasher.xcodeproj/project.pbxproj
@@ -363,6 +363,7 @@
335DB0FB100B332C006DB155 /* alphabet.spyDict.xml in Resources */ = {isa = PBXBuildFile; fileRef = 335DB0FA100B332C006DB155 /* alphabet.spyDict.xml */; };
335DB101100B3358006DB155 /* training_spyDict.txt in Resources */ = {isa = PBXBuildFile; fileRef = 335DB100100B3358006DB155 /* training_spyDict.txt */; };
335DB122100B3606006DB155 /* PinYinConversionHelper.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1948BE760C226CFD001DFA32 /* PinYinConversionHelper.cpp */; };
+ 336C2D13101A31EE00CCD70D /* NodeQueue.h in Headers */ = {isa = PBXBuildFile; fileRef = 336C2D12101A31EE00CCD70D /* NodeQueue.h */; };
33ABFEC60FC379EA00EA2BA5 /* ButtonMultiPress.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 33ABFEC40FC379EA00EA2BA5 /* ButtonMultiPress.cpp */; };
33ABFEC70FC379EA00EA2BA5 /* ButtonMultiPress.h in Headers */ = {isa = PBXBuildFile; fileRef = 33ABFEC50FC379EA00EA2BA5 /* ButtonMultiPress.h */; };
33E173C70F3E0B6400D19B38 /* Makefile.am in Resources */ = {isa = PBXBuildFile; fileRef = 33E173A70F3E0B6400D19B38 /* Makefile.am */; };
@@ -782,7 +783,8 @@
335901B31009E5A900821255 /* ConversionHelper.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ConversionHelper.cpp; sourceTree = "<group>"; };
335DB0FA100B332C006DB155 /* alphabet.spyDict.xml */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.xml; path = alphabet.spyDict.xml; sourceTree = "<group>"; };
335DB100100B3358006DB155 /* training_spyDict.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = training_spyDict.txt; sourceTree = "<group>"; };
- 33ABFEC40FC379EA00EA2BA5 /* ButtonMultiPress.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = ButtonMultiPress.cpp; path = ../DasherCore/ButtonMultiPress.cpp; sourceTree = SOURCE_ROOT; };
+ 336C2D12101A31EE00CCD70D /* NodeQueue.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NodeQueue.h; sourceTree = "<group>"; };
+ 33ABFEC40FC379EA00EA2BA5 /* ButtonMultiPress.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ButtonMultiPress.cpp; sourceTree = "<group>"; };
33ABFEC50FC379EA00EA2BA5 /* ButtonMultiPress.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ButtonMultiPress.h; sourceTree = "<group>"; };
33E173A70F3E0B6400D19B38 /* Makefile.am */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = Makefile.am; sourceTree = "<group>"; };
33E173A80F3E0B6400D19B38 /* training_albanian_SQ.txt */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = training_albanian_SQ.txt; sourceTree = "<group>"; };
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
