Dorian Fevrier's blog

Sommaire

• Ce qu'on cherche à faire
• Le principe
  • Remplir un mesh de particule
  • Récupérer les positions des particules
  • Calcul du rayon maximal de chaque particule
  • Déterminer la plus grosse sphère
  • Suppression des particules "inutiles"
  • Et...
• Das Code!
  • En brut
  • Les détails
• BEKRI Djelloul

:longBar:

Ce qu'on cherche à faire

Et bien... Ça:

Avant de commencer, il faut savoir que les algorithmes permettant de mettre des sphères dans de la géométrie (sphere packing algorythms) sont des sujets de recherche fréquents:

• Inner Sphere Trees for 6-DOF Haptic Rendering
• A GPU-Assisted Prototype Guided Sphere Packing Algorithm for Arbitrary Objects
• Et Google...

Et hop! Une petite vidéo du principe:

Merci à Adrien Herubel pour ces quelques liens. :)

Ces algorithmes peuvent servir à pleins de chose. Un exemple assez précis est de "sortir" les lignes de force/d’énergie d'un mesh pour lui appliquer un rigging automatique:

• ART - Auto-Rigging Tool

A vous de voir quoi en tirer. :sourit:

Je vais d'abords expliquer le principe. Ensuite je vous donnerai, en brut, le script de Djelloul que je commenterai, ligne à ligne. Si vous scritpez un peu, vous verrez qu'il y a énormément d'optimisations possibles mais ce n'était pas sa priorité lorsqu'il m'a montré ce script.

Cette méthode est donc un peu longue en temps machine. :seSentCon:

Mais si il vous en prend l'envie de vouloir optimiser ce code, n'hésitez pas à me l'envoyer. Je me ferai un plaisir de faire un lien et un commentaire ici même. :bravo:

:longBar:

Le principe

Et bien oui, comme toute technique un chouilla compliqué, il y a de la théorie! :jdicajdirien:

Vous allez voir que le principe est assez simple et si vous pigez le truc, vous pourrez l'adapter à vos besoins.

Remplir un mesh de particule

La première chose à faire est de remplir un mesh de particule.

Si vous suivez régulièrement mon blog, j'ai proposé une solution mais Djelloul, dans sa version (et surtout pour gagner du temps :laClasse: ) utilise particleFill qui remplit le mesh sélectionné de nParticle.

Récupérer les positions des particules

On récupère la position dans l'espace de chacune des particules crées.

Calcul du rayon maximal de chaque particule

Une fois qu'on a toutes les positions des particules, pour chacune d'elle, on va récupérer la taille maximale (le rayon) que pourrait atteindre une sphère placée sur cette particule, sans sortir de la géométrie.

Pour calculer cette taille, on va récupérer le point de la géométrie le plus proche de la particule courante. Et pour cela on va utiliser un node que vous connaissez peut être déjà. Je vous le donne en mille, il s'agit du closestPointOnMesh. Je ne vais pas réexpliquer le principe, je me suis déjà étalé dessus.

Arrivé ici, nous avons deux choses:

• Une liste de points dans l'espace (les particules).
• Une liste de rayon.

Et bien entendu, ces deux listes font la même taille (un rayon par particule). Si vous n'avez pas compris ça, il peut être intéressant de relire des quelques points plus haut. :siffle:

On peut donc maintenant considérer qu'un ensemble "point+rayon" est une sphère.

Déterminer la plus grosse sphère

Il faut bien un point de départ et dans le cas de cette algorithme, tout commence par la sphère la plus grosse.

Pour savoir ça, on parcourt tous les points et on regarde leur rayon. On ne garde que le point ayant le rayon le plus gros.

Une fois tous les points parcourus, le point ayant le rayon le plus gros est considéré comme la sphère la plus grosse (si vous ne comprenez pas ça... :septic: ).

Notez aussi que c'est à cet endroit dans le mesh que (pardonnez moi l'expression) "l'espace est le plus grand".

Suppression des particules "inutiles"

Une fois qu'on sait quelle est la sphère (l'ensemble point-rayon) la plus grosse dans le mesh, on peut supprimer toute les autres sphères qui sont en collision avec elle.

L'avantage d'utiliser des sphères pour des tests de collision c'est qu'il suffit de deux points et de deux rayons (un par sphère) pour savoir si elles se touchent, c'est tout!

Ça tombe bien, c'est exactement ce que l'on a!

Vérifier ça est assez simple:

Dans un premier temps, on récupère la distance entre les deux points (en jaune). Une petite recherche sur google et on trouve facilement la formule:

distance = sqrt( (pt1.x-pt2.x)² + (pt1.z-pt2.z)² + (pt1.z-pt2.z)² )

