~ubuntu-branches/ubuntu/saucy/blender/saucy-proposed : revision 42

1

/*

2

*

3

*

4

* ***** BEGIN GPL LICENSE BLOCK *****

5

*

6

* This program is free software; you can redistribute it and/or

7

* modify it under the terms of the GNU General Public License

8

* as published by the Free Software Foundation; either version 2

9

* of the License, or (at your option) any later version.

10

*

11

* This program is distributed in the hope that it will be useful,

12

* but WITHOUT ANY WARRANTY; without even the implied warranty of

13

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

14

* GNU General Public License for more details.

15

*

16

* You should have received a copy of the GNU General Public License

17

* along with this program; if not, write to the Free Software Foundation,

18

* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.

19

*

20

21

22

*

23

* The Original Code is: all of this file.

24

*

25

* Contributor(s): none yet.

26

*

27

* ***** END GPL LICENSE BLOCK *****

28

*/

29

30

/** \file boolop/intern/BOP_Mesh.cpp

31

* \ingroup boolopintern

32

*/

33

34

35

#include "BOP_Mesh.h"

36

#include "BOP_MathUtils.h"

37

#include <iostream>

38

#include <fstream>

39

40

#include "MEM_guardedalloc.h"

41

#include "BLI_blenlib.h"

42

43

BOP_Mesh::BOP_Mesh()

44

{

45

#ifdef HASH

46

#ifdef HASH_PRINTF_DEBUG

47

printf ("has hashing\n");

48

#endif

49

hash = NULL;

50

hashsize = 0;

51

#endif

52

}

53

54

/**

55

* Destroys a mesh.

56

*/

57

BOP_Mesh::~BOP_Mesh()

58

{

59

const BOP_IT_Vertexs vertexsEnd = m_vertexs.end();

60

for(BOP_IT_Vertexs itv=m_vertexs.begin();itv!=vertexsEnd;itv++){

61

delete *itv;

62

}

63

m_vertexs.clear();

64

65

const BOP_IT_Edges edgesEnd = m_edges.end();

66

for(BOP_IT_Edges ite=m_edges.begin();ite!=edgesEnd;ite++){

67

delete *ite;

68

}

69

m_edges.clear();

70

71

const BOP_IT_Faces facesEnd = m_faces.end();

72

for(BOP_IT_Faces itf=m_faces.begin();itf!=facesEnd;itf++){

73

delete *itf;

74

}

75

m_faces.clear();

76

77

#ifdef HASH

78

while( hashsize ) {

79

--hashsize;

80

BLI_freelistN( &hash[hashsize] );

81

}

82

MEM_freeN( hash );

83

hash = NULL;

84

#endif

85

}

86

87

/**

88

* Adds a new vertex.

89

* @param p vertex point

90

* @return mesh vertex index

91

*/

92

BOP_Index BOP_Mesh::addVertex(MT_Point3 p)

93

{

94

m_vertexs.push_back(new BOP_Vertex(p));

95

return m_vertexs.size()-1;

96

}

97

98

/**

99

* Adds a new edge.

100

* @param v1 mesh vertex index

101

* @param v2 mesh vertex index

102

* @return mesh edge index

103

*/

104

BOP_Index BOP_Mesh::addEdge(BOP_Index v1, BOP_Index v2)

105

{

106

#ifdef HASH

107

/* prepare a new hash entry for the edge */

108

int minv;

109

EdgeEntry *h = (EdgeEntry *)MEM_callocN( sizeof( EdgeEntry ), "edgehash" );

110

111

/* store sorted, smallest vert first */

112

if( v1 < v2 ) {

113

minv = HASH(v1);

114

h->v1 = v1;

115

h->v2 = v2;

116

} else {

117

minv = HASH(v2);

118

h->v1 = v2;

119

h->v2 = v1;

120

}

121

h->index = m_edges.size();

122

123

/* if hash index larger than hash list, extend the list */

124

if( minv >= hashsize ) {

125

int newsize = (minv + 8) & ~7;

126

ListBase *nhash = (ListBase *)MEM_mallocN(

127

newsize * sizeof( ListBase ),

128

"edgehashtable" );

129

/* copy old entries */

130

memcpy( nhash, hash, sizeof( ListBase ) * hashsize );

131

/* clear new ones */

132

while( hashsize < newsize ) {

133

nhash[hashsize].first = nhash[hashsize].last = NULL;

134

++hashsize;

135

}

136

if( hash )

137

MEM_freeN( hash );

138

hash = nhash;

139

}

140

141

/* add the entry to tail of the right hash list */

142

BLI_addtail( &hash[minv], h );

143

#endif

144

m_edges.push_back(new BOP_Edge(v1,v2));

145

return m_edges.size()-1;

146

}

