| blob | 10833cc731534e46665975ec45d0c10a193a5350 |
1 // Copyright 2003, 2004, 2005, 2006 David Hilvert <dhilvert@auricle.dyndns.org>,
2 // <dhilvert@ugcs.caltech.edu>
4 /* This file is part of the Anti-Lamenessing Engine.
6 The Anti-Lamenessing Engine is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 The Anti-Lamenessing Engine 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.
16 You should have received a copy of the GNU General Public License
17 along with the Anti-Lamenessing Engine; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
21 /*
22 * d3/scene.h: Representation of a 3D scene.
23 */
25 #ifndef __scene_h__
26 #define __scene_h__
30 /*
31 * View angle multiplier.
32 *
33 * Setting this to a value larger than one can be useful for debugging.
34 */
36 #define VIEW_ANGLE_MULTIPLIER 1
40 /*
41 * Clipping planes
42 */
46 /*
47 * Decimation exponents for geometry
48 */
53 /*
54 * Output clipping
55 */
58 /*
59 * Model files
60 */
64 /*
65 * Occupancy attenuation
66 */
70 /*
71 * Normalization of output by weight
72 */
76 /*
77 * Filtering data
78 */
83 /*
84 * Falloff exponent
85 */
89 /*
90 * Third-camera error multiplier
91 */
94 /*
95 * Occupancy update iterations
96 */
99 /*
100 * Pairwise ambiguity
101 */
104 /*
105 * Pairwise comparisons
106 */
109 /*
110 * 3D Post-exclusion
111 */
115 /*
116 * Nearness threshold
117 */
120 /*
121 * Encounter threshold for defined pixels.
122 */
125 /*
126 * Median calculation radii.
127 */
131 /*
132 * Flag for subspace traversal.
133 */
136 /*
137 * Structure to hold input frame information at levels of
138 * detail between full detail and full decimation.
139 */
147 /*
148 * Constructor
149 */
152 pt _pt;
172 }
173 }
175 /*
176 * Get the number of scales
177 */
180 }
182 /*
183 * Get an image.
184 */
188 }
192 }
194 /*
195 * Get a 'trilinear' color. We currently don't do interpolation
196 * between levels of detail; hence, it's discontinuous in tl_coord.
197 */
222 }
247 }
249 /*
250 * Get the transformation
251 */
256 }
258 /*
259 * Get the camera origin in world coordinates
260 */
263 }
265 /*
266 * Destructor
267 */
271 }
272 }
273 };
275 /*
276 * Structure to hold weight information for reference images.
277 */
281 pt transformation;
291 }
303 }
307 /*
308 * Explicit weight subtree
309 */
311 ale_real node_value;
320 }
326 }
327 };
329 /*
330 * Constructor
331 */
336 }
338 /*
339 * Check spatial bounds.
340 */
358 }
363 }
365 /*
366 * Increase resolution to the given level.
367 */
374 /*
375 * Check for the cases known to have no lower level of detail.
376 */
386 /*
387 * Load the lower-level image structure.
388 */
396 /*
397 * Check for the case where no lower level of detail is
398 * available.
399 */
404 /*
405 * Spread out the lower level of detail among (uninitialized)
406 * peer values.
407 */
416 }
418 /*
419 * Set the lower level of detail to point here.
420 */
423 }
425 /*
426 * Add weights to positive higher-resolution pixels where
427 * found when their current values match the given subtree
428 * values; set negative pixels to zero and return 0 if no
429 * positive higher-resolution pixels are found.
430 */
438 }
443 /*
444 * Check for positive values.
445 */
452 }
454 /*
455 * Handle the case where there are no higher levels of detail.
456 */
462 }
465 }
467 /*
468 * Handle the case where higher levels of detail are available.
469 */
484 }
496 }
501 }
503 /*
504 * Add weight.
505 */
513 // fprintf(stderr, "[aw tc=%d i=%d j=%d imax=%d jmax=%d]\n",
514 // tc, i, j, im->height(), im->width());
519 /*
520 * Increase resolution, if necessary
521 */
525 /*
526 * Attempt to add the weight at levels of detail
527 * where weight is defined.
528 */
533 /*
534 * If no weights are defined at any level of detail,
535 * then set the weight here.
536 */
539 }
551 }
566 /*
567 * Establish a reasonable (?) upper bound on resolution.
568 */
573 }
575 /*
576 * Initialize, if necessary.
577 */
587 }
589 /*
590 * Check resolution bounds
591 */
595 /*
596 * Generate additional levels of detail, if necessary.
597 */
600 tc_low--;
605 }
608 tc_high++;
613 }
616 }
618 /*
619 * Get weight
620 */
623 // fprintf(stderr, "[gw tc=%d i=%u j=%u tclow=%d tchigh=%d]\n",
624 // tc, i, j, tc_low, tc_high);
634 }
654 }
662 }
665 }
675 }
689 }
692 }
694 /*
695 * Check whether a subtree is simple.
696 */
708 }
710 /*
711 * Get a weight subtree.
712 */
715 /*
716 * tc > tc_high is handled recursively.
717 */
729 }
732 }
739 /*
740 * Rectangular images will, in general, have
741 * out-of-bounds tree sections. Handle this case.
742 */
749 /*
750 * -1 weights are handled recursively
751 */
764 }
767 }
769 /*
770 * Zero weights have NULL subtrees.
771 */
776 /*
777 * Handle the remaining case.
778 */
781 }
790 }
809 }
811 /*
812 * Destructor
813 */
817 }
818 }
819 };
821 /*
822 * Resolution check.
823 */
834 }
836 /*
837 * Structure to hold input frame information at all levels of detail.
838 */
841 /*
842 * All images.
843 */
851 }
855 }
862 }
867 }
872 }
878 }
883 }
887 }
888 };
890 /*
891 * All levels-of-detail
892 */
896 /*
897 * Data structure for storing best encountered subspace candidates.
898 */
905 /*
906 * Point p is in world coordinates.
907 */
910 // fprintf(stderr, "[gs iw=%f %f %f d=%f]\n",
911 // iw[0], iw[1], iw[2], diagonal);
918 }
923 /*
924 * Loop until resolutions of interest have been generated.
925 */
933 /*
934 * Generate any new desired spatial registers.
935 */
937 /*
938 * Inputs
939 */
943 /*
944 * Low resolution
945 */
952 }
954 }
956 /*
957 * High resolution.
958 */
965 }
967 }
968 }
970 /*
971 * Check for completion
972 */
977 /*
978 * Check precision before analyzing space further.
979 */
985 }
989 total_tsteps++;
992 total_tsteps++;
997 }
998 }
999 }
1008 /*
1009 * Is this necessary?
1010 */
1018 }
1019 }
1021 /*
1022 * Point p is expected to be in local projective coordinates.
1023 */
1041 &(levels[tc - input_decimation_lower][i * swidth * pairwise_ambiguity + j * pairwise_ambiguity + k]);
1060 }
1061 }
1063 /*
1064 * Generate subspaces for candidates.
1065 */
1086 }
1091 // fprintf(stderr, "[gss l=%d i=%d j=%d d=%g]\n", l, i, j, pk->first);
1097 }
1098 }
1099 }
1100 };
1102 /*
1103 * List for calculating weighted median.
1104 */
1113 }
1118 }
1124 else
1136 }
1137 }
1145 }
1150 used++;
1151 }
1157 }
1161 }
1168 }
1172 }
1179 }
1185 }
1186 }
1190 }
1192 /*
1193 * Finds the median at half-weight, or between half-weight
1194 * and zero-weight, depending on the attenuation value.
1195 */
1211 // if (weight_sum == 0)
1212 // return undefined;
1222 }
1237 }
1238 }
1241 }
1245 // if (initial_size == 0) {
1246 // initial_size = (int) (d2::image_rw::count() * 1.5);
1247 // }
1257 }
1258 }
1260 /*
1261 * copy constructor. This is required to avoid undesired frees.
1262 */
1271 }
1275 }
1276 };
1278 /*
1279 * Class for information regarding spatial regions of interest.
1280 *
1281 * This class is configured for convenience in cases where sampling is
1282 * performed using an approximation of the fine:box:1,triangle:2 chain.
1283 * In this case, the *_1 variables would store the fine data and the
1284 * *_2 variables would store the coarse data. Other uses are also
1285 * possible.
1286 */
1289 /*
1290 * Map channel value --> weight.
1291 */
1295 /*
1296 * Current color.
1297 */
1300 /*
1301 * Map occupancy value --> weight.
1302 */
1303 wml occupancy_weights_1;
1304 wml occupancy_weights_2;
1306 /*
1307 * Current occupancy value.
1308 */
1309 ale_real occupancy;
1311 /*
1312 * pocc/socc density
1313 */
1318 /*
1319 * Insert a weight into a list.
1320 */
1323 }
1325 /*
1326 * Find the median of a weighted list. Uses NaN for undefined.
1327 */
1330 }
1333 /*
1334 * Constructor.
1335 */
1341 }
1343 /*
1344 * Accumulate color; primary data set.
1345 */
1349 }
1351 /*
1352 * Accumulate color; secondary data set.
1353 */
1357 }
1359 /*
1360 * Accumulate occupancy; primary data set.
1361 */
1364 }
1366 /*
1367 * Accumulate occupancy; secondary data set.
1368 */
1375 // fprintf(stderr, "%p updated socc with: %f %f\n", this, occupancy, weight);
1376 // occupancy_weights_2.print_info();
1377 }
1379 /*
1380 * Update color (and clear accumulation structures).
1381 */
1394 }
1395 }
1397 /*
1398 * Update occupancy (and clear accumulation structures).
1399 */
1415 }
1417 /*
1418 * Get current color.
1419 */
1422 }
1424 /*
1425 * Get current occupancy.
1426 */
1430 }
1432 /*
1433 * Get primary color density.
1434 */
1438 }
1442 }
1443 };
1445 /*
1446 * Map spatial regions of interest to spatial info structures. XXX:
1447 * This may get very poor cache behavior in comparison with, say, an
1448 * array. Unfortunately, there is no immediately obvious array
1449 * representation. If some kind of array representation were adopted,
1450 * it would probably cluster regions of similar depth from the
1451 * perspective of the typical camera. In particular, for a
1452 * stereoscopic view, depth ordering for two random points tends to be
1453 * similar between cameras, I think. Unfortunately, it is never
1454 * identical for all points (unless cameras are co-located). One
1455 * possible approach would be to order based on, say, camera 0's idea
1456 * of depth.
1457 */
1459 #if !defined(HASH_MAP_GNU) && !defined(HASH_MAP_STD)
1461 #elif defined(HASH_MAP_GNU)
1462 struct node_hash
1463 {
1465 {
1467 }
1468 };
1469 typedef __gnu_cxx::hash_map<struct space::node *, spatial_info, node_hash > spatial_info_map_t;
1470 #elif defined(HASH_MAP_STD)
1472 #endif
1478 /*
1479 * Debugging variables.
1480 */
1487 /*
1488 * Member functions
1489 */
1493 }
1497 }
1501 }
1505 }
1509 }
1513 }
1517 }
1521 }
1525 }
1529 }
1533 }
1537 }
1539 /*
1540 * Initialize 3D scene from 2D scene, using 2D and 3D alignment
1541 * information.
1542 */
1545 /*
1546 * Rear clip value of 0 is converted to infinity.
1547 */
1555 }
1557 /*
1558 * Scale and translate clipping plane depths.
1559 */
1566 /*
1567 * Allocate image structures.
1568 */
1574 }
1575 }
1577 /*
1578 * Perform spatial_info updating on a given subspace, for given
1579 * parameters.
1580 */
1587 /*
1588 * Reject out-of-bounds spaces.
1589 */
1593 }
1595 /*
1596 * Skip spaces with no color information.
1597 *
1598 * XXX: This could be more efficient, perhaps.
1599 */
1604 }
1609 /*
1610 * Get in-bounds centroid, if one exists.
1611 */
1618 }
1620 /*
1621 * Get information on the subspace.
1622 */
1628 /*
1629 * Store current weight so we can later check for
1630 * modification by higher-resolution subspaces.
1631 */
1635 /*
1636 * Check for higher resolution subspaces, and
1637 * update the space iterator.
1638 */
1643 /*
1644 * Cleave space for the higher-resolution pass,
1645 * skipping the current space, since we will
1646 * process that later.
1647 */
1657 }
1659 /*
1660 * Add new data on the subspace and update weights.
1661 */
1673 }
1675 /*
1676 * Determine the probability of encounter.
1677 */
1681 /*
1682 * Update weights
1683 */
1687 /*
1688 * Delete the subtree, if necessary.
1689 */
1693 /*
1694 * Check for cases in which the subspace should not be
1695 * updated.
1696 */
1704 /*
1705 * Update subspace.
1706 */
1719 }
1720 }
1722 /*
1723 * Run a single iteration of the spatial_info update cycle.
1724 */
1726 /*
1727 * Iterate through each frame.
1728 */
1733 /*
1734 * Open the frame and transformation.
1735 */
1740 /*
1741 * Allocate weights data structure for storing encounter
1742 * probabilities.
1743 */
1747 /*
1748 * Call subspace_info_update for the root space.
1749 */
1753 /*
1754 * Free weights.
1755 */
1759 /*
1760 * Close the frame and transformation.
1761 */
1765 }
1767 /*
1768 * Update all spatial_info structures.
1769 */
1770 for (spatial_info_map_t::iterator i = spatial_info_map.begin(); i != spatial_info_map.end(); i++) {
1774 // d2::pixel color = i->second.get_color();
1776 // fprintf(stderr, "space p=%p updated to c=[%f %f %f] o=%f\n",
1777 // i->first, color[0], color[1], color[2],
1778 // i->second.get_occupancy());
1779 }
1780 }
1782 /*
1783 * Support function for view() and depth(). This function
1784 * always performs exclusion.
1785 */
1787 static const void view_recurse(int type, d2::image *im, d2::image *weights, space::iterate si, pt _pt,
1792 /*
1793 * Remove excluded regions.
1794 */
1799 }
1801 /*
1802 * Prune.
1803 */
1808 }
1810 /*
1811 * XXX: This could be more efficient, perhaps.
1812 */
1817 }
1823 /*
1824 * Get information on the subspace.
1825 */
1828 // d2::pixel color = d2::pixel(1, 1, 1) * (double) (((unsigned int) (st.get_node()) / sizeof(space)) % 65535);
1831 /*
1832 * Determine the view-local bounding box for the
1833 * subspace.
1834 */
1850 }
1865 }
1867 /*
1868 * Data structure to check modification of weights by
1869 * higher-resolution subspaces.
1870 */
1874 /*
1875 * Check for higher resolution subspaces, and
1876 * update the space iterator.
1877 */
1882 /*
1883 * Store information about current weights,
1884 * so we will know which areas have been
1885 * covered by higher-resolution subspaces.
1886 */
1892 /*
1893 * Cleave space for the higher-resolution pass,
1894 * skipping the current space, since we will
1895 * process that afterward.
1896 */
1906 }
1909 /*
1910 * Iterate over pixels in the bounding box, finding
1911 * pixels that intersect the subspace. XXX: assume
1912 * for now that all pixels in the bounding box
1913 * intersect the subspace.
1914 */
1919 /*
1920 * Check for higher-resolution updates.
1921 */
1927 }
1929 }
1931 /*
1932 * Determine the probability of encounter.
1933 */
1939 /*
1940 * Update images.
1941 */
1945 /*
1946 * Color view
1947 */
1956 /*
1957 * Weighted (transparent) depth display
1958 */
1968 /*
1969 * Ambiguity (ambivalence) measure.
1970 */
1978 /*
1979 * Closeness measure.
1980 */
1992 }
1996 /*
1997 * Weighted (transparent) contribution display
1998 */
2011 /*
2012 * Weighted (transparent) occupancy display
2013 */
2023 /*
2024 * (Depth, xres, yres) triple
2025 */
2036 }
2040 /*
2041 * (xoff, yoff, 0) triple
2042 */
2052 }
2056 /*
2057 * Value = 1 for any intersected space.
2058 */
2065 /*
2066 * Number of contributions for the nearest space.
2067 */
2077 }
2078 }
2079 }
2081 /*
2082 * Generate an depth image from a specified view.
2083 */
2095 }
2126 }
2128 /*
2129 * Iterate through subspaces.
2130 */
2144 }
2146 #if 1
2148 #else
2151 #endif
2153 /*
2154 * Normalize depths by weights
2155 */
2166 /*
2167 * Handle interpolation.
2168 */
2179 else
2183 }
2201 }
2202 }
2206 /*
2207 * Handle encounter thresholds
2208 */
2214 }
2215 }
2222 }
2231 }
2234 /*
2235 * This function always performs exclusion.
2236 */
2238 static space::node *most_visible_pointwise(d2::pixel *weight, space::iterate si, pt _pt, d2::point p) {
2245 /*
2246 * Prune certain regions known to be uninteresting.
2247 */
2252 }
2254 /*
2255 * XXX: This could be more efficient, perhaps.
2256 */
2261 }
2265 /*
2266 * Get information on the subspace.
2267 */
2271 /*
2272 * Preserve current weight in order to check for
2273 * modification by higher-resolution subspaces.
2274 */
2278 /*
2279 * Check for higher resolution subspaces, and
2280 * update the space iterator.
2281 */
2286 /*
2287 * Cleave space for the higher-resolution pass,
2288 * skipping the current space, since we will
2289 * process that afterward.
2290 */
2303 }
2306 /*
2307 * Check for higher-resolution updates.
2308 */
2313 /*
2314 * Determine the probability of encounter.
2315 */
2319 /*
2320 * (*weight)[0] stores the cumulative weight; (*weight)[1] stores the maximum.
2321 */
2326 }
2329 }
2332 }
2334 /*
2335 * This function performs exclusion iff SCALED is true.
2336 */
2348 }
2350 /*
2351 * XXX: This could be more efficient, perhaps.
2352 */
2357 }
2361 /*
2362 * Get information on the subspace.
2363 */
2367 /*
2368 * Determine the view-local bounding box for the
2369 * subspace.
2370 */
2379 /*
2380 * Data structure to check modification of weights by
2381 * higher-resolution subspaces.
2382 */
2386 /*
2387 * Check for higher resolution subspaces, and
2388 * update the space iterator.
2389 */
2394 /*
2395 * Store information about current weights,
2396 * so we will know which areas have been
2397 * covered by higher-resolution subspaces.
2398 */
2404 /*
2405 * Cleave space for the higher-resolution pass,
2406 * skipping the current space, since we will
2407 * process that afterward.
2408 */
2418 }
2421 /*
2422 * Iterate over pixels in the bounding box, finding
2423 * pixels that intersect the subspace. XXX: assume
2424 * for now that all pixels in the bounding box
2425 * intersect the subspace.
2426 */
2431 /*
2432 * Check for higher-resolution updates.
2433 */
2439 }
2441 }
2443 /*
2444 * Determine the probability of encounter.
2445 */
2449 /*
2450 * weights[0] stores the cumulative weight; weights[1] stores the maximum.
2451 */
2457 }
2460 }
2461 }
2462 }
2474 }
2486 }
2499 }
2501 /*
2502 * Class to generate focal sample views.
2503 */
2507 /*
2508 * Original projective transformation.
2509 */
2511 pt original_pt;
2513 /*
2514 * Data type for shared view data.
2515 */
2518 pt _pt;
2534 }
2544 }
2552 }
2555 /*
2556 * Iterate through subspaces.
2557 */
2564 }
2574 }
2578 }
2591 }
2596 }
2605 }
2609 }
2614 }
2621 }
2626 }
2631 }
2636 }
2641 }
2656 }
2657 }
2662 }
2672 }
2673 }
2678 }
2684 }
2687 }
2701 }
2702 }
2704 };
2706 /*
2707 * Shared view array, indexed by aperture diameter and view number.
2708 */
2712 /*
2713 * Method to generate a new stochastic focal view.
2714 */
2724 }
2726 /*
2727 * Generate a new view from the given offset.
2728 */
2736 }
2740 /*
2741 * Result type.
2742 */
2746 pt _pt;
2756 }
2757 }
2761 }
2766 }
2771 }
2777 }
2781 }
2787 }
2789 /*
2790 * Determine weight and color for the given point.
2791 */
2805 }
2810 }
2812 void get_median_depth_and_diff(d2::pixel *depth, d2::pixel *diff, unsigned int i, unsigned int j) {
2815 }
2821 }
2823 /*
2824 * Generate a local depth image of required radius.
2825 */
2838 /*
2839 * Find depth and diff at this point, check for
2840 * undefined values, and generate projections
2841 * of the image corners on the estimated normal
2842 * surface.
2843 */
2854 }
2855 };
2862 }
2865 }
2868 }
2872 }
2873 };
2875 /*
2876 * Unfiltered function
2877 */
2887 }
2906 /*
2907 * Data structures for calculating focal statistics.
2908 */
2915 }
2917 /*
2918 * Iterate over views for this focus region.
2919 */
2928 /*
2929 * Map the focused point to the new view.
2930 */
2934 /*
2935 * Determine weight and color for the given point.
2936 */
2952 }
2958 }
2964 else
2966 }
2971 }
2973 /*
2974 * Unfiltered function
2975 */
2988 }
2997 /*
2998 * Use adaptive subspace data.
2999 */
3004 /*
3005 * Iterate through subspaces.
3006 */
3023 }
3030 }
3032 /*
3033 * Filtered function.
3034 */
3039 /*
3040 * Get depth image for focus region determination.
3041 */
3048 /*
3049 * Prepare input frame data.
3050 */
3062 }
3067 /*
3068 * Open all files for rendering.
3069 */
3073 /*
3074 * Prepare data structures for averaging views, as we render
3075 * each view separately. This is spacewise inefficient, but
3076 * is easy to implement given the current operation of the
3077 * renderers.
3078 */
3086 }
3090 /*
3091 * Prepare view generator.
3092 */
3096 /*
3097 * Render views separately. This is spacewise inefficient,
3098 * but is easy to implement given the current operation of the
3099 * renderers.
3100 */
3104 /*
3105 * Generate a new 2D renderer for filtering.
3106 */
3113 /*
3114 * Iterate over output points.
3115 */
3134 /*
3135 * Determine the most-visible subspace.
3136 */
3143 /*
3144 * Get median depth and diff.
3145 */
3158 };
3160 /*
3161 * Iterate over files.
3162 */
3171 /*
3172 * Determine transformation at (i, j). First
3173 * determine transformation from the output to
3174 * the input, then invert this, as we need the
3175 * inverse transformation for filtering.
3176 */
3182 };
3184 /*
3185 * Forward matrix for the linear component of the
3186 * transformation.
3187 */
3192 };
3194 /*
3195 * Inverse matrix for the linear component of
3196 * the transformation. Calculate using the
3197 * determinant D.
3198 */
3209 };
3211 /*
3212 * Determine the projective transformation parameters for the
3213 * inverse transformation.
3214 */
3233 }
3243 /*
3244 * Perform render step for the given frame,
3245 * transformation, and point.
3246 */
3249 }
3250 }
3262 }
3263 }
3265 /*
3266 * Close all files and return the result.
3267 */
3272 }
3281 /*
3282 * Generate a new 2D renderer for filtering.
3283 */
3288 /*
3289 * Get depth image in order to estimate normals (and hence
3290 * transformations).
3291 */
3322 /*
3323 * Check visibility.
3324 */
3331 /*
3332 * Find depth and diff at this point, check for
3333 * undefined values, and generate projections
3334 * of the image corners on the estimated normal
3335 * surface.
3336 */
3340 // d2::pixel diff = d2::pixel(0, 0, 0);
3349 };
3351 /*
3352 * Determine transformation at (i, j). First
3353 * determine transformation from the output to
3354 * the input, then invert this, as we need the
3355 * inverse transformation for filtering.
3356 */
3362 };
3364 /*
3365 * Forward matrix for the linear component of the
3366 * transformation.
3367 */
3372 };
3374 /*
3375 * Inverse matrix for the linear component of
3376 * the transformation. Calculate using the
3377 * determinant D.
3378 */
3389 };
3391 /*
3392 * Determine the projective transformation parameters for the
3393 * inverse transformation.
3394 */
3412 }
3418 /*
3419 * Perform render step for the given frame,
3420 * transformation, and point.
3421 */
3426 }
3430 }
3435 }
3437 /*
3438 * Generic function.
3439 */
3448 }
3449 }
3453 }
3457 }
3461 }
3465 }
3470 }
3474 }
3478 }
3482 }
3486 }
3490 }
3494 }
3498 }
3510 }
3513 }
3515 /*
3516 * This function returns true if a space is completely excluded.
3517 */
3528 }
3531 }
3540 }
3546 /*
3547 * Make pt list.
3548 */
3558 }
3559 }
3561 for (std::map<const char *, pt>::iterator i = d3_depth_pt->begin(); i != d3_depth_pt->end(); i++) {
3563 }
3565 for (std::map<const char *, pt>::iterator i = d3_output_pt->begin(); i != d3_output_pt->end(); i++) {
3567 }
3570 }
3572 /*
3573 * Get a trilinear coordinate for an anisotropic candidate cell.
3574 */
3584 /*
3585 * Determine the view-local extrema in 2 dimensions.
3586 */
3598 }
3599 }
3604 }
3606 /*
3607 * Check whether a cell is visible from a given viewpoint. This function
3608 * is guaranteed to return 1 when a cell is visible, but it is not guaranteed
3609 * to return 0 when a cell is invisible.
3610 */
3620 /*
3621 * Cycle through all vertices of the cell to check certain
3622 * properties.
3623 */
3660 }
3672 }
3674 /*
3675 * Check whether a cell is output-visible.
3676 */
3682 }
3684 /*
3685 * Check whether a cell is input-visible.
3686 */
3689 }
3691 /*
3692 * Return true if a cell fails an output resolution bound.
3693 */
3694 static int fails_output_resolution_bound(point min, point max, const std::vector<pt> &pt_outputs) {
3704 }
3707 }
3709 /*
3710 * Check lower-bound resolution constraints
3711 */
3727 }
3729 /*
3730 * Try the candidate nearest to the specified cell.
3731 */
3732 static void try_nearest_candidate(unsigned int f1, unsigned int f2, candidates *c, point min, point max) {
3737 // fprintf(stderr, "[tnc n=%f %f %f x=%f %f %f]\n", min[0], min[1], min[2], max[0], max[1], max[2]);
3739 /*
3740 * Reject clipping plane violations.
3741 */
3747 /*
3748 * Calculate projections.
3749 */
3758 // fprintf(stderr, ":");
3762 }
3769 tc++;
3770 stc++;
3771 }
3776 /*
3777 * Calculate score from color match. Assume for now
3778 * that the transformation can be approximated locally
3779 * with a translation.
3780 */
3793 }
3807 }
3809 /*
3810 * Include third-camera contributions in the score.
3811 */
3831 score += tc_multiplier
3833 }
3836 }
3838 /*
3839 * Check for cells that are completely clipped.
3840 */
3844 }
3846 /*
3847 * Update extremum variables for cell points mapped to a particular view.
3848 */
3849 static void update_extrema(point min, point max, pt _pt, int *extreme_dim, ale_pos *extreme_ratio) {
3860 /*
3861 * Determine the view-local extrema in all dimensions, and
3862 * determine the vertex of closest z coordinate.
3863 */
3873 }
3877 }
3881 /*
3882 * Update extrema as necessary for each dimension.
3883 */
3894 ale_pos local_distance = (_pt.wp_unscaled(point(cell[p1[0]][0], cell[p1[1]][1], cell[p1[2]][2])).xy()
3900 }
3901 }
3902 }
3904 /*
3905 * Get the next split dimension.
3906 */
3907 static int get_next_split(int f1, int f2, point min, point max, const std::vector<pt> &pt_outputs) {
3920 }
3923 }
3925 /*
3926 * Find candidates for subspace creation.
3927 */
3928 static void find_candidates(unsigned int f1, unsigned int f2, candidates *c, point min, point max,
3941 }
3943 (double) min[0], (double) min[1], (double) min[2], (double) max[0], (double) max[1], (double) max[2]);
3944 }
3950 }
3957 }
3963 }
3970 __LINE__);
3977 }
3981 if (!space::traverse::get_next_cells(get_next_split(f1, f2, min, max, pt_outputs), min, max, new_cells)) {
3985 }
4001 }
4005 }
4007 /*
4008 * Generate a map from scores to 3D points for various depths at point (i, j) in f1, at
4009 * lowest resolution.
4010 */
4011 static score_map p2f_score_map(unsigned int f1, unsigned int f2, unsigned int i, unsigned int j) {
4013 score_map result;
4022 /*
4023 * Get the pixel color in the primary frame
4024 */
4026 // d2::pixel color_primary = if1->get_pixel(i, j);
4028 /*
4029 * Map two depths to the secondary frame.
4030 */
4035 // fprintf(stderr, "%d->%d (%d, %d) point pair: (%d, %d, %d -> %f, %f), (%d, %d, %d -> %f, %f)\n",
4036 // f1, f2, i, j, i, j, 1000, p1[0], p1[1], i, j, -1000, p2[0], p2[1]);
4037 // _pt1.debug_output();
4038 // _pt2.debug_output();
4041 /*
4042 * For cases where the mapped points define a
4043 * line and where points on the line fall
4044 * within the defined area of the frame,
4045 * determine the starting point for inspection.
4046 * In other cases, continue to the next pixel.
4047 */
4058 }
4060 /*
4061 * Make absurdly large/small slopes either infinity, negative infinity, or zero.
4062 */
4072 }
4074 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4081 // fprintf(stderr, "slope == %f\n", slope);
4085 // fprintf(stderr, "case 0\n");
4089 // fprintf(stderr, "case 1\n");
4093 // fprintf(stderr, "case 2\n");
4097 // fprintf(stderr, "case 3\n");
4101 // fprintf(stderr, "case 4\n");
4102 // fprintf(stderr, "%d->%d (%d, %d) does not intersect the defined area\n",
4103 // f1, f2, i, j);
4105 }
4108 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4110 /*
4111 * Determine increment values for examining
4112 * point, ensuring that incr_i is always
4113 * positive.
4114 */
4127 }
4129 // fprintf(stderr, "%d->%d (%d, %d) increments are (%f, %f)\n",
4130 // f1, f2, i, j, incr_i, incr_j);
4132 /*
4133 * Examine regions near the projected line.
4134 */
4140 // fprintf(stderr, "%d->%d (%d, %d) checking (%f, %f)\n",
4141 // f1, f2, i, j, ii, jj);
4143 #if 0
4144 /*
4145 * Check for higher, lower, and nearby points.
4146 *
4147 * Red = 2^0
4148 * Green = 2^1
4149 * Blue = 2^2
4150 */
4167 }
4168 }
4170 /*
4171 * If this is not a region of interest,
4172 * then continue.
4173 */
4178 // if (((higher & lower) | nearby) != 0x7)
4179 // continue;
4180 #endif
4181 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4183 // fprintf(stderr, "%d->%d (%d, %d) accepted (%f, %f)\n",
4184 // f1, f2, i, j, ii, jj);
4186 /*
4187 * Create an orthonormal basis to
4188 * determine line intersection.
4189 */
4196 // fprintf(stderr, "(%d, %d, 0) transformed to world and back is: (%f, %f, %f)\n",
4197 // i, j, foo[0], foo[1], foo[2]);
4200 // fprintf(stderr, "(%d, %d, 10) transformed to world and back is: (%f, %f, %f)\n",
4201 // i, j, foo[0], foo[1], foo[2]);
4211 /*
4212 * Select a fourth point to define a second line.
4213 */
4217 /*
4218 * Representation in the new basis.
4219 */
4222 // d2::point nbp1 = d2::point(bp1.dproduct(b0), bp1.dproduct(b1));
4226 /*
4227 * Determine intersection of line
4228 * (nbp0, nbp1), which is parallel to
4229 * b0, with line (nbp2, np3).
4230 */
4232 /*
4233 * XXX: a stronger check would be
4234 * better here, e.g., involving the
4235 * ratio (np3[0] - nbp2[0]) / (np3[1] -
4236 * nbp2[1]). Also, acceptance of these
4237 * cases is probably better than
4238 * rejection.
4239 */
4242 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4248 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4256 /*
4257 * Map the intersection back to the world
4258 * basis.
4259 */
4263 /*
4264 * Reject intersection points behind a
4265 * camera.
4266 */
4272 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4278 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4280 /*
4281 * Reject clipping plane violations.
4282 */
4285 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4292 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4294 /*
4295 * Score the point.
4296 */
4304 /*
4305 * Calculate score from color match. Assume for now
4306 * that the transformation can be approximated locally
4307 * with a translation.
4308 */
4321 }
4324 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4337 score += l1_multiplier
4340 }
4342 /*
4343 * Include third-camera contributions in the score.
4344 */
4363 score += tc_multiplier
4365 }
4370 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4372 /*
4373 * Reject points with undefined score.
4374 */
4377 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4383 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4385 #if 0
4386 /*
4387 * XXX: reject points not on the z=-27.882252 plane.
4388 */
4391 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4395 #endif
4398 // fprintf(stderr, "score map (%u, %u) line %u\n", i, j, __LINE__);
4400 /*
4401 * Add the point to the score map.
4402 */
4404 // d2::pixel c_ip = if1->in_bounds(ip.xy()) ? if1->get_bl(ip.xy())
4405 // : d2::pixel();
4406 // d2::pixel c_is = if2->in_bounds(is.xy()) ? if2->get_bl(is.xy())
4407 // : d2::pixel();
4409 // fprintf(stderr, "Candidate subspace: f1=%u f2=%u i=%u j=%u ii=%f jj=%f"
4410 // "cp=[%f %f %f] cs=[%f %f %f]\n",
4411 // f1, f2, i, j, ii, jj, c_ip[0], c_ip[1], c_ip[2],
4412 // c_is[0], c_is[1], c_is[2]);
4415 }
4417 // fprintf(stderr, "Iterating through the score map:\n");
4418 //
4419 // for (score_map::iterator smi = result.begin(); smi != result.end(); smi++) {
4420 // fprintf(stderr, "%f ", smi->first);
4421 // }
4422 //
4423 // fprintf(stderr, "\n");
4426 }
4429 /*
4430 * Attempt to refine space around a point, to high and low resolutions
4431 * resulting in two resolutions in total.
4432 */
4441 }
4445 /*
4446 * Loop until all resolutions of interest have been generated.
4447 */
4459 }
4461 /*
4462 * Generate any new desired spatial registers.
4463 */
4467 /*
4468 * Low resolution
4469 */
4476 }
4478 }
4480 /*
4481 * High resolution.
4482 */
4488 }
4490 }
4491 }
4493 /*
4494 * Check precision before analyzing space further.
4495 */
4501 }
4505 total_tsteps++;
4508 total_tsteps++;
4513 }
4514 }
4515 }
4517 /*
4518 * Calculate target dimension
4519 */
4532 }
4534 for (std::map<const char *, pt>::iterator i = d3_output_pt->begin(); i != d3_output_pt->end(); i++) {
4537 }
4539 for (std::map<const char *, pt>::iterator i = d3_depth_pt->begin(); i != d3_depth_pt->end(); i++) {
4542 }
4547 }
4549 /*
4550 * Calculate level of detail for a given viewpoint.
4551 */
4555 }
4557 /*
4558 * Calculate depth range for a given pair of viewpoints.
4559 */
4579 // assert (reference_change > 0);
4580 // assert (d1 > 0 || d2 > 0);
4586 else
4588 }
4597 }
4599 /*
4600 * Calculate a refined point for a given set of parameters.
4601 */
4605 ale_pos depth_range) {
4636 }
4637 }
4640 }
4642 /*
4643 * Analyze space in a manner dependent on the score map.
4644 */
4668 total_ambiguity++;
4685 }
4710 /*
4711 * Re-evaluate target dimension.
4712 */
4714 ale_pos target_dim_ =
4728 }
4730 /*
4731 * Attempt to refine space around the intersection point.
4732 */
4737 // if (!resolution_ok(al->get(f1)->get_t(0), al->get(f1)->get_t(0).trilinear_coordinate(st))) {
4738 // pt transformation = al->get(f1)->get_t(0);
4739 // ale_pos tc = al->get(f1)->get_t(0).trilinear_coordinate(st);
4740 //
4741 // fprintf(stderr, "Resolution not ok.\n");
4742 // fprintf(stderr, "pow(2, tc)=%f\n", pow(2, tc));
4743 // fprintf(stderr, "transformation.unscaled_height()=%f\n",
4744 // transformation.unscaled_height());
4745 // fprintf(stderr, "transformation.unscaled_width()=%f\n",
4746 // transformation.unscaled_width());
4747 // fprintf(stderr, "tc=%f", tc);
4748 // fprintf(stderr, "input_decimation_lower - 1.5 = %f\n",
4749 // input_decimation_lower - 1.5);
4750 //
4751 // }
4752 //
4753 // assert(resolution_ok(al->get(f1)->get_t(0), al->get(f1)->get_t(0).trilinear_coordinate(st)));
4754 // assert(resolution_ok(al->get(f2)->get_t(0), al->get(f2)->get_t(0).trilinear_coordinate(st)));
4755 }
4757 }
4758 }
4761 /*
4762 * Initialize space and identify regions of interest for the adaptive
4763 * subspace model.
4764 */
4771 /*
4772 * Variable indicating whether low-resolution filler space
4773 * is desired to avoid aliased gaps in surfaces.
4774 */
4785 /*
4786 * Initialize root space.
4787 */
4791 /*
4792 * Special handling for experimental option 'subspace_traverse'.
4793 */
4796 /*
4797 * Subdivide space to resolve intensity matches between pairs
4798 * of frames.
4799 */
4830 }
4834 }
4837 }
4839 /*
4840 * Subdivide space to resolve intensity matches between pairs
4841 * of frames.
4842 */
4856 }
4858 /*
4859 * Iterate over all points in the primary frame.
4860 */
4872 total_pixels++;
4874 /*
4875 * Generate a map from scores to 3D points for
4876 * various depths in f1.
4877 */
4881 /*
4882 * Analyze space in a manner dependent on the score map.
4883 */
4888 }
4890 /*
4891 * This ordering may encourage image f1 to be cached.
4892 */
4897 }
4898 }
4899 }
4902 /*
4903 * Update spatial information structures.
4904 *
4905 * XXX: the name of this function is horribly misleading. There isn't
4906 * even a 'search depth' any longer, since there is no longer any
4907 * bounded DFS occurring.
4908 */
4911 /*
4912 * Subspace model
4913 */
4920 }
4922 }
4924 #if 0
4925 /*
4926 * Describe a scene to a renderer
4927 */
4929 }
4930 #endif
4931 };
4933 #endif