• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0

disk octree

1 post in this topic

Jon Olick stores a node with 8 bits only, 1 for on, 0 for off... but thats not enough information to actually GET to the child and access its data, how the hell does that work with such little information?!?

Share this post

Link to post
Share on other sites
I know that this is an old topic, but it hasn't been answered so I'll give it a try.

8 bit per atom for placement data is all you need. From that you can very quickly generate all the remaining data - all the ID-s of children and brother nodes.
If this is stored in a PNG file, it will be compressed even more and that is how you can get 1.5 bit like Jon Olic states.
The only thing you need to know to reconstruct all the data is the maximal octree level.

If you assume that traversal of data goes like this:
[font="Courier New"][CODE]
| |
B F--+
| | |
C-+ G I
| | | |
... you can easily determine all the ID-s of child nodes, store that in separate texture and send it to graphic card...
[b]Note that if child node exists, its nodeID is always curNodeID+1[/b]. For the next child you just continue from where you've stopped.
You don't really need child node, but nextNodeID for every node and relative position within parent node...
This is what I would choose for my final node structure that can easily be derived from that simplest 8bit disk data structure:
[font="Courier New"][CODE]
struct NODE
unsigned char curNodeLocationMask; // relative position within parent - only 3 bits are important
int nextNodeID;
// I don't need first childNodeID because I know it is curNodeID+1
So this is how traversal would look:
void Travese(RAY ray, int curNodeID, int level, BOX parentBox, BEST_RESULT& bestResult)
BOX myBox = GetSubBox( octreeNodes[curNodeID].curNodeLocationMask ); // To get box of the current node
if( rayIntersect(myBox, ray) )
if( level == maxLevelForCurrentDistance ) // if no children or we don't want to go further...
// find result:
if( curResult > bestResult ) bestResult = curResult;
else Traverse( ray, curNodeID+1, level+1, myBox, bestResult); // Let's do children...
if( VALID(octreeNodes[curNodeID].nextNodeID) ) Traverse( ray, octreeNodes[curNodeID].nextNodeID, level, parentBox, bestResult);
So, from that 1 byte structure stored in a PNG file we've ended up with more suitable 5 byte structure used for traversal which is also stored in a texture and send to the graphic card.
Color and other info can be in seperate textures and packed even stronger with DX compression - once you know curNodeID and resolution of the octree texture, you can determine point in color/normal/spec/emissive texture and sample that data, but you only need that at the very end of traversal (level == maxLevelforCurrentDistance).

So to store entire geometry you need:
* one 8bit PNG texture for octree branching (preferably PNG format)
* one 24 bit texture for atom's color (32 bit if you want transparency)
* one 32 bit texture for atom's plane (normal + D constant of a plane)
* one 24 bit texture with emissive amout, specular amount and specular power.
But those other 3 textures you have to have even with regular triangular mesh, so adding one single channel PNG texture that can be well compressed is nothing much. In fact, in most cases this will take much less space than triangle mesh.

NOTE: I don't use this structure because it isn't suitable for GPU traversal - too much dynamic branching, stack required etc....
I use something else, also 5 byte, but much better for GPU traversal - no branching - no stack - no hassle and very fast.

Problem with this is that you can't order traversal to visit those subcubes that are closer to the ray origin first. Then if you get a hit, you don't even have to go through the rest of the nodes, and you don't need BEST_RESULT variable.

Storing geometry in octree isn't memory expensive at all.

That is all.

EDIT: Small modifications

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
Followers 0