Octrees or something similar maybe?

Coding
1

Hi all

Been reading these forums for ages a learnt loads so thanks for that to start with :smiley:

I have recently (today) decided to write a new tool which should replace an artists repetitive task of creating illumination volumes for our game engine. Each volume has a gridded point cloud inside it storing lighting information in 3 dimension making them quite memory heavy

unfortunately im not happy with the solution i have come up with and thought i would ask for some input before continuing.

Currently any room that an artist models needs these illumination volumes created manually. Each volume is represented by a simple world aligned box. The number of volumes per room should be as low as possible with as little wastage as possible outside the graphics geometry
For example, if a room is in a L shape the artist would create 2 boxes to encompass the room, one covering the length of the room and another covering the area around the corner, easy by hand

My current script looks at the bounds of the object in plan view generates points in the xz plane based on a stride value, fires rays up into the geometry to see if it hits
If it does it will create a box the height of the first and last intersect point so to cover the whole height of the room positions the box and steps onto the next point

This gives me a lot of tall boxes, i combine these based on bounds and object centres if they are within a tolerance. The combinations only test to see if the x and y component are the same as the z definitely will be

The problem im having is because these volumes are generated in strips running along the x at the stride intervals then moving across to the next row (y) some of the time there will be very long thin volumes which the game engine doesent like, and because each volume must overlap slightly to ensure a smooth transition this is not a great solution

Any suggestions on how to generate volumes that encompass all of a mesh with as little of the volumes outside the geometry as possible would be greatly appreciated, I was thinking about using octrees to somehow find the extremes of the graphics mesh? if the subdivided octree has a single vertex contained and is furthest away from the bounds center then it should be the border, not sure that would work.

Any help would be greatly appreciated

Thanks in advance
d.b

2

You could look at some sort of convex hull algorithm? This is definitely in the realm of graphics programming algorithms and you should be sure you’re ready to get into heavy duty math before embarking. Nor should you try to ‘cheat’ because you’re constantly going to be losing- invest it doing it right, or just try to facilitate doing it by hand.

3

Hi Rob
You are absolutely right it the heavy maths realms, I have spoken to a few of the programmers where I work and the suggestions were mostly, do it by hand, the result will be better. Slightly disappointed at that but hey. I have tried a new approach by expanding a cube in one axis at a time until it can’t any more then starting the process over again which sort of worked but left gaps in places probably due to the cheating your warned me about :).
A different thought was to give a simple script that created bounds around the maximums of the selected geometry, points or faces whatever they have selected. This ill do for now but I shall still have it as a project to think about.

As for convex hulls they show potential but I would need to determine where to split the geometry which was not easy when I last looked at something like that.

Any who thanks for the thoughts I shall look at the convex hulls again tomorrow to see if it sparks anything

cheers
:slight_smile:

4

Having been down this route and seen many people fail down this route as well- just facilitate doing it by hand :slight_smile: If you aren’t sure about what you’re doing yet (ie, if you haven’t read and understand a half dozen research papers on this topic), you’re not ready to do this.