Kameleon

06-09-2008, 11:23 AM

Is this possible? I want to detect objects nearby a central object within a X radius in 3d space... dunno how to do it thow. Thanks in advance.

View Full Version : Detect objects within X radius?

Kameleon 06-09-2008, 11:23 AM Is this possible? I want to detect objects nearby a central object within a X radius in 3d space... dunno how to do it thow. Thanks in advance. |

ZeBoxx2

06-09-2008, 11:38 AM

presuming you don't already have all your objects in an acceleration structure of sort (a plugin octree or kd-tree being nicest, but a maxscript structure* would do), just use the 'distance' function.

centralObject = $myCentralObject

objectsWithinXRadiusDistance = for o in objects collect (

if ((distance centralObject o) < xRadius) then ( o ) else ( dontCollect )

)

The above is relatively slow whent there's a lot of objects (hence acceleration structures recommended; but if you don't already have one, and this is a one-off, then building that acceleration structure first will take its sweet time as well).

Also to note is that 'distance A B' is the distance between two pivot points; it does not mean that the actual geometry of object B is checked against the geometry of object A. So if you have a very large object B whose mesh surface is within xRadius of object A, but object B's pivot point is not, then it will not get collected.

Edit: * Chapter "MAXScript FAQ > How To Make It Faster > Dice your data into smaller pieces" of the MaxScript help file; doesn't come with sample code, but I'm sure there's code floating around on the interwebs.

centralObject = $myCentralObject

objectsWithinXRadiusDistance = for o in objects collect (

if ((distance centralObject o) < xRadius) then ( o ) else ( dontCollect )

)

The above is relatively slow whent there's a lot of objects (hence acceleration structures recommended; but if you don't already have one, and this is a one-off, then building that acceleration structure first will take its sweet time as well).

Also to note is that 'distance A B' is the distance between two pivot points; it does not mean that the actual geometry of object B is checked against the geometry of object A. So if you have a very large object B whose mesh surface is within xRadius of object A, but object B's pivot point is not, then it will not get collected.

Edit: * Chapter "MAXScript FAQ > How To Make It Faster > Dice your data into smaller pieces" of the MaxScript help file; doesn't come with sample code, but I'm sure there's code floating around on the interwebs.

Kameleon

06-09-2008, 11:44 AM

Thanks ZeBoxx, pivot should be just fine, the thing is that I have looooots of objects, point helpers in this case... so how could I build a kd-tree? I don't even know what that is, only from reading in some sites...

ZeBoxx2

06-09-2008, 12:03 PM

A kd-tree is pretty deep stuff.

The basic idea proposed in the maxscript help is that you stick each node inside a 3D Array, where each 'cell' is no smaller than your desired search radius (no point in going deeper, would just make things slower again). Then to find the objects that are within the xRadius of your object, you only have to check 27 cells (the cell your central object is in, the 8 surrounding cells on one plane, the 9 cells above and the 9 cells below), and can ignore any of the cells further away; which presumably would be a great many number, as otherwise there's nothing to gain from this particular approach :)

The basic idea proposed in the maxscript help is that you stick each node inside a 3D Array, where each 'cell' is no smaller than your desired search radius (no point in going deeper, would just make things slower again). Then to find the objects that are within the xRadius of your object, you only have to check 27 cells (the cell your central object is in, the 8 surrounding cells on one plane, the 9 cells above and the 9 cells below), and can ignore any of the cells further away; which presumably would be a great many number, as otherwise there's nothing to gain from this particular approach :)

Kameleon

06-11-2008, 10:45 PM

I've just wrote some code at home based on an algorithm in wikipedia, I guess this is it, now I'm going to try the nearest points stuff or whatever.... Is this the right way to go? I confess I'm a little lost here.

(

seed(timestamp())

gpointlist=#()

gnamelist=#()

struct KDTNode (name,location,left,right)

fn kdtree objname pointlist kdepth =

(

if pointlist[1]==undefined then return undefined

k=length pointlist[1]

axis=mod kdepth k

median=(pointlist.count)/2

if median==0 then median=1

kdtn=KDTNode()

kdtn.name=objname[median]

kdtn.location=pointlist[median]

kl=for i=1 to median-1 collect pointlist[i]

kn=for i=1 to median-1 collect objname[i]

kdtn.left=kdtree kn kl (kdepth+1)

kr=for i=median+1 to pointlist.count collect pointlist[i]

kn=for i=median+1 to objname.count collect objname[i]

kdtn.right=kdtree kn kr (kdepth+1)

return kdtn

)

for i=1 to 10 do

(

ox=random 0 100

oy=random 0 100

oz=random 0 100

oname=uniquename "foo_"

Point name:oname pos:[ox,oy,oz] isselected:true

append gpointlist $.pos

append gnamelist oname

)

select $foo_*

tree=kdtree gnamelist gpointlist 0

)

(

seed(timestamp())

gpointlist=#()

gnamelist=#()

struct KDTNode (name,location,left,right)

fn kdtree objname pointlist kdepth =

(

if pointlist[1]==undefined then return undefined

k=length pointlist[1]

axis=mod kdepth k

median=(pointlist.count)/2

if median==0 then median=1

kdtn=KDTNode()

kdtn.name=objname[median]

kdtn.location=pointlist[median]

kl=for i=1 to median-1 collect pointlist[i]

kn=for i=1 to median-1 collect objname[i]

kdtn.left=kdtree kn kl (kdepth+1)

kr=for i=median+1 to pointlist.count collect pointlist[i]

kn=for i=median+1 to objname.count collect objname[i]

kdtn.right=kdtree kn kr (kdepth+1)

return kdtn

)

for i=1 to 10 do

(

ox=random 0 100

oy=random 0 100

oz=random 0 100

oname=uniquename "foo_"

Point name:oname pos:[ox,oy,oz] isselected:true

append gpointlist $.pos

append gnamelist oname

)

select $foo_*

tree=kdtree gnamelist gpointlist 0

)

Kameleon

06-12-2008, 04:35 PM

Bobo... help..... please..... :D

CGTalk Moderation

06-12-2008, 04:35 PM

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.

vBulletin v3.0.5, Copyright ©2000-2014, Jelsoft Enterprises Ltd.