[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnash-commit] gnash ChangeLog libgeometry/Makefile.am testsui...
|
From: |
Sandro Santilli |
|
Subject: |
[Gnash-commit] gnash ChangeLog libgeometry/Makefile.am testsui... |
|
Date: |
Sat, 01 Dec 2007 22:11:25 +0000 |
CVSROOT: /sources/gnash
Module name: gnash
Changes by: Sandro Santilli <strk> 07/12/01 22:11:25
Modified files:
. : ChangeLog
libgeometry : Makefile.am
testsuite/swfdec: PASSING
Removed files:
libgeometry : kd_tree_dynamic.cpp kd_tree_dynamic.h
kd_tree_packed.cpp kd_tree_packed.h
Log message:
Drop unused files guilty of using hash_wrapper.h
Sync expected swfdec testsuite successes to master.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/gnash/ChangeLog?cvsroot=gnash&r1=1.5046&r2=1.5047
http://cvs.savannah.gnu.org/viewcvs/gnash/libgeometry/Makefile.am?cvsroot=gnash&r1=1.32&r2=1.33
http://cvs.savannah.gnu.org/viewcvs/gnash/libgeometry/kd_tree_dynamic.cpp?cvsroot=gnash&r1=1.17&r2=0
http://cvs.savannah.gnu.org/viewcvs/gnash/libgeometry/kd_tree_dynamic.h?cvsroot=gnash&r1=1.6&r2=0
http://cvs.savannah.gnu.org/viewcvs/gnash/libgeometry/kd_tree_packed.cpp?cvsroot=gnash&r1=1.12&r2=0
http://cvs.savannah.gnu.org/viewcvs/gnash/libgeometry/kd_tree_packed.h?cvsroot=gnash&r1=1.3&r2=0
http://cvs.savannah.gnu.org/viewcvs/gnash/testsuite/swfdec/PASSING?cvsroot=gnash&r1=1.68&r2=1.69
Patches:
Index: ChangeLog
===================================================================
RCS file: /sources/gnash/gnash/ChangeLog,v
retrieving revision 1.5046
retrieving revision 1.5047
diff -u -b -r1.5046 -r1.5047
--- ChangeLog 1 Dec 2007 21:54:24 -0000 1.5046
+++ ChangeLog 1 Dec 2007 22:11:23 -0000 1.5047
@@ -1,5 +1,12 @@
2007-12-01 Sandro Santilli <address@hidden>
+ * testsuite/swfdec/PASSING: sync to master.
+ * libgeometry/: Makefile.am, kd_tree_dynamic.{cpp,h},
+ kd_tree_packed.{cpp,h}: drop unused files guilty of
+ using hash_wrapper.h
+
+2007-12-01 Sandro Santilli <address@hidden>
+
* libmedia/sdl/sound_handler_sdl.{cpp,h}: drop dependency on
hash_wrapper.h.
Index: libgeometry/Makefile.am
===================================================================
RCS file: /sources/gnash/gnash/libgeometry/Makefile.am,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -b -r1.32 -r1.33
--- libgeometry/Makefile.am 10 Nov 2007 09:46:54 -0000 1.32
+++ libgeometry/Makefile.am 1 Dec 2007 22:11:24 -0000 1.33
@@ -18,7 +18,7 @@
#
#
-# $Id: Makefile.am,v 1.32 2007/11/10 09:46:54 strk Exp $
+# $Id: Makefile.am,v 1.33 2007/12/01 22:11:24 strk Exp $
AUTOMAKE_OPTIONS =
@@ -51,8 +51,6 @@
collision.cpp \
cull.cpp \
geometry.cpp \
- kd_tree_dynamic.cpp \
- kd_tree_packed.cpp \
tqt.cpp
noinst_HEADERS = \
@@ -64,8 +62,6 @@
collision.h \
cull.h \
geometry.h \
- kd_tree_dynamic.h \
- kd_tree_packed.h \
tqt.h \
view_state.h \
visual.h
Index: testsuite/swfdec/PASSING
===================================================================
RCS file: /sources/gnash/gnash/testsuite/swfdec/PASSING,v
retrieving revision 1.68
retrieving revision 1.69
diff -u -b -r1.68 -r1.69
--- testsuite/swfdec/PASSING 30 Nov 2007 11:26:05 -0000 1.68
+++ testsuite/swfdec/PASSING 1 Dec 2007 22:11:25 -0000 1.69
@@ -45,13 +45,16 @@
attachmovie-object-5.swf:a1fa0db4e7ac649e5451ff5e96a71436
attachmovie-object-6.swf:52c0c8d46a3535c7db79d3d827b31b41
attachmovie-object-7.swf:9a18445affc4ae1dc0e0fe085b13f1e1
+bevel-filter-properties-5.swf:019bb55478951055973b5f953b2e82ef
bevel-filter-properties-5.swf:0ec31af3035594a9cbcb1ba8a645ad4c
bitmap-filter-properties-5.swf:62973bfcdf9f1fd383440fabcbfebca9
+bitmap-filter-properties-5.swf:d69ea38322111b3626c6b9577838674f
bitwise-5.swf:98475055aae4796a066e7728d5a7a944
bitwise-6.swf:ef818f643cc14a4cc57248473e05a48c
bitwise-7.swf:c18505cd0d075c512d15b6d96ab221d0
bitwise-8.swf:a99b312eddd076f8b9df649bc4b33964
blur-filter-properties-5.swf:4c29ecc04df379ced45039fdbb79eb9c
+blur-filter-properties-5.swf:f2e1d9ccc47765bd6c88095b19974c7b
call-arguments-5.swf:422c391a2abd3e864eb8ed8a1e05ad31
callfunction-stack.swf:21d0c957f4caf0eb0ccd0dcadaf17500
case1-6.swf:ba805f628a3a2d1bbd292ec1e56d1708
@@ -68,11 +71,13 @@
clonesprite-depths-8.swf:af472e7f31b31e886ca86430fb71106f
color-getters.swf:4cee4418f75171e7bf423759a468b36b
color-matrix-filter-properties-5.swf:2349ffbd77298b0dea59d6ed618c382b
+color-matrix-filter-properties-5.swf:cc51e1cb7864d648f958ffef649d5464
color-new.swf:b19cf3d46f416b919eb312da473b6756
color-setRGB.swf:0841414e9ac7d2f9b57e40aec3d2f44f
color-setTransform-empty.swf:2a72a5273ab8713ee289ff1726b0959c
color-setTransform-negative.swf:0bc0510c35fc5c82de31b0db887fe535
color-transform-properties-5.swf:74bd1e74d40fd8741000366645b7c776
+color-transform-properties-5.swf:7e620e53cb1e19d5793e3198e9f08993
color1.swf:3cc52a41193d342cfdfaeffe56edc3db
comparisons-4.swf:e0bb89e492f3f35e51b1beb190935a14
comparisons-5.swf:d4dfeb4ec80ec1f5a7390eb699e269ee
@@ -88,6 +93,7 @@
constructor-madness-8.swf:5357273baf6b66f6af0223cb1d13b144
constructor-prototype.swf:22505f0f8dd8440972a298110d697e3b
convolution-filter-properties-5.swf:96e15de475e31c328e201c152ffd2f42
+convolution-filter-properties-5.swf:db6e2ddcbee195363a53c276bfc460d7
crash-0.5.2-cvs-return-from-block-5.swf:4aab3181976e557d6e0457ff7e0a6403
crash-0.5.2-cvs-return-from-block-6.swf:c1c585c3c888f13d69f9646c0f2fb928
crash-0.5.2-cvs-return-from-block-7.swf:e09d75c52f6209e8f488fb50744e1435
@@ -100,6 +106,7 @@
crash-0.5.3-text-field-root-variable-6.swf:523e410878987c9437735d64419cc5a2
crash-0.5.3-text-field-root-variable-7.swf:d01c94174267217b7856d88b74c1c5a4
crash-0.5.3-text-field-root-variable-8.swf:eb57d51faba048c41b994aada7954acc
+crash-0.5.4-goto-in-constructor-5.swf:01f124ea9669b0b609a82b58a503dea3
currentframe.swf:ba479d5adbece0ddafeaa75e68eff052
dangling-compare-5.swf:7daa85d63e7bf29df6aa1668d21a28a9
dangling-compare-6.swf:51999fa1cbc988765b5dee03717d22a5
@@ -135,10 +142,12 @@
delete-prototypes-6.swf:1734eb410cfe52dffb937d5c1c210a0f
delete-prototypes-7.swf:5b01906b25bcc0fa0783b259d49a9348
delete-prototypes-8.swf:4ec22b5249be231984324ee407255d56
+displacement-map-filter-properties-5.swf:795a7a326674cedb0900a9714ef890c4
displacement-map-filter-properties-5.swf:b0d6a60fa2f9eee15163634c5a6c224f
divide-7.swf:8b1d7b8cb6af31c83878774864c3900a
doaction-after-placeobject.swf:ea4387286e602dd93cf2f75ea6698690
doaction-before-placeobject.swf:4e8f238ef804fe0d254cd9ed9581e097
+drop-shadow-filter-properties-5.swf:68ec26c24ecb04174a484d810dab523f
drop-shadow-filter-properties-5.swf:827a880fc55b1afb96515f0d64a064b6
duplicate-names-5.swf:d73096f662cf35b34c15e3f59fb88258
duplicate-names-6.swf:2f1c48973f13cb831bca9a4b7bbccde0
@@ -149,6 +158,10 @@
empty-function-7.swf:d65a6d323a864fad2965496ff2a69f2b
empty-function-8.swf:8590a81f543ca2f7a1bc6fb2105f5672
empty-stack.swf:47ef885ae85e56e2ba8caae6eed46704
+emptymovie-frames-bytes-5.swf:70cef0b90e7c6202bd70d386338dd682
+emptymovie-frames-bytes-6.swf:40850e9e5980b0f8cac3e2702079eb3f
+emptymovie-frames-bytes-7.swf:26277a3087d867d21225496f42219e5b
+emptymovie-frames-bytes-8.swf:1536a58d30e4ac04bfd3338cef62729d
enumerate-5.swf:62ec57ff724247d42c254cfadca06f2d
enumerate-6.swf:85f81c4443f6137238d4fa5561579812
enumerate-7.swf:35e50f33fd5b00821d709ce06dc3bcad
@@ -161,8 +174,10 @@
extends-constructors-7.swf:bdd4d88deef41da109379e5dc0c130d6
extends-constructors-8.swf:b812f8e472f897a73914d10101841b87
extends-simple.swf:5e3daf1e64d50b0c9ef06f7ad99f2bda
+file-reference-list-properties-5.swf:47e812391ae3b295a7f85dc5ab988179
file-reference-list-properties-5.swf:4d13076bcc6ab1cd02fea9f62d4013cf
file-reference-properties-5.swf:238ae6d8bf7d0ee8a241f20cf1247e6e
+file-reference-properties-5.swf:5edd2cb082cf1c50a9bae21c7a6e75c0
foreach-proto-simple-5.swf:63689d87c2e1eb1602b2624fa9a61c3e
foreach-proto-simple-6.swf:6ef0541de231d2f6254bda0056d6c5db
foreach-proto-simple-7.swf:08e9473a6b4d9ebb125a1d352a431b25
@@ -208,6 +223,7 @@
getvariable-slashpath-7.swf:499213312255eba3746c4ff6b7b4782d
getvariable-slashpath-8.swf:19df043ceda9c1db9efbd185bb5ae2cb
getvariable-special-5.swf:4baac55533a4cc67a3419dafb97cc888
+glow-filter-properties-5.swf:10d87d4cbd9c1f4c41a817f67cf3f530
glow-filter-properties-5.swf:b3d05908aaa98c7115ec1727d695a16a
goto1.swf:6f35a27cb3aee7f282eccb3b16290c70
goto2.swf:f845271dd90a84b3919ca9000d66cd25
@@ -216,7 +232,9 @@
goto5.swf:cc19122dcb5d0c4d68bf7889822e4eb2
gotoframe.swf:2979edee317cb3e109ef769451b09616
gradient-bevel-filter-properties-5.swf:4e4322654b7b7368fdc5499cff81654f
+gradient-bevel-filter-properties-5.swf:b0d435175adc96e6300b4a522aae7d47
gradient-glow-filter-properties-5.swf:719ca44e28c6f4fd8ca97ed2c1386fdd
+gradient-glow-filter-properties-5.swf:dd43dd6eb377ad30efd52286f1ce0b1b
height1.swf:245da260d32dbc48a5f38566ee70171b
height3.swf:2b7547493377ae1c0163c8273a4073f7
height4.swf:8d36c180d196b49608f996db21a421bc
@@ -246,11 +264,18 @@
math-constants-5.swf:ca9d0fc66667d7c7863e699367176573
math-constants-6.swf:cc4a6b92d473f57cb5479c97ba77c2e0
math-constants-7.swf:53df046dd67c331c79c0c939215ac770
+mouse-addProperty-relevant-5.swf:1bfc494379c8192d0b410ab431efbebd
+mouse-movie-below-movie-5.swf:c7d97de8768c341a64df75dca2686c0b
+mouse-movie-below-nonevent-movie-5.swf:9027280bdb516e12f2e4255776c079a1
mouse-scaled-5.swf:9138b10aab35c2d4e969057b9c253b42
+movieclip-get-swf-version-5.swf:276a5f85dc4368fa3f1c79f41f50b46b
movieclip-get-swf-version-5.swf:fe088f984b71c0e78c2335bb05bbec16
+movieclip-get-swf-version-6.swf:2fdfe7f422bf76061c258e8ea5316c4a
movieclip-get-swf-version-6.swf:dc4632e3ba339e083676380c81e70e0d
movieclip-get-swf-version-7.swf:17a8fa635b8b9d109b0fd0795c50b347
+movieclip-get-swf-version-7.swf:77fd36d2dbdec306c3b4f59e1456419a
movieclip-get-swf-version-8.swf:5228a59ad74ce8ba27e0fb8a593a2c8d
+movieclip-get-swf-version-8.swf:c79a3ef15927fe63fa9bc66cd6959e55
movieclip-get-swf-version-load-5.swf:3d7dcf17068a176d72b14ca18b166c21
movieclip-set-prototype-5.swf:99235a738d69d9c78fa2bc5d355c6dae
movieclip-set-prototype-6.swf:bae79ccbb89bb7c11cd1961d2c473022
@@ -282,6 +307,7 @@
object-valueof-5.swf:2520f058ac5a1af3db81ba9b3002e6ab
object-watch-5.swf:12bd406ac79e6ce18130f854626e9003
object-watch-segv-5.swf:990733edee1b528931b182c03bea8b6e
+onUnload-prototype-5.swf:63014a643d2cdec7a93fb115678833f1
onload-childparent.swf:657c404873bde57d597a8a8c43f7c008
onresize-5.swf:76f88b683c640279239628f030ad8291
onresize-6.swf:322df0e4ac0cbb3beb5c86026be8c716
@@ -370,6 +396,7 @@
place-object-remove-name-6.swf:302e32a0834a50f219f8ab9a15234c41
place-object-remove-name-7.swf:689ff2c69386d51ce336691cb485ab55
point-5.swf:9e49aa1df7118acccf003ae0648ef439
+point-properties-5.swf:2b1071acd6c53d5342c1946214a3b3df
point-properties-5.swf:c3439d59fa29fb709630ee3a3ad230b0
preload.swf:2fd2da9440e29289e83dadd1ed9c99c4
print-job-init-5.swf:22889777e5e8230cee8c760c0930b5db
@@ -391,10 +418,15 @@
register-count.swf:861abb623a228e4152df92896ee807f0
registerclass-previous.swf:7ea3d590fa576190bda56996ff0fa768
registerclass-properties.swf:9deba9b328c2e4af1c1eb98a62d4e355
+remove-child-onUnload-5.swf:895da940f20c08bdccfcc3c826acbe34
+remove-child-onUnload-6.swf:ff63ff1af8eb36815c85f8dfdcbe2814
+remove-child-onUnload-7.swf:45ddcce6e9b19e512183557c552c8a08
+remove-child-onUnload-8.swf:a14d9306cd33e0fbd7c1ec7062a8cae2
remove-depths-5.swf:1fabff7e05aaa1149898e320b8149313
remove-depths-6.swf:0c3bb7456c11fbff848efc03a29efe30
remove-depths-7.swf:4172052b6f6e97339c52d6315c1c139b
remove-depths-8.swf:55303aac24d7e87427ba716c1d50e631
+remove-with-onUnload-5.swf:5d41fcdce5757cff3e4c9678c9c3e72b
removesprite-depths-5.swf:03c73fab9efd3909214def0f6b233486
removesprite-depths-6.swf:039c217ab8233668d64bffd2e7a6ef79
removesprite-depths-7.swf:b792dc92c63978c09f9c937a2d5a24cf
@@ -517,6 +549,8 @@
stylesheet-load-6.swf:e3b34170df069108049f1381e93572c6
stylesheet-parse-5.swf:f77505087f69427b13c91f30a9c103ad
stylesheet-parse-6.swf:0c070dfd772d1b7280ac53b711dcbb1c
+stylesheet-properties-5.swf:3f43b40ef887836be3cc363a9347ad57
+stylesheet-properties-6.swf:678fd39739e2d49aa353147c66cfb6ad
substr-5.swf:cf154038f95d1d654f2d162f16c60a5b
substr-6.swf:d16644cf5ac2775cceb46f19c8663fcd
substr-7.swf:5fd2eea885c31f6b5bd881addc0f11ba
@@ -550,6 +584,7 @@
tointeger-various-6.swf:71257f69e5f3feb6ae18ebf26ad2eb22
tointeger-various-7.swf:6251bc39b6449a82c89b6c821f9af0ff
totalframes.swf:cdc0d5e2017d293438ef80fa136c44e8
+transform-properties-5.swf:9332e41f53db6ec456387efffd9e12a7
transform-properties-5.swf:b0386824584340e1d0a80f986ce779b9
transform.swf:5c8533f9168ca3e92d000ce1693ed5ef
try-throw-in-finally-6.swf:1c12d4b0f949704bd0794d73f0385007
Index: libgeometry/kd_tree_dynamic.cpp
===================================================================
RCS file: libgeometry/kd_tree_dynamic.cpp
diff -N libgeometry/kd_tree_dynamic.cpp
--- libgeometry/kd_tree_dynamic.cpp 30 Oct 2007 18:55:41 -0000 1.17
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,1268 +0,0 @@
-// kd_tree_dynamic.cpp -- by Thatcher Ulrich <address@hidden>
-
-// This source code has been donated to the Public Domain. Do
-// whatever you want with it.
-
-// Utility kd-tree structure, for building kd-trees from triangle
-// soup.
-
-// #include <cwctype>
-// #include <cwchar>
-#include <cstdio>
-
-#include "kd_tree_dynamic.h"
-#include "tu_file.h"
-#include <cfloat>
-#include "hash_wrapper.h"
-
-using namespace std;
-using namespace gnash;
-
-static const float EPSILON = 1e-4f;
-static const int LEAF_FACE_COUNT = 6;
-static const int MAX_SPLIT_PLANES_TESTED = 10;
-
-//#define CARVE_OFF_SPACE
-//#define ADHOC_METRIC
-#define MACDONALD_AND_BOOTH_METRIC
-//#define SORT_VERTICES
-
-// A higher value for MAX_SPLIT_PLANES_TESTED gives faster trees;
-// e.g. on one dataset, MSPT=100 gives 10% faster queries than
-// MSPT=10. But the tree building is much slower.
-
-// On one dataset I checked, SORT_VERTICES makes queries ~10% faster.
-// On most others, it seemed to make no difference. It takes extra
-// time to do the sort, though.
-
-
-float kd_tree_dynamic::face::get_min_coord(int axis, const std::vector<vec3>&
verts) const
-{
- float minval = verts[m_vi[0]][axis];
- minval = fmin(minval, verts[m_vi[1]][axis]);
- minval = fmin(minval, verts[m_vi[2]][axis]);
- return minval;
-}
-
-
-float kd_tree_dynamic::face::get_max_coord(int axis, const std::vector<vec3>&
verts) const
-{
- float maxval = verts[m_vi[0]][axis];
- maxval = fmax(maxval, verts[m_vi[1]][axis]);
- maxval = fmax(maxval, verts[m_vi[2]][axis]);
- return maxval;
-}
-
-
-void split_mesh(
- std::vector<vec3>* verts0,
- std::vector<int>* tris0,
- std::vector<vec3>* verts1,
- std::vector<int>* tris1,
- int /* vert_count */,
- const vec3 verts[],
- int triangle_count,
- const int indices[],
- int axis,
- float offset)
-// Divide a mesh into two pieces, roughly along the plane [axis]=offset.
-// Assign faces to one side or the other based on centroid.
-{
- assert(verts0 && tris0 && verts1 && tris1);
- assert(verts0->size() == 0);
- assert(tris0->size() == 0);
- assert(verts1->size() == 0);
- assert(tris1->size() == 0);
-
- // Remap table from verts array to new verts0/1 arrays.
- hash_wrapper<int, int> verts_to_verts0;
- hash_wrapper<int, int> verts_to_verts1;
-
- // Divide the faces.
- for (int i = 0; i < triangle_count; i++)
- {
- int index = i * 3;
- int v[3] = {
- indices[index],
- indices[index + 1],
- indices[index + 2]
- };
-
- float centroid = (verts[v[0]][axis] + verts[v[1]][axis] +
verts[v[2]][axis]) / 3.0f;
-
- if (centroid < offset)
- {
- // Put this face into verts0/tris0
- for (int ax = 0; ax < 3; ax++)
- {
- int new_index;
- if (verts_to_verts0.get(v[ax], &new_index))
- {
- // OK.
- }
- else
- {
- // Must add.
- new_index = verts0->size();
- verts_to_verts0.add(v[ax], new_index);
- verts0->push_back(verts[v[ax]]);
- }
- tris0->push_back(new_index);
- }
- }
- else
- {
- // Put this face into verts1/tris1
- for (int ax = 0; ax < 3; ax++)
- {
- int new_index;
- if (verts_to_verts1.get(v[ax], &new_index))
- {
- // OK.
- }
- else
- {
- // Must add.
- new_index = verts1->size();
- verts_to_verts1.add(v[ax], new_index);
- verts1->push_back(verts[v[ax]]);
- }
- tris1->push_back(new_index);
- }
- }
- }
-}
-
-
-static void remap_vertex_order(kd_tree_dynamic::node* node,
hash_wrapper<int, int>* map_indices_old_to_new, int* new_vertex_count)
-// Traverse this tree in depth-first order, and remap the vertex
-// indices to go in order.
-{
- if (node == NULL) return;
-
- if (node->m_leaf)
- {
- for (int i = 0, n = node->m_leaf->m_faces.size(); i < n; i++)
- {
- kd_tree_dynamic::face* f = &node->m_leaf->m_faces[i];
- for (int vi = 0; vi < 3; vi++)
- {
- int old_index = f->m_vi[vi];
- int new_index = *new_vertex_count;
- if (map_indices_old_to_new->get(old_index,
&new_index))
- {
- // vert is already remapped; use
existing mapping.
- }
- else
- {
- // vert is not remapped yet; remap it.
- map_indices_old_to_new->add(old_index,
new_index);
- (*new_vertex_count)++;
- }
-
- // Remap.
- f->m_vi[vi] = new_index;
- }
- }
- }
- else
- {
- remap_vertex_order(node->m_neg, map_indices_old_to_new,
new_vertex_count);
- remap_vertex_order(node->m_pos, map_indices_old_to_new,
new_vertex_count);
- }
-}
-
-
-/*static*/ void kd_tree_dynamic::build_trees(
- std::vector<kd_tree_dynamic*>* treelist,
- int vert_count,
- const vec3 verts[],
- int triangle_count,
- const int indices[]
- )
-// Build one or more kd trees to represent the given mesh.
-{
- if (vert_count >= 65536)
- {
- // Too many verts for one tree; subdivide.
- axial_box bound;
- compute_actual_bounds(&bound, vert_count, verts);
-
- int longest_axis = bound.get_longest_axis();
- float offset = bound.get_center()[longest_axis];
-
- std::vector<vec3> verts0, verts1;
- std::vector<int> tris0, tris1;
- split_mesh(
- &verts0,
- &tris0,
- &verts1,
- &tris1,
- vert_count,
- verts,
- triangle_count,
- indices,
- longest_axis,
- offset);
-
- if ((int) verts0.size() >= vert_count || (int) verts1.size() >=
vert_count)
- {
- // Trouble: couldn't reduce vert count by
- // splitting.
- abort();
- // log error
- return;
- }
-
- build_trees(treelist, verts0.size(), &verts0[0], tris0.size() /
3, &tris0[0]);
- build_trees(treelist, verts1.size(), &verts1[0], tris1.size() /
3, &tris1[0]);
-
- return;
- }
-
- treelist->push_back(new kd_tree_dynamic(vert_count, verts,
triangle_count, indices));
-}
-
-
-kd_tree_dynamic::kd_tree_dynamic(
- int vert_count,
- const vec3 verts[],
- int triangle_count,
- const int indices[])
-// Constructor; build the kd-tree from the given triangle soup.
-{
- assert(vert_count > 0 && vert_count < 65536);
- assert(triangle_count > 0);
-
- // Copy the verts.
- m_verts.resize(vert_count);
- memcpy(&m_verts[0], verts, sizeof(verts[0]) * vert_count);
-
- // Make a mutable array of faces, and also compute our bounds.
- axial_box bounds(axial_box::INVALID, vec3::flt_max,
vec3::minus_flt_max);
- std::vector<face> faces;
- for (int i = 0; i < triangle_count; i++)
- {
- face f;
- f.m_vi[0] = indices[i * 3 + 0];
- f.m_vi[1] = indices[i * 3 + 1];
- f.m_vi[2] = indices[i * 3 + 2];
- f.m_flags = 0; // @@ should be a way to initialize this
-
- faces.push_back(f);
-
- // Update bounds.
- bounds.set_enclosing(m_verts[f.m_vi[0]]);
- bounds.set_enclosing(m_verts[f.m_vi[1]]);
- bounds.set_enclosing(m_verts[f.m_vi[2]]);
- }
-
- m_bound = bounds;
-
- m_root = build_tree(1, faces.size(), &faces[0], bounds);
-
-#ifdef SORT_VERTICES
- // Sort vertices in the order they first appear in a
- // depth-first traversal of the tree. Idea is to exploit
- // cache coherency when traversing tree.
-
- index map_indices_old_to_new;
- int new_vertex_count = 0;
- remap_vertex_order(m_root, &map_indices_old_to_new, &new_vertex_count);
-
- assert(new_vertex_count == m_verts.size());
-
- // Make the re-ordered vertex buffer.
- std::vector<vec3> new_verts;
- new_verts.resize(new_vertex_count);
- for (int i = 0; i < m_verts.size(); i++)
- {
- int new_index = 0;
- bool found = map_indices_old_to_new.get(i, &new_index);
- assert(found);
- if (found)
- {
- new_verts[new_index] = m_verts[i];
- }
- }
-
- // Use the new verts.
- m_verts = new_verts;
-#endif // SORT_VERTICES
-}
-
-
-kd_tree_dynamic::~kd_tree_dynamic()
-// Destructor; make sure to delete the stuff we allocated.
-{
- delete m_root;
-}
-
-
-kd_tree_dynamic::node* kd_tree_dynamic::build_tree(int depth, int face_count,
face faces[], const axial_box& bounds)
-// Recursively build a kd-tree from the given set of faces. Return
-// the root of the tree.
-{
- assert(face_count >= 0);
-
- if (face_count == 0)
- {
- return NULL;
- }
-
- // Should we make a leaf?
- if (face_count <= LEAF_FACE_COUNT)
- {
- // Make a leaf
- node* n = new node;
- n->m_leaf = new leaf;
- n->m_leaf->m_faces.resize(face_count);
- memcpy(&(n->m_leaf->m_faces[0]), faces, sizeof(faces[0]) *
face_count);
-
- return n;
- }
-
- // TODO I believe it may be better to try partitioning planes,
- // which separate the faces according to triangle centroid (or
- // centroid of the bound?), and then compute the actual
- // splitting planes based on the partition. I think this
- // helps avoid some bad situations with large triangles, where
- // a large tri keeps getting pushed down deeper and deeper.
- //
- // Currently we generate a candidate neg_offset plane
- // directly, and include all triangles fully behind the
- // neg_offset in one child, which may tend to be unbalanced.
-
- // Find a good splitting plane.
- float best_split_quality = 0.0f;
- int best_split_axis = -1;
- float best_split_neg_offset = 0.0f;
- float best_split_pos_offset = 0.0f;
-
- for (int axis = 0; axis < 3; axis++)
- {
- if (bounds.get_extent()[axis] < EPSILON)
- {
- // Don't try to divide
- continue;
- }
-
- // Try offsets that correspond to existing face boundaries.
- int step_size = 1;
- if (face_count > MAX_SPLIT_PLANES_TESTED)
- {
- // For the sake of speed & sanity, only try the bounds
- // of every N faces.
- step_size = face_count / MAX_SPLIT_PLANES_TESTED;
- }
- assert(step_size > 0);
-
- float last_offset_tried = -FLT_MAX;
- float pos_offset = 0;
- for (int i = 0; i < face_count; i += step_size)
- {
- float neg_offset = faces[i].get_max_coord(axis,
m_verts);
-
- if (fabsf(neg_offset - last_offset_tried) < EPSILON)
- {
- // Already tried this.
- continue;
- }
-
- last_offset_tried = neg_offset;
-
- // How good is this split?
- float quality = evaluate_split(depth, face_count,
faces, bounds, axis, neg_offset, &pos_offset);
- if (quality > best_split_quality)
- {
- // Best so far.
- best_split_quality = quality;
- best_split_axis = axis;
- best_split_neg_offset = neg_offset;
- best_split_pos_offset = pos_offset;
- }
- }
- }
-
- if (best_split_axis == -1)
- {
- // Couldn't find any acceptable split!
- // Make a leaf.
- node* n = new node;
- n->m_leaf = new leaf;
- n->m_leaf->m_faces.resize(face_count);
- memcpy(&(n->m_leaf->m_faces[0]), faces, sizeof(faces[0]) *
face_count);
-
- return n;
- }
- else
- {
- // Make the split.
- int back_end = 0;
- int front_end = 0;
-
- // We use the implicit node bounds, not the actual bounds of
- // the face sets, for computing split quality etc, since that
- // is what the run-time structures have when they are
- // computing query results.
-
- axial_box back_bounds(bounds);
- back_bounds.set_axis_max(best_split_axis,
best_split_neg_offset);
-
- axial_box front_bounds(bounds);
- front_bounds.set_axis_min(best_split_axis,
best_split_pos_offset);
-
- node* n = new node;
- n->m_axis = best_split_axis;
- n->m_neg_offset = best_split_neg_offset;
- n->m_pos_offset = best_split_pos_offset;
-
- // Recursively build sub-trees.
- do_split(&back_end, &front_end, face_count, faces,
best_split_axis, best_split_neg_offset, best_split_pos_offset);
-
- n->m_neg = build_tree(depth + 1, back_end, faces + 0,
back_bounds);
- n->m_pos = build_tree(depth + 1, front_end - back_end, faces +
back_end, front_bounds);
-
- return n;
- }
-}
-
-
-kd_tree_dynamic::node::node()
-// Default constructor, null everything out.
- :
- m_neg(0),
- m_pos(0),
- m_leaf(0),
- m_axis(0),
- m_neg_offset(0.0f),
- m_pos_offset(0.0f)
-{
-}
-
-
-kd_tree_dynamic::node::~node()
-// Destructor, delete children if any.
-{
- delete m_neg;
- delete m_pos;
- delete m_leaf;
-}
-
-
-bool kd_tree_dynamic::node::is_valid() const
-{
- return
- // internal node.
- (m_leaf == 0
- && m_axis >= 0
- && m_axis < 3)
- ||
- // leaf node
- (m_leaf != 0
- && m_neg == 0
- && m_pos == 0)
- ;
-}
-
-
-void kd_tree_dynamic::compute_actual_bounds(axial_box* result, int
face_count, face faces[])
-// Compute the actual bounding box around the given list of faces.
-{
- assert(face_count > 0);
-
- result->set_min_max_invalid(vec3::flt_max, vec3::minus_flt_max);
-
- for (int i = 0; i < face_count; i++)
- {
- const face& f = faces[i];
-
- // Update bounds.
- result->set_enclosing(m_verts[f.m_vi[0]]);
- result->set_enclosing(m_verts[f.m_vi[1]]);
- result->set_enclosing(m_verts[f.m_vi[2]]);
- }
-}
-
-
-/*static*/ void kd_tree_dynamic::compute_actual_bounds(axial_box*
result, int vert_count, const vec3 verts[])
-// Compute the actual bounding box around the given list of faces.
-{
- assert(vert_count > 0);
-
- result->set_min_max_invalid(vec3::flt_max, vec3::minus_flt_max);
-
- for (int i = 0; i < vert_count; i++)
- {
- // Update bounds.
- result->set_enclosing(verts[i]);
- }
-}
-
-
-static int classify_coord(float coord, float offset)
-{
- if (coord < offset /* - EPSILON */)
- {
- return -1;
- }
- else if (coord > offset /* + EPSILON */)
- {
- return 1;
- }
- else
- {
- return 0;
- }
-}
-
-
-void kd_tree_dynamic::do_split(
- int* back_end,
- int* front_end,
- int face_count,
- face faces[],
- int axis,
- float neg_offset,
- float pos_offset)
-// Classify the given faces as either negative or positive. The faces
-// within faces[] are shuffled. On exit, the faces[] array has the
-// following segments:
-//
-// [0, *neg_end-1] -- the faces behind the plane axis=neg_offset
-// [neg_end, face_count-1] -- the faces in front of axis=pos_offset (i.e.
everything else)
-//
-// pos_offset must be placed so that it catches everything not on the
-// negative side; this routine asserts against that.
-{
- // We do an in-place sort. During sorting, faces[] is divided
- // into three segments: at the beginning are the front faces,
- // in the middle are the unsorted faces, and at the end are
- // the back faces. when we sort a face, we swap it into the
- // next position for either the back or front face segment.
- int back_faces_end = 0;
- int front_faces_start = face_count;
- //int next_face = 0;
-
- while (back_faces_end < front_faces_start)
- {
- const face& f = faces[back_faces_end];
-
- int result = classify_face(f, axis, neg_offset);
- if (result == -1)
- {
- // Behind. Leave this face where it is, and
- // bump back_faces_end so it's now in the back
- // faces segment.
- back_faces_end++;
- }
- else
- {
- // In front.
- assert(f.get_min_coord(axis, m_verts) >= pos_offset);
// should not have any crossing faces!
-
- // Swap this face up to the beginning of the front
faces.
- front_faces_start--;
- swap(&faces[back_faces_end], &faces[front_faces_start]);
- }
- }
-
- *back_end = back_faces_end;
- *front_end = face_count;
- assert(*back_end <= *front_end);
- assert(*front_end == face_count);
-
-#if 0
- std::vector<face> back_faces;
- std::vector<face> front_faces;
-
- for (int i = 0; i < face_count; i++)
- {
- const face& f = faces[i];
-
- int result = classify_face(f, axis, neg_offset);
- if (result == -1)
- {
- // Behind.
- back_faces.push_back(f);
- }
- else
- {
- assert(f.get_min_coord(axis, m_verts) >= pos_offset);
// should not have any crossing faces!
-
- front_faces.push_back(f);
- }
- }
-
- assert(back_faces.size() + front_faces.size() == face_count);
-
- *back_end = back_faces.size();
- if (back_faces.size() > 0)
- {
- memcpy(&(faces[0]), &(back_faces[0]), back_faces.size() *
sizeof(faces[0]));
- }
-
- *front_end = *back_end + front_faces.size();
- if (front_faces.size() > 0)
- {
- memcpy(&faces[*back_end], &front_faces[0], front_faces.size() *
sizeof(faces[0]));
- }
-
- assert(*back_end <= *front_end);
- assert(*front_end == face_count);
-#endif // 0
-}
-
-
-float kd_tree_dynamic::evaluate_split(
- int /* depth */,
- int face_count,
- face faces[],
- const axial_box& bounds,
- int axis,
- float neg_offset,
- float* pos_offset)
-// Compute the "value" of splitting the given set of faces, bounded by
-// the given box, along the plane [axis]=offset. A value of 0 means
-// that a split is possible, but has no value. A negative value means
-// that the split is not valid at all. Positive values indicate
-// increasing goodness.
-//
-// *pos_offset is computed based on the minimum coord of the faces
-// that don't fit behind the neg_offset. Could be greater or less
-// than neg_offset.
-//
-// This is kinda heuristicy -- it's where the "special sauce" comes
-// in.
-{
- // Count the faces that will end up in the groups
- // back,front.
- int back_count = 0;
- int front_count = 0;
-
- *pos_offset = bounds.get_max()[axis];
-
- for (int i = 0; i < face_count; i++)
- {
- const face& f = faces[i];
-
- int result = classify_face(f, axis, neg_offset);
- if (result == -1)
- {
- // Neg.
- back_count++;
- }
- else
- {
- // Pos.
- front_count++;
-
- // Update *pos_offset so it contains this face.
- float mincoord = f.get_min_coord(axis, m_verts);
- if (mincoord < *pos_offset)
- {
- *pos_offset = mincoord;
- assert(mincoord >= bounds.get_min()[axis]);
- }
- }
- }
-
- if ((back_count == 0 && *pos_offset - EPSILON <= bounds.get_min()[axis])
- || (front_count == 0 && neg_offset + EPSILON >=
bounds.get_max()[axis]))
- {
- // No faces are separated by this split; this split is
- // entirely useless.
- return -1;
- }
-
- //float center = bounds.get_center().get(axis);
- //float extent = bounds.get_extent().get(axis);
-
- axial_box back_bounds(bounds);
- back_bounds.set_axis_max(axis, neg_offset);
- axial_box front_bounds(bounds);
- front_bounds.set_axis_min(axis, *pos_offset);
-
-// Probably not a win.
-#ifdef CARVE_OFF_SPACE
- // Special case: if the plane carves off space at one side or the
- // other, without orphaning any faces, then we reward a large
- // empty space.
- float space_quality = 0.0f;
- if (front_count == 0)
- {
- // All the faces are in back -- reward a bigger empty front
volume.
- return space_quality = back_count *
front_bounds.get_surface_area();
- }
- else if (back_count == 0)
- {
- // All the faces are in front.
- return space_quality = front_count *
back_bounds.get_surface_area();
- }
-#endif // CARVE_OFF_SPACE
-
-
-// My ad-hoc metric
-#ifdef ADHOC_METRIC
- // compute a figure for how close to the center this splitting
- // plane is. Normalize in [0,1].
- float volume_balance = 1.0f - fabsf(center - (neg_offset +
*pos_offset) / 2) / extent;
-
- // Compute a figure for how well we balance the faces. 0 == bad,
- // 1 == good.
- float face_balance = 1.0f - (fabsf(float(front_count - back_count)))
/ face_count;
-
- float split_quality = bounds.get_surface_area() * volume_balance *
face_balance;
-
- return split_quality;
-#endif // ADHOC_METRIC
-
-
-#ifdef MACDONALD_AND_BOOTH_METRIC
- // MacDonald and Booth's metric, as quoted by Havran, endorsed by
- // Ville Miettinen and Atman Binstock:
-
- float cost_back = back_bounds.get_surface_area() * (back_count);
- float cost_front = front_bounds.get_surface_area() * (front_count);
-
- float havran_cost = cost_back + cost_front;
-
- float parent_cost = bounds.get_surface_area() * face_count;
-
- // We need to turn the cost into a quality, so subtract it from a
- // big number.
- return parent_cost - havran_cost;
-
-#endif // MACDONALD_AND_BOOTH_METRIC
-}
-
-
-int kd_tree_dynamic::classify_face(const face& f, int axis, float offset)
-// Return -1 if the face is entirely behind the plane [axis]=offset
-// Return 0 if the face spans the plane.
-// Return 1 if the face is entirely in front of the plane.
-//
-// "behind" means on the negative side, "in front" means on the
-// positive side.
-{
- assert(axis >= 0 && axis < 3);
-
- bool has_front_vert = false;
- bool has_back_vert = false;
-
- for (int i = 0; i < 3; i++)
- {
- float coord = m_verts[f.m_vi[i]].get(axis);
- int cr = classify_coord(coord, offset);
-
- if (cr == -1)
- {
- has_back_vert = true;
- }
- else if (cr == 1)
- {
- has_front_vert = true;
- }
- }
-
- if (has_front_vert && has_back_vert)
- {
- return 0; // crossing.
- }
- else if (has_front_vert)
- {
- return 1; // all verts in front.
- }
- else if (has_back_vert)
- {
- return -1; // all verts in back.
- }
- else
- {
- // Face is ON the plane.
- return 0; // call it "crossing".
- }
-}
-
-
-void kd_tree_dynamic::clip_faces(std::vector<face>* faces, int axis, float
offset)
-// Clip the given faces against the plane [axis]=offset. Update the
-// *faces array with the newly clipped faces; add faces and verts as
-// necessary.
-{
- int original_face_count = faces->size();
-
- for (int i = 0; i < original_face_count; i++)
- {
- face f = (*faces)[i];
-
- if (classify_face(f, axis, offset) == 0)
- {
- // Crossing face, probably needs to be clipped.
-
- int vr[3];
- vr[0] = classify_coord(m_verts[f.m_vi[0]].get(axis),
offset);
- vr[1] = classify_coord(m_verts[f.m_vi[1]].get(axis),
offset);
- vr[2] = classify_coord(m_verts[f.m_vi[2]].get(axis),
offset);
-
- // Sort...
- if (vr[0] > vr[1])
- {
- swap(&vr[0], &vr[1]);
- swap(&f.m_vi[0], &f.m_vi[1]);
- }
- if (vr[1] > vr[2])
- {
- swap(&vr[1], &vr[2]);
- swap(&f.m_vi[1], &f.m_vi[2]);
- }
- if (vr[0] > vr[1])
- {
- swap(&vr[0], &vr[1]);
- swap(&f.m_vi[0], &f.m_vi[1]);
- }
-
- if (vr[0] == 0 || vr[2] == 0)
- {
- // Face doesn't actually cross; no need to clip.
- continue;
- }
-
- const vec3 v[3] = {
- m_verts[f.m_vi[0]],
- m_verts[f.m_vi[1]],
- m_verts[f.m_vi[2]]
- };
-
- // Different cases.
- if (vr[1] == 0)
- {
- // Middle vert is on the plane; make two
triangles.
-
- // One new vert.
- float lerper = (offset - v[0].get(axis)) /
(v[2].get(axis) - v[0].get(axis));
- vec3 new_vert = v[0] * (1 - lerper) + v[2] *
lerper;
- new_vert.set(axis, offset); // make damn
sure
- assert(new_vert.checknan() == false);
-
- int new_vi = m_verts.size();
- m_verts.push_back(new_vert);
-
- // New faces.
- face f0 = f;
- f0.m_vi[2] = new_vi;
- (*faces)[i] = f0; // replace original face
-
- assert(classify_face(f0, axis, offset) <= 0);
-
- face f1 = f;
- f1.m_vi[0] = new_vi;
- faces->push_back(f1); // add a face
-
- assert(classify_face(f1, axis, offset) >= 0);
- }
- else if (vr[1] < 0)
- {
- // Middle vert is behind the plane.
- // Make two tris behind, one in front.
-
- // Two new verts.
- float lerper0 = (offset - v[0].get(axis)) /
(v[2].get(axis) - v[0].get(axis));
- vec3 new_vert0 = v[0] * (1 - lerper0) + v[2]
* lerper0;
- new_vert0.set(axis, offset); // make damn
sure
- assert(new_vert0.checknan() == false);
- int new_vi0 = m_verts.size();
- m_verts.push_back(new_vert0);
-
- float lerper1 = (offset - v[1].get(axis)) /
(v[2].get(axis) - v[1].get(axis));
- vec3 new_vert1 = v[1] * (1 - lerper1) + v[2]
* lerper1;
- new_vert1.set(axis, offset); // make damn
sure
- assert(new_vert1.checknan() == false);
- int new_vi1 = m_verts.size();
- m_verts.push_back(new_vert1);
-
- // New faces.
- face f0 = f;
- f0.m_vi[2] = new_vi0;
- (*faces)[i] = f0;
-
- assert(classify_face(f0, axis, offset) <= 0);
-
- face f1 = f;
- f1.m_vi[0] = new_vi0;
- f1.m_vi[2] = new_vi1;
- faces->push_back(f1);
-
- assert(classify_face(f1, axis, offset) <= 0);
-
- face f2 = f;
- f2.m_vi[0] = new_vi0;
- f2.m_vi[1] = new_vi1;
- faces->push_back(f2);
-
- assert(classify_face(f2, axis, offset) >= 0);
- }
- else if (vr[1] > 0)
- {
- // Middle vert is in front of the plane.
- // Make on tri behind, two in front.
-
- // Two new verts.
- float lerper1 = (offset - v[0].get(axis)) /
(v[1].get(axis) - v[0].get(axis));
- vec3 new_vert1 = v[0] * (1 - lerper1) + v[1]
* lerper1;
- new_vert1.set(axis, offset); // make damn
sure
- assert(new_vert1.checknan() == false);
- int new_vi1 = m_verts.size();
- m_verts.push_back(new_vert1);
-
- float lerper2 = (offset - v[0].get(axis)) /
(v[2].get(axis) - v[0].get(axis));
- vec3 new_vert2 = v[0] * (1 - lerper2) + v[2]
* lerper2;
- new_vert2.set(axis, offset); // make damn
sure
- assert(new_vert2.checknan() == false);
- int new_vi2 = m_verts.size();
- m_verts.push_back(new_vert2);
-
- // New faces.
- face f0 = f;
- f0.m_vi[1] = new_vi1;
- f0.m_vi[2] = new_vi2;
- (*faces)[i] = f0;
-
- assert(classify_face(f0, axis, offset) <= 0);
-
- face f1 = f;
- f1.m_vi[0] = new_vi1;
- f1.m_vi[2] = new_vi2;
- faces->push_back(f1);
-
- assert(classify_face(f1, axis, offset) >= 0);
-
- face f2 = f;
- f2.m_vi[0] = new_vi2;
- faces->push_back(f2);
-
- assert(classify_face(f2, axis, offset) >= 0);
- }
- }
-
- }
-}
-
-
-void kd_tree_dynamic::dump(tu_file* out) const
-// Dump some debug info.
-{
- node* n = m_root;
-
- if (n) n->dump(out, 0);
-}
-
-
-void kd_tree_dynamic::node::dump(tu_file* out, int depth) const
-{
- for (int i = 0; i < depth; i++) { out->write_byte(' '); }
-
- if (m_leaf)
- {
- int face_count = m_leaf->m_faces.size();
- char c = ("0123456789X")[iclamp(face_count, 0, 10)];
- out->write_byte(c);
- out->write_byte('\n');
- }
- else
- {
- out->write_byte('+');
- out->write_byte('\n');
- if (m_neg)
- {
- m_neg->dump(out, depth + 1);
- }
- if (m_pos)
- {
- m_pos->dump(out, depth + 1);
- }
- }
-}
-
-
-#include "postscript.h"
-
-
-static const int X_SIZE = 612;
-static const int Y_SIZE = 792;
-static const int MARGIN = 20;
-
-
-class kd_diagram_dump_info
-{
-public:
- postscript* m_ps;
- int m_depth;
- int m_max_depth;
- std::vector<int> m_width; // width of the tree at each
level
- std::vector<int> m_max_width;
- std::vector<int> m_count; // width so far, during drawing
-
- // Some stats.
- int m_leaf_count;
- int m_node_count;
- int m_face_count;
- int m_max_faces_in_leaf;
- int m_null_children;
- int m_depth_times_faces;
-
- kd_diagram_dump_info()
- :
- m_ps(0),
- m_depth(0),
- m_max_depth(0),
- m_leaf_count(0),
- m_node_count(0),
- m_face_count(0),
- m_max_faces_in_leaf(0),
- m_null_children(0),
- m_depth_times_faces(0)
- {
- }
-
- void get_node_coords(int* x, int* y)
- {
- float h_spacing = (X_SIZE - MARGIN*2) /
float(m_max_width.back());
- float adjust = 1.0f;
- if (m_width[m_depth] > 1) adjust = (m_max_width[m_depth] + 1) /
float(m_width[m_depth] + 1);
-
- *x = int(X_SIZE/2 + (m_count[m_depth] - m_width[m_depth] / 2) *
h_spacing * adjust);
- *y = Y_SIZE - MARGIN - m_depth * (Y_SIZE - MARGIN*2) /
(m_max_depth + 1);
- }
-
- void update_stats(kd_tree_dynamic::node* n)
- // Add this node's stats to our totals.
- {
- if (n == 0)
- {
- m_null_children++;
- }
- else if (n->m_leaf)
- {
- m_leaf_count++;
-
- assert(n->m_leaf);
- int faces = n->m_leaf->m_faces.size();
- m_face_count += faces;
- if (faces > m_max_faces_in_leaf) m_max_faces_in_leaf =
faces;
-
- m_depth_times_faces += (m_depth + 1) * faces;
- }
- else
- {
- m_node_count++;
- }
- }
-
- void diagram_stats()
- // Print some textual stats to the given Postscript stream.
- {
- float x = MARGIN;
- float y = Y_SIZE - MARGIN;
- const float LINE = 10;
- y -= LINE; m_ps->printf(x, y, "Loose KD-Tree");
-#ifdef MACDONALD_AND_BOOTH_METRIC
- y -= LINE; m_ps->printf(x, y, "using MacDonald and Booth
metric");
-#endif
-#ifdef ADHOC_METRIC
- y -= LINE; m_ps->printf(x, y, "using ad-hoc metric");
-#endif
-#ifdef CARVE_OFF_SPACE
- y -= LINE; m_ps->printf(x, y, "using carve-off-space
heuristic");
-#endif
- y -= LINE; m_ps->printf(x, y, "leaf face count limit: %d",
LEAF_FACE_COUNT);
- y -= LINE; m_ps->printf(x, y, "face ct: %d", m_face_count);
- y -= LINE; m_ps->printf(x, y, "leaf ct: %d", m_leaf_count);
- y -= LINE; m_ps->printf(x, y, "node ct: %d", m_node_count);
- y -= LINE; m_ps->printf(x, y, "null ct: %d", m_null_children);
- y -= LINE; m_ps->printf(x, y, "worst leaf: %d faces",
m_max_faces_in_leaf);
- y -= LINE; m_ps->printf(x, y, "max depth: %d", m_max_depth + 1);
- y -= LINE; m_ps->printf(x, y, "avg face depth: %3.2f",
m_depth_times_faces / float(m_face_count));
- }
-};
-
-
-static void node_traverse(kd_diagram_dump_info* inf, kd_tree_dynamic::node*
n)
-// Traverse the tree, updating inf->m_width. That's helpful for
-// formatting the diagram.
-{
- inf->update_stats(n);
-
- if (inf->m_depth > inf->m_max_depth)
- {
- inf->m_max_depth = inf->m_depth;
- }
-
- while ((int) inf->m_width.size() <= inf->m_max_depth)
- {
- inf->m_width.push_back(0);
- }
-
- inf->m_width[inf->m_depth]++; // count this node.
-
- if (n && n->m_leaf == 0)
- {
- // Count children.
- inf->m_depth++;
- node_traverse(inf, n->m_neg);
- node_traverse(inf, n->m_pos);
- inf->m_depth--;
-
- assert(inf->m_depth >= 0);
- }
-}
-
-
-static void node_diagram(kd_diagram_dump_info* inf, kd_tree_dynamic::node*
n, int parent_x, int parent_y)
-// Emit Postscript drawing commands to diagram this node in the tree.
-{
- // Diagram this node.
- int x, y;
- inf->get_node_coords(&x, &y);
-
- // Line to parent.
- inf->m_ps->line((float) x, (float) y, (float) parent_x, (float)
parent_y);
-
- if (n == 0)
- {
- // NULL --> show a circle w/ slash
- inf->m_ps->circle((float) x, (float) y, 1);
- inf->m_ps->line((float) x + 1, (float) y + 1, (float) x - 1,
(float) y - 1);
- }
- else if (n->m_leaf)
- {
- // Leaf. Draw concentric circles.
- int face_count = n->m_leaf->m_faces.size();
- for (int i = 0; i < face_count + 1; i++)
- {
- inf->m_ps->circle((float) x, (float) y, 2 + i * 1.0f);
- }
- }
- else
- {
- // Internal node.
-
- // draw disk
- inf->m_ps->disk((float) x, (float) y, 1);
-
- // draw children.
- inf->m_depth++;
- node_diagram(inf, n->m_neg, x, y);
- node_diagram(inf, n->m_pos, x, y);
- inf->m_depth--;
-
- assert(inf->m_depth >= 0);
- }
-
- // count this node.
- inf->m_count[inf->m_depth]++;
-}
-
-
-void kd_tree_dynamic::diagram_dump(tu_file* out) const
-// Generate a Postscript schematic diagram of the tree.
-{
- postscript* ps = new postscript(out, "kd-tree diagram");
-
- kd_diagram_dump_info inf;
- inf.m_ps = ps;
- inf.m_depth = 0;
-
- node_traverse(&inf, m_root);
-
- while ((int) inf.m_count.size() <= inf.m_max_depth)
- {
- inf.m_count.push_back(0);
- }
-
- int max_width = 1;
- for (int i = 0; i <= inf.m_max_depth; i++)
- {
- if (inf.m_width[i] > max_width)
- {
- max_width = inf.m_width[i];
- }
- inf.m_max_width.push_back(max_width);
- }
-
- inf.diagram_stats();
-
- int root_x = 0, root_y = 0;
- inf.get_node_coords(&root_x, &root_y);
-
- node_diagram(&inf, m_root, root_x, root_y);
-
- delete ps;
-}
-
-
-static void mesh_node_dump(
- postscript* ps,
- int axis,
- kd_tree_dynamic::node* node,
- const axial_box& bound,
- const std::vector<vec3>& verts)
-// Draw faces under node, projected onto given axis plane. Scale to fit paper.
-{
- if (node == NULL) return;
-
- if (node->m_leaf)
- {
- // Draw faces.
- for (int i = 0, n = node->m_leaf->m_faces.size(); i < n; i++)
- {
- vec3 v[3] = {
- verts[node->m_leaf->m_faces[i].m_vi[0]],
- verts[node->m_leaf->m_faces[i].m_vi[1]],
- verts[node->m_leaf->m_faces[i].m_vi[2]]
- };
-
- float x[3], y[3];
- int axis1 = (axis + 1) % 3;
- int axis2 = (axis + 2) % 3;
- for (int vert = 0; vert < 3; vert++)
- {
- x[vert] = (v[vert][axis1] -
bound.get_min()[axis1]) / bound.get_size()[axis1];
- y[vert] = (v[vert][axis2] -
bound.get_min()[axis2]) / bound.get_size()[axis2];
-
- x[vert] = flerp(float(MARGIN), float(X_SIZE -
MARGIN), x[vert]);
- y[vert] = flerp(float(MARGIN), float(Y_SIZE -
MARGIN), y[vert]);
- }
-
- // Draw triangle.
- ps->line(x[0], y[0], x[1], y[1]);
- ps->line(x[1], y[1], x[2], y[2]);
- ps->line(x[2], y[2], x[0], y[0]);
- }
-
- return;
- }
-
- mesh_node_dump(ps, axis, node->m_neg, bound, verts);
- mesh_node_dump(ps, axis, node->m_pos, bound, verts);
-}
-
-
-void kd_tree_dynamic::mesh_diagram_dump(tu_file* out, int axis) const
-// Generate a Postscript schematic diagram of the mesh, orthogonal to
-// the given axis.
-{
- postscript* ps = new postscript(out, "kd-tree diagram");
-
- mesh_node_dump(ps, axis, m_root, get_bound(), m_verts);
-
- delete ps;
-}
-
-
-// Local Variables:
-// mode: C++
-// c-basic-offset: 8
-// tab-width: 8
-// indent-tabs-mode: t
-// End:
Index: libgeometry/kd_tree_dynamic.h
===================================================================
RCS file: libgeometry/kd_tree_dynamic.h
diff -N libgeometry/kd_tree_dynamic.h
--- libgeometry/kd_tree_dynamic.h 26 Aug 2006 00:35:21 -0000 1.6
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,151 +0,0 @@
-// kd_tree_dynamic.h -- by Thatcher Ulrich <address@hidden>
-
-// This source code has been donated to the Public Domain. Do
-// whatever you want with it.
-
-// Data structure for building a kd-tree from a triangle mesh.
-
-
-#ifndef KD_TREE_DYNAMIC_H
-#define KD_TREE_DYNAMIC_H
-
-
-#include "container.h"
-#include "geometry.h"
-#include "axial_box.h"
-
-
-class tu_file;
-class kd_diagram_dump_info;
-
-
-class kd_tree_dynamic
-{
-public:
- // Build tree(s) from the given mesh.
- static void build_trees(
- std::vector<kd_tree_dynamic*>* treelist,
- int vert_count,
- const vec3 verts[],
- int triangle_count,
- const int indices[]
- );
-
- // vert count must be under 64K
- kd_tree_dynamic(
- int vert_count,
- const vec3 verts[],
- int triangle_count,
- const int indices[]
- );
- ~kd_tree_dynamic();
-
- struct face
- {
- uint16_t m_vi[3]; // indices of verts
- uint16_t m_flags;
-
- float get_min_coord(int axis, const std::vector<vec3>& verts)
const;
- float get_max_coord(int axis, const std::vector<vec3>& verts)
const;
- };
-
- struct leaf
- {
- std::vector<face> m_faces;
- };
-
- // Internal node. Not too tidy; would use unions etc. if it were
- // important.
- //
- // This is a "loose" kdtree in the sense that there are two
- // independent splitting planes on the chosen axis. This
- // ensures that all faces can be classified onto one side or
- // the other. Almost the same as a binary AABB tree.
- //
- // | |
- // +--------------+---+----------------+
- // | / / \ | |/ -- \ |
- // | / / \+---/ \ \ |
- // | | --- \ | /|--\ \ / |
- // | | \ -- | / | \ / ---|
- // +--------------+---+----------------+
- // | |
- // axis *--> + neg pos
- //
- // So the idea here is that the neg node contains all faces
- // that are strictly on the negative side of the neg_offset,
- // and the pos node has all the rest of the faces, and the
- // pos_offset is placed so that all the pos node faces are
- // strictly on the positive side of pos_offset.
- //
- // Note that the pos and neg nodes could overlap, or could be
- // disjoint.
- struct node
- {
- node* m_neg;
- node* m_pos;
- leaf* m_leaf;
- int m_axis; // split axis: 0 = x, 1 = y, 2 = z
- float m_neg_offset; // where the back split occurs
- float m_pos_offset; // where the front split occurs
-
- node();
- ~node();
- bool is_valid() const;
- void dump(tu_file* out, int depth) const;
- };
-
- const std::vector<vec3>& get_verts() const { return m_verts; }
- const node* get_root() const { return m_root; }
- const axial_box& get_bound() const { return m_bound; }
-
- // For debugging/evaluating.
- void dump(tu_file* out) const;
- void diagram_dump(tu_file* out) const; // make a Postscript
diagram.
- void mesh_diagram_dump(tu_file* out, int axis) const; // make
a Postscript diagram of the mesh data.
-
-private:
- static void compute_actual_bounds(axial_box* result, int
vert_count, const vec3 verts[]);
-
- void compute_actual_bounds(axial_box* result, int face_count, face
faces[]);
- node* build_tree(int depth, int face_count, face faces[], const
axial_box& bounds);
-
- void do_split(
- int* neg_end,
- int* pos_end,
- int face_count,
- face faces[],
- int axis,
- float neg_offset,
- float pos_offset);
-
- float evaluate_split(
- int depth,
- int face_count,
- face faces[],
- const axial_box& bounds,
- int axis,
- float neg_offset,
- float* pos_offset);
-
- int classify_face(const face& f, int axis, float offset);
-
- // Utility, for testing a clipping non-loose kdtree. Duping
- // is probably much preferable to clipping though.
- void clip_faces(std::vector<face>* faces, int axis, float offset);
-
- std::vector<vec3> m_verts;
- node* m_root;
- axial_box m_bound;
-};
-
-
-#endif // KD_TREE_DYNAMIC_H
-
-
-// Local Variables:
-// mode: C++
-// c-basic-offset: 8
-// tab-width: 8
-// indent-tabs-mode: t
-// End:
Index: libgeometry/kd_tree_packed.cpp
===================================================================
RCS file: libgeometry/kd_tree_packed.cpp
diff -N libgeometry/kd_tree_packed.cpp
--- libgeometry/kd_tree_packed.cpp 30 Oct 2007 18:55:41 -0000 1.12
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,639 +0,0 @@
-// kd_tree_packed.cpp -- by Thatcher Ulrich <address@hidden>
-
-// This source code has been donated to the Public Domain. Do
-// whatever you want with it.
-
-// packed kd-tree structure for accelerated collision queries
-// vs. static triangle soup
-
-
-#include "kd_tree_packed.h"
-
-#include "tu_file.h"
-#include "tu_types.h"
-#include "utility.h"
-#include "axial_box.h"
-#include "kd_tree_dynamic.h"
-
-using namespace std;
-
-#if 0
-
-
-struct ray_test_result;
-struct ray_test_query;
-
-
-class kd_tree_packed::node_chunk
-{
-public:
- void ray_test(
- ray_test_result* result,
- const ray_test_query& query,
- const axial_box& node_bound,
- int node_idx = 0) const;
-
- void get_child(const node_chunk** child, int* child_idx, int idx,
int which_child) const;
-
-private:
- struct leaf;
-
- // Kudos to Christer Ericson for the sweet packed node union.
- union node
- {
- float m_plane; // axis is packed into low 2 bits.
01==x, 02==y, 03==z
- int m_leaf_offset; // if low 2 bits == 00 then this is an
offset into the leaf array
-
- // @@ can unions have member functions? MSVC says yes...
-
- bool is_leaf() const { return (m_leaf_offset & 3) == 00; }
- const leaf* get_leaf() const { return (const leaf*)
(((const char*) this) + m_leaf_offset); }
-
- int get_axis() const
- {
- assert(is_leaf() == false);
- return (m_leaf_offset & 3) - 1;
- }
-
- float get_plane_offset() const
- {
- // @@ should we mask off bottom bits? Or leave them
alone?
- return m_plane;
- }
- };
-
- node m_nodes[13]; // interior nodes
- int m_first_child_offset; // offset of first child chunk,
relative to the head of this struct
- int m_child_offset_bits; // 1 bit for each existing
breadth-first child
-};
-
-
-void kd_tree_packed::node_chunk::ray_test(
- ray_test_result* result,
- const ray_test_query& query,
- const axial_box& node_bound,
- int node_idx /* = 0 */) const
-// Ray test against the node_idx'th node in this chunk.
-{
- assert(node_idx >= 0 && node_idx < 13);
-
- const node& n = m_nodes[node_idx];
- if (n.is_leaf())
- {
-//x n.get_leaf()->ray_test(result, query);
- }
- else
- {
- int axis = n.get_axis();
- float plane_offset = n.get_plane_offset();
-
- const node_chunk* chunk;
- int child_idx;
-
- // crossing node always gets queried.
- get_child(&chunk, &child_idx, node_idx, 0);
- chunk->ray_test(result, query, node_bound, child_idx);
-
- // cut the ray at plane_offset
-
- axial_box child_box(node_bound);
-
- // if query reaches front child
- child_box.set_axis_min(axis, plane_offset);
- get_child(&chunk, &child_idx, node_idx, 1);
- chunk->ray_test(result, query, child_box, child_idx);
-
- // if query reaches back child
- child_box = node_bound;
- child_box.set_axis_max(axis, plane_offset);
- get_child(&chunk, &child_idx, node_idx, 2);
- chunk->ray_test(result, query, child_box, child_idx);
- }
-}
-
-
-
-#endif // 0
-
-
-
-//
-// straightforward impl
-//
-
-
-struct kd_face
-{
- uint16_t m_vi[3]; // vert indices
-
-// void local_assert() { compiler_assert(sizeof(struct kd_face) == 6); }
-};
-
-
-struct kd_leaf
-{
- uint8_t m_flags; // low two bits == 0b11
- uint8_t m_face_count;
-
- kd_face* get_face(int index)
- {
- assert(index >= 0 && index < m_face_count);
-
- return (kd_face*) (((uint8_t*) this) + sizeof(struct kd_leaf) +
sizeof(kd_face) * index);
- }
-
-// void local_assert() { compiler_assert(sizeof(struct kd_leaf) == 2); }
-};
-
-
-// TODO I believe it may be better for cache usage to store the leaf
-// array separately from the kd tree nodes. The reasoning is, when
-// traversing, the two child nodes of a parent can be adjacent in
-// memory, so if the first child is rejected, the second child is
-// (likely) already in cache.
-//
-// The node layout changes: siblings are always stored together, so
-// the child offset points to both children and the neg child is not
-// immediately after the parent. IIRC this is what both Opcode and
-// OpenRT do, and they both have clues.
-//
-// (Also, obviously, need to try aligning this class.)
-
-class kd_node
-{
-public:
- uint8_t m_flags[4];
- // low two bits == axis, if axis == 3 then this is leaf.
- // 0x04 is set if the neg child is present.
- // 0x08 is set if the pos child is present
- // m_flags[1..3] is the offset to the pos child, little-endian.
-
- float m_neg_offset;
- float m_pos_offset;
-
- kd_leaf* get_leaf() { assert(is_leaf()); return (kd_leaf*) this;
}
- bool is_leaf() const { return (m_flags[0] & 3) == 3; }
- int get_axis() const { return (m_flags[0] & 3); }
-
- bool has_neg_child() const { return (m_flags[0] & 4) ? true : false;
}
- bool has_pos_child() const { return (m_flags[0] & 8) ? true : false;
}
-
- kd_node* get_neg_child()
- {
- if (has_neg_child())
- {
- // Neg child follows immediately.
- return (kd_node*) (((uint8_t*) this) + sizeof(kd_node));
- }
- else return NULL;
- }
-
- kd_node* get_pos_child()
- {
- if (has_pos_child())
- {
- unsigned int offset = (m_flags[1]) + (m_flags[2] << 8)
+ (m_flags[3] << 16);
- assert(offset >= sizeof(kd_node)); // sanity check
-
- return (kd_node*) (((uint8_t*) this) + offset);
- }
- else return NULL;
- }
-
-
- void local_assert() { compiler_assert(sizeof(kd_node) == 12); }
-};
-
-
-kd_tree_packed::kd_tree_packed()
- :
- m_vert_count(0),
- m_verts(0),
- m_packed_tree_size(0),
- m_packed_tree(0)
-{
-}
-
-
-kd_tree_packed::~kd_tree_packed()
-{
- if (m_verts)
- {
- tu_free(m_verts, sizeof(vec3) * m_vert_count);
- }
-
- if (m_packed_tree)
- {
- tu_free(m_packed_tree, m_packed_tree_size);
- }
-}
-
-
-static void write_packed_data(tu_file* out, const kd_tree_dynamic::node*
source)
-// Write kd tree data in the form of packed node & leaf structs.
-{
- if (source->m_leaf)
- {
- // leaf case.
- assert(source->m_neg == NULL);
- assert(source->m_pos == NULL);
-
- kd_tree_dynamic::leaf* sl = source->m_leaf;
- assert(sl);
-
- kd_leaf l;
- l.m_flags = 3; // mark this as a leaf
- if (sl->m_faces.size() > 255)
- {
- // problem.
- abort();
- l.m_face_count = 255;
- }
- else
- {
- l.m_face_count = sl->m_faces.size();
- }
- out->write_bytes(&l, sizeof(l));
-
- // write faces.
- for (int i = 0; i < l.m_face_count; i++)
- {
- kd_face f;
- f.m_vi[0] = sl->m_faces[i].m_vi[0];
- f.m_vi[1] = sl->m_faces[i].m_vi[1];
- f.m_vi[2] = sl->m_faces[i].m_vi[2];
- out->write_bytes(&f, sizeof(f));
- }
- }
- else
- {
- // node case.
-
- kd_node n;
-
- n.m_neg_offset = source->m_neg_offset;
- n.m_pos_offset = source->m_pos_offset;
-
- n.m_flags[0] = source->m_axis;
- n.m_flags[1] = 0;
- n.m_flags[2] = 0;
- n.m_flags[3] = 0;
- if (source->m_neg)
- {
- n.m_flags[0] |= 4; // neg child present.
- }
- if (source->m_pos)
- {
- n.m_flags[0] |= 8; // pos child present.
- }
-
- // Remember where our flags are, so we can come back
- // and overwrite the pos child offset.
- int flags_start = out->get_position();
-
- // Write node data.
- out->write_bytes(&n, sizeof(n));
-
- // Neg child data.
- if (source->m_neg)
- {
- write_packed_data(out, source->m_neg);
- }
-
- // Pos child data.
- if (source->m_pos)
- {
- int pos_child_start = out->get_position();
- int pos_child_delta = pos_child_start - flags_start;
- if (pos_child_delta >= (1 << 24))
- {
- // Problem.
- abort();
- }
- else
- {
- n.m_flags[1] = (pos_child_delta ) & 0x0FF;
- n.m_flags[2] = (pos_child_delta >> 8 ) & 0x0FF;
- n.m_flags[3] = (pos_child_delta >> 16) & 0x0FF;
- out->set_position(flags_start);
- out->write_bytes(&n.m_flags[0], 4);
- out->set_position(pos_child_start);
-
- // Write pos child.
- write_packed_data(out, source->m_pos);
- }
- }
- }
-}
-
-
-/*static*/ kd_tree_packed* kd_tree_packed::build(const kd_tree_dynamic*
source)
-{
- tu_file buf(tu_file::memory_buffer);
-
- assert(source->get_root());
-
- write_packed_data(&buf, source->get_root());
-
- kd_tree_packed* kd = new kd_tree_packed;
-
- kd->m_bound = source->get_bound();
-
- // Copy vert data.
- kd->m_vert_count = source->get_verts().size();
- assert(kd->m_vert_count < 65536); // we use 16-bit indices for
verts
- kd->m_verts = (vec3*) tu_malloc(kd->m_vert_count * sizeof(vec3));
- memcpy(kd->m_verts, &source->get_verts()[0], sizeof(vec3) *
kd->m_vert_count);
-
- // Copy packed tree data.
- kd->m_packed_tree_size = buf.get_position();
- kd->m_packed_tree = (kd_node*) tu_malloc(kd->m_packed_tree_size);
- buf.set_position(0);
- buf.read_bytes(kd->m_packed_tree, kd->m_packed_tree_size);
-
- return kd;
-}
-
-
-class kd_ray_query_info
-{
-public:
- kd_ray_query_info(const ray_query& query, const vec3* verts, int
vert_count)
- :
- m_query(query),
- m_vert_count(vert_count),
- m_verts(verts)
- {
- }
-
-//data:
- ray_query m_query;
- int m_vert_count;
- const vec3* m_verts;
-
- // other helpful precomputed data?
-};
-
-
-// cbloom code
-static inline float triple_product(const vec3 &a, const vec3 &b, const vec3 &c)
-// a * (b cross c)
-{
- // return Epsilon_ijk A_i B_j C_k
- const float t =
- a.x * (b.y * c.z - b.z * c.y) +
- a.y * (b.z * c.x - b.x * c.z) +
- a.z * (b.x * c.y - b.y * c.x);
- return t;
-}
-
-
-// For crack prevention. This expands the triangle bounds slightly;
-// smaller triangles get more expansion. Needs to be sized big enough
-// so that we don't get cracks on edges between large triangles, but
-// small enough so that small triangles don't get expanded too much.
-static double INTERSECT_EPSILON = 1e-4;
-
-
-// Does not do any checking of t value (time ray crosses plane)
-// Haines-Moller with cbloom tweaks
-static bool intersect_triangle(
- const vec3& orig, const vec3& dir,
- const vec3& vert0, const vec3& /* vert1 */, const vec3& /* vert2 */,
- const vec3& edge1, const vec3& edge2)
-{
- /* begin calculating determinant - also used to calculate U parameter */
- vec3 pvec;
- pvec.set_cross(dir, edge2);
-
- /* if determinant is near zero, ray lies in plane of triangle */
- const float det = fabsf( edge1 * pvec ); // =
vec3U::TripleProduct(dir,edge1,edge2);
-
- /* calculate distance from vert0 to ray origin */
- const vec3 tvec = orig - vert0;
-
- /* calculate U parameter and test bounds */
- const float u = tvec * pvec; // = vec3U::TripleProduct(dir,edge2,tvec);
- if ( u < -INTERSECT_EPSILON || u > det + INTERSECT_EPSILON)
- return false;
-
- /* prepare to test V parameter */
-
- /* calculate V parameter and test bounds */
- const float v = triple_product(dir,tvec,edge1);
- if ( v < -INTERSECT_EPSILON || u + v > det + INTERSECT_EPSILON)
- return false;
-
- return true;
-}
-
-
-// Statistics.
-int kd_tree_packed::s_ray_test_face_count = 0;
-int kd_tree_packed::s_ray_test_leaf_count = 0;
-int kd_tree_packed::s_ray_test_node_count = 0;
-
-
-static bool ray_test_face(const kd_ray_query_info& qi, kd_face* face)
-{
- kd_tree_packed::s_ray_test_face_count++; // stats
-
- assert(face->m_vi[0] < qi.m_vert_count);
- assert(face->m_vi[1] < qi.m_vert_count);
- assert(face->m_vi[2] < qi.m_vert_count);
-
- const vec3& v0 = qi.m_verts[face->m_vi[0]];
- const vec3& v1 = qi.m_verts[face->m_vi[1]];
- const vec3& v2 = qi.m_verts[face->m_vi[2]];
-
- vec3 edge1(v1); edge1 -= v0;
- vec3 edge2(v2); edge2 -= v0;
- vec3 unscaled_normal;
- unscaled_normal.set_cross(edge1, edge2);
-
- float plane_d = v0 * unscaled_normal;
-
- if (qi.m_query.m_start * unscaled_normal < plane_d)
- {
- // ray can't hit face; it starts behind the face.
- return false;
- }
-
- if (qi.m_query.m_end * unscaled_normal > 0)
- {
- // ray doesn't reach the face.
- return false;
- }
-
- // Ray crosses plane of triangle; see if it crosses inside the triangle
bounds.
- return intersect_triangle(qi.m_query.m_start, qi.m_query.m_dir, v0, v1,
v2, edge1, edge2);
-}
-
-
-static bool ray_test_leaf(const kd_ray_query_info& qi, kd_leaf* leaf)
-// Return true if ray subset hits any of our faces.
-{
- kd_tree_packed::s_ray_test_leaf_count++; // stats
-
- for (int i = 0, n = leaf->m_face_count; i < n; i++)
- {
- kd_face* face = leaf->get_face(i);
- if (ray_test_face(qi, face))
- {
- return true;
- }
- }
-
- return false;
-}
-
-
-static bool ray_test_node(const kd_ray_query_info& qi, float t_min, float
t_max, kd_node* node)
-// Return true if the ray (limited to the subset [t_min,t_max], where
-// t is in [0,1]) hits any of our faces.
-{
- assert(node);
-
- if (node->is_leaf())
- {
- // Test the faces.
- return ray_test_leaf(qi, node->get_leaf());
- }
-
- // Node check.
-
- kd_tree_packed::s_ray_test_node_count++; // stats
-
- int axis = node->get_axis();
-
- if (qi.m_query.m_inv_dir[axis] == 0)
- {
- // Query is effectively parallel to splitting plane.
-
- // Does query possibly touch the neg child?
- kd_node* neg_child = node->get_neg_child();
- if (neg_child
- && qi.m_query.m_start[axis] <= node->m_neg_offset)
- {
- // Check neg child.
- if (ray_test_node(qi, t_min, t_max, neg_child))
- {
- return true;
- }
- }
-
- // Does query possibly touch the pos child?
- kd_node* pos_child = node->get_pos_child();
- if (pos_child
- && qi.m_query.m_start[axis] >= node->m_pos_offset)
- {
- // Check pos child.
- if (ray_test_node(qi, t_min, t_max, pos_child))
- {
- return true;
- }
- }
-
- return false;
- }
-
- // Ordinary node check.
-
- if (qi.m_query.m_dir[axis] > 0)
- {
- // Neg child is the near side.
-
- // Handle neg child.
- kd_node* neg_child = node->get_neg_child();
- if (neg_child)
- {
- float t_exit_neg = (node->m_neg_offset -
qi.m_query.m_start[axis])
- * qi.m_query.m_inv_displacement[axis];
-
- if (t_exit_neg >= t_min)
- {
- if (ray_test_node(qi, t_min, fmin(t_exit_neg,
t_max), neg_child))
- {
- return true;
- }
- }
- }
-
- // Handle pos child.
- kd_node* pos_child = node->get_pos_child();
- if (pos_child)
- {
- float t_enter_pos = (node->m_pos_offset -
qi.m_query.m_start[axis])
- * qi.m_query.m_inv_displacement[axis];
-
- if (t_enter_pos <= t_max)
- {
- if (ray_test_node(qi, fmax(t_enter_pos, t_min),
t_max, pos_child))
- {
- return true;
- }
- }
- }
- }
- else
- {
- // Pos child is the near side.
-
- // Handle neg child.
- kd_node* neg_child = node->get_neg_child();
- if (neg_child)
- {
- float t_enter_neg = (node->m_neg_offset -
qi.m_query.m_start[axis])
- * qi.m_query.m_inv_displacement[axis];
-
- if (t_enter_neg <= t_max)
- {
- if (ray_test_node(qi, fmax(t_enter_neg, t_min),
t_max, neg_child))
- {
- return true;
- }
- }
- }
-
- // Handle pos child.
- kd_node* pos_child = node->get_pos_child();
- if (pos_child)
- {
- float t_exit_pos = (node->m_pos_offset -
qi.m_query.m_start[axis])
- * qi.m_query.m_inv_displacement[axis];
-
- if (t_exit_pos >= t_min)
- {
- if (ray_test_node(qi, t_min, fmin(t_exit_pos,
t_max), pos_child))
- {
- return true;
- }
- }
- }
- }
-
- return false;
-}
-
-
-bool kd_tree_packed::ray_test(const ray_query& query)
-// Return true if the ray query hits any of our faces.
-{
- assert(m_packed_tree);
- assert(m_verts);
-
- kd_ray_query_info qi(query, m_verts, m_vert_count);
-
- // @@ Check (and trim?) against bounding box.
-
- return ray_test_node(qi, 0, 1, m_packed_tree);
-}
-
-
-
-// Local Variables:
-// mode: C++
-// c-basic-offset: 8
-// tab-width: 8
-// indent-tabs-mode: t
-// End:
Index: libgeometry/kd_tree_packed.h
===================================================================
RCS file: libgeometry/kd_tree_packed.h
diff -N libgeometry/kd_tree_packed.h
--- libgeometry/kd_tree_packed.h 26 Aug 2006 00:35:21 -0000 1.3
+++ /dev/null 1 Jan 1970 00:00:00 -0000
@@ -1,68 +0,0 @@
-// kd_tree_packed.h -- by Thatcher Ulrich <address@hidden>
-
-// This source code has been donated to the Public Domain. Do
-// whatever you want with it.
-
-// packed kd-tree structure for accelerated collision queries
-// vs. static triangle soup
-
-#ifndef KD_TREE_PACKED_H
-#define KD_TREE_PACKED_H
-
-
-#include "container.h"
-#include "axial_box.h"
-#include "collision.h"
-#include "geometry.h"
-
-
-class tu_file;
-class kd_tree_dynamic;
-class kd_node;
-
-
-class kd_tree_packed
-{
-public:
- ~kd_tree_packed();
-
- void read(tu_file* in);
- void write(tu_file* out);
-
- static kd_tree_packed* build(const kd_tree_dynamic* source_tree);
-
- // Return true if the ray query hits any of our faces.
- bool ray_test(const ray_query& query);
-
- // void lss_test(....);
-
- const axial_box& get_bound() const { return m_bound; }
-
- // statistics.
- static int s_ray_test_face_count;
- static int s_ray_test_leaf_count;
- static int s_ray_test_node_count;
-
-private:
- kd_tree_packed();
-
- //struct node_chunk;
-
- axial_box m_bound;
- int m_vert_count;
- vec3* m_verts;
-
- int m_packed_tree_size;
- kd_node* m_packed_tree;
-};
-
-
-#endif // KD_TREE_PACKED_H
-
-
-// Local Variables:
-// mode: C++
-// c-basic-offset: 8
-// tab-width: 8
-// indent-tabs-mode: t
-// End:
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Gnash-commit] gnash ChangeLog libgeometry/Makefile.am testsui...,
Sandro Santilli <=