Vertex connexion [optimisation]

Ici on parle des scripts

Modérateurs : frez, Yadoob, stilobique, Matpi, ModSquad

Vertex connexion [optimisation]

Message par GameL » 08 Déc 2015, 16:31

Salut tout le monde.

Je viens d'écrire un script qui permet de connecter les vertex entre eux par une edges selon un rayon de détection.
Pour un petit mesh de 2000 vertex, cela fonctionne plutôt bien. Quand je passe à 30000... bin ça calcul encore ^^

Auriez- vous une idée d'optimisation?
merci d'avance

Code : Tout sélectionner
import bpy

connectionDistance = 0.5;
obj = bpy.context.object
vertices = obj.data.vertices
nbVertex = len(vertices)

edges = []
for i in range(0,nbVertex):
    verta = vertices[i].co
    for j in range(0,nbVertex):
        vertb = vertices[j].co
        distance = (verta - vertb).length
        if distance <= connectionDistance:
            edge = [i, j]
            edges.append(edge)


obj.data.edges.add(count=len(edges))
for i_edge, edge in enumerate(edges):
    obj.data.edges[i_edge].vertices = edge
           
obj.update_from_editmode()
Avatar de l’utilisateur
GameL
 
Message(s) : 80
Inscription : 06 Sep 2014, 05:12

Re: Vertex connexion [optimisation]

Message par Matpi » 08 Déc 2015, 18:25

Salut,

Tu peux utiliser un KDTree, ce sera probablement plus rapide.

Et comme il y en a une implémentation dans la bibliothèque de Blender (du coup écrite en C, autre avantage), ça sera simple d'essayer. ;)

http://www.blender.org/api/blender_python_api_2_76_release/mathutils.kdtree.html

Je fais un essai à l'instant.
BAddons - La Collection d'Addons de Matpi: https://github.com/qwenger/BAddons
Avatar de l’utilisateur
Matpi
 
Message(s) : 288
Inscription : 07 Déc 2014, 10:51
Localisation : in dr Schwiiz

Re: Vertex connexion [optimisation]

Message par lapineige » 08 Déc 2015, 18:30

Ne pas passer par Python ? :mrgreen:
(plus surcouche, etc)

Déjà regarde ce qui prends le plus de temps, l'itération dans la boucle ou la création des arêtes (à mon avis c'est ça).
Le module timeit est très pratique pour ça.
Si ça bloque niveau python et non au niveau du code C++, on peut envisager de le compiler en C.

Le calcul distance stocké, puis utilisé une seule fois, est utile en terme de lisibilité, mais pas en terme de mémoire et de perfs, mets le directement dans la condition. Tu peux aussi remplacer connectionDistance par ta valeur, sa évite un appel mémoire.
Code : Tout sélectionner
if (verta - vertb).length <= 0.5:

(à voir si un calcul "à la main" de la longueur n'est pas plus rapide, normalement oui)
Idem pour le:
Code : Tout sélectionner
edge = [i, j]
edges.append(edge)

autant faire directement:
Code : Tout sélectionner
edges.append((i, j))

(Un tuple prends moins de place en mémoire et est plus rapide à traiter si je me souviens bien)

Faire deux boucles ne me parait pas très rentable, encore plus avec la troisième pour créer une arête déjà stockée en mémoire pendant les deux premières boucles. Y'aurait moyen de faire mieux avec Numpy, avec du PyCuda (c'est hyper parallélisable comme calcul), etc.
Un KDTree peut aussi servir (edit: grillé ^^)

Y'a aussi le problème du test du vertex avec lui-même (qui fait doublon dans ton cas), le problème c'est que mettre une condition économise peut de calcul (1/le nombre de vertices), et qu'une condition ça coûte cher en calcul.

A voir si la création de l'edge ne serait pas plus rapide une fois inséré dans les deux premières boucles.
Quitte à ajouter des edges en trop, et à les supprimer à la fin. À tester.
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par lapineige » 08 Déc 2015, 18:49

