1 /* -*- c++ -*-
2 FILE: Polymgr.cpp
3 RCS REVISION: $Revision: 1.23 $
4
5 COPYRIGHT: (c) 1999 -- 2003 Melinda Green, Don Hatch, and Jay Berkenbilt - Superliminal Software
6
7 LICENSE: Free to use and modify for non-commercial purposes as long as the
8 following conditions are adhered to:
9 1) Obvious credit for the source of this code and the designs it embodies
10 are clearly made, and
11 2) Ports and derived versions of 4D Magic Cube programs are not distributed
12 without the express written permission of the authors.
13
14 DESCRIPTION:
15 Implementation of the PolygonManager4D class
16 */
17
18 #include "MagicCube.h"
19 #include "Polymgr.h"
20 #include "Math4d.h"
21 #include "Preferences.h"
22 #include <stdio.h>
23
24 static int length = LENGTH;
25 // FIX THIS-- need consistent initializion method
26 static real tilt = DTOR(TILT), twirl = DTOR(TWIRL);
27
28
29 static real bbox[2][2] = { {0} };
30
31 static real
sine_interp(real x)32 sine_interp(real x)
33 {
34 return (sin((x - .5) * PI) + 1) / 2;
35 }
36
37 #define are_CCW(v0,v1,v2) (twice_triangle_area(v0,v1,v2) > 0)
38 #define are_CW(v0,v1,v2) (twice_triangle_area(v0,v1,v2) < 0)
39 /* HA! the following are reversed from the above, since we inverted Y */
40 #define ushort_are_CCW(v0,v1,v2) (ushort_twice_triangle_area(v0,v1,v2) < 0)
41 #define ushort_are_CW(v0,v1,v2) (ushort_twice_triangle_area(v0,v1,v2) > 0)
42 static real
twice_triangle_area(real v0[2],real v1[2],real v2[2])43 twice_triangle_area(real v0[2], real v1[2], real v2[2])
44 {
45 real edge1[2], edge2[2];
46 VMV2(edge1, v1, v0);
47 VMV2(edge2, v2, v0);
48 return VXV2(edge1, edge2);
49 }
50 static long
ushort_twice_triangle_area(unsigned short v0[2],unsigned short v1[2],unsigned short v2[2])51 ushort_twice_triangle_area(unsigned short v0[2],
52 unsigned short v1[2], unsigned short v2[2])
53 {
54 int edge1[2], edge2[2];
55 VMV2(edge1, v1, v0);
56 VMV2(edge2, v2, v0);
57 return VXV2(edge1, edge2);
58 }
59
60
61 static void
get_triangle_normal(real v0[2],real v1[2],real v2[2],real nrml[3])62 get_triangle_normal(real v0[2], real v1[2], real v2[2], real nrml[3])
63 {
64 real edge1[3], edge2[3], tomultiplyby;
65 VMV3(edge1, v1, v0);
66 VMV3(edge2, v2, v0);
67 VXV3(nrml, edge1, edge2);
68 /* normalize */
69 tomultiplyby = 1 / sqrt(NORMSQRD3(nrml));
70 VXS3(nrml, nrml, tomultiplyby);
71 }
72
73
74 static void
getrotmat(int ax,real angle,real mat3[3][3])75 getrotmat(int ax, real angle, real mat3[3][3])
76 {
77 real c = cos(angle), s = sin(angle);
78 int fromax = (ax + 1) % 3, toax = (ax + 2) % 3;
79
80 ZEROMAT3(mat3);
81 mat3[ax][ax] = 1;
82 mat3[fromax][fromax] = c;
83 mat3[fromax][toax] = s;
84 mat3[toax][fromax] = -s;
85 mat3[toax][(ax + 2) % 3] = c;
86 }
87 /*
88 * Comparison function for qsort
89 */
90 static int
zcmp(const void * a,const void * b)91 zcmp(const void *a, const void *b)
92 {
93 const real **A = (const real **)a;
94 const real **B = (const real **)b;
95 return **A < **B ? -1 : **A > **B ? 1 : 0;
96 }
97
98
PolygonManager4D(Preferences & prefs)99 PolygonManager4D::PolygonManager4D(Preferences& prefs) :
100 preferences(prefs)
101 {
102 tilt = DTOR(prefs.getRealProperty(M4D_TILT, TILT));
103 twirl = DTOR(prefs.getRealProperty(M4D_TWIRL, TWIRL));
104 faceshrink = prefs.getRealProperty(M4D_FACESHRINK, FACESHRINK);
105 stickershrink = prefs.getRealProperty(M4D_STICKERSHRINK, STICKERSHRINK);
106 nframes_90 = prefs.getIntProperty(M4D_NFRAMES_90, NFRAMES_90);
107 nframes_120 = prefs.getIntProperty(M4D_NFRAMES_120, NFRAMES_120);
108 nframes_180 = prefs.getIntProperty(M4D_NFRAMES_180, NFRAMES_180);
109
110 reset(prefs.getLength());
111 }
112
reset(int new_length)113 void PolygonManager4D::reset(int new_length)
114 {
115 if (new_length != -1)
116 {
117 length = new_length;
118
119 bbox[0][0] = 0;
120 n_untwisted_verts4 = getUntwistedVerts4(untwisted_verts4, faceshrink, stickershrink);
121
122 calc3DFrameInfo(
123 (struct stickerspec *)NULL,
124 CCW,
125 0, /* slicesmask-- so everything else is ignored */
126 0.,
127 sine_interp,
128 n_untwisted_verts4,
129 untwisted_verts4,
130 preferences.getRealProperty(M4D_EYEW, EYEW),
131 !preferences.getBoolProperty(M4D_NOCULLCELLS), /* cullcells */
132 &n_untwisted_verts3,
133 untwisted_verts3,
134 &n_untwisted_quads3,
135 untwisted_quads3,
136 untwisted_stickerids3,
137 NULL);
138 }
139 }
140
setShrinkers(real face_val,real sticker_val)141 void PolygonManager4D::setShrinkers(real face_val, real sticker_val)
142 {
143 faceshrink = face_val;
144 stickershrink = sticker_val;
145 n_untwisted_verts4 =
146 getUntwistedVerts4(untwisted_verts4,
147 faceshrink, stickershrink);
148 }
149
calc3DTo2DFrameInfo(int nverts3,real verts3[][3],int nquads3,int quads3[][4],int stickerids3[],real tilt,real twirl,real eyez,real sunvec[3],int sunvec_is_in_objspace,int cullverts,int cullbackfaces,int zsort,int * Nverts2,real verts2[][2],int * Nquads2,int quads2[][4],int quadids2[],real brightnesses[])150 void PolygonManager4D::calc3DTo2DFrameInfo(
151 /* INPUTS */
152 int nverts3, real verts3[][3], int nquads3,
153 int quads3[][4], int stickerids3[], real tilt,
154 real twirl, real eyez, real sunvec[3],
155 int sunvec_is_in_objspace, int cullverts,
156 int cullbackfaces, int zsort,
157 /* OUTPUTS */
158 int *Nverts2, real verts2[][2], int *Nquads2,
159 int quads2[][4], int quadids2[],
160 real brightnesses[])
161 {
162 int i;
163 real twirlmat[3][3], tiltmat[3][3], viewingmat[3][3];
164 real objspace_sunvec[3], triangle_normal[3];
165 real tomultiplyby, norm;
166 int nverts2, nquads2; /* set *Nverts2 and *Nquads2 to these at
167 end */
168 real transformed_verts3[MAXVERTS][3];
169
170
171 /*
172 * make a viewing matrix that tilts and twirls
173 */
174 getrotmat(Y, twirl, twirlmat);
175 getrotmat(X, tilt, tiltmat);
176 MXM3(viewingmat, twirlmat, tiltmat);
177
178 /*
179 * get normalized sunvec in object space
180 * (it's more efficient to transform the light vector to object space
181 * than to transform all the face normals to world space)
182 */
183 if (sunvec && brightnesses)
184 {
185 if (sunvec_is_in_objspace)
186 SET3(objspace_sunvec, sunvec);
187 else /* apply inverse of viewingmat to sunvec to
188 get objspace_sunvec */
189 MXV3(objspace_sunvec, viewingmat, sunvec);
190 norm = sqrt(NORMSQRD3(objspace_sunvec));
191 VDS3(objspace_sunvec, objspace_sunvec, norm);
192 }
193
194 /*
195 * transform verts
196 */
197 for (i = 0; i < nverts3; ++i)
198 {
199 VXM3(transformed_verts3[i], verts3[i], viewingmat);
200 tomultiplyby = 1. / (eyez - transformed_verts3[i][Z]);
201 VXS2(verts2[i], transformed_verts3[i], tomultiplyby);
202 }
203
204 /*
205 * Copy quads3 to quads2
206 * and stickerids3 to quadids2,
207 * discarding back faces
208 */
209 nquads2 = 0;
210 for (i = 0; i < nquads3; ++i)
211 {
212 if (cullbackfaces && !are_CCW(verts2[quads3[i][0]],
213 verts2[quads3[i][1]],
214 verts2[quads3[i][2]]))
215 {
216 continue;
217 }
218 SET4(quads2[nquads2], quads3[i]);
219 quadids2[nquads2] = (stickerids3[quads3[i][0] / 8]) * 6 + (i % 6);
220 if (sunvec && brightnesses)
221 {
222 get_triangle_normal(verts3[quads3[i][0]],
223 verts3[quads3[i][1]],
224 verts3[quads3[i][2]], triangle_normal);
225 brightnesses[nquads2] = DOT3(triangle_normal, objspace_sunvec);
226 if (brightnesses[nquads2] < 0)
227 brightnesses[nquads2] = 0;
228 }
229 nquads2++;
230 }
231
232 nverts2 = nverts3;
233
234 /*
235 * Zsort the quads, quadids and brighnesses, from least to greatest z
236 */
237 if (zsort)
238 {
239 real quadzs[MAXQUADS];
240 real *qsortbuf[MAXQUADS];
241 int tempquads[MAXQUADS][4];
242 int tempquadids[MAXQUADS];
243 real tempbrightnesses[MAXQUADS];
244 for (i = 0; i < nquads2; ++i)
245 {
246 quadzs[i] = transformed_verts3[quads2[i][0]][Z]
247 + transformed_verts3[quads2[i][2]][Z];
248 qsortbuf[i] = &quadzs[i];
249 }
250 qsort((char *)qsortbuf, nquads2, sizeof(*qsortbuf), zcmp);
251 for (i = 0; i < nquads2; ++i)
252 {
253 SET4(tempquads[i], quads2[qsortbuf[i] - quadzs]);
254 tempquadids[i] = quadids2[qsortbuf[i] - quadzs];
255 tempbrightnesses[i] = brightnesses[qsortbuf[i] - quadzs];
256 }
257 for (i = 0; i < nquads2; ++i)
258 {
259 SET4(quads2[i], tempquads[i]);
260 quadids2[i] = tempquadids[i];
261 brightnesses[i] = tempbrightnesses[i];
262 }
263 }
264
265 if (cullverts)
266 {
267 /*
268 * FIX THIS-- should discard unused vertices here if we are
269 * planning to store the frame in a file or something.
270 */
271 }
272
273
274 *Nverts2 = nverts2;
275 *Nquads2 = nquads2;
276 }
277
278
getTwistTotalAngle(int dim,int dir)279 real PolygonManager4D::getTwistTotalAngle(int dim, int dir)
280 {
281 switch (dim)
282 {
283 case 0: /* vertex; 120 degrees */
284 return 2 * PI / 3 * dir;
285 break;
286 case 1: /* edge; 180 degrees */
287 return 2 * PI / 2 * dir;
288 break;
289 case 2: /* face; 90 degrees */
290 return 2 * PI / 4 * dir;
291 break;
292 default:
293 assert(INRANGE(0 <=, dim, <2));
294 break;
295 }
296 return 2 * PI; /* this never happens */
297 }
298
getTwistNFrames(struct stickerspec * grip)299 int PolygonManager4D::getTwistNFrames(struct stickerspec *grip)
300 {
301 switch (grip->dim)
302 {
303 case 0: /* vertex; 120 degrees */
304 return nframes_120;
305 break;
306 case 1: /* edge; 180 degrees */
307 return nframes_180;
308 break;
309 case 2: /* face; 90 degrees */
310 return nframes_90;
311 break;
312 default:
313 assert(INRANGE(0 <=, grip->dim, <2));
314 break;
315 }
316 return nframes_90; /* this never happens */
317 }
318
319
320 /*
321 * This procedure is hopelessly confusing, but it works.
322 * Note there are two functions here that are almost identical.
323 */
makeRangesReal(int slicesmask,int,int sgn,real ranges[MAXLENGTH][2])324 int PolygonManager4D::makeRangesReal(int slicesmask, int, // whichaxis,
325 int sgn, real ranges[MAXLENGTH][2])
326 {
327 int i, nranges;
328 real temp;
329
330 nranges = 0;
331 for (i = 0; i < length; ++i)
332 {
333 if (BIT(&slicesmask, i))
334 {
335 if (i == 0 || !BIT(&slicesmask, i - 1))
336 ranges[nranges++][0] = (length - 2 * i) * faceshrink;
337 ranges[nranges - 1][1] = (length - 2 * (i + 1)) * faceshrink;
338 }
339 }
340 if (BIT(&slicesmask, 0))
341 ranges[0][0] += 2 * length; /* bigger than any vertex */
342 if (BIT(&slicesmask, length - 1))
343 ranges[nranges - 1][1] -= 2 * length; /* smaller than any vertex */
344
345 if (sgn > 0) /* then the ranges are right but in the wrong
346 order */
347 for (i = 0; i < nranges; ++i)
348 {
349 SWAP(ranges[i][0], ranges[nranges - 1 - i][1], temp);
350 }
351 else /* the signs of the ranges are wrong */
352 for (i = 0; i < nranges; ++i)
353 VXS2(ranges[i], ranges[i], -1);
354
355 return nranges;
356 }
357
makeRangesInt(int slicesmask,int,int sgn,int ranges[MAXLENGTH][2])358 int PolygonManager4D::makeRangesInt(int slicesmask, int, // whichaxis,
359 int sgn, int ranges[MAXLENGTH][2])
360 {
361 int i, nranges;
362 int temp;
363
364 nranges = 0;
365 for (i = 0; i < length; ++i)
366 {
367 if (BIT(&slicesmask, i))
368 {
369 #if sgi
370 /* work around N32 compiler optimizer problem */
371 if (length < 0)
372 printf("foo\n");
373 #endif
374 if (i == 0 || !BIT(&slicesmask, i - 1))
375 ranges[nranges++][0] = (length - 2 * i);
376 ranges[nranges - 1][1] = (length - 2 * (i + 1));
377 }
378 }
379 if (BIT(&slicesmask, 0))
380 ranges[0][0] += 2 * length; /* bigger than any vertex */
381 if (BIT(&slicesmask, length - 1))
382 ranges[nranges - 1][1] -= 2 * length; /* smaller than any vertex */
383
384 if (sgn > 0) /* then the ranges are right but in the wrong
385 order */
386 for (i = 0; i < nranges; ++i)
387 {
388 SWAP(ranges[i][0], ranges[nranges - 1 - i][1], temp);
389 }
390 else /* the signs of the ranges are wrong */
391 for (i = 0; i < nranges; ++i)
392 VXS2(ranges[i], ranges[i], -1);
393
394 return nranges;
395 }
396
397 /*
398 * The following is pretty arbitrary... there might be a more natural way.
399 */
400 /* the iris doesn't seem to like the following being chars */
401 int facetoaxis[8] = { W, Z, Y, X, X, Y, Z, W };
402 int facetosign[8] = { -1, -1, -1, -1, 1, 1, 1, 1 };
403 int axis_and_sign_to_face[4][2] = { {3, 4}, {2, 5}, {1, 6}, {0, 7} };
404
405 #define FACETOAXIS(f) facetoaxis[f]
406 #define FACETOSIGN(f) facetosign[f]
407 #define AXIS_AND_SIGN_TO_FACE(a,s) axis_and_sign_to_face[a][((s)+1)/2]
408
oppositeFace(int f)409 int PolygonManager4D::oppositeFace(int f)
410 {
411 return NFACES - 1 - f;
412 }
413
faceOfGrip(int id)414 int PolygonManager4D::faceOfGrip(int id)
415 {
416 struct stickerspec grip;
417 grip.id_within_cube = id;
418 PolygonManager4D::fillStickerspecFromIdAndLength(&grip, 3);
419 return grip.face;
420 }
421
fillStickerspecFromIdAndLength(struct stickerspec * sticker,int length)422 void PolygonManager4D::fillStickerspecFromIdAndLength(struct stickerspec *sticker,
423 int length)
424 {
425 int i, ax, sgn, id, face0coords[4], mat[4][4];
426 sticker->id_within_face =
427 sticker->id_within_cube % intpow(length, NDIMS - 1);
428 sticker->face = sticker->id_within_cube / intpow(length, NDIMS - 1);
429 ax = FACETOAXIS(sticker->face);
430 sgn = FACETOSIGN(sticker->face);
431 Math4d::getCanonicalMatThatTakesAxisToMinusW(ax, sgn, mat);
432 TRANSPOSE4i(mat, mat); /* want to go in the opposite direction */
433 id = sticker->id_within_face;
434 face0coords[X] = -(length - 1) + 2 * (id % length);
435 face0coords[Y] = -(length - 1) + 2 * ((id / length) % length);
436
437 face0coords[Z] = -(length - 1) + 2 * ((id / length / length) % length);
438 face0coords[W] = -length;
439 VXM4(sticker->coords, face0coords, mat);
440 assert(sticker->coords[ax] == sgn * length);
441
442 /* sticker->depth = 0; */
443 sticker->dim = NDIMS - 1;
444 for (i = 0; i < NDIMS; ++i)
445 {
446 if (ABS(sticker->coords[i]) == length - 1)
447 sticker->dim--;
448 /* sticker->depth = MAX(sticker->depth,
449 length-1-ABS(sticker->coords[i])); */
450 }
451 }
452
fillStickerspecFromId(struct stickerspec * sticker)453 void PolygonManager4D::fillStickerspecFromId(struct stickerspec *sticker)
454 {
455 fillStickerspecFromIdAndLength(sticker, length);
456 }
457
fillStickerspecFromFaceAndIdAndLength(struct stickerspec * sticker,int length)458 void PolygonManager4D::fillStickerspecFromFaceAndIdAndLength(struct stickerspec
459 *sticker, int length)
460 {
461 int face = sticker->face;
462 int id_within_face = sticker->id_within_face;
463 sticker->id_within_cube =
464 face * length * length * length + id_within_face;
465 fillStickerspecFromIdAndLength(sticker, length);
466 assert(sticker->face == face);
467 assert(sticker->id_within_face == id_within_face);
468 }
469
fillStickerspecFromFaceAndId(struct stickerspec * sticker)470 void PolygonManager4D::fillStickerspecFromFaceAndId(struct stickerspec *sticker)
471 {
472 fillStickerspecFromFaceAndIdAndLength(sticker, length);
473 }
474
fillStickerspecFromCoordsAndLength(struct stickerspec * sticker,int length)475 void PolygonManager4D::fillStickerspecFromCoordsAndLength(struct stickerspec *sticker,
476 int length)
477 {
478 int i, ax = 0, sgn, mat[4][4], newcoords[4];
479
480 sticker->dim = NDIMS - 1;
481 /* sticker->depth = 0; */
482 for (i = 0; i < NDIMS; ++i)
483 {
484 if (ABS(sticker->coords[i]) == length)
485 ax = i;
486 else if (ABS(sticker->coords[i]) == length - 1)
487 sticker->dim--;
488 /* sticker->depth = MAX(sticker->depth,
489 length-1-ABS(sticker->coords[i])); */
490 }
491 assert(INRANGE(X <=, ax, <=W));
492 sgn = SGN(sticker->coords[ax]);
493 sticker->face = AXIS_AND_SIGN_TO_FACE(ax, sgn);
494 Math4d::getCanonicalMatThatTakesAxisToMinusW(ax, sgn, mat);
495 VXM4(newcoords, sticker->coords, mat);
496 assert(newcoords[W] == -length);
497
498 sticker->id_within_face = 0;
499 for (i = NDIMS - 2; i >= 0; --i)
500 {
501 sticker->id_within_face *= length;
502 sticker->id_within_face += (newcoords[i] + length - 1) / 2;
503 }
504 assert(INRANGE
505 (0 <=, sticker->id_within_face, <intpow(length, NDIMS - 1)));
506 sticker->id_within_cube =
507 sticker->face * intpow(length, NDIMS - 1) + sticker->id_within_face;
508 }
509
fillStickerspecFromCoords(struct stickerspec * sticker)510 void PolygonManager4D::fillStickerspecFromCoords(struct stickerspec *sticker)
511 {
512 fillStickerspecFromCoordsAndLength(sticker, length);
513 }
514
515
516 /*
517 * Get a sticker for which a CCW twist is the same transformation
518 * as the given face-to-center rotation.
519 * returns 1 if legal rot, 0 otherwise.
520 */
facetocenterToGrip(int facetocenter,struct stickerspec * sticker)521 int PolygonManager4D::facetocenterToGrip(int facetocenter, struct stickerspec *sticker)
522 {
523 int ax = FACETOAXIS(facetocenter);
524 int sgn = FACETOSIGN(facetocenter);
525 if (!INRANGE(X <=, ax, <=Z))
526 return 0;
527
528 sticker->coords[ax] = 0;
529 sticker->coords[(ax + 1) % 3] = 3; /* axis of face on which sticker lies
530 */
531 sticker->coords[(ax + 2) % 3] = sgn * -(3 - 1); /* it's magic */
532 sticker->coords[W] = 0;
533
534 fillStickerspecFromCoordsAndLength(sticker, 3);
535
536 return 1;
537 }
538
calc2DFrameInfo(struct stickerspec * sticker,int dir,int slicesmask,real frac,real (* interp)(real),int nverts4,real untwisted_verts4[][4],real eyew,int cullcells,real tilt,real twirl,real eyez,real sunvec[3],int sunvec_is_in_objspace,int cullverts,int cullbackfaces,int zsort,int * Nverts2,real verts2[][2],int * Nquads2,int quads2[][4],int quadids[],real brightnesses[])539 void PolygonManager4D::calc2DFrameInfo(
540 /* INPUTS */
541 struct stickerspec *sticker, int dir,
542 int slicesmask, real frac, real(*interp) (real),
543 int nverts4, real untwisted_verts4[][4],
544 real eyew, int cullcells, real tilt, real twirl,
545 real eyez, real sunvec[3],
546 int sunvec_is_in_objspace, int cullverts,
547 int cullbackfaces, int zsort,
548 /* OUTPUTS */
549 int *Nverts2, real verts2[][2], int *Nquads2,
550 int quads2[][4], int quadids[],
551 real brightnesses[]) /* brightnesses not
552 calculated if NULL */
553 {
554 int nverts3, nquads3;
555 real verts3[MAXVERTS][3];
556 int quads3[MAXQUADS][4];
557 int stickerids3[MAXSTICKERS];
558
559 if (slicesmask)
560 calc3DFrameInfo(sticker, dir, slicesmask, frac, interp,
561 nverts4, untwisted_verts4, eyew, cullcells,
562 &nverts3, verts3, &nquads3, quads3,
563 stickerids3, NULL);
564 else
565 {
566 int i;
567 /* FIX THIS-- this copying shouldn't be necessary */
568 nverts3 = n_untwisted_verts3;
569 for (i = 0; i < nverts3; ++i)
570 SET3(verts3[i], untwisted_verts3[i]);
571 for (i = 0; i < nverts3 / 8; ++i)
572 stickerids3[i] = untwisted_stickerids3[i];
573 nquads3 = n_untwisted_quads3;
574 for (i = 0; i < nquads3; ++i)
575 SET4(quads3[i], untwisted_quads3[i]);
576 }
577
578 calc3DTo2DFrameInfo(nverts3, verts3, nquads3, quads3, stickerids3,
579 tilt, twirl, eyez,
580 sunvec, sunvec_is_in_objspace,
581 cullverts, cullbackfaces, zsort,
582 Nverts2, verts2, Nquads2, quads2, quadids,
583 brightnesses);
584 }
585
586 /*
587 * "grip" is equal to the sticker id
588 * if length=3; otherwise
589 * it's equal to the stickerid on the 3x3x3x3 puzzle
590 * that corresponds to the twist.
591 * returns 1 if landed on a sticker, 0 otherwise.
592 * NOTE: this is mostly the same as pick().
593 */
pickGrip(int x,int y,struct frame * frame,struct stickerspec * sticker)594 int PolygonManager4D::pickGrip(int x, int y,
595 struct frame *frame, struct stickerspec *sticker)
596 {
597 int checking_bbox = !preferences.getBoolProperty(M4D_DONT_CHECK_BBOX);
598 unsigned short (*verts)[2] = frame->verts;
599 unsigned short (*quads)[4] = frame->quads;
600 int i, j;
601 unsigned short thispoint[2];
602 thispoint[0] = x;
603 thispoint[1] = y;
604
605 for (i = frame->nquads - 1; i >= 0; --i)
606 {
607
608 if (checking_bbox)
609 {
610 for (j = 0; j < 4; ++j)
611 if (x <= verts[quads[i][j]][0])
612 break;
613 if (j == 4)
614 continue;
615
616 for (j = 0; j < 4; ++j)
617 if (x >= verts[quads[i][j]][0])
618 break;
619 if (j == 4)
620 continue;
621
622 for (j = 0; j < 4; ++j)
623 if (y <= verts[quads[i][j]][1])
624 break;
625 if (j == 4)
626 continue;
627
628 for (j = 0; j < 4; ++j)
629 if (y >= verts[quads[i][j]][1])
630 break;
631 if (j == 4)
632 continue;
633 }
634
635
636 for (j = 0; j < 4; ++j)
637 if (!ushort_are_CCW(verts[quads[i][j]],
638 verts[quads[i][(j + 1) % 4]], thispoint))
639 break;
640 if (j == 4)
641 { /* they were all CCW, so we hit a quad */
642
643 sticker->id_within_cube = frame->quadids[i] / 6;
644 fillStickerspecFromId(sticker);
645
646 if (length == 2)
647 {
648 int ax, sgn, face0coords[4], M[4][4];
649 ax = frame->quadids[i] % 3;
650 sgn = (frame->quadids[i] % 6) < 3 ? -1 : 1;
651
652 /* invent a nonexistent sticker at the appropriate axis */
653 face0coords[ax] = sgn * (length - 1);
654 face0coords[(ax + 1) % 3] = 0;
655 face0coords[(ax + 2) % 3] = 0;
656 face0coords[3] = -length;
657 Math4d::getCanonicalMatThatTakesAxisToMinusW(
658 FACETOAXIS(sticker->face), FACETOSIGN(sticker->face), M);
659 /* apply inv of that matrix to face0coords */
660 MXV4(sticker->coords, M, face0coords);
661 sticker->dim = 2;
662 }
663
664 /*
665 * Now we know the coordinates of the sticker.
666 * "Straighten it out" to the coords of the appropriate grip.
667 * I.e. change everything < length-1 to 0,
668 * change length-1 to 2 and change length to 3.
669 */
670 for(j=0; j<4; ++j)
671 {
672 if (ABS(sticker->coords[j]) < length - 1)
673 sticker->coords[j] = 0;
674 else
675 sticker->coords[j] = SGN(sticker->coords[j]) *
676 (ABS(sticker->coords[j]) - length + 3);
677 }
678 fillStickerspecFromCoordsAndLength(sticker, 3);
679
680 return 1;
681 }
682 }
683 return 0;
684 }
685
pick(int x,int y,struct frame * frame,struct stickerspec * sticker)686 int PolygonManager4D::pick(int x, int y, struct frame *frame, struct stickerspec *sticker)
687 {
688 int checking_bbox = !preferences.getBoolProperty(M4D_DONT_CHECK_BBOX);
689 unsigned short (*verts)[2] = frame->verts;
690 unsigned short (*quads)[4] = frame->quads;
691 int i, j;
692 unsigned short thispoint[2];
693 thispoint[0] = x;
694 thispoint[1] = y;
695
696 for (i = frame->nquads - 1; i >= 0; --i)
697 {
698
699 if (checking_bbox)
700 {
701 for (j = 0; j < 4; ++j)
702 if (x <= verts[quads[i][j]][0])
703 break;
704 if (j == 4)
705 continue;
706
707 for (j = 0; j < 4; ++j)
708 if (x >= verts[quads[i][j]][0])
709 break;
710 if (j == 4)
711 continue;
712
713 for (j = 0; j < 4; ++j)
714 if (y <= verts[quads[i][j]][1])
715 break;
716 if (j == 4)
717 continue;
718
719 for (j = 0; j < 4; ++j)
720 if (y >= verts[quads[i][j]][1])
721 break;
722 if (j == 4)
723 continue;
724 }
725
726
727 for (j = 0; j < 4; ++j)
728 if (!ushort_are_CCW(verts[quads[i][j]],
729 verts[quads[i][(j + 1) % 4]], thispoint))
730 break;
731 if (j == 4)
732 { /* they were all CCW, so we hit a quad */
733
734 sticker->id_within_cube = frame->quadids[i] / 6;
735 fillStickerspecFromId(sticker);
736
737 return 1;
738 }
739 }
740 return 0;
741 }
742
getUntwistedFrame(struct frame * frame)743 void PolygonManager4D::getUntwistedFrame(struct frame *frame)
744 {
745 struct stickerspec sticker;
746 sticker.id_within_cube = 0;
747 fillStickerspecFromId(&sticker);
748 getFrame(&sticker, CCW, 0, 0, 1, frame);
749 }
750
getFrame(struct stickerspec * sticker,int dir,int slicesmask,int seqno,int outof,struct frame * frame)751 void PolygonManager4D::getFrame(struct stickerspec *sticker,
752 int dir, int slicesmask, int seqno, int outof,
753 struct frame *frame)
754 {
755 /*
756 * The frame calculation routines use different types from the
757 * struct frame, so we must translate
758 */
759 int nverts, nquads;
760 real verts[MAXVERTS][2];
761 int quads[MAXQUADS][4];
762 int quadids[MAXQUADS];
763 real brightnesses[MAXQUADS];
764 int i;
765 static real sunvec[3] = { .82, 1.55, 3.3 }; /* FIX THIS--- figure out where
766 to put it */
767
768 calc2DFrameInfo(sticker, dir, slicesmask, (real) seqno / outof,
769 sine_interp,
770 n_untwisted_verts4, untwisted_verts4,
771 preferences.getRealProperty(M4D_EYEW, EYEW),
772 !preferences.getBoolProperty(M4D_NOCULLCELLS), /* cullcells */
773 tilt,
774 twirl,
775 preferences.getRealProperty(M4D_EYEZ, EYEZ),
776 sunvec, 0, /* sunvec_is_in_objspace */
777 preferences.getBoolProperty(M4D_CULLVERTS), /* cullverts */
778 !preferences.getBoolProperty(M4D_NOCULLFACES), /* cullbackfaces */
779 !preferences.getBoolProperty(M4D_NOZSORT), /* zsort */
780 &nverts, verts, &nquads, quads,
781 quadids, brightnesses);
782
783 frame->nverts = nverts;
784 if (!bbox[0][0])
785 {
786 /*
787 * It is assumed that the first time this function is called,
788 * it is with the untwisted frame. The bounding box
789 * of this frame is the one that will always be used.
790 */
791 real ctr[2], rad;
792 ZEROMAT2(bbox);
793 for (i = 0; i < nverts; ++i)
794 {
795 bbox[0][0] = MIN(bbox[0][0], verts[i][0]);
796 bbox[0][1] = MIN(bbox[0][1], verts[i][1]);
797 bbox[1][0] = MAX(bbox[1][0], verts[i][0]);
798 bbox[1][1] = MAX(bbox[1][1], verts[i][1]);
799 }
800 LERP2(ctr, bbox[0], bbox[1], .5);
801 rad = MAX(bbox[1][0] - ctr[0], bbox[1][1] - ctr[1]);
802 /* make bbox a square twice or so as big as it was */
803 bbox[0][0] = ctr[0] - 1.2 * rad;
804 bbox[0][1] = ctr[1] - 1.2 * rad;
805 bbox[1][0] = ctr[0] + 1.2 * rad;
806 bbox[1][1] = ctr[1] + 1.2 * rad;
807 }
808 for (i = 0; i < nverts; ++i)
809 {
810 frame->verts[i][0] =
811 (unsigned short)((verts[i][0] - bbox[0][0]) /
812 (bbox[1][0] - bbox[0][0]) * ((1 << 16) - 1));
813 frame->verts[i][1] =
814 (unsigned short)((bbox[1][1] - verts[i][1]) /
815 (bbox[1][1] - bbox[0][1]) * ((1 << 16) - 1));
816 }
817 frame->nquads = nquads;
818 for (i = 0; i < nquads; ++i)
819 {
820 SET4(frame->quads[i], quads[i]);
821 frame->quadids[i] = quadids[i];
822 frame->brightnesses[i] = brightnesses[i];
823 }
824 }
825
826
calc3DFrameInfo(struct stickerspec * grip,int dir,int slicesmask,real frac,real (* interp)(real),int nverts4,real uv4[][4],real eyew,int cullcells,int * Nverts3,real verts3[][3],int * Nquads3,int quads3[][4],int stickerids3[],int stickers_inverted[])827 void PolygonManager4D::calc3DFrameInfo(
828 /* INPUTS */
829 struct stickerspec *grip, int dir,
830 int slicesmask, real frac, real(*interp) (real),
831 int nverts4, real uv4[][4], real eyew,
832 int cullcells,
833 /* OUTPUTS */
834 int *Nverts3, real verts3[][3],
835 int *Nquads3, int quads3[][4],
836 int stickerids3[], int stickers_inverted[])
837 {
838 int i, j, k;
839 int whichax = 0, sgn;
840 real total_angle;
841 real center[4], real_stickercoords[4], mat[4][4];
842 int nranges = 0;
843 real ranges[MAXLENGTH][2];
844 real toverts4[MAXVERTS][4];
845 int nverts3, nquads3;
846 real tomultiplyby, orientationmat[3][3];
847 /*
848 * NOTE: Don't change the order here.
849 * the miserable little hack in polymgr_pick_grip
850 * depends on the assumption that cubequads[i] is on axis i%3
851 * in direction (i<3 ? -1 : 1).
852 */
853 static int cubequads[6][4] = {
854 {0, 4, 6, 2},
855 {0, 1, 5, 4},
856 {0, 2, 3, 1},
857 {7, 5, 1, 3},
858 {7, 3, 2, 6},
859 {7, 6, 4, 5},
860 };
861
862 if (0 == nverts4 || NULL == uv4)
863 {
864 nverts4 = n_untwisted_verts4;
865 uv4 = untwisted_verts4;
866 }
867
868
869 if (slicesmask)
870 {
871 /*
872 * Calculate rotation center; it's the center of the face containing
873 * the grip
874 */
875 whichax = -1;
876 for (i = 0; i < NDIMS; ++i)
877 {
878 if (ABS(grip->coords[i]) == 3)
879 {
880 center[i] = grip->coords[i];
881 whichax = i;
882 }
883 else
884 center[i] = 0;
885 }
886 assert(INRANGE(0 <=, whichax, <NDIMS));
887
888 total_angle = getTwistTotalAngle(grip->dim, dir);
889 SET4(real_stickercoords, grip->coords);
890
891 Math4d::get4dRotMatrix(center, real_stickercoords,
892 interp(frac) * total_angle, mat);
893 sgn = SGN(center[whichax]);
894 nranges = makeRangesReal(slicesmask, whichax, sgn, ranges);
895 }
896
897 /*
898 * Transform the vertices
899 */
900 nverts3 = 0;
901 for (i = 0; i < nverts4; ++i)
902 {
903 if (i % 8 == 0)
904 stickerids3[nverts3 / 8] = i / 8;
905 if (slicesmask)
906 {
907 /*
908 * Transform the vertex in 4-space
909 */
910 for (j = 0; j < nranges; ++j)
911 {
912 if (INRANGE(ranges[j][0] <=, untwisted_verts4[i][whichax],
913 <=ranges[j][1]))
914 {
915 VXM4(toverts4[i], untwisted_verts4[i], mat);
916 break;
917 }
918 }
919 if (j == nranges)
920 SET4(toverts4[i], untwisted_verts4[i]);
921 }
922 else
923 {
924 SET4(toverts4[i], untwisted_verts4[i]);
925 }
926
927 /*
928 * W-divide to get 3d coords
929 */
930 tomultiplyby = 1 / (eyew - toverts4[i][3]);
931 VXS3(verts3[nverts3], toverts4[i], tomultiplyby);
932 nverts3++;
933 if ((cullcells || stickers_inverted) && i % 8 == 4)
934 {
935 int is_inverted;
936 /* got enough verts to determine whether to cull */
937 j = (nverts3 / 8) * 8; /* round down to start of sticker */
938 VMV3(orientationmat[0], verts3[j + 1], verts3[j]);
939 VMV3(orientationmat[1], verts3[j + 2], verts3[j]);
940 VMV3(orientationmat[2], verts3[j + 4], verts3[j]);
941 is_inverted = DET3(orientationmat) <= 0;
942 if (stickers_inverted)
943 stickers_inverted[i / 8] = is_inverted;
944 if (cullcells && is_inverted)
945 {
946 i = ROUNDUP(i, 8) - 1; /* skip rest of this sticker's verts */
947 nverts3 = j;
948 }
949 }
950 }
951
952 /*
953 * Now we have nverts3 and verts3;
954 * set quads.
955 */
956 nquads3 = 0;
957 for (i = 0; i < nverts3 / 8; ++i) // for each sticker
958 for (j = 0; j < 6; ++j)
959 { // for each sticker face
960 for (k = 0; k < 4; ++k) // for each face vertex
961 quads3[nquads3][k] = 8 * i + cubequads[j][k];
962 nquads3++;
963 }
964
965 *Nverts3 = nverts3;
966 *Nquads3 = nquads3;
967 }
968
getUntwistedVerts4(real verts4[][4],real faceshrink,real stickershrink)969 int PolygonManager4D::getUntwistedVerts4(real verts4[][4],
970 real faceshrink, real stickershrink)
971 {
972 real sticker_centers_3d[MAXLENGTH][MAXLENGTH][MAXLENGTH][NDIMS - 1];
973 real face0verts[MAXLENGTH][MAXLENGTH][MAXLENGTH][2][2][2][NDIMS];
974 int i, j, k, ii, jj, kk, f;
975 int mat[4][4];
976 int nverts4;
977
978 for (k = 0; k < length; ++k)
979 for (j = 0; j < length; ++j)
980 for (i = 0; i < length; ++i)
981 {
982 sticker_centers_3d[i][j][k][X] = -length + 2 * i + 1;
983 sticker_centers_3d[i][j][k][Y] = -length + 2 * j + 1;
984 sticker_centers_3d[i][j][k][Z] = -length + 2 * k + 1;
985 for (kk = 0; kk < 2; ++kk)
986 for (jj = 0; jj < 2; ++jj)
987 for (ii = 0; ii < 2; ++ii)
988 {
989 face0verts[i][j][k][ii][jj][kk][X] =
990 -length + 2 * (i + ii);
991 face0verts[i][j][k][ii][jj][kk][Y] =
992 -length + 2 * (j + jj);
993 face0verts[i][j][k][ii][jj][kk][Z] =
994 -length + 2 * (k + kk);
995 face0verts[i][j][k][ii][jj][kk][W] = -length;
996
997 LERP3(face0verts[i][j][k][ii][jj][kk],
998 sticker_centers_3d[i][j][k],
999 face0verts[i][j][k][ii][jj][kk],
1000 stickershrink);
1001 VXS3(face0verts[i][j][k][ii][jj][kk],
1002 face0verts[i][j][k][ii][jj][kk], faceshrink);
1003 }
1004 }
1005
1006 nverts4 = 0;
1007 for (f = 0; f < NFACES; ++f)
1008 {
1009 Math4d::getCanonicalMatThatTakesAxisToMinusW(
1010 FACETOAXIS(f), FACETOSIGN(f), mat);
1011 for (k = 0; k < length; ++k)
1012 for (j = 0; j < length; ++j)
1013 for (i = 0; i < length; ++i)
1014 for (kk = 0; kk < 2; ++kk)
1015 for (jj = 0; jj < 2; ++jj)
1016 for (ii = 0; ii < 2; ++ii)
1017 {
1018 assert(nverts4 < MAXVERTS);
1019 /*
1020 * want to take -W to the axis, so we apply the inverse,
1021 * i.e. apply the transpose, i.e. multiply by the matrix on
1022 * the left
1023 */
1024 MXV4(verts4[nverts4], mat,
1025 face0verts[i][j][k][ii][jj][kk]);
1026 nverts4++;
1027 }
1028 }
1029 return nverts4;
1030 }
1031
1032
incTilt(real inc)1033 void PolygonManager4D::incTilt(real inc)
1034 {
1035 tilt += inc;
1036 /* restrict to range [-pi/2, pi/2] */
1037 if (tilt > PI / 2)
1038 tilt = PI / 2;
1039 if (tilt < -PI / 2)
1040 tilt = -PI / 2;
1041 // printf("Tilt = %g degrees\n", RTOD(tilt));
1042 }
1043
incTwirl(real inc)1044 void PolygonManager4D::incTwirl(real inc)
1045 {
1046 twirl += inc;
1047 // printf("Twirl = %g degrees\n", RTOD(twirl));
1048 }
1049
1050 // Local Variables:
1051 // c-basic-offset: 4
1052 // c-comment-only-line-offset: 0
1053 // c-file-offsets: ((defun-block-intro . +) (block-open . 0) (substatement-open . 0) (statement-cont . +) (statement-case-open . +4) (arglist-intro . +) (arglist-close . +) (inline-open . 0))
1054 // indent-tabs-mode: nil
1055 // End:
1056