# [Python]Efficient way to group points for delaunay triangulation

 02 February 2013 kdronez Frequenter   portfolio Veselin Gyurov Noobie xD Searching for Job T_T. United Kingdom [Python]Efficient way to group points for delaunay triangulation Elo, I`m trying to create effect like that plexus plug-in 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 __________________ Maya Fluids own xD. Graduate showreel:vimeo.com/64879738 xD share quote
 02 February 2013 ntashev apiApe   portfolio Nikolay Tashev Lighting/Rendering Artist www.cinemotion.bg Sofia, Bulgaria You can build some 3d grid and use that for faster look-up. 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.: ``````grid = { cellX0: { cellY0: { cellZ0:[p1, p2, p3], cellZ1:[p3,p4,p5..]}, cellY1:{{}} }, cellX1:{{{}}}, .... }`````` 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. __________________ ..aut inveniam viam aut faciam.. ::Copy SOP 4 Maya:: share quote
 02 February 2013 kdronez Frequenter   portfolio Veselin Gyurov Noobie xD Searching for Job T_T. United Kingdom Originally Posted by Azrail: You can build some 3d grid and use that for faster look-up. 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.: ``````grid = { cellX0: { cellY0: { cellZ0:[p1, p2, p3], cellZ1:[p3,p4,p5..]}, cellY1:{{}} }, cellX1:{{{}}}, .... }`````` 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. __________________ Maya Fluids own xD. Graduate showreel:vimeo.com/64879738 xD share quote
 02 February 2013 Chrisgibbs Veteran portfolio Chris Gibbs Palmetto bay, USA Originally Posted by kdronez: Elo, I`m trying to create effect like that plexus plug-in 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. share quote
 02 February 2013 kdronez Frequenter   portfolio Veselin Gyurov Noobie xD Searching for Job T_T. United Kingdom 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 ^^. __________________ Maya Fluids own xD. Graduate showreel:vimeo.com/64879738 xD share quote
 02 February 2013 Aikiman Pixel Collisions   portfolio Jeremy Raven Wellington, New Zealand 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. __________________ Vimeo share quote
 02 February 2013 kdronez Frequenter   portfolio Veselin Gyurov Noobie xD Searching for Job T_T. United Kingdom 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 :>. __________________ Maya Fluids own xD. Graduate showreel:vimeo.com/64879738 xD share quote
 02 February 2013 CGTalk Moderation Expert Thread automatically closed 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. __________________ CGTalk Policy/Legalities Note that as CGTalk Members, you agree to the terms and conditions of using this website. share quote

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off CGSociety Society of Digital Artists www.cgsociety.org Powered by vBulletinCopyright ©2000 - 2006, Jelsoft Enterprises Ltd.