[2d] : Bezier + Point containment = bord arrondis

: Bezier + Point containment = bord arrondis [2d] - Algo - Programmation

Marsh Posté le 23-04-2003 à 10:47:05    

(bon j'espere pas trop avoir de reponse, mais bon...)
 
Voila, je suis tombe recemment sur le net sur un papier "Antialiasing of Curves by Discrete Pre-filtering", papier expliquant comment dessiner de chouettes courbes de bezier d'epaisseurs quelconque avec en prime un anti-alias*. L'algorithme pivot de ce papier est le point containment (autrement dit, on prends chaque point de l'ecran, on regarde si ce point appartient a la courbe, et si oui on l'allume. Je vous l'accorde, c'est assez bourrin, mais precis)
 
Ca marche super, effectivement on a de belle courbe d'epaisseur bien constante. Bref, je suis tres content mais il y a une grosse ombre au tableau : les bords de la courbe (au niveau des points initiaux/terminaux) ne sont pas droit mais arrondi, et pour le coup c'est plutot indesirable. Je me suis creuse le citron mais je n'ai pas reussi a trouver de methode permettant de contrecarrer cet effet. Alors je me suis dit que, peut etre, en posant la question sur hfr.... :ange:
 
thks
 
 
*niveau anti-alias, manque de bol l'explication exacte de comment bien faire se trouve dans deux documents et je n'ai pas reussi a mettre la main dessus. J'ai bidouille un truc, ca marchouille plus ou moins. Si jamais qqun sait ou j'ai des chances de les trouver ...
 

  • A.E. Fabris. Robust Anti-aliasing of Curves. Ph.D. Thesis,

University of East Anglia, U.K., November 1995.
 

  • A.E. Fabris and A.R. Forrest. Robust Anti-aliasing of Curves. December 1996, submitted for publication.


et le papier initial, si jamais ca interesse du monde (trouvable facilement via google):
 

  • A.E. Fabris and A.R. Forrest. Antialiasing of Curves by Discrete Pre-filtering


Message édité par chrisbk le 23-04-2003 à 10:49:04
Reply

Marsh Posté le 23-04-2003 à 10:47:05   

Reply

Marsh Posté le 23-04-2003 à 11:12:58    

bin la fait d'avoir les extrémitées arrondies est utile, et en même temps effecitvement ça peut être chiant si tu connectes plusieurs courbes de couleurs différentes....
 
mais en fait c pour quoi ? afficher des modèles CAO à la autocad ?

Reply

Marsh Posté le 23-04-2003 à 11:14:42    

sinon je sais pas du tout, ptet calculer le vecteur tangent à la courbe aux extrémitées et ignorer les points "derrière" ce vecteur (en gros quand le produit scalaire te donne un négatif)

Reply

Marsh Posté le 23-04-2003 à 11:16:25    

ben en fait c juste que parfois j'en veux et parfois j'en veux pas (enfin, l'utilisateur plutot)
 
 

BJOne a écrit :

sinon je sais pas du tout, ptet calculer le vecteur tangent à la courbe aux extrémitées et ignorer les points "derrière" ce vecteur (en gros quand le produit scalaire te donne un négatif)


 
J'avais penser a ca mais dans certains cas ca ne marche pas (genre une courbe de bezier qui fait une sorte de demi cercle, chaipas si tu vois :D)  
 
 
 
 

Reply

Marsh Posté le 23-04-2003 à 11:18:33    

beuh le casse-couilles....
 
et si tu testes la distance par rapport au point des extrémitées...
 
genre si "distance_début <= épaisseur && scalaire(vecteur_tangent_début, vecteur_debut_vers_point)<0" => on traçe po  [:spamafote]  ?
 
à priori ça devrait passer non ?


Message édité par bjone le 23-04-2003 à 11:19:15
Reply

Marsh Posté le 23-04-2003 à 11:21:12    

à la limite dans un soucis de vitesse tester uniquement la distance après que le scalaire sous trouvé nul....
 
mais ça chiera si la courbe reviens en tangentant une extrémitée :/

Reply

Marsh Posté le 23-04-2003 à 11:22:59    

BJOne a écrit :

beuh le casse-couilles....


merci bien :D
 
 
 

BJOne a écrit :


et si tu testes la distance par rapport au point des extrémitées...
 
genre si "distance_début <= épaisseur && scalaire(vecteur_tangent_début, vecteur_debut_vers_point)<0" => on traçe po  [:spamafote]  ?
 
à priori ça devrait passer non ?


 
poink, erreur mon cher ami, imaginez une courbe qui fait une sorte de noeud et repasse presque par dessus le point initial..... tel que decrit la ca risque de ne pas m'afficher des points pourtant necessaire...... crois bien que c mort cette histoire

Reply

Marsh Posté le 23-04-2003 à 11:31:52    

et vi je m'en suis aperçu après...

Reply

Marsh Posté le 23-04-2003 à 11:45:47    

sinon la technique serait d'encapsuler les points à tester, je m'explique:
 
quand tu testes tes points par rapport à la courbe, tu testes tous les points de l'écran, un peu comme avec du raytraçing tu testes chaque point qui donne un vecteur par rapport à tes polys...
 
MAIS comme du raytraçing, qui pour accélérer on utilise des bounding boxes et d'autres trucs, SI tu encapsulais ta courbe avec des rectangles OBB, du moins SURTOUT avec un bord perpendiculaire aux tangentes des extrémitées....
 
un peut comme en ogl/d3d, pour faire des arcs éléctriques tu as une ribembelle de polys dans lesquels tu as une texture d'éclair, et tu utilises de la transparence....
 
tu "entoures" ta courbe avec des rectangles qui suivent la courbe segmentée, avec le dernier et le premier rectangle orientés qui ont un bord perpendiculaire à la tangente au premier et dernier point de contrôle.
 
ça te permet de pas échantillonner les points "derrière" les extrémitées, de pas tester des points pour rien.
 
par contre pour que ça marche tout le temps, il faudait découper le "domaine" de la coube par rectangle afin que les points d'un rectangle du mileu de la courbe ailles pas tester les extrémitées réelles de la courbe (qui sont contenus dans un autre rectangle)...


Message édité par bjone le 23-04-2003 à 12:10:27
Reply

Marsh Posté le 23-04-2003 à 11:47:06    

attends je fais un petit paint...

Reply

Marsh Posté le 23-04-2003 à 11:47:06   

Reply

Marsh Posté le 23-04-2003 à 12:00:55    

ça je dirais:
 
http://membres.lycos.fr/bjone/images/mouarf.gif
 
tu segmentes en rectangles, ou pour chaque point du rectangle tu testes avec la courbe, mais uniquement la portion incluse dans le rectangle.
 
à priori tu auras des extrémitées "nettes", et comme tu te confines au domaine de 't' du rectangle, des points testés pour des portions intermédiaires ne seront pas traçés à cause de la proximité d'une extrémité....
 
et symétriquement tu n'auras pas de trou dans une portion intérmédiaire à cause de la proximité d'une extrémitée..
 
donc à priori: c'est une solution qui pourrait résoudre ton problème d'extrémité, et en plus tu as un speed-up gratuit car tu réduits la quantitée de points à tester...


Message édité par bjone le 23-04-2003 à 12:07:02
Reply

Marsh Posté le 23-04-2003 à 12:15:24    

la seule chose à faire attention, c'est de bien tester tous les pixos à l'intersection de deux rectangles (dumoins quadrilatères ;)) pour pas avoir de pixel popping comme en 3d :/
 
en fait ton "point containment", c'est un calcul de distance à la courbe ?
que tu compares à l'épaisseur, ou sa moitié ?


Message édité par bjone le 23-04-2003 à 12:18:04
Reply

Marsh Posté le 23-04-2003 à 13:17:05    

(j'arrives, j'arrives ;)

Reply

Marsh Posté le 23-04-2003 à 13:28:31    

en fait, bon, je teste pas tous les points de l'ecran, juste ceux du convex hull de la courbe (+precisement la bounding box du convex hull). C un peu moins porc.
 
Effectivement ton idee a l'air de se tenir :) Le tout etant maintenant de subdiviser la courbe de facon intelligente (faire gaffe aux endroits a forte courbure par exemple). Faut encore que je reflechisse un peu a tout ca. Je me demande si le mieux ne serait pas une subdivision par changement de direction de la courbe ?
 
 
Pour le point containment, l'idee est vraiment tres con, en gros et dans un superbe pseudo code:
Soit P le point a tester, C la courbe, W la largeur de la courbe :
 

Code :
  1. bool pointContainment(Courbe C,Point P)
  2. {
  3. Point S
  4. S = premier point de C
  5. D = distance(P,S)
  6. si (D < W)
  7. return true;
  8. Courbe cGauche = subdiviseGauche(C);
  9. si ( pointContainment(cGauche,P) == true)
  10. return true;
  11. Courbe cDroite = subdiviseDroite(C);
  12. si ( pointContainment(cDroite,P) == true)
  13. return true;
  14. return false;
  15. }


 
Bref, plus ca va plus on affine
voila en gros l'idee. La subdivision de courbe se fait via de Casteljau mais ca on s'en cogne
 
Manque de bol je sais pas si je vais pouvoir tester ca dans l'immediat, y'a des bricoles qui viennent de me tomber dessus :O  
 
te tiens au courant :)

Reply

Marsh Posté le 23-04-2003 à 13:37:12    

ha bon ouki...

Reply

Marsh Posté le 23-04-2003 à 13:41:43    

sinon y'a ptet moyen de juste segmenter le début et la fin et de faire un gros rectangle pour le milieu... (ce sera ptet plus cheap de faire quelque récursions de plus, que de se faire chier à générer plein de section)
 

Reply

Marsh Posté le 23-04-2003 à 13:44:21    

BJOne a écrit :

sinon y'a ptet moyen de juste segmenter le début et la fin et de faire un gros rectangle pour le milieu... (ce sera ptet plus cheap de faire quelque récursions de plus, que de se faire chier à générer plein de section)
 
 


 
[:meganne]
a voir :D
 
au fait, j'avais pas fait gaffe au nom de ton image [:fifiz]
On sent l'artiste tres fier de lui [:ddr555]

Reply

Marsh Posté le 23-04-2003 à 14:09:12    

:lol:  :p

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed