~ubuntu-branches/ubuntu/utopic/blender/utopic-proposed : revision 54

32

33

#include "MEM_guardedalloc.h"

34

35

#include "BLI_alloca.h"

35

36

#include "BLI_math.h"

36

#include "BLI_array.h"

37

#include "BLI_scanfill.h"

38

#include "BLI_listbase.h"

39

95

*

96

* Same as #calc_poly_normal but operates directly on a bmesh face.

97

*/

98

static void bm_face_calc_poly_normal(BMFace *f, float n[3])

98

static void bm_face_calc_poly_normal(const BMFace *f, float n[3])

99

{

100

BMLoop *l_first = BM_FACE_FIRST_LOOP(f);

101

BMLoop *l_iter = l_first;

125

* Same as #calc_poly_normal and #bm_face_calc_poly_normal

126

* but takes an array of vertex locations.

127

*/

128

static void bm_face_calc_poly_normal_vertex_cos(BMFace *f, float n[3],

128

static void bm_face_calc_poly_normal_vertex_cos(BMFace *f, float r_no[3],

129

float const (*vertexCos)[3])

130

{

131

BMLoop *l_first = BM_FACE_FIRST_LOOP(f);

133

float const *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];

134

float const *v_curr = vertexCos[BM_elem_index_get(l_first->v)];

135

136

zero_v3(n);

136

zero_v3(r_no);

137

138

/* Newell's Method */

139

do {

140

add_newell_cross_v3_v3v3(n, v_prev, v_curr);

140

add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);

141

142

l_iter = l_iter->next;

143

v_prev = v_curr;

144

v_curr = vertexCos[BM_elem_index_get(l_iter->v)];

145

} while (l_iter != l_first);

146

147

if (UNLIKELY(normalize_v3(n) == 0.0f)) {

148

n[2] = 1.0f; /* other axis set to 0.0 */

147

if (UNLIKELY(normalize_v3(r_no) == 0.0f)) {

148

r_no[2] = 1.0f; /* other axis set to 0.0 */

149

}

150

}

151

152

/**

153

* \brief COMPUTE POLY CENTER (BMFace)

154

*/

155

static void bm_face_calc_poly_center_mean_vertex_cos(BMFace *f, float r_cent[3],

156

float const (*vertexCos)[3])

157

{

158

BMLoop *l_first = BM_FACE_FIRST_LOOP(f);

159

BMLoop *l_iter = l_first;

160

161

zero_v3(r_cent);

162

163

/* Newell's Method */

164

do {

165

add_v3_v3(r_cent, vertexCos[BM_elem_index_get(l_iter->v)]);

166

} while ((l_iter = l_iter->next) != l_first);

167

mul_v3_fl(r_cent, 1.0f / f->len);

168

}

169

170

/**

153

171

* For tools that insist on using triangles, ideally we would cache this data.

154

172

*

155

173

* \param r_loops Store face loop pointers, (f->len)

156

174

* \param r_index Store triangle triples, indicies into \a r_loops, ((f->len - 2) * 3)

157

175

*/

158

int BM_face_calc_tessellation(BMFace *f, BMLoop **r_loops, int (*_r_index)[3])

176

int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*_r_index)[3])

159

177

{

160

178

int *r_index = (int *)_r_index;

161

179

BMLoop *l_first = BM_FACE_FIRST_LOOP(f);

370

388

*/

371

389

void BM_face_calc_center_mean(BMFace *f, float r_cent[3])

372

390

{

373

BMLoop *l_iter;

374

BMLoop *l_first;

391

BMLoop *l_iter, *l_first;

375

392

376

393

zero_v3(r_cent);

377

394

379

396

do {

380

397

add_v3_v3(r_cent, l_iter->v->co);

381

398

} while ((l_iter = l_iter->next) != l_first);

382

383

if (f->len)

384

mul_v3_fl(r_cent, 1.0f / (float) f->len);

399

mul_v3_fl(r_cent, 1.0f / (float) f->len);

385

400

}

386

401

387

402

/**

564

579

* is passed in as well.

565

580

*/

566

581

567

void BM_face_calc_normal(BMFace *f, float r_no[3])

582

void BM_face_calc_normal(const BMFace *f, float r_no[3])

568

583

{

569

584

BMLoop *l;

570

585

601

616

BM_face_calc_normal(f, f->no);

602

617

}

603

618

604

/* exact same as 'bmesh_face_normal_update' but accepts vertex coords */

605

void BM_face_normal_update_vcos(BMesh *bm, BMFace *f, float no[3],

606

float const (*vertexCos)[3])

619

/* exact same as 'BM_face_calc_normal' but accepts vertex coords */

620

void BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3],

621

float const (*vertexCos)[3])

607

622

{

608

623

BMLoop *l;

609

624

620

635

const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];

