1: /// <summary>
2: /// A Bezier Object represented by a set of BezierPatch objects, each containing 16 control points
3: /// </summary>
4: public class BezierObject : BaseObject
5: {
6: /// <summary>
7: /// The minimum division size to recurse to
8: /// </summary>
9: private static double DIV_SIZE = 0.005;
10:
11: /// <summary>
12: /// A Bezier Patch, made up of 16 control points
13: /// </summary>
14: public class BezierPatch
15: {
16: /// <summary>
17: /// The 4x4 array of control points
18: /// </summary>
19: public Vector[,] idx = new Vector[4,4];
20: /// <summary>
21: /// A public indexer to the array of control points
22: /// </summary>
23: public Vector this[int i, int j]
24: {
25: get
26: {
27: return idx[i,j];
28: }
29: set
30: {
31: idx[i,j] = value;
32: }
33: }
34: /// <summary>
35: /// A linear indexer to the array of control points
36: /// </summary>
37: public Vector this[int i]
38: {
39: get
40: {
41: return this[i >> 2, i & 0x3];
42: }
43: set
44: {
45: this[i >> 2, i & 0x3] = value;
46: }
47: }
48:
49: /// <summary>
50: /// Creates a copy of this bezier patch
51: /// </summary>
52: /// <returns>A clone of this patch</returns>
53: public BezierPatch Clone()
54: {
55: BezierPatch ret = new BezierPatch();
56: for (int i = 0; i < 4; i++)
57: for (int j = 0; j < 4; j++)
58: ret.idx[i,j] = idx[i,j];
59: return ret;
60: }
61:
62: /// <summary>
63: /// Evaluates the Bezier Patch at the specified location
64: /// </summary>
65: /// <param name="s">The s parameter, from 0 to 1</param>
66: /// <param name="t">The t parameter, from 0 to 1</param>
67: /// <returns>A Vector containing the 3D world space location of the desired point</returns>
68: public Vector Evaluate(double s, double t)
69: {
70: // Copy our vectors into a temporary array
71: Vector[,] tmp = new Vector[4,4];
72: for (int i = 0; i < 4; i++)
73: for (int j = 0; j < 4; j++)
74: tmp[i,j] = this[i,j];
75:
76: // Take our 16 points, condense them into 9 points
77: // Condense the 9 points into 4
78: // Condense the 4 points into 1
79: for (int size = 3; size > 0; size--)
80: for (int i = 0; i < size; i++)
81: for (int j = 0; j < size; j++)
82: {
83: // Replace the Pij with the average of the 3 'next' points
84: // i,j+1 - i+1,j+1
85: // | |
86: // | |
87: // i,j ---- i+1,j
88: // First bisect along the top and bottom lines
89: Vector vi1 = tmp[i+1,j] - tmp[i,j];
90: Vector vi2 = tmp[i+1,j+1] - tmp[i,j+1];
91: // Then bisect through the line connecting those two points
92: Vector itemp1 = tmp[i,j] + vi1 * t;
93: Vector itemp2 = tmp[i,j+1] + vi2 * t;
94: Vector vj = itemp2 - itemp1;
95: tmp[i,j] = itemp1 + vj * s;
96: }
97:
98: // After that loop, tmp[0,0] will contain the requested point
99: return tmp[0,0];
100: }
101:
102: /// <summary>
103: /// Splits this Bezier Patch in the t direction
104: /// </summary>
105: /// <param name="t">The 't' parameter to split at, from 0 to 1</param>
106: /// <param name="a">Will contain the first half of the split</param>
107: /// <param name="b">Will contain the second half of the split</param>
108: public void Split_t(double t, out BezierPatch a, out BezierPatch b)
109: {
110: // Check for degenerate case
111: if (t < 0.0 || t > 1.0)
112: {
113: a = b = null;
114: return;
115: }
116:
117: a = new BezierPatch();
118: b = new BezierPatch();
119:
120: // We're going to be splitting this bezier patch into two pieces,
121: // effectively doubling the number of 'i' values
122:
123: // Treat each row of 4 points as a single bezier curve
124: for (int j = 0; j < 4; j++)
125: {
126: // For each row, calculate the new points
127: Vector i1_1 = this[0,j] + t * (this[1,j] - this[0,j]);
128: Vector i1_2 = this[1,j] + t * (this[2,j] - this[1,j]);
129: Vector i1_3 = this[2,j] + t * (this[3,j] - this[2,j]);
130: Vector i2_1 = i1_1 + t * (i1_2 - i1_1);
131: Vector i2_2 = i1_2 + t * (i1_3 - i1_2);
132: Vector i3_1 = i2_1 + t * (i2_2 - i2_1);
133: // Points idx[0,j], i1_1, i2_1, and i3_1 make up curve A
134: a.idx[0,j] = this[0,j];
135: a.idx[1,j] = i1_1;
136: a.idx[2,j] = i2_1;
137: a.idx[3,j] = i3_1;
138: // Points i3_1, i2_2, i1_3, and idx[3,j] make up curve B
139: b.idx[0,j] = i3_1;
140: b.idx[1,j] = i2_2;
141: b.idx[2,j] = i1_3;
142: b.idx[3,j] = this[3,j];
143: }
144: // Once all four curves are split, we're done
145: }
146:
147: /// <summary>
148: /// Splits this Bezier Patch in the s direction
149: /// </summary>
150: /// <param name="s">The 's' parameter to split at, from 0 to 1</param>
151: /// <param name="a">Will contain the first half of the split</param>
152: /// <param name="b">Will contain the second half of the split</param>
153: public void Split_s(double s, out BezierPatch a, out BezierPatch b)
154: {
155: if (s < 0.0 || s > 1.0)
156: {
157: a = b = null;
158: return;
159: }
160:
161: a = new BezierPatch();
162: b = new BezierPatch();
163:
164: // We're going to be splitting this bezier patch into two pieces,
165: // effectively doubling the number of 'j' values
166:
167: // Treat each row of 4 points as a single bezier curve
168: for (int i = 0; i < 4; i++)
169: {
170: // For each row, calculate the new points
171: Vector j1_1 = this[i,0] + s * (this[i,1] - this[i,0]);
172: Vector j1_2 = this[i,1] + s * (this[i,2] - this[i,1]);
173: Vector j1_3 = this[i,2] + s * (this[i,3] - this[i,2]);
174: Vector j2_1 = j1_1 + s * (j1_2 - j1_1);
175: Vector j2_2 = j1_2 + s * (j1_3 - j1_2);
176: Vector j3_1 = j2_1 + s * (j2_2 - j2_1);
177: // Points this[i,0], j1_1, j2_1, and j3_1 make up curve A
178: a.idx[i,0] = this[i,0];
179: a.idx[i,1] = j1_1;
180: a.idx[i,2] = j2_1;
181: a.idx[i,3] = j3_1;
182: // Points j3_1, j2_2, j1_3, and this[i,3] make up curve B
183: b.idx[i,0] = j3_1;
184: b.idx[i,1] = j2_2;
185: b.idx[i,2] = j1_3;
186: b.idx[i,3] = this[i,3];
187: }
188: // Once all four curves are split, we're done
189: }
190:
191: /// <summary>
192: /// Clips this bezier patch in the t direction
193: /// </summary>
194: /// <param name="t0">The first location to split at</param>
195: /// <param name="t1">The second location to split at</param>
196: /// <param name="a">The Bezier Patch representing the original Bezier Patch from parameter t0 to t1</param>
197: public void Clip_t(double t0, double t1, out BezierPatch a)
198: {
199: BezierPatch split_trash, split_a;
200: // First split at t0
201: Split_t(t0, out split_trash, out split_a);
202: // split_trash contains the bezier curve from 0 to t0, so we can ignore it
203: // split_a contains the curve from t0 to 1, so split it at the location
204: // where t1 would be on that curve
205: double t1n = (t1 - t0)/(1.0 - t0);
206: // Keep the first part (t0 to t1), and throw out the second (t1 to 1)
207: split_a.Split_t(t1n, out a, out split_trash);
208: // Voila!
209: }
210:
211: /// <summary>
212: /// Clips this bezier patch in the s direction
213: /// </summary>
214: /// <param name="s0">The first location to split at</param>
215: /// <param name="s1">The second location to split at</param>
216: /// <param name="a">The Bezier Patch representing the original Bezier Patch from parameter s0 to s1</param>
217: public void Clip_s(double s0, double s1, out BezierPatch a)
218: {
219: BezierPatch split_trash, split_a;
220: // First split at s0
221: Split_s(s0, out split_trash, out split_a);
222: // split_trash contains the bezier curve from 0 to s0, so we can ignore it
223: // split_a contains the curve from s0 to 1, so split it at the location
224: // where s1 would be on that curve
225: double s1n = (s1 - s0)/(1.0 - s0);
226: // Keep the first part (s0 to s1), and throw out the second (s1 to 1)
227: split_a.Split_s(s1n, out a, out split_trash);
228: // Voila!
229: }
230:
231: /// <summary>
232: /// Creates a Hit object that intersects a given ray
233: /// </summary>
234: /// <param name="r">A Ray to intersect with this object</param>
235: /// <returns>The correct Hit object for the given ray</returns>
236: private Hit GenerateHit(Ray r)
237: {
238: Hit h = new Hit();
239: Vector ploc = Evaluate(0.5,0.5);
240: double dist = Vector.Length(ploc - r.o);
241: if (Vector.Dot(ploc - r.o, r.d) < 0)
242: dist = -dist;
243: h.n = Vector.Unitize(Vector.Cross(this[3,0] - this[0,0],this[0,3] - this[0,0]));
244: h.r = r;
245: if (Vector.Dot(h.n, r.d) > 0)
246: h.n = -1 * h.n;
247: h.t = dist;
248: h.x = r.o + r.d * dist;
249: return h;
250: }
251:
252: /// <summary>
253: /// Called by the scene to determine whether a given ray intersects this Bezier Patch
254: /// </summary>
255: /// <param name="r">The Ray to test for intersection</param>
256: /// <param name="divSize">The minimum size to recurse down to</param>
257: /// <param name="depth">The current depth of recursion</param>
258: /// <param name="dir">The direction to split in, 0 == t, 1 == s</param>
259: /// <returns>A new Hit object if the Ray intersects this patch, null if it does not</returns>
260: public Hit Intersect(Ray r, double divSize, int depth, int dir)
261: {
262: // ---------------------
263: // 1. Convert ray into intersection of two planes
264: Plane xp = new Plane();
265: xp.p = r.o + r.d;
266: xp.n = Vector.Unitize(Vector.Cross(new Vector(0,1,0),r.d));
267: Plane yp = new Plane();
268: yp.p = r.o + r.d;
269: yp.n = Vector.Unitize(Vector.Cross(r.d,xp.n));
270: // ---------------------
271: // 2. Flatten bezier patch onto these two new axes
272: bool transpose = false;
273: if (dir == 1)
274: transpose = true;
275:
276: double i_dist = Vector.Length(this[3,0] - this[0,0]);
277: double j_dist = Vector.Length(this[0,3] - this[0,0]);
278:
279: double[,,] Dij = new double[4,4,2];
280: for (int i = 0; i < 4; i++)
281: {
282: for (int j = 0; j < 4; j++)
283: {
284: // If we're going to split along the 's' direction, then
285: // transpose the control points of Dij
286: if (transpose)
287: {
288: Dij[i,j,0] = xp.Dist(this[j,i]);
289: Dij[i,j,1] = yp.Dist(this[j,i]);
290: }
291: else
292: {
293: Dij[i,j,0] = xp.Dist(this[i,j]);
294: Dij[i,j,1] = yp.Dist(this[i,j]);
295: }
296: }
297: }
298: // ---------------------
299: // 3. Choose a direction to split on, create a line through that direction,
300: // roughly parallel to the control points
301: Vector Di1 = new Vector(Dij[3,0,0],Dij[3,0,1],0) - new Vector(Dij[0,0,0],Dij[0,0,1],0);
302: Vector Di2 = new Vector(Dij[3,3,0],Dij[3,3,1],0) - new Vector(Dij[0,3,0],Dij[0,3,1],0);
303: Vector Di = Vector.Unitize(Di1 + Di2);
304: // Check for degenerate cases
305: if (Di[0] == 0.0 && Di[1] == 0.0)
306: {
307: Di = Di1;
308: }
309: Vector l = Vector.Cross(Di,new Vector(0,0,1));
310: // ---------------------
311: // 4. Create a height map based on distance from that line
312: double[,,] dij = new double[4,4,2];
313: for (int i = 0; i < 4; i++)
314: {
315: for (int j = 0; j < 4; j++)
316: {
317: dij[i,j,0] = i / 3.0;
318: dij[i,j,1] = l[0] * Dij[i,j,0] + l[1] * Dij[i,j,1];
319: }
320: }
321:
322: // Check whether the points actually cross the axis
323: bool pos = false;
324: bool changed = false;
325: if (dij[0,0,1] >= 0.0)
326: pos = true;
327: for (int i = 0; i < 4; i++)
328: {
329: for (int j = 0; j < 4; j++)
330: {
331: if (dij[i,j,1] >= 0.0 && !pos)
332: changed = true;
333: if (dij[i,j,1] < 0.0 && pos)
334: changed = true;
335: }
336: }
337: // If they don't, then the ray doesn't hit this patch
338: if (!changed)
339: return null;
340:
341: // Check to see if we're done yet
342: if (i_dist <= divSize && j_dist <= divSize)
343: return GenerateHit(r);
344:
345: // Check whether the currently selected axis is already small enough
346: // If so, recurse in the other direction
347: if (i_dist < divSize && !transpose)
348: return Intersect(r, divSize, depth + 1, (transpose ? 0 : 1));
349: else if (j_dist < divSize && transpose)
350: return Intersect(r, divSize, depth + 1, (transpose ? 0 : 1));
351:
352: // ---------------------
353: // 5. Find the convex hull of the height map
354:
355: // We only need the lowest and highest values at each interval
356: double[,,] bounds = new double[4,2,2];
357: for (int i = 0; i < 4; i++)
358: {
359: double minval = double.MaxValue;
360: double maxval = double.MinValue;
361: bounds[i,0,0] = dij[i,0,0];
362: bounds[i,1,0] = dij[i,0,0];
363: for (int j = 0; j < 4; j++)
364: {
365: if (dij[i,j,1] < minval)
366: minval = dij[i,j,1];
367: if (dij[i,j,1] > maxval)
368: maxval = dij[i,j,1];
369: }
370: bounds[i,0,1] = minval;
371: bounds[i,1,1] = maxval;
372: }
373:
374: // Determine location where the convex hull passes 'sea-level'
375: double min_hull = double.MaxValue;
376: double max_hull = double.MinValue;
377: bool success = false;
378: for (int a_i = 0; a_i < 4; a_i++)
379: for (int a_j = 0; a_j < 2; a_j++)
380: for (int b_i = 0; b_i < 4; b_i++)
381: for (int b_j = 0; b_j < 2; b_j++)
382: {
383: double t;
384: if (HitsAxis(bounds[a_i,a_j,0], bounds[a_i,a_j,1], bounds[b_i,b_j,0], bounds[b_i,b_j,1], out t))
385: {
386: if (t < min_hull)
387: min_hull = t;
388: if (t > max_hull)
389: max_hull = t;
390: success = true;
391: }
392: }
393:
394: if (!success)
395: return null;
396:
397: // ---------------------
398: // 6-8. Check for max - min > 0.8, subdivide, or clip the bezier patch and recurse
399:
400: // If our hull contains more than 80% of the axis line...
401: if (max_hull - min_hull > 0.8)
402: {
403: // .. Split the bezier patch and call on each half
404: BezierPatch a, b, temp;
405: if (transpose)
406: {
407: Clip_s(min_hull, max_hull, out temp);
408: Split_s(0.5, out a, out b);
409: }
410: else
411: {
412: Clip_t(min_hull, max_hull, out temp);
413: Split_t(0.5, out a, out b);
414: }
415: Hit ha = a.Intersect(r, divSize, depth + 1, (transpose ? 0 : 1));
416: Hit hb = b.Intersect(r, divSize, depth + 1, (transpose ? 0 : 1));
417: if (ha != null && hb != null)
418: {
419: if (ha.t <= hb.t)
420: {
421: ha.next = hb;
422: return ha;
423: }
424: else
425: {
426: hb.next = ha;
427: return hb;
428: }
429: }
430: else if (ha != null)
431: return ha;
432: else if (hb != null)
433: return hb;
434: else
435: return null;
436: }
437: else
438: {
439: // Otherwise, just clip the bezier patch
440: BezierPatch nbp;
441: if (transpose)
442: Clip_s(min_hull,max_hull,out nbp);
443: else
444: Clip_t(min_hull,max_hull,out nbp);
445: return nbp.Intersect(r,divSize,depth + 1,(transpose ? 0 : 1));
446: }
447: }
448: }
449:
450: /// <summary>
451: /// A private method which tests whether a line from (x1,y1) to (x2,y2) crosses the y axis
452: /// </summary>
453: /// <param name="x1">The x parameter of the first point</param>
454: /// <param name="y1">The y parameter of the first point</param>
455: /// <param name="x2">The x parameter of the second point</param>
456: /// <param name="y2">The y parameter of the second point</param>
457: /// <param name="i">The x value at which this line would pass the y axis</param>
458: /// <returns>True if this line actually crosses the y axis somewhere between x1 and x2</returns>
459: private static bool HitsAxis(double x1, double y1, double x2, double y2, out double i)
460: {
461: i = 0;
462:
463: double inv_m = (x2 - x1) / (y2 - y1);
464: if (double.IsNaN(inv_m) || double.IsInfinity(inv_m))
465: {
466: // There's no rise, so this cannot cross the axis
467: return false;
468: }
469: if (inv_m == 0.0)
470: {
471: if (y1 < 0.0 && y2 < 0.0)
472: return false;
473: if (y2 > 0.0 && y2 > 0.0)
474: return false;
475: }
476:
477: i = (-y1) * inv_m + x1;
478: if (x1 < x2)
479: {
480: if (i < x1)
481: return false;
482: if (i > x2)
483: return false;
484: }
485: else
486: {
487: if (i > x1)
488: return false;
489: if (i < x2)
490: return false;
491: }
492:
493: return true;
494: }
495:
496: /// <summary>
497: /// The list of patches which make up this Bezier Object
498: /// </summary>
499: public System.Collections.ArrayList patchList;
500:
501: /// <summary>
502: /// Loads a Bezier Object from a .bez file
503: /// </summary>
504: /// <param name="fs">An input stream to an open .bez file</param>
505: /// <returns>A new BezierObject if successful, null otherwise</returns>
506: public static BezierObject FromFile(System.IO.FileStream fs)
507: {
508: if (fs == null || !fs.CanRead)
509: return null;
510:
511: BezierObject ret = new BezierObject();
512: System.Collections.ArrayList pointList = new System.Collections.ArrayList();
513: ret.patchList = new System.Collections.ArrayList();
514:
515: // Loop through the scene file and parse each line
516: String line;
517: while ((line = Util.GetLine(fs)) != null)
518: {
519: // Break the string up into tokens
520: line = Regex.Replace(line,@"((^[\s\t]+)|([s\t]+$))","");
521: String[] mc = Regex.Split(line,@"[\s\t]+");
522:
523: if (mc.Length == 4) // 4 numbers == control point
524: {
525: Vector newPoint = new Vector(Double.Parse(mc[1]),Double.Parse(mc[2]),Double.Parse(mc[3]));
526: pointList.Add(newPoint);
527: }
528: else if (mc.Length == 16) // 16 numbers == patch
529: {
530: BezierPatch newPatch = new BezierPatch();
531: newPatch[0] = (Vector)pointList[(-Int16.Parse(mc[0])) - 1];
532: for (int i = 1; i < 16; i++)
533: newPatch[i] = (Vector)pointList[(Int16.Parse(mc[i]) - 1)];
534: ret.patchList.Add(newPatch);
535: }
536: }
537:
538: return ret;
539: }
540:
541: /// <summary>
542: /// Converts a Bezier Object to triangles, and inserts these triangles into a given Scene
543: /// </summary>
544: /// <param name="scn">The Scene to insert the triangles into</param>
545: /// <param name="divisions">How many times to subdivide the Bezier Patch</param>
546: /// <remarks>
547: /// This should probably not be used, except for testing purposes, as rendering the Bezier Patch
548: /// directly is much faster and produces a much cleaner image.
549: /// </remarks>
550: public void ConvToTriangles(Scene scn, int divisions)
551: {
552: // Converts each patch to triangles and adds them to the scene
553: for (int i = 0; i < patchList.Count; i++)
554: {
555: BezierPatch bp = (BezierPatch)patchList[i];
556:
557: double div_size = 1.0 / (double)divisions;
558:
559: for (int s_i = 0; s_i < divisions; s_i++)
560: for (int t_i = 0; t_i < divisions; t_i++)
561: {
562: Double s = s_i * div_size;
563: Double t = t_i * div_size;
564:
565: // Evaluate the bezierpatch at four points to create triangles
566: Vector va = bp.Evaluate(s,t);
567: Vector vb = bp.Evaluate(s + div_size, t);
568: Vector vc = bp.Evaluate(s + div_size, t + div_size);
569: Vector vd = bp.Evaluate(s, t + div_size);
570: TriangleObject t1 = new TriangleObject(va,vd,vb);
571: TriangleObject t2 = new TriangleObject(vb,vd,vc);
572: t1.mat = t2.mat = mat;
573: scn.AddObject(t1);
574: scn.AddObject(t2);
575: }
576: }
577: }
578:
579: /// <summary>
580: /// The material for this BezierObject
581: /// </summary>
582: public BaseMaterial mat;
583:
584: /// <summary>
585: /// A necessary function to return the material at a given point
586: /// </summary>
587: /// <param name="x">The location to get a material at</param>
588: /// <returns>This object's material</returns>
589: public override BaseMaterial GetMaterialAt(Vector x)
590: {
591: return mat;
592: }
593: /// <summary>
594: /// Since it's impossible to say whether one is inside or outside of a Bezier Patch, this always returns false
595: /// </summary>
596: /// <param name="v">Location to test</param>
597: /// <returns>False</returns>
598: public override bool IsIn(Vector v)
599: {
600: return false;
601: }
602:
603: /// <summary>
604: /// A simple helper class to represent a Plane
605: /// </summary>
606: private class Plane
607: {
608: /// <summary>
609: /// A point on the plane
610: /// </summary>
611: public Vector p;
612: /// <summary>
613: /// The normal of the plane
614: /// </summary>
615: public Vector n;
616:
617: /// <summary>
618: /// Distance from a point to this plane
619: /// </summary>
620: /// <param name="x">A point</param>
621: /// <returns>The distance from 'x' to this plane</returns>
622: public double Dist(Vector x)
623: {
624: return Vector.Dot(n,x - p);
625: }
626: }
627:
628: /// <summary>
629: /// Tests for an intersection between a given Ray and this Bezier Object
630: /// </summary>
631: /// <param name="r">The Ray to test</param>
632: /// <returns>The closest hit out of all of the patches in this object</returns>
633: public override Hit Intersect(Ray r)
634: {
635: Hit closest = null;
636: // Find the closest hit out of all of the bezier patches in this object
637: for (int patchnum = 0; patchnum < patchList.Count; patchnum++)
638: {
639: BezierPatch bp = ((BezierPatch)patchList[patchnum]);
640: Hit h = bp.Intersect(r,DIV_SIZE,0,0);
641: if (h != null)
642: {
643: Hit ch = h;
644: while (ch != null)
645: {
646: if (ch.t > 0)
647: {
648: ch.obj = this;
649: if (closest == null)
650: closest = ch;
651: else if (ch.t < closest.t)
652: closest = ch;
653: }
654: ch = ch.next;
655: }
656: }
657: }
658: return closest;
659: }
660: }