02 February 2013  #1 
Frequenter
portfolio
Veselin Gyurov
Noobie xD
Searching for Job T_T.
United Kingdom
Join Date: Mar 2009
Posts: 202

[Python]Efficient way to group points for delaunay triangulation
Elo,
I`m trying to create effect like that plexus plugin for after effects,but in Maya xD.I created procedure that do everything,but the problem is that its not efficient,because its checking each point then creating every possible circle for all points and creating the triangulation which leads to very heavy computations for alot of points T_T. Is there a way to split this into smaller steps so I can have faster performance? Any links to possible formulas are welcome ^^. Heres a little rend I just did with 11 points: http://www.youtube.com/watch?v=4D7w...eature=youtu.be 
02 February 2013  #2 
apiApe
portfolio
Nikolay Tashev
Lighting/Rendering Artist
www.cinemotion.bg
Sofia,
Bulgaria

You can build some 3d grid and use that for faster lookup. Something like this:
1. Get the bounding box of all points 2. Separate that volume to a 3d grid of a given size and than populate each cell with the points that are inside it 3. For each point calculate only the points in the same grid cell and one cell in each direction This is something that can speed the things a bit, but you will need to do it python, since I can't think of a structure in MEL that can hold the grid data, but in python you can just use some nested dictionaries i.e.:
this way you can quickly get the corresponding grid cell by using the point coordinates, like this: we have a bounding box of 10x10x10 units we have a grid of 5x5x5 cells => each cell is 2 units w/h/d our point cell id would be something like X: floor(p.x/2), Y: floor(p.x/2), Z:(p.z/2) so the nearest points would be grid[X][Y][Z] and the adjacent cells' points are gonna be grid[X+/1][Y+1][Z+1]... ... Hope this can help a little. __________________

02 February 2013  #3 
Frequenter
portfolio
Veselin Gyurov
Noobie xD
Searching for Job T_T.
United Kingdom
Join Date: Mar 2009
Posts: 202

Originally Posted by Azrail:
You can build some 3d grid and use that for faster lookup. Something like this:
1. Get the bounding box of all points 2. Separate that volume to a 3d grid of a given size and than populate each cell with the points that are inside it 3. For each point calculate only the points in the same grid cell and one cell in each direction This is something that can speed the things a bit, but you will need to do it python, since I can't think of a structure in MEL that can hold the grid data, but in python you can just use some nested dictionaries i.e.:
this way you can quickly get the corresponding grid cell by using the point coordinates, like this: we have a bounding box of 10x10x10 units we have a grid of 5x5x5 cells => each cell is 2 units w/h/d our point cell id would be something like X: floor(p.x/2), Y: floor(p.x/2), Z:(p.z/2) so the nearest points would be grid[X][Y][Z] and the adjacent cells' points are gonna be grid[X+/1][Y+1][Z+1]... ... Hope this can help a little. That looks like the representation of Voxels in container which is a very interesting idea I will definitly try it thx man ^^. Ou and BTW chestit Trifon zarezan aahahaha xD. 
02 February 2013  #4 
Veteran
portfolio
Chris Gibbs
Palmetto bay,
USA
Join Date: May 2012
Posts: 32

Originally Posted by kdronez:
Elo,
I`m trying to create effect like that plexus plugin for after effects,but in Maya xD.I created procedure that do everything,but the problem is that its not efficient,because its checking each point then creating every possible circle for all points and creating the triangulation which leads to very heavy computations for alot of points T_T. Is there a way... You will need a complex data structure to optimize the procedure. Go to the Max scripting programming forum and look up 'octree'. There is a guy using octrees in python to check for collisions between 1000 objects in milliseconds. 
02 February 2013  #5 
Frequenter
portfolio
Veselin Gyurov
Noobie xD
Searching for Job T_T.
United Kingdom
Join Date: Mar 2009
Posts: 202

Originally Posted by Chrisgibbs:
You will need a complex data structure to optimize the procedure.
Go to the Max scripting programming forum and look up 'octree'. There is a guy using octrees in python to check for collisions between 1000 objects in milliseconds. Thank you for your replay I`m actually checking this right now ^^. 
02 February 2013  #6 
Pixel Collisions
portfolio
Jeremy Raven
Wellington,
New Zealand
Join Date: Jun 2005
Posts: 3,582

Are you just wanting to build something or actually looking for a working solution? Reason I ask is SOuP has a node that does just that, its called the cocoon node. It works in openGL but you can also convert it to curves and attach PaintFX to it. There is also a ramp to control thickness of lines in openGL.

02 February 2013  #7 
Frequenter
portfolio
Veselin Gyurov
Noobie xD
Searching for Job T_T.
United Kingdom
Join Date: Mar 2009
Posts: 202

Originally Posted by Aikiman:
Are you just wanting to build something or actually looking for a working solution? Reason I ask is SOuP has a node that does just that, its called the cocoon node. It works in openGL but you can also convert it to curves and attach PaintFX to it. There is also a ramp to control thickness of lines in openGL.
Elo, I dont really need working solution I prefer to try and do it myself so I can learn stuff from it ^^.It will be good to get that code and see it tho thx man :>. 
Thread Closed share thread 
«
Previous Thread

Next Thread
»