621

636

const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];

622

637

623

normal_quad_v3(no, co1, co2, co3, co4);

638

normal_quad_v3(r_no, co1, co2, co3, co4);

624

639

break;

625

640

}

626

641

case 3:

629

644

const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];

630

645

const float *co3 = vertexCos[BM_elem_index_get((l->next)->v)];

631

646

632

normal_tri_v3(no, co1, co2, co3);

647

normal_tri_v3(r_no, co1, co2, co3);

633

648

break;

634

649

}

635

650

case 0:

636

651

{

637

zero_v3(no);

652

zero_v3(r_no);

638

653

break;

639

654

}

640

655

default:

641

656

{

642

bm_face_calc_poly_normal_vertex_cos(f, no, vertexCos);

657

bm_face_calc_poly_normal_vertex_cos(f, r_no, vertexCos);

643

658

break;

644

659

}

645

660

}

646

661

}

647

662

663

/* exact same as 'BM_face_calc_normal' but accepts vertex coords */

664

void BM_face_calc_center_mean_vcos(BMesh *bm, BMFace *f, float r_cent[3],

665

float const (*vertexCos)[3])

666

{

667

/* must have valid index data */

668

BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);

669

(void)bm;

670

671

bm_face_calc_poly_center_mean_vertex_cos(f, r_cent, vertexCos);

672

}

673

648

674

/**

649

675

* \brief Face Flip Normal

650

676

*

803

829

continue;

804

830

}

805

831

806

if (isect_point_tri_v2(pv1, v1, v2, v3) || isect_point_tri_v2(pv1, v3, v2, v1)) {

832

if (isect_point_tri_v2(pv1, v1, v2, v3) ||

833

isect_point_tri_v2(pv1, v3, v2, v1))

834

{

807

835

#if 0

808

836

if (isect_point_tri_v2(pv1, v1, v2, v3))

809

837

printf("%d in (%d, %d, %d)\n", v3i, i, v1i, v2i);

837

865

const float cos_threshold = 0.9f;

838

866

const float bias = 1.0f + 1e-6f;

839

867

840

BLI_assert(len_squared_v3(f->no) > FLT_EPSILON);

868

/* just triangulate degenerate faces */

869

if (UNLIKELY(is_zero_v3(f->no))) {

870

return BM_FACE_FIRST_LOOP(f);

871

}

841

872

842

873

if (f->len == 4) {

843

874

BMLoop *larr[4];

849

880

i++;

850

881

} while ((l_iter = l_iter->next) != l_first);

851

882

852

/* pick 0/1 based on best lenth */

883

/* pick 0/1 based on best length */

853

884

/* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */

854

885

i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) >

855

len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);

886

len_squared_v3v3(larr[1]->v->co, larr[3]->v->co) * bias)) != use_beauty);

856

887

i4 = (i + 3) % 4;

857

888

/* Check produced tris aren't too flat/narrow...

858

889

* Probably not the best test, but is quite efficient and should at least avoid null-area faces! */

865

896

#endif

866

897

if (cos1 < cos2)

867

898

cos1 = cos2;

899

868

900

if (cos1 > cos_threshold) {

869

901

if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) &&

870

902

cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co)))

875

907

/* Last check we do not get overlapping triangles

876

908

* (as much as possible, there are some cases with no good solution!) */

877

909

i4 = (i + 3) % 4;

878

if (!bm_face_goodline((float const (*)[2])projectverts, f, BM_elem_index_get(larr[i4]->v),

879

BM_elem_index_get(larr[i]->v), BM_elem_index_get(larr[i + 1]->v)))

910

if (!bm_face_goodline((float const (*)[2])projectverts, f,

911

BM_elem_index_get(larr[i4]->v),

912

BM_elem_index_get(larr[i]->v),

913

BM_elem_index_get(larr[i + 1]->v)))

880

914

{

881

915

i = !i;

882

916

}

886

920

}

887

921

else {

888

922

/* float angle, bestangle = 180.0f; */

889

float cos, bestcos = 1.0f;

890

int i, j, len;

923

const int len = f->len;

924

float cos, cos_best = 1.0f;

925

int i, j;

891

926

892

927

/* Compute cos of all corners! */

893

928

i = 0;

894

929

l_iter = l_first = BM_FACE_FIRST_LOOP(f);

895

len = l_iter->f->len;

896

930

do {

897

931

const BMVert *v1 = l_iter->prev->v;

898

932

const BMVert *v2 = l_iter->v;

910

944

const BMVert *v2 = l_iter->v;

911

945

const BMVert *v3 = l_iter->next->v;

912

946

913

if (bm_face_goodline((float const (*)[2])projectverts, f,

914

BM_elem_index_get(v1), BM_elem_index_get(v2), BM_elem_index_get(v3)))

915

{

916

/* Compute highest cos (i.e. narrowest angle) of this tri. */

917

cos = max_fff(abscoss[i],

918

fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),

919

fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));

947

/* Compute highest cos (i.e. narrowest angle) of this tri. */

948

cos = max_fff(abscoss[i],

949

fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)),