147

148

#ifdef HASH

149

/**

150

* replace one vertex with another in the hash list

151

* @param o old mesh vertex index

152

* @param n new mesh vertex index

153

* @param x edge's other mesh vertex index

154

*/

155

void BOP_Mesh::rehashVertex(BOP_Index o, BOP_Index n, BOP_Index x)

156

{

157

EdgeEntry *edge;

158

int minv = HASH(o);

159

BOP_Index v1, v2;

160

161

/* figure out where and what to look for */

162

if( o < x ) {

163

minv = HASH(o);

164

v1 = o; v2 = x;

165

} else {

166

minv = HASH(x);

167

v1 = x; v2 = o;

168

}

169

170

/* if hash is valid, search for the match */

171

if( minv < hashsize ) {

172

for(edge = (EdgeEntry *)hash[minv].first;

173

edge; edge = edge->next ) {

174

if(edge->v1 == v1 && edge->v2 == v2)

175

break;

176

}

177

178

/* NULL edge == no match */

179

if(!edge) {

180

#ifdef HASH_PRINTF_DEBUG

181

printf ("OOPS! didn't find edge (%d %d)\n",v1,v2);

182

#endif

183

return;

184

}

185

#ifdef HASH_PRINTF_DEBUG

186

printf ("found edge (%d %d)\n",v1,v2);

187

#endif

188

/* remove the edge from the old hash list */

189

BLI_remlink( &hash[minv], edge );

190

191

/* decide where the new edge should go */

192

if( n < x ) {

193

minv = HASH(n);

194

v1 = n; v2 = x;

195

} else {

196

minv = HASH(x);

197

edge->v1 = x; edge->v2 = n;

198

}

199

200

/* if necessary, extend the hash list */

201

if( minv >= hashsize ) {

202

#ifdef HASH_PRINTF_DEBUG

203

printf ("OOPS! new vertex too large! (%d->%d)\n",o,n);

204

#endif

205

int newsize = (minv + 8) & ~7;

206

ListBase *nhash = (ListBase *)MEM_mallocN(

207

newsize * sizeof( ListBase ),

208

"edgehashtable" );

209

memcpy( nhash, hash, sizeof( ListBase ) * hashsize );

210

while( hashsize < newsize ) {

211

nhash[hashsize].first = nhash[hashsize].last = NULL;

212

++hashsize;

213

}

214

if( hash )

215

MEM_freeN( hash );

216

hash = nhash;

217

}

218

219

/* add the entry to tail of the right hash list */

220

BLI_addtail( &hash[minv], edge );

221

} else {

222

#ifdef HASH_PRINTF_DEBUG

223

printf ("OOPS! hash not large enough for (%d %d)\n",minv,hashsize);

224

#endif

225

}

226

}

227

#endif

228

229

/**

230

* Adds a new face.

231

* @param face mesh face

232

* @return mesh face index

233

*/

234

BOP_Index BOP_Mesh::addFace(BOP_Face *face)

235

{

236

if (face->size()==3)

237

return addFace((BOP_Face3 *)face);

238

else

239

return addFace((BOP_Face4 *)face);

240

}

241

242

/**

243

* Adds a new triangle.

244

* @param face mesh triangle

245

* @return mesh face index

246

*/

247

BOP_Index BOP_Mesh::addFace(BOP_Face3 *face)

248

{

249

BOP_Index indexface = m_faces.size();

250

251

BOP_Index index1 = face->getVertex(0);

252

BOP_Index index2 = face->getVertex(1);

253

BOP_Index index3 = face->getVertex(2);

254

255

m_faces.push_back((BOP_Face *)face);

256

257

BOP_Index edge;

258

259

if (!getIndexEdge(index1,index2,edge)) {

260

edge = addEdge(index1,index2);

261

getVertex(index1)->addEdge(edge);

262

getVertex(index2)->addEdge(edge);

263

}

264

265

getEdge(edge)->addFace(indexface);

266

267

if (!getIndexEdge(index2,index3,edge)) {

268

edge = addEdge(index2,index3);

269

getVertex(index2)->addEdge(edge);

270

getVertex(index3)->addEdge(edge);

271

}

272

273

getEdge(edge)->addFace(indexface);

274

275

if (!getIndexEdge(index3,index1,edge)) {

276

edge = addEdge(index3,index1);

277

getVertex(index3)->addEdge(edge);

278

getVertex(index1)->addEdge(edge);

279

}

280

281

getEdge(edge)->addFace(indexface);

282

283

if ((index1 == index2) || (index1 == index3) || (index2 == index3))

284

face->setTAG(BROKEN);

285

286

return indexface;

287

}

288

289

/**

290

* Adds a new quad.

291

* @param face mesh quad

292

* @return mesh face index

293

*/

