New files from new booleans
[blender.git] / intern / boolop / intern / BOP_BSPTree.cpp
1 /**
2  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version. The Blender
8  * Foundation also sells licenses for use in proprietary software under
9  * the Blender License.  See http://www.blender.org/BL/ for information
10  * about this.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software Foundation,
19  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
20  *
21  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
22  * All rights reserved.
23  *
24  * The Original Code is: all of this file.
25  *
26  * Contributor(s): none yet.
27  *
28  * ***** END GPL/BL DUAL LICENSE BLOCK *****
29  */
30  
31 #include "BOP_BSPTree.h"
32 #include <vector>
33 #include <iostream>
34 using namespace std;
35
36 /**
37  * Constructs a new BSP tree.
38  */
39 BOP_BSPTree::BOP_BSPTree()
40 {
41         m_root = NULL;
42         m_bspBB = NULL;
43 }
44
45 /**
46  * Destroys a BSP tree.
47  */
48 BOP_BSPTree::~BOP_BSPTree()
49 {
50         if (m_root!=NULL) delete m_root;
51         if (m_bspBB!=NULL) delete m_bspBB;
52 }
53
54 /**
55  * Adds all mesh faces to BSP tree.
56  * @param mesh mesh to add.
57  * @param facesList face list to add.
58  */
59 void BOP_BSPTree::addMesh(BOP_Mesh* mesh, BOP_Faces& facesList)
60 {
61         for (BOP_IT_Faces it = facesList.begin(); it != facesList.end(); ++it) {
62                 addFace( mesh, *it );
63         }
64         
65 }
66
67 /**
68  * Adds a new face into bsp tree.
69  * @param mesh Input data for BSP tree.
70  * @param face index to mesh face.
71  */
72 void BOP_BSPTree::addFace(BOP_Mesh* mesh, BOP_Face* face)
73 {
74         addFace(mesh->getVertex(face->getVertex(0))->getPoint(),
75                         mesh->getVertex(face->getVertex(1))->getPoint(),
76                         mesh->getVertex(face->getVertex(2))->getPoint(),
77                         face->getPlane());
78 }
79
80 /**
81  * Adds new facee to the bsp-tree.
82  * @param p1 first face point.
83  * @param p2 second face point.
84  * @param p3 third face point.
85  * @param plane face plane.
86  */
87 void BOP_BSPTree::addFace(const MT_Point3& p1, 
88                                                   const MT_Point3& p2, 
89                                                   const MT_Point3& p3, 
90                                                   const MT_Plane3& plane)
91 {
92         if (m_root == NULL)
93                 m_root = new BOP_BSPNode(plane);
94         else
95                 m_root->addFace(p1,p2,p3,plane);
96
97         // update bounding box
98         m_bbox.add(p1);
99         m_bbox.add(p2);
100         m_bbox.add(p3);
101 }
102
103 /**
104  * Tests face vs bsp-tree (returns where is the face respect bsp planes).
105  * @param p1 first face triangle point.
106  * @param p2 secons face triangle point.
107  * @param p3 third face triangle point.
108  * @param plane face plane.
109  * @return BSP_IN, BSP_OUT or BSP_IN_OUT
110  */
111 BOP_TAG BOP_BSPTree::classifyFace(const MT_Point3& p1, 
112                                                                   const MT_Point3& p2, 
113                                                                   const MT_Point3& p3, 
114                                                                   const MT_Plane3& plane) const
115 {
116         if ( m_root != NULL )
117           return m_root->classifyFace(p1, p2, p3, plane);
118         else
119           return OUT;
120 }
121
122 /**
123  * Filters a face using the BSP bounding infomation.
124  * @param p1 first face triangle point.
125  * @param p2 secons face triangle point.
126  * @param p3 third face triangle point.
127  * @param face face to test.
128  * @return UNCLASSIFIED, BSP_IN, BSP_OUT or BSP_IN_OUT
129  */
130 BOP_TAG BOP_BSPTree::filterFace(const MT_Point3& p1, 
131                                                                 const MT_Point3& p2, 
132                                                                 const MT_Point3& p3, 
133                                                                 BOP_Face* face)
134 {
135         if ( m_bspBB != NULL ) {
136                 return m_bspBB->classifyFace(p1,p2,p3,face->getPlane());
137         }
138         else
139                 return UNCLASSIFIED;
140 }
141
142 /**
143  * Tests face vs bsp-tree (returns where is the face respect bsp planes).
144  * @param p1 first face triangle point.
145  * @param p2 secons face triangle point.
146  * @param p3 third face triangle point.
147  * @param plane face plane.
148  * @return BSP_IN, BSP_OUT or BSP_IN_OUT
149  */
150 BOP_TAG BOP_BSPTree::simplifiedClassifyFace(const MT_Point3& p1, 
151                                                                                         const MT_Point3& p2, 
152                                                                                         const MT_Point3& p3, 
153                                                                                         const MT_Plane3& plane) const
154 {
155         if ( m_root != NULL )
156           return m_root->simplifiedClassifyFace(p1, p2, p3, plane);
157         else
158           return OUT;
159 }
160
161 /**
162  * Returns the deep of this BSP tree.
163  * @return tree deep
164  */
165 unsigned int BOP_BSPTree::getDeep() const
166 {
167         if ( m_root != NULL )
168           return m_root->getDeep();
169         else
170           return 0;
171 }
172
173 /**
174  * Computes the bounding BSP data.
175  */
176 void BOP_BSPTree::computeBox()
177 {
178         if ( m_root != NULL ) {
179                 MT_Point3 p1(m_bbox.m_minX,m_bbox.m_minY,m_bbox.m_minZ);
180                 MT_Point3 p2(m_bbox.m_maxX,m_bbox.m_minY,m_bbox.m_minZ);
181                 MT_Point3 p3(m_bbox.m_maxX,m_bbox.m_maxY,m_bbox.m_minZ);
182                 MT_Point3 p4(m_bbox.m_minX,m_bbox.m_maxY,m_bbox.m_minZ);
183                 MT_Point3 p5(m_bbox.m_minX,m_bbox.m_minY,m_bbox.m_maxZ);
184                 MT_Point3 p6(m_bbox.m_maxX,m_bbox.m_minY,m_bbox.m_maxZ);
185                 MT_Point3 p7(m_bbox.m_maxX,m_bbox.m_maxY,m_bbox.m_maxZ);
186                 MT_Point3 p8(m_bbox.m_minX,m_bbox.m_maxY,m_bbox.m_maxZ);        
187                 
188                 MT_Plane3 plane1(p3,p2,p1);
189                 MT_Plane3 plane2(p5,p6,p7);
190                 MT_Plane3 plane3(p1,p2,p6);
191                 MT_Plane3 plane4(p8,p7,p3);
192                 MT_Plane3 plane5(p2,p3,p7);
193                 MT_Plane3 plane6(p1,p5,p8);
194                 
195                 BOP_BSPNode bsp(plane1);
196                 bsp.addFace(p5,p6,p7,plane2);
197                 bsp.addFace(p1,p2,p6,plane3);
198                 bsp.addFace(p8,p7,p3,plane4);
199                 bsp.addFace(p2,p3,p7,plane5);
200                 bsp.addFace(p1,p5,p8,plane6);
201         }
202 }
203
204 /**
205  * Prints debug information.
206  */
207 void BOP_BSPTree::print()
208 {
209         if ( m_root != NULL )
210                 m_root->print( 0 );
211 }
212