Voxel Problem

[Bobo]

Hi Khye,

You are approaching this the wrong way. There is no good reason to use an acceleration method for finding the closest OBJECT if you have less objects than grid cells.

Also, there is no need to define a bounding box using the VoxelBounds - all you need is taking all min values of all objects to be encoded (including the camera) and finding the least of them, then use that as the origin. Even better, you could convert the addresses to strings and allow negative voxel addresses (which are impossible using direct array indexing).
Basically, for each voxel you create an address entry in one array and a data entry in a second array. Then, to resolve the address, you convert the x y z to a string address, findItem into the first array and read the data from the second.

But the grid approach only makes sense if you are looking for, say, the closest vertex to the camera (since a mesh can have a million vertices and a linear search through million vertices would be slower than a search through the neighbour voxels).

Of course, if you intend to search for the closest of 10K spheres, it might make sense.
But the time needed to build the acceleration structure could be longer than the time needed to do a comparison against each position the brute force way.

The main reason it fails is because of the try()catch() context which masks a typo - theVoxelGrid instead of VoxelGrid. Once you fix that and possibly increase the tier, it might find a closest object. But this approach is not very good - you should expand from the camera position outwards - first test the voxel with the same address as the camera. If no sphere is registered in it, expand the tier by one and scal the surrounding 3x3x3 voxels except the central one which you already tested. If you don't find anything there, expand the search to the 5x5x5 grid minus the 3x3x3 voxels already tested previously and so on. This way, if a sphere is registered in the same voxel as the camera, you are not wasting mutiple tests of surrounding voxels before even asking about the closest proximity...

[oatz]

Thanks for the info. As you suspected, my real scene does have 10K spheres. Think phospholipid bilayer

http://www.che.vt.edu/Sum/images/cell-membrane.gif

This was a test scene to verify I had the foundations correct.

I understand the minimum object as the origin and indeed made a function to find the .min of an array of objects. However, the camera would be moving through the scene and so may not be within a voxel. I thought a bounds was a simple method to solve this problem.

I've read your suggestion about the two arrays and I don't quite understand on first glance but I will read it phrase by phrase until it makes sense.

Thanks for the insight.

[Bobo]

Thanks for the info. As you suspected, my real scene does have 10K spheres. This was a test scene to verify I had the foundations correct.

I understand the minimum object as the origin and indeed made function to find the .min of an array of objects. However, the camera would be moving through the scene and so may not be within a voxel. I thought a bounds was a simple method to solve this problem.

I've read your suggestion about the two arrays and I don't quite understand on first glance but I will read it phrase by phrase until it makes sense.

Thanks for the insight.

I will try to explain step by step:

*Instead of creating a nested array with 3 levels depth (for X, Y and Z) which always requires positive indices and thus the knowledge of the min x,y,z, create a one-dimensional array where the data is stored at a single level. Let's call it VoxelData.
*Create a second array called VoxelAddress.
*In the beginning, bot are empty.
*When you encode data in the array, you need the following steps:
**Calculate the address as before.
**NEW: Convert the Point3 value of the address into String. For example, "[-5,4,10]".
**Append this address value to the VoxelAddress array.
**Append the data corresponding to this address to the VoxelData array.
*Since you performed the append to both array at the same time, the data and the address will have the same index inside their corresponding arrays. Alternatively, use the .count of voxelAddress after the append and write the data at that same index in the VoxelData array.

Now in order to read the data from a voxel, you calculate the address, convert to string again, perform (theIndex = findItem VoxelAddress theAddress) and use theIndex to read the record from the VoxelData array - theIndex will be the same for both arrays, so the item in VoxelAddress at index theIndex CORRESPONDS to the item at index theIndex in VoxelData. In Max 2009, MAXScript will provide a bsearch() function which can perform the search through a huge data base even faster as long as it is sorted, but in most cases findItem is pretty fast, especially if the number of voxels is not too high.

The benefit of this scheme is that you are now allowed to convert ANY world coordinate into a voxel address including NEGATIVE and ZERO indices which are otherwise not allowed in the other implementation as arrays need positive indices. Thus, you don't have to figure out any bounds, ANY address is valid. If the findItem call with the address of the camera returns 0, the database contains no data record for that voxel, but the test is still valid. You can ask about an arbitrary point in space and you will either get 0 (no objects in the voxel) or a positive index (data found).

[oatz]

Hey bobo - using your comments this is what I came up with. It works as it should, in my opinion. I made the voxelData be multidimensional since findItem will only return the first item.

clearListener()

(
local voxelData = #()
local voxelAddress = #()
local thecamera = $camera01
local voxelUnit = 100
local objArray = $sphere*
local tier = 3

fn getVoxelAddress pos =
(
local theAddress = pos/voxelUnit
[1+(ceil theAddress.x) as integer, 1+(ceil theAddress.y) as integer, 1+(ceil theAddress.z) as integer ]
)

fn BuildVoxelGrid =
(
for obj in objArray do
(
vA = (getVoxelAddress obj.pos) as string
testIndex = findItem voxelAddress vA
if testIndex == 0 then
(
format "New Item: % at address %\n" obj vA
append voxelAddress vA
append voxelData #(obj)
) else (
format "Repeat Item: %\n" obj
append voxelData[testIndex] obj
)
)
)

fn findItemsInVoxel refObj =
(
local theAddress = getVoxelAddress refObj.pos
for z = theAddress.z-tier to theAddress.z+tier do
(
for y = theAddress.y-tier to theAddress.y+tier do
(
for x = theAddress.x-tier to theAddress.x+tier do
(
try
(
selectMore (voxelData[(findItem voxelAddress ([x,y,z] as string))])
)catch()
)--end x loop
)--end y loop
)--end z loop
)--end fn
-----call functions
BuildVoxelGrid()
findItemsInVoxel thecamera

)--end local

[oatz]

Using this method and added some functionality to my 10K sphere scene in which I test the camera pos with tiers, then set .segs depending on what tier they were found in, and setting hemisphere to false for spheres in vector 0 (identical to camera) the results are:

Brute force setting level of detail : 11,969ms
Voxel method with synced arrays: 922ms
I'd say its worth it.

[CGTalk Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.