294

BOP_Index BOP_Mesh::addFace(BOP_Face4 *face)

295

{

296

m_faces.push_back((BOP_Face *)face);

297

BOP_Index indexface = m_faces.size()-1;

298

299

BOP_Index index1 = face->getVertex(0);

300

BOP_Index index2 = face->getVertex(1);

301

BOP_Index index3 = face->getVertex(2);

302

BOP_Index index4 = face->getVertex(3);

303

304

BOP_Index edge;

305

306

if (!getIndexEdge(index1,index2,edge)) {

307

edge = addEdge(index1,index2);

308

getVertex(index1)->addEdge(edge);

309

getVertex(index2)->addEdge(edge);

310

}

311

312

getEdge(edge)->addFace(indexface);

313

314

if (!getIndexEdge(index2,index3,edge)) {

315

edge = addEdge(index2,index3);

316

getVertex(index2)->addEdge(edge);

317

getVertex(index3)->addEdge(edge);

318

}

319

320

getEdge(edge)->addFace(indexface);

321

322

if (!getIndexEdge(index3,index4,edge)) {

323

edge = addEdge(index3,index4);

324

getVertex(index3)->addEdge(edge);

325

getVertex(index4)->addEdge(edge);

326

}

327

328

getEdge(edge)->addFace(indexface);

329

330

if (!getIndexEdge(index4,index1,edge)) {

331

edge = addEdge(index4,index1);

332

getVertex(index4)->addEdge(edge);

333

getVertex(index1)->addEdge(edge);

334

}

335

336

getEdge(edge)->addFace(indexface);

337

338

if ((index1 == index2) || (index1 == index3) || (index1 == index4) ||

339

(index2 == index3) || (index2 == index4) || (index3 == index4))

340

face->setTAG(BROKEN);

341

342

return m_faces.size()-1;

343

}

344

345

/**

346

* Returns if a faces set contains the specified face.

347

* @param faces faces set

348

* @param face face

349

* @return true if the set contains the specified face

350

*/

351

bool BOP_Mesh::containsFace(BOP_Faces *faces, BOP_Face *face)

352

{

353

const BOP_IT_Faces facesEnd = faces->end();

354

for(BOP_IT_Faces it = faces->begin();it!=facesEnd;it++) {

355

if (face == *it)

356

return true;

357

}

358

359

return false;

360

}

361

/**

362

* Returns the first edge with the specified vertex index from a list of edge indexs.

363

* @param edges edge indexs

364

* @param v vertex index

365

* @return first edge with the specified vertex index, NULL otherwise

366

*/

367

BOP_Edge* BOP_Mesh::getEdge(BOP_Indexs edges, BOP_Index v)

368

{

369

const BOP_IT_Indexs edgesEnd = edges.end();

370

for(BOP_IT_Indexs it=edges.begin();it!=edgesEnd;it++){

371

BOP_Edge *edge = m_edges[*it];

372

if ((edge->getVertex1() == v) || (edge->getVertex2() == v))

373

return edge;

374

}

375

return NULL;

376

}

377

378

/**

379

* Returns the mesh edge with the specified vertex indexs.

380

* @param v1 vertex index

381

* @param v2 vertex index

382

* @return mesh edge with the specified vertex indexs, NULL otherwise

383

*/

384

BOP_Edge* BOP_Mesh::getEdge(BOP_Index v1, BOP_Index v2)

385

{

386

#ifdef HASH

387

int minv;

388

EdgeEntry *edge;

389

390

/* figure out where and what to search for */

391

if( v1 < v2 ) {

392

minv = HASH(v1);

393

} else {

394

minv = HASH(v2);

395

BOP_Index tmp = v1;

396

v1 = v2;

397

v2 = tmp;

398

}

399

400

/* if hash index valid, search the list and return match if found */

401

if( minv < hashsize ) {

402

for(edge = (EdgeEntry *)hash[minv].first;

403

edge; edge = edge->next ) {

404

if(edge->v1 == v1 && edge->v2 == v2)

405

return m_edges[edge->index];

406

}

407

}

408

#else

409

const BOP_IT_Edges edgesEnd = m_edges.end();

410

for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++) {

411

if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) ||

412

((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1))

413

return *edge;

414

}

415

#endif

416

return NULL;

417

}

418

419

/**

420

* Returns the mesh edge index with the specified vertex indexs.

421

* @param v1 vertex index

422

* @param v2 vertex index

423

* @param e edge index with the specified vertex indexs

424

* @return true if there is a mesh edge with the specified vertex indexs, false otherwise

425

*/

426

bool BOP_Mesh::getIndexEdge(BOP_Index v1, BOP_Index v2, BOP_Index &e)

