Suppression des lignes cachées: Dévoiler l'invisible : les secrets de la vision par ordinateur

Par Fouad Sabry

Qu'est-ce que la suppression des lignes cachées

Les objets solides sont généralement modélisés sous forme de polyèdres dans le domaine de l'infographie tridimensionnelle. Dans un polyèdre, une face est un polygone plan entouré de segments de ligne droite appelés arêtes. Lorsque l'on tente d'imiter des surfaces courbes, un maillage polygonal est généralement utilisé. Il est nécessaire que les programmes informatiques utilisés pour créer des dessins au trait d'objets opaques soient capables de déterminer si les bords ou les sections des bords sont masqués par l'objet lui-même ou par d'autres objets. Cela permet de découper les bords pendant le processus de rendu. La difficulté en question est appelée suppression des lignes cachées.

Comment vous en bénéficierez

(I) Informations et validations sur les sujets suivants :

Chapitre 1 : Suppression des lignes cachées

Chapitre 2 : Algorithme de Painter

Chapitre 3 : Géométrie computationnelle

Chapitre 4 : Lancement de rayons

Chapitre 5 : Détermination des surfaces cachées

Chapitre 6 : Localisation des points

Chapitre 7 : Arbre couvrant minimum euclidien

Chapitre 8 : Problème de galerie d'art

Chapitre 9 : Rendu à plage dynamique élevée

Chapitre 10 : Squelette droit

(II) Répondre aux principales questions du public sur la suppression des lignes cachées .

(III) Exemples concrets d'utilisation de la suppression des lignes cachées dans de nombreux domaines.

À qui s'adresse ce livre

Professionnels, étudiants de premier cycle et des cycles supérieurs, passionnés, amateurs et ceux qui souhaitent aller au-delà des connaissances ou des informations de base pour tout type de suppression de lignes cachées.

 

 

• Langue: Français
• Éditeur: Un Milliard De Personnes Informées [French]
• Date de sortie: 5 mai 2024

Aperçu du livre

Suppression des lignes cachées

Dévoiler l'invisible : les secrets de la vision par ordinateur

Fouad Sabry est l'ancien responsable régional du développement commercial pour les applications chez Hewlett Packard pour l'Europe du Sud, le Moyen-Orient et l'Afrique. Fouad est titulaire d'un baccalauréat ès sciences des systèmes informatiques et du contrôle automatique, d'une double maîtrise, d'une maîtrise en administration des affaires et d'une maîtrise en gestion des technologies de l'information, de l'Université de Melbourne en Australie. Fouad a plus de 25 ans d'expérience dans les technologies de l'information et de la communication, travaillant dans des entreprises locales, régionales et internationales, telles que Vodafone et des machines professionnelles internationales. Actuellement, Fouad est un entrepreneur, auteur, futuriste, axé sur les technologies émergentes et les solutions industrielles, et fondateur de l'initiative One Billion Knowledge.

Un milliard de connaissances

Suppression des lignes cachées

Dévoiler l'invisible : les secrets de la vision par ordinateur

Fouad Sabry

Copyright

Suppression de © la ligne cachée 2024 par Fouad Sabry. Tous droits réservés.

Aucune partie de ce livre ne peut être reproduite sous quelque forme que ce soit ou par quelque moyen électronique ou mécanique que ce soit, y compris les systèmes de stockage et de récupération d'informations, sans l'autorisation écrite de l'auteur. La seule exception est celle d'un critique, qui peut citer de courts extraits dans une critique.

Couverture dessinée par Fouad Sabry.

Bien que toutes les précautions aient été prises dans la préparation de ce livre, les auteurs et les éditeurs n'assument aucune responsabilité pour les erreurs ou omissions, ou pour les dommages résultant de l'utilisation des informations contenues dans le présent document.

Table des matières

Chapitre 1 : Suppression des lignes cachées

Chapitre 2 : Algorithme de Painter

Chapitre 3 : Géométrie computationnelle

Chapitre 4 : Lancer de rayons

Chapitre 5 : Détermination de la surface cachée

