Comment représenter/modifier des solides 3D

Question

Dans mon programme j'ai quelques cubes (simple, emplacement xyz, taille xyz). Je veux être capable de prendre un de ces cubes et de 'soustraire' un autre cube.

Donc, ma question, quelle est une bonne structure de données génériques pour représenter l'objet 3d résultant, et quel type d'algorithme est utilisé pour soustraire un solide 3d d'un autre?

Answer 1

Ceci est une question assez générale et dépend de ce que vous voulez savoir sur le solide et à quelle vitesse vous voulez le savoir. En supposant que vous ne voulez des tests d'adhésion, cela pourrait fonctionner (psuedocode):

class Solid { 
    Solid solids = [] // each Solid has a list of solids that 
         // have been subtracted from it.      

    abstract method containedInSelf(point) { 
     // this will obviously vary from one type of solid to another 
    } 

    method contains(point) { 
     if !containedInSelf(point) return False; 
     else { 
      for solid in solids { // loop over all contained solids 
       if solid.contains(point) return False; 
       // point is contained in a solid that has been subtracted from it 
      } 
      // Now we know that point is contained but not contained in anything 
      // that's been subtracted 
      return True; 
     } 
    } 

    method subtract(solid) { 
     solids.append(solid) 
    } 

} 

Cela a l'avantage de permettre soustractions composites. Par exemple, vous pouvez soustraire A du solide B, puis B du solide C et cela fonctionnera comme prévu. Par exemple avec trois sphères centrées à l'origine et radius(A) < radius(B) < radius(C), vous obtiendrez des points qui sont contenus dans A ou contenus dans C mais pas B.

Vous pouvez également, par exemple, soustraire deux dodécaèdres d'une sphère, puis les soustraire à un cube. Ce qui revient à soustraire la sphère d'un cube et à y ajouter deux dodécaèdres.

Answer 2

Je doute qu'il existe une façon standard de représenter des objets géométriques à ce niveau.

Je rappelle que Povray, un raytracer open source, qui a un joli langage textuel pour représenter des scènes 3D, et qui comprend un jeu complet d'opérations géométriques (union, intersection, etc.) "Constructive Solid Geometry"; c'est assez flexible mais je doute que ce soit ce que vous cherchez. Gardez à l'esprit, d'ailleurs, qu'un raytracer a d'autres concepts à traiter, en dehors de la géométrie pure: textures, lumières, etc