(double post, tant pis ça aère :))
On peut alléger ça
Code : Tout sélectionner
for i in range(0,nbVertex):
    verta = vertices[i].co

par:
Code : Tout sélectionner
for verta in vertices:
# ta deuxième boucle, ou tu utilise verta.co

Ça fait une entrée en mémoire de moins à chaque tour de boucle.

(d'ailleurs nbVertex peut être simplement remplacé par len(vertices), et même len(bpy.context.object.data.vertices), mais bon le gain est à peut près nul)

Une idée comme ça, à tester: si tu créé une liste des vertices directement avec list(vertices), et qu'ensuite tu fais une boucle qui prends chaque vertices et qui calcule la distance avec les suivants, créé une arête, et stocke le résultat du calcul et les paires de vertices utilisés. Comme de toute façon tu va faire doublon ensuite... AU début c'est une perte de temps, très vite c'est un gain. Le calcul vertice1-vertice2 est fait pour vertice1 puis pour vertice2, une grosse perte de temps.
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par Matpi » 08 Déc 2015, 18:50

Bon je passe la tartine à Lapi (je la lirai après, espérons que je répète pas ce qu'il y explique...).

Voici un petit essai, déjà pas mal optimisé (itérateurs, zip, éviter les variables locales, ne choisir que les edges utiles, etc.)

Code : Tout sélectionner
import bpy
from mathutils.kdtree import KDTree

connection_distance = 0.5

obj = bpy.context.object
vertices = obj.data.vertices
nb_vertex = len(vertices)

kd = KDTree(nb_vertex)

for i, v in enumerate(vertices):
    kd.insert(v.co, i)

kd.balance()

edges = []

for i, v in enumerate(vertices):
    candidates = kd.find_range(v.co, connection_distance)

    for candidate in candidates:
        # candidate is (co, index, distance)
        j = candidate[1]
        # avoid creating edges twice or edges
        # between identical vertices;
        # so pick up a rule
        if j > i:
            edges.append((i, j))


obj.data.edges.add(count=len(edges))

# XXX: this works only if there is no edge
# in the mesh before the script runs!
for edge, vpair in zip(obj.data.edges, edges):
    edge.vertices = vpair

#obj.update_from_editmode()
obj.data.update()


Bon même s'il est bien plus rapide que la première implémentation "naïve" (le prends pas mal, c'est comme ça qu'on dit), il en est pas pour autant "rapide" sur des gros nombres de vertices. A benchmarker.

Je suis encore pas très convaincu par la dernière boucle, mais je crois pas qu'il y ait d'autre moyen. En tous cas tel quel ça ne fonctionne que si le mesh au départ ne contient aucun edge, voir le commentaire.

Ah et à part ça, il faut faire un aller-retour en Edit Mode pour voir les changements, malgré le update_from_editmode(). J'sais pas pourquoi.


EDIT:

les prefs dépendent non seulement du nombre de vertices de l'objet, mais également beaucoup de leur proximité. Quelle est la densité de ton mesh? Genre en moyenne combien d'arêtes seront effectivement créées autour d'un vertex avec la distance limite que tu as mise?

EDIT 2:

@Lapi: nested loops -> O(n^2), simple loop -> O(n). Donc la recherche des vertices sera probablement bien plus lente que la création des edges (même s'il faut que Blender travaille en dessous dans ce dernier cas, mais l'utilisation de edges.add(count) puis d'un itérateur réduit considérablement ce genre de problèmes).

Après ça dépend aussi de ce que je discute dans l'EDIT 1.

Et puis finalement c'est bien clair qu'en C/C++ ce serait plus rapide (quoique en utilisant le KDTree de Blender c'est moins un problème, surtout qu'autrement il faudrait encore réimporter les résultats, ce qui reprend du temps - donc peut-être le calcul en lui même un petit peu, mais au final on doit pas être loin d'un bon compromis).
BAddons - La Collection d'Addons de Matpi: https://github.com/qwenger/BAddons
Avatar de l’utilisateur
Matpi
 
Message(s) : 288
Inscription : 07 Déc 2014, 10:51
Localisation : in dr Schwiiz

Re: Vertex connexion [optimisation]

Message par lapineige » 08 Déc 2015, 19:03

Matpi a écrit :Ah et à part ça, il faut faire un aller-retour en Edit Mode pour voir les changements, malgré le update_from_editmode(). J'sais pas pourquoi.

Faut pas passer par bmesh ?

Matpi a écrit :@Lapi: nested loops -> O(n^2), simple loop -> O(n). Donc la recherche des vertices sera probablement bien plus lente que la création des edges (même s'il faut que Blender travaille en dessous dans ce dernier cas, mais l'utilisation de edges.add(count) puis d'un itérateur réduit considérablement ce genre de problèmes).

Bien vu, je n'y avait pas pensé.
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par Matpi » 08 Déc 2015, 19:14

Heu... BMesh c'est une autre manière de faire (je sais pas ce qui est le mieux question rapidité, d'ailleurs, mais à première vue la méthode précédente permet une algorithmique pas mauvaise), il doit bien y avoir une possibilité de rafraîchir l'objet sans passer par BMesh, non? J'aurais attendu de update_from_editmode qu'elle fasse cela, mais apparemment non...

A part ça j'aurait Mesh.from_pydata pour créer de la géométrie, je sais pas ce que ça vaut question rapidité.
BAddons - La Collection d'Addons de Matpi: https://github.com/qwenger/BAddons
Avatar de l’utilisateur
Matpi
 
Message(s) : 288
Inscription : 07 Déc 2014, 10:51
Localisation : in dr Schwiiz

Re: Vertex connexion [optimisation]

Message par lapineige » 08 Déc 2015, 19:31

Matpi a écrit :A part ça j'aurait Mesh.from_pydata pour créer de la géométrie, je sais pas ce que ça vaut question rapidité.

À défaut de savoir comment ça marche derrière, à tester en effet.

Matpi a écrit :J'aurais attendu de update_from_editmode qu'elle fasse cela, mais apparemment non...

Je les confonds toutes, c'est pas plutôt pour récupérer un mesh édité par l'utilisateur, depuis le mode édition ?
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par Matpi » 08 Déc 2015, 19:38

Ah oui, effectivement, et j'ai trouvé: obj.data.update.

Je modifie mon code en conséquence.
BAddons - La Collection d'Addons de Matpi: https://github.com/qwenger/BAddons
Avatar de l’utilisateur
Matpi
 
Message(s) : 288
Inscription : 07 Déc 2014, 10:51
Localisation : in dr Schwiiz

Re: Vertex connexion [optimisation]

Message par GameL » 09 Déc 2015, 09:28

yeah merci pour vos réponses si détaillées. Je suis en train de faire plusieurs test avec vos diverses propositions.

En ce qui concerne mon mesh. Il sera variable, mais ce sera dans tous les cas un nuage de point d'une photogrammétrie. Pour mon test j'ai 35 000 vertex. Mais il se peut que si ça fonctionne bien. on dépasse les 400 000 vertex.

Une seconde chose. Il semble que Blender met beaucoup de temps à convertir en curve ce mesh. y a pas une possibilité d'éditer ce code pour qu'il travail directement sur une curve et non un mesh?

encore merci.

Je vous tiens au jus
Avatar de l’utilisateur
GameL
 
Message(s) : 80
Inscription : 06 Sep 2014, 05:12

Re: Vertex connexion [optimisation]

Message par GameL » 09 Déc 2015, 09:32

Bon y a pas photo avec le code de Matpi et le KDtree je passe de 2 min de calculs à 10 s pour un rayon de détection à 0.3 et un nombre de vertex à 35 000.

Par contre toujours un long problème de conversion en curve.

J'ai besoin d'une curves pour lui donner une épaisseur et la rendre visible au rendu.


Je continu mes recherches
Avatar de l’utilisateur
GameL
 
Message(s) : 80
Inscription : 06 Sep 2014, 05:12

Re: Vertex connexion [optimisation]

Message par lapineige » 09 Déc 2015, 14:50

Bof un fois 12.5 pour une méthode optimisée, en C++, face au code en API Python + C++ mal optimisé... C'est pas énorme ^^

Faire ça avec des courbes... pas un problème simple.

Pour l'épaisseur, un solidify ne suffirait pas ?

Et pour relier tout ça, puisque que ça vient d'une opération de phototgramétrie, un remesh pourrait être utile, non ? Tu retrouverai la surface de base, certainement à retoucher mais bon... Après le temps de calcul peut être bien long.
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par Matpi » 09 Déc 2015, 15:27

(comment tu arrives à 12.5, lapi??? 2mn = 12*10s)

Comme la complexité algorithmique est différente, plus grand sera le nombre de vertices, plus grand le facteur d'écart. Tendant vers l'infini...

Dans le BI tu peux rendre directement des meshes sans faces. Mais je sais pas si ça te convient...
BAddons - La Collection d'Addons de Matpi: https://github.com/qwenger/BAddons
Avatar de l’utilisateur
Matpi
 
Message(s) : 288
Inscription : 07 Déc 2014, 10:51
Localisation : in dr Schwiiz

Re: Vertex connexion [optimisation]

Message par lapineige » 09 Déc 2015, 15:30

Matpi a écrit :(comment tu arrives à 12.5, lapi??? 2mn = 12*10s)

C'est la question, je ne sais pas d’où il sors ^^
Même pas écrit depuis un portable pourtant.

Matpi a écrit :Comme la complexité algorithmique est différente, plus grand sera le nombre de vertices, plus grand le facteur d'écart. Tendant vers l'infini...

Ouaip, mais je trouvais que pour un nombre quand même important de vertices, c'est pas bien rapide.
Mon terrier/blog: https://lapineige.fr/wp (l'ancien: le-terrier-de-lapineige.over-blog.com) | Mon GitHub: https://github.com/lapineige/Blender_add-ons | Lapineige's Tools: http://cgcookiemarkets.com/blender/all- ... ompilation
Avatar de l’utilisateur
lapineige
 
Message(s) : 3716
Inscription : 25 Juin 2014, 07:06

Re: Vertex connexion [optimisation]

Message par GameL » 09 Déc 2015, 15:42

un tricks génial!

En gros le script ne va connecté uniquement que les 10 premiers vertex détecté et puis stop il passe au suivant (je vais voir pour un random dans l'éventualité d'une animation)

Code : Tout sélectionner
import bpy
from mathutils.kdtree import KDTree

connection_distance = 0.5
max_points = 10

obj = bpy.context.object
vertices = obj.data.vertices
nb_vertex = len(vertices)

kd = KDTree(nb_vertex)

for i, v in enumerate(vertices):
    kd.insert(v.co, i)

kd.balance()

edges = []

for i, v in enumerate(vertices):
    candidates = kd.find_range(v.co, connection_distance)

    for candidate in candidates[:max_points]:
        # candidate is (co, index, distance)
        j = candidate[1]
        # avoid creating edges twice or edges
        # between identical vertices;
        # so pick up a rule
        if j > i:
            edges.append((i, j))


obj.data.edges.add(count=len(edges))

# XXX: this works only if there is no edge
# in the mesh before the script runs!
for edge, vpair in zip(obj.data.edges, edges):
    edge.vertices = vpair

#obj.update_from_editmode()
obj.data.update()
Avatar de l’utilisateur
GameL
 
Message(s) : 80
Inscription : 06 Sep 2014, 05:12

Suivant

Retour vers Scripts - Python - OSL

Qui est en ligne ?

Utilisateur(s) parcourant ce forum : Aucun utilisateur inscrit et 1 invité