>Предыдущий OpenGL тред 7
Нормальная ссылка:
Пропук сделан осознанно?
А нет подробного справочника по directx12? Я успел накать этим в с++ тред, не заметил этого. Но вопрос актуален.
Мне бы почитать, что и зачем делается с объяснением каждого аргумента используемых функций. А то мешанина такая, что даже туториал с треугольником модифицировать голове больно. Уверен, не я один такой.
Уже задумываюсь от отчаяния обратится к движку Cauldron.
>Пропук
Каво чаво?
Разрыв в анимации? Мне просто лень было подгонять стык в стык.
Справка от мелкомягких не канает?
https://learn.microsoft.com/en-us/windows/win32/direct3d12/directx-12-programming-guide
>лень было подгонять
Тыжпрограммист, ты можешь написать формулу, чтобы программа отрендерила ровно столько, сколько нужно для анимации, а потом склеить.
Даже яждизайнер с такой задачей справится...
>Тыжпрограммист, ты можешь написать формулу, чтобы программа отрендерила ровно столько, сколько нужно для анимации, а потом склеить.
Так я рендерю только в окно. А окно записывал сторонней прогой, которая просто экран в гифку пишет.
А чтобы самому в гифку писать, это надо искать какую-то библиотечку для гифа, подрубать ее в проект, писать всю мишуру для создания и сохранения гифки... Мех, оно того не стоит.
stb_image сохраняешь в png покадрово, потом imagemagick-ом или ffmpeg склеиваешь в анимацию. Приключение на 20 минут или весь день.
Ну в таком случае есть и попроще решение
https://github.com/charlietangora/gif-h
>Приключение на 20 минут или весь день.
Вот это и пугает. Я потратил всего 2 минуты на гифку, которая утонет в бездне, и думаю, что это достаточно рационально.
>Я потратил всего 2 минуты на гифку, которая утонет в бездне
А мог потратить 20 минут и создать шедевр, который будут вспоминать поколениями.
Мотивирует, надо стремиться к совершенству в каждой детали
>в каждой детали
Особенно в ней.
Подскажите какую-нить статью, где подробно разжовываеться как делаь матрицы для каскадных теней
>как делаь матрицы для каскадных теней
Первой же ссылкой
https://rekovalev.site/opengl-11-shadows-p1/#cascaded-shadow-maps
Игры свои показывайте.
Мы безигорные байтоебы
Так может тогда стоило создать в /pr ?
там уже был тред для типа элиты, которые об алгоритмах спорят, а не о движках
но постят в него один хуй хуилы из /гд
Вкат начат, держитесь кабанчики, к концу года буду сотрясать рынок труда
Как кстати сейчас с рынком труда обстоит дела? Я на хх ру видел что только saber и томские unigine кого то набирают
Всё слишком грустно?
ну рейт игрулю
Как кстати сейчас с рынком труда обстоит дела? Я на хх ру видел что только saber и томские unigine кого то набирают
Всё слишком грустно?
ну рейт игрулю
Какой гкймплей?
в этой игре у тебя безграничное кол-во возможностей
- можешь мышкой кубик крутить
- менять цвет фона
- перезагружать шейдеры на кнопку R
как раскраска, только вместо красок, два шейдера
Какой либой эти менюшки делаются?
да я её первой смотрел. Это говно, а не справка.
Вот, например, есть две функции: RsScissorsRect и RsSetViewports
Вьюпорт я знаю, что такое, но меня интересовали ножницы. Зашел на сайт майков: биндит площадь экранного пространства для растеризатора. Ок, предположим, я понял, что это значит.
Отправляем нули в ножницы: не рисуется ничего. Удалило экранное пространство. Ок, мы вернём ножницы и занулим вьюпорт. Снова не рисуется ничего.
Ок, мы уменьшим площадь отправляемую в ножницы, оставим прежнюю в вьюпорте.
На выходе: площадь отрисовки сжалась до площади отправленной в ножницы.
Так на кой хуй вообще нужны ножницы, если эффект от них идентичен изменению площади вьюпорта? А хуй их знает. Майки не считают нужным пояснить это.
Только тут я хотя бы могу проверить, че изменится визуально, а большинство изменений функций тупо вызывают вылет. И для них также нет пояснения.
Попробуй предыдущие версии ДХа покурить, там наверняка 90% концепций наследуется.
https://learn.microsoft.com/en-us/windows/win32/direct3d9/scissor-test
https://gamedev.stackexchange.com/questions/100890/what-is-the-difference-between-a-viewport-and-a-scissor-rectangle
По урокам learnopengl.com
>4 скрин
Крста
Это рендеринг текстуры в текстуру в текстуру?
Да, framebuffer.
>Как кстати сейчас с рынком труда обстоит дела? Я на хх ру видел что только saber и томские unigine кого то набирают
VK (бывшая Mail.ru Group) разрабатывают Nau Engine, ответ Saber3D & Unigine, предназначенный для пориджей/смузихлёбов с Унити.
https://nauengine.org
> vulkan
Господи, как же всё не понятно
Какие то рендер пассы, которые имеют несколько сабпассов, которые хуй знает что делают
Почему то depth buffer должен крепится к рендер пассу при создании
А FrameBuffer создается через рендер пасс, которые крепится уже к его createInfo
Как этим пользоваться без мануалов в соседнем окне
Надо было получить благословение Джона Кармака, как это произошло с его преемником Тьягой Соузой (после idTech 7 вроде в ИИ/ML пошёл, судя по прошлогоднему линкедину), и родиться хорватом, ибо это они (Croteam, разработчики Serious Sam) первыми в мире пустили в рыночек видеоигру на Vulkan.
> Чтобы поменять layout в VkImage нужно зачем то сабмитить комманду в графическую Queue
Май хонест реакшен
а полегче пути есть?
ТУПОЙ ВОПРОС:
Я правильно понимаю что для рейтресера, который использует RaytracingPipeline, не нужен вобще DepthBuffer
Май хонест реакшен
а полегче пути есть?
ТУПОЙ ВОПРОС:
Я правильно понимаю что для рейтресера, который использует RaytracingPipeline, не нужен вобще DepthBuffer
Для любого чистейшего рейкастинга (рейтрейсинга в т.ч.) никакое тестирование глубины не нужно, и Depth/Z buffer, следовательно, тоже. Но, так как у тебя RT идёт в дополнении к полигональной, и я обычный школьник (см. видрил), ещё не переросший апенгл, то в вулканических нанотехнологиях я не очень-то шарю. Думаю, что тебе не нужон этот буффер в этой ситуации.
Основной смысл этого поста: чекни документацию/спецификацию:
Вода от Khronos:
https://developer.nvidia.com/blog/vulkan-raytracing/
https://www.khronos.org/assets/uploads/developers/presentations/Vulkan_Ray_Tracing_Overview_Apr21.pdf
https://www.khronos.org/blog/vulkan-ray-tracing-best-practices-for-hybrid-rendering
Практика от корпорации рептилоидов:
https://developer.nvidia.com/blog/three-things-you-need-to-know-about-ray-tracing-in-vulkan/
https://developer.nvidia.com/rtx/raytracing/vkray
https://nvpro-samples.github.io/vk_raytracing_tutorial_KHR/
Спасибо за ссылочки анон
> я обычный школьник, ещё не переросший апенгл
Я пока что сам от этого не далеко ушел
надеюсь к новому году хотя бы разбераться начну что да как
кидзуня :3
Алсо ознакомся с этим https://github.com/RayTracing/gpu-tracing https://github.com/RayTracing/raytracing.github.io
>кидзуня :3
https://neolurk.org/wiki/%D0%9A%D0%B8%D0%B4%D0%B7%D0%BE%D0%BD%D1%8F
Я написал про неё статью, по, как оказалось, инфе ею забаненых в своих соц. сетях битардов, что оч понравилось админам лурка. Кста, тред в фаге KIDZONYA#12, который последний, на днях умер и продолжения в ближайшее время не будет. Эх, ты такое приключение по кидзонястану и мордору её битардом летом пропустил. Соболезную.
Подскажите где можно почитать или подсмотреть архитектуру для рендерера?
Пытался как то сам написать, но либо кишочки графического апи начинают наверх протекать, либо эта штуковина становится не устойчива к изменениям, что чуть ли не переписывать приходится
Пытался как то сам написать, но либо кишочки графического апи начинают наверх протекать, либо эта штуковина становится не устойчива к изменениям, что чуть ли не переписывать приходится
На гитхабе ввести в поиск renderer.
> эта штуковина становится не устойчива к изменениям, что чуть ли не переписывать приходится
пиши рендер на ЕКС
Ну так надо знать требования, на что должен быть рассчитан движок. Не случайно до сих пор люди пишут свои рендеры под свои игры. А существующие универсальные решения громоздкие. Тут либо одно, либо другое. Такшо постановка цели тут важна, в любом случае надо ориентироваться на определенный круг технологий.
А так, каких-то хитровыдуманных решений тут не будет скорее всего, паттерны все одни и те же уж лет 20. Либо гляди опенсорсные движки, либо общие архитектурные штуки кури и придумывай велосипед.
https://github.com/OGRECave/ogre
https://github.com/ConfettiFX/The-Forge -- этот рендерер использовался в Starfield
https://github.com/DustinHLand/vkDOOM3 -- vulkan-реализация idTech 4 (Doom 3 engine).
https://github.com/Croteam-official/Serious-Engine -- движок первого "Серьёзного Сэма". Глянь.
>становится не устойчива к изменениям
Рекомендую https://github.com/SanderMertens/ecs-faq https://www.flecs.dev/
ох спасибо анончик, то что и искал
>Судя по всему, характер мегатоксичный из-за жизненных обстоятельств, хотя в душе очень добрая. Психика периодическая, присутствует многополярный мир (по её словам — исключительно богатый внутренний мир, превосходящий таковые всяких далай-лам и перипатетиков) и параноидальная шиза, в связи с чем и вкатилась в клоунаду своего манямирка в попытке сбежать от шайтанов и суровой правды.
Перелуркили малехо. Вроде и понятно, в чем суть, но читать невозможно без крови из глаз.
Анонче, знает ли кто-нибудь, как во flecs итерировать дочерние сущности с фильтром (компонентов), как это можно делать с flecs::world::each(...) ?
классика луркоёбства. Это было написано по клевете одного куколда, который пытался форсить эту вхору на харкаче ~1.5 года. Когда вскрылась эта правда, я попытался исправить этот поток шизофазии а точнее -- спермотоксикоз разбитого сердца куколда, который нравился админам лурка и защищался ими.
классика луркоёбства. Это было написано по клевете одного куколда, который пытался форсить эту вхору на харкаче ~1.5 года. Когда вскрылась эта правда, я попытался исправить этот поток шизофазии а точнее -- спермотоксикоз разбитого сердца куколда, который нравился админам лурка и защищался ими.
Почему webgl2 дает мне создать текстуру размером 4x3, но для размера 3x3 выдает ошибку? Думал, может сторона должна быть степенью двойки или кратной степени двойки, но 22x1 проходит, a 22x5 - нет.
Некропеку обнови.
Вебгл устарел, юзай webGPU.
А то что у него отступ в два пробела тебя не смутило?
>Вебгл устарел,
Что несет...
Ох.. Ах...
Этот антихрист посмел диктовать свой табстайл.
Ну хуй знает, такая ошибка должна выпадать, если указанные размеры и размеры буффера не матчатся.
https://stackoverflow.com/questions/54276566/webgl-invalid-operation-teximage2d-arraybufferview-not-big-enough-for-reques
https://registry.khronos.org/webgl/specs/latest/1.0/#TEXIMAGE2D
Затесть что будет если null закинуть вместо pixels для тех же размеров.
Еще можно попробовать для всех размеров, например, от 1х1 до 10х10 сделать запуск и посмотреть где крашится, есть ли логика какая-то.
Ну и принтани размер массива на всякий случай.
У меня щас объекты рендерятся и хранятся в таком порядке (утрированно):
>for Shader s : shaders
> s.use()
> for Object o : s.children
> o.draw()
Объекты у меня привязаны к шейдерам (пох если у модели должно быть > 1 шейдера) и фильтруются по ним, чтобы не было лишнего вызова шейдера.
Правильно ли я сделал или это залупа?
>for Shader s : shaders
> s.use()
> for Object o : s.children
> o.draw()
Объекты у меня привязаны к шейдерам (пох если у модели должно быть > 1 шейдера) и фильтруются по ним, чтобы не было лишнего вызова шейдера.
Правильно ли я сделал или это залупа?
Для хэлоуворда сойдет. В нормальном рендере будет индирект драв в 1 вызов.
В годоте так и сделано
Полезные ссылочки петухонерам и просто преемникам Джона Кармака:
https://www.rastergrid.com/blog/2010/10/gpu-based-dynamic-geometry-lod/ -- GPU based dynamic geometry LOD.
https://www.rastergrid.com/blog/2011/01/frei-chen-edge-detector/ -- алгоритм детектора краев.
https://www.rastergrid.com/blog/2010/11/texture-and-buffer-access-performance/ -- советы по производительному доступу к текстурам и буферам.
https://www.rastergrid.com/blog/2010/10/hierarchical-z-map-based-occlusion-culling/ -- Hierarchical-Z map based occlusion culling.
https://stackoverflow.com/questions/4995652/3d-occlusion-culling
https://visualizationlibrary.org/documentation/pag_guide_occlusion_culling.html -- OpenGL-Accelerated Occlusion Culling Tutorial.
https://developer.nvidia.com/gpugems/gpugems/part-v-performance-and-practicalities/chapter-29-efficient-occlusion-culling -- Efficient Occlusion Culling.
https://cpp-rendering.io/indirect-rendering/ -- Indirect Rendering : “A way to a million draw calls”.
https://gamedev.ru/code/articles/Cook-Torrance -- Быстрая реализация модели освещения Кука-Торренса. (Она очень хорошо подходит для создания различных стеклянных и металлических поверхностей).
https://interplayoflight.wordpress.com/2022/01/22/shader-tips-and-tricks/ -- Shader tips and tricks.
https://seblagarde.files.wordpress.com/2015/07/course_notes_moving_frostbite_to_pbr_v32.pdf -- Moving Frostbite to Physically Based Rendering 3.0.
https://interplayoflight.wordpress.com/2020/12/21/to-z-prepass-or-not-to-z-prepass/ -- To z-prepass or not to z-prepass.
https://interplayoflight.wordpress.com/2018/07/08/how-to-start-learn-graphics-programming/ -- How to start learning graphics programming?
https://interplayoflight.wordpress.com/2018/07/17/applying-for-a-graphics-programming-job/ -- Applying for a graphics programming job.
https://interplayoflight.wordpress.com/2020/02/17/ways-to-speedup-pixel-shader-execution/ -- Ways to speedup pixel shader execution.
https://google.github.io/filament/Filament.md.html -- Physically Based Rendering in Filament.
https://www.advances.realtimerendering.com/s2016/Siggraph2016_idTech6.pdf -- мастхэв про idTech 6 от преемника Джона Кармака -- Тьяги Соузы.
Не забудьте про "спасибо", смузихлёбы.
Анонче, это ваши инициалы на пикриле? Был бы я вашей маменькой, то меня переполняло бы от гордости
Алсо, кое-что забыл:
https://gamedev.ru/code/articles/Megatexture
https://gamedev.ru/code/articles/Virtual_textures -- статейки о мега-/виртуальных текстурах.
https://advances.realtimerendering.com/s2020/RenderingDoomEternal.pdf -- очередной мастхэв от id про idTech 7.
https://habr.com/ru/companies/intel/articles/266427/ -- Реализация многопоточной архитектуры игрового движка.
https://dspace.spbu.ru/bitstream/11701/32450/1/Abschlussarbeit_spring__6_.pdf -- Реализация алгоритмов для системы
геометрических частиц в игровом движке
Saber3D.
https://habr.com/ru/articles/309368/ -- Разбор графики Supreme Commander. это масштабнейшая RTS, которую кастит Yuri the Professional. Интересный пэйпер.
https://www.ixbt.com/video2/terms2k5.shtml#bm -- Современная терминология 3D графики. База.
https://dspace.spbu.ru/bitstream/11701/32450/1/Abschlussarbeit_spring__6_.pdf -- Реализация алгоритмов для системы
геометрических частиц в игровом движке
Saber3D.
https://habr.com/ru/articles/309368/ -- Разбор графики Supreme Commander. это масштабнейшая RTS, которую кастит Yuri the Professional. Интересный пэйпер.
https://www.ixbt.com/video2/terms2k5.shtml#bm -- Современная терминология 3D графики. База.
Спасибо.
Ссасный бук на пикриле, хочу
Топ, но быдло не настолько духовно развито, чтобы сразу прикасаться к элитарным изотерическим господским манускриптам.
Как же кайфово с пасскодом
Пипл, хаваем линки
>пик
Угарнул с Эйлера.
А где можно подтянуть матан под энто ваше графическое погромирование? Ничем сложнее рядов Фурье не пользовался, а в гайде на ОпенГл нужны какие-то полиномы
>Ничем сложнее рядов Фурье не пользовался
Ты успешнее 95% сидящих в этом треде.
>в гайде на ОпенГл нужны какие-то полиномы
Матан тебе нужен только для шейдеров, которые придумывать ты не будешь, а кроме шейдеров он в опенгле не нужон, так как он всё сделает сам за тебя. Тебе останется лишь нужную матрицу подкинуть, формулу создания которых можешь просто с любого учебника скопировать и -- фсё.
https://www.euclideanspace.com/maths/algebra/vectors/lookat/index.htm
Что за Umbra 3D? Известно, что это -- промежуточное ПО, выполняющее клипинг/отсечение геометрии, которое юзает овер9к компаний, в том числе и так же Ид.
У меня вопрос: как сделать ахринительно производительных двигатель/рендерер без занашивания огромных мани этому проприетарному неизвестно как работающему куску кала, у которого даже оф. сайт не работает?
Хз.
Завидуй буржуям молча и страдай от своей никчёмности, ничтожный червь.
Сколько анонов сидит в этом треде? Три?
>как сделать ахринительно производительных двигатель/рендерер
Все очень просто, никаких секретов нет, достаточно покурить несколько книг. Куришь книгу по алгоритмам и структурам данным. Книгу по архитектуре процов и памяти. Куришь книгу по распараллеливанию и всякой векторизации. Куришь всяческие graphics gems, gpu gems. Куришь книги по архитектуре кода. Не забываешь раскурить плюсы. Применяешь полученные знания на практике. ???. Готово!
А сколько десятилетий на всё это понадобится? Тем более что на всяких вакансиях по рендереру нередко стоит условие: делать то, что никто не делал и по чему нет статьи. Вряд ли, начиная с фундаментального гпу гемс получится дорасти до титанов 3Д мироздания. Скажи ещё ОС специально пiд движок написать
Ну ладно, я ещё школо, есть время на задротинг ассемблеров, SIMD, vulkan, алгоритмы и т.д.
Published August 22, 1999 by Bretton Wade, posted by Myopic Rhino
Do you see issues with this article? Let us know.
(Editor's Note - this article requires additional formatting work and is incomplete)
BSP Tree Frequently Asked Questions (FAQ)
Questions
CHANGES
ABOUT THIS DOCUMENT
ACKNOWLEDGEMENTS
HOW CAN YOU CONTRIBUTE?
ABOUT THE PSEUDO C++ CODE
WHAT IS A BSP TREE?
HOW DO YOU BUILD A BSP TREE?
HOW DO YOU PARTITION A POLYGON WITH A PLANE?
HOW DO YOU REMOVE HIDDEN SURFACES WITH A BSP TREE?
HOW DO YOU COMPUTE ANALYTIC VISIBILITY WITH A BSP TREE?
HOW DO YOU ACCELERATE RAY TRACING WITH A BSP TREE?
HOW DO YOU PERFORM BOOLEAN OPERATIONS ON POLYTOPES WITH A BSP TREE?
HOW DO YOU PERFORM COLLISION DETECTION WITH A BSP TREE?
HOW DO YOU HANDLE DYNAMIC SCENES WITH A BSP TREE?
HOW DO YOU COMPUTE SHADOWS WITH A BSP TREE?
HOW DO YOU EXTRACT CONNECTIVITY INFORMATION FROM BSP TREES?
HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING?
HOW ARE BSP TREES USED IN DOOM?
HOW CAN YOU MAKE A BSP TREE MORE ROBUST?
HOW EFFICIENT IS A BSP TREE?
HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT?
HOW CAN YOU AVOID RECURSION?
WHAT IS THE HISTORY OF BSP TREES?
WHERE CAN YOU FIND SAMPLE CODE AND RELATED ONLINE RESOURCES?
REFERENCES
Answers
CHANGES Date Section Change 06/02/98
Online Resources Updated the pointer to A.T. Campbell's home page. 01/22/98
Online Resources Added a pointer to the Id Software source code and utilities (finally). 06/08/97
Building a tree Added definition of an autopartition. Efficiency Completely rewrote this section with a concise explanation of the complexity of HSR with an autopartition. Online Resources Updated link to Paton Lewis's BSP tree page, and added a link to Tom Hammersly's web page which describes his experience at implementing a BSP tree compiler and viewer. 06/01/97
Motion Planning Initial draft. Doom Removed text which is confusing and not quite informative enough. Still looking for a replacement. 04/29/97
Online Resources Updated the link to the Computational Gemoetry Pages. 04/25/97
What is... Corrected an error in the ascii-art version of the tree diagram. Building BSP Trees Corrected an error in the example code. 04/14/97
Boolean Ops Corrected an error: "... polygon EFGH is inserted ... one polygon at a time." was changed to "... is inserted ... one edge at a time." Thanks to Filip J. D. Uhlik for noticing this. 04/08/97
Online Resources Updated pointer to FTP site for the FAQ support files: ftp://ftp.sgi.com/other/bspfaq/. 04/02/97
Entire Document Moved document to reality.sgi.com. Changes were made to reflect the new host, but otherwise only a few minor HTML changes were made. 10/09/96
Acknowledgements Added a Michael Brundage to the acknowledgements. Online Resources Added a reference to GFX, a general graphics programming resource.
Added a reference to John Whitley's BSP tree tutorial page. 10/07/96
Definitions Added new definitions page to clarify some difficult terms. Ray Tracing Added a note about using the parent node of the ray origin as a hint for improving run-time performance. Efficiency Corrected a long standing error in the stated complexity of BSP trees for Hidden Surface Removal. 10/06/96
About Added new sub-sections describing the intended audience for the FAQ, and guidelines for obtaining assistance from the FAQ maintainer. Definition Began to re-word the overview of BSP trees in an attempt to make the definition clearer. 08/21/96
Online Resources Added a reference to Paton Lewis's Java based BSP tree demo applet. 08/07/96
Online Resources Added a reference to the Win95 BSP Tree Demo Application. 07/24/96
Online Resources Added reference to Michael Abrash's ftp site at Id. 07/11/96
Online Resources Added reference to Andrea Marchini and Stefano Tommesani's BSP tree compiler page. 05/01/96
General The FAQ articles may now be annotated using the forum mechanism. 04/28/96
Forum Experimental new discussion area for BSP trees. 04/24/96
General Added "Next" and "Previous" links on each page of the FAQ. 04/17/96
Whole FAQ The web search engines have been pointing a lot of people at the entire listing version of the FAQ, rather than at the indexed version. This has led to significantly increased load on our server, and slow response times. As a result, I have made it possible to view the whole document only by following the link from the index page. 04/12/96
Online Resources Update on A.T. Campbell's resources 04/08/96
Eliminating Recursion Initial Draft with code example 03/25/96
General White pages 03/22/96
Online Resources A.T. Campbell's home page
Update Mel Slater's location 03/21/96
Contribution Corrected e-mail address Online Resources Arcball FTP site
Paper by John Holmes, Jr. 02/19/96
Changes NEW Ray Tracing Draft implementation notes Analytic Visibility Draft contents Boolean Operations Spelling corrections
--
Last Update: 09/06/101 14:50:28
ABOUT THIS DOCUMENT General
The purpose of this document is to provide answers to Frequently Asked Questions about Binary Space Partitioning (BSP) Trees. The intended audience for this document has a working knowledge of computer graphics principles such as viewing transformations, clipping, and polygons. The intended audience also has knowledge of binary searching and sorting trees as covered in most computer algorithms textbooks.
A pointer to this document will be posted monthly to comp.graphics.algorithms and rec.games.programmer. It is available via WWW at the URL:
ftp://ftp.sgi.com/ot...faq/bspfaq.html The most recent newsgroup posting of this document is available via ftp at the following URL:
ftp://rtfm.mit.edu/p...ics/bsptree-faq Requesting the FAQ by mail
You can't. Sorry.
About the maintainer
This document was maintained by Bretton Wade, software engineer at Silicon Graphics, Incorporated, and graduate of the Cornell University Program of Computer Graphics. This resource is provided as a service to the computing community in the interest of disseminating useful information. Mr. Wade considers any personal exchange regarding BSP tree related technology to be confidential and not part of the business of Silicon Graphics, Incorporated. As of 2001-09-20, this FAQ does not appear to be maintained and the copy on ftp.sgi.com is the latest known copy.
Requesting assistance
The BSP tree FAQ maintainer receives a large number of requests for assistance. The maintainer makes every effort to respond to individual requests, but this is not always possible. There are several steps that you can take to insure a timely reply. First, be sure that any request for assistance is accompanied by a valid reply address. Second, try to limit your question to the topic of BSP trees. Third, if you are including source code, send only the portions necessary to illustrate your difficulty.
If you do not receive a reply within a reasonable amount of time, it most likely that your reply e-mail address is invalid. If you did not get an acknowledgement from the auto-responder, then you can be sure this is the case. Check your return address and try again.
Copyrights and distribution
This document, and all its associated parts, are Copyright (C) 1995-97, Bretton Wade. All rights reserved. Permisson to distribute this collection, in part or full, via electronic means (emailed, posted or archived) or printed copy are granted providing that no charges are involved, reasonable attempt is made to use the most current version, and all credits and copyright notices are retained. If you make a link to the WWW page, please inform the maintainer so he can construct reciprocal links.
Warranty and disclaimer
This article is provided as is without any express or implied warranties. While every effort has been taken to ensure the accuracy of the information contained in this article, the author/maintainer/contributors assume(s) no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein.
The contents of this article do not necessarily represent the opinions of Silicon Graphics, Incorporated.
--
Last Update: 09/20/101 11:02:10
ACKNOWLEDGEMENTS Web Space
Thank you to Silicon Graphics, Incorporated for kindly providing the web space for this document free of charge.
About the contributors
This document would not have been possible without the selfless contributions and efforts of many individuals. I would like to take the opportunity to thank each one of them. Please be aware that these people may not be amenable to recieving e-mail on a random basis.
Contributors
Bruce Naylor ([email="naylor%20@%20research.att.com"]mailto:naylor%20@%20research.att.com[/email])
Richard Lobb ([email="richard%20@%20cs.auckland.ac.nz"]mailto:richard%20@%20cs.auckland.ac.nz[/email])
Dani Lischinski ([email="danix%20@%20cs.washington.edu"]mailto:danix%20@%20cs.washington.edu[/email])
Chris Schoeneman ([email="crs%20@%20engr.sgi.com"]mailto:crs%20@%20engr.sgi.com[/email])
Philip Hubbard ([email="pmh%20@%20graphics.cornell.edu"]mailto:pmh%20@%20graphics.cornell.edu[/email])
Jim Arvo ([email="arvo%20@%20cs.caltech.edu"]mailto:arvo%20@%20cs.caltech.edu[/email])
Kevin Ryan ([email="kryan%20@%20access.digex.net"]mailto:kryan%20@%20access.digex.net[/email])
Joseph Fiore ([email="fiore%20@%20cs.buffalo.edu"]mailto:fiore%20@%20cs.buffalo.edu[/email])
Lukas Rosenthaler ([email="rosenth%20@%20foto.chemie.unibas.ch"]mailto:rosenth%20@%20foto.chemie.unibas.ch[/email])
Anson Tsao ([email="ansont%20@%20hookup.net"]mailto:ansont%20@%20hookup.net[/email])
Robert Zawarski ([email="zawarski%20@%20chaph.usc.edu"]mailto:zawarski%20@%20chaph.usc.edu[/email])
Ron Capelli ([email="capelli%20@%20vnet.ibm.com"]mailto:capelli%20@%20vnet.ibm.com[/email])
Eric A. Haines ([email="erich%20@%20eye.com"]mailto:erich%20@%20eye.com[/email])
Ian CR Mapleson ([email="mapleson%20@%20cee.hw.ac.uk"]mailto:mapleson%20@%20cee.hw.ac.uk[/email])
Richard Dorman ([email="richard%20@%20cs.wits.ac.za"]mailto:richard%20@%20cs.wits.ac.za[/email])
Steve Larsen ([email="larsen%20@%20sunset.cs.utah.edu"]mailto:larsen%20@%20sunset.cs.utah.edu[/email])
Timothy Miller ([email="tsm%20@%20cs.brown.edu"]mailto:tsm%20@%20cs.brown.edu[/email])
Ben Trumbore ([email="wbt%20@%20graphics.cornell.edu"]mailto:wbt%20@%20graphics.cornell.edu[/email])
Richard Matthias ([email="richardm%20@%20cogs.susx.ac.uk"]mailto:richardm%20@%20cogs.susx.ac.uk[/email])
Ken Shoemake ([email="shoemake%20@%20graphics.cis.upenn.edu"]mailto:shoemake%20@%20graphics.cis.upenn.edu[/email])
Seth Teller ([email="seth%20@%20theory.lcs.mit.edu"]mailto:seth%20@%20theory.lcs.mit.edu[/email])
Peter Shirley ([email="shirley%20@%20cs.utah.edu"]mailto:shirley%20@%20cs.utah.edu[/email])
Michael Abrash ([email="mikeab%20@%20idsoftware.com"]mailto:mikeab%20@%20idsoftware.com[/email])
Robert Schmidt ([email="robert%20@%20idt.unit.no"]mailto:robert%20@%20idt.unit.no[/email])
Samuel P. Uselton ([email="uselton%20@%20nas.nasa.gov"]mailto:uselton%20@%20nas.nasa.gov[/email])
Michael Brundage ([email="brundage%20@%20ipac.caltech.edu"]mailto:brundage%20@%20ipac.caltech.edu[/email])
If I have neglected to mention your name, and you contributed, please let me know immediately!
--
Last Update: 09/20/101 11:03:21
HOW CAN YOU CONTRIBUTE? As of 2001-09-20, this faq does not appear to be maintained.
--
Last Update: 09/20/101 11:03:55
ABOUT THE PSEUDO C++ CODE Overview
The general efficiency of C++ makes it a well suited language for programming computer graphics. Furthermore, the abstract nature of the language allows it to be used effectively as a psuedo code for demonstrative purposes. I will use C++ notation for all the examples in this document.
In order to provide effective examples, it is necessary to assume that certain classes already exist, and can be used without presenting excessive details of their operation. Basic classes such as lists and arrays fall into this category.
Other classes which will be very useful for examples need to be presented here, but the definitions will be generic to allow for freedom of interpretation. I assume points and vectors to each be an array of 3 real numbers (X, Y, Z).
Planes are represented as an array of 4 real numbers (A, B, C, D). The vector (A, B, C) is the normal vector to the plane. Polygons are structures composited from an array of points, which are the vertices, and a plane.
The overloaded operator for a dot product (inner product, scalar product, etc.) of two vectors is the '|' symbol. This has two advantages, the first of which is that it can't be confused with the scalar multiplication operator. The second is that precedence of C++ operators will usually require that dot product operations be parenthesized, which is consistent with the linear algebra notation for an inner product.
The code for BSP trees presented here is intended to be educational, and may or may not be very efficient. For the sake of clarity, the BSP tree itself will not be defined as a class.
--
Last Update: 09/06/101 14:50:29
Do you see issues with this article? Let us know.
(Editor's Note - this article requires additional formatting work and is incomplete)
BSP Tree Frequently Asked Questions (FAQ)
Questions
CHANGES
ABOUT THIS DOCUMENT
ACKNOWLEDGEMENTS
HOW CAN YOU CONTRIBUTE?
ABOUT THE PSEUDO C++ CODE
WHAT IS A BSP TREE?
HOW DO YOU BUILD A BSP TREE?
HOW DO YOU PARTITION A POLYGON WITH A PLANE?
HOW DO YOU REMOVE HIDDEN SURFACES WITH A BSP TREE?
HOW DO YOU COMPUTE ANALYTIC VISIBILITY WITH A BSP TREE?
HOW DO YOU ACCELERATE RAY TRACING WITH A BSP TREE?
HOW DO YOU PERFORM BOOLEAN OPERATIONS ON POLYTOPES WITH A BSP TREE?
HOW DO YOU PERFORM COLLISION DETECTION WITH A BSP TREE?
HOW DO YOU HANDLE DYNAMIC SCENES WITH A BSP TREE?
HOW DO YOU COMPUTE SHADOWS WITH A BSP TREE?
HOW DO YOU EXTRACT CONNECTIVITY INFORMATION FROM BSP TREES?
HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING?
HOW ARE BSP TREES USED IN DOOM?
HOW CAN YOU MAKE A BSP TREE MORE ROBUST?
HOW EFFICIENT IS A BSP TREE?
HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT?
HOW CAN YOU AVOID RECURSION?
WHAT IS THE HISTORY OF BSP TREES?
WHERE CAN YOU FIND SAMPLE CODE AND RELATED ONLINE RESOURCES?
REFERENCES
Answers
CHANGES Date Section Change 06/02/98
Online Resources Updated the pointer to A.T. Campbell's home page. 01/22/98
Online Resources Added a pointer to the Id Software source code and utilities (finally). 06/08/97
Building a tree Added definition of an autopartition. Efficiency Completely rewrote this section with a concise explanation of the complexity of HSR with an autopartition. Online Resources Updated link to Paton Lewis's BSP tree page, and added a link to Tom Hammersly's web page which describes his experience at implementing a BSP tree compiler and viewer. 06/01/97
Motion Planning Initial draft. Doom Removed text which is confusing and not quite informative enough. Still looking for a replacement. 04/29/97
Online Resources Updated the link to the Computational Gemoetry Pages. 04/25/97
What is... Corrected an error in the ascii-art version of the tree diagram. Building BSP Trees Corrected an error in the example code. 04/14/97
Boolean Ops Corrected an error: "... polygon EFGH is inserted ... one polygon at a time." was changed to "... is inserted ... one edge at a time." Thanks to Filip J. D. Uhlik for noticing this. 04/08/97
Online Resources Updated pointer to FTP site for the FAQ support files: ftp://ftp.sgi.com/other/bspfaq/. 04/02/97
Entire Document Moved document to reality.sgi.com. Changes were made to reflect the new host, but otherwise only a few minor HTML changes were made. 10/09/96
Acknowledgements Added a Michael Brundage to the acknowledgements. Online Resources Added a reference to GFX, a general graphics programming resource.
Added a reference to John Whitley's BSP tree tutorial page. 10/07/96
Definitions Added new definitions page to clarify some difficult terms. Ray Tracing Added a note about using the parent node of the ray origin as a hint for improving run-time performance. Efficiency Corrected a long standing error in the stated complexity of BSP trees for Hidden Surface Removal. 10/06/96
About Added new sub-sections describing the intended audience for the FAQ, and guidelines for obtaining assistance from the FAQ maintainer. Definition Began to re-word the overview of BSP trees in an attempt to make the definition clearer. 08/21/96
Online Resources Added a reference to Paton Lewis's Java based BSP tree demo applet. 08/07/96
Online Resources Added a reference to the Win95 BSP Tree Demo Application. 07/24/96
Online Resources Added reference to Michael Abrash's ftp site at Id. 07/11/96
Online Resources Added reference to Andrea Marchini and Stefano Tommesani's BSP tree compiler page. 05/01/96
General The FAQ articles may now be annotated using the forum mechanism. 04/28/96
Forum Experimental new discussion area for BSP trees. 04/24/96
General Added "Next" and "Previous" links on each page of the FAQ. 04/17/96
Whole FAQ The web search engines have been pointing a lot of people at the entire listing version of the FAQ, rather than at the indexed version. This has led to significantly increased load on our server, and slow response times. As a result, I have made it possible to view the whole document only by following the link from the index page. 04/12/96
Online Resources Update on A.T. Campbell's resources 04/08/96
Eliminating Recursion Initial Draft with code example 03/25/96
General White pages 03/22/96
Online Resources A.T. Campbell's home page
Update Mel Slater's location 03/21/96
Contribution Corrected e-mail address Online Resources Arcball FTP site
Paper by John Holmes, Jr. 02/19/96
Changes NEW Ray Tracing Draft implementation notes Analytic Visibility Draft contents Boolean Operations Spelling corrections
--
Last Update: 09/06/101 14:50:28
ABOUT THIS DOCUMENT General
The purpose of this document is to provide answers to Frequently Asked Questions about Binary Space Partitioning (BSP) Trees. The intended audience for this document has a working knowledge of computer graphics principles such as viewing transformations, clipping, and polygons. The intended audience also has knowledge of binary searching and sorting trees as covered in most computer algorithms textbooks.
A pointer to this document will be posted monthly to comp.graphics.algorithms and rec.games.programmer. It is available via WWW at the URL:
ftp://ftp.sgi.com/ot...faq/bspfaq.html The most recent newsgroup posting of this document is available via ftp at the following URL:
ftp://rtfm.mit.edu/p...ics/bsptree-faq Requesting the FAQ by mail
You can't. Sorry.
About the maintainer
This document was maintained by Bretton Wade, software engineer at Silicon Graphics, Incorporated, and graduate of the Cornell University Program of Computer Graphics. This resource is provided as a service to the computing community in the interest of disseminating useful information. Mr. Wade considers any personal exchange regarding BSP tree related technology to be confidential and not part of the business of Silicon Graphics, Incorporated. As of 2001-09-20, this FAQ does not appear to be maintained and the copy on ftp.sgi.com is the latest known copy.
Requesting assistance
The BSP tree FAQ maintainer receives a large number of requests for assistance. The maintainer makes every effort to respond to individual requests, but this is not always possible. There are several steps that you can take to insure a timely reply. First, be sure that any request for assistance is accompanied by a valid reply address. Second, try to limit your question to the topic of BSP trees. Third, if you are including source code, send only the portions necessary to illustrate your difficulty.
If you do not receive a reply within a reasonable amount of time, it most likely that your reply e-mail address is invalid. If you did not get an acknowledgement from the auto-responder, then you can be sure this is the case. Check your return address and try again.
Copyrights and distribution
This document, and all its associated parts, are Copyright (C) 1995-97, Bretton Wade. All rights reserved. Permisson to distribute this collection, in part or full, via electronic means (emailed, posted or archived) or printed copy are granted providing that no charges are involved, reasonable attempt is made to use the most current version, and all credits and copyright notices are retained. If you make a link to the WWW page, please inform the maintainer so he can construct reciprocal links.
Warranty and disclaimer
This article is provided as is without any express or implied warranties. While every effort has been taken to ensure the accuracy of the information contained in this article, the author/maintainer/contributors assume(s) no responsibility for errors or omissions, or for damages resulting from the use of the information contained herein.
The contents of this article do not necessarily represent the opinions of Silicon Graphics, Incorporated.
--
Last Update: 09/20/101 11:02:10
ACKNOWLEDGEMENTS Web Space
Thank you to Silicon Graphics, Incorporated for kindly providing the web space for this document free of charge.
About the contributors
This document would not have been possible without the selfless contributions and efforts of many individuals. I would like to take the opportunity to thank each one of them. Please be aware that these people may not be amenable to recieving e-mail on a random basis.
Contributors
Bruce Naylor ([email="naylor%20@%20research.att.com"]mailto:naylor%20@%20research.att.com[/email])
Richard Lobb ([email="richard%20@%20cs.auckland.ac.nz"]mailto:richard%20@%20cs.auckland.ac.nz[/email])
Dani Lischinski ([email="danix%20@%20cs.washington.edu"]mailto:danix%20@%20cs.washington.edu[/email])
Chris Schoeneman ([email="crs%20@%20engr.sgi.com"]mailto:crs%20@%20engr.sgi.com[/email])
Philip Hubbard ([email="pmh%20@%20graphics.cornell.edu"]mailto:pmh%20@%20graphics.cornell.edu[/email])
Jim Arvo ([email="arvo%20@%20cs.caltech.edu"]mailto:arvo%20@%20cs.caltech.edu[/email])
Kevin Ryan ([email="kryan%20@%20access.digex.net"]mailto:kryan%20@%20access.digex.net[/email])
Joseph Fiore ([email="fiore%20@%20cs.buffalo.edu"]mailto:fiore%20@%20cs.buffalo.edu[/email])
Lukas Rosenthaler ([email="rosenth%20@%20foto.chemie.unibas.ch"]mailto:rosenth%20@%20foto.chemie.unibas.ch[/email])
Anson Tsao ([email="ansont%20@%20hookup.net"]mailto:ansont%20@%20hookup.net[/email])
Robert Zawarski ([email="zawarski%20@%20chaph.usc.edu"]mailto:zawarski%20@%20chaph.usc.edu[/email])
Ron Capelli ([email="capelli%20@%20vnet.ibm.com"]mailto:capelli%20@%20vnet.ibm.com[/email])
Eric A. Haines ([email="erich%20@%20eye.com"]mailto:erich%20@%20eye.com[/email])
Ian CR Mapleson ([email="mapleson%20@%20cee.hw.ac.uk"]mailto:mapleson%20@%20cee.hw.ac.uk[/email])
Richard Dorman ([email="richard%20@%20cs.wits.ac.za"]mailto:richard%20@%20cs.wits.ac.za[/email])
Steve Larsen ([email="larsen%20@%20sunset.cs.utah.edu"]mailto:larsen%20@%20sunset.cs.utah.edu[/email])
Timothy Miller ([email="tsm%20@%20cs.brown.edu"]mailto:tsm%20@%20cs.brown.edu[/email])
Ben Trumbore ([email="wbt%20@%20graphics.cornell.edu"]mailto:wbt%20@%20graphics.cornell.edu[/email])
Richard Matthias ([email="richardm%20@%20cogs.susx.ac.uk"]mailto:richardm%20@%20cogs.susx.ac.uk[/email])
Ken Shoemake ([email="shoemake%20@%20graphics.cis.upenn.edu"]mailto:shoemake%20@%20graphics.cis.upenn.edu[/email])
Seth Teller ([email="seth%20@%20theory.lcs.mit.edu"]mailto:seth%20@%20theory.lcs.mit.edu[/email])
Peter Shirley ([email="shirley%20@%20cs.utah.edu"]mailto:shirley%20@%20cs.utah.edu[/email])
Michael Abrash ([email="mikeab%20@%20idsoftware.com"]mailto:mikeab%20@%20idsoftware.com[/email])
Robert Schmidt ([email="robert%20@%20idt.unit.no"]mailto:robert%20@%20idt.unit.no[/email])
Samuel P. Uselton ([email="uselton%20@%20nas.nasa.gov"]mailto:uselton%20@%20nas.nasa.gov[/email])
Michael Brundage ([email="brundage%20@%20ipac.caltech.edu"]mailto:brundage%20@%20ipac.caltech.edu[/email])
If I have neglected to mention your name, and you contributed, please let me know immediately!
--
Last Update: 09/20/101 11:03:21
HOW CAN YOU CONTRIBUTE? As of 2001-09-20, this faq does not appear to be maintained.
--
Last Update: 09/20/101 11:03:55
ABOUT THE PSEUDO C++ CODE Overview
The general efficiency of C++ makes it a well suited language for programming computer graphics. Furthermore, the abstract nature of the language allows it to be used effectively as a psuedo code for demonstrative purposes. I will use C++ notation for all the examples in this document.
In order to provide effective examples, it is necessary to assume that certain classes already exist, and can be used without presenting excessive details of their operation. Basic classes such as lists and arrays fall into this category.
Other classes which will be very useful for examples need to be presented here, but the definitions will be generic to allow for freedom of interpretation. I assume points and vectors to each be an array of 3 real numbers (X, Y, Z).
Planes are represented as an array of 4 real numbers (A, B, C, D). The vector (A, B, C) is the normal vector to the plane. Polygons are structures composited from an array of points, which are the vertices, and a plane.
The overloaded operator for a dot product (inner product, scalar product, etc.) of two vectors is the '|' symbol. This has two advantages, the first of which is that it can't be confused with the scalar multiplication operator. The second is that precedence of C++ operators will usually require that dot product operations be parenthesized, which is consistent with the linear algebra notation for an inner product.
The code for BSP trees presented here is intended to be educational, and may or may not be very efficient. For the sake of clarity, the BSP tree itself will not be defined as a class.
--
Last Update: 09/06/101 14:50:29
HOW DO YOU BUILD A BSP TREE? Overview
Given a set of polygons in three dimensional space, we want to build a BSP tree which contains all of the polygons. For now, we will ignore the question of how the resulting tree is going to be used.
The algorithm to build a BSP tree is very simple:
Select a partition plane.
Partition the set of polygons with the plane.
Recurse with each of the two new sets.
Choosing the partition plane
The choice of partition plane depends on how the tree will be used, and what sort of efficiency criteria you have for the construction. For some purposes, it is appropriate to choose the partition plane from the input set of polygons (called an autopartition). Other applications may benefit more from axis aligned orthogonal partitions.
In any case, you want to evaluate how your choice will affect the results. It is desirable to have a balanced tree, where each leaf contains roughly the same number of polygons. However, there is some cost in achieving this. If a polygon happens to span the partition plane, it will be split into two or more pieces. A poor choice of the partition plane can result in many such splits, and a marked increase in the number of polygons. Usually there will be some trade off between a well balanced tree and a large number of splits.
Partitioning polygons
Partitioning a set of polygons with a plane is done by classifying each member of the set with respect to the plane. If a polygon lies entirely to one side or the other of the plane, then it is not modified, and is added to the partition set for the side that it is on. If a polygon spans the plane, it is split into two or more pieces and the resulting parts are added to the sets associated with either side as appropriate.
When to stop
The decision to terminate tree construction is, again, a matter of the specific application. Some methods terminate when the number of polygons in a leaf node is below a maximum value. Other methods continue until every polygon is placed in an internal node. Another criteria is a maximum tree depth.
Pseudo C++ code example
Here is an example of how you might code a BSP tree:
struct BSP_tree { plane partition; list polygons; BSP_tree front, back; }; This structure definition will be used for all subsequent example code. It stores pointers to its children, the partitioning plane for the node, and a list of polygons coincident with the partition plane. For this example, there will always be at least one polygon in the coincident list: the polygon used to determine the partition plane. A constructor method for this structure should initialize the child pointers to NULL. void Build_BSP_Tree (BSP_tree tree, list polygons) { polygon root = polygons.Get_From_List (); tree->partition = root->Get_Plane (); tree->polygons.Add_To_List (root); list front_list, back_list; polygon poly; while ((poly = polygons.Get_From_List ()) != 0) { int result = tree->partition.Classify_Polygon (poly); switch (result) { case COINCIDENT: tree->polygons.Add_To_List (poly); break; case IN_BACK_OF: back_list.Add_To_List (poly); break; case IN_FRONT_OF: front_list.Add_To_List (poly); break; case SPANNING: polygon front_piece, back_piece; Split_Polygon (poly, tree->partition, front_piece, back_piece); back_list.Add_To_List (back_piece); front_list.Add_To_List (front_piece); break; } } if ( ! front_list.Is_Empty_List ()) { tree->front = new BSP_tree; Build_BSP_Tree (tree->front, front_list); } if ( ! back_list.Is_Empty_List ()) { tree->back = new BSP_tree; Build_BSP_Tree (tree->back, back_list); } } This routine recursively constructs a BSP tree using the above definition. It takes the first polygon from the input list and uses it to partition the remainder of the set. The routine then calls itself recursively with each of the two partitions. This implementation assumes that all of the input polygons are convex. One obvious improvement to this example is to choose the partitioning plane more intelligently. This issue is addressed separately in the section, "How can you make a BSP Tree more efficient?".
--
Last Update: 09/06/101 14:50:29
HOW DO YOU PARTITION A POLYGON WITH A PLANE? Overview
Partitioning a polygon with a plane is a matter of determining which side of the plane the polygon is on. This is referred to as a front/back test, and is performed by testing each point in the polygon against the plane. If all of the points lie to one side of the plane, then the entire polygon is on that side and does not need to be split. If some points lie on both sides of the plane, then the polygon is split into two or more pieces.
The basic algorithm is to loop across all the edges of the polygon and find those for which one vertex is on each side of the partition plane. The intersection points of these edges and the plane are computed, and those points are used as new vertices for the resulting pieces.
Implementation notes
Classifying a point with respect to a plane is done by passing the (x, y, z) values of the point into the plane equation, Ax + By + Cz + D = 0. The result of this operation is the distance from the plane to the point along the plane's normal vector. It will be positive if the point is on the side of the plane pointed to by the normal vector, negative otherwise. If the result is 0, the point is on the plane.
For those not familiar with the plane equation, The values A, B, and C are the coordinate values of the normal vector. D can be calculated by substituting a point known to be on the plane for x, y, and z.
Convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.
Pseudo C++ code example
Here is a very basic function to split a convex polygon with a plane:
void Split_Polygon (polygon poly, plane part, polygon &front, polygon &back) { int count = poly->NumVertices (), out_c = 0, in_c = 0; point ptA, ptB, outpts[MAXPTS], inpts[MAXPTS]; real sideA, sideB; ptA = poly->Vertex (count - 1); sideA = part->Classify_Point (ptA); for (short i = -1; ++i < count;) { ptB = poly->Vertex (i); sideB = part->Classify_Point (ptB); if (sideB > 0) { if (sideA < 0) { // compute the intersection point of the line // from point A to point B with the partition // plane. This is a simple ray-plane intersection. vector v = ptB - ptA; real sect = - part->Classify_Point (ptA) / (part->Normal () | v); outpts[out_c++] = inpts[in_c++] = ptA + (v sect); } outpts[out_c++] = ptB; } else if (sideB < 0) { if (sideA > 0) { // compute the intersection point of the line // from point A to point B with the partition // plane. This is a simple ray-plane intersection. vector v = ptB - ptA; real sect = - part->Classify_Point (ptA) / (part->Normal () | v); outpts[out_c++] = inpts[in_c++] = ptA + (v * sect); } inpts[in_c++] = ptB; } else outpts[out_c++] = inpts[in_c++] = ptB; ptA = ptB; sideA = sideB; } front = new polygon (outpts, out_c); back = new polygon (inpts, in_c); } A simple extension to this code that is good for BSP trees is to combine its functionality with the routine to classify a polygon with respect to a plane. Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.
Given a set of polygons in three dimensional space, we want to build a BSP tree which contains all of the polygons. For now, we will ignore the question of how the resulting tree is going to be used.
The algorithm to build a BSP tree is very simple:
Select a partition plane.
Partition the set of polygons with the plane.
Recurse with each of the two new sets.
Choosing the partition plane
The choice of partition plane depends on how the tree will be used, and what sort of efficiency criteria you have for the construction. For some purposes, it is appropriate to choose the partition plane from the input set of polygons (called an autopartition). Other applications may benefit more from axis aligned orthogonal partitions.
In any case, you want to evaluate how your choice will affect the results. It is desirable to have a balanced tree, where each leaf contains roughly the same number of polygons. However, there is some cost in achieving this. If a polygon happens to span the partition plane, it will be split into two or more pieces. A poor choice of the partition plane can result in many such splits, and a marked increase in the number of polygons. Usually there will be some trade off between a well balanced tree and a large number of splits.
Partitioning polygons
Partitioning a set of polygons with a plane is done by classifying each member of the set with respect to the plane. If a polygon lies entirely to one side or the other of the plane, then it is not modified, and is added to the partition set for the side that it is on. If a polygon spans the plane, it is split into two or more pieces and the resulting parts are added to the sets associated with either side as appropriate.
When to stop
The decision to terminate tree construction is, again, a matter of the specific application. Some methods terminate when the number of polygons in a leaf node is below a maximum value. Other methods continue until every polygon is placed in an internal node. Another criteria is a maximum tree depth.
Pseudo C++ code example
Here is an example of how you might code a BSP tree:
struct BSP_tree { plane partition; list polygons; BSP_tree front, back; }; This structure definition will be used for all subsequent example code. It stores pointers to its children, the partitioning plane for the node, and a list of polygons coincident with the partition plane. For this example, there will always be at least one polygon in the coincident list: the polygon used to determine the partition plane. A constructor method for this structure should initialize the child pointers to NULL. void Build_BSP_Tree (BSP_tree tree, list polygons) { polygon root = polygons.Get_From_List (); tree->partition = root->Get_Plane (); tree->polygons.Add_To_List (root); list front_list, back_list; polygon poly; while ((poly = polygons.Get_From_List ()) != 0) { int result = tree->partition.Classify_Polygon (poly); switch (result) { case COINCIDENT: tree->polygons.Add_To_List (poly); break; case IN_BACK_OF: back_list.Add_To_List (poly); break; case IN_FRONT_OF: front_list.Add_To_List (poly); break; case SPANNING: polygon front_piece, back_piece; Split_Polygon (poly, tree->partition, front_piece, back_piece); back_list.Add_To_List (back_piece); front_list.Add_To_List (front_piece); break; } } if ( ! front_list.Is_Empty_List ()) { tree->front = new BSP_tree; Build_BSP_Tree (tree->front, front_list); } if ( ! back_list.Is_Empty_List ()) { tree->back = new BSP_tree; Build_BSP_Tree (tree->back, back_list); } } This routine recursively constructs a BSP tree using the above definition. It takes the first polygon from the input list and uses it to partition the remainder of the set. The routine then calls itself recursively with each of the two partitions. This implementation assumes that all of the input polygons are convex. One obvious improvement to this example is to choose the partitioning plane more intelligently. This issue is addressed separately in the section, "How can you make a BSP Tree more efficient?".
--
Last Update: 09/06/101 14:50:29
HOW DO YOU PARTITION A POLYGON WITH A PLANE? Overview
Partitioning a polygon with a plane is a matter of determining which side of the plane the polygon is on. This is referred to as a front/back test, and is performed by testing each point in the polygon against the plane. If all of the points lie to one side of the plane, then the entire polygon is on that side and does not need to be split. If some points lie on both sides of the plane, then the polygon is split into two or more pieces.
The basic algorithm is to loop across all the edges of the polygon and find those for which one vertex is on each side of the partition plane. The intersection points of these edges and the plane are computed, and those points are used as new vertices for the resulting pieces.
Implementation notes
Classifying a point with respect to a plane is done by passing the (x, y, z) values of the point into the plane equation, Ax + By + Cz + D = 0. The result of this operation is the distance from the plane to the point along the plane's normal vector. It will be positive if the point is on the side of the plane pointed to by the normal vector, negative otherwise. If the result is 0, the point is on the plane.
For those not familiar with the plane equation, The values A, B, and C are the coordinate values of the normal vector. D can be calculated by substituting a point known to be on the plane for x, y, and z.
Convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.
Pseudo C++ code example
Here is a very basic function to split a convex polygon with a plane:
void Split_Polygon (polygon poly, plane part, polygon &front, polygon &back) { int count = poly->NumVertices (), out_c = 0, in_c = 0; point ptA, ptB, outpts[MAXPTS], inpts[MAXPTS]; real sideA, sideB; ptA = poly->Vertex (count - 1); sideA = part->Classify_Point (ptA); for (short i = -1; ++i < count;) { ptB = poly->Vertex (i); sideB = part->Classify_Point (ptB); if (sideB > 0) { if (sideA < 0) { // compute the intersection point of the line // from point A to point B with the partition // plane. This is a simple ray-plane intersection. vector v = ptB - ptA; real sect = - part->Classify_Point (ptA) / (part->Normal () | v); outpts[out_c++] = inpts[in_c++] = ptA + (v sect); } outpts[out_c++] = ptB; } else if (sideB < 0) { if (sideA > 0) { // compute the intersection point of the line // from point A to point B with the partition // plane. This is a simple ray-plane intersection. vector v = ptB - ptA; real sect = - part->Classify_Point (ptA) / (part->Normal () | v); outpts[out_c++] = inpts[in_c++] = ptA + (v * sect); } inpts[in_c++] = ptB; } else outpts[out_c++] = inpts[in_c++] = ptB; ptA = ptB; sideA = sideB; } front = new polygon (outpts, out_c); back = new polygon (inpts, in_c); } A simple extension to this code that is good for BSP trees is to combine its functionality with the routine to classify a polygon with respect to a plane. Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.
HOW DO YOU REMOVE HIDDEN SURFACES WITH A BSP TREE? Overview
Probably the most common application of BSP trees is hidden surface removal in three dimensions. BSP trees provide an elegant, efficient method for sorting polygons via a depth first tree walk. This fact can be exploited in a back to front "painter's algorithm" approach to the visible surface problem, or a front to back scanline approach.
BSP trees are well suited to interactive display of static (not moving) geometry because the tree can be constructed as a preprocess. Then the display from any arbitrary viewpoint can be done in linear time. Adding dynamic (moving) objects to the scene is discussed in another section of this document.
Painter's algorithm
The idea behind the painter's algorithm is to draw polygons far away from the eye first, followed by drawing those that are close to the eye. Hidden surfaces will be written over in the image as the surfaces that obscure them are drawn. One condition for a successful painter's algorithm is that there be a single plane which separates any two objects. This means that it might be necessary to split polygons in certain configurations. For example, this case can not be drawn correctly with a painter's algorithm:
+------+ | | +---------------| |--+ | | | | | | | | | | | | | +--------| |--+ | | | | +--| |--------+ | | | | | | | | | | | | | +--| |---------------+ | | +------+ One reason that BSP trees are so elegant for the painter's algorithm is that the splitting of difficult polygons is an automatic part of tree construction. Note that only one of these two polygons needs to be split in order to resolve the problem. To draw the contents of the tree, perform a back to front tree traversal. Begin at the root node and classify the eye point with respect to its partition plane. Draw the subtree at the far child from the eye, then draw the polygons in this node, then draw the near subtree. Repeat this procedure recursively for each subtree.
Scanline hidden surface removal
It is just as easy to traverse the BSP tree in front to back order as it is for back to front. We can use this to our advantage in a scanline method method by using a write mask which will prevent pixels from being written more than once. This will represent significant speedups if a complex lighting model is evaluated for each pixel, because the painter's algorithm will blindly evaluate the same pixel many times.
The trick to making a scanline approach successful is to have an efficient method for masking pixels. One way to do this is to maintain a list of pixel spans which have not yet been written to for each scan line. For each polygon scan converted, only pixels in the available spans are written, and the spans are updated accordingly.
The scan line spans can be represented as binary trees, which are just one dimensional BSP trees. This technique can be expanded to a two dimensional screen coverage algorithm using a two dimensional BSP tree to represent the masked regions. Any convex partitioning scheme, such as a quadtree, can be used with similar effect.
Implementation notes
When building a BSP tree specifically for hidden surface removal, the partition planes are usually chosen from the input polygon set. However, any arbitrary plane can be used if there are no intersecting or concave polygons, as in the example above.
Pseudo C++ code example
Using the BSP_tree structure defined in the section, "How do you build a BSP Tree?", here is a simple example of a back to front tree traversal:
void Draw_BSP_Tree (BSP_tree tree, point eye) { real result = tree->partition.Classify_Point (eye); if (result > 0) { Draw_BSP_Tree (tree->back, eye); tree->polygons.Draw_Polygon_List (); Draw_BSP_Tree (tree->front, eye); } else if (result < 0) { Draw_BSP_Tree (tree->front, eye); tree->polygons.Draw_Polygon_List (); Draw_BSP_Tree (tree->back, eye); } else // result is 0 { // the eye point is on the partition plane... Draw_BSP_Tree (tree->front, eye); Draw_BSP_Tree (tree->back, eye); } } If the eye point is classified as being on the partition plane, the drawing order is unclear. This is not a problem if the Draw_Polygon_List routine is smart enough to not draw polygons that are not within the viewing frustum. The coincident polygon list does not need to be drawn in this case, because those polygons will not be visible to the user. It is possible to substantially improve the quality of this example by including the viewing direction vector in the computation. You can determine that entire subtrees are behind the viewer by comparing the view vector to the partition plane normal vector. This test can also make a better decision about tree drawing when the eye point lies on the partition plane. It is worth noting that this improvement resembles the method for tracing a ray through a BSP tree, which is discussed in another section of this document.
Front to back tree traversal is accomplished in exactly the same manner, except that the recursive calls to Draw_BSP_Tree occur in reverse order.
--
Last Update: 09/06/101 14:50:29
HOW DO YOU COMPUTE ANALYTIC VISIBILITY WITH A BSP TREE? Overview
Analytic visibility is a term which describes the list of surfaces visible from a single point in a scene. Analytic visibility is important to the architectural community because it may be necessary to obtain a visible lines only view of a building for output to a pen plotter. It is also important to the global illumination community because it makes it possible to accurately compute the form factor from a differential area to a patch. Analytic visibility is also used in a preprocessing step to speed up walkthrough renderings for large models.
BSP trees can be used to compute visible fragments of polygons in a scene in at least two different ways. Both methods involve the use of a bsp tree for front to back traversal, and a second tree which describes the visible space in the viewing volume.
Screen partitioning
This method uses a two dimensional BSP tree to partition the viewing plane into regions which have and have not been covered by previously rendered polygons. Whenever a polygon is rendered, it is inserted into the screen tree and clipped to the currently visible region. In the process, the visible region of the polygon is removed from the visible region of the screen.
Beam tree
This method clips each polygon drawn to a beam tree which defines the viewable area. The beam tree originates as a description of the viewing frustum, and is in fact a special kind of BSP tree. When a new polygon is rendered, it is first passed through the beam tree to obtain the visible fragments in a manner very similar to the union operation for boolean modelling. Each fragment is then used to describe a new beam consisting of a series of planes through the eye point and each edge of the fragment. These planes become the hyperplanes used for defining new partitions in the beam tree.
First DRAFT.
--
Last Update: 09/06/101 14:50:28
HOW DO YOU ACCELERATE RAY TRACING WITH A BSP TREE? Overview
Ray tracing with a BSP tree is very similar to hidden surface removal with a BSP tree. The algorithm is a simple forward tree walk, with a few additions that apply to ray casting. See Jim Arvo's voxel walking algorithm for ray tracing excerpted from the Ray Tracing News.
Implementation notes
Probably the biggest difference between ray tracing and other applications of BSP trees is that ray tracing does not require splitting of primitives to obtain correct results. This means that the hyperplanes can, and should, be chosen strictly for tree balance.
A large improvement can be made over the voxel walking algorithm for recursive ray tracing by using the parent node of the ray origin as a hint.
Because ray tracing is a spatial classification problem, balancing is the key to performance. Most spatial partitioning schemes for accellerating ray tracing use a criteria called "occupancy", which refers to the number of primitives residing in each partition. A BSP tree which has approximately the same occupancy for all partitions is balanced.
Balancing is discussed elsewhere in this document.
MORE TO COME
--
Last Update: 09/20/101 11:05:05
HOW DO YOU PERFORM BOOLEAN OPERATIONS ON POLYTOPES WITH A BSP TREE? Overview
There are two major classes of solid modeling methods with BSP trees. For both methods, it is useful to introduce the notion of an in/out test.
An in/out test is a different way of talking about the front/back test we have been using to classify points with respect to planes. The necessity for this shift in thought is evident when considering polytopes instead of just polygons. A point can not be merely in front or back of a polytope, but inside or outside. Somewhat formally, a point is inside of a convex polytope if it is inside of, or in back of, each hyperplane which composes the polytope, otherwise it is outside.
Incremental construction
Incremental construction of a BSP Tree is the process of inserting convex polytopes into the tree one by one. Each polytope has to be processed according to the operation desired.
It is useful to examine the construction process in two dimensions. Consider the following figure:
A B +-------------+ | | | | | E | F | +-----+-------+ | | | | | | | | | | | | +-------+-----+ | D | C | | | | | +-------------+ H G Two polygons, ABCD, and EFGH, are to be inserted into the tree. We wish to find the union of these two polygons. Start by inserting polygon ABCD into the tree, choosing the splitting hyperplanes to be coincident with the edges. The tree looks like this after insertion of ABCD: AB -/ \+ / \ / BC -/ \+ / \ / CD -/ \+ / \ / DA -/ \+ / \ Now, polygon EFGH is inserted into the tree, one edge at a time. The result looks like this: A B +-------------+ | | | | | E |J F | +-----+-------+ | | | | | | | | | | | | +-------+-----+ | D |L :C | | : | | : | +-----+-------+ H K G AB -/ \+ / \ / BC -/ \+ / \ / \ CD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ / \ \ EJ KH \ -/ \+ -/ \+ \ / \ / \ \ / / \ LE HL JF -/ \+ -/ \+ -/ \+ / \ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ Notice that when we insert EFGH, we split edges EF and HE along the edges of ABCD. this has the effect of dividing these segments into pieces which are inside ABCD, and outside ABCD. Segments EJ and LE will not be part of the boundary of the union. We could have saved our selves some work by not inserting them into the tree at all. For a union operation, you can always throw away segments that land in inside nodes. You must be careful about this though. What I mean is that any segments which land in inside nodes of the pre-existing tree, not the tree as it is being constructed. EJ and LE landed in an inside node of the tree for polygon ABCD, and so can be discarded. Our tree now looks like this:
. A B +-------------+ | | | | | |J F | +-------+ | | | | | | | | | +-------+-----+ | D |L :C | | : | | : | +-----+-------+ H K G AB -/ \+ / \ / BC -/ \+ / \ / \ CD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ \ \ KH \ -/ \+ \ / \ \ / \ HL JF -/ \+ -/ \+ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ Now, we would like some way to eliminate the segments JC and CL, so that we will be left with the boundary segments of the union. Examine the segment BC in the tree. What we would like to do is split BC with the hyperplane JF. Conveniently, we can do this by pushing the BC segment through the node for JF. The resulting segments can be classified with the rest of the JF subtree. Notice that the segment BJ lands in an out node, and that JC lands in an in node. Remembering that we can discard interior nodes, we can eliminate JC. The segment BJ replaces BC in the original tree. This process is repeated for segment CD, yielding the segments CL and LD. CL is discarded as landing in an interior node, and LD replaces CD in the original tree. The result looks like this: . A B +-------------+ | | | | | |J F | +-------+ | | | | | L | +-------+ | D | | | | | | +-----+-------+ H K G AB -/ \+ / \ / BJ -/ \+ / \ / \ LD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ \ \ KH \ -/ \+ \ / \ \ / \ HL JF -/ \+ -/ \+ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ As you can see, the result is the union of the polygons ABCD and EFGH. To perform other boolean operations, the process is similar. For intersection, you discard segments which land in exterior nodes instead of internal ones. The difference operation is special. It requires that you invert the polytope before insertion. For simple objects, this can be achieved by scaling with a factor of -1. The insertion process is then conducted as an intersection operation, where segments landing in external nodes are discarded.
Tree merging
--
Last Update: 09/06/101 14:50:28
HOW DO YOU PERFORM COLLISION DETECTION WITH A BSP TREE? Overview
Detecting whether or not a point moving along a line intersects some object in space is essentially a ray tracing problem. Detecting whether or not two complex objects intersect is something of a tree merging problem.
Typically, motion is computed in a series of Euler steps. This just means that the motion is computed at discrete time intervals using some description of the speed of motion. For any given point P moving from point A with a velocity V, it's location can be computed at time T as P = A + (T V).
Consider the case where T = 1, and we are computing the motion in one second steps. To find out if the point P has collided with any part of the scene, we will first compute the endpoints of the motion for this time step. P1 = A + V, and P2 = A + (2 V). These two endpoints will be classified with respect to the BSP tree. If P1 is outside of all objects, and P2 is inside some object, then an intersection has clearly occurred. However, if P2 is also outside, we still have to check for a collision in between.
Two approaches are possible. The first is commonly used in applications like games, where speed is critical, and accuracy is not. This approach is to recursively divide the motion segment in half, and check the midpoint for containment by some object. Typically, it is good enough to say that an intersection occurred, and not be very accurate about where it occurred.
The second approach, which is more accurate, but also more time consuming, is to treat the motion segment as a ray, and intersect the ray with the BSP Tree. This also has the advantage that the motion resulting from the impact can be computed more accurately.
Probably the most common application of BSP trees is hidden surface removal in three dimensions. BSP trees provide an elegant, efficient method for sorting polygons via a depth first tree walk. This fact can be exploited in a back to front "painter's algorithm" approach to the visible surface problem, or a front to back scanline approach.
BSP trees are well suited to interactive display of static (not moving) geometry because the tree can be constructed as a preprocess. Then the display from any arbitrary viewpoint can be done in linear time. Adding dynamic (moving) objects to the scene is discussed in another section of this document.
Painter's algorithm
The idea behind the painter's algorithm is to draw polygons far away from the eye first, followed by drawing those that are close to the eye. Hidden surfaces will be written over in the image as the surfaces that obscure them are drawn. One condition for a successful painter's algorithm is that there be a single plane which separates any two objects. This means that it might be necessary to split polygons in certain configurations. For example, this case can not be drawn correctly with a painter's algorithm:
+------+ | | +---------------| |--+ | | | | | | | | | | | | | +--------| |--+ | | | | +--| |--------+ | | | | | | | | | | | | | +--| |---------------+ | | +------+ One reason that BSP trees are so elegant for the painter's algorithm is that the splitting of difficult polygons is an automatic part of tree construction. Note that only one of these two polygons needs to be split in order to resolve the problem. To draw the contents of the tree, perform a back to front tree traversal. Begin at the root node and classify the eye point with respect to its partition plane. Draw the subtree at the far child from the eye, then draw the polygons in this node, then draw the near subtree. Repeat this procedure recursively for each subtree.
Scanline hidden surface removal
It is just as easy to traverse the BSP tree in front to back order as it is for back to front. We can use this to our advantage in a scanline method method by using a write mask which will prevent pixels from being written more than once. This will represent significant speedups if a complex lighting model is evaluated for each pixel, because the painter's algorithm will blindly evaluate the same pixel many times.
The trick to making a scanline approach successful is to have an efficient method for masking pixels. One way to do this is to maintain a list of pixel spans which have not yet been written to for each scan line. For each polygon scan converted, only pixels in the available spans are written, and the spans are updated accordingly.
The scan line spans can be represented as binary trees, which are just one dimensional BSP trees. This technique can be expanded to a two dimensional screen coverage algorithm using a two dimensional BSP tree to represent the masked regions. Any convex partitioning scheme, such as a quadtree, can be used with similar effect.
Implementation notes
When building a BSP tree specifically for hidden surface removal, the partition planes are usually chosen from the input polygon set. However, any arbitrary plane can be used if there are no intersecting or concave polygons, as in the example above.
Pseudo C++ code example
Using the BSP_tree structure defined in the section, "How do you build a BSP Tree?", here is a simple example of a back to front tree traversal:
void Draw_BSP_Tree (BSP_tree tree, point eye) { real result = tree->partition.Classify_Point (eye); if (result > 0) { Draw_BSP_Tree (tree->back, eye); tree->polygons.Draw_Polygon_List (); Draw_BSP_Tree (tree->front, eye); } else if (result < 0) { Draw_BSP_Tree (tree->front, eye); tree->polygons.Draw_Polygon_List (); Draw_BSP_Tree (tree->back, eye); } else // result is 0 { // the eye point is on the partition plane... Draw_BSP_Tree (tree->front, eye); Draw_BSP_Tree (tree->back, eye); } } If the eye point is classified as being on the partition plane, the drawing order is unclear. This is not a problem if the Draw_Polygon_List routine is smart enough to not draw polygons that are not within the viewing frustum. The coincident polygon list does not need to be drawn in this case, because those polygons will not be visible to the user. It is possible to substantially improve the quality of this example by including the viewing direction vector in the computation. You can determine that entire subtrees are behind the viewer by comparing the view vector to the partition plane normal vector. This test can also make a better decision about tree drawing when the eye point lies on the partition plane. It is worth noting that this improvement resembles the method for tracing a ray through a BSP tree, which is discussed in another section of this document.
Front to back tree traversal is accomplished in exactly the same manner, except that the recursive calls to Draw_BSP_Tree occur in reverse order.
--
Last Update: 09/06/101 14:50:29
HOW DO YOU COMPUTE ANALYTIC VISIBILITY WITH A BSP TREE? Overview
Analytic visibility is a term which describes the list of surfaces visible from a single point in a scene. Analytic visibility is important to the architectural community because it may be necessary to obtain a visible lines only view of a building for output to a pen plotter. It is also important to the global illumination community because it makes it possible to accurately compute the form factor from a differential area to a patch. Analytic visibility is also used in a preprocessing step to speed up walkthrough renderings for large models.
BSP trees can be used to compute visible fragments of polygons in a scene in at least two different ways. Both methods involve the use of a bsp tree for front to back traversal, and a second tree which describes the visible space in the viewing volume.
Screen partitioning
This method uses a two dimensional BSP tree to partition the viewing plane into regions which have and have not been covered by previously rendered polygons. Whenever a polygon is rendered, it is inserted into the screen tree and clipped to the currently visible region. In the process, the visible region of the polygon is removed from the visible region of the screen.
Beam tree
This method clips each polygon drawn to a beam tree which defines the viewable area. The beam tree originates as a description of the viewing frustum, and is in fact a special kind of BSP tree. When a new polygon is rendered, it is first passed through the beam tree to obtain the visible fragments in a manner very similar to the union operation for boolean modelling. Each fragment is then used to describe a new beam consisting of a series of planes through the eye point and each edge of the fragment. These planes become the hyperplanes used for defining new partitions in the beam tree.
First DRAFT.
--
Last Update: 09/06/101 14:50:28
HOW DO YOU ACCELERATE RAY TRACING WITH A BSP TREE? Overview
Ray tracing with a BSP tree is very similar to hidden surface removal with a BSP tree. The algorithm is a simple forward tree walk, with a few additions that apply to ray casting. See Jim Arvo's voxel walking algorithm for ray tracing excerpted from the Ray Tracing News.
Implementation notes
Probably the biggest difference between ray tracing and other applications of BSP trees is that ray tracing does not require splitting of primitives to obtain correct results. This means that the hyperplanes can, and should, be chosen strictly for tree balance.
A large improvement can be made over the voxel walking algorithm for recursive ray tracing by using the parent node of the ray origin as a hint.
Because ray tracing is a spatial classification problem, balancing is the key to performance. Most spatial partitioning schemes for accellerating ray tracing use a criteria called "occupancy", which refers to the number of primitives residing in each partition. A BSP tree which has approximately the same occupancy for all partitions is balanced.
Balancing is discussed elsewhere in this document.
MORE TO COME
--
Last Update: 09/20/101 11:05:05
HOW DO YOU PERFORM BOOLEAN OPERATIONS ON POLYTOPES WITH A BSP TREE? Overview
There are two major classes of solid modeling methods with BSP trees. For both methods, it is useful to introduce the notion of an in/out test.
An in/out test is a different way of talking about the front/back test we have been using to classify points with respect to planes. The necessity for this shift in thought is evident when considering polytopes instead of just polygons. A point can not be merely in front or back of a polytope, but inside or outside. Somewhat formally, a point is inside of a convex polytope if it is inside of, or in back of, each hyperplane which composes the polytope, otherwise it is outside.
Incremental construction
Incremental construction of a BSP Tree is the process of inserting convex polytopes into the tree one by one. Each polytope has to be processed according to the operation desired.
It is useful to examine the construction process in two dimensions. Consider the following figure:
A B +-------------+ | | | | | E | F | +-----+-------+ | | | | | | | | | | | | +-------+-----+ | D | C | | | | | +-------------+ H G Two polygons, ABCD, and EFGH, are to be inserted into the tree. We wish to find the union of these two polygons. Start by inserting polygon ABCD into the tree, choosing the splitting hyperplanes to be coincident with the edges. The tree looks like this after insertion of ABCD: AB -/ \+ / \ / BC -/ \+ / \ / CD -/ \+ / \ / DA -/ \+ / \ Now, polygon EFGH is inserted into the tree, one edge at a time. The result looks like this: A B +-------------+ | | | | | E |J F | +-----+-------+ | | | | | | | | | | | | +-------+-----+ | D |L :C | | : | | : | +-----+-------+ H K G AB -/ \+ / \ / BC -/ \+ / \ / \ CD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ / \ \ EJ KH \ -/ \+ -/ \+ \ / \ / \ \ / / \ LE HL JF -/ \+ -/ \+ -/ \+ / \ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ Notice that when we insert EFGH, we split edges EF and HE along the edges of ABCD. this has the effect of dividing these segments into pieces which are inside ABCD, and outside ABCD. Segments EJ and LE will not be part of the boundary of the union. We could have saved our selves some work by not inserting them into the tree at all. For a union operation, you can always throw away segments that land in inside nodes. You must be careful about this though. What I mean is that any segments which land in inside nodes of the pre-existing tree, not the tree as it is being constructed. EJ and LE landed in an inside node of the tree for polygon ABCD, and so can be discarded. Our tree now looks like this:
. A B +-------------+ | | | | | |J F | +-------+ | | | | | | | | | +-------+-----+ | D |L :C | | : | | : | +-----+-------+ H K G AB -/ \+ / \ / BC -/ \+ / \ / \ CD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ \ \ KH \ -/ \+ \ / \ \ / \ HL JF -/ \+ -/ \+ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ Now, we would like some way to eliminate the segments JC and CL, so that we will be left with the boundary segments of the union. Examine the segment BC in the tree. What we would like to do is split BC with the hyperplane JF. Conveniently, we can do this by pushing the BC segment through the node for JF. The resulting segments can be classified with the rest of the JF subtree. Notice that the segment BJ lands in an out node, and that JC lands in an in node. Remembering that we can discard interior nodes, we can eliminate JC. The segment BJ replaces BC in the original tree. This process is repeated for segment CD, yielding the segments CL and LD. CL is discarded as landing in an interior node, and LD replaces CD in the original tree. The result looks like this: . A B +-------------+ | | | | | |J F | +-------+ | | | | | L | +-------+ | D | | | | | | +-----+-------+ H K G AB -/ \+ / \ / BJ -/ \+ / \ / \ LD \ -/ \+ \ / \ \ / \ \ DA \ \ -/ \+ \ \ / \ \ \ \ \ KH \ -/ \+ \ / \ \ / \ HL JF -/ \+ -/ \+ / \ / \ FG -/ \+ / \ / GK -/ \+ / \ As you can see, the result is the union of the polygons ABCD and EFGH. To perform other boolean operations, the process is similar. For intersection, you discard segments which land in exterior nodes instead of internal ones. The difference operation is special. It requires that you invert the polytope before insertion. For simple objects, this can be achieved by scaling with a factor of -1. The insertion process is then conducted as an intersection operation, where segments landing in external nodes are discarded.
Tree merging
--
Last Update: 09/06/101 14:50:28
HOW DO YOU PERFORM COLLISION DETECTION WITH A BSP TREE? Overview
Detecting whether or not a point moving along a line intersects some object in space is essentially a ray tracing problem. Detecting whether or not two complex objects intersect is something of a tree merging problem.
Typically, motion is computed in a series of Euler steps. This just means that the motion is computed at discrete time intervals using some description of the speed of motion. For any given point P moving from point A with a velocity V, it's location can be computed at time T as P = A + (T V).
Consider the case where T = 1, and we are computing the motion in one second steps. To find out if the point P has collided with any part of the scene, we will first compute the endpoints of the motion for this time step. P1 = A + V, and P2 = A + (2 V). These two endpoints will be classified with respect to the BSP tree. If P1 is outside of all objects, and P2 is inside some object, then an intersection has clearly occurred. However, if P2 is also outside, we still have to check for a collision in between.
Two approaches are possible. The first is commonly used in applications like games, where speed is critical, and accuracy is not. This approach is to recursively divide the motion segment in half, and check the midpoint for containment by some object. Typically, it is good enough to say that an intersection occurred, and not be very accurate about where it occurred.
The second approach, which is more accurate, but also more time consuming, is to treat the motion segment as a ray, and intersect the ray with the BSP Tree. This also has the advantage that the motion resulting from the impact can be computed more accurately.
HOW DO YOU HANDLE DYNAMIC SCENES WITH A BSP TREE? Overview
So far the discussion of BSP tree structures has been limited to handling objects that don't move. However, because the hidden surface removal algorithm is so simple and efficient, it would be nice if it could be used with dynamic scenes too. Faster animation is the goal for many applications, most especially games.
The BSP tree hidden surface removal algorithm can easily be extended to allow for dynamic objects. For each frame, start with a BSP tree containing all the static objects in the scene, and reinsert the dynamic objects. While this is straightforward to implement, it can involve substantial computation.
If a dynamic object is separated from each static object by a plane, the dynamic object can be represented as a single point regardless of its complexity. This can dramatically reduce the computation per frame because only one node per dynamic object is inserted into the BSP tree. Compare that to one node for every polygon in the object, and the reason for the savings is obvious. During tree traversal, each point is expanded into the original object.
Implementation notes
Inserting a point into the BSP tree is very cheap, because there is only one front/back test at each node. Points are never split, which explains the requirement of separation by a plane. The dynamic object will always be drawn completely in front of the static objects behind it.
A dynamic object inserted into the tree as a point can become a child of either a static or dynamic node. If the parent is a static node, perform a front/back test and insert the new node appropriately. If it is a dynamic node, a different front/back test is necessary, because a point doesn't partition three dimesnional space. The correct front/back test is to simply compare distances to the eye. Once computed, this distance can be cached at the node until the frame is drawn.
An alternative when inserting a dynamic node is to construct a plane whose normal is the vector from the point to the eye. This plane is used in front/back tests just like the partition plane in a static node. The plane should be computed lazily and it is not necessary to normalize the vector.
Cleanup at the end of each frame is easy. A static node can never be a child of a dynamic node, since all dynamic nodes are inserted after the static tree is completed. This implies that all subtrees of dynamic nodes can be removed at the same time as the dynamic parent node.
Caveats
Recent discussion on comp.graphics.algorithms has demonstrated some weaknesses with this approach. In particular, an object modelled as a point may not be rendered in the correct order if the actual object spans a partitioning plane.
Advanced methods
Tree merging, "ghosts", real dynamic trees... MORE TO COME
HOW DO YOU COMPUTE SHADOWS WITH A BSP TREE? Overview
HOW DO YOU EXTRACT CONNECTIVITY INFORMATION FROM BSP TREES? Overview
HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING? Overview
BSP trees are useful for building an "exact cell decomposition". A cell is any region which is used as a node in a planning graph. An exact cell decomposition is one in which every cell is entirely occupied, or entirely empty. The alternative is an "approximate cell decomposition", in which cells may also be partially occupied. A regular grid on a complex scene is an example of an "approximate cell decomposition".
Example
Consider a game which uses randomly oriented blocks for obstacles in an enclosed arena. For purposes of path planning, we are interested in the decomposition of the ground plane. We can get this by building a BSP tree containing all of the blocks, and pass a polygon which represents the ground into the tree. The splitting routine should be modified to maintain connectivity information when splitting polygons. Using a technique similar to boolean modelling, we can reduce the tree to contain only those polygons which are the regions of the ground plane not contained inside any obstacles.
Now, a planning graph can be built, using some point inside of each polygon, and connecting to a point inside of each of its neighbors. Note that the selection of the point location has implications for the length of resulting paths. Planning begins by identifying the cell which contains the start point, and the cell which contains the end point. Then a standard A style search can be used on the planning graph to find the set of polygons that must be crossed to get to the end point from the start point.
Implementation Notes
A simple optimization can help yield a straight path where on is important. When planning through a given region, keep track of where you are coming from and where you are going to. By treating the edges of the region as portals, and allowing your entry and exit points to slide along the portals, you can insure a minimum length path through each node.
FIRST DRAFT
--
Last Update: 09/06/101 14:50:29
HOW ARE BSP TREES USED IN DOOM? Overview
--
Last Update: 09/06/101 14:50:29
HOW CAN YOU MAKE A BSP TREE MORE ROBUST? Overview
--
Last Update: 09/06/101 14:50:29
HOW EFFICIENT IS A BSP TREE? Space complexity
For the problem of hidden surface removal, consider a set of n parallel polygons, and the set of m partitioning planes, all of which are perpendicular to the polgyons. This has the effect of splitting every polygon with every partition. The number of polygons resulting from this partitioning scheme is n + (n m). If the partitioning planes are selected from the candidate polygon set (an autopartition), then m = n, and the expression reduces to n^2 + n. Thus the worst case spatial complexity of a BSP tree constructed using an autopartition is O(n^2).
It will be extremely difficult to construct a case which satisfies this formula. The "expected" case, repeatedly expressed by Naylor, is O(n).
Time complexity
The time complexity of rendering from a BSP built using an autopartition is the same as the spatial complexity, that is a worst case of O(n^2), and an "expected" case of O(n).
--
Last Update: 09/06/101 14:50:28
HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT? Bounding volumes
Bounding spheres are simple to implement, take only a single plane comparison, using the center of the sphere.
Optimal trees
Construction of an optimal tree is an NP-complete problem. The problem is one of splitting versus tree balancing. These are mutually exclusive requirements. You should choose your strategy for building a good tree based on how you intend to use the tree.
Minimizing splitting
An obvious problem with BSP trees is that polygons get split during the construction phase, which results in a larger number of polygons. Larger numbers of polygons translate into larger storage requirements and longer tree traversal times. This is undesirable in all applications of BSP trees, so some scheme for minimizing splitting will improve tree performance.
Bear in mind that minimization of splitting requires pre-existing knowledge about all of the polygons that will be inserted into the tree. This knowledge may not exist for interactive uses such as solid modelling.
Tree balancing
Tree balancing is important for uses which perform spatial classification of points, lines, and surfaces. This includes ray tracing and solid modelling. Tree balancing is important for these applications because the time complexity for classification is based on the depth of the tree. Unbalanced trees have deeper subtrees, and therefore have a worse worst case.
For the hidden surface problem, balancing doesn't significantly affect runtime. This is because the expected time complexity for tree traversal is linear on the number of polygons in the tree, rather than the depth of the tree.
Balancing vs. splitting
If balancing is an important concern for your application, it will be necessary to trade off some balance for reduced splitting. If you are choosing your hyperplanes from the polygon candidates, then one way to optimize these two factors is to randomly select a small number of candidates. These new candidates are tested against the full list for splitting and balancing efficiency. A linear combination of the two efficiencies is used to rank the candidates, and the best one is chosen.
Reference Counting
Other Optimizations
--
Last Update: 09/06/101 14:50:28
HOW CAN YOU AVOID RECURSION? Overview
A BSP tree resembles a standard binary tree structure in many ways. Using the tree for a painter's algorithm or for ray tracing is a "depth first" traversal of the tree structure. Depth first traversal is traditionally presented as a recursive operation, but can also be performed using an explicit stack.
Implementation Notes
Depth first traversal is a means of enumerating all of the leaves of a tree in sorted order. This is accomplished by visiting each child of each node in a recursive manner as follows:
void Enumerate (BSP_tree tree) { if (tree->front) Enumerate (tree->front); if (tree->back) Enumerate (tree->back); } To eliminate the recursion, you have to explicitly model the recursion using a stack. Using a stack of pointers to BSP_tree, you can perform the enumeration like this:
void Enumerate (BSP_tree tree) { Stack stack; while (tree) { if (tree->back) stack.Push (tree->back); if (tree->front) stack.Push (tree->front); tree = stack.Pop (); } } On some processors, using a stack will be faster than the recursive method. This is especially true if the recursive routine has a lot of local variables. However, the recursive approach is usually easier to understand and debug, as well as requiring less code.
--
Last Update: 09/06/101 14:50:28
WHAT IS THE HISTORY OF BSP TREES? Overview
Neophyte: How did the BSP-Tree come to be?
Sage: Long ago in a small village in Nepal, a minor godling gave a special nut to the priests at an out of the way temple. With the nut, was a prophecy: When a group of three gurus, two with red hair, and the other who was not what he seemed, came to the temple on pilgrimage, if the nut was given unto them, and they nurtured it together, it would produce a tree of great benefit to mankind. Many years later, ...
N: no! No! NO! The TRUE story.
S: OK.
Long ago (by computer industry standards) in a rapidly growing sunbelt city in Texas, a serendipitous convergence of unusual talents and personalities occurred. A brief burst of graphics wonderments appeared, and the convergence diverged under its own explosive production, leading to further graphics developments in several new locations. One of the wonderous paths followed ...
N: ...No! The facts!
S: Huh? Oh you want FACTS. Boring stuff?
Henry Fuchs started teaching at an essentially brand new campus, the University of Texas at Dallas, in January 1975. He returned to Utah to complete his PhD the following summer. He returned to Dallas and taught for the 1975-76, 1976-77 and 1977-78 academic years, before being lured away to UNC-Chapel Hill.
Zvi Kedem joined this faculty in the fall of 1975. He was (and still is I suppose) a "theory person," but a special theory person. He is good at applying theory to practical problems.
Bruce Naylor had a bachelors degree from the U of Texas (Austin - "the real one"), in philosophy if I r
So far the discussion of BSP tree structures has been limited to handling objects that don't move. However, because the hidden surface removal algorithm is so simple and efficient, it would be nice if it could be used with dynamic scenes too. Faster animation is the goal for many applications, most especially games.
The BSP tree hidden surface removal algorithm can easily be extended to allow for dynamic objects. For each frame, start with a BSP tree containing all the static objects in the scene, and reinsert the dynamic objects. While this is straightforward to implement, it can involve substantial computation.
If a dynamic object is separated from each static object by a plane, the dynamic object can be represented as a single point regardless of its complexity. This can dramatically reduce the computation per frame because only one node per dynamic object is inserted into the BSP tree. Compare that to one node for every polygon in the object, and the reason for the savings is obvious. During tree traversal, each point is expanded into the original object.
Implementation notes
Inserting a point into the BSP tree is very cheap, because there is only one front/back test at each node. Points are never split, which explains the requirement of separation by a plane. The dynamic object will always be drawn completely in front of the static objects behind it.
A dynamic object inserted into the tree as a point can become a child of either a static or dynamic node. If the parent is a static node, perform a front/back test and insert the new node appropriately. If it is a dynamic node, a different front/back test is necessary, because a point doesn't partition three dimesnional space. The correct front/back test is to simply compare distances to the eye. Once computed, this distance can be cached at the node until the frame is drawn.
An alternative when inserting a dynamic node is to construct a plane whose normal is the vector from the point to the eye. This plane is used in front/back tests just like the partition plane in a static node. The plane should be computed lazily and it is not necessary to normalize the vector.
Cleanup at the end of each frame is easy. A static node can never be a child of a dynamic node, since all dynamic nodes are inserted after the static tree is completed. This implies that all subtrees of dynamic nodes can be removed at the same time as the dynamic parent node.
Caveats
Recent discussion on comp.graphics.algorithms has demonstrated some weaknesses with this approach. In particular, an object modelled as a point may not be rendered in the correct order if the actual object spans a partitioning plane.
Advanced methods
Tree merging, "ghosts", real dynamic trees... MORE TO COME
HOW DO YOU COMPUTE SHADOWS WITH A BSP TREE? Overview
HOW DO YOU EXTRACT CONNECTIVITY INFORMATION FROM BSP TREES? Overview
HOW ARE BSP TREES USEFUL FOR ROBOT MOTION PLANNING? Overview
BSP trees are useful for building an "exact cell decomposition". A cell is any region which is used as a node in a planning graph. An exact cell decomposition is one in which every cell is entirely occupied, or entirely empty. The alternative is an "approximate cell decomposition", in which cells may also be partially occupied. A regular grid on a complex scene is an example of an "approximate cell decomposition".
Example
Consider a game which uses randomly oriented blocks for obstacles in an enclosed arena. For purposes of path planning, we are interested in the decomposition of the ground plane. We can get this by building a BSP tree containing all of the blocks, and pass a polygon which represents the ground into the tree. The splitting routine should be modified to maintain connectivity information when splitting polygons. Using a technique similar to boolean modelling, we can reduce the tree to contain only those polygons which are the regions of the ground plane not contained inside any obstacles.
Now, a planning graph can be built, using some point inside of each polygon, and connecting to a point inside of each of its neighbors. Note that the selection of the point location has implications for the length of resulting paths. Planning begins by identifying the cell which contains the start point, and the cell which contains the end point. Then a standard A style search can be used on the planning graph to find the set of polygons that must be crossed to get to the end point from the start point.
Implementation Notes
A simple optimization can help yield a straight path where on is important. When planning through a given region, keep track of where you are coming from and where you are going to. By treating the edges of the region as portals, and allowing your entry and exit points to slide along the portals, you can insure a minimum length path through each node.
FIRST DRAFT
--
Last Update: 09/06/101 14:50:29
HOW ARE BSP TREES USED IN DOOM? Overview
--
Last Update: 09/06/101 14:50:29
HOW CAN YOU MAKE A BSP TREE MORE ROBUST? Overview
--
Last Update: 09/06/101 14:50:29
HOW EFFICIENT IS A BSP TREE? Space complexity
For the problem of hidden surface removal, consider a set of n parallel polygons, and the set of m partitioning planes, all of which are perpendicular to the polgyons. This has the effect of splitting every polygon with every partition. The number of polygons resulting from this partitioning scheme is n + (n m). If the partitioning planes are selected from the candidate polygon set (an autopartition), then m = n, and the expression reduces to n^2 + n. Thus the worst case spatial complexity of a BSP tree constructed using an autopartition is O(n^2).
It will be extremely difficult to construct a case which satisfies this formula. The "expected" case, repeatedly expressed by Naylor, is O(n).
Time complexity
The time complexity of rendering from a BSP built using an autopartition is the same as the spatial complexity, that is a worst case of O(n^2), and an "expected" case of O(n).
--
Last Update: 09/06/101 14:50:28
HOW CAN YOU MAKE A BSP TREE MORE EFFICIENT? Bounding volumes
Bounding spheres are simple to implement, take only a single plane comparison, using the center of the sphere.
Optimal trees
Construction of an optimal tree is an NP-complete problem. The problem is one of splitting versus tree balancing. These are mutually exclusive requirements. You should choose your strategy for building a good tree based on how you intend to use the tree.
Minimizing splitting
An obvious problem with BSP trees is that polygons get split during the construction phase, which results in a larger number of polygons. Larger numbers of polygons translate into larger storage requirements and longer tree traversal times. This is undesirable in all applications of BSP trees, so some scheme for minimizing splitting will improve tree performance.
Bear in mind that minimization of splitting requires pre-existing knowledge about all of the polygons that will be inserted into the tree. This knowledge may not exist for interactive uses such as solid modelling.
Tree balancing
Tree balancing is important for uses which perform spatial classification of points, lines, and surfaces. This includes ray tracing and solid modelling. Tree balancing is important for these applications because the time complexity for classification is based on the depth of the tree. Unbalanced trees have deeper subtrees, and therefore have a worse worst case.
For the hidden surface problem, balancing doesn't significantly affect runtime. This is because the expected time complexity for tree traversal is linear on the number of polygons in the tree, rather than the depth of the tree.
Balancing vs. splitting
If balancing is an important concern for your application, it will be necessary to trade off some balance for reduced splitting. If you are choosing your hyperplanes from the polygon candidates, then one way to optimize these two factors is to randomly select a small number of candidates. These new candidates are tested against the full list for splitting and balancing efficiency. A linear combination of the two efficiencies is used to rank the candidates, and the best one is chosen.
Reference Counting
Other Optimizations
--
Last Update: 09/06/101 14:50:28
HOW CAN YOU AVOID RECURSION? Overview
A BSP tree resembles a standard binary tree structure in many ways. Using the tree for a painter's algorithm or for ray tracing is a "depth first" traversal of the tree structure. Depth first traversal is traditionally presented as a recursive operation, but can also be performed using an explicit stack.
Implementation Notes
Depth first traversal is a means of enumerating all of the leaves of a tree in sorted order. This is accomplished by visiting each child of each node in a recursive manner as follows:
void Enumerate (BSP_tree tree) { if (tree->front) Enumerate (tree->front); if (tree->back) Enumerate (tree->back); } To eliminate the recursion, you have to explicitly model the recursion using a stack. Using a stack of pointers to BSP_tree, you can perform the enumeration like this:
void Enumerate (BSP_tree tree) { Stack stack; while (tree) { if (tree->back) stack.Push (tree->back); if (tree->front) stack.Push (tree->front); tree = stack.Pop (); } } On some processors, using a stack will be faster than the recursive method. This is especially true if the recursive routine has a lot of local variables. However, the recursive approach is usually easier to understand and debug, as well as requiring less code.
--
Last Update: 09/06/101 14:50:28
WHAT IS THE HISTORY OF BSP TREES? Overview
Neophyte: How did the BSP-Tree come to be?
Sage: Long ago in a small village in Nepal, a minor godling gave a special nut to the priests at an out of the way temple. With the nut, was a prophecy: When a group of three gurus, two with red hair, and the other who was not what he seemed, came to the temple on pilgrimage, if the nut was given unto them, and they nurtured it together, it would produce a tree of great benefit to mankind. Many years later, ...
N: no! No! NO! The TRUE story.
S: OK.
Long ago (by computer industry standards) in a rapidly growing sunbelt city in Texas, a serendipitous convergence of unusual talents and personalities occurred. A brief burst of graphics wonderments appeared, and the convergence diverged under its own explosive production, leading to further graphics developments in several new locations. One of the wonderous paths followed ...
N: ...No! The facts!
S: Huh? Oh you want FACTS. Boring stuff?
Henry Fuchs started teaching at an essentially brand new campus, the University of Texas at Dallas, in January 1975. He returned to Utah to complete his PhD the following summer. He returned to Dallas and taught for the 1975-76, 1976-77 and 1977-78 academic years, before being lured away to UNC-Chapel Hill.
Zvi Kedem joined this faculty in the fall of 1975. He was (and still is I suppose) a "theory person," but a special theory person. He is good at applying theory to practical problems.
Bruce Naylor had a bachelors degree from the U of Texas (Austin - "the real one"), in philosophy if I r
Игровой движок. Программирование и внутреннее устройство (2021 год). Аноним 27/11/23 Пнд 20:48:56 #76 №918827
Ты зачем и откуда это скопипастил?
Прикольная книжка, только про саму графику там мало
Ну или как саму архитектуру рендерера построить, больше просто ознакомительный осмотр некоторых подсистем движка
>А сколько десятилетий на всё это понадобится?
1-2
По факту сейчас успешными людьми в интеллектуальных сферах становятся как раз к 30. Чтобы в 20 что-то пиздатое сделать, надо быть неибацца уникумом 1 на миллиард.
>Тем более что на всяких вакансиях по рендереру нередко стоит условие: делать то, что никто не делал и по чему нет статьи
Ты уверен что там такая формулировка? Мб есть научная статья, но нет реализации например? Это норм тема.
И для этого не обязательно знать абсолютно все имеющиеся технологии. В основном опыт нужен, ну и уметь думать, решать задачки.
Если полностью с нуля придумывать алгоритм, то это какой-то совсем R&D, для обычной практики в разработке игр такое не нужно.
>Ты уверен что там такая формулировка?
https://hh.ru/vacancy/84457918?from=employer&hhtmFrom=employer
Забыл добавить что практика даёт 99% результата и понимания, а чтение ничего не даёт хоть зачитайся. Иначе бы любой долбоёб после курсов или лекций мог написать что угодно.
На ютубе есть весьма наглядные серии по темам, причём они при своей наглядности ещё и глубже тему освещают чем любой типичный курс из школки/универа.
https://www.youtube.com/watch?v=WUvTyaaNkzM
>По факту сейчас успешными людьми в интеллектуальных сферах становятся как раз к 30
Таксссс...
Со скольки лет Торвальдс начал прогать? А Кармак? А Хуан (макака годота)? Чтобы стать успешными к 30 надо быть либо ими, либо мохнатым орангутанами Страуструпом и RMS.
Ты на требования смотри, а не на задачи. В требованиях не написано, что нужно быть йоба-выдумщиком каких-то новых технологий.
А задачи это просто задачи. Тебе скажут заниматься этим, ты будешь заниматься этим. Если ты как это интерпретировать, скорее всего у тебя нет тех самых 6+ лет опыта. Тебе скорее надо на джуна-мидла метить, на таких позициях тебе какой-то старший чел будет говорить "кодь вот это", и ты будешь кодить, дебажить, оптимизировать. Чисто роль рабочих рук с минимальной головой на плечах.
>Со скольки лет Торвальдс начал прогать? А Кармак?
Выбрал самых ебаных уникумов. Кармак вообще робот, хуячит в 2 раза больше обычных людей. Плюс они попали на то время, где можно было выехать за счет комбинации относительно простых идей, а в дальнейшем накручивать и накручивать.
Хуан не ебу что пиздатого сделал.
придумайте мне алгоритм для маски двустороннего сферического объекта
нужно при приближении камеры скрывать переднюю сторону и проявлять заднюю в этом окошке
пикрил иллюстрация
вроде всё просто, но 3 дня уже ебусь
уже и в блендере сферки двигал пытался придумать математику, но обосрался
нужно при приближении камеры скрывать переднюю сторону и проявлять заднюю в этом окошке
пикрил иллюстрация
вроде всё просто, но 3 дня уже ебусь
уже и в блендере сферки двигал пытался придумать математику, но обосрался
Так у тебя и так есть плоскость рендера, когда у тебя полигоны заходят за эту плоскость, их не видно, ты будешь видеть внутренние полигоны сферы.
Вопрос в масштабах всей этой херни, чтобы плоскость соотносилась с размерами сферы, чтобы можно было поймать такой момент, когда часть наружных полигонов еще видно, и при этом ты видишь пятно внутренних полигонов.
А нужно именно чтобы сфера камеры вошла в другую сферу (то есть при определённом расстоянии от камеры до сферы камера видела часть внутренностей этой сферы) ?
Если да:
то находим расстояние между сферами формулой
> abs(length(Ic (положение камеры) -- Sc (центр сферы))) -- Ir (радиус сферы камеры) -- Sr (радиус сферы).
Подчёркнутые переменные -- векторы. Другие -- скаляры.
Если эта функция вернёт 0, то значит\. что сферы гипотетически соприкасаются (ибо точность вычислений не бесконечна) в одной точке. Если она вернёт отрицательное значение -- одна сфера погружена в другую на это значение.
Это делаешь в фрагментном шейдере.
И так ты либо сразу во фрагментном/пиксельном шейдере откидываешь фрагмент (ключевым словом discard в GLSL), либо играешься с трафаретом, куллингом и z-тестом (но может потребоваться отдельный фреймбуфер).
спасибо за ответы
я это пытаюсь сделать в пиксельном шейдере в UE, в транспаренси пассе, на полупрозрачном двустороннем материале. т.е. обе стороны сферы рендерятся
дырку спереди замаскировать довольно легко: если дистанция до пикселя меньше радиуса глаза, значит пиксель не видно
а вот как проявить зад на величину этой "проруби" - я никак понять не могу
задача сделать так, чтобы перед и зад не пересекались. но в идеале мне нужен плавный переход
>если дистанция до пикселя меньше радиуса глаза, значит пиксель не видно
>а вот как проявить зад на величину этой "проруби" - я никак понять не могу
Что значит проявить? Если ты отбрасываешь передние пиксели, значит задние автоматом должно быть видно, не?
Или ты хочешь блендить перед и зад при приближении, типа чем ближе, тем яснее зад видно, а перед растворяется?
>значит задние автоматом должно быть видно, не?
да, но мне всё равно нужно посчитать эту маску, потому что мне нужен комплемент этой видности, чтобы скрыть остальную изнанку
>ты хочешь блендить перед и зад при приближении, типа чем ближе, тем яснее зад видно, а перед растворяется
именно это я и хочу
Ну т.е. тебе нужна самая ближняя точка по выпуклости к камере, и расстояние от этой точки до конкретного пикселя, это расстояние будет говорить насколько прозрачным должен быть пиксель.
Ближнюю точку можно вычислить как вектор Ic-Sc помноженный на радиус Sr. Ну и соответственно берешь расстояние между ней и текущим пикселем.
Ну и полученное расстояние нужно нормализовать, т.е. найти расстояние от центра дырки до ее окружности (ее радиус по сути), и расстояние разделить на этот радиус. Точки окружности можно получить, если приравнять уравнение этих двух сфер. Или мб проще будет, если в 2д проекции рассмотреть, оттуда вывести радиус дырки, и потом упрощенную формулу юзать.
С радиусом дырки все-таки не совсем правильно будет.
Надо короче именно точку на окружности дырки найти, и взять расстояние от той самой ближайшей точки к краю дырки. Тогда получится нормализовать более корректно.
Сорян, я криво выразился, короче такая формула должна быть
center_point = Sc + norm(Ic - Sc) x Sr
потом
alpha = length(pixel_point - center_point) / length(Ho - center_point)
вместо Hc надо именно точку на поверхности брать (center_point), иначе расстояние от пикселя до центра будет больше, чем Ho-Hc, нормализация неправильная будет.
Ну и это формула для внешних пикселей, которые должны быть полупрозрачными.
Сап рендерерач.
С 30-летием DooM
С 30-летием DooM
лоооооол
аватар джона кармака?
Его вроде хуесосили за консервативность 1-3 года назад, кажется из-за высказывания своего мнения о детях на выставке sci-fi книг.
С 30-летием двиглостроения!!!111
https://youtu.be/QvAkaJsvAXs?si=YqY6eyIzfAtdO63S
>консервативность 1-3 года назад
18 мая 2023
Лучше бы по теме умничал
Есть кто разбирается в современном вулкане? ну и бамп заодно
А есть несовременный? Он же молодой ещё...
Разумеется.
Современный значит 1.3+ спецификация и расширения - т очто развивается.
А то что ниже, это легаси по сути.
Многие большинсво пишут под 1.0 вообще, для совместимости с со старым железом, на пример.
Я не говорю что это плохо или не нужно, но у меня вопрос именно по современным фичам, со старыми и так все понятно.
А чем 1.0 не хватает?
Как тебе сказать...
Все что мне нужно реальзовать, уже сделано и работает. На устаревших, либо совсем старых технологиях, даже если в рамках вулкана.
Если совсем грубо, то пиксельные тени завезли в директикс 8вроде, так что все можно и на нем сидеть и не дергаться.
Это не вопрос как сделать. Это вопрос как сделать лучше.
Вот есть прикрепляемые ресурсы, старая тема. Есть биндлесс ресурсы через дескриптор индексинг, оносительно современная фича, дает безразмерные массивы сэмплеров, это то что реализовано у меня.
Но это все равно дискрипторы, от которых, в идеале, лучше бьы вообще уйти. В чистых буферах уже ушли - все по адресу, а вот с сэмплерами так не работает.
И тут я открываю спецификацию, смотрю подвезли расширение - дескриптор буфер.
Я его опробовал, на базовом уровне работает, но не могу разобратсья как заюиндить весь такой буффер разом, без оффетов, чтоб шейдер воспринимал его как безразмерный массив и можно ли.
Мне бы, лазлаботчику опенг-убийцы уринала, такие проблемы.
Где ты работаешь? Давно ли?
> Vulkan 1.3 now has dynamic rendering
Так бля, объясните новенькому, RenderPass и FrameBuffer больше не нужны?
Так бля, объясните новенькому, RenderPass и FrameBuffer больше не нужны?
Для пк да, не нужны, и уже пару лет как. Для мобилок нужны.
Король королей, повелитель времён
Из чаши Грааля глядит на меня,
Сиянием Чёрной Луны озарён
Учитель Закона в Короне Огня...
Из чаши Грааля глядит на меня,
Сиянием Чёрной Луны озарён
Учитель Закона в Короне Огня...
Мне вулкан давал только VK_ERROR_DEVICE_LOST
Какой ГП юзаешь, бро?
На больное давишь, анон, gtx 1060 6gb у меня
что думаете про webgpu? проще opengl 4, мультиплатформа, в теории можно даже сделать backend'ы для приставок.
WebGPU он для браузерного JS, вместо устаревшего WebGL, как аналог Metal, Vulkan & D3D 12.
>проще opengl 4
Вкат в 3д стоит начинать с opengl 3.3+ (это opengl 4 под устаревшее железо) или с opengl es 3.1 (его аналог под, преимущественно, мобилки).
>backend'ы для приставок.
На иксбокс вроде только directx работает, про Sony не знаю.
webgpu это новое графическое api для веба, но особенность в том, что оно изначально разрабатывается как некий стандарт с webgpu.h заголовком со всеми функциями, для которого можно сделать свою реализацию API, в том числе для нативных платформ. сейчас есть 2 реализации: dawn от гугла и wgpu native разрабатываемый для firefox. например, движок bevy использует wgpu.
то есть webgpu это такая обертка поверх существующих api. в этом смысле webgpu похоже на библиотеку bgfx. она тоже реализует абстракцию графического api поверх существующих, но преимущество webgpu в том, что это api с более современным дизайном (говорят, похоже на metal от apple), оно стандартизовано, есть отличная документация и его поддерживают крупные компании.
я делал обертку для wgpu native на c#
Ух ты, а я и не знал.
Но начни с opengl, туториалы у него отличные. Они тут >>2981068 https://2ch.hk/pr/res/2938659.html#2981068
я с них и начинал. только учить opengl сейчас - это трата времени. лучше бы начинать учить сейчас именно с webgpu, он даже проще и интуитивнее opengl. это как vulkan для чайников, он учит современным концепциям графических api, а не устаревшим, как opengl 3. можно прямо в браузере, а можно нативно на c/c++ или с биндингами для другого языка.
просто я недавно ковырялся с wgpu, думал может тут кто-то тоже ковырялся с ним.
забудьте: должна была быть кидзоня.
Возможно ли, используя wgpu computing shaders, написать движок физики? Насколько это лучше, чем вычисления на cpu? Кто-нибудь пробовал на gpu вообще физ движки писать?
И webgpu еще является более high-level api, и в качестве бэкендов использует те же самые vulkan, opengl, metal, webgl, так что это не замена чему-то из них. Действительно лучше его сразу изучать, как говорит анон , потому что если начинаешь делать на том же vulkan, то неизбежно переизобретаешь вариацию webgpu, только хуже (потому что это собственный велосипед).
Не по сабжу треда, но проблемка именно в гле, а не просто движках. Как вы реализуете gui? В плане, интересно почитать соответсвующую литературу. Например, как отработать клики. Вот я листаю форумы, спрашиваю у гопоты, везде тривиальные решения просто проверять каждый гуи объект с точкой нажатия курсора. И чисто случайно узнал про дерево квадрантов, которое как раз правильно решает эту проблему.
Так же хотелось бы литературы по самому геймдеву. Не понимаю, как работают игры. Я вроде бы свои решения делаю, но всегда не уверен, правильно и оптимально ли.
Так же хотелось бы литературы по самому геймдеву. Не понимаю, как работают игры. Я вроде бы свои решения делаю, но всегда не уверен, правильно и оптимально ли.
Я понимаю что для новичка это сложно возможно будет, но можешь глянуть как imgui устроен
> Не понимаю, как работают игры.
Слишком абстрактный вопрос, конкретизируй хоть немного
Как работает графика? Как работает физика в играх? Как работает сетевая составляющая? Как работает анимации? Как работает искусственный интеллект у неигровых персонажей?
> Слишком абстрактный вопрос, конкретизируй хоть немного
Да, не правильно сказал. Интересует тема, как строится архитектура в играх. Всякие алгоритмы и паттерны в них. Видел книгу по паттернам, но общей картины, как построить игру нету. Точнее, есть то, что я сам надумал в процессе практики.
> Как работает графика? Как работает физика в играх? Как работает сетевая составляющая? Как работает анимации? Как работает искусственный интеллект у неигровых персонажей?
Вот эти темы вполне понятны.
Почему ты решил, что дерево квадрантов - правильное решение?
Это преждевременная оптимизация. Затраты времени на отладку и тесты алгоритма (который с твоими вопросами очевидно без ошибок ты с первого раза не напишешь).Ты наверняка не делал бенчмарков, чтобы узнать, сколько времени занимает обработка кнопки проходом по списку.
У тебя в игре на экране одновременно не 1000, не 100, и скорее всего даже не 10 кнопок, чтобы с этим запариваться. А если кнопок много, то, скорее всего, это не реалтайм ситуация, а какая-то менюшка настроек.
Мне друг подсказал и мне показалось это правильным.
Обычное дерево. У каждой ноды свой AABB. Сначала ищешь пересечение с AABB самой верхней ноды, если пересечение есть - ищешь пересечение со всеми дочерними нодами. И так пока не спустишься к ноде без дочерних элементов, это и будет искомый объект. Сложность логарифмическая.
бамп
Physx для чего-то вроде этого и предназначен.
Вот чувак даже делал 2д игрулю с физоном на гпу https://habr.com/ru/articles/320142/
https://store.steampowered.com/app/593530/Jelly_in_the_sky/
Преимущества гпу - можно делать дохера (типа 100х относительно проца) сравнительно простых операций параллельно. Минусы - взаимодействия между потоками затруднительно, мало памяти, мало гибкости, плюс передача данных между гпу и цпу прилично времени отжирает. Но при определенных кувырках и ужимках можно запихнуть все, чтобы реалтайм пахало.
Jason Gregory Game Engine Architecture хвалят вроде как. Но там всё обо всем, в основном по вершкам темы обходят, иногда углубляясь.
Чисто по паттернам, но особо без архитектуры - Robert Nystrom Game Programming Patterns. Довольно простая и небольшая книжка по существу.
Но все это бессмысленно, и ты не построишь общей картины, если не начнешь с чего-то простого, с теми знаниями, которые имеешь. Сначала сделай какую-нибудь хуйню, потом пойми какие у тебя проблемы возникают. Потом можешь начинать курить серьезные книги, только тогда ты их поймешь.
Ну и на хабре, или еще где-то, можешь поглядеть литературу по геймдеву. Из недавнего вот попалось https://habr.com/ru/articles/792996/ https://habr.com/ru/articles/794102/
Грегори у меня на полке лежит. Где-то половину прочитал, дошел до графики. Книга действительно касается только верхов, не совсем подходит для моих целей. У Нистрома пару глав прочитал и отложил на будущее, довольно интересная книга, но, опять же, не касается самого процесса разработки. Ну и отвечая на собственный вопрос, думаю посмотреть серию роликов по созданию майнкрафта на ютубе, заодно и вспомню опенгл.
> Но все это бессмысленно, и ты не построишь общей картины, если не начнешь с чего-то простого, с теми знаниями, которые имеешь. Сначала сделай какую-нибудь хуйню, потом пойми какие у тебя проблемы возникают. Потом можешь начинать курить серьезные книги, только тогда ты их поймешь.
Да вот я уже пару проектиков поделал и понял, что мне не хватает именно общей картины, как работают игры. Да и порой кажется, что то что я делаю, я делаю не правильно. Тот же гуй пару раз писал и все время спотыкаюсь о то, что новая фича не подходит к устроенной архитектуре. В итоге начинают появлятся костыли и интерес к проекту гаснет.
Ну в игре про танчики вроде как дофига частиц, все состоит из них, и это реально много памяти отжирает как при вокселях. А если делать не весь мир разрушаемым на физ частицах как в нойта, норм может выйти?
> Тот же гуй пару раз писал и все время спотыкаюсь о то, что новая фича не подходит к устроенной архитектуре. В итоге начинают появлятся костыли
В основном это вопрос проектирования и рефакторинга.
Сначала ты проектируешь - прикидываешь какие фичи тебе нужны будут, где надо гибче, где можно проще и монолитно, загодя предполагаешь что где-то костылить придется - там придумываешь более умное решение. И тут в целом разве что паттерны программирования нужно знать. Дальше все за тобой остается, насколько креативно ты их применишь. Какие-то хитрые решения можешь подсматривать в разборах или исходниках других игр/движков.
Я не уверен, что есть какая-то прям книга по выстраиванию "правильной" архитектуры. Тут все очень индивидуально, и состоит разве что из локальных принятий решения как запилить ту или иную штуку.
Как я понял, все упирается в личный опыт? И не стоит будоражить свой перфекционизм, если кажется, что решение не правильное, при этом правильное решение не приходит в голову.
Скорее всего можно.
Ноита на цпу вроде как работает. Учитывай, что там все пиксельное и по пиксельной сетке выровнено. Это упрощает многие моменты. Например поиск коллизий вообще изичный.
А какие способы оптимизации есть для узкого места cpu->gpu->cpu?
>Как я понял, все упирается в личный опыт? И не стоит будоражить свой перфекционизм
Абсолютно. Это извечный камень преткновения, и надо учиться брать перфекционизм в узду. Вопрос того, что ты хочешь достичь, какие критерии успеха у тебя. Хочешь ты дрочить абстрактные движки до бесконечности, или хочешь выпустить продукт.
Когда инженер решает инженерную задачу, у него нет бесконечного числа времени и ресурсов на поиск "идеального" решения. Решение должно соответствовать каким-то реалистичным и разумным рамкам по разработке, а также самим целям проекта. И перво-наперво, оно должно работать. Неоптимально, некрасиво, неудобно - это вторично.
Инженерство - это всегда про поиск компромиссов. Какой-нибудь алгоритм может считать задачу неделю, в таком случае и оптимизация до 1 часа уже круто. Можно было бы какими-то способами добиться вычислений за 1 минуту - но на это уже надо вбухать кучу ресурсов. А есть ли они? А стоит ли оно того? А может даже до 1 часа не надо оптимизировать, а потратить силы на что-то более важное?
Всегда можно сделать "идеальнее", но не всегда нужно так делать.
И вот в программировании ПО ты не всегда можешь предугадать все варианты использования. Лучше опираться на текущие известные требования, и чуть-чуть думать наперед.
Уменьшать размер передаваемых данных, уменьшать число передач данных.
Как именно это делать - зависит уже от задачи. Для начала надо понять на чем именно затык есть.
Как уменьшать-то, если я хочу, скажем, 50К+ объектов обсчитывать? Понятно там алгоритмы разные есть для того, как именно коллизии обрабатывать уже внутри, но данных на вход/выход меньше не становится. Число передач данных тоже не изменится особо, один раз отправляешь и один раз получаешь, и так каждый фрейм.
Если у тебя есть время для того чтобы подумать - конечно стоит подумать. Особенно если решение которое ты пишешь это движок или рендер, зависимое к качеству кода. Правильные решения приходят довольно быстро, буквально несколько итераций и ты получаешь топовый код.
Забивать хуй можно уже на какие-то скрипты и игровую логику, их исправить всегда можно, на производительность они влияют меньше всего.
> Неоптимально, некрасиво, неудобно - это вторично.
Это если у тебя задача хуякс-хуякс и в продакшн. Результат конечно же будет соответствующий - нахуй никому не нужный очередной кал.
Ты задумал создать кал - ты получил никому нахуй не нужный кал. Хуй даже знает зачем такой кал создавать. Чтобы никто его не трогал?
Чекни, шо такое мегатекстуратм или виртуальная текстура.
Олсо https://cpp-rendering.io/opengl-azdo-bindless-textures/
Так себе, какие то пластиковые игрушки.
Аноны, вы же видели фотореалистичный нанорендерер, использующий 3д-гауссианы и позволяющий строить сцены, основываясь только на фотографиях?
https://github.com/graphdeco-inria/gaussian-splatting
https://github.com/graphdeco-inria/gaussian-splatting
Вроде как он небыстный, неточный, и нестабильный в движении.
В целом похоже на поинтклауды которыми давно весь скетфаб забит.
А, и там исследовательская лицензия, то есть конкретно этот код для некоммерческого. Хотя, может независимую реализацию можно сделать.
Еще, где-то читал, что там сложно сделать прозрачные материалы.
Светлейшие умы, а что с работой делать?
Без опыта сейчас чтоли совсем никуда?
Куда в спб податься можно 4-курснику?
Я хз, в доставку можешь попробовать
Т.Т
бамп
Нейродрисня? Не интересует.
Возможно ли научиться программировать комп. графику сразу на Vulkan?
Конечно возможно, будет тяжело
А есть примеры челов, которые успешно изучали графику на вулкане?
Есть.
C нуля
Ну ты же просто ленивый долбаёб, и даже если я тебе сотню примеров приведу, ты всё равно его учить не начнёшь по какой-то надуманной причине.
Иди открывай вулкан туториал прямо сейчас, и учи. Если поймёшь, что всё хуево и ты вообще нихуя не понимаешь, учи опенгл сначала, и потом перекатывайся на вулкан, если захочешь.
Добрался до собесов, что могу
Поясните за шейдеры, что это такое. Кроме графического программирования, нужно еще изучать программирования шейдеров?
> Поясните за шейдеры, что это такое
Маленькие программы, выполняющиеся на видеокарте.
> Кроме графического программирования, нужно еще изучать программирования шейдеров?
Что такое графическое программирование?
шейдер вычисляет цвет пикселя. вычислив все пиксели получишь финальное изображение
Vulkan API.
Они не только цвета выщитывают.
>нужно еще изучать программирования шейдеров
там изучать особо нечего, если ты не хочешь творчеством заниматься и всякие приколы в shadertoy пилить
Там целые языки свои есть, которые по функционалу друг от друга еще отличаются.
>если ты не хочешь творчеством заниматься
Разве сделать свою игру это не творчество или что ты имеешь ввиду?
> Там целые языки свои есть
и все почти что сишка, разобраться достаточно быстро
> что ты имеешь ввиду
Ну зайди на shadertoy и посмотри что я под творчеством в шейдерах имею ввиду
прикольные демосценки которые на 99% не используются в играх
Да.
Да?
Я тупой. В чем разница между вулкан и опенгл. Я знаю, что второе проприетарное, а первое опенсурс. Я имею ввиду какие моменты при работе с инструментом
Еще нубский вопрос. Я пытался вкатится в опенгл или как там это, но почему чтобы мне не приходилось делать, то нужно качать библиотеку
вылкан это следующая итерация опенгл, современная. и то и то опенсорс, кроносгруп
Вулкан более низкоуровневый и близкий к железу.
К чему быть готовым на собесе на Джуна?
Особенно интересно что по части математики могут спросить
>по части математики
Наверно то, что изучают в ВУЗе.
Или вектора, матрицы др., что нужно для писанины шейдеров и создания всяких крутых штук.
База 3д короче.
Теперь это тред программирования компьютерной графики.
Темы OpenGL/DirectX/Vulkan, 3D математика, алгоритмы компьютерной графики, программирование шейдеров и все прочее.
Постим свои потуги в рисовании треугольников, задаем ответы, получаем вопросы.
Шапка старого треда https://gist.github.com/2ch-gd-opengl/26b94fc6f16100af730d84a3d8bbd557
Предыдущий OpenGL тред 7 https://2ch.hk/gd/res/678945.htm