Chapitre 6 : Localisation du point

Chapitre 7 : Arbre couvrant minimum euclidien

Chapitre 8 : Le problème des galeries d'art

Chapitre 9 : Liste des sujets de géométrie computationnelle combinatoire

Chapitre 10 : Squelette droit

Appendice

À propos de l'auteur

Chapitre 1 : Suppression des lignes cachées

En infographie 3D, les polyèdres sont généralement utilisés pour modéliser des choses solides. Une face d'un polyèdre est un polygone planaire délimité par des arêtes, qui sont des segments de ligne droite. En règle générale, un maillage surfacique est utilisé pour représenter des surfaces courbes. Pour découper les arêtes pendant le rendu, les programmes informatiques pour les dessins au trait d'objets opaques doivent être en mesure de déterminer quelles arêtes ou parties d'arêtes sont masquées par un élément ou par d'autres objets. C'est ce que l'on appelle la suppression des lignes cachées.

Roberts a développé la première solution connue au problème de la ligne cachée. Ivan E. Sutherland a mis en évidence dix problèmes non résolus en infographie en 1966.

Dans la conception assistée par ordinateur, par exemple, les modèles peuvent avoir des milliers ou des millions d'arêtes. Par conséquent, il est essentiel d'utiliser une méthode de complexité computationnelle qui exprime les besoins en ressources (tels que le temps et la mémoire) en fonction de la taille des problèmes. Les contraintes de temps pour les systèmes interactifs sont particulièrement cruciales.

Les tailles de problème pour la suppression de ligne cachée sont le nombre n des arêtes du modèle et le nombre v des segments visibles des arêtes.

Aux endroits où se croisent les images des bords, la visibilité peut changer.

Soit k le nombre total de sites où les images des tronçons se croisent.

k = Θ(n2) et v = Θ(n2) dans le pire des cas, mais généralement v k.

Avant 1984, les algorithmes de lignes cachées publiés par Ottmann et Widmayer et Wood proposaient des algorithmes de lignes cachées O((n + k) log2 n)-temps.

Ensuite, Nurmi a amélioré le temps d'exécution à O((n + k) log n).

Ces algorithmes prennent Θ(n2 log2 n), respectivement Θ(n2 log n) temps dans le pire des cas, si k est inférieur à quadratique néanmoins, peut être plus rapide en réalité.

Tout algorithme de ligne cachée doit déterminer l'union de Θ(n) intervalles cachés sur n arêtes dans le pire des cas.

Comme Ω(n log n) est une borne inférieure pour déterminer l'union de n intervalles, il apparaît que le mieux que l'on puisse espérer atteindre est Θ(n2 log n) temps du pire des cas, Par conséquent, l'algorithme de Nurmi est le meilleur.

Cependant, le facteur log n a été éliminé par Devai, que les méthodes de Devai et McKenna « sont des jalons dans les algorithmes de visibilité », brisant une barrière théorique de O(n2 log n) à O(n2) pour le traitement d'une scène de n arêtes.

L'autre question en suspens, présentée par Devai, de savoir s'il existe un  algorithme de ligne cachée O(n log n + v)-temps, où v, comme déjà dit, est le nombre de segments visibles, restait sans réponse au moment de la rédaction de cet article.

En 1988, Devai a proposé un algorithme parallèle O(log n)-temps utilisant n2 processeurs pour le problème de la ligne cachée sous la lecture simultanée, Modèle de calcul utilisant une machine à accès aléatoire parallèle (PRAM) en écriture exclusive (CREW).

Comme le produit du nombre de processeurs et du temps d'exécution est asymptotiquement supérieur à Θ(n2), la complication séquentielle du problème, L'algorithme est inefficace, Cependant, il prouve que le problème de la ligne cachée appartient à la classe de difficulté NC, c'est-à-dire qu'il peut être résolu à l'aide d'un nombre polynomial de processeurs en temps polylogarithmique.

Cependant, les algorithmes de surface cachée peuvent être utilisés pour éliminer les lignes cachées, et non l'inverse.

Reif