[Python]Efficient way to group points for delaunay triangulation

Become a member of the CGSociety

Connect, Share, and Learn with our Large Growing CG Art Community. It's Free!

THREAD CLOSED
 
Thread Tools Search this Thread Display Modes
  02 February 2013
[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
 
  02 February 2013
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::
 
  02 February 2013
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
 
  02 February 2013
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.
 
  02 February 2013
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
 
  02 February 2013
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
 
  02 February 2013
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
 
  02 February 2013
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.
 
Thread Closed share thread



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 vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump
Miscellaneous

All times are GMT. The time now is 06:55 AM.


Powered by vBulletin
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.