sqrt(x) étant la racine carré de x.

Une fois qu'on a la distance, on additionne la taille des deux rayons et on compare!

Si la distance entre les deux centres des sphères est plus petite que la somme de leurs rayons, les sphères se touchent.

Et...

...Caetera! On recommence! :sourit:

En effet, tant qu'on a supprimé au moins un point, on recommence la boucle avec tousles points restants, et ce, jusqu'à ce qu'il ne reste aucun point à supprimer:

• Déterminer la plus grosse sphère
• Suppression des particules "inutiles"
• Etc...

Arrivé ici vous devriez avoir une vision globale de "comment que ça fonctionne ce truc". :joue:

Mais sans plus tarder: Le code!

:longBar:

Das Code!

En brut

Voici le code de Djelloul, brut de pomme! Fait avec ses petits doigts, sans modifs de ma part.

[python]

from pymel.all import *
import maya.mel as mel
import maya.cmds as cmds
import time

step = 100
######################################
def mag(p1,p2):
	return ((p1[0]-p2[0])**2+(p1[1]-p2[1])**2+(p1[2]-p2[2])**2)**.5

if(len(ls(sl=1))):
	obj=ls(sl=1)[0]
	try:
		particleFill(rs=step,maxX=1,maxY=1,maxZ=1,minX=0,minY=0,minZ=0,pd=1,cp=0)
	except:
		pass
	part = ls(sl=1)[0]
	partShape = listRelatives(part,shapes=1)[0]

	closest=createNode("closestPointOnMesh")
	connectAttr(obj+".outMesh",closest+".inMesh")
	points=getAttr(part+".position")
	delete(part)

	rayons=[]
	for point in points:
		setAttr(closest+".inPosition",point)
		rayons.append(mag(point,getAttr(closest+".position")))
	delete(closest)

	newPoints,newRayons = [],[]
	while len(points)>0:
		print "%s points encore a traiter..." % len(points)
		action,p,max,maxId = 0,[],-1,-1
		for i in range(len(points)):
			if rayons[i]>max:
				max,p,maxId=rayons[i],points[i],i
		del(points[maxId])
		del(rayons[maxId])
		newPoints.append(p)
		newRayons.append(max*1.2)
		i=0
		while i<len(points):
			if mag(p,points[i])<rayons[i]+max:
				del(points[i])
				del(rayons[i])
			else:
				i=i+1

	#Attention ! Le mode de creation des nParticles par default doit etre "Points" !
	part = nParticle(p=newPoints)[1]
	setAttr(part+".particleRenderType",4)
	setAttr(part+".ignoreSolverGravity",1)
	addAttr(part,ln="radiusPP",dt="doubleArray")
	setAttr(part+".radiusPP",newRayons,type="doubleArray")
	print "Fini."
else:
	print("Il faut selectionner un mesh !")

Les détails

Bon, le premier truc est de passer les nParticules par défaut sur "Points":

Vous pouvez l'essayer! Sélectionnez votre mesh et lancez le! (Si vous avez mis 100 en step, il vaut mieux être patient. Mettez 30 pour vos tests).

Pour la suite, je partirai de cette forme:

On commence par une petite déclaration d'une fonction qui renvoie la distance entre deux points.

[python]
def mag(p1,p2):
	return ((p1[0]-p2[0])**2+(p1[1]-p2[1])**2+(p1[2]-p2[2])**2)**.5

Si vous regardez bien, c'est la version Python de la formule que j'ai donné plus haut.

[python]
x**2

En Python, ça veut dire x² (au carré).

Et:

[python]
x**0.5

Ça veut dire "racine carré".

En gros, chaque point (p1 et p2) est une liste de trois valeurs (x, y, z) et on s'en sert pour calculer la distance qui les sépares.

[python]
if(len(ls(sl=1))):
	obj=ls(sl=1)[0]
	try:
		particleFill(rs=step,maxX=1,maxY=1,maxZ=1,minX=0,minY=0,minZ=0,pd=1,cp=0)
	except:
		pass

Ici on s'assure que l'objet que l'on souhaite remplir est sélectionné et on lui applique un particleFill qui le remplit de nParticle (notez que c'est ici qu'est utilisé la variable step):

[python]
part = ls(sl=1)[0]
partShape = listRelatives(part,shapes=1)[0]

Quand on créé un système de particule, Maya le sélectionne automatiquement. Ici, il récupère la sélection ("part"). La variable "partShape" ne sera pas utilisée dans la suite du script.

[python]
closest=createNode("closestPointOnMesh")
connectAttr(obj+".outMesh",closest+".inMesh")

On créé le node de closestPointOnMesh et on lui connecte la géométrie qu'on souhaite remplir.

[python]
points=getAttr(part+".position")
delete(part)

On récupère la position de toute les particules du système dans une variable ("points"), puis on supprime le système de particule.

Vous comprenez donc que l'intérêt d'utiliser le particleFill est uniquement de récupérer, sans trop se casser le c** une liste de positions (x, y, z) qui soit "dans le mesh".

[python]
rayons=[]
for point in points:
	setAttr(closest+".inPosition",point)
	rayons.append(mag(point,getAttr(closest+".position")))
delete(closest)

Cette boucle parcourt tous les points récupérés plus haut et demande au node de closestPointOnMesh quelle est la position (sur la surface du mesh) la plus proche de ce point. La distance (entre le point d'origine et le point le plus proche sur la surface) est ensuite calculée (via la procédure "mag") et est stockée dans la liste des rayons. (Il fait ça en une ligne donc n'hésitez pas à relire le code! :dentcasse: )

[python]
newPoints,newRayons = [],[]

Il initialise deux listes (points et rayons) qui seront les listes des points et rayons restants (ceux qui vont vraiment servir).

Et maintenant, accrochez vous car on rentre dans le gros de l'algo! :gniarkgniark:

[python]
while len(points)>0:
	print "%s points encore a traiter..." % len(points)
	p,max,maxId = [],-1,-1

Début de la boucle. On initialise trois variables:

• "p" qui sera le point le plus "gros" (ayant le rayon le plus gros).
• "max", idem que pour point mais pour le rayon.
• "maxId", l'index de l'ensemble point-rayon qui est le plus gros (rappelez vous, les deux listes font la même taille).

[python]
	for i in range(len(points)):
		if rayons[i]>max:
			max,p,maxId=rayons[i],points[i],i

Cette boucle ne fait que rechercher (parmis tout les points) le point le plus gros et le stocke dans les variables initialisées plus haut.

A la fin de la boucle, max, p, et maxId appartiennent à la sphère (l'ensemble point-rayon toujours) la plus grosse. Celle qu'on va garder!

[python]
	del(points[maxId])
	del(rayons[maxId])
	newPoints.append(p)
	newRayons.append(max*1.2)

Ici on "déplace" en quelque sorte le point le plus gros vers la nouvelle liste ("newPoints" et "newRayons"):

• On le supprime de la liste principale.
• On l'ajoute à la nouvelle liste.

Djelloul choisit de multiplier la taille du rayon par 1.2 pour compenser le fait que les sphères semblent ne pas se toucher.

[python]
	i=0
	while i<len(points):
		if mag(p,points[i])<rayons[i]+max:
			del(points[i])
			del(rayons[i])
		else:
			i=i+1

Là, on arrive à la fin de l'algo: On parcourt tous les points restants, on fait, sur chacun d'eux, un test de collision avec la sphère la plus grosse (qu'on a récupéré juste au dessus).

Si il y a collision, on supprime le point. :grenadelauncher: (Et on "valide" la variable "action" pour que la boucle continue).

Notez qu'on n'incrémente pas "i" si on supprime les sphères des listes car tous les index se décalent de un à cet endroit. L'index actuel doit donc être revérifié.

[python]
#Attention ! Le mode de creation des nParticles par default doit etre "Points" !
part = nParticle(p=newPoints)[1]
setAttr(part+".particleRenderType",4)
setAttr(part+".ignoreSolverGravity",1)
addAttr(part,ln="radiusPP",dt="doubleArray")
setAttr(part+".radiusPP",newRayons,type="doubleArray")
print "Fini."

C'est la dernière partie du script:

• On recréé un système de particule en lui donnant les points qu'on a conservé de l'ancien système (les nouveaux points en quelque sorte).
• On met le display de particule en sphère, désactive la gravité.
• On ajoute un attribut de "rayon per particle".
• On donne à ce nouvel attribut les valeurs des rayons conservé de l'ancien système.

[python]
else:
	print("Il faut selectionner un mesh !")

Ce dernier point ferme la boucle ouverte tout au début. :sourit:

Et voilà! :bravo:

Rappelez vous que cette méthode n'est pas très optimisée. Soyez donc un peu patient. :siffle:

:longBar:

BEKRI Djelloul

Et parce que je pouvais pas finir ce tuto sans un dernier remercient à celui qui en est le principal créateur.

Un grand merci à Djelloul donc. N'hésitez pas à parcourir ces différentes pages pour avoir une idée de ses compétences. :sourit:

• Son site
• Son LinkedIn
• Son IMDB

J'espère que ce tuto était clair et que vous avez appris des choses aujourd'hui. N'hésitez pas à laisser un commentaire si je n'ai pas été assez précis ou que certains points vous semblent encore flou.