49b7489530248ab94c0a2701cac99c60a504988a
[blender.git] / source / gameengine / Rasterizer / RAS_MeshObject.cpp
1 /*
2  * ***** BEGIN GPL 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.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file gameengine/Rasterizer/RAS_MeshObject.cpp
29  *  \ingroup bgerast
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "DNA_object_types.h"
35 #include "DNA_key_types.h"
36 #include "DNA_mesh_types.h"
37 #include "DNA_meshdata_types.h"
38
39 #include "RAS_MeshObject.h"
40 #include "RAS_IRasterizer.h"
41 #include "MT_MinMax.h"
42 #include "MT_Point3.h"
43
44 #include <algorithm>
45
46 extern "C" {
47 #       include "BKE_deform.h"
48 }
49
50 /* polygon sorting */
51
52 struct RAS_MeshObject::polygonSlot
53 {
54         float m_z;
55         int m_index[4];
56         
57         polygonSlot() {}
58
59         /* pnorm is the normal from the plane equation that the distance from is
60          * used to sort again. */
61         void get(const RAS_TexVert *vertexarray, const unsigned short *indexarray,
62                 int offset, int nvert, const MT_Vector3& pnorm)
63         {
64                 MT_Vector3 center(0, 0, 0);
65                 int i;
66
67                 for (i=0; i<nvert; i++) {
68                         m_index[i] = indexarray[offset+i];
69                         center += vertexarray[m_index[i]].getXYZ();
70                 }
71
72                 /* note we don't divide center by the number of vertices, since all
73                  * polygons have the same number of vertices, and that we leave out
74                  * the 4-th component of the plane equation since it is constant. */
75                 m_z = MT_dot(pnorm, center);
76         }
77
78         void set(unsigned short *indexarray, int offset, int nvert)
79         {
80                 int i;
81
82                 for (i=0; i<nvert; i++)
83                         indexarray[offset+i] = m_index[i];
84         }
85 };
86         
87 struct RAS_MeshObject::backtofront
88 {
89         bool operator()(const polygonSlot &a, const polygonSlot &b) const
90         {
91                 return a.m_z < b.m_z;
92         }
93 };
94
95 struct RAS_MeshObject::fronttoback
96 {
97         bool operator()(const polygonSlot &a, const polygonSlot &b) const
98         {
99                 return a.m_z > b.m_z;
100         }
101 };
102
103 /* mesh object */
104
105 STR_String RAS_MeshObject::s_emptyname = "";
106
107 RAS_MeshObject::RAS_MeshObject(Mesh* mesh)
108         : m_bModified(true),
109         m_bMeshModified(true),
110         m_mesh(mesh)
111 {
112         if (m_mesh && m_mesh->key)
113         {
114                 KeyBlock *kb;
115                 int count=0;
116                 // initialize weight cache for shape objects
117                 // count how many keys in this mesh
118                 for (kb= (KeyBlock*)m_mesh->key->block.first; kb; kb= (KeyBlock*)kb->next)
119                         count++;
120                 m_cacheWeightIndex.resize(count,-1);
121         }
122 }
123
124 RAS_MeshObject::~RAS_MeshObject()
125 {
126         vector<RAS_Polygon*>::iterator it;
127
128         if (m_mesh && m_mesh->key) 
129         {
130                 KeyBlock *kb;
131                 // remove the weight cache to avoid memory leak 
132                 for (kb= (KeyBlock*)m_mesh->key->block.first; kb; kb= (KeyBlock*)kb->next) {
133                         if (kb->weights) 
134                                 MEM_freeN(kb->weights);
135                         kb->weights= NULL;
136                 }
137         }
138
139         for (it=m_Polygons.begin(); it!=m_Polygons.end(); it++)
140                 delete (*it);
141
142         m_sharedvertex_map.clear();
143         m_Polygons.clear();
144         m_materials.clear();
145 }
146
147 bool RAS_MeshObject::MeshModified()
148 {
149         return m_bMeshModified;
150 }
151
152 //unsigned int RAS_MeshObject::GetLightLayer()
153 //{
154 //      return m_lightlayer;
155 //}
156
157
158
159 int RAS_MeshObject::NumMaterials()
160 {
161         return m_materials.size();
162 }
163
164 const STR_String& RAS_MeshObject::GetMaterialName(unsigned int matid)
165
166         RAS_MeshMaterial* mmat = GetMeshMaterial(matid);
167
168         if (mmat)
169                 return mmat->m_bucket->GetPolyMaterial()->GetMaterialName();
170         
171         return s_emptyname;
172 }
173
174 RAS_MeshMaterial* RAS_MeshObject::GetMeshMaterial(unsigned int matid)
175 {
176         if ((m_materials.empty() == false) && (matid < m_materials.size()))
177         {
178                 list<RAS_MeshMaterial>::iterator it = m_materials.begin();
179                 while (matid--) ++it;
180                 return &*it;
181         }
182
183         return NULL;
184 }
185
186
187
188 int RAS_MeshObject::NumPolygons()
189 {
190         return m_Polygons.size();
191 }
192
193
194
195 RAS_Polygon* RAS_MeshObject::GetPolygon(int num) const
196 {
197         return m_Polygons[num];
198 }
199
200         
201         
202
203         list<RAS_MeshMaterial>::iterator GetFirstMaterial();
204         list<RAS_MeshMaterial>::iterator GetLastMaterial();
205 list<RAS_MeshMaterial>::iterator RAS_MeshObject::GetFirstMaterial()
206 {
207         return m_materials.begin();
208 }
209
210
211
212 list<RAS_MeshMaterial>::iterator RAS_MeshObject::GetLastMaterial()
213 {
214         return m_materials.end();
215 }
216
217
218
219 void RAS_MeshObject::SetName(const char *name)
220 {
221         m_name = name;
222 }
223
224
225
226 STR_String& RAS_MeshObject::GetName()
227 {
228         return m_name;
229 }
230
231
232
233 const STR_String& RAS_MeshObject::GetTextureName(unsigned int matid)
234
235         RAS_MeshMaterial* mmat = GetMeshMaterial(matid);
236         
237         if (mmat)
238                 return mmat->m_bucket->GetPolyMaterial()->GetTextureName();
239
240         return s_emptyname;
241 }
242
243 RAS_MeshMaterial *RAS_MeshObject::GetMeshMaterial(RAS_IPolyMaterial *mat)
244 {
245         list<RAS_MeshMaterial>::iterator mit;
246
247         /* find a mesh material */
248         for (mit = m_materials.begin(); mit != m_materials.end(); mit++)
249                 if (mit->m_bucket->GetPolyMaterial() == mat)
250                         return &*mit;
251
252         return NULL;
253 }
254
255 int RAS_MeshObject::GetMaterialId(RAS_IPolyMaterial *mat)
256 {
257         list<RAS_MeshMaterial>::iterator mit;
258         int imat;
259
260         /* find a mesh material */
261         for (imat=0, mit = m_materials.begin(); mit != m_materials.end(); mit++, imat++)
262                 if (mit->m_bucket->GetPolyMaterial() == mat)
263                         return imat;
264
265         return -1;
266 }
267
268 RAS_Polygon* RAS_MeshObject::AddPolygon(RAS_MaterialBucket *bucket, int numverts)
269 {
270         RAS_MeshMaterial *mmat;
271         RAS_Polygon *poly;
272         RAS_MeshSlot *slot;
273
274         /* find a mesh material */
275         mmat = GetMeshMaterial(bucket->GetPolyMaterial());
276
277         /* none found, create a new one */
278         if (!mmat) {
279                 RAS_MeshMaterial meshmat;
280                 meshmat.m_bucket = bucket;
281                 meshmat.m_baseslot = meshmat.m_bucket->AddMesh(numverts);
282                 meshmat.m_baseslot->m_mesh = this;
283                 m_materials.push_back(meshmat);
284                 mmat = &m_materials.back();
285         }
286
287         /* add it to the bucket, this also adds new display arrays */
288         slot = mmat->m_baseslot;
289         slot->AddPolygon(numverts);
290
291         /* create a new polygon */
292         RAS_DisplayArray *darray = slot->CurrentDisplayArray();
293         poly = new RAS_Polygon(bucket, darray, numverts);
294         m_Polygons.push_back(poly);
295
296         return poly;
297 }
298
299 void RAS_MeshObject::DebugColor(unsigned int abgr)
300 {
301         /*int numpolys = NumPolygons();
302
303         for (int i=0;i<numpolys;i++) {
304                 RAS_Polygon* poly = m_polygons[i];
305                 for (int v=0;v<poly->VertexCount();v++)
306                         RAS_TexVert* vtx = poly->GetVertex(v)->setDebugRGBA(abgr);
307         }
308         */
309
310         /* m_debugcolor = abgr; */
311 }
312
313 void RAS_MeshObject::SetVertexColor(RAS_IPolyMaterial* mat,MT_Vector4 rgba)
314 {
315         RAS_MeshMaterial *mmat = GetMeshMaterial(mat);
316         RAS_MeshSlot *slot = mmat->m_baseslot;
317         RAS_MeshSlot::iterator it;
318         size_t i;
319
320         for (slot->begin(it); !slot->end(it); slot->next(it))
321                 for (i=it.startvertex; i<it.endvertex; i++)
322                         it.vertex[i].SetRGBA(rgba);
323 }
324
325 void RAS_MeshObject::AddVertex(RAS_Polygon *poly, int i,
326                                                                 const MT_Point3& xyz,
327                                                                 const MT_Point2 uvs[RAS_TexVert::MAX_UNIT],
328                                                                 const MT_Vector4& tangent,
329                                                                 const unsigned int rgba,
330                                                                 const MT_Vector3& normal,
331                                                                 bool flat,
332                                                                 int origindex)
333 {
334         RAS_TexVert texvert(xyz, uvs, tangent, rgba, normal, flat, origindex);
335         RAS_MeshMaterial *mmat;
336         RAS_DisplayArray *darray;
337         RAS_MeshSlot *slot;
338         int offset;
339         
340         mmat = GetMeshMaterial(poly->GetMaterial()->GetPolyMaterial());
341         slot = mmat->m_baseslot;
342         darray = slot->CurrentDisplayArray();
343
344         { /* Shared Vertex! */
345                 /* find vertices shared between faces, with the restriction
346                  * that they exist in the same display array, and have the
347                  * same uv coordinate etc */
348                 vector<SharedVertex>& sharedmap = m_sharedvertex_map[origindex];
349                 vector<SharedVertex>::iterator it;
350
351                 for (it = sharedmap.begin(); it != sharedmap.end(); it++)
352                 {
353                         if (it->m_darray != darray)
354                                 continue;
355                         if (!it->m_darray->m_vertex[it->m_offset].closeTo(&texvert))
356                                 continue;
357
358                         /* found one, add it and we're done */
359                         if (poly->IsVisible())
360                                 slot->AddPolygonVertex(it->m_offset);
361                         poly->SetVertexOffset(i, it->m_offset);
362                         return;
363                 }
364         }
365
366         /* no shared vertex found, add a new one */
367         offset = slot->AddVertex(texvert);
368         if (poly->IsVisible())
369                 slot->AddPolygonVertex(offset);
370         poly->SetVertexOffset(i, offset);
371
372         { /* Shared Vertex! */
373                 SharedVertex shared;
374                 shared.m_darray = darray;
375                 shared.m_offset = offset;
376                 m_sharedvertex_map[origindex].push_back(shared);
377         }
378 }
379
380 int RAS_MeshObject::NumVertices(RAS_IPolyMaterial* mat)
381 {
382         RAS_MeshMaterial *mmat;
383         RAS_MeshSlot *slot;
384         RAS_MeshSlot::iterator it;
385         size_t len = 0;
386
387         mmat = GetMeshMaterial(mat);
388         slot = mmat->m_baseslot;
389         for (slot->begin(it); !slot->end(it); slot->next(it))
390                 len += it.endvertex - it.startvertex;
391         
392         return len;
393 }
394
395
396 RAS_TexVert* RAS_MeshObject::GetVertex(unsigned int matid,
397                                                                            unsigned int index)
398 {
399         RAS_MeshMaterial *mmat;
400         RAS_MeshSlot *slot;
401         RAS_MeshSlot::iterator it;
402         size_t len;
403
404         mmat = GetMeshMaterial(matid);
405
406         if (!mmat)
407                 return NULL;
408         
409         slot = mmat->m_baseslot;
410         len = 0;
411         for (slot->begin(it); !slot->end(it); slot->next(it)) {
412                 if (index >= len + it.endvertex - it.startvertex)
413                         len += it.endvertex - it.startvertex;
414                 else
415                         return &it.vertex[index - len];
416         }
417         
418         return NULL;
419 }
420
421 const float* RAS_MeshObject::GetVertexLocation(unsigned int orig_index)
422 {
423         vector<SharedVertex>& sharedmap = m_sharedvertex_map[orig_index];
424         vector<SharedVertex>::iterator it= sharedmap.begin();
425         return it->m_darray->m_vertex[it->m_offset].getXYZ();
426 }
427
428 void RAS_MeshObject::AddMeshUser(void *clientobj, SG_QList *head, RAS_Deformer* deformer)
429 {
430         list<RAS_MeshMaterial>::iterator it;
431         list<RAS_MeshMaterial>::iterator mit;
432
433         for (it = m_materials.begin();it!=m_materials.end();++it) {
434                 /* always copy from the base slot, which is never removed 
435                  * since new objects can be created with the same mesh data */
436                 if (deformer && !deformer->UseVertexArray())
437                 {
438                         // HACK! 
439                         // this deformer doesn't use vertex array => derive mesh
440                         // we must keep only the mesh slots that have unique material id
441                         // this is to match the derived mesh drawing function
442                         // Need a better solution in the future: scan the derive mesh and create vertex array
443                         RAS_IPolyMaterial* curmat = it->m_bucket->GetPolyMaterial();
444                         if (curmat->GetFlag() & RAS_BLENDERGLSL) 
445                         {
446                                 for (mit = m_materials.begin(); mit != it; ++mit)
447                                 {
448                                         RAS_IPolyMaterial* mat = mit->m_bucket->GetPolyMaterial();
449                                         if ((mat->GetFlag() & RAS_BLENDERGLSL) && 
450                                                 mat->GetMaterialIndex() == curmat->GetMaterialIndex())
451                                                 // no need to convert current mesh slot
452                                                 break;
453                                 }
454                                 if (mit != it)
455                                         continue;
456                         }
457                 }
458                 RAS_MeshSlot *ms = it->m_bucket->CopyMesh(it->m_baseslot);
459                 ms->m_clientObj = clientobj;
460                 ms->SetDeformer(deformer);
461                 it->m_slots.insert(clientobj, ms);
462                 head->QAddBack(ms);
463         }
464 }
465
466 void RAS_MeshObject::RemoveFromBuckets(void *clientobj)
467 {
468         list<RAS_MeshMaterial>::iterator it;
469         
470         for (it = m_materials.begin();it!=m_materials.end();++it) {
471                 RAS_MeshSlot **msp = it->m_slots[clientobj];
472
473                 if (!msp)
474                         continue;
475
476                 RAS_MeshSlot *ms = *msp;
477
478                 it->m_bucket->RemoveMesh(ms);
479                 it->m_slots.remove(clientobj);
480         }
481 }
482
483 //void RAS_MeshObject::Transform(const MT_Transform& trans)
484 //{
485         //m_trans.translate(MT_Vector3(0,0,1));//.operator *=(trans);
486         
487 //      for (int i=0;i<m_Polygons.size();i++)
488 //      {
489 //              m_Polygons[i]->Transform(trans);
490 //      }
491 //}
492
493
494 /*
495 void RAS_MeshObject::RelativeTransform(const MT_Vector3& vec)
496 {
497         for (int i=0;i<m_Polygons.size();i++)
498         {
499                 m_Polygons[i]->RelativeTransform(vec);
500         }
501 }
502 */
503
504 void RAS_MeshObject::SortPolygons(RAS_MeshSlot& ms, const MT_Transform &transform)
505 {
506         // Limitations: sorting is quite simple, and handles many
507         // cases wrong, partially due to polygons being sorted per
508         // bucket.
509         // 
510         // a) mixed triangles/quads are sorted wrong
511         // b) mixed materials are sorted wrong
512         // c) more than 65k faces are sorted wrong
513         // d) intersecting objects are sorted wrong
514         // e) intersecting polygons are sorted wrong
515         //
516         // a) can be solved by making all faces either triangles or quads
517         // if they need to be z-sorted. c) could be solved by allowing
518         // larger buckets, b) and d) cannot be solved easily if we want
519         // to avoid excessive state changes while drawing. e) would
520         // require splitting polygons.
521
522         RAS_MeshSlot::iterator it;
523         size_t j;
524
525         for (ms.begin(it); !ms.end(it); ms.next(it)) {
526                 unsigned int nvert = (int)it.array->m_type;
527                 unsigned int totpoly = it.totindex/nvert;
528
529                 if (totpoly <= 1)
530                         continue;
531                 if (it.array->m_type == RAS_DisplayArray::LINE)
532                         continue;
533
534                 // Extract camera Z plane...
535                 const MT_Vector3 pnorm(transform.getBasis()[2]);
536                 // unneeded: const MT_Scalar pval = transform.getOrigin()[2];
537
538                 vector<polygonSlot> poly_slots(totpoly);
539
540                 /* get indices and z into temporary array */
541                 for (j=0; j<totpoly; j++)
542                         poly_slots[j].get(it.vertex, it.index, j*nvert, nvert, pnorm);
543
544                 /* sort (stable_sort might be better, if flickering happens?) */
545                 std::sort(poly_slots.begin(), poly_slots.end(), backtofront());
546
547                 /* get indices from temporary array again */
548                 for (j=0; j<totpoly; j++)
549                         poly_slots[j].set(it.index, j*nvert, nvert);
550         }
551 }
552
553
554 void RAS_MeshObject::SchedulePolygons(int drawingmode)
555 {
556         if (m_bModified)
557         {
558                 m_bModified = false;
559                 m_bMeshModified = true;
560         } 
561 }
562
563 static int get_def_index(Object* ob, const char* vgroup)
564 {
565         bDeformGroup *curdef;
566         int index = 0;
567
568         for (curdef = (bDeformGroup*)ob->defbase.first; curdef; curdef=(bDeformGroup*)curdef->next, index++)
569                 if (!strcmp(curdef->name, vgroup))
570                         return index;
571
572         return -1;
573 }
574
575 void RAS_MeshObject::CheckWeightCache(Object* obj)
576 {
577         KeyBlock *kb;
578         int kbindex, defindex;
579         MDeformVert *dv= NULL;
580         int totvert, i;
581         float *weights;
582
583         if (!m_mesh->key)
584                 return;
585
586         for (kbindex = 0, kb = (KeyBlock *)m_mesh->key->block.first; kb; kb = kb->next, kbindex++)
587         {
588                 // first check the cases where the weight must be cleared
589                 if (kb->vgroup[0] == 0 ||
590                         m_mesh->dvert == NULL ||
591                         (defindex = get_def_index(obj, kb->vgroup)) == -1) {
592                         if (kb->weights) {
593                                 MEM_freeN(kb->weights);
594                                 kb->weights = NULL;
595                         }
596                         m_cacheWeightIndex[kbindex] = -1;
597                 } else if (m_cacheWeightIndex[kbindex] != defindex) {
598                         // a weight array is required but the cache is not matching
599                         if (kb->weights) {
600                                 MEM_freeN(kb->weights);
601                                 kb->weights = NULL;
602                         }
603
604                         dv= m_mesh->dvert;
605                         totvert= m_mesh->totvert;
606                 
607                         weights= (float*)MEM_mallocN(totvert*sizeof(float), "weights");
608                 
609                         for (i=0; i < totvert; i++, dv++) {
610                                 weights[i] = defvert_find_weight(dv, defindex);
611                         }
612
613                         kb->weights = weights;
614                         m_cacheWeightIndex[kbindex] = defindex;
615                 }
616         }
617 }
618
619