1<?php
2
3/* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
4
5/**
6 * 3d Library
7 *
8 * PHP versions 5
9 *
10 * LICENSE:
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser General Public
13 * License as published by the Free Software Foundation; either
14 * version 2.1 of the License, or (at your option) any later version.
15 *
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19 * Lesser General Public License for more details.
20 *
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with this library; if not, write to the Free Software
23 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
24 *
25 * @category  Image
26 * @package   Image_3D
27 * @author    Kore Nordmann <3d@kore-nordmann.de>
28 * @copyright 1997-2005 Kore Nordmann
29 * @license   http://www.gnu.org/licenses/lgpl.txt lgpl 2.1
30 * @version   CVS: $Id$
31 * @link      http://pear.php.net/package/PackageName
32 * @since     File available since Release 0.1.0
33 */
34
35
36/**
37 * Image_3D_Object
38 *
39 * @category  Image
40 * @package   Image_3D
41 * @author    Kore Nordmann <3d@kore-nordmann.de>
42 * @copyright 1997-2005 Kore Nordmann
43 * @license   http://www.gnu.org/licenses/lgpl.txt lgpl 2.1
44 * @version   Release: @package_version@
45 * @link      http://pear.php.net/package/PackageName
46 * @since     Class available since Release 0.1.0
47 */
48class Image_3D_Object implements Image_3D_Interface_Paintable
49{
50
51    protected $_polygones;
52
53    public function __construct()
54    {
55        $this->_polygones = array();
56    }
57
58    public function getPolygonCount()
59    {
60        return count($this->_polygones);
61    }
62
63    public function setColor(Image_3D_Color $color)
64    {
65        foreach ($this->_polygones as $polygon) {
66            $polygon->setColor($color);
67        }
68    }
69
70    public function setOption($option, $value)
71    {
72        foreach ($this->_polygones as $polygon) {
73            $polygon->setOption($option, $value);
74        }
75    }
76
77    public function transform(Image_3D_Matrix $matrix, $id = null)
78    {
79
80        if ($id === null) {
81            $id = substr(md5(microtime()), 0, 8);
82        }
83
84        foreach ($this->_polygones as $polygon) {
85            $polygon->transform($matrix, $id);
86        }
87    }
88
89    public function getPolygones()
90    {
91        return $this->_polygones;
92    }
93
94    protected function _addPolygon(Image_3D_Polygon $polygon)
95    {
96        $this->_polygones[] = $polygon;
97    }
98
99    protected function _buildInzidenzGraph()
100    {
101        $polygons = $this->getPolygones();
102
103        $surfaces = array();
104        $edges    = array();
105        $points   = array();
106
107        $point_hash = array();
108        $edge_hash  = array();
109
110        foreach ($polygons as $nr => $polygon) {
111            $p_points = $polygon->getPoints();
112
113            $last_index  = false;
114            $first_index = false;
115            foreach ($p_points as $point) {
116                // Add point to edge
117                $p_p_hash = $point->__toString();
118                if (isset($point_hash[$p_p_hash])) {
119                    $p_p_index = $point_hash[$p_p_hash];
120                } else {
121                    $points[]  = $point;
122                    $p_p_index = count($points) - 1;
123
124                    $point_hash[$p_p_hash] = $p_p_index;
125                }
126
127                // Add edge to surface
128                if ($last_index !== false) {
129                    $e_points = array($p_p_index, $last_index);
130                    sort($e_points);
131                    $p_e_hash = implode(' -> ', $e_points);
132                    if (isset($edge_hash[$p_e_hash])) {
133                        $surfaces[$nr][] = $edge_hash[$p_e_hash];
134                    } else {
135                        $edges[] = $e_points;
136
137                        $edge_hash[$p_e_hash] = count($edges) - 1;
138
139                        $surfaces[$nr][] = $edge_hash[$p_e_hash];
140                    }
141                } else {
142                    $first_index = $p_p_index;
143                }
144
145                // Prepare last index for next iteration
146                $last_index = $p_p_index;
147            }
148
149            // Close surface
150            $e_points = array($first_index, $last_index);
151            sort($e_points);
152            $p_e_hash = implode(' -> ', $e_points);
153            if (isset($edge_hash[$p_e_hash])) {
154                $surfaces[$nr][] = $edge_hash[$p_e_hash];
155            } else {
156                $edges[]              = $e_points;
157                $edge_hash[$p_e_hash] = count($edges) - 1;
158                $surfaces[$nr][]      = $edge_hash[$p_e_hash];
159            }
160        }
161
162        return array(
163            'surfaces' => $surfaces,
164            'edges' => $edges,
165            'points' => $points,
166        );
167    }
168
169    public function subdivideSurfaces($factor = 1)
170    {
171        for ($i = 0; $i < $factor; ++$i) {
172            $data = $this->_buildInzidenzGraph();
173
174            // Additional hash maps
175            $edge_surfaces = array();
176            $edge_middles  = array();
177            $point_edges   = array();
178
179            // New calculated points
180            $face_points = array();
181            $edge_points = array();
182            $old_points  = array();
183
184            // Calculate "face points"
185            foreach ($data['surfaces'] as $surface => $edges) {
186                // Get all points
187                $points = array();
188                foreach ($edges as $edge) {
189                    $points = array_merge($points, $data['edges'][$edge]);
190
191                    $edge_surfaces[$edge][] = $surface;
192                }
193                $points = array_unique($points);
194
195                // Calculate average
196                $face_point  = array(0, 0, 0);
197                $point_count = count($points);
198                foreach ($points as $point) {
199                    $face_point[0] += $data['points'][$point]->getX() / $point_count;
200                    $face_point[1] += $data['points'][$point]->getY() / $point_count;
201                    $face_point[2] += $data['points'][$point]->getZ() / $point_count;
202                }
203
204                // Create face point
205                $face_points[$surface] = new Image_3D_Point($face_point[0], $face_point[1], $face_point[2]);
206            }
207
208            // Calculate "edge points"
209            foreach ($data['edges'] as $edge => $points) {
210                // Calculate middle of edge
211                if (isset($edge_middles[$edge])) {
212                    $edge_middle = $edge_middles[$edge];
213                } else {
214                    $edge_middle = array(0, 0, 0);
215                    $point_count = count($points);
216                    foreach ($points as $point) {
217                        $point_edges[$point][] = $edge;
218
219                        $edge_middle[0] += $data['points'][$point]->getX() / $point_count;
220                        $edge_middle[1] += $data['points'][$point]->getY() / $point_count;
221                        $edge_middle[2] += $data['points'][$point]->getZ() / $point_count;
222                    }
223                    $edge_middles[$edge] = $edge_middle;
224                }
225
226                // Calculate average of the adjacent faces
227                $average_face = array(0, 0, 0);
228                $point_count  = count($edge_surfaces[$edge]);
229                foreach ($edge_surfaces[$edge] as $surface) {
230                    $average_face[0] += $face_points[$surface]->getX() / $point_count;
231                    $average_face[1] += $face_points[$surface]->getY() / $point_count;
232                    $average_face[2] += $face_points[$surface]->getZ() / $point_count;
233                }
234
235                // Create edge point on this base
236                $edge_points[$edge] = new Image_3D_Point(($average_face[0] + $edge_middle[0]) / 2, ($average_face[1] + $edge_middle[1]) / 2, ($average_face[2] + $edge_middle[2]) / 2);
237            }
238
239            // Reposition old vertices
240            foreach ($data['points'] as $point => $value) {
241                // Calculate average of midpoints of adjacent edges
242                $r = array(0, 0, 0);
243
244                $surfaces = array();
245
246                $point_count = count($point_edges[$point]);
247
248                foreach ($point_edges[$point] as $edge) {
249                    $r[0] += $edge_middles[$edge][0] / $point_count;
250                    $r[1] += $edge_middles[$edge][1] / $point_count;
251                    $r[2] += $edge_middles[$edge][2] / $point_count;
252
253                    $surfaces = array_merge($surfaces, $edge_surfaces[$edge]);
254                }
255                $surfaces = array_unique($surfaces);
256
257                // Calculate average of surrounding face points
258                $q = array(0, 0, 0);
259
260                $surface_count = count($surfaces);
261                foreach ($surfaces as $surface) {
262                    $q[0] += $face_points[$surface]->getX() / $surface_count;
263                    $q[1] += $face_points[$surface]->getY() / $surface_count;
264                    $q[2] += $face_points[$surface]->getZ() / $surface_count;
265                }
266
267                // Create new edge point
268                $n = count($point_edges[$point]);
269
270                $old_points[$point] = new Image_3D_Point(
271                    ($q[0] / $n) + ((2 * $r[0]) / $n) + (($value->getX() * ($n - 3)) / $n),
272                    ($q[1] / $n) + ((2 * $r[1]) / $n) + (($value->getY() * ($n - 3)) / $n),
273                    ($q[2] / $n) + ((2 * $r[2]) / $n) + (($value->getZ() * ($n - 3)) / $n)
274                );
275            }
276
277            // Create polygones on new points
278            $this->_polygones = array();
279            foreach ($face_points as $surface => $face_point) {
280                // Get all points for face
281                $points = array();
282                foreach ($data['surfaces'][$surface] as $edge) {
283                    $points = array_merge($points, $data['edges'][$edge]);
284                }
285                $points = array_unique($points);
286
287                // Create new polygones
288                foreach ($points as $point) {
289                    $edges = array_values(array_intersect($point_edges[$point], $data['surfaces'][$surface]));
290                    $this->_addPolygon(new Image_3D_Polygon($old_points[$point],
291                                                            $edge_points[$edges[0]],
292                                                            $face_point,
293                                                            $edge_points[$edges[1]]));
294                }
295            }
296
297            // Debug output
298            /*
299            echo "\nFace points:\n";
300            foreach ($face_points as $point) echo $point, "\n";
301
302            echo "\nEdge points:\n";
303            foreach ($edge_points as $point) echo $point, "\n";
304
305            echo "\nRepositioned points:\n";
306            foreach ($old_points as $point) echo $point, "\n";
307
308            echo "\nCreated polygones:\n";
309            foreach ($this->_polygones as $polygon) {
310                echo $polygon;
311            }
312            */
313        }
314    }
315}
316
317