So I was rethinking the problem and I think I found a faster way of going about this that still uses the idea of C0lumbo. So I'm using an octree and I figured that the node which is closest to the camera intersects with all of the visible nodes of my cube. Here are some examples:
Using this, I can almost instantly get the 3 faces which are visible to the camera. The problem however are off cases where 2 or 1 face are visible. The issue here is I don't have a quick and dirty way of getting which of these faces are visible so I might have to settle with rasterizing them or maybe using another property but I'm not sure. Below is an image illustrating 2 of these cases:
If anyone has any other idea's, please write a post. I'm going to begin implementing this algo and will post the code later.