950

fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)));

920

951

921

/* Compare to prev best (i.e. lowest) cos. */

922

if (cos < bestcos) {

952

/* Compare to prev best (i.e. lowest) cos. */

953

if (cos < cos_best) {

954

if (bm_face_goodline((float const (*)[2])projectverts, f,

955

BM_elem_index_get(v1),

956

BM_elem_index_get(v2),

957

BM_elem_index_get(v3)))

958

{

923

959

/* We must check this tri would not leave a (too much) degenerated remaining face! */

924

960

/* For now just assume if the average of cos of all

925

961

* "remaining face"'s corners is below a given threshold, it's OK. */

926

float avgcos = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));

962

float cos_mean = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co));

927

963

const int i_limit = (i - 1 + len) % len;

928

avgcos += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));

964

cos_mean += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co));

929

965

j = (i + 2) % len;

930

966

do {

931

avgcos += abscoss[j];

967

cos_mean += abscoss[j];

932

968

} while ((j = (j + 1) % len) != i_limit);

933

avgcos /= len - 1;

969

cos_mean /= len - 1;

934

970

935

971

/* We need a best ear in any case... */

936

if (avgcos < cos_threshold || (!bestear && avgcos < 1.0f)) {

972

if (cos_mean < cos_threshold || (!bestear && cos_mean < 1.0f)) {

937

973

/* OKI, keep this ear (corner...) as a potential best one! */

938

974

bestear = l_iter;

939

bestcos = cos;

975

cos_best = cos;

940

976

}

941

977

#if 0

942

978

else

943

printf("Had a nice tri (higest cos of %f, current bestcos is %f), "

979

printf("Had a nice tri (higest cos of %f, current cos_best is %f), "

944

980

"but average cos of all \"remaining face\"'s corners is too high (%f)!\n",

945

cos, bestcos, avgcos);

981

cos, cos_best, cos_mean);

946

982

#endif

947

983

}

948

984

}

980

1016

float *abscoss = BLI_array_alloca(abscoss, f_len_orig);

981

1017

float mat[3][3];

982

1018

1019

BLI_assert(BM_face_is_normal_valid(f));

1020

983

1021

axis_dominant_v3_to_m3(mat, f->no);

984

1022

985

1023

/* copy vertex coordinates to vertspace area */

1035

1073

{

1036

1074

const int len2 = len * 2;

1037

1075

BMLoop *l;

1038

float v1[2], v2[2], v3[2] /*, v4[3 */, no[3], mid[2], *p1, *p2, *p3, *p4;

1076

float v1[2], v2[2], v3[2], mid[2], *p1, *p2, *p3, *p4;

1039

1077

float out[2] = {-FLT_MAX, -FLT_MAX};

1040

1078

float axis_mat[3][3];

1041

1079

float (*projverts)[2] = BLI_array_alloca(projverts, f->len);

1043

1081

float fac1 = 1.0000001f, fac2 = 0.9f; //9999f; //0.999f;

1044

1082

int i, j, a = 0, clen;

1045

1083

1046

/* TODO, the face normal may already be correct */

1047

BM_face_calc_normal(f, no);

1084

BLI_assert(BM_face_is_normal_valid(f));

1048

1085

1049

axis_dominant_v3_to_m3(axis_mat, no);

1086

axis_dominant_v3_to_m3(axis_mat, f->no);

1050

1087

1051

1088

for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {

1052

1089

BM_elem_index_set(l, i); /* set_loop */

1176

1213

r_verts[2] = l->v; l = l->next;

1177

1214

r_verts[3] = l->v;

1178

1215

}

1216

1217

1218

/**

1219

* Small utility functions for fast access

1220

*

1221

* faster alternative to:

1222

* BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 3);

1223

*/

1224

void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3])

1225

{

1226

BMLoop *l = BM_FACE_FIRST_LOOP(f);

1227

1228

BLI_assert(f->len == 3);

1229

1230

r_loops[0] = l; l = l->next;

1231

r_loops[1] = l; l = l->next;

1232

r_loops[2] = l;

1233

}

1234

1235

/**

1236

* faster alternative to:

1237

* BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 4);

1238

*/

1239

void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])

1240

{

1241

BMLoop *l = BM_FACE_FIRST_LOOP(f);

1242

1243

BLI_assert(f->len == 4);

1244

1245

r_loops[0] = l; l = l->next;

1246

r_loops[1] = l; l = l->next;

1247

r_loops[2] = l; l = l->next;

1248

r_loops[3] = l;

1249

}