Transcript


00:02
okay but at the end of today's class
00:07
we're going to do the course evaluation
00:09
and I'm going to try and finish a little
00:12
bit before our period so that you do
00:15
have time to do the course evaluation
00:18
before you head off to your next class
00:21
alright so today we're going to talk
00:23
about about binary space partitioning
00:27
trees this data structure is it's
00:33
probably one of the most commonly used
00:35
structures in the computer graphics area
00:38
especially in in the gaming industry to
00:41
represent scenes especially those
00:45
portions of a scene that don't change
00:47
and it's probably one of the most
00:50
efficient structures around for for
00:54
rendering say static seams so as people
00:57
change the orientation move from let's
01:00
say one part of this room to another
01:01
part turn around and look in different
01:03
directions you want to be able to show
01:05
what is it that this person is seeing
01:07
and an efficient way to do that is to
01:12
take the part of this room that doesn't
01:15
change so the worlds the location of the
01:17
TVs the desk the chairs and stuff and
01:20
represent that using a BSP tree and then
01:25
you have to handle the objects that move
01:28
using some different structure alright
01:32
so talking about binary space
01:37
partitioning trees said used to store a
01:42
collection of objects in n-dimensional
01:45
space typically if you're looking at
01:48
game operations you looking at three
01:50
dimensional space but depending upon
01:52
your application you may be looking at
01:54
objects in 2d or dimensions more than
01:58
three alright basically you know if one
02:04
just thinks about the concepts that are
02:05
used in a BSP tree we'll see that there
02:08
really aren't any new concepts we've
02:11
seen all the concepts
02:13
when we studied other data structures
02:15
it's basically a binary tree that just
02:19
takes a collection of N or collection of
02:22
objects and divides them up somehow into
02:26
smaller collections and you keep
02:29
dividing your large collection of
02:31
objects into smaller collections till
02:34
each collection ends up having only one
02:36
object in it okay so it's basically a
02:41
recursive decomposition of a collection
02:43
of objects the recursive decomposition
02:46
here is done by using hyperplanes whose
02:51
dimension is 1 less than that of the
02:53
objects you're dealing with okay so you
02:59
have object sitting in D dimensional
03:01
space we're going to take D dimensional
03:04
space and at each level of our binary
03:07
tree cut it up into two parts so for
03:11
example if you're looking at two
03:13
dimensions okay then to chop two
03:15
dimensions into two parts we need to
03:17
take a line okay so you could have a
03:19
line like this which cuts up your two
03:21
dimensions into two parts in general if
03:26
you have D dimensions okay then you'll
03:30
cut D dimensions into two parts using a
03:32
D minus 1 dimensional hyper plane and
03:35
that has an equation that looks like
03:37
this so in two dimensions you have a
03:39
straight line and in three dimensions
03:42
you get what you typically look as a
03:43
plane and the equation of a plane is ax
03:46
plus B Y we'll see y plus some constant
03:49
equals 0 when you break up your space
03:57
into two parts we referred to one part
04:02
as the positive half plane okay this has
04:06
the property that if you let the points
04:09
in this half plane and you plug them
04:11
into the equation of this splitting
04:13
hyperplane your equation or your
04:17
expression turns out to be bigger than 0
04:19
see an example in a moment for two
04:22
dimensions okay the points in this side
04:25
give you an equation or expression value
04:28
that is less than 0 and the points that
04:31
lie on the splitting hyperplane will
04:34
have value equal to 0 ok so when you
04:42
talk about having values above oh bigger
04:45
than 0 and less than 0 see we're
04:47
starting off with an equation that say
04:48
let's say whisk like this if you're
04:49
looking at cutting two dimensions okay
04:52
so got a straight line it's equal to 0
04:54
if I just change this to minus a and
04:56
minus B and minus C I still get a 0 okay
05:00
but now if you take the minus a version
05:03
and you take some point out here and you
05:05
plug it in previously you were getting a
05:08
positive number so now you're going to
05:09
get a negative number okay so we're just
05:11
changing the sign of the coefficients
05:13
you can change the orientation in in the
05:17
sense that what was previously the
05:18
positive half point now becomes the
05:20
negative half plane okay and that's
05:23
important in some representations where
05:27
you want to always arrange say for the
05:30
interior of an object that you're
05:32
representing should be in the left
05:34
sub-tree rather than in the right
05:36
subtree okay so you can accomplish that
05:38
by just changing the sign of the
05:41
coefficients in that hyperplane okay so
05:49
we said in two dimensions the splitting
05:52
hyper plane or the petitioning hyper
05:54
plane is a straight line and when you
06:01
split your space using say a line we're
06:05
going to need to be able to tell which
06:07
are out which of our objects are in the
06:09
positive half space which are in the
06:12
negative half space and which actually
06:14
straddle this splitting hyperplane and
06:20
the way you do that is you start with
06:22
the equation of your splitting of
06:25
partitioning hyperplane so it's a
06:26
straight line and you take all of the
06:31
vertices of the objects you're dealing
06:33
with so you take one object you look at
06:35
all of its vertices and you
06:37
plug in the coordinates of the vertices
06:38
and if all of them have a value that's
06:41
less than zero then the entire object is
06:44
in the left half plane or in the
06:46
negative half plane and if all of them
06:49
are positive it's on the right or the
06:51
positive half plane okay I'm using left
06:53
and right because if it's in the
06:56
negative half plane I'm going to store
06:57
it in the left subtree if it's in the
06:59
positive half plane would store in the
07:00
right subtree okay so so left and right
07:03
a synonymous with negative and positive
07:06
half points if all the points if at all
07:13
the points the equation of the line
07:14
works out to be zero then that object
07:17
lies in the partitioning hyperplane it's
07:23
in that case we'll say that the object
07:25
is coincident with the petitioning
07:27
hyperplane so in the case of two
07:29
dimensions if you are coincident with
07:32
the petitioning hyperplane you have to
07:35
be a straight line if you're not a
07:36
straight line part of you has to be off
07:38
of that petitioning hyperplane okay okay
07:42
so if you take an object the
07:45
possibilities are now here we're looking
07:48
at two dimensions okay so if we take an
07:51
object in two dimensions the
07:52
possibilities of it either lies entirely
07:55
to the left of this line okay on the
07:58
negative part or it lies entirely in the
08:01
positive part or it lies on that line
08:06
and if not any of those then it's got to
08:09
cross the line so some parts on the left
08:11
some parts on the right all right so I
08:19
have an example out here I've got a
08:22
bunch of objects in two dimensions the
08:25
in this case they're all polygons but
08:27
they don't need to be you can have
08:29
objects that are straight lines as well
08:31
okay all right so here I'm using a
08:38
partitioning line which is aligned with
08:40
the y-axis the next example will not
08:44
necessarily have lines aligned within
08:46
axis but they let align the line with
08:49
the y-axis
08:50
the petitioning hyperplane that I'm
08:53
using has the equation X minus 6 equals
08:55
0 or x equals 6 so in this particular
08:59
case the yellow objects lie in the
09:04
negative plane and the green ones lie in
09:09
the positive plane or in the right and
09:11
in the left so if you took any of these
09:16
vertices the coordinates of these and
09:18
plug them into X minus 6 you would get a
09:20
negative number because all of these
09:23
have X less than 6 all of these have X
09:27
bigger than 6 and you get a positive
09:28
number in this case I don't have any
09:32
object that is coincident with the
09:33
petitioning hyperplane all right so
09:39
here's another petitioning done using a
09:45
line that's not aligned with one of the
09:47
axes so the equation of this line is y
09:51
minus X minus 2 equals 0 and again if
09:57
you took the coordinates of the
10:00
endpoints of this triangle and you plug
10:02
them in you would get a positive number
10:06
and if you did that sorry I think you
10:11
get a negative number here yeah okay so
10:14
you get negatives for the ones that on
10:18
this side and if you did it here for the
10:21
ones with the bigger Y values you get
10:23
the positives okay so in this case if I
10:27
was using this is my petitioning line
10:30
then the fellows below this line would
10:35
show up in my left subtree the fellows
10:38
above this line would show up in my
10:39
right subtree ok these fellows will get
10:44
split okay so this part will be in the
10:47
right subtree in this part in the left
10:49
subtree this guy would get split that
10:51
guy would get split and that guy who
10:52
gets split into two pieces
11:00
on a three-dimensional case so I've got
11:07
two objects the yellow one and the green
11:09
one in the back
11:11
and I'm using as a partitioning
11:19
hyperplane this light blue plane and the
11:24
equation of this is just Z equals 2 of
11:28
course you don't have to use an axis
11:30
align plane you could use some odd
11:31
angled plane in which case the equation
11:35
would have a z term a white term in the
11:37
next term here the partitioning
11:45
hyperplane I'm using is coincident with
11:49
this face of that green cube okay so
11:54
it's petitioning these objects into two
11:57
groups one that's behind the plane
11:59
that's the green guy and one that's in
12:01
front of the plane that's the yellow guy
12:08
alright so in space partitioning you
12:13
need to pick a hyperplane to use to
12:17
split the space that you're currently
12:21
dealing with when you split the space
12:25
that you're dealing with some objects
12:27
will lie wholly in the positive part
12:29
some will lie wholly on the negative
12:32
part some will get some will straddle
12:34
and some might lie entirely on the
12:37
splitting hyperplane okay so the data
12:40
structure okay is a binary tree we will
12:44
have a node okay so this node represents
12:48
that whole space the objects that are
12:53
coincident with the splitting hyperplane
12:55
will be stored in that node you also
12:59
store the equation of the splitting
13:01
hyperplane in that node objects that lie
13:07
wholly in the negative
13:10
side will show up in the left sub-tree
13:12
objects that were holding the right side
13:14
will show up in the right subtree and
13:16
then objects astraddle will get cut into
13:21
pieces a piece that lies holding on this
13:23
side showing up in the left subtree
13:25
pieces that like wholly on that side
13:27
show up in the right subtree okay and
13:30
then you recursively handle this
13:34
subspace okay so we'll chop this up into
13:37
two pieces the next level we'll chop
13:39
that up into two pieces okay let's look
13:46
at building a binary space partitioning
13:50
tree for this collection of two
13:52
dimensional objects let's say I choose
13:58
at the root level to partition using
14:01
this line here so that's x equals six
14:10
all right so in the root I'll store the
14:13
equation of this petitioning line in the
14:16
rule that will store any objects that
14:19
are coincident with this the only things
14:21
that can be considered with this really
14:23
are if you have some points that could
14:25
be coincident or if you have some other
14:26
lines okay I don't have either so I
14:31
won't have anything coincident sitting
14:34
in that red node these objects a through
14:39
D will show up in the left subtree those
14:42
objects eat through H will show up on
14:45
the right subtree at the next level I
14:53
will petition these two sub spaces so
14:59
again I need to pick partitioning lines
15:02
so let's suppose that for the left half
15:04
space I pick this blue line and for the
15:08
right half space I think that blue line
15:16
so then in the left subtree for this
15:20
half space I will have a and B okay and
15:25
then you have C and D again whether you
15:29
get a and B here in the left or you get
15:32
a and B in the right depends on how you
15:34
pick the coefficients of this equation
15:36
so depending upon how you pick the
15:40
coefficients of this line here you can
15:43
switch between left and right subtrees
15:48
and when you continue this partitioning
15:51
till I end up with one object in each
15:54
subspace so my blue my four blue
16:00
petitions will get split and again we'll
16:04
need to pick petitioning hyperplanes for
16:07
each of these and you can use different
16:09
hyperplanes in each one so here I'm
16:12
using green foes
16:22
all right so the basic idea is to come
16:27
up with a binary tree that represents
16:31
the objects in your high dimension space
16:35
the binary tree basically recursively
16:40
subdivides space into two pieces at each
16:44
node in that process you may end up
16:48
chopping your objects as well though in
16:50
this example we didn't chop any objects
16:58
all right before going further let's
17:01
just take a look at a couple of the
17:03
common things people do with this kind
17:05
of a structure all right the first one
17:08
is collision detection okay so let's say
17:13
you have a person who's moving in a
17:15
certain direction okay so you think of a
17:18
computer game you've got objects moving
17:20
at high speed in there you'd like to be
17:22
able to tell when an object hits
17:25
something okay
17:27
and you need to detect that fairly fast
17:30
all right so you build a BSP tree of the
17:35
non-moving objects and so you can try
17:39
and optimize that for search and if you
17:44
have other things that move you got to
17:45
handle that with a separate structure
17:48
because this structure is really not
17:50
designed to handle insertions and
17:52
deletions okay so if you want to find
18:00
the first well if you want to find out
18:03
what this person moving in this
18:05
direction okay so this guy is going to
18:07
walk in this direction would like to
18:09
know which object is this fellow going
18:12
to hit okay and so we'd like to trace
18:18
this path and say that you're going to
18:24
hit this object F and you're going to
18:26
hit it at that point to say
18:30
now in order to determine this if you
18:36
look at this drawing of the subspaces we
18:38
know that if this line okay it's an
18:45
object in this space down here okay in
18:49
this if I call this region here okay
18:52
this is a region or a cell if there's
18:54
any object in this region or cell that's
18:57
intersected by this line well that'll be
18:59
the first one okay but this line first
19:01
goes through that region okay
19:05
there's nothing here then this line next
19:07
goes into this region or cell so if
19:09
there's somebody here that's intersected
19:11
well that'll be the one okay if there's
19:14
nobody here
19:15
we'll then the line enters this cell out
19:18
here and our partitioning has arranged
19:22
this so that each of these cells has
19:23
only one object okay so and the logical
19:28
level what I'd like to do is see if this
19:31
line here intersects the object in the
19:33
cell it doesn't okay then I'd like to
19:36
see if this line intersects the object
19:38
and this cell it does and I'm finished
19:42
okay
19:43
and of course you have to do that using
19:45
the tree because the tree is what you
19:46
have you don't really have this picture
19:50
all right so we're going to start at the
19:52
root of the tree okay and here I've got
19:56
the equation of the cut line that was
19:58
used so using that equation I can tell
20:06
whether this fellow is originally on
20:11
this side originally on that side okay
20:15
so using that equation and this guy's
20:18
coordinates I know that this follows on
20:19
this side so if there's a collision with
20:21
anybody on this side I don't need to
20:23
search anybody out here okay all right
20:27
so you're down here now I got to know
20:29
well should I be looking at the cells on
20:31
this side of the cells on that side
20:33
first okay
20:35
so again you have the equation of the
20:36
blue line here okay and
20:41
you can tell that okay
20:43
this path this segment is going to be
20:46
first on the right side and then you're
20:48
going to cross into the left side okay
20:51
so you first go into the right side out
20:53
here okay and then you want to know
20:58
should you be checking here first or
21:00
should you be checking out there so
21:02
again you have to do a comparison with
21:03
this green line to know that first you
21:05
should be looking down here and in fact
21:07
you should not be looking here at all
21:09
because this line has no intersection
21:10
with that so okay so I check this fellow
21:15
first I'll reach a leaf and that's got a
21:18
single object I do an intersection with
21:20
that object in this line and find
21:23
there's no intersection so back up here
21:25
I don't come here because my line has no
21:27
intersection with that cell and you back
21:30
up here and you have an intersection
21:33
with this blue subspace so you have to
21:38
come in down here okay and when you
21:43
check here you have an intersection with
21:45
that subspace but not with that so you
21:46
only need to check this subspace okay so
21:49
that gets you down to this place here
21:51
and here you actually find intersection
21:53
with the object okay all right so
21:58
basically that's how how it works okay
22:01
so you do a check for intersection only
22:09
with the objects in the cells that are
22:12
cut by this line and you find those by
22:15
traversing the tree
22:25
but something else it's commonly done is
22:29
it's maybe just drawing the whole scene
22:32
say so you'd like to be able to say that
22:36
if if the observers out here and you've
22:41
given a line of an angle of vision what
22:45
all does this person see so if these two
22:51
lines define the angle of vision well
22:54
then certainly things that are on this
22:55
side of that line or that side of that
22:57
line are not seen things behind the
22:59
person and not seen but within this
23:05
angle region there are other things that
23:10
I've possibly not seen because they're
23:13
hidden by things in front of them okay
23:16
so if you're looking this way you may
23:17
not see part of this guy because it's
23:21
being occluded so if you project this up
23:23
some of this would not get seen so you'd
23:30
like to be able to draw the part of the
23:33
scene that's actually seen okay and
23:38
basically the way you handle that is by
23:45
starting again at the root okay and you
23:49
say well the observer is sitting in this
23:50
right half plane okay so if you're
23:54
sitting in the right half plane then
23:58
whatever you can see in the right half
24:00
plane cannot be occluded by things that
24:04
are in your line of sight but maybe
24:05
hidden in the other half plane okay so
24:10
you can either say I will draw stuff in
24:15
this region first and then I will draw
24:21
things that can be seen in this region
24:23
in the sense that they're contained in
24:26
in this angle okay but when you're
24:30
drawing something if you already
24:32
illuminated a pixel on your screen you
24:35
will not really Minh ate it
24:37
okay so drawing means eliminating pixels
24:41
so I'll first handle the newer
24:44
half-space then I'll handle the far half
24:48
space and things in the far half space
24:50
will not be allowed to overwrite things
24:52
in the new house space and you do that
24:55
recursively or you can do it the other
25:01
way around which says you'll do the far
25:03
half space first okay and then you'll do
25:07
the near one later and now you can
25:10
overwrite so you don't have to keep
25:12
track of what's been written or it
25:14
hasn't near objects overwrite further
25:18
objects so you can do it front to back
25:22
or back to front drawing and get an
25:27
accurate view okay alright so so the
25:34
most common operations are collision
25:36
detection and just plain drawing of
25:38
scenes once you know the location of the
25:42
viewer and the direction in which you're
25:46
doing the view
25:49
now let's take a look at constructing a
25:54
BSP tree so the constructed tree you
26:02
need to be able to select the
26:04
petitioning hyperplanes
26:06
you need to build to partition objects
26:11
into a petition and to say those that
26:15
fall in the left-half space and those
26:17
that fall in the right-half space of
26:18
course you also may need to partition
26:20
them because they're cut so you need to
26:21
cut them up into pieces well there are
26:34
several strategies for this for
26:39
selection of the petitioning hyperplanes
26:47
one strategy that is used in perhaps the
26:50
most common method to construct BSP's
26:52
common method is Auto partition is that
26:56
you always select a traditional
26:59
hyperplane that is a face of an object
27:02
so if you're dealing with
27:04
two-dimensional objects as here
27:06
you're partitioning line is always one
27:09
of the boundaries of a polygon so for
27:14
example here I've chosen this particular
27:16
boundary there's another possibility you
27:24
pick this edge so you always pick an
27:28
edge of a polygon to do the partitioning
27:35
so that as I said leads to a method
27:38
called Auto partition now even if you
27:44
use this idea okay always pick an edge
27:49
of a polygon you still have to decide
27:52
which edge depending upon which edge you
27:57
pick you can have different results so
28:02
for example if I picked this top edge
28:04
out here well I would end up with one
28:07
subtree that's empty so you might say
28:15
that well when I pick an edge with the
28:19
property that you get maybe an even
28:22
Division so half the objects in one side
28:25
the other half of the objects on the
28:27
other side or maybe you don't get too
28:29
many objects getting split and practice
28:33
it turns out that's too expensive
28:36
because you're dealing with scenes that
28:38
maybe have millions tens of millions of
28:42
edges or if you're dealing with 3d
28:44
objects use triangles so you got a very
28:46
large number of edges or triangles to
28:48
deal with and trying to pick the one
28:51
that's going to give you the best is a
28:54
very time-consuming operation well I'll
29:00
say something about about about a random
29:02
selection and that's kind of typical in
29:06
computing when something selection is
29:08
too hard you just make a random
29:10
selection and random selections usually
29:12
work out pretty good
29:19
another possibility is to just use hyper
29:23
planes that are access oriented okay so
29:27
in the case of 2d you may pick a
29:28
vertical line or a horizontal line to do
29:31
the cut regardless of which way you go
29:40
you still have choices even if you're
29:45
going axis aligned or where do you place
29:47
this horizontal axis or this horizontal
29:50
cut and as I said you may try to do this
29:52
by balancing the number of objects in
29:55
each subtree you may try and do it by
29:58
minimizing the number of pieces you
30:00
create so like here I create three extra
30:03
pieces because I cut three objects as I
30:08
said earlier computationally that's
30:10
expensive so typically people don't try
30:14
to do that all right here's a 3d example
30:23
it's one we've seen before so in an auto
30:26
petition I might pick a face of one of
30:28
these objects okay so here I've taken
30:32
the the front face of this green cube
30:37
for my first cut
30:43
so if I took that first face then the
30:48
entire white region gets split into two
30:52
one has the yellow object in it and the
30:55
other one has the green object in it
30:58
again whether the yellow object shows up
31:01
on the left sub-tree or the right
31:02
depends on how you pick the coefficients
31:05
on the equation for that plane or it has
31:15
the same properties if you're trying to
31:17
do a view and you want to see what's
31:18
going to come you'd basically take a
31:23
look at the viewer and say which
31:27
subspace are un well this fellow's in
31:29
the front of this cutting hyperplane and
31:33
if you're trying to do a draw if you're
31:37
doing a back to front draw you would
31:38
then first do the subtree behind the
31:42
plane and then do the subtree in front
31:45
of the plane and if you're doing a front
31:47
to back you'll do the other way around
31:49
whichever where you go you're guaranteed
31:52
to get the right scene all right
32:00
similarly if you were on the other side
32:02
okay you'd first compute which side
32:05
you're on
32:06
and either do the near side first and
32:08
then the far side or the other way
32:10
around
32:14
you could have complex arrangements of
32:19
objects I guess here are some things
32:24
we've got this object here which is in
32:27
front of this green fellow on this side
32:29
and then it goes behind it okay then it
32:32
comes back in front so you really can't
32:36
do an ordering of the object inside this
32:38
objects in front of that because part of
32:40
it is in front and part of it is not in
32:42
front so if you did a BSP tree you'd
32:45
probably know let's say you picked the
32:49
back face of this object as a cutting
32:52
hyperplane well in that case on the
32:55
front of this
32:56
cutting plane you would get this green
32:58
object and you get these two blue these
33:01
two yellow pieces this yellow object
33:03
will get cut into three pieces two in
33:06
the front and then a middle one that
33:08
connects from here to here showing up in
33:09
the back okay and now when you use the
33:14
BSP drawing things would show up right
33:19
okay if you were sitting on this side
33:22
and you're doing the back to front you
33:25
would first end up drawing this back
33:27
part but then it'll get overwritten by
33:29
the green part when you got around to
33:32
that all right so far when we talked
33:43
about BSP trees we've talked about just
33:45
petitioning down into cells and regions
33:49
that have single objects which you don't
33:50
have to stop there you can keep
33:53
petitioning so that each leaf node
33:57
represents a homogeneous region but
33:59
which I mean a leaf node represents part
34:02
of a unique object so right now a region
34:07
has an object plus open space so then
34:12
you still have to do some geometry on
34:14
the object to figure out which pixels
34:17
need to get painted the color of the
34:19
object and which should be painted the
34:21
color of the background so we could go
34:26
all the way down okay so for example if
34:30
this was your object okay even though it
34:35
might be sitting and I sell it this time
34:37
I could take that cell and divide it
34:39
further so I could take a take a line
34:46
out here and typically what's done is
34:55
you orient these lines now so that the
34:59
interior of the object i dealing with is
35:02
in the left subtree okay so
35:06
we will always pick things that are acts
35:12
well I guess aligned with the edges of a
35:14
polygon okay so here I picked this
35:18
fellow okay then I might pick this guy
35:20
and again I'll have to arrange it so
35:23
that the interior is in the left subtree
35:25
of this okay so I'll have to change the
35:28
coefficients the sign of the
35:29
coefficients here relative to what I had
35:31
over there okay all right then I might
35:36
pick this line and then I might pick
35:43
this line out here okay so when you pick
35:46
this one you end up chopping this fellow
35:48
into two pieces all right then you pick
35:56
this guy okay so notice that each time
35:59
you take a petitioning line it only
36:01
spans the region that you're cutting so
36:04
this line doesn't cross over into that
36:06
one okay it's local to the subtree
36:09
you're currently dealing with okay all
36:13
right in this case you'll finally have
36:14
one more cut over there
36:26
all right so we don't have to stop at
36:31
cells that have single objects we can
36:34
keep going until each leaf node is
36:37
homogeneous in the sense that it either
36:39
represents the exterior or it represents
36:42
the interior of the object all right
36:51
typically this is done in a systematic
36:53
fashion
36:53
so that when you traverse this tree the
36:57
right subtrees represent exterior sub
36:59
regions and the left sub trees of sort
37:02
of the right leaves so if a leaf is a
37:05
right child of its parent it's an
37:06
exterior if it's a left child of its
37:08
parent is an interior right we just look
37:18
at trying to restate some of the stuff
37:20
we've said so far construction each node
37:25
is have will have the equation of the
37:27
petitioning hyperplane it's going to
37:29
keep a list of coincident objects and
37:31
then it's going to have a left child in
37:33
a right child pointer the algorithm is
37:38
fairly straightforward if you've got no
37:41
objects the trees empty otherwise you
37:44
can have at least a node if you have
37:46
only one object that node will sit if
37:48
that object will sit in that node okay
37:51
this is zooming we're just going down to
37:53
a single object per cell if you have
37:58
more than one you'll need to select a
38:00
partitioning hyperplane and then you
38:02
need to compute whether somebody is
38:04
coincident twice to the left close to
38:06
the right or straddles it if it
38:10
straddles you can have to split it then
38:13
you recursively build the left and right
38:14
subtrees
38:20
if you want to draw you have to take a
38:27
look at the observer see whether the
38:29
observer is sitting in the left subtree
38:31
or the right subtree or where you
38:34
currently are okay so do you lie to the
38:38
left of the right so you take the
38:39
coordinates of the observer plug it into
38:42
the equation see whether you get a
38:44
negative or positive result so if in the
38:48
left okay so here I'm doing back to
38:51
front okay so if you the left then the
38:54
right is further away so you do the
38:56
right okay then you do the stuff in the
38:59
coincidence list and then you do this
39:01
stuff in the New York Region if the eye
39:05
is in the right side then you reverse
39:08
the order you do the left first then
39:11
they consider it on the right if the eye
39:15
is considered to the petitioning plane
39:18
well doesn't really matter which way you
39:22
go left or right first but you don't do
39:27
the coincident plane because now all you
39:29
can see is the end of the object you can
39:31
see the whole object right front to back
39:38
is pretty similar
39:44
well I said that your first reaction to
39:50
trying to build a nice BSP tree might be
39:53
to kind of use a greedy strategy to pick
39:56
at each point the partitioning
39:59
hyperplane so let's say you're doing an
40:01
auto partition your choices are limited
40:04
to the number of faces in the objects
40:07
that you have so you might try out each
40:09
choice and see which one better balances
40:11
the tree now you can construct examples
40:14
where that doesn't result in really good
40:17
trees also it's an expensive strategy so
40:23
typically as I said people will just
40:26
select one of the faces of the object at
40:31
random when you do that if you're
40:38
looking say A to D okay so you start
40:41
with n number of line segments so in
40:45
this particular example there are three
40:49
line segments for this triangle four for
40:53
this program you got six out here eight
40:56
out there here I'm assuming there's
40:58
curve that we're kind of approximating
41:00
the curve with straight lines okay so
41:03
I've got eight here if you're doing a
41:05
final approximation you may have more
41:07
than one line for each of these all
41:11
right so we start with a number of line
41:14
segments in this case n is 23 and what
41:18
one can prove is that if if you select
41:23
the the line segments for your
41:28
petitioning at random then the total
41:31
number of line segments and the result
41:33
okay so like yeah for example here if I
41:36
pick this one my line segments go up by
41:38
one because well actually by two got a
41:41
little piece out here and a big piece
41:42
there and a piece here and a piece there
41:44
okay so as you do these the total number
41:48
of line segments increase okay but when
41:51
you do it at random you can prove that
41:53
the expectation is that you're going to
41:56
end up with the total number of line
41:57
segments
41:58
at most 2n natural log n more than what
42:01
you started with and typically then the
42:08
way people would build this tree using
42:10
that result is you pick things you pick
42:13
things at random and if your particular
42:17
selection ended up with more than this
42:20
many segments well then you start all
42:23
over again using a different random
42:24
selection and you would keep repeating
42:27
that restart process so that you don't
42:31
have more than this many things okay
42:35
typically people have found that you
42:36
only need to restart this thing once so
42:39
after you try like two rounds of this
42:41
construction you end up with a structure
42:45
that has no more than this many line
42:47
segments in it and so the construction
42:56
time using a then become something like
43:03
n Square log n you've got a total of
43:07
about n log n line segments to deal with
43:13
and that means that the total number of
43:18
nodes in your structure would be n log n
43:20
okay total number of nodes won't exceed
43:24
the number of objects or sub object
43:27
pieces that you have and if the line
43:29
segments is n log n the total number of
43:30
objects cannot be more than n log n
43:32
either in the end if you only go down to
43:36
one object object piece for node the
43:39
number of leaves will be equal to the
43:41
number of object pieces and the number
43:43
of internal nodes will be one less than
43:45
the number of leaves so the total number
43:48
of nodes is out of n and you end up with
43:50
that kind of complexity for the
43:52
construction okay there's similar result
43:58
for 3d what you just read that on your
44:02
own
44:05
something that's probably been going
44:07
through your mind is well maybe we could
44:09
do a little bit of heuristic in this
44:11
thing rather than there's total random
44:13
perhaps there were some edges which give
44:15
you free partitions and that they don't
44:17
increase the number of segments so
44:22
certainly in practice people introduce
44:24
this idea of first pick a free edge to
44:29
partition on if there is one otherwise
44:32
selected random then there are some
44:35
results around which say that if you
44:39
have an edge that crosses one of your
44:43
cells of your current cells will that
44:46
edge if you use that to do a petition it
44:49
will not intersect anybody else so
44:51
that's a free petition gives you a quick
44:55
way to check for a free partition in
45:02
contrast if you pick an edge like this
45:06
which doesn't span the region if you use
45:09
this to petition if you extend it out
45:11
it's going to chop that edge and chop
45:13
that edge okay but if you had an edge
45:15
that went all the way since the objects
45:18
you're dealing with
45:18
can't intersect each other there aren't
45:21
really one object doesn't go through
45:22
another one okay the previous result and
45:25
shows that picking line segments that
45:29
cross the region results in a free
45:33
partition
45:39
all right any questions again there are
45:46
other ideas here people might construct
45:48
using some of the ideas from segment
45:50
trees that we talked about in 2d if you
45:55
use the segment tree construction step
45:57
ideas you can construct in n log n time
46:01
without any randomization but again
46:05
people have found that in practice the
46:06
BSP trees you get are a little bit
46:09
bigger than the trees you get using
46:11
randomization okay alright so we'll stop
46:21
here and if you can stay back there's a
46:23
course evaluation to be done all right
46:24
thanks
46:28
you