BSP2D

Information about BSP2D

Published on September 14, 2007

Author: Alien

Source: authorstream.com

Content

Motivation for BSP Trees:The Visibility Problem:  Motivation for BSP Trees: The Visibility Problem We have a set of objects (either 2d or 3d) in space. We have an 'eye' at some point in this space, looking at the objects from a particular direction. Drawing the Visible Objects:  Drawing the Visible Objects We want to generate the image that the eye would see, given the objects in our space. How do we draw the correct object at each pixel, given that some objects may obscure others in the scene? A Simple Solution: The Z-buffer:  A Simple Solution: The Z-buffer Keep a buffer that holds the z-depth of the pixel currently at each point on screen Draw each polygon: for each pixel, test its depth versus current screen depth to decide if we draw it or not Drawbacks to Z-buffering:  Drawbacks to Z-buffering This used to be a very expensive solution! Requires memory for the z-buffer – extra hardware cost was prohibitive Requires extra z-test for every pixel So, a software solution was developed … The Painter's Algorithm:  The Painter's Algorithm Avoid extra z-test andamp; space costs by scan converting polygons in back-to-front order Is there always a correct back-to-front order? How Do We Deal With Cycles?:  How Do We Deal With Cycles? In 3 dimensions, polygons can overlap, creating cycles in which no depth ordering would draw correctly. How do we deal with these cases? BSP Trees:  BSP Trees Having a pre-built BSP tree will allow us to get a correct depth order of polygons in our scene for any point in space. We will build a data structure based on the polygons in our scene, that can be queried with any point input to return an ordering of those polygons. The Big Picture:  The Big Picture Assume that no objects in our space overlap. Use planes to recursively split our object space, keeping a tree structure of these recursive splits. Choose a Splitting Line:  Choose a Splitting Line Choose a splitting plane, dividing our objects into three sets – those on each side of the plane, and those fully contained on the plane. Choose More Splitting Lines:  Choose More Splitting Lines What do we do when an object (like object 1) is divided by a splitting plane? It is divided into two objects, one on each side of the plane. Split Recursively Until Done:  Split Recursively Until Done When we reach a convex space containing exactly zero or one objects, that is a leaf node. Continue:  Continue Continue:  Continue Finished:  Finished Once the tree is constructed, every root-to-leaf path describes a single convex subspace. Querying the Tree:  Querying the Tree If a point is in the positive half-space of a plane, then everything in the negative half-space is farther away -- so draw it first, using this algorithm recursively. Then draw objects on the splitting plane, and recurse into the positive half-space. What Order Is Generated From This Eye Point?:  What Order Is Generated From This Eye Point? How much time does it take to query the BSP tree, asymptotically? Structure of a BSP Tree:  Structure of a BSP Tree Each internal node has a +half space, a -half space, and a list of objects contained entirely within that plane (if any exist). Each leaf has a list of zero or one objects inside it, and no subtrees. The size of a BSP tree is the total number of objects stored in the leaves andamp; nodes of the tree. This can be larger than the number of objects in our scene because of splitting. Building a BSP Tree From Line Segments in the Plane:  Building a BSP Tree From Line Segments in the Plane We’ll now deal with a formal algorithm for building a BSP tree for line segments in the 2D plane. This will generalize for building trees of D-1 dimensional objects within D-dimensional spaces. Auto-Partitioning:  Auto-Partitioning Auto-partitioning: splitting only along planes coincident on objects in our space Algorithm for the 2d Case:  Algorithm for the 2d Case If we only have one segment 's', return a leaf node containing s. Otherwise, choose a line segment 's' along which to split. For all other line segments, one of four cases will be true: 1) The segment is in the +half space of s 2) The segment is in the -half space of s 3) The segment crosses the line through s 4) The segment is entirely contained within the line through s. Split all segments who cross 's' into two new segments -- one in the +half space, and one in the -half space. Create a new BSP tree from the set of segments in the +half space of s, and another on the set of segments in the -half space. Return a new node whose children are these +/- half space BSP’s, and which contains the list of segments entirely contained along the line through s. How Small Is the BSP From This Algorithm?:  Different orderings result in different trees Greedy approach doesn't always work -- sometimes it does very badly, and it is costly to find How Small Is the BSP From This Algorithm? Random Approach Works Well:  Random Approach Works Well If we randomly order segments before building the tree, then we do well in the average case. Expected Number of Fragments: O(n Log n):  Expected Number of Fragments: O(n Log n) Expected Running Time: O(n2log n):  Expected Running Time: O(n2log n) Optimization: Free Splits:  Optimization: Free Splits Sometimes a segment will entirely cross a convex region described by some interior node -- if we choose that segment to split on next, we get a 'free split' -- no splitting needs to occur on the other segments since it crosses the region. Our Building Algorithm Extends to 3D!:  Our Building Algorithm Extends to 3D! The same procedure we used to build a tree from two-dimensional objects can be used in the 3D case – we merely use polygonal faces as splitting planes, rather than line segments. A Slight Modification, for the Sake of Analysis::  A Slight Modification, for the Sake of Analysis: Split both the + and - half space of a node with the same plane, when we choose to do a split. An exception: When a split does not subdivide some cell, it isn't necessary to include an extra node for it. Expected number of fragments: O(n^2):  Expected number of fragments: O(n^2) More analysis: How good are auto-partitions?:  There are sets of triangles in 3-space for which autopartitions guarantee W(n2) fragments. More analysis: How good are auto-partitions? Can we do better by not using autopartitions? Sometimes, No:  Sometimes, No There are actually sets of triangles for which any BSP will have W(n2) fragments! More applications:  More applications Querying a point to find out what convex space it exists within Cell visibility -- put extra data into your BSP leaves, such as links to adjacent convex subspaces

Related presentations


Other presentations created by Alien

Physical Security Lecture
05. 01. 2008
0 views

Physical Security Lecture

GREEK THEATRE
15. 10. 2007
0 views

GREEK THEATRE

Singapore National Symbols
14. 09. 2007
0 views

Singapore National Symbols

Origins of the Cold War
23. 12. 2007
0 views

Origins of the Cold War

CG43SlideSet
30. 04. 2008
0 views

CG43SlideSet

kaiser pres
28. 04. 2008
0 views

kaiser pres

GoldDifferences
22. 04. 2008
0 views

GoldDifferences

visn8
17. 04. 2008
0 views

visn8

Nov24 Regulatory approaches
16. 04. 2008
0 views

Nov24 Regulatory approaches

dr rom
14. 04. 2008
0 views

dr rom

file 6943
13. 04. 2008
0 views

file 6943

The Peak Oil Context Tom Petrie
10. 04. 2008
0 views

The Peak Oil Context Tom Petrie

H106g
09. 04. 2008
0 views

H106g

JapaneseGeography
07. 04. 2008
0 views

JapaneseGeography

Hamburg 2007
14. 09. 2007
0 views

Hamburg 2007

lfg
14. 09. 2007
0 views

lfg

Eddie Final Presentation
14. 09. 2007
0 views

Eddie Final Presentation

chalmers
14. 09. 2007
0 views

chalmers

The Rain Forest Final
14. 09. 2007
0 views

The Rain Forest Final

ECAKnowledgeFair
12. 10. 2007
0 views

ECAKnowledgeFair

Ch18part1
15. 10. 2007
0 views

Ch18part1

WNV AVB 02212006
21. 10. 2007
0 views

WNV AVB 02212006

giraffe pp
14. 09. 2007
0 views

giraffe pp

giraffe powerpoint
14. 09. 2007
0 views

giraffe powerpoint

giraffe
14. 09. 2007
0 views

giraffe

COOL STUFF ABOUT GIRAFFES
14. 09. 2007
0 views

COOL STUFF ABOUT GIRAFFES

ub041104
23. 10. 2007
0 views

ub041104

STORY OF THEME AND PLOT
23. 10. 2007
0 views

STORY OF THEME AND PLOT

PhiladelphiaZooPPP
14. 09. 2007
0 views

PhiladelphiaZooPPP

qu10 11
01. 12. 2007
0 views

qu10 11

Angelos CME Energetics
02. 11. 2007
0 views

Angelos CME Energetics

pptPanama s
22. 10. 2007
0 views

pptPanama s

hirotani
13. 11. 2007
0 views

hirotani

bon2003 mpls
29. 10. 2007
0 views

bon2003 mpls

PROF AZZA
23. 10. 2007
0 views

PROF AZZA

Fenton
29. 10. 2007
0 views

Fenton

Countering Offshore
29. 12. 2007
0 views

Countering Offshore

walters082902
23. 11. 2007
0 views

walters082902

razbash
26. 11. 2007
0 views

razbash

DVMRPandMOSPF
01. 01. 2008
0 views

DVMRPandMOSPF

One 783Ngupta
04. 01. 2008
0 views

One 783Ngupta

Chapter 18 PPT
22. 10. 2007
0 views

Chapter 18 PPT

History of NAIS John Wiemers
20. 08. 2007
0 views

History of NAIS John Wiemers

costarica1 ftparraud
22. 10. 2007
0 views

costarica1 ftparraud

mcmc2000a
06. 11. 2007
0 views

mcmc2000a

050317lc
16. 11. 2007
0 views

050317lc

ALA2003 OAI
04. 10. 2007
0 views

ALA2003 OAI

fwing
22. 10. 2007
0 views

fwing

acute 060727 transfusionmed
23. 10. 2007
0 views

acute 060727 transfusionmed

bckexpk3b
09. 07. 2007
0 views

bckexpk3b

anorexia
09. 07. 2007
0 views

anorexia

070207 Adjektiv
09. 07. 2007
0 views

070207 Adjektiv

A Brachmann
09. 10. 2007
0 views

A Brachmann

mueller jun07
19. 10. 2007
0 views

mueller jun07

Late Classic Maya Collapse
16. 02. 2008
0 views

Late Classic Maya Collapse

ISLAS GALAPAGOS
14. 09. 2007
0 views

ISLAS GALAPAGOS

Heatingoilwebsection ppp
24. 02. 2008
0 views

Heatingoilwebsection ppp

PIndustrialTrucks
26. 02. 2008
0 views

PIndustrialTrucks

ethanap
14. 09. 2007
0 views

ethanap

Propulsion CEV
07. 11. 2007
0 views

Propulsion CEV

MichelleWatt
20. 02. 2008
0 views

MichelleWatt

newsletterfall04
11. 03. 2008
0 views

newsletterfall04

EC T9 2008 Conference Proposal
12. 03. 2008
0 views

EC T9 2008 Conference Proposal

drugstatistics
17. 12. 2007
0 views

drugstatistics

icfa chep06
23. 10. 2007
0 views

icfa chep06

Hubert CW8
14. 09. 2007
0 views

Hubert CW8

A mi Papi 2089
19. 06. 2007
0 views

A mi Papi 2089

An ode to Mothers
19. 06. 2007
0 views

An ode to Mothers

LoffPresentation
17. 10. 2007
0 views

LoffPresentation

Maschera
19. 06. 2007
0 views

Maschera

manual
19. 06. 2007
0 views

manual

Luces De Navidad 1848
19. 06. 2007
0 views

Luces De Navidad 1848

leer
19. 06. 2007
0 views

leer

Lean Six SigmaATL011706
19. 06. 2007
0 views

Lean Six SigmaATL011706

lexisnexis
05. 10. 2007
0 views

lexisnexis

OAT Presentation v5
19. 06. 2007
0 views

OAT Presentation v5

moscatelli
19. 06. 2007
0 views

moscatelli

moon split
19. 06. 2007
0 views

moon split

money plus
19. 06. 2007
0 views

money plus

MKCL
19. 06. 2007
0 views

MKCL

Journey of the Spirit Lesson 6
01. 10. 2007
0 views

Journey of the Spirit Lesson 6

2 Jornada BISHOP
10. 10. 2007
0 views

2 Jornada BISHOP

No esperes
19. 06. 2007
0 views

No esperes

Amores locos 1992
19. 06. 2007
0 views

Amores locos 1992

College English book 2 Unit 7
24. 02. 2008
0 views

College English book 2 Unit 7

A vista de pajaro II 2109
19. 06. 2007
0 views

A vista de pajaro II 2109

Ammosov Vladimir ammosov pra
12. 10. 2007
0 views

Ammosov Vladimir ammosov pra

Amber la mejor de todas
19. 06. 2007
0 views

Amber la mejor de todas

CP317 lecture 6 Huck II 05
11. 12. 2007
0 views

CP317 lecture 6 Huck II 05

AHQA031204Mck
09. 07. 2007
0 views

AHQA031204Mck

Evergreen
03. 01. 2008
0 views

Evergreen

04 NJIT3
02. 01. 2008
0 views

04 NJIT3

Poster A4 Glasgow nov04
04. 10. 2007
0 views

Poster A4 Glasgow nov04

Ally McBeal
09. 07. 2007
0 views

Ally McBeal

sara paige
14. 09. 2007
0 views

sara paige

36181003
24. 10. 2007
0 views

36181003

MusicApprecBaroque 2
22. 11. 2007
0 views

MusicApprecBaroque 2

ELE386 Malware
20. 08. 2007
0 views

ELE386 Malware

RohanShah
12. 10. 2007
0 views

RohanShah

1022MAS net big picture
03. 01. 2008
0 views

1022MAS net big picture

Lo Suficiente 1744
19. 06. 2007
0 views

Lo Suficiente 1744

gm3 jp item14 Mangrove ITTO
22. 10. 2007
0 views

gm3 jp item14 Mangrove ITTO

2005AuditResults
09. 07. 2007
0 views

2005AuditResults

HABIC1 summary
17. 11. 2007
0 views

HABIC1 summary

aro ald informalsession
24. 10. 2007
0 views

aro ald informalsession

etu ambassadeurs juin 07 en
13. 03. 2008
0 views

etu ambassadeurs juin 07 en

Gobert poster
03. 10. 2007
0 views

Gobert poster

Kistenev
15. 11. 2007
0 views

Kistenev

6 History of Chemistry I
12. 10. 2007
0 views

6 History of Chemistry I

Jan2000report
04. 01. 2008
0 views

Jan2000report

course 4
03. 01. 2008
0 views

course 4