427

{

428

#ifdef HASH

429

int minv;

430

EdgeEntry *edge;

431

432

/* figure out what and where to look */

433

if( v1 < v2 ) {

434

minv = HASH(v1);

435

} else {

436

minv = HASH(v2);

437

BOP_Index tmp = v1;

438

v1 = v2;

439

v2 = tmp;

440

}

441

442

/* if hash index is valid, look for a match */

443

if( minv < hashsize ) {

444

for(edge = (EdgeEntry *)hash[minv].first;

445

edge; edge = edge->next ) {

446

if(edge->v1 == v1 && edge->v2 == v2)

447

break;

448

}

449

450

/* edge != NULL means match */

451

if(edge) {

452

#ifdef HASH_PRINTF_DEBUG

453

printf ("found edge (%d %d)\n",v1,v2);

454

#endif

455

e = edge->index;

456

#ifdef BOP_NEW_MERGE

457

if( m_edges[e]->getUsed() == false ) {

458

m_edges[e]->setUsed(true);

459

m_vertexs[v1]->addEdge(e);

460

m_vertexs[v2]->addEdge(e);

461

}

462

#endif

463

return true;

464

}

465

#ifdef HASH_PRINTF_DEBUG

466

else

467

printf ("didn't find edge (%d %d)\n",v1,v2);

468

#endif

469

}

470

#else

471

BOP_Index pos=0;

472

const BOP_IT_Edges edgesEnd = m_edges.end();

473

for(BOP_IT_Edges edge=m_edges.begin();edge!=edgesEnd;edge++,pos++) {

474

if (((*edge)->getVertex1() == v1 && (*edge)->getVertex2() == v2) ||

475

((*edge)->getVertex1() == v2 && (*edge)->getVertex2() == v1)){

476

e = pos;

477

return true;

478

}

479

}

480

#endif

481

return false;

482

}

483

484

/**

485

* Returns the mesh edge on the specified face and relative edge index.

486

* @param face mesh face

487

* @param edge face relative edge index

488

* @return mesh edge on the specified face and relative index, NULL otherwise

489

*/

490

BOP_Edge* BOP_Mesh::getEdge(BOP_Face *face, unsigned int edge)

491

{

492

if (face->size()==3)

493

return getEdge((BOP_Face3 *)face,edge);

494

else

495

return getEdge((BOP_Face4 *)face,edge);

496

}

497

498

/**

499

* Returns the mesh edge on the specified triangle and relative edge index.

500

* @param face mesh triangle

501

* @param edge face relative edge index

502

* @return mesh edge on the specified triangle and relative index, NULL otherwise

503

*/

504

BOP_Edge* BOP_Mesh::getEdge(BOP_Face3 *face, unsigned int edge)

505

{

506

switch(edge){

507

case 1:

508

return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1));

509

case 2:

510

return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2));

511

case 3:

512

return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(0));

513

};

514

515

return NULL;

516

}

517

518

/**

519

* Returns the mesh edge on the specified quad and relative edge index.

520

* @param face mesh quad

521

* @param edge face relative edge index

522

* @return mesh edge on the specified quad and relative index, NULL otherwise

523

*/

524

BOP_Edge * BOP_Mesh::getEdge(BOP_Face4 *face, unsigned int edge)

525

{

526

switch(edge){

527

case 1:

528

return getEdge(m_vertexs[face->getVertex(0)]->getEdges(),face->getVertex(1));

529

case 2:

530

return getEdge(m_vertexs[face->getVertex(1)]->getEdges(),face->getVertex(2));

531

case 3:

532

return getEdge(m_vertexs[face->getVertex(2)]->getEdges(),face->getVertex(3));

533

case 4:

534

return getEdge(m_vertexs[face->getVertex(3)]->getEdges(),face->getVertex(0));

535

};

536

537

return NULL;

538

}

539

540

/**

541

* Returns the mesh face with the specified vertex indexs.

542

* @param v1 vertex index

543

* @param v2 vertex index

544

* @param v3 vertex index

545

* @return mesh edge with the specified vertex indexs, NULL otherwise

546

*/

547

BOP_Face* BOP_Mesh::getFace(BOP_Index v1, BOP_Index v2, BOP_Index v3)

548

{

549

const BOP_IT_Faces facesEnd = m_faces.end();

550

for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) {

551

if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) &&

552

(*face)->containsVertex(v3))

553

return (*face);

554

}

555

return NULL;

556

}

557

558

/**

559

* Returns the mesh face index with the specified vertex indexs.

560

* @param v1 vertex index

561

* @param v2 vertex index

562

* @param v3 vertex index

563

* @param f face index with the specified vertex indexs

564

* @return true if there is a mesh face with the specified vertex indexs, false otherwise

565

*/

566

bool BOP_Mesh::getIndexFace(BOP_Index v1, BOP_Index v2, BOP_Index v3, BOP_Index &f)

567

{

568

BOP_Index pos=0;

569

const BOP_IT_Faces facesEnd = m_faces.end();

570

for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++,pos++) {

571

if ((*face)->containsVertex(v1) && (*face)->containsVertex(v2) &&

572

(*face)->containsVertex(v3)){

573

f = pos;

574

return true;

575

}

576

}

577

return false;

578

}

579

580

/**

581

* Returns the vertices set of this mesh.

582

* @return vertices set

583

*/

584

BOP_Vertexs &BOP_Mesh::getVertexs()

585

{

586

return m_vertexs;

587

}

588

589

/**

590

* Returns the edges set of this mesh.

591

* @return edges set

592

*/

593

BOP_Edges &BOP_Mesh::getEdges()

594

{

595

return m_edges;

596

}

597

598

/**

599

* Returns the faces set of this mesh.

600

* @return faces set

601

*/

602

BOP_Faces &BOP_Mesh::getFaces()

603

{

604

return m_faces;

605

}

606

607

/**

608

* Returns the mesh vertex with the specified index.

609

* @param i vertex index

610

* @return vertex with the specified index

611

*/

612

BOP_Vertex* BOP_Mesh::getVertex(BOP_Index i)

613

{

614

return m_vertexs[i];

615

}

616

617

/**

618

* Returns the mesh edge with the specified index.

619

* @param i edge index

620

* @return edge with the specified index

621

*/

622

BOP_Edge* BOP_Mesh::getEdge(BOP_Index i)

623

{

624

return m_edges[i];

625

}

626

627

/**

628

* Returns the mesh face with the specified index.

629

* @param i face index

630

* @return face with the specified index

631

*/

632

BOP_Face* BOP_Mesh::getFace(BOP_Index i)

633

{

634

return m_faces[i];

635

}

636

637

/**

638

* Returns the number of vertices of this mesh.

639

* @return number of vertices

640

*/

641

unsigned int BOP_Mesh::getNumVertexs()

642

{

643

return m_vertexs.size();

644

}

645

646

/**

647

* Returns the number of edges of this mesh.

648

* @return number of edges

649

*/

650

unsigned int BOP_Mesh::getNumEdges()

651

{

652

return m_edges.size();

653

}

654

655

/**

656

* Returns the number of faces of this mesh.

657

* @return number of faces

658

*/

659

unsigned int BOP_Mesh::getNumFaces()

660

{

661

return m_faces.size();

662

}

663

664

/**

665

* Returns the number of vertices of this mesh with the specified tag.

666

* @return number of vertices with the specified tag

667

*/

668

unsigned int BOP_Mesh::getNumVertexs(BOP_TAG tag)

669

{

670

unsigned int count = 0;

671

const BOP_IT_Vertexs vertexsEnd = m_vertexs.end();

672

for(BOP_IT_Vertexs vertex=m_vertexs.begin();vertex!=vertexsEnd;vertex++) {

673

if ((*vertex)->getTAG() == tag) count++;

674

}

675

return count;

676

}

677

/**

678

* Returns the number of faces of this mesh with the specified tag.

679

* @return number of faces with the specified tag

680

*/

681

unsigned int BOP_Mesh::getNumFaces(BOP_TAG tag)

682

{

683

unsigned int count = 0;

684

const BOP_IT_Faces facesEnd = m_faces.end();

685

for(BOP_IT_Faces face=m_faces.begin();face!=facesEnd;face++) {

686

if ((*face)->getTAG() == tag) count++;

687

}

688

return count;

689

}

690

691

/**

692

* Marks faces which bad edges as BROKEN (invalid face, no further processing).

693

* @param edge edge which is being replaced

694

* @param mesh mesh containing faces

695

*/

696

697

static void removeBrokenFaces( BOP_Edge *edge, BOP_Mesh *mesh )

698

{

699

BOP_Faces m_faces = mesh->getFaces();

700

701

BOP_Indexs edgeFaces = edge->getFaces();

702

const BOP_IT_Indexs edgeFacesEnd = edgeFaces.end();

703

for(BOP_IT_Indexs idxFace=edgeFaces.begin();idxFace!=edgeFacesEnd;

704

idxFace++)

705

m_faces[*idxFace]->setTAG(BROKEN);

706

}

707

708

/**

709

* Replaces a vertex index.

710

* @param oldIndex old vertex index

711

* @param newIndex new vertex index

712

*/

713

BOP_Index BOP_Mesh::replaceVertexIndex(BOP_Index oldIndex, BOP_Index newIndex)

714

{

715

BOP_IT_Indexs oldEdgeIndex;

716

if (oldIndex==newIndex) return newIndex;

717

718

// Update faces, edges and vertices

719

BOP_Vertex *oldVertex = m_vertexs[oldIndex];

720

BOP_Vertex *newVertex = m_vertexs[newIndex];

721

BOP_Indexs oldEdges = oldVertex->getEdges();

722

723

// Update faces to the newIndex

724

BOP_IT_Indexs oldEdgesEnd = oldEdges.end();

725

for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;

726

oldEdgeIndex++) {

727

BOP_Edge *edge = m_edges[*oldEdgeIndex];

728

if ((edge->getVertex1()==oldIndex && edge->getVertex2()==newIndex) ||

729

(edge->getVertex2()==oldIndex && edge->getVertex1()==newIndex)) {

730

// Remove old edge ==> set edge faces to BROKEN

731

removeBrokenFaces( edge, this );

732

oldVertex->removeEdge(*oldEdgeIndex);

733

newVertex->removeEdge(*oldEdgeIndex);

734

}

735

else {

736

BOP_Indexs faces = edge->getFaces();

737

const BOP_IT_Indexs facesEnd = faces.end();

738

for(BOP_IT_Indexs face=faces.begin();face!=facesEnd;face++) {

739

if (m_faces[*face]->getTAG()!=BROKEN)

740

m_faces[*face]->replaceVertexIndex(oldIndex,newIndex);

741

}

742

}

743

}

744

745

oldEdgesEnd = oldEdges.end();

746

for(oldEdgeIndex=oldEdges.begin();oldEdgeIndex!=oldEdgesEnd;

747

oldEdgeIndex++) {

748

BOP_Edge * edge = m_edges[*oldEdgeIndex];

749

BOP_Edge * edge2;

750

BOP_Index v1 = edge->getVertex1();

751

752

v1 = (v1==oldIndex?edge->getVertex2():v1);

753

if ((edge2 = getEdge(newIndex,v1)) == NULL) {

754

edge->replaceVertexIndex(oldIndex,newIndex);

755

if ( edge->getVertex1() == edge->getVertex2() ) {

756

removeBrokenFaces( edge, this );

757

oldVertex->removeEdge(*oldEdgeIndex);

758

}

759

#ifdef HASH

760

rehashVertex(oldIndex,newIndex,v1);

761

#endif

762

newVertex->addEdge(*oldEdgeIndex);

763

}

764

else {

765

BOP_Indexs faces = edge->getFaces();

766

const BOP_IT_Indexs facesEnd = faces.end();

767

for(BOP_IT_Indexs f=faces.begin();f!=facesEnd;f++) {

768

if (m_faces[*f]->getTAG()!=BROKEN)

769

edge2->addFace(*f);

770

}

771

BOP_Vertex *oppositeVertex = m_vertexs[v1];

772

oppositeVertex->removeEdge(*oldEdgeIndex);

773

edge->replaceVertexIndex(oldIndex,newIndex);

774

if ( edge->getVertex1() == edge->getVertex2() ) {

775

removeBrokenFaces( edge, this );

776

oldVertex->removeEdge(*oldEdgeIndex);

777

newVertex->removeEdge(*oldEdgeIndex);

778

}

779

#ifdef HASH

780

rehashVertex(oldIndex,newIndex,v1);

781

#endif

782

}

783

}

784

oldVertex->setTAG(BROKEN);

785

786

return newIndex;

787

}

788

789

bool BOP_Mesh::isClosedMesh()

790

{

791

for(unsigned int i=0; i<m_edges.size(); i++) {

792

BOP_Edge *edge = m_edges[i];

793

BOP_Indexs faces = edge->getFaces();

794

unsigned int count = 0;

795

const BOP_IT_Indexs facesEnd = faces.end();

796

for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {

797

if (m_faces[*it]->getTAG()!=BROKEN)

798

count++;

799

}

800

801

if ((count%2)!=0) return false;

802

}

803

804

return true;

805

}

806

807

808

#ifdef BOP_DEBUG

809

/******************************************************************************

810

* DEBUG METHODS *

811

* This functions are used to test the mesh state and debug program errors. *

812

******************************************************************************/

813

814

/**

815

* print

816

*/

817

void BOP_Mesh::print()

818

{

819

unsigned int i;

820

cout << "--Faces--" << endl;

821

for(i=0;i<m_faces.size();i++){

822

cout << "Face " << i << ": " << m_faces[i] << endl;

823

}

824

825

cout << "--Vertices--" << endl;

826

for(i=0;i<m_vertexs.size();i++){

827

cout << "Point " << i << ": " << m_vertexs[i]->getPoint() << endl;

828

}

829

}

830

831

/**

832

* printFormat

833

*/

834

void BOP_Mesh::printFormat(BOP_Faces *faces)

835

{

836

if (faces->size()) {

837

for(unsigned int it=1;it<faces->size();it++) {

838

if ((*faces)[it]->getTAG()!=BROKEN) {

839

cout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";

840

cout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";

841

cout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;

842

}

843

}

844

}

845

}

846

847

/**

848

* saveFormat

849

*/

850

void BOP_Mesh::saveFormat(BOP_Faces *faces,char *filename)

851

{

852

ofstream fout(filename);

853

854

if (!fout.is_open()) {

855

cerr << "BOP_Mesh::saveFormat Error: Could not create file." << endl;

856

return;

857

}

858

859

unsigned int count = 0;

860

if (faces->size()) {

861

for(unsigned int it=0;it<faces->size();it++) {

862

if ((*faces)[it]->getTAG()!=BROKEN) {

863

count++;

864

}

865

}

866

}

867

868

fout << count << endl;

869

if (faces->size()) {

870

for(unsigned int it=0;it<faces->size();it++) {

871

if ((*faces)[it]->getTAG()!=BROKEN){

872

fout << m_vertexs[(*faces)[it]->getVertex(0)]->getPoint() << " ";

873

fout << m_vertexs[(*faces)[it]->getVertex(1)]->getPoint() << " ";

874

fout << m_vertexs[(*faces)[it]->getVertex(2)]->getPoint() << endl;

875

}

876

}

877

}

878

879

fout.close();

880

}

881

882

/**

883

* printFormat

884

*/

885

void BOP_Mesh::printFormat()

886

{

887

cout << "--Vertices--" << endl;

888

if (m_vertexs.size()>0) {

889

cout << "{" << m_vertexs[0]->getPoint().x() << ",";

890

cout << m_vertexs[0]->getPoint().y() << ",";

891

cout << m_vertexs[0]->getPoint().z() << "}";

892

for(unsigned int i=1;i<m_vertexs.size();i++) {

893

cout << ",{" << m_vertexs[i]->getPoint().x() << ",";

894

cout << m_vertexs[i]->getPoint().y() << ",";

895

cout << m_vertexs[i]->getPoint().z() << "}";

896

}

897

cout << endl;

898

}

899

900

cout << "--Faces--" << endl;

901

if (m_faces.size()>0) {

902

cout << "{" << m_faces[0]->getVertex(0) << ",";

903

cout << m_faces[0]->getVertex(1) << "," << m_faces[0]->getVertex(2) << "}";

904

for(unsigned int i=1;i<m_faces.size();i++) {

905

cout << ",{" << m_faces[i]->getVertex(0) << ",";

906

cout << m_faces[i]->getVertex(1) << "," << m_faces[i]->getVertex(2) << "}";

907

}

908

cout << endl;

909

}

910

}

911

912

/**

913

* printFace

914

*/

915

void BOP_Mesh::printFace(BOP_Face *face, int col)

916

{

917

cout << "--Face" << endl;

918

cout << m_vertexs[face->getVertex(0)]->getPoint();

919

cout << " " << m_vertexs[face->getVertex(1)]->getPoint();

920

cout << " " << m_vertexs[face->getVertex(2)]->getPoint();

921

if (face->size()==4)

922

cout << " " << m_vertexs[face->getVertex(3)]->getPoint();

923

cout << " " << col << endl;

924

}

925

926

/**

927

* testMesh

928

*/

929

void BOP_Mesh::testMesh()

930

{

931

932

BOP_Face* cares[10];

933

unsigned int nedges=0,i;

934

for(i=0;i<m_edges.size();i++) {

935

BOP_Edge *edge = m_edges[i];

936

BOP_Indexs faces = edge->getFaces();

937

unsigned int count = 0;

938

const BOP_IT_Indexs facesEnd = faces.end();

939

for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {

940

if (m_faces[*it]->getTAG()!=BROKEN) {

941

cares[count] = m_faces[*it];

942

count++;

943

944

}

945

}

946

947

if ((count%2)!=0) nedges++;

948

}

949

if (nedges)

950

cout << nedges << " wrong edges." << endl;

951

else

952

cout << "well edges." << endl;

953

954

unsigned int duplFaces = 0;

955

unsigned int wrongFaces = 0;

956

for(i=0;i<m_faces.size();i++){

957

BOP_Face *faceI = m_faces[i];

958

if (faceI->getTAG()==BROKEN)

959

continue;

960

961

if (testFace(faceI)){

962

wrongFaces++;

963

cout << "Wrong Face: " << faceI << endl;

964

}

965

966

for(unsigned int j=i+1;j<m_faces.size();j++){

967

BOP_Face *faceJ = m_faces[j];

968

969

if (faceJ->getTAG()==BROKEN)

970

continue;

971

972

if (testFaces(faceI,faceJ)){

973

duplFaces++;

974

cout << "Duplicate FaceI: " << faceI << endl;

975

cout << "Duplicate FaceJ: " << faceJ << endl;

976

}

977

}

978

}

979

980

cout << duplFaces << " duplicate faces." << endl;

981

cout << wrongFaces << " wrong faces." << endl;

982

}

983

984

/**

985

* testFace

986

*/

987

bool BOP_Mesh::testFace(BOP_Face *face){

988

989

for(unsigned int i=0;i<face->size();i++){

990

for(unsigned int j=i+1;j<face->size();j++){

991

if (face->getVertex(i)==face->getVertex(j))

992

return true;

993

}

994

}

995

996

return false;

997

}

998

999

/**

1000

* testFaces

1001

*/

1002

bool BOP_Mesh::testFaces(BOP_Face *faceI, BOP_Face *faceJ){

1003

1004

if (faceI->size()<faceJ->size()){

1005

for(unsigned int i=0;i<faceI->size();i++){

1006

if (!faceJ->containsVertex(faceI->getVertex(i)))

1007

return false;

1008

}

1009

//faceI->setTAG(BROKEN);

1010

}

1011

else{

1012

for(unsigned int i=0;i<faceJ->size();i++){

1013

if (!faceI->containsVertex(faceJ->getVertex(i)))

1014

return false;

1015

}

1016

//faceJ->setTAG(BROKEN);

1017

}

1018

1019

return true;

1020

}

1021

1022

/**

1023

* testPlane

1024

*/

1025

void BOP_Mesh::testPlane(BOP_Face *face)

1026

{

1027

MT_Plane3 plane1(m_vertexs[face->getVertex(0)]->getPoint(),

1028

m_vertexs[face->getVertex(1)]->getPoint(),

1029

m_vertexs[face->getVertex(2)]->getPoint());

1030

1031

if (BOP_orientation(plane1,face->getPlane()) < 0) {

1032

cout << "Test Plane " << face << " v1: ";

1033

cout << m_vertexs[face->getVertex(0)]->getPoint() << " v2: ";

1034

cout << m_vertexs[face->getVertex(1)]->getPoint() << " v3: ";

1035

cout << m_vertexs[face->getVertex(2)]->getPoint() << " plane: ";

1036

cout << face->getPlane() << endl;

1037

cout << "Incorrect vertices order!!! plane1: " << plane1 << " (";

1038

cout << BOP_orientation(plane1,face->getPlane()) << ") " << " invert ";

1039

cout << MT_Plane3(m_vertexs[face->getVertex(2)]->getPoint(),

1040

m_vertexs[face->getVertex(1)]->getPoint(),

1041

m_vertexs[face->getVertex(0)]->getPoint()) << endl;

1042

if (BOP_collinear(m_vertexs[face->getVertex(0)]->getPoint(),

1043

m_vertexs[face->getVertex(1)]->getPoint(),

1044

m_vertexs[face->getVertex(2)]->getPoint())) {

1045

cout << " COLLINEAR!!!" << endl;

1046

}

1047

else {

1048

cout << endl;

1049

}

1050

}

1051

}

1052

1053

/**

1054

* testEdges

1055

*/

1056

bool BOP_Mesh::testEdges(BOP_Faces *facesObj)

1057

{

1058

for(unsigned int i=0;i<m_edges.size();i++) {

1059

BOP_Edge *edge = m_edges[i];

1060

BOP_Indexs faces = edge->getFaces();

1061

unsigned int count = 0;

1062

const BOP_IT_Indexs facesEnd = faces.end();

1063

for(BOP_IT_Indexs it = faces.begin();it!=facesEnd;it++) {

1064

if ((m_faces[*it]->getTAG()!=BROKEN) && containsFace(facesObj,m_faces[*it]))

1065

count++;

1066

}

1067

if ((count%2)!=0) {

1068

return false;

1069

}

1070

}

1071

1072

return true;

1073

}

1074

1075

/**

1076

* updatePlanes

1077

*/

1078

void BOP_Mesh::updatePlanes()

1079

{

1080

const BOP_IT_Faces facesEnd = m_faces.end();

1081

for(BOP_IT_Faces it = m_faces.begin();it!=facesEnd;it++) {

1082

BOP_Face *face = *it;

1083

MT_Plane3 plane(m_vertexs[face->getVertex(0)]->getPoint(),

1084

m_vertexs[face->getVertex(1)]->getPoint(),

1085

m_vertexs[face->getVertex(2)]->getPoint());

1086

face->setPlane(plane);

1087

}

1088

}

1089

1090

#endif