Hi there,
I jut tested out something and I thought it looked cool so I thought I'd post it. The idea is quite simple.
Imagine you're in a huge city. How do you render it fast? You don't want to render buildings that are too far away in order to save precious rendering time on closer objects which you're more likely to see, BUT, if you do a distance check on every object to see if it's too far away, you'll again lose valid time, just for distance checking.
But intuitively, everything isn't that separately arranged. In a city, you have building blocks, and entire square. Think about it, if you can't see a block of buildings (the actual encompassing block), then you obviously can't see the actual buildings either. Scene graphs solve this, because they are based on a tree structure. If one node is too far away, you don't only not render the child nodes, but you don't even do a distance check on them.
Here's the code. Move the mouse around, and up/down to change viewing radius.
#include "DarkGDK.h"
#include <vector>
// Abstract node
class Node
{
public:
int X, Y, W, H;
std::vector<Node*> Child;
Node(void) : X(0), Y(0), W(0), H(0)
{
}
Node(int x, int y, int w, int h) : X(x), Y(y), W(w), H(h)
{
}
void AddChild(Node* child)
{
Child.push_back(child);
}
virtual void Render(int x, int y, float dist)
{
for (size_t c = 0; c < Child.size(); c++)
{
float distToChild = (x - Child[c]->X) * (x - Child[c]->X) + (y - Child[c]->Y) * (y - Child[c]->Y);
if (distToChild <= (dist * dist))
Child[c]->Render(x, y, dist / 2);
}
}
void Drop(void)
{
while (!Child.empty())
{
if (Child.back())
{
Child.back()->Drop();
delete Child.back();
}
Child.pop_back();
}
}
};
// Square node
class Square : public Node
{
public:
Square(void) : Node()
{
}
Square(int x, int y, int w, int h) : Node(x, y, w, h)
{
}
void Render(int x, int y, float dist)
{
Node::Render(x, y, dist);
//if (Child.empty())
{
dbLine(X - W / 2, Y - H / 2, X + W / 2, Y - H / 2);
dbLine(X - W / 2, Y + H / 2, X + W / 2, Y + H / 2);
dbLine(X - W / 2, Y - H / 2, X - W / 2, Y + H / 2);
dbLine(X + W / 2, Y - H / 2, X + W / 2, Y + H / 2);
}
}
};
void Generate(Node* node, int depth)
{
if (depth == 0) return;
int count = 4;
float ang = 360.0f / count;
for (int c = 0; c < count; c++)
{
int mx = (dbSin(c * 90.0f + 45.0f) >= 0.0f) ? 1 : -1;
int my = (dbCos(c * 90.0f + 45.0f) >= 0.0f) ? 1 : -1;
Node* child = new Square(node->X + (node->W / 4) * mx, node->Y + (node->H / 4) * my, node->W / 2.1f, node->H / 2.1f);
node->AddChild(child);
Generate(child, depth - 1);
}
}
void DarkGDK(void)
{
dbSyncOn();
dbSyncRate(60);
dbSetDisplayMode(1024, 768, 32);
dbRandomize(dbTimer());
Node * test = new Square(512, 394, 750, 750);
Generate(test, 6);
float dist = 1000.0f;
while (LoopGDK())
{
test->Render(dbMouseX(), dbMouseY(), dist);
if (dbUpKey()) dist *= 1.2f;
if (dbDownKey()) dist /= 1.2f;
dbText(10, 10, dbStr(dist));
dbText(10, 50, dbStr(dbScreenFPS()));
dbSync();
dbCLS();
}
test->Drop();
delete test;
return;
}
I had to do this in 2D because the GDK engine automatically renders 3D objects for you (i.e., it just loops through a linear list). If you have a linear list, the amount of time it takes to go through it depends on the size of the list. But with a tree, you can skip entire sections, meaning it takes significantly less time to traverse. Of course, you don't create lines in DBP, you just draw them, which is important in this example.
"everyone forgets a semi-colon sometimes." - Phaelax
