>Предыдущий 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д короче.
Как из коммандной строки что бы можно было через system в рантайме при инициализировать проверить поддержку resizable bar?
Нагуглил как то для нвидии на линуксе, работает. Как на винде сделать?
Нагуглил как то для нвидии на линуксе, работает. Как на винде сделать?
Привет, Сосач. Хочу пользоваться Ogre3D, но тут возникла дилемма: в Ogre 1.14 нет глобального освещения, а в Ogre-Next нет occlusion culling, но есть depth prepass. Хочу запилить коридорный шутер, но совершенно не уверен, что в случае Ogre 2.21 ничего не будет тормозить. Если среди нас есть спецы по конвейеру рендеринга, подскажите, поможет ли Depth Prepass убрать из кадра ненужную геометрию в той же степени, что и occlusion culling?
> occlusion culling
Так оно же прямо в видеокарте сделано.
Ой дурак.
зачем ты срешь в тематике не имея ни малецшего представления
Откуда текстура знает как её данные считываются и записываются?
Т.е. в шейдере чтение из текстуры, например, возвращает float4, но ведь декодирование R32G32B32A32_FLOAT, R11G11B10_FLOAT и R8G8B8A8_UNORM явно требует разного кода. Так вот, как это работает?
Моё предположение: дескриптор текстуры в шейдере содержит указатель на код (ну или сам код), который вызывается для чтения/записи значений.
Может есть какая-нибудь статья, глава книги и т.д., в которой подобные моменты расписаны (желательно о реальном железе), то ткните меня пожалуйста в них.
Т.е. в шейдере чтение из текстуры, например, возвращает float4, но ведь декодирование R32G32B32A32_FLOAT, R11G11B10_FLOAT и R8G8B8A8_UNORM явно требует разного кода. Так вот, как это работает?
Моё предположение: дескриптор текстуры в шейдере содержит указатель на код (ну или сам код), который вызывается для чтения/записи значений.
Может есть какая-нибудь статья, глава книги и т.д., в которой подобные моменты расписаны (желательно о реальном железе), то ткните меня пожалуйста в них.
На каком языке ты пишешь шейдеры? Шейдерные языки - языки высокого уровня, так что там может автоматически вставляться дополнительный код.
>На каком языке ты пишешь шейдеры?
Это хобби, но в основном OpenGL GLSL. Слежу за VK и D3D12 (и за GLSL и HLSL), так что в курсе про VK_EXT_descriptor_indexing, VK_EXT_descriptor_buffer, ResourceDescriptorHeap/SamplerDescriptorHeap, но абсолютно не знаком с тем, что делает драйвер/гпу.
>Шейдерные языки - языки высокого уровня, так что там может автоматически вставляться дополнительный код.
Но как он может вставляться при descriptor indexing, ведь формат текстуры заранее неизвестен? К тому же если учесть component swizzle (VkComponentSwizzle), subresource view и format reinterpret? Там что какой-то убер метод на все случаи, который всё это учитывает? Он же будет неадекватно ОГРОМНЫЙ и медленный, не? Неужели там какие-то убер инструкции гпу, которые по набору "настроек" загруженных из дескриптора могут это всё делать?
Чел ты говоришь что что то там знаешь , так вот мог бы знать что формат заранее известен. Формат указывается при создании изображения на хосте. А так же может быть явно указан в шейдере на девайсе.
>Чел ты говоришь что что то там знаешь , так вот мог бы знать что формат заранее известен. Формат указывается при создании изображения на хосте. А так же может быть явно указан в шейдере на девайсе.
Но шейдер же не знает формат. Всё что он может знать это тип возвращаемого значения (указание формата в шейдере мы не учитываем, потому что в том же HLSL для D3D неуказывается даже для UAV'шек), а float4 может быть: R32_FLOAT, R16_FLOAT, R11G11B10_FLOAT, BC1-BC7, и все они требуют явно разного кода для декодирования.
Я упомянул descriptor indexing, потому что там даже предположить нельзя, какие форматы могут быть у текстур, которые будут сэмплиться в шейдере (т.е. заранее код для нужных форматов не вставишь перед запуском шейдера).
Может я недооцениваю современные гпу и там реально один опкод (и соответствующий супер специализированный блок), который декодирует все возможные (поддерживаемые) форматы. Но если это так, насколько это медленно?
Честно скажу, что я в этом вообще не разбираюсь, но большие дяди уже всё продумали и разработали, нет необходимости копаться в машинных кодах GPU и изучать архитектуру её процессора. Просто бери и используй как сказано в документации...
А разве что-то кроме RGBA_8888 сегодня вообще используется? У мониторов редко бывает честная поддержка 24-битного цвета, чаще 18 бит. Зачем использовать аж 32 бита на канал в шейдерах?
Т.е. зачем тратить память впустую?
Смысл есть. Это во всю используется там где нужно. Разумеется представление будет в р8г8б8 или что там твой монитор считает оптимальным и портебует дополнительных пересчетов
Ты похоже просто нахватался инфы кашеобразной. Посмотри шейдеры нормальных проектов, как ответил челу выше - преобразование форматов требует действий. На пример у кого то двигло на компе с чистым хдр, у кого то пожатым псевдо, а у кого то 8 бит. Вот в шейдере перебирают кейсом. и твоя формулировка что формат не известен звучит как бред
Апд ну или пересборка шецдеров в рантайме на целеевой машине с специлизацонными константами.
Есть вопрос по Assimp и glm.
Итак, при загрузке модели он возвращает mesh, который содержит mBones, а они в свою очередь имеют матрицу (со свой особой структурой aiMatrix4x4) mOffsetMatrix. Эту матрицу можно инвертировать и превращать потом в glm::mat4, с этим проблем нет.
Но как я понимаю эта матрица содержит координаты кости, но локальные, потому что только первая кость корректна, все остальные - уже идут с каким-то смещением.
Собственно вопрос - как mOffsetMatrix у нужной кости преобразовать так, что бы получить vec3 с глобальными координатами этой самой кости? Что-то на выходе вроде glm::vec3 (0.0 0.2, 1.2) - где эти xyz - уже глобальные координаты кости в сцене. Гугление ничего внятного к сожалению не принесло.
Очень надеюсь на вас.
Итак, при загрузке модели он возвращает mesh, который содержит mBones, а они в свою очередь имеют матрицу (со свой особой структурой aiMatrix4x4) mOffsetMatrix. Эту матрицу можно инвертировать и превращать потом в glm::mat4, с этим проблем нет.
Но как я понимаю эта матрица содержит координаты кости, но локальные, потому что только первая кость корректна, все остальные - уже идут с каким-то смещением.
Собственно вопрос - как mOffsetMatrix у нужной кости преобразовать так, что бы получить vec3 с глобальными координатами этой самой кости? Что-то на выходе вроде glm::vec3 (0.0 0.2, 1.2) - где эти xyz - уже глобальные координаты кости в сцене. Гугление ничего внятного к сожалению не принесло.
Очень надеюсь на вас.
матрица содержить соазу координаты, скейл и поворот. и каждая матрица локальная по отношению к паренту. поэтому если тебе нужны глобальные координаты надо каждую множить на матрицы по цепочке парентов. там главное порядок правильный вьебать (кажись от рута вниз). а дальше из глоб. матрицы уже и позицию и поворот вытаскиваешь
Спасибо, тоже думал что нужно будет идти по скелетному дереву до нужной кости, но все оказалось проще.
Суть задачи - нужно было в определенную кость вставлять другой меш, например оружие в кость руки, в движках это часто сделано через костыль в виде слота, который на самом деле, как я понимаю, тоже кость.
Поэтому для Т позы можно так:
aiMatrix4x4 boneAiM = pBone->aiMatrix;
boneAiM.Inverse();
glm::mat4 boneGlmM = ConvertToGlm(boneAiM);
Где в boneGlmM[3]xyz - будут глобальные позиции кости.
И сам конвертер:
inline glm::mat4 ConvertToGlm(aiMatrix4x4 aMatrix)
{
glm::mat4 gMatrix;
for (int y = 0; y < 4; y++)
for (int x = 0; x < 4; x++)
gMatrix[x][y] = aMatrix[y][x];
return gMatrix;
}
Может кому-то пригодится. Экспорт делал в Бледере.
что такое семплировать?
вычислять значения в определенных точках/координатах
То есть просчитывать?
То есть получить значение, расположенное в данных координатах.
Например: семплировать текстуру -- из каждого её пикселя (координаты x, y) достать цвет этого пикселя (например, красных).
А как обычно реализована отрисовка одним дро-коллом нескольких моделей? Для упрощения - без текстур и материалов.
На ум приходит объединение мешей моделей, и через юниформы передавать матрицы моделей, их индексы, соответствующие диапазону вертексов.
Так?
На ум приходит объединение мешей моделей, и через юниформы передавать матрицы моделей, их индексы, соответствующие диапазону вертексов.
Так?
В общих чертах. Но не обязательно юниформы.
Гитхаб зеукс ниагара - отличная базовый реализация такого подхода.
Сап, аноны. Часто во всяких демках графики вижу эту сцену. Кто может дать название? Что это?
Sponza
Спасибо, анон
в 2гис можно. там в 3д карту разраб нужен.
сколько в треде годноты...
я дома.
я дома.
Кленовый листик или травинку как реализовывать? Растягивать текстуру по треугольным полигонам или через альфа-отсечение как-нибудь? Как? Их же туча должна быть. Просто сотни.
Только начинаю изучать OpenGL.
Вывожу куб по 8 цветным вершинам и 12 треугольным индексам. Пробрасываю цвет через varying. Почему видны затемнения между полигонами в диагоналях? Может есть какие опции/режимы экстраполяции пикселей? Свет не используется.
Вывожу куб по 8 цветным вершинам и 12 треугольным индексам. Пробрасываю цвет через varying. Почему видны затемнения между полигонами в диагоналях? Может есть какие опции/режимы экстраполяции пикселей? Свет не используется.
тут всё нормально. затемнение - потому что тут чистая математическая интерполяция, а перцептивная яркость цветов разная
>varying
ты очень старую версию opengl учишь, обнови методичку
Из серии, абсолютно точный и абсолютно бесполезный аутистско - программерский ответ.
Потому что интерполяция происходит между трёх точек внутри треугольника, а не по квадам между четырех точек. Поэтому видны границы треугольников
> Тред Графического Программирования
> программерский ответ
Сложный вопрос. Есть какие-то достаточно свежие биндинги для DirectX под C# Winforms?
тыжпрограммист на заводе
тыжпрограммист на заводе
Можете в шапку ещё добавить туториалы от ChiliTomatoNoodle. Мужик сделал туториалы с основ программирования до дх11. Естественно на плюсах. У него несколько плейлистов
Бегинер: переменные, условия, циклы, классы, массивы
Интермидиент: работа с памятью, указатели и больше ооп
Адвансед: рисования прямых на плоскости, матрицы, вращения
3дФундамнеталс: софтвеерный 3д движок
3дХардвеер: 3д движок на дх11
Бегинер: переменные, условия, циклы, классы, массивы
Интермидиент: работа с памятью, указатели и больше ооп
Адвансед: рисования прямых на плоскости, матрицы, вращения
3дФундамнеталс: софтвеерный 3д движок
3дХардвеер: 3д движок на дх11
>рисования прямых на плоскости, матрицы, вращения
>Адвансед
лол, матрицы и рисование прямых изучают на первом курсе любого вуза (направление гейимдзайн, естественно)
а лучше бы геймдизайн изучали
нельзя изучать то, чего не существует
лол
геймдизайн это математика
причем во многом проще чем матрицы
как математика поможет сделать хорошую игру?
"геймдизайн" это что-то уровня астрологии.
геймдизайн тоже в вузах изучают. Например видел программу "Теория игр, теорию вероятностей и общий геймдизайн" на одном из курсов
а потом игры говном получаются
как раз говном они получаются у дипломированных "геймдизайнеров". в 90-00 игры делали энтузиасты как получалось, и получались шедевры.
надо делать игры сердцем, а не умом.
потому что учат всякую хуйню, а не геймдизайн
Если не уметь считать, конечно, это все выглядит как "магия", для кого то и матрицы магия.
Только геймплей 99% игр это геометрия, расположение препятствий, скорость фишки, урон/защита, кулдаун.
потому что нельзя научиться "делать игры". игры это искусство. научиться можно только делать движки.
так же как с рисованием. можно научиться рисовать правильные пропорции и цвета, но никто не научит рисовать красиво. так же и с играми, никто не научит делать интересные игры.
никто это не делает по формулам. "баланс" это вообще новое веяние из-за соревновательных игр.
нужно делать, чтобы было КРУТО, и все.
Все делают по формулам еще со времен старкрафта.
Все игры соревновательные в плане нужно пройти какой-то челлендж. (ВНки не игры). Игра определяется как последовательность выборов, некоторые неудачные и ведут к проигрышу. Причем это может быть на разных масштабах размером от "походил конем через пол поля" до "помансил на пиксель из за угла чтобы не словить пулю".
КРУТО не будет если у тебя слишком легко или слишком сложно или темп медленный. А это все измеряется.
Несомненно есть интуиторы которые понимают все на подсознательном уровне, такое есть везде, музыканты которые не учили гармонию и ноты, и так далее, но это всего лишь значит что они делают ту же работу просто не осознавая ее. Ну и толку с этого? Ты не сможешь научиться быть гением, если им не родился, в плане - "не буду учиться математике, ведь гении не учились, у них само выходит". Ну тужься, верь что и у тебя выйдет, мальчик 35 летний который еще не решил кем станешь.
С картинами тоже так было, все охали ахали как так, а оказывается все довольно просто разбирается по теории цвета и прочему.
с чего ты взял, что искусству нельзя научить? ученичество это абсолютная норма в искусстве
к тому же геймдизайн - понятие растяжимое. половина людей этой профессии буквально формулы изобретает и симуляции запускает
потому, что интерес нельзя измерить. то, что нравится людям, зависит много чего, и сама вещь - это еще только половина причины, потому что остальные вообще зависят от социальных факторов, от места и времени.
одна и та же вещь сегодня может считаться интересной, а завтра - нет, и наоборот.
если не существует цели, то чему учить? научить можно кокретной вещи, например, рисовать фотореалистично. но не факт, что это кому-то понравится.
даже если сможешь "померять свою игру линейкой" и найти абсолютно безупречный дизайн, то что с того? это еще не гарантирует что твою игру вообще кто-то заметит.
а вместо этого все обратят внимание на какой-нибудь кривой бред, который стал случайно популярно, потому кто-то популярный в это поиграл.
а вместо этого все обратят внимание на какой-нибудь кривой бред, который стал случайно популярно, потому кто-то популярный в это поиграл.
> потому, что интерес нельзя измерить
Можно, чел. Берешь метрики и меришь. Как в кинотеатрах, ставят камеры и буквально собирают статистики с какой секунды по какую кому было весело. Так же и в плейтестах игр делают, еще с бородатых годов, с 90-х точно.
ну то есть выверенный игровой дизайн - это просто цель, которую люди сами придумывает, которая на самом деле никак не влияет на интерес игры. на одного человека которому нравится идеальный баланс - найдется 10 которые скажут, что "сломанный" баланс веселее.
маркетологи юбисофт и сони тоже наверное что-то меряли, бошковитые ребята выпускники престижных университетов, наверное. правда это им не очень помогло.
я ж говорю, все эти метрики - это уровень астрологии. людям просто нравится обманывать себя.
чет не припомню чтобы сони закрывались
открыл новости - а у них рост
видно не зря считают, пока ты со своим магическим мышлением отрицаешь реальность
>ты со своим магическим мышлением
это же не я верю в "геймдизайн" какой-то, который поможет сделать интересную игру.
А я забыл у Сони же одна игра.
Да, именно у тебя и есть магическое мышление. Это же ты отрицаешь измерения. Это как если бы ты утверждал что температура рандомная каждый день, отрицая изученные движения воздушных масс. Да, прогнозы могут быть неточными, но только иногда, а еще методы постоянно уточняются.
измерения измеряют только приближенность к некоему эталонному измерению
дебилы с обрыготных пту - нахуй с треда.
есть вопросы серьезные:
1. как затащить инклюды в glsl?
2. как дебажить glsl
3. как писать динамические шейдер пайплайны
есть вопросы серьезные:
1. как затащить инклюды в glsl?
2. как дебажить glsl
3. как писать динамические шейдер пайплайны
это вопросы с подвохом?
>1. как затащить инклюды в glsl?
написать препроцессор
>2. как дебажить glsl
хуком функций
>3. как писать динамические шейдер пайплайны
по документации
>с подвохом
нету тут подвохов.
бесконечная ебля с FBO
>как затащить инклюды в glsl?
Буквально час назад случайно увидел упоминание на гитхабе stb. Эту конкретно не пробовал, но крайне рекомендую всего его либы. Вдруг подойдёт.
Помню как у автора сгорел пердак, когда кто-то написал сотни репортов на дырявые несекьюрные реализации от анализатора
>КРУТО не будет если у тебя слишком легко или слишком сложно или темп медленный. А это все измеряется.
это все хуита, и тому кто это продвигает в массы - уготован свой котелчик в аду - превратили геймдев в какую-то хуиту и дрочку на баланс, убив дохуя серий игр этим ебучим балансом
(меня вот до сих пор забавляет что в какой-нибудь новой части ранее культовой стратегии режут все фракции, оставив одну-две и верещат что для баланса это... ну то есть в девяностые было 12 фракций, а теперь 3 - это же блядь круто)
Запомни - в сингловых играх не нужен баланс от слова вообще. Ну будет какой-то класс нагибать и блядь че? Ну блядь какая разница если маг нагибает воина в экшен-рпг? это более естественно, потому что блядь да, магия сильнее стуканья дубинкой и баланс нахуй не нужен.
А некоторые игроки игры вообще с читами проходят, так что....
Хуйня. Ты предлагаешь сделать сломанную в области геймдизайна игру. С таким же успехом ты можешь предложить делать сломанную в техническом плане игру, в которой все время что то проваливается или застревает. Игроку будет противно как от игры без сбалансированного челленджа, так и от глючной игры.
Не говоря о том что ты просто проебал время рисуя воина, оружие ему, броню, раз он все равно бесполезен
Встал вопрос, вдруг кто подскажет, как эффективнее реализовать композицию разных изображений в изображение свапчейна? Пробовал через ренедеринг в свапчейн с фулскрин шейдером и без рендеринга через компуте, разница не видна.
а эту херню можно на Си писать? или надо плюсы изучать?
Есть мнение, что лучше вообще плюсы сюда не впутывать, голые си производительнее.
Ну, это не совсем правда.
Без умных указателей, динамического полиморфизма или упаси-господи исключений разница будет нулевая. В тех же шейдерах всего этого и нет толком.
При этом есть разница, в том, чтобы для векторов писать vec_add(&res, a, b) вместо перегруженного оператора+ или метод .count() для октодерева вместо octtree_count(&x). То есть перегрузка операторов, const методы, возможности прятать в private часть всякого, неймспейсы и ссылки вместо указателей - это чисто синтаксический мусор. Это чуть ли не скриптом можно в си-код перевести с минимальными модификациями - и компилятор это и сделает мгновенно и безошибочно, а вот человек может и понаошибаться когда у тебя в глобальной области видимости 800 функций.
Короче, мысль в том, что код на си будет в полтора раза длиннее и в два раза менее ясным - что позволяет на с++ за то же время написать или больше кода с тем же быстродействием, или же добавить какие-то оптимизации и даже выиграть по производительности, из-за того, что теперь ты за 20 часов делаешь не просто фичу-нейм, а ты делаешь ещё за 10, и ещё 10 часов можешь шонглировать методами и оптимизациями, чтобы она побыстрее заработала.
Просто не использовать ничего, что работает в рантайме, то есть юзаешь:
1 - структуры с методами и private-полями (вместо вызова функций с указателями на структуру).
2 - шаблоны (вместо год define или ctrl+c/ctrl+v), constexpr поля и функции.
3 - неймспейсы.
4 - ссылки вместо указателей во всех местах без адресной арифметики (то есть почти везде, кроме контейнеров).
5 - перегрузка операторов во всех подходящих и неподходящих местах.
Получаешь даже не С+, а Си с половиной плюса - но твой код яснее в два раза и пишется побыстрее раза в полтора почти без модификаций. И IDE радостно и весело подсказывает где и что, автодополняет твои методы и подсказываешь какие ты можешь вызвать от какого типа.
Ну просто сам прикинь, как slerp на кватернионах с поворотом нужного тебе объекта выглядит на си, а как выглядит на крестах с перегрузкой операторов.
Простыню не читал.
Чел бредит.
Плюсы ничем не уступают си, зачастую превосходят из-за лучшей оптимизации. Любое прикладное по можнл писать на плюсах, никто не заставляет исрользовать новые всратые стандарты и их патерны.
И нет эта херня требует отдельного компилятора. Глсланг, его вариация шейдерс, дхс, сланг... Все наптсано на плюсах, разумеется.
Из контекста кажется, будто анон уже знает си, а плюсы не знает. Следовательно все эти советы не в кассу.
Можно, но Си же люто неудобный по современным меркам.
Планирую запилить свой движок на Вулкане. Не спрашивайте, просто чувствую что хочу и могу. Уже сделал создание логического устройства.
Вопрос: чего вам не хватает в существующих движках?
Вопрос: чего вам не хватает в существующих движках?
возможности пёрнуть
>возможности пёрнуть
Это к звукачам
К звукачам? Хммм... А ты не считаешь, что суть хорошого движка, вся его база, весь циммес заключается в том, чтобы стереть границы, чтобы стать квентисенцией всего прошлого и, вероятно, будущего? преобразоваться и воплотиться в чём-то новом? Нет? Хах, В таком случае - твой движок станет лишь очередным проходным и всеми забытым дерьмом.
я бы добавил встроенный генератор танцулек
>я бы добавил встроенный генератор танцулек
Реалистично. Записал.
>Планирую запилить свой движок на Вулкане. Не спрашивайте, просто чувствую что хочу и могу. Уже сделал создание логического устройства.
Кручу несколько текстурированных треугольников, до воскресенья поставил цель загружать сцену
Вопрос: а как привязаться к кадровой развёртке в плане FPS?
Использую GLFW для создания окошка, но сам Vulkan фигачит кадры как не в себя, под 1000 в секунду легко. И после отрисовки кадра немедленно начинается следующий, да ещё тройная буферизация
Как сделать ему barrier чтобы он не спешил так сильно? Почему-то во всех руководствах что я читаю этот вопрос как-то обошли стороной
Раскажи о своей боли нейронке. Если даже буквально не поможет, то хотябы даст представление о том какие вообще варианты бывают.
бля, а как же 640 килобайт должно хватить всем? я расстроен. хотел стать бздотей-2 и следующие 15 лет жизни делать свой "движок за 2 месяца", а оказывается, что голый триангл на опенжопеле весит чуть меньше анрила, если статически линкануть опенжопель. думал ща сделаю игрульку из одного экзешника размером 42 килобайта, а сделал очередного монстра. полное разочарование
Напишите движок или игроОС на чистом железе без жму/пинусов. Перфоманс будет выпрыгивать из штанов, Гейб предложит породнится.
Если там всунут компилятор шейдеров аля spir-v, то это очень неплохо.
Если же просто чтобы нарисовать треугольник... meh.
А ведь ты наверное еще не все прилинковал. Вроде бы cosmocc умеет статично линковать и libc
Где то нас наебывают. Чтобы нарисовать 3д трегуольник достаточно программы 256 байт
https://www.youtube.com/watch?v=ByVCn3WFaZw
там GLEW3 и GLFW внутри
https://learnopengl.com/code_viewer_gh.php?code=includes/learnopengl/mesh.h
ультранубский вопрос по С++, не должно ли тут быть каких-то освобождающих ресурсов функций? типа
~Mesh()
{
glDeleteVertexArrays(1, &vao);
glDeleteBuffers(1, &vbo);
glDeleteBuffers(1, &ebo);
}
автор просто не сделал для краткости? или это не здесь делается?
ультранубский вопрос по С++, не должно ли тут быть каких-то освобождающих ресурсов функций? типа
~Mesh()
{
glDeleteVertexArrays(1, &vao);
glDeleteBuffers(1, &vbo);
glDeleteBuffers(1, &ebo);
}
автор просто не сделал для краткости? или это не здесь делается?
>
>автор просто не сделал для краткости? или это не здесь делается?
Векторы на стеке - при выходе из скоупа будут уничтожены
господа, затекстуренный квадрат
это было сложнее, чем сделать игру на анриле, но я справился
это было сложнее, чем сделать игру на анриле, но я справился
Решил все же вкатиться, буду делать свой легковесный движок
Первая программа рисующая треугольник весит 688 байт
Первая программа рисующая треугольник весит 688 байт
Ya ebal
Какие есть хорошие книги по дх11?
Книга из шапки и книга Шеррода написаны хуй знает когда, не используют современные плюсы, в коде нет исключений ассертов и прочего.
Есть ли что получше?
Аноны, вот думаю, если у меня несколько текстур в шейдере, то как их выбирать? Разумно ли передавать в вертексе кроме позиции и uv еще и номер текстуры?
Это вряд ли хорошо работает, скорее всего шейдер тупо будет читать все текстуры всегда и просто отбрасывать неиспользованное, грея воздух.
помню года три назад от нехуй делать сделал простенький 3д движок на КуМире, рендерил плоскость, шарик и источник света с тенями. если интересно, могу файл кинуть на тест. единственное, есть проблема с нулевыми значениями, иногда выдаёт ошибку деления на ноль, но фиксится легко
А как правильно то делать?
В одну текстуру слепи
Не знаю, разное пишут, от "последовательно байндить текстуру, рисовать, байндить другую, рисовать" до текстурных атласов, массивов текстур и 3д текстур.
https://community.khronos.org/t/most-efficient-way-to-use-multiple-textures-with-instancing/75255/4
https://community.khronos.org/t/different-textures-in-instanced-rendering/71414/2
Хотя твой вариант тоже упоминают. А еще bindless textures
Где сглаживание, пидорас?
Бамп
Есть ещё вариант:
https://www.reddit.com/r/opengl/comments/1c5d4uu/a_short_guide_about_safe_nonuniform_resource/
Но примеру с waterfall loop я бы не доверял (он будет работать по крайней мере на десктопе), ибо это вроде как UB, а во вторых он гарантирует только subgroup uniform, не dynamically uniform, который нужен для индексации.
https://docs.vulkan.org/samples/latest/samples/extensions/descriptor_indexing/README.html#_when_to_use_non_uniform_indexing_qualifier
The OpenGL Shading Language,Version 4.60.8 (Mon, 14 Aug 2023)
3.8.2. Dynamically Uniform Expressions and Uniform Control Flow
Ты ответил на мой тред двухлетней давности. Я уже OpenGL успел забросить.
> Решил все же вкатиться, буду делать свой легковесный движок
> Первая программа рисующая треугольник весит 688 байт
Неблохо, стандартную либу не юзаешь что ли?
Там так и написано: /NODEFAULTLIB
Чюваки, а вы можете мне пояснить, Vulkan это нечто пришедшее на смену OpenGL ? Или это разные вещи ?
Да. Вулкан это такой опенгл, где собери всё сам, с поддержкой compute, любого числа видеокарт, любых пайплайнов, короче полный контроль над всеми gpu в системе сразу. Опенгл попроще для вкатунов, особенно старый, чем более навороченный становился опенгл, становилось понятнее что уже давно не надо делать попроще, и получше раскрыть апи непосредственно железки.
Там ещё чисто технические моменты есть. Производители железок очень не любят писать для них драйвера. Раньше драйвер должен был включать в себя полную реализацию опенгл. И у нас было много разных хуёвых реализаций опенгл, каждая со своими особенностями. Для вулкана драйвер намного тоньше, и как следствие, лучше. Но опять же, всё перекладывается теперь на плечи разработчика.
Алсо, есть версия опенгл реализованная поверх вулкана: zinc. Алсо, всякие webgl в браузерах скорее всего никогда не умрут, потому что оно безопаснее для недоверенного кода. Сама концепция вулкана противоречит целям безопасности. То есть, вулкан в ближайшие десятилетия полностью опенгл не заменит, будет с ним сосуществовать. А игровые движки постепенно перекатятся все на вулкан/свежий дх, потому что результат у пользователя будет предсказуемее, именно из-за той херни с драйверами.
Спасибо, стало понятнее
Так OpenGL уже не пишут, или там всё идеально? Я что то не знаю?
Котоны, как делать инклюды в glsl шейдерах?
Понятно, что можно просто передать массив строк, но тогда номера строк в ошибках по уебански отображаются.
Понятно, что можно просто передать массив строк, но тогда номера строк в ошибках по уебански отображаются.
GL_ARB_shading_language_include
Компилить оффлайн
Как нибудь пердолиться ручками, с line директивой или аккуратно c glShaderSource: https://stackoverflow.com/a/73098434
Я просто х.з., ибо я компилю оффлайн Vulkan GLSL в SPIR-V (через shaderc и include там просто работает), немного редактирую его и собираю рефлексию с помощью SPIRV-Cross (хотя по хорошему надо чем-то другим) и им же компилю в OpenGL GLSL.
> Как нибудь пердолиться ручками, с line директивой или аккуратно c glShaderSource:
О, шикарно, ровно то что нужно! Спасибо!
Я как раз через glShaderSource инклюд добавлял.
Воткнул '#line 0 1' в конце инклуд файла и автоматом везде все хорошо теперь.
> Я просто х.з., ибо я компилю оффлайн Vulkan GLSL в SPIR-V (через shaderc и include там просто работает), немного редактирую его и собираю рефлексию с помощью SPIRV-Cross (хотя по хорошему надо чем-то другим) и им же компилю в OpenGL GLSL.
Сможешь в двух словах объяснить что это все такое и почему ты это делаешь?
>Сможешь в двух словах объяснить что это все такое и почему ты это делаешь?
Почему я так делать стал я уже не помню (оффлайн компилятором, я начал пользоваться может из-за рефлексии и инклюдов, х.з.).
В Vulkan'е вместо GLSL используется SPIR-V (байткод) и вышло расширение для GLSL (GL_KHR_vulkan_glsl), которое добавляет новые фишечки (например, раздельные texture и sampler), и теперь выходят расширения для GLSL, с расчётом что это будет всё компилиться в SPIR-V и использоваться с Vulkan'он. Так вот из-за этих новых фишечек его и не скормишь OpenGL'у, поэтому я так и обозвал эти "диалекты".
shaderc это враппер над glslang, а glslang - компилятор GLSL'а (и не только) в SPIR-V. И там инклюды работают, и можно компилировать оффлайн или на старте приложения, и т.д.
SPIRV-Cross позволяет компилить SPIR-V обратно в GLSL (а ещё в HLSL и MSL) (я х.з. можно ли скомпилить обратно в Vulkan GLSL, но нахуя?). В нём (SPIRV-Cross) же можно и получить рефлексию (которую я могу использовать для своего враппера), и немного модифицировать SPIR-V через API SPIRV-Cross, перед компиляцией.
Я выбрал Vulkan'овский вариант, потому что раз я начал пердолиться с оффлайн компиляцией в SPIR-V, то: сделать это просто, я могу использовать раздельные texture и sampler (т.е. и в движке есть OpenGL враппер, которому я скармливаю часть рефлексии; в итоге в враппере биндинг выглядит как будто текстуры и сэмплеры раздельны и я могу их биндить как хочу, а враппер сам склеит нужные комбинации), я могу использовать другой язык (HLSL, slang) или компилятор (DXC, slang), если добавлю Vulkan в движок, то шейдеры уже "готовы".
Я мог бы скармливать SPIR-V напрямую OpenGL'у (GL_ARB_gl_spirv), но мой текущий вариант работает и без него, а во вторых - ссыкотно ( https://www.reddit.com/r/opengl/comments/1bjuxy1/does_spirv_actually_work_with_opengl_in_the_real/ ).
Звучит как знатный пердолинг.
> например, раздельные texture и sampler
Какой юз-кейс?
Алсо, для чего нужна рефлексия для шейдеров?
>Звучит как знатный пердолинг.
А это он и есть.
>Какой юз-кейс?
Чтобы как у людей в нормальных графических АПИ. Или можно задекларить все нужные сэмплеры в инклюд-файле, всех их забиндить один раз, и в шейдерах юзать только те, которые нужны. Ну или когда сэмплер не нужен (texelFetch). В других шейдерных языках такого нет (почти).
>Алсо, для чего нужна рефлексия для шейдеров?
Если сделан свой биндинг ресурсов (по имени, или все ресурсы биндятся в одном пространстве (т.е. на один слот можно забиндить любой ресурс, но только один), или ещё что-нибудь), ну или просто замена всяких glGetActiveUniformBlock() и т.д.
Почему не используете directx? В HLSL include и макросы из коробки, да и язык во всем лучше мертвого glsl.
Не до конца понял в чем проблема, ну да ладно, может дорасту.
Покажешь скрины того что пилишь?
Вопросец про освещение.
Вот мне нужно N точечных источников света (костры/факелы и т.п.).
Мне че, на каждый источник света генерить шедоумапу надо?
Вот мне нужно N точечных источников света (костры/факелы и т.п.).
Мне че, на каждый источник света генерить шедоумапу надо?
нет. на каждый точечный источник света тебе нужно 6 шадоумап генерить (ака шэдоу кубмап)
Ну да, но я к тому что прям пиздец на каждый точечный источник света по 6 текстур надо и рендерить сцену 6*nlights раз?
да. тени для точечных источников света самые дорогие
Говнина, конешн. Ну лан. Спасибо анончик!
Взгляд он острый глаза перестал внезапно лю пятый вдруг уставился как когда дракон чанцзе смеяться его на наполнил лезвие.
Опенгл просто популярнее, так сложилось, причину не знаю. Гуглишь любой гайд как вкатиться в движки, везде советы с опенгл начинать. По нему кучу ресурсов, книг, как платных, так и бесплатных, большое коммьюнити. Даже нейросеть тебе будет в лицо тыкать learnopgl'ом. Ещё кроссплатформенность.
Возможно причина историческая, дх проигрывал опенглу первое время. Технически дх дал на клык глу только в 8 или 9 версии.
OpenGL пока еще есть везде. На десктопах всех ОС, на мобилках, в VR, в браузере. DX - чисто десктопные проекты под винду.
>но тогда номера строк в ошибках по уебански отображаются.
Парсишь строку ошибки, и меняешь номер файла на имя файла. Там макрос из __LINE__ и __FILE__ плюс несложная функция по замене имени файла в шейдере на номер, и наоборот.
HLSL же вроде можно кросс-компилить в GLSL, а значит применять HLSL в OpenGL проекте тоже можно. или на практике так не делают?
Не путай теплое с мягким. Огл фреймворк, а глсл и хлсл языки програмировпния. Глсл и на вулкане себя отлично чуствкют, за частую давая хлслу который тоже норм на вк на клык.
Если уходить с глсла зачем? то тогда уж на сланг.
Ну а про дх чел правильно сказал, он мелкомягкий.
Юзкркейс в том что ты можешь держать пару нужных сеплеров и сотню текстур и по индексу подмтавлять семплеры, а не биндить их все разом.
то что ты про инклюд в глсле не щнал это конечно печально
Спирв не вместе глсл, это результат его компиляции.
Если так прагматически рассуждать, то лучше вообще брать готовый движок. Графические API это в первую очередь удел энтузиастов. Нужно делать то, что будет приносить удовольствие, а не думать о несуществующих преимуществах многоплатформенности.
DirectX намного приятнее в использовании чем opengl/vulkan. Линуксоиды попердолятся и запустят через vkdx/vkd3d, с этим проблем быть не жолжно.
>Если так прагматически рассуждать, то лучше вообще брать готовый движок.
Смотря какие у тебя запросы. Графония уровня OpenGL 3.x обычно хватает с головой для большинства васянопроектов.
>Линуксоиды попердолятся
Мобилки и webgl, мне кажется, гораздо важнее линукс десктопа.
>Ну да, но я к тому что прям пиздец на каждый точечный источник света по 6 текстур надо и рендерить сцену 6*nlights раз?
1. Обычно хватает пяти, потому что одна сторона всегда смотрит в стену.
2. Можно вообще две если использовать dual parabaloid (но там своих нюансов хватает).
3. Рендерить надо не всю сцену, а только то, что в радиусе источника света.
4. Если хранить отдельно карты глубин для статической и динамической геометрии сцены, то рендерить надо будет еще меньше.
Мне почему то кажется, что создателей веб игр программирование на opengl интересует в последнюю очередь. Туда обычно суются люди другого склада.
Это все ментальная гимнастика. Программирование движка, это просто трата времени, если называть вещи своими именами, то есть хобби. А это значит что оно должно в первую очередь приносить удовольствие.
На мой взгляд является ошибкой пытаться усидеть на всех стульях.
А fixed-pipeline чем плох? Не осилил leranopengl, там сразу же идет cmake, viusal studio, а я такое не умею, я на freebsd умею тока gcc компилить. Попробовал fixed pipeline - всё уже реализовано за меня, буфер глубины, затенение, прозрачность. Была бы возможность ещё вносить изменения в пайплайн вообще можно было бы суперграфику погромировать. Но для игр на уровне quake вроде достаточно и fixed.
никто не заставляет тебя использовать cmake и visualstudio, можешь найти туториалы и без них
в любом случае, библиотеки подключать уметь надо
fixed pipeline устарел до твоего рождения, он менее производительный, и на совр. видеокартах его нет, есть эмуляция
Зачем это тебе? Если для тебя программирования это скорее помеха, и ты хочешь сэкономить время на движке, то просто бери годот.
>я на freebsd умею тока gcc компилить
Там все проекты из одного файла. Можно просто gcc -lglad -lglew3 hello_triangle.cpp -o hello_triangle.
>Там все проекты из одного файла.
Че бля? С хуя ли? C и C++ компилят в объектный файл .о . Достаточно просто по частям откомпилить потом собрать линкером. Если нужно автоматизировать - make или шел-скрипты. Больше проекты часто пичкают ещё premake, waf, gmake и прочим калом - но это уже лишнее, разве что premake какую-то пользу имеет. Не умею на visual studio делать, не вкурсе за концепцию "проектов", к тому же на винде есть и нативный msvc. Чтобы выкатиться в visual studio, это нужно винду ставить - +70 гб на всю хуйню, плюс она ещё и тормозить будет на моей некропердоле. Не хочу.
>в любом случае, библиотеки подключать уметь надо
Я попытался найти glsl - нихуя нет. В пакетах попытался поискать либу - пол софта захотела снести своими говнопакетами. Только glx есть, стандартный xlibовский. Но это fixed pipeline.
А хз. С современными движками геймдев в какую-то рутину превращается: пили модельки, пиои концепты, пиши музыку, пиши скрипты. Нудятина пиздец. Ещё и всё это хуй знает как работает, труд макаки сидеть скрипты на шарпе писать. Единственное что имеет смысл - на renderware что-то запилить, вот это хороший движок, чисто на C++ и openal
Свой движок проще, в плане что весь код понятен. Думал создать чисто монолитный движок: opengl для графики, ffmpeg для звуков, обертка окон - xlib/winapi, шрифты freetype2. Все ресурсы статично в бинарнике зашиты, игра представляет собой клиент/сервер по tcp sys/socket.h, на сервере выполняется обновление игровой логики, на клиенте отрисовка всего.
А понял, соре, не то написал.
Ну у меня основное что не нашлось это glad, glsl. Хз есть оно нет на фряхе.
>Свой движок проще, в плане что весь код понятен
>opengl, ffmpeg, freetype
>Выучить библиотеки и писать монолитный костыль vs выучить движковое апи и писать скрипты либо напрямую управлять двиглом через условный libgodot, имея готовый редактор
>геймдев в какую-то рутину превращается: пили модельки, пиои концепты, пиши музыку, пиши скрипты. Нудятина пиздец.
Без комментариев. Возможно ты просто вошёл не в ту дверь ошибся сферой программирования.
мимо протек движкосрачер
ты находишься в местах лишения свободы и это единственный доступный тебе компьютер? что мешает установить нормальную ОС?
>пили модельки, пиои концепты, пиши музыку, пиши скрипты. Нудятина пиздец.
Ты отдаёшь себе отчёт, что чтобы сделать игру, тебе потребуется всё это рано или поздно делать? Хоть пятнадцать лет ковыряй свой велосипедный движок, захочешь сделать игру на нём - придётся окунуться в "нудятину", то есть модельки, текстурки и всё такое. Готовый движок просто сокращает дорогу до этого.
мимо проходил, тред не читал, на SDL2/OpenGL писал
>А fixed-pipeline чем плох?
Тем, что
>всё уже реализовано за
тебя и ещё нет возможности
>вносить изменения в пайплайн
Поэтому от него отказались.
>можно было бы суперграфику погромировать
Именно поэтому все давно перешли на шейдеры.
>Но для игр на уровне quake
Такое даже любителям ретро малоинтересно...
Осознаю. Но если честно, мне показалось что как раз разработка уровней и ресурсов - это то на что уходят годы. В разработка движка занимает не так много, просто потому что движок выпоняет отдельные абстрактные функции, а готовая игра должна представлять миллион вариаций этих функций. Движок наверное можно за год сделать. А на саму игру может уйти лет 5.
Системные требования мешают. Нынче Windows 11 уже актуальна. Моя некропердола еле тянет десятку. Я чё сто ккк наносек себе компьютеры дорогие покупать. Денег нет, я нищий.
А твой гондот есть на фрибсд? Нет? Ну и как мне на нём кодить если его нет. А opengl и ffmpeg кроссплатформенный!
> твой гондот есть на фрибсд? Нет?
Есть. Конпелируй сам. https://docs.godotengine.org/en/4.4/contributing/development/compiling/compiling_for_linuxbsd.html
Как кодить думаю разберешься.
>В разработка движка занимает не так много
Желаю удачи и каменное очко, оно тебе точно понадобится. На ютубе есть челик, tokyospliff, он пилит свое двигло на опенгл с редактором уже четвертый год, и не могу сказать что графика там сильно пиздатая.
>Есть.
>Кидает версию для линукс
Стало быть нет. Справедливости ради загуглил - есть порт с линукса на бсд. Вприципе сойдёт, вроде всего-то 65 мб весит. Но самостоятельно хуй откомпилируешь - это нужно самому вначале портировать.
>Как кодить думаю разберешься.
Там вроде бы очередная скртптовуха если не ошибаюсь. По сути создание игры на движке - всё равно что создание мода к годоту.
>он пилит свое двигло на опенгл с редактором
Нахуя ему редактор? Сложность движка пропорциональна его гибкости. Если хочешь сделать современный unity-like движок, то тебе конечно для начала придется интерпритатор для своего скриптового языка придумать. Потом выдумывать "универсальную" подгрузку сцен, которая по определению не может быть универсальной!!! Тот же unity для многих игр упирается в производительность, в то время как Source нет. Потому что source использует подгрузку уровней оптимизированную под fps, а юнити для всего подряд. В то же время в gta 3 допустим подгрузка идет world-streamingом и всем норм. Почему бы не пилить монолитный движок без скриптов, без гибких возможностей. В этом то как раз и суть своего движка, что ты можешь сделать его оптимизированным под свои задачи. В противном случае не понятно чем unity не угодил. Я вот когда фантизировал о своём движке, вообще никакого способа подгрузки мира не поанировал - уровни целиком просто грузятся, а при переходе на следующей уровень берется просто из таблицы новый. Если у тебя онлайн-слешер где нужно гонять по подземельям и бить гоблинов - этого должно хватить.
>Кидает версию для линукс
В шары долбимся? Ты по ссылке то перейди, а потом ищи порты.
>Там вроде бы очередная скртптовуха если не ошибаюсь. >По сути создание игры на движке - всё равно что создание мода к годоту.
Тебе вот вообще ничего не мешает взять libgodot, собрать его по инструкции из ссылки под bsd и общаться с движком как с либой. Либо просто не используй nodethree и ебашь прям на renderingdevice все что угодно с помощью модов к годоту через апи модулей на плюсах/форка движка с ручным управлением снова на плюсах, а годот со своей стороны обеспечит кроссплатформу и графические бэкенды. Но я бы советовал таки освоить работу не через велосипедостроение, оно того стоит.
>вот когда фантизировал о своём движке, вообще никакого способа подгрузки мира не поанировал -
С таким подходом годота за глаза хватит уж точно. Я бы мог обосрать и всуе упомянутый тобой юнити и предлагаемый мной годот и твой план по написанию своего двигла, но такое только в движкосрачах - велкам. По теме треда написал всё - ты кажись не понял зачем ты тут, учитывая что ты не хочешь заниматься ассетами.
>на фрибсд
Ты бы еще с эльбруса капчевал.
Эльбрус это какое то руснявое поделие. Всё равно что с астра линукс сидеть. Зачем? Современные линуксы с их пайтоном, растом и гномом тормозят не хуже винды. Бежать не куда, придется на фрибзде пердолиться. И чего плохого в увеличении производительности за счёт новой архитектуры процессора? Пересесть на risc какой-нибудь, можно было бы быстрее жить.
Проблема правда основная в софте - сейчас ни один браузер не будет работать без qt, и прочего говна. Это печально.
Годот под Эльбрус работает, ищи сборку
зарепортил
>зарепортил
За что? За обсуждение /s и /hw. Да вы тут все блядь opengl обсужаете это вообще ни разу не геймдев, так что идите нахуй обиженки. Весь тред зарепортить надо.
Скажите а как принято в пайплайне шейдеры соединять в вулкане?
Точнее, вот если сделать два vertex-шейдера в каком порядке они будут выполняться в пайплайне? Что будет с результатами их работы?
Играю с вулканом и этот момент как-то не очевиден
Точнее, вот если сделать два vertex-шейдера в каком порядке они будут выполняться в пайплайне? Что будет с результатами их работы?
Играю с вулканом и этот момент как-то не очевиден
>два vertex-шейдера
>в пайплайне
так не бывает
>>два vertex-шейдера
>>в пайплайне
>так не бывает
Если попытаться то слой проверки ошибок заругается? Спасибо, понял
не советую начинать с vulkan. вообще никому не советую тратить время на opengl/vulkan.
идеальный вариант начать с d3d11. потом перейти на d3d12.
я делаю движок на d3d12, и в целом считаю это самым лучшим API, даже самым простым в какой-то степени. да, сначала нужно потратить время на изучение специфических особенностей, но потом многие вещи ГОРАЗДО проще чем в том же opengl, в том числе по числу строк.
рр
>d3d12, и в целом считаю это самым лучшим API
Ебало представили? (я не хочу сказать что он прямо хуёвый, но местами возникают вопросы к адекватности создателей).
>многие вещи ГОРАЗДО проще чем в том же opengl
Зачем продолжать издеваться над инвалидом?
например, в opengl рекомендуется сначала заполнять uniform buffer, а потом биндить по динамическому смещению. нужно 2 цикла, сначала заполнить uniform buffer, потом биндить и вызывать команды рисования.
в d3d12 можно просто на лету субаллоцировать из upload heap, копировать memcpy в эту память, и биндить виртуальный адрес в root signature. на практике реальный код рендеринга сильно упрощается. особенно если сделать небольшой фреймворк поверх API для удобства.
возможность дергать текстуры по индексу в шейдере - это вообще глоток свежего воздуха после opengl. это реально упрощает разработку именно для целей инди движка. у меня код sprite renderer буквально 25-50 строчек.
>в D3D12 можно просто на лету субаллоцировать из upload heap, копировать memcpy в эту память, и биндить виртуальный адрес в root signature. на практике реальный код рендеринга сильно упрощается. особенно если сделать небольшой фреймворк поверх API для удобства.
Да я не спорю что D3D12 удобнее GL (особенно этот момент с заливкой данных перед drawcallом), я к тому что ты назвал D3D12 лучшим. Я бы сказал что: лучший среди остальных API (хз чё там у консолей) - скорее да, но явно некоторые вещи могли быть лучше (ну или менее наркоманскими). Ну а GL не пинал только ленивый.
К слову в GL 4.4 (или с ARB_buffer_storage) добавили persistent mapped buffers, где можно один раз замаппить буфер и делать примерно тоже самое что в D3D12/VK.
у меня есть canvas, там простая триангуляция полигонов и линий на cpu. я сделал многопоточность, но проблема в том, что для opengl нужно было в конце объединить все буферы в один и т.д., сохранить все команды рисовки в свой самодельный список команд, и потом в цикле перебирать все команды и вызывать все drawcall'ы.
на d3d12 я перенес создание нативного command list в сами потоки. это не только значительно упростило код, но и на одной тестовой сцене FPS выросло с ~200 до ~300.
вот так вот.
проблема в том, что когда люди говорят что opengl легкий, а d3d12 сложный, они сравнивают только простые задачи типа нарисовать треугольник. но на сложных задачах по моему опыту ситуация становится противоположной.
на d3d12 я перенес создание нативного command list в сами потоки. это не только значительно упростило код, но и на одной тестовой сцене FPS выросло с ~200 до ~300.
вот так вот.
проблема в том, что когда люди говорят что opengl легкий, а d3d12 сложный, они сравнивают только простые задачи типа нарисовать треугольник. но на сложных задачах по моему опыту ситуация становится противоположной.
Салам, не совсем уверен, что обращаюсь по адресу, но попробую.
Как сделать туман войны в игре?
Я спрашиваю исходя не из определённого движка, а более общей концепции.
Спрашивал у нейронки, но она мне выдаёт просто обрывки разныз туториалов к другим движкам.
Я так понимаю туман войны можно сделать, через тайлы, через прозрачную текстуру и ещё с помощью шейдеров.
Как бы вы сделали туман войны если для меня главное производительность и комерческий результат, т.е. результат который не стыдно продать.
уточни движок. но в общем случае размещаешь плейн над своей картой и делаешь простенький шейдер (например dissolve shader), где текстура-маска открытых зон определяет прозрачность поверхности. а как писать из игровой логики в эту маску - зависит от движка уже
>Спрашивал у нейронки
>для меня главное комерческий результат
>продать
поищи в unity asset store
так там как раз параша, которая не проходит по основному требованию:
> результат который не стыдно продать
какие есть C++ либы для скелетной анимации, кроме Cal3D? либа не обновлялась 20 лет, наверное люди что-то другое юзают?
пока знаю о ozz‑animation
что еще?
пока знаю о ozz‑animation
что еще?
мы не используем библиотеки. все сами делаем.
> мы не используем библиотеки
че, в коде ни одного внешнего инклуда нет? хуясе, хуй знает как у вас получилось
Делать то по чему нет статей это буквально минимальное требование работы программистом в гейдеве, если ты не мобилки клепаешь. И наверно где угодно вне гейдеве. Смысл платить челу за переписывание кода из туториалов?
Мне нравится что ты не упомянул изучение графических апи.
А оно и видно, что их изучают полтора землекопа даже в среде AAA, видно по релизам драйверов для видях, где "улучшена производительность и исправление визуальные баги YOBA Simulator 2025", видно по workaroundам в dxvk (причём workaroundить на БАЗОВЫЕ ошибки (нпаример, WRITE вместо WRITE_DISCARD, и т.д.)).
>идеальный вариант начать с d3d11
Я на прыщах
Начал с вулкана, всё нормально
Но я бородатый и 25 лет назад однажды крутил треугольник в опенгл. Вулка намного лучше и проще
>Я на прыщах
Тогда тем более надо использовать d3d11. Тогда твою игру смогут все запустить через wine.
d3d11 легко транслируется в вулкан, поэтому dxvk отлично работает. А вот с d3d12 проблемы, потому что он более низкоуровневый.
>Вулка намного лучше и проще
Вулкан по сравнению с directx это как линукс vs windows. На первый взгляд то же самое, но есть нюансы, которые разительно влияют на опыт использования.
Например, в vulkan для синхронизации нужно использовать semaphore и fence. В directx только fence, причем это не бинарный fence как в вулкане, можно сигнализировать определенное числовое значение, и получить его есть свойство GetCompletedValue(). Казалось бы, это не такое большое отличие, но это разительно упрощает всю модель синхронизации. Большинство вещей синхронизируются просто через один fence и считывание его значений. И так во всем.
Многие такие фичи сделаны расширениями, эти расширения являются частью базы в разных версиях. Например рендерпассов сейчас считай нет, если не на мобилки работаешь.
> лучше и проще
Не могу не согласиться. Ты буквально говоришь что делать и оно делает. Не надо гадать что там драйвер может сделать и как заколдоовать чтобы он делал что надо. Как те трюки с рисованием динамической геометрии без unmap от Nvidia. Сейчас ты просто делаешь все прямо и оно просто работает.
Котоны, если источник света находится внутри здания. Как сделать так, чтобы он не протекал наружу?
Просто не обсчитывай его если взгляд идёт снаружи
>>Я на прыщах
>Тогда тем более надо использовать d3d11. Тогда твою игру смогут все запустить через wine.
У меня сейчас Vulkan-овская версия запускается на винде без проблем. Я даже хз как: любители винды что-то подкрутили в сборочных скриптах, не вникал даже.
И у меня важный вопрос про формат glTF:
Там есть такое понятие как offset и stride. Подразумевается что бинарные буферы грузятся в память как есть одним куском (ну если надо только порядок байтов переставляется для big endian) и потом сам Vulkan умеет скакать по таким массивам, если ему верно передать offset и stride.
Но по стандарту glTF эта вот stride задаётся в самом файле gltf, она не дана нам в описании стандарта. То есть, мы обязаны набиндить много шейдеров для glTF, указав правильные значения этих stride/offset. (Точнее, можем задавать и в самом коде шейдера эту stride, но это извращение же и лишняя нагрузка при вычислении каждой вершины.)
Короче, я стою перед выбором: перетасовывать при загрузке glTF буферы в формат для своих шейдеров или нет? Насколько реально они там экономят память когда используют один и тот же буфер по много раз для вершин и индексов, например? Если я просто по всем mesh пройдусь и сделаю для каждого из них свой буфер то что я потеряю?
А ещё лучше подскажите формат 3D моделек без этого мозгоёбства. Ощущение что описание для него зумеры писали, читаю и охуеваю
И ещё вопрос: а в каких форматах принято описывать поверхности земли, ландшафт, здания? Тоже glTF?
Если ты грузишь gltf то ты естественно переводишь данные в свой внутренний формат на загрузке. Плюс оптимизииушь геометрию через meshoptimizer. Gltf чисто транспортный формат. В идеале все это делаешь на сборке ресурсов если нет цели дать грузить именно gltf для UGC например.
>Подразумевается что бинарные буферы грузятся в память как есть одним куском
Не знаю где это подразумевается.
Я не использую interleaved атрибуты вершин. С этим будет проблема, если нужно использовать один шейдер с моделями, у которых разные атрибуты. Если byteStride не равно 0, то я создаю буфер и копирую атрибуты туда линейно.
>запускается на винде
а на линуксе на запустится
Как сделать такой эффект дрожания вертексов? Помню раньше такое было в играх. Квантизация какая-то
гугли ps1 shader, integer coordinates
хотя на твоем видике по-моему какой-то шум рандомный, не похоже на движение вершин сквозь дискретное пространство
не надо. твой слоп от этого лучше не станет
>не надо. твой слоп от этого лучше не станет
Ты заебал уже ныть, клоун. Ебучку бы тебе разъебать
https://www.youtube.com/watch?v=cUiyph17F3A
А анимацию от glTF можно "оторвать"?
Скажем, у меня есть модели, в них кости названы одинаково общепринято. И я хочу взять "чужую" анимацию (потому что мне лень моделлить и я криворукий)
Скажем, у меня есть модели, в них кости названы одинаково общепринято. И я хочу взять "чужую" анимацию (потому что мне лень моделлить и я криворукий)
>движение вершин сквозь дискретное пространство
Понятно, тогда это просто. Автор того видео что чел запостил имитировал это всё, это не игрвоой движок а просто для графония программа
можно, почему нет. чтение - конвертация - запись. но готовь жопу к лютому геморрою на этапе конвертации. потому что кроме названия костей важны еще их локальные оси, и хендиднесс
ну да просто привести позицию вертекса к мировой сетке округленной до заданного шага. делается за 5 сек
еще на ps1 применялись аффинные текстурные координаты, которые давали характерную корявость, вот это должно быть посложнее
а на пк не было всей этой хуиты, и игры выглядели пиздато даже в 1998
разраб кенши ниасилил. вместо этого здания в игре расширяются книзу и имеют толстые стены, чтобы хоть как-то скрывать торчащие конусы спотлайтов
gltf специально сделан, чтобы можно было "оторвать". это называется "скиннинг". в gltf нет костей, там для анимации используются узлы сцены.
это совершенно не так, как на ps1.
как на ps1 нельзя сделать. для этого надо округлять экранные координаты после проекции, но деление на z происходит в фиксированной функции. ты округляешь мировые координаты. но тебе без разницы, тебе же надо просто чтобы твой слоп еще более шкалально выглядел. можешь попробовать еще добавлять случайное смещение к вершинам, чтобы они смешнее дергались
Почему нет? У тебя есть данные, делай с ними что хочешь.
Техническ кости и узлы это то же самое.
вся математика обратима, делать можно что угодно
ты не туда ответил
>Техническ кости и узлы это то же самое.
тоже так думаю, хотя меня всю жизнь убеждают что это приципиально разные системы. ну типа кость всегда направлена на присоединенного потомка, а джоинт может смотреть как угодно. в этом вся разница
>делать можно что угодно
можно, но для этого придется сделать свою программную растеризацию. аппаратную растеризацию нельзя настроить, а именно в ней отличие.
Находятся дурачки не понимающие такую простую концепцию. Смешно их читать
https://github.com/KhronosGroup/glTF/issues/1665
Это уровень художников чтобы правильно все расставили. А ты получаешь файлик с геометрией и нодами.
>аппаратную растеризацию нельзя настроить, а именно в ней отличие.
Что именно там нельзя настроить по-твоему? Снэп вершин к пикселям или перспективную коррекцию?
маской для света и для объектов.
то есть как маска коллизий, например. в forward рендеринге это просто сделать, просто во время перебора источников света проверять маску.
>>Подразумевается что бинарные буферы грузятся в память как есть одним куском
>Не знаю где это подразумевается.
>Я не использую interleaved атрибуты вершин. С этим будет проблема, если нужно использовать один шейдер с моделями, у которых разные атрибуты. Если byteStride не равно 0, то я создаю буфер и копирую атрибуты туда линейно.
Тоже к этому пришёл. Авторы glTF думали что stride указывается при биндинге, но в Vulkan stride почему-то можно указать только при создании пайплайна, в отличие от оффсета
а в D3D12 указывается во время вызова IASetVertexBuffers()
для инди движка с небольшим числом геометрии самый простой вариант - это создать большие буферы для всех атрибутов сразу, и для индексов, и субаллоцировать во время загрузки моделей. тогда перед рисовкой просто привязываются эти буферы один раз, и для рисования нужно только смещение в буферах индексов, вершин и число индексов.
>А ещё лучше подскажите формат 3D моделек без этого мозгоёбства.
Свой экспорт напиши. Можно прямо в формат твоего движка, чтобы достаточно было в память загрузить, и указатель поставить. Не понимаю, зачем вообще со сторонними форматами ебаться, если моддинг не нужен.
>Тоже к этому пришёл. Авторы glTF думали что stride указывается при биндинге, но в Vulkan stride почему-то можно указать только при создании пайплайна, в отличие от оффсета
vkCmdBindVertexBuffers2(), но это 1.3 или VK_EXT_extended_dynamic_state, так что на мобилках с этим не очень.
Хз почему они так сделали, может из-за того что VertexInputState "заливается" в код вертекс шейдера в драйвере и из-за мобилок (хотя в OpenGL ES 3.1 появился "vertex attrib binding")./
потому что на amd input assembler эмулируется в вершинном шейдере. вся кривизна там из-за сомнительных решений amd и мобилок.
>>Тоже к этому пришёл. Авторы glTF думали что stride указывается при биндинге, но в Vulkan stride почему-то можно указать только при создании пайплайна, в отличие от оффсета
>vkCmdBindVertexBuffers2(),
Где ты раньше был? Я исправил уже всё, а теперь всё назад теперь переделывать придётся
Arrghh!
Спасиб всё равно
> но это 1.3 или VK_EXT_extended_dynamic_state, так что на мобилках с этим не очень.
>
>Хз почему они так сделали
Просто проебались, может
>>А ещё лучше подскажите формат 3D моделек без этого мозгоёбства.
>Свой экспорт напиши. Можно прямо в формат твоего движка
Всё равно придётся поддерживать конвертер, так что лучше сразу грузить общепринятые форматы
У тебя обычно есть какой-то препроцессор для контента. Так что ты трансформируешь все эти общепринятые форматы в свои. Ты скорее всего не хочешь иметь текстуру в png, ты хочешь иметь её в BC7 с мипами. Грузить обычные форматы имеет смысл для моддинга и во время разработки чтобы перезагружать контент на ходу.
BC это только для 3D текстурок. для картинок png. для 2D игр лучше в png.
>Ты скорее всего не хочешь иметь текстуру в png, ты хочешь иметь её в BC7 с мипами
Почему? У меня сейчас glTF грузятся и там png
Этого двачую. Всё равно все эти "общепринятые" форматы не годятся ни для чего, всё конвертировать, и текстуры, и модели. И BC7 это как-то щедро, не всегда и надо, можно в пятёрочку, восемь бит на канал бывает достаточно.
Потому что BC это block compression. У видях есть аппаратное ускорение для рендеринга текстур из сырых пиксельных данных. А png это сжатый через zlib/DEFLATE набор данных, который для каждого рендеринга нужно разжать. Рано или поздно у тебя начнутся лаги, ты обязан использовать только то, для чего есть хардварное ускорение.
Популярный basis universal это BC текстурки сжатые zlib. png не сильно отличается.
BC это не универсальный формат, потому что это сжатие с потерями. Оно идеально только для фототекстурок, которые сами по себе "шумные", и большинство времени ты все равно видишь разной степени мыльности мипы, на которых артефактов сжатия не видно.
Ты не хочешь отправлять ничего сжатого на GPU. Кроме, очевидно, поддерживаемых форматов, в число которых png не входит. GPU не может прочитать PNG принципиально, так что она заставляет CPU его декодировать, скажем, это текстурка 4к. Получаем 4096 4096 4, итого 64 мегабайта, даже если сам пнг на диске будет весить 2 мегабайта. GPU не может семплировать png не читая его целиком каждый раз, потому что нет аппаратной поддержки, так что мы читаем весь файл. Страдают кеши, страдает пропускная способность, страдает vram.
>BC это не универсальный формат, потому что это сжатие с потерями.
Сжимаем мы png в BC3, например, исходник 8-8-8-8 RGBA = 32 бита на пиксель суммарно. В BC3 у нас будет ~5.3 бита на RGB часть и ~2.7 бита на альфу. Суммарно 8 бит. Некоторые потери очевидны. Если мы сжимаем в BC7, то битрейт на канал и пиксель выбирается в зависимости от контента и итоговый результат неотличим от png. Только весит меньше, может семплироваться блоками 4х4 пикселя, имеет поддержку всех инструкций в железе, декодируется в TMU, а не на CPU. BC это вообще новое название для старых добрых DXT/DDS. Отраслевой стандарт. Никто не пользуется png, потому что ими пользоваться невозможно. Шум может быть, а может и не быть, смотря какой вариант компрессии выберешь.
Занимает в разы больше места в видеопамяти и тебе надо в рантайме генерировать мипы. Может быть пригодно только на этапе разработки, когда тебе надо на полном ходу перезагружать ресурсы. Типа сохранил текстурку и она сразу же обновилась в работающей игре.
Хотя у людей есть кодировщики в BC на вычислительных шейдерах. Но всё это увеличивает время загрузки.
прямо в душу смотрит
> надо в рантайме генерировать мипы
А в glTF не бывает мипов встроенных готовых?
Откуда? В принципе ты можешь ссылаться на текстуры в dds, там могут быть и мипы и всё. Но поскольку gltf это транспортный а не рантайм формат, то так не делают.
>Но поскольку gltf это транспортный а не рантайм формат
Если бы это было так они бы оттуда stride и оффсеты выпилили
>можно в пятёрочку, восемь бит на канал бывает достаточно.
8 бит на канал? Чё?
>А png это сжатый через zlib/DEFLATE набор данных, который для каждого рендеринга нужно разжать.
Разжимать при загрузке (чтении с диска)?
>Рано или поздно у тебя начнутся лаги, ты обязан использовать только то, для чего есть хардварное ускорение.
А может и не начнутся.
>Ты не хочешь отправлять ничего сжатого на GPU. Кроме, очевидно, поддерживаемых форматов
А разжимать basis universal на GPU запрещено?
>Сжимаем мы png в BC3, например, исходник 8-8-8-8 RGBA = 32 бита на пиксель суммарно. В BC3 у нас будет ~5.3 бита на RGB часть и ~2.7 бита на альфу.
Ты чё, бля, посчитал? Я догадываюсь откуда ты эти числа взял, но они не это обозначают (если они вообще хоть что-то значат).
>Если мы сжимаем в BC7, то битрейт на канал и пиксель выбирается в зависимости от контента и итоговый результат неотличим от png
>Шум может быть, а может и не быть, смотря какой вариант компрессии выберешь.
Зависит от того насколько тебе важна точность значения пикселя. И BC7 всё равно пердолит от слишком разных цветов в одном блоке.
>BC это вообще новое название для старых добрых DXT/DDS
DDS это контейнер, там не обязан быть DXT.
>Никто не пользуется png, потому что ими пользоваться невозможно.
Minecraft и другие игры пользуются.
>Если бы это было так они бы оттуда stride и оффсеты выпилили
Баланс между транспорт-френдли и гпу-френдли.
>8 бит на канал? Чё?
8bpp
>Разжимать при загрузке (чтении с диска)?
Тебе нужно разжать, применить pngшные фильтры и отправить эту кучу в vram. Во-первых, загружаться это будет долго, во-вторых это займёт дохуя и больше vram. Это катастрофа, которая случится рано или поздно. Главная проблема здесь как раз память. Если ты семплируешь пиксель, то это адище каждый раз. GPU делает 4 семпла, каждый из которых больше, чем блок 4х4 BC7 суммарно. GPU не знает, что ты конченый и будет загружать соседние данные, засирая кеши и расходуя пропускную способность. В BC7 будет прочитан один блок, который не разворотит кеши, будет прочитан быстро и будет разжат в TMU, то есть операция будет выполнена в сотни раз быстрее буквально и с минимальным футпринтом в памяти. С png ты потеряешь больше 90% перформанса просто в никуда.
>Minecraft и другие игры пользуются.
Нужно смотреть в код клиента, скорее всего окажется, что текстуры только хранятся в png и при загрузке конвертируются в адекватные форматы. Иначе там бы было не больше 3-5 фпс.
Это вообще тут при чём? gltf это буквально GL transmission format, то что он транспортный есть прямо в названии.
> minecraft
Текстуры размеров в 8 пикселей пофиг в чём и как хранить, удачи держать сотню 4К текстур в png, ага.
>Это вообще тут при чём?
При том что (лично для меня) ебля с оффсетами и стридами это максимально уёбищно
Тем более что я мог бы сам их разложить как мне удобно
Разложи. В этом суть. Ты читаешь gltf, вытаскиваешь данные и раскладываешь как надо. Опционально сохраняешь чтобы не повторять. Потому это и называется "транспортный формат".
>Потому это и называется "транспортный формат".
Как ты заебал долбёбина
Раскладывать перекладывать это сложно (там надо будет искать дубли) и дорого. Нет в этом смысла если формат изначально предназначен для прямой загрузки
>glTF (Graphics Language Transmission Format) — это
стандартный формат для обмена 3D-моделями и сценами, разработанный группой Khronos Group. Он оптимизирован для передачи данных и эффективного использования веб-технологиями, за что его часто называют "JPEG для 3D". Основные типы файлов — текстовый .gltf (на основе JSON) и бинарный .glb, который содержит все ресурсы (текстуры, анимацию) в одном файле
Эээ.. Бля, это для рендеринга не годится от слова совсем. Это прямая противоположность того, что ты хочешь для рендеринга, это полностью конвертировать надо.
стандартный формат для обмена 3D-моделями и сценами, разработанный группой Khronos Group. Он оптимизирован для передачи данных и эффективного использования веб-технологиями, за что его часто называют "JPEG для 3D". Основные типы файлов — текстовый .gltf (на основе JSON) и бинарный .glb, который содержит все ресурсы (текстуры, анимацию) в одном файле
Эээ.. Бля, это для рендеринга не годится от слова совсем. Это прямая противоположность того, что ты хочешь для рендеринга, это полностью конвертировать надо.
glTF это говно
>сложно (там надо будет искать дубли)
зачем?
Есть библиотека meshoptimizer которая всевозможные оптимизации для мешей делает если что. И есть готовые библиотеки для загрузки gltf у которых ты просто спрашиваешь "дай мне нормали для всех вершин".
>glTF это говно
Согласен. ему вего несколько лет а в нём уже нахуевертили легаси и неоднозначностей
Вот вы тут знаете может зачем в gltf сделано это?
```json
"skins": [
{
"inverseBindMatrices": 12,
"joints": [ 1, 2, 3 ... ]
}
],
```
Какая-то хуйня которая зачем-то преобразует вертексы к нодам. Смысл этого какой?
Мы ведь можем меши к нодам приделать и так, без этого
```json
"skins": [
{
"inverseBindMatrices": 12,
"joints": [ 1, 2, 3 ... ]
}
],
```
Какая-то хуйня которая зачем-то преобразует вертексы к нодам. Смысл этого какой?
Мы ведь можем меши к нодам приделать и так, без этого
Зацени анонче, решил упороться и запилить свое динамическое bvh дерево с блекджеком и шлюхами. С эвристикой поиска вставки, рефитом, автобалансировкой, реконнектом и чтобы БЫСТРА БЛЯДЬ с сотнями-тысячами вставок-удалений за кадр, без единой аллокации. Я доволен тем что получилось. На спайки похуй, это запись лагает.
а в jolt используют 4 дочерние узла вместо 2-х. якобы это эффективнее с simd операциями.
>jolt
Эта ебанина поддерживает gpu ускорение из коробки без пердолинга? Я в свое время заебался писать кастомные OpenCL кернелы броад фазы для Буллета под наш рендерер в одном проекте.
Нет конечно. Игровая физика должна на CPU обновляться.
Анон, подскажи!
В Вулкане есть uniiform buffer и он загружается и работает как ожидается
Теперь же мне понадобился аналогичный но большой SSBO ("storage buffer" или как-то так). Я его точно также загружаю (тем же кодом), только поменял везде фаги на VK_DESCRIPTOR_TYPE_STORAGE_BUFFER и VK_DESCRIPTOR_TYPE_STORAGE_BUFFER. И буфер этот приезжает нулевого размера, при попытке читать из него шейдер падает, а проверка .length() == 0 говорит true
Что не так делаю?
В Вулкане есть uniiform buffer и он загружается и работает как ожидается
Теперь же мне понадобился аналогичный но большой SSBO ("storage buffer" или как-то так). Я его точно также загружаю (тем же кодом), только поменял везде фаги на VK_DESCRIPTOR_TYPE_STORAGE_BUFFER и VK_DESCRIPTOR_TYPE_STORAGE_BUFFER. И буфер этот приезжает нулевого размера, при попытке читать из него шейдер падает, а проверка .length() == 0 говорит true
Что не так делаю?
Уточнение:
>на VK_BUFFER_USAGE_STORAGE_BUFFER_BIT и VK_DESCRIPTOR_TYPE_STORAGE_BUFFER
Могу только подсказать по directx. Надо?
>Что не так делаю?
Ты создал буфер нулевого размера
Добавил в двигло поддержку вычислительных шейдеров. Постпроцессинг на них намного проще делать.
Валидация что-то говорит? Очевидно где-то забыл размер или не забиндил в дескриптор.
Валидация что-то говорит? Очевидно где-то забыл размер или не забиндил в дескриптор.
>Валидация что-то говорит? Очевидно где-то забыл размер или не забиндил в дескриптор.
Забиндил: если биндинг убрать то попытка загрузить шейдер падает с руганью валидатора:
... the descriptor is being used in draw but has never been updated via vkUpdateDescriptorSets() or a similar call.
>>Что не так делаю?
>Ты создал буфер нулевого размера
Размер задан в VkDescriptorBufferInfo, если его занулить то это ни на что не влияет, но если написать больше чем в буфере есть то ругается:
pDescriptorWrites[0].pBufferInfo[0].range is not VK_WHOLE_SIZE and is zero.
The Vulkan spec states: If range is not equal to VK_WHOLE_SIZE, range must be greater than 0
Если же задать меньше или ноль то никак не ругается, просто проглатывает. Как проверить лучше - хз
Ещё заметил что если закомментировать вызов vkCmdCopyBuffer то ничего не меняется. Хуйня какая-то. Пиздец, второй день ебусь
Я нашёл проблему!
Аноны, спасибо за участие. Поддержка очень важна, помогает не чувствовать себя один на один с этой машиной.
Проблема была в том что я передавал копию VkDescriptorBufferInfo вместо ссылки, и после прогруза в вулканские внутренности с моей стороны она уничтожалась и вулкан поэтому начинал смотреть в мусор
Вопрос про GlTF2 и скинам
Куда преобразует матрица inverseBindMatrices ?
Вот, допустим, у меня есть корневая точка, пусть она лежит в начале координат отрисовываемого объекта. Из неё вторая нода (кость, джоинт) идёт в точку 1,1,1. Нода номер 3 иерархически торчит из ноды два.
Такая вот "змейка"
А куда покажет матрица из inverseBindMatrices для ноды три? В ноду 2 или в ноду 1 которая в начале координат?
Куда преобразует матрица inverseBindMatrices ?
Вот, допустим, у меня есть корневая точка, пусть она лежит в начале координат отрисовываемого объекта. Из неё вторая нода (кость, джоинт) идёт в точку 1,1,1. Нода номер 3 иерархически торчит из ноды два.
Такая вот "змейка"
А куда покажет матрица из inverseBindMatrices для ноды три? В ноду 2 или в ноду 1 которая в начале координат?
Надо находить мировую матрицу для каждого узла (умножая родительскую на локальную), умножать на inverseBindMatrices, и использовать эту матрицу в шейдере
>Куда преобразует матрица inverseBindMatrices ?
как то так
>https://github.khronos.org/glTF-Tutorials/gltfTutorial/gltfTutorial_020_Skins.html
Слишком по-русски себя ведёшь. Лучше почитай обсуждение: https://github.com/KhronosGroup/glTF-Tutorials/pull/64
Долбоёбам выпала возможность сделать нормально, но они нахуевертили так что сами разобраться не могут
>Надо находить мировую матрицу для каждого узла (умножая родительскую на локальную), умножать на inverseBindMatrices, и использовать эту матрицу в шейдере
То есть, ещё до первой отрисовки я должен пробежать дерево нод и заполнить jointMatrices таким:
jointMatrices = parentMatrix currMatrix inverseBindMatrices;
?
Спасибо за труд
>
>jointMatrices = parentMatrix currMatrix inverseBindMatrices;
[code]
jointMatrices = parentMatrix currMatrix inverseBindMatrices;
[/code]
блядь, ну короче, там умножение
Если в движке есть иерархия узлов, в любом случае нужно находить мировые матрицы. Как это делать эффективно, это другой вопрос. Надо просто мировую матрицу умножить на inverseBindMatrix этого узла.
В туториале есть готовый пример шейдера. Ничего сложного.
>В туториале есть готовый пример шейдера. Ничего сложного.
Он. Не. Работает.
По какой причине понять не могу ещё. Точнее, могу: описание формата писал долбоёб
>Если в движке есть иерархия узлов, в любом случае нужно находить мировые матрицы.
Что такое "мировая матрица", на пальцах?
Просто я в голове оперирую чем-то другим, видимо. Я мысленно как бы иду от MVP к конкретным объектам и их элементам, домножая матрицы, начиная от MVP и заканчивая последним листиком на этом дереве объектов. И таким образом координаты вертекса преобразуются в экранные. Всё верно же?
И у меня всё работает, кроме скинов
>Как это делать эффективно, это другой вопрос. Надо просто мировую матрицу умножить на inverseBindMatrix этого узла.
А вот выше упомянули пример шейдера и там в самом шейдере этого нет. И если я каждый кадр буду домножать inverseBindMatrix на "мировую матрицу" (что бы это не значило) это ведь будет расход СPU, значит!
Очень путанно всё, и все объяснения какие-то обрывочные, "на отъебись"
Один чел в каментах на гитхабе тоже столкнулся с этим, три косяка нашёл в доках. Один косяк исправили, а в других он был не уверен поэтому удалил свои соображения, и там как раз было про обратные матрицы. Вот обидно!
Самый простой вариант это
GetWorldMatrix() {
return parent == null ? GetLocalMatrix() : parent.GetWorldMatrix() * GetLocalMatrix();
}
у меня в движке так было долгое время.
>Что такое "мировая матрица", на пальцах?
Это юнитивская терминология. Я к ней привык.
Это трансформация дочернего обернего в мировых координатах. Например, на пике мировая матрица Б. Если умножить на нее (1, 0, 0), получится положение этого кубика.
>это ведь будет расход СPU, значит
Сначала сделай просто, а потом думай об оптимизациях.
>>Что такое "мировая матрица", на пальцах?
>Это юнитивская терминология. Я к ней привык.
>Это трансформация дочернего обернего в мировых координатах. Например, на пике мировая матрица Б. Если умножить на нее (1, 0, 0), получится положение этого кубика
...в мировых координатах.
Верно?
>>это ведь будет расход СPU, значит
>Сначала сделай просто, а потом думай об оптимизациях.
Именно так и делаю. Не работает никак.
https://registry.khronos.org/glTF/specs/2.0/glTF-2.0.html
Читаю про скины и там... Как, знаешь, пишут госструктуры российские документацию к своим API - так чтобы только прикормленный свой программист мог её понять. Вот прям оно, такое ощущение.
Я человек со стороны, первый раз ковыряю по-серьёзному 3Д, но опыт в ИТ овер 20 лвл, и бля, это реально пиздец! Вместо объяснения от общего к частному там идёт куча подробностей, за которыми "не видно леса"
>Сначала сделай просто
Ок, а простой вопрос тогда: как оно должно работать если ОПЦИОНАЛЬНОЙ инфы inverseBindMatrices нет в наличии? Где и как вычислить эту инфу?
Да, у куба вершины заданы как (1, 1, 1) и т.д., но после умножения на эту матрицу они трансформируется туда, где они нарисованы на экране. Если передать эту матрицу в шейдер и умножать на нее вершины куба, то и нарисуется этот куб.
Со скинами то же самое, только перед этим вершину нужно умножить на inverseBindMatrix, чтобы трансформировать ее в локальные координаты джоина.
"Джоин" в данном случае это твоя мировая матрица. То есть суть в том, что вершины модели начнут рисоваться относительно трансформации узла, и изменение трансформации узла будет изменять положение вершин.
>Со скинами то же самое, только перед этим вершину нужно умножить на inverseBindMatrix, чтобы трансформировать ее в локальные координаты джоина.
Погоди, не спеши
Вот у меня есть вершина в её локальных координатах относительно ноды с mesh, в который входит эта вершина
Верно?
Далее, так как это скин, то у меня есть индексы 4 джойнтов, от которых вершина зависит, и соответствующие этим зависимостям весА.
Тут мне всё ясно.
Далее, чтобы вычислить как вершина натянулась между этими джойнтами на коже нужно сделать такое:
```
void main()
{
const mat4 skinMatrix =
weight.x jointMatrices[jointIndices.x] +
weight.y jointMatrices[jointIndices.y] +
weight.z jointMatrices[jointIndices.z] +
weight.w jointMatrices[jointIndices.w];
gl_Position = pushConsts.transl skinMatrix vec4(position, 1.0);
}
```
Тут мне всё ясно, но кроме содержимого jointMatrices[]
У меня уже есть position - это координаты вертекса сама по себе (относительно ноды меша)
jointMatrices же надо как-то рассчитать. Как? Ведь они могут быть частью скелета, который двигается, а значит значения будут каждый раз новыми? Или нет, можно один раз расчитать?
И как конкретно их расчитать?! Мне надо каждый раз обходить дерево нод в глубину для этого? Тогда нахуя дают inverseBindMatrices вообще? Эти значения ведь гвоздями прибиты
[code]
void main()
{
fragTextureCoord = vertTextureCoord;
const mat4 skinMatrix =
weight.x jointMatrices[jointIndices.x] +
weight.y jointMatrices[jointIndices.y] +
weight.z jointMatrices[jointIndices.z] +
weight.w jointMatrices[jointIndices.w];
gl_Position = pushConsts.transl skinMatrix vec4(position, 1.0);
//~ gl_Position = pushConsts.transl * vec4(position, 1.0);
}
[/code]
как код приложить? пиздец лять
Никак. Макаба не умеет. Абу сделай.
Не понял о чем ты. Каким образом создание буферов связанно с пайплайном? Если ты про вертекс атрибуты, то их уже давно можно скипать и работать по адресу.
через pastebin
любая низкоуровневая спецификация так выглядит. Ты попробуй прочитать доки для китайских МК, вот там реальная боль через кривой гугл транслейт
>Мне надо каждый раз обходить дерево нод в глубину для этого?
Это зависит от твоей реализации.
Можешь посмотреть как сделано в годот https://github.com/godotengine/godot/blob/ef34c3d534a16b140aef0643ed2fa36f8e9d1612/scene/3d/node_3d.cpp#L641
>Тогда нахуя дают inverseBindMatrices вообще?
inverseBindMatrix трансфомирует кусочек модели в локальное пространство. Например, вершины руки трансформируются так, что рука находится в центре координат и повернута вверх. Потом это трансформиуется матрицей узла (джоинта) и получается вращение джоинта. Это позволяет трансформировать (анимировать) разные части модели.
>И как конкретно их расчитать?!
jointMatrices = skinNodes.GetGlobalMatrix() x inverseBindMatrices;
UploadToShader(jointMatrices);
gl_Position = projMatrix viewMatrix skinMatrix;
Интересно, у flax не используются матрицы в трансформе https://github.com/FlaxEngine/FlaxEngine/blob/master/Source/Engine/Core/Math/Transform.cs#L220
Означает ли это, что flax не поддерживает sheared трансформации
Это значит что слепой не увидел что они крутят кватернионом, а не матрицей. там 5 строчек кода лол
Дело не в кватернионе, а в scale.
На пике левый куб это родитель, масштабированный по X, правый - дочерний, повернутый. Можно видеть, что он масштабирован не по осям. Такой эффект можно достичь только матрицей.
Это из годот. Flax мне лень проверять. Может у кого он есть установленный.
>Такой эффект можно достичь только матрицей.
почему? не особо понимаю о чем вы базарите, но здесь просто порядок операций решает. при TRS ты умножишь позицию на вектор скейла, и получишь такой скособоченный куб. матрицы необязательны
Нельзя создать такую матрицу из 3 компонентов. Будет вот так.
ты нарисовал что будет, если сначала сделать скейл, затем поворот
Если ты будешь так умножать все матрицы, это поломает обычный масштаб. Перемножая Vector3 scale теряется эта информация масштабирования, вот в чем дело.
То есть ты в инспекторе введешь 1, 0, 0, и у тебя будет неправильно рисоваться объекта.
объясни развернуто, что конкретно ты считаешь поломкой масштаба. в данном примере будет просто плоский объект.
Я пытаюсь понять почему в flax переменожаются Vector3 scale вместо матриц. Мне кажется это неправильно, и не будет работать.
>в данном примере будет просто плоский объект
Если повернуть на 45, и сделать 2, 1, 1, то объект должен масштабироваться по своим локальным осям. А если умножать наоборот, то он будет масштабироваться по мировым осям - неправильно. Если машстаировать родителя, то объект должен еще масштабироваться по осям родителя, если перемножать Vector3 scale, эта информация теряется.
математически идентично получается. в 3Д полно математики взаимозаменяемой. матрицы поворота заменяются кватернионами. матрицы трансформации - трансформ объектами с полями для транслейта, ориентейшна и скейла. конвертируется туда-обратно при желании
без разницы, когда ты умножишь (1,2,1) на (2,1,1) - до поворота или после. результат будет всегда (2, 2, 1)
Ты умножишь 2,1,1 родителя и 2,1,1 ребенка, получится 4,1,1 ты создаешь матрицу и она будет масштабировать на 4 по локальной оси. Оси родителя потеряются.
>>Тогда нахуя дают inverseBindMatrices вообще?
>
>inverseBindMatrix трансфомирует кусочек модели в локальное пространство.
Я о том что если ты вынужден обходить дерево нод модели, то ты легко сам можешь получить эту матрицу и нет смысла предоставлять её
Если матрицы узлов "джоинтов" в эскпортированной сцене совпадают со скелетом, то да. Но узлы могут быть экспортированы в другой позе.
> skinNodes.GetGlobalMatrix()
Я не понимаю что это. Я не понимаю смысла понятия "глобальный" вообще в 3Д графике. И не пнимаю смысла введения таких определений.
Все координаты у нас относительно чего-либо (относительно начала координат Вулкана и далее до самого последнего листа дерева)
Пикрил я пытаюсь рисовать лисицу из gltf семплов
Хуй пойми почему её попердоливает
Запихал в jointMatrices просто содержимое inverseBindMatrices
Шейдер на пике
Получилось то что на пике - все детали лисы собрались в кучу. Вроде, всё верно?
Куда дальше двигаться? Я уже готов тупо перебором хуярить все варианты блеа
Шейдер на пике
Получилось то что на пике - все детали лисы собрались в кучу. Вроде, всё верно?
Куда дальше двигаться? Я уже готов тупо перебором хуярить все варианты блеа
>> skinNodes.GetGlobalMatrix()
>
>Я не понимаю что это.
Если это "абсолютные координаты" то мне не понятно зачем они нужны и как их избежать. На момент начала рендеринга я не знаю абсолютных координат вертексов. Хотелось бы их передвигать на коже без возвращения по дереву обратно потому что ведь могут быть много экземпляров одного объекта в разных местах игрового мира
На пике я при вычислении jointMatrices зачем-то домножил inverseBindMatrice на обычные translation matrix которые задают позу модели по умолчанию - тоже пердолит, ессно.
Хуй пойми как эту кожу считать
Ты вообще gltf сцену создаешь где-то?
>Все координаты у нас относительно чего-либо
Координаты дочернего узла указываются относительно родителя. Ты трансформируешь эти координаты в систему координат родителя и так далее, пока не останется родителей. Это и будут глобальные координаты.
>Ты вообще gltf сцену создаешь где-то?
В каком смысле где-то? Я пишу с нуля движок. Он использует рутовую сцену в качестве первой ноды дерева отображаемых объектов. (Одним из видов этих объектов является gltf, который внутри тоже дерево, но это уже детали)
>Координаты дочернего узла указываются относительно родителя. Ты трансформируешь эти координаты в систему координат родителя и так далее, пока не останется родителей. Это и будут глобальные координаты.
Но ведь, грубо говоря, это всегда будет статичный (0, 0, 0)?
Добавил анимирование чтобы было понятно натягиваются на самом деле вертексы шейдером или нет и нашёл простую такую вот загогулину:
https://github.khronos.org/glTF-Tutorials/gltfTutorial/gltfTutorial_019_SimpleSkin.html
Получился видрил (извините не умею делать запись с экрана)
Значит, шейдер работает! Но вот сам объект выглядит не пропорционально и не так как у авторов статьи. Поэтому и лисицу пердолит, видимо.
Похоже что после инверсного опускания точек и их поворота назад они не поднимаются
формула вычисления jointMatrices сейчас такая:
const inverseTransform = skinNodeTrans.inverse; // это матрица рутовой ноды скина, хз зачем она вообще, но так в оригинале
Дальше для каждой ноды так:
jointMatrices = inverseTransform x perNodeTranslations[jointIdx] x inverseBindMatrices;
>Дальше для каждой ноды так:
>jointMatrices = inverseTransform x perNodeTranslations[jointIdx] x inverseBindMatrices;
Тут была ошибка, видимо
Вот так вроде всё корректно выглядит:
jointMatrices = inverseBindMatrices.inverse x perNodeTranslations[jointIdx] x inverseBindMatrices;
Работает, по моему мнению, так: опускаем joint к началу координат, крутим, возвращаем назад
Всё верно, анончики?
При таком варианте лиса уже просматривается, но выглядит как-то всрато.
Колени у неё не в ту сторону. Wtf?!
Возможно стоит оставить такой вариант
Так а в чем твоя проблема найти глобальную матрицу? У тебя же у нодов есть какой-то трансформ, есть родитель.
>это всегда будет статичный (0, 0, 0)?
Ты находишься в начале системе координат и держишь в руке яблоко на расстоянии 1 метр. Потом отходишь на 1 метр. Яблоко по прежнему на 1 метр от тебя, если его трансформировать в твою систему координат, оно будет 2 метрах от центра. Это и есть глобальный трансформ.
>Так а в чем твоя проблема найти глобальную матрицу? У тебя же у нодов есть какой-то трансформ, есть родитель.
Могу, но сейчас это даже вроде не реализовано у меня, потому что нужды в этом нет. Самое главное, я не вижу причин зачем это могло бы понадобиться: все преобразования можно (?) делать в локальных координатах, на сколько я сейчас понимаю эти вычисления
>>это всегда будет статичный (0, 0, 0)?
>Ты находишься в начале системе координат и держишь в руке яблоко на расстоянии 1 метр. Потом отходишь на 1 метр. Яблоко по прежнему на 1 метр от тебя, если его трансформировать в твою систему координат, оно будет 2 метрах от центра. Это и есть глобальный трансформ.
Ну да. Но зачем чтобы подвигать на яблоке гусеницу узнавать её абсолютные (глобальные)? Нам ведь достаточно её координат относительно яблока. При этом сама гусеница и не знает что её "двигают"
>Ну да. Но зачем чтобы подвигать на яблоке гусеницу узнавать её абсолютные (глобальные)? Нам ведь достаточно её координат относительно яблока. При этом сама гусеница и не знает что её "двигают"
Другими словами: зачем мне для скина нужны координаты ноды к которой скина прилеплен или её родительские?
>потому что нужды в этом нет
В этом есть нужда. Без этого нельзя сделать скины.
>можно (?) делать в локальных координатах, на сколько я сейчас понимаю эти вычисления
Нельзя. В конечно счете тебе надо трансфомировать координаты в экранную систему координат. У тебя джоинты имеют одинаковые локальные координаты.
>У тебя джоинты имеют одинаковые локальные координаты.
Нет, ведь скин от какой-то (условно рутовой) ноды обсчитывается. И я могу с помощью inverseBindMatrices вернуться к этому руту ведь
>ты создаешь матрицу и она будет масштабировать на 4 по локальной оси. Оси родителя потеряются
теперь понял. ну да, есть такое ограничение у трансформов. но почему-то создатели движков живут с этим, не знаю почему
>можно (?) делать в локальных координатах
>ведь скин от какой-то (условно рутовой) ноды обсчитывается
>ведь скин от какой-то (условно рутовой) ноды обсчитывается
unity использует трансформ для конструирования локальной матрицы, а глобальную считает матрицами.
Снова я со своими glTF-проблемами с лисой
Смотрите на видеорилы
Первое видео это анимация того что есть в тестовом glTF файле. В нём нет скинов, только меши и кости. Это специально так задумано чтобы исключить проблемы с расчётом скинов (дело оказалось не в расчёте скина)
Второе видео - это то как оно на моей стороне показывается (вид только сделан другой, сверху, и нет цвета - это всё так и задумано, пока что смотрим только на координаты)
Что-то куда-то едет немного не туда. Не соответствует оригиналу файла, и не пойму почему так. Например, углы поворота соответствуют (совпадение?), но перемещение увеличено ровно в 2 раза, а масштабирования куба ошибается в бОльшую сторону раза примерно в 4
Расчёт вертексов сцены сейчас устроен таким образом, псевдокодом:
Координаты на экране = proj x view x model x координаты_на_сцене x glTF_model_root x bone0 x bone1 x bone3 x cube_mesh_vertex_coord
Т.е. тупо обхожу рекурсивно в глубину каждый вертекс и домножаю чтобы это получить.
Это верно или всё фигня, переделывать?
При этом сцена в своём изначальном стартовом виде корректно рендерится, но потом при анимации всё как-то "разъезжается": лишний проезд, потом корректный доворот на 90 градусов, а потом scale какой-то запредельный. Явно я неверно анимацию костей применяю, но ведь остальное всё работает корректно: объект рисуется в нужном месте сцены и камера туда направлена, всё красиво выглядит в этом смысле.
Хз как это дебажить. Выручайте, на вас одна надежда!
Смотрите на видеорилы
Первое видео это анимация того что есть в тестовом glTF файле. В нём нет скинов, только меши и кости. Это специально так задумано чтобы исключить проблемы с расчётом скинов (дело оказалось не в расчёте скина)
Второе видео - это то как оно на моей стороне показывается (вид только сделан другой, сверху, и нет цвета - это всё так и задумано, пока что смотрим только на координаты)
Что-то куда-то едет немного не туда. Не соответствует оригиналу файла, и не пойму почему так. Например, углы поворота соответствуют (совпадение?), но перемещение увеличено ровно в 2 раза, а масштабирования куба ошибается в бОльшую сторону раза примерно в 4
Расчёт вертексов сцены сейчас устроен таким образом, псевдокодом:
Координаты на экране = proj x view x model x координаты_на_сцене x glTF_model_root x bone0 x bone1 x bone3 x cube_mesh_vertex_coord
Т.е. тупо обхожу рекурсивно в глубину каждый вертекс и домножаю чтобы это получить.
Это верно или всё фигня, переделывать?
При этом сцена в своём изначальном стартовом виде корректно рендерится, но потом при анимации всё как-то "разъезжается": лишний проезд, потом корректный доворот на 90 градусов, а потом scale какой-то запредельный. Явно я неверно анимацию костей применяю, но ведь остальное всё работает корректно: объект рисуется в нужном месте сцены и камера туда направлена, всё красиво выглядит в этом смысле.
Хз как это дебажить. Выручайте, на вас одна надежда!
Монитор протри.
Что ты там делаешь? Ты с глобальными матрицами разобрался?
Забудь пока про gltf. Сделай корневой Node, добавь к нему дочерний, и изменяй у них параметры положения, масштаба и вращения у обоих. Используй их глобальные матрицы для рисования куба proj x view x global_matrix. Убедись что все отображается правильно.
Потом приходи за новыми советами.
>Монитор протри.
Я под прыщами, щас придумаю как записать экран и перезапишу
Готово, записал
>Что ты там делаешь? Ты с глобальными матрицами разобрался?
Вроде да
>Забудь пока про gltf. Сделай корневой Node, добавь к нему дочерний, и изменяй у них параметры положения, масштаба и вращения у обоих.
Это есть, до того как начать gltf ковырять и сделал вывод объектов всяких типа текстурированного квадрата и кубика цветного, они выводятся как задумано на той же сцене (на видео я их обрезал прост)
> Используй их глобальные матрицы для рисования куба proj x view x global_matrix. Убедись что все отображается правильно.
Да, это всё есть
>Потом приходи за новыми советами.
Я тут
Нет, судя по всему ты не разобрался.
>proj x view x model x координаты_на_сцене x glTF_model_root x bone0 x bone1 x bone3 x cube_mesh_vertex_coord
Это ты вручную где-то умножаешь? Если bone0 это root, то нужно наоборот bone3 x bone1 x bone0. Справа локальные узлы
Хотя нет, у тебя все правильно
Первое вращение не правильное. Возможно вращаешь не те кости
Масштабируешь тоже не ту кость. Ты неправильно биндишь узлы. Дело закрыто.
>>proj x view x model x координаты_на_сцене x glTF_model_root x bone0 x bone1 x bone3 x cube_mesh_vertex_coord
>Это ты вручную где-то умножаешь? Если bone0 это root,
Я как таковой root не выделяю: вся сцена это дерево, начиная от PVM и далее до каждого вертекса, а уже что есть root зависит относительно чего смотреть ведь?
>Первое вращение не правильное. Возможно вращаешь не те кости
Хоба, а поясни? Слишком "рано" по дереву нод или, наоборот, "запаздывает" (должно быть применено к родителю, но применено к ребёнку)?
>Масштабируешь тоже не ту кость. Ты неправильно биндишь узлы. Дело закрыто.
Тэк-тэк... А как так получается?
В gltf идут ноды, и к ним трансформация описанная через матрицу или через вращение-смещение-масштабирование. Но нигде не написано к какой ноде это применять: к текущей, к предыдущей или только к children
Я иду тупо по списку нод и присваиваю матрицу каждой из них сообразно тому как она в JSON-описании идёт.
Потом применяю (то есть фактически просто домножаю к матрице переданной от родителя), а далее уже с этой новой матрицей рисую меш приаттаченый к ноде и далее также рисую детей передавая им эту домноженную матрицу.
>Масштабируешь тоже не ту кость. Ты неправильно биндишь узлы. Дело закрыто.
Скажи как ты это заметил вообще? Конкретно вот тыкни что не так вращается, например?
Спасибо тебе, ты сэкономил уже кучу времени мне: я смотрел в сторону неверной работы функций интерполяции, мол, неверно вычисляется что-то
В анимации есть target node index, индекс в списке node в gltf. Похоже ты анимируешь неправильные node.
Объект во время масштабирования как бы уезжает вперед. Это потому что он смещен от цента масштабируемых координат.
То есть ты скорее всего масштабируешь родительскую кость, относительно которой дочерняя немного сдвинута вперед.
>В анимации есть target node index,
Он в канале лежит, да. И у меня сейчас там такой код (исправил потому что 2ч портит код)
translations{chan.targetNode} =
trans.translationMatrix x
rot.toMatrix4x4 x
scaling.scaleMatrix;
translations это массив матриц каждой ноды по порядку
Вроде всё норм, тут сложно ошибиться, но завтра аккуратно перепроверю. Спасибо!
> индекс в списке node в gltf. Похоже ты анимируешь неправильные node.
>Объект во время масштабирования как бы уезжает вперед. Это потому что он смещен от цента масштабируемых координат.
Вот я это заметил и подумал что вычисляю эту "матрёшку" матриц где-то неправильно в том смысле что может надо сначала локальную (рутовую относительно объекта) на вертекс умножать, а потом уже это всё домножать на более глобальную - но ничего не поменялось когда я попробовал так сделать
>То есть ты скорее всего масштабируешь родительскую кость, относительно которой дочерняя немного сдвинута вперед.
Хорошо, я сейчас поменял алгоритм на такой:
сначала рисуем меш текущей ноды, потом домножаем её локальную трансляционную матрицу и уже этот результат передаём в работу её детям рекурсивно
В результате картинка изменилась так: всё так же, но немного уменьшилось в размерах, и при масштабировании куба он всё равно продолжает смещаться и выглядит больше чем 2x2 (как в оригинале)
Загадочно
>Похоже ты анимируешь неправильные node.
Там единственный канал с таргетом scale это Node=2, и это как раз тот куб. А также одна ротация и одно перемещение. Перепутать невозможно
Вот целиком GLTF: https://github.com/user-attachments/files/23588850/ArticulatedAnimation.2025-11-18.zip
>Вот целиком GLTF: https://github.com/user-attachments/files/23588850/ArticulatedAnimation.2025-11-18.zip
Может кто-то скинет значения трёх матриц 4x4 для всех трёх нод при полностью "развернутом" кубе? Может всё-таки в их вычислении дело...
Или может в каком-то редакторе можно это глянуть?
>Может кто-то скинет значения трёх матриц 4x4 для всех трёх нод при полностью "развернутом" кубе? Может всё-таки в их вычислении дело...
Вот мои "локальные" матрицы для всех трёх нод, по порядку:
0.0000 0.0000 2.0000 1.0000
0.0000 2.0000 0.0000 0.0000
-2.0000 0.0000 0.0000 0.0000
0.0000 0.0000 0.0000 1.0000
2.0000 0.0000 0.0000 1.0000
0.0000 2.0000 0.0000 0.0000
0.0000 0.0000 2.0000 0.0000
0.0000 0.0000 0.0000 1.0000
2.0000 0.0000 0.0000 0.0000
0.0000 2.0000 0.0000 0.0000
0.0000 0.0000 2.0000 0.0000
0.0000 0.0000 0.0000 1.0000
Анончик, спасибо за наводку! Я нашёл ошибку!
Суть была вот в чём:
Изначально я почему-то (хз что дёрнуло - смысла в этом нет, плюс лишние телодвижения) сделал так: на входе функции вычисления трансформации создал базовые "единичные" трансформации таким образом:
auto trans = Vector3f(0, 0, 0);
auto rot = Quaternionf.identity;
auto scaling = Vector3f(1, 1, 1);
И далее в условиях в зависимости от того что реально требовалось вместо конкретных трансформации уже присваивал конкретные довороты или траснляции координат
А в конце после выхода из всех условий делал:
translations{chan.targetNode} = trans.translationMatrix x rot.toMatrix4x4 x scaling.scaleMatrix;
Я думал что всё что "единичное" не будет никак менять матрицу и всё будет ок. Но почему-то (не понимаю почему) это умножение единичных давало такой странные эффект. Возможно что не такие уж они и единичные получались
Сейчас я прямо в условиях сделал что выбирается только одна трансформационная матрица и присваивается и этот глюк пропал, и стало работать как положено (видеорил)
Спасибо за сочуствие, поддержку и помощь! Очень сложно было бы в одного расковыривать когда знаешь что никто не придёт и не подскажет
Ты же по этому делал https://github.com/erincatto/box2d/blob/main/src/dynamic_tree.c ?
Привет, это снова кун, запиливающий glTF
Снова проблема. Помните кривульку которая вроде начала нормально работать?
Так вот, после исправления анимации нод здесь
она перестала нормально работать, появились искажения. Видимо, в прошлый раз я подогнал под результат и баг наложился на баг, дав нормальную картинку в некоторых случаях.
Теперь пришло время окончательно разобраться со скинами и jointMatrices. В настоящее время имеем видрил 1. А должно быть - видрил 2 (это пример из стандартного набора https://github.com/KhronosGroup/glTF-Sample-Assets/tree/main/Models/SimpleSkin )
К шейдеру, похоже, вопросов нет, стандартный из документации действительно работает. А вот как на CPU предварительно вычисляю данные для jointMatrices:
Сначала получаю "довороты" относительно каждого джоинта. Здесь у меня массив baseNodeTranslations это "локальные" матрицы каждой ноды, то есть это те трансформации, которые идут по умолчанию со скелетом в самом файле glTF - то есть, без применения каких-либо анимаций. Правильно ли так делать?
auto skinRootRelative = baseNodeTranslations{jointIdx} x inverseBindMatrices{i};
Теперь вычисляю окончательную матрицу уже для каждого джоинта. Здесь perNodeTranslations это массив "локальных" матриц, к которым уже применена анимация.
jointMatrices = perNodeTranslations[jointIdx] * skinRootRelative;
Получается видрил 1, что, очевидно, неправильно. Где я ошибся?
Данные о полных "глобальных относительно рута (начала меша)"
у меня теперь тоже есть и если что, могу их быстро подставить и проверить гипотезы.
Снова проблема. Помните кривульку которая вроде начала нормально работать?
Так вот, после исправления анимации нод здесь
она перестала нормально работать, появились искажения. Видимо, в прошлый раз я подогнал под результат и баг наложился на баг, дав нормальную картинку в некоторых случаях.
Теперь пришло время окончательно разобраться со скинами и jointMatrices. В настоящее время имеем видрил 1. А должно быть - видрил 2 (это пример из стандартного набора https://github.com/KhronosGroup/glTF-Sample-Assets/tree/main/Models/SimpleSkin )
К шейдеру, похоже, вопросов нет, стандартный из документации действительно работает. А вот как на CPU предварительно вычисляю данные для jointMatrices:
Сначала получаю "довороты" относительно каждого джоинта. Здесь у меня массив baseNodeTranslations это "локальные" матрицы каждой ноды, то есть это те трансформации, которые идут по умолчанию со скелетом в самом файле glTF - то есть, без применения каких-либо анимаций. Правильно ли так делать?
auto skinRootRelative = baseNodeTranslations{jointIdx} x inverseBindMatrices{i};
Теперь вычисляю окончательную матрицу уже для каждого джоинта. Здесь perNodeTranslations это массив "локальных" матриц, к которым уже применена анимация.
jointMatrices = perNodeTranslations[jointIdx] * skinRootRelative;
Получается видрил 1, что, очевидно, неправильно. Где я ошибся?
Данные о полных "глобальных относительно рута (начала меша)"
у меня теперь тоже есть и если что, могу их быстро подставить и проверить гипотезы.
>jointMatrices = perNodeTranslations[jointIdx] * skinRootRelative;
jointMatrices{i} = perNodeTranslations{jointIdx} x skinRootRelative;
(Поправка, борда съела часть кода)
Починилось (или как бы починилось) через домножение к базовой ориентации нод анимированной составляющей. Ранее я просто заменял матрицу на анимированную версию при её наличии.
Как применяются анимации к нодам корректно? В стандарте это чётко не оговорено, кажется?
Продолжаю ковырять. Сгибающаяся палка показывается нормально, теперь смотрим на лисицу (видрил)
Уже понятно что шейдер нормально отрабатывает веса - всё шевелится как живое. Проблема только в криво загнутых ногах, хвосте и почему-то она лежит вместо того чтобы стоять (вращающийся вокруг объекта вид настроен сбоку сверху, значит она почти лежит на правом боку)
Это лучшее чего смог добиться, код заполнения jointMatrices такой:
jointMatrices{i} = rootRelativeNodeTranslations{jointIdx} x inverseBindMatrices{i};
Здесь rootRelativeNodeTranslations это матрица преобразований нод относительно начала фигурки (относительно начала меша). ЧТобы её получить я рекурсивно обощёл дерево нод и домножил матрицы.
Есть идеи?
Уже понятно что шейдер нормально отрабатывает веса - всё шевелится как живое. Проблема только в криво загнутых ногах, хвосте и почему-то она лежит вместо того чтобы стоять (вращающийся вокруг объекта вид настроен сбоку сверху, значит она почти лежит на правом боку)
Это лучшее чего смог добиться, код заполнения jointMatrices такой:
jointMatrices{i} = rootRelativeNodeTranslations{jointIdx} x inverseBindMatrices{i};
Здесь rootRelativeNodeTranslations это матрица преобразований нод относительно начала фигурки (относительно начала меша). ЧТобы её получить я рекурсивно обощёл дерево нод и домножил матрицы.
Есть идеи?
Дополнительно: если отключить анимацию (использовать для создания массива rootRelativeNodeTranslations базовые изначальные матрицы нод) то получается красивая статичная лиса в правильной ориентации
Что у тебя за библиотека матриц. Ты не путаешь column major / row major умножения матриц
>Ты не путаешь column major / row major умножения матриц
А какое и где надо использовать? Об этом ничего нет в спецификации, вроде?
Я могу сделать транспонирование где нужно
> Ты не путаешь column major / row major умножения матриц
У меня на лисе такой вот ассерт падает:
assert(inverseBindMatrices{i}.getRow(3) == Vector4f({0.0, 0.0, 0.0, 1.0]});
Хотя в спецификации glTF написано что в массиве inverseBindMatrices у матриц четвёртая строка всегда состоит из 0,0,0,1
Это то о чём ты говоришь?
А ты попробуй вместо translation x rotation x scale сделать scale x rotation x translation
>А ты попробуй вместо translation x rotation x scale сделать scale x rotation x translation
В каком месте?
Ты это наугад говоришь ведь? Это сообщение видел раньше?
>Я пишу с нуля движок. Он использует рутовую сцену в качестве первой ноды дерева отображаемых объектов. (Одним из видов этих объектов является gltf, который внутри тоже дерево, но это уже детали)
То есть, сцена с объектами корректно показывается, да и лиса сама тоже похожа на настоящую, если бы перепутал TRS порядок то была бы всякая вермишель ведь на экране?
Сейчас я скорее подозреваю всё-таки неверное применение анимации. Всю спецификацию пролистал и не вижу как её применять правильно.
Сейчас только что сделал так:
Беру массив локальных матриц каждой ноды и прибавляю(ага, += делаю) T, R и S интерполированной анимации от каждого канала
Получился видрил. Ооочень похоже к тому что должно быть! Явно не в TRS дело
Раньше (на этом видео ) я домножал анимированные T,R и S к базовой матрице
>Всю спецификацию пролистал и не вижу как её применять правильно.
Вспомнил, видел такое обсуждение у них там на гитхабе: https://community.khronos.org/t/gltf-is-too-complicated/105496 (JoshKlint там упоминает что запиливал поддержки разных 3D форматов в свою софтину за несколько дней, а glTF запиливал около года)
>Беру массив локальных матриц каждой ноды и прибавляю(ага, += делаю) T, R и S интерполированной анимации от каждого канала
У класса Node должны быть vec3 position, vec3 scale, quat rotation. Нужно обновлять их, создавать из них локальную матрицу и умножать на глобальную родителя, чтобы получить глобальную матрицу этого узла.
>У класса Node должны быть vec3 position, vec3 scale, quat rotation.
Да (у меня это всё сразу собрано в матрицу 4x4 при загрузке glTF)
> Нужно обновлять их,
По какому принципу?
> создавать из них локальную матрицу и умножать на глобальную родителя, чтобы получить глобальную матрицу этого узла.
Это всё работает (статичные неанимированные файлы тоже этот механизм используют и с ними всё ок)
>>Беру массив локальных матриц каждой ноды и прибавляю(ага, += делаю) T, R и S интерполированной анимации от каждого канала
Да, это странное, согласен. Но домножение втупую не сработало, а делать поиск изменений по каналу было лень
>А ты попробуй вместо translation x rotation x scale сделать scale x rotation x translation
Ты имеешь ввиду при вычислении матрицы анимации ноды?
>По какому принципу?
Интерполируемые значения из "каналов" анимации нужно просто записывать туда
локальной матрицы. Просто здесь похоже на неправильный порядок трансформаций
>у меня это всё сразу собрано в матрицу 4x4 при загрузке glTF
Это неправильно, потому что анимации обновляют отдельные компоненты трансформа.
>>у меня это всё сразу собрано в матрицу 4x4 при загрузке glTF
>Это неправильно, потому что анимации обновляют отдельные компоненты трансформа.
То есть, если происходит вращение, то я должен только компонент "вращение" перезаписать для конкретной ноды? Ну а потом TRS уже делать при окончательном вычислении координат
Балин! А это точно так? Где-то это написано в спецификации, можете тыкнуть?
Я когда описание формата читал подумал что они это разделение сделали чтобы сэкономить размеры файлов анимаций (матрица 3х4 занимала бы больше место в буферах ключей интерполяции)
>похоже на неправильный порядок трансформаций
Видимо, оно потому и похоже что просто перезаписывается неправильно сделанная матрица, судя по
Хорошо, зато узнал признаки разных косяков, а то глючит а что глючит понять сложно
>>у меня это всё сразу собрано в матрицу 4x4 при загрузке glTF
>Это неправильно, потому что анимации обновляют отдельные компоненты трансформа.
А где их взять? В стандарте базовое состояние трансформа может быть задано матрицей, а не только отдельными компонентами. Хотя это и редко делается, но тестовые образцы файлов с таким мне встречались.
Потому, вопрос актуален:
>Балин! А это точно так? Где-то это написано в спецификации, можете тыкнуть?
А сейчас ты как обновляешь анимации?
>В стандарте базовое состояние трансформа может быть задано матрицей
Это не имеет значения. Матрицу можно разложить на компоненты. Фундаментально, анимации изменяют компоненты трансформа. У тебя в движке должна быть концепция графа сцены с трансформами.
Как альтернатива можно как нибудь "запечь" анимации, но это уже продвинутый уровень.
>А сейчас ты как обновляешь анимации?
Пробовал по-разному. Изначально заменял целиком матрицы (думал что результат применения анимаций надо превращать в матрицу и целиком заменять матрицу джоинта)
Сейчас вот сделал как сказал анон тут и результат получился на видеориле. Вроде, всё верно в этой лисе? Я уже своим глазам не доверяю, вдруг опять что-то не так рендерится, но я не замечаю?
Матрица джоинтов для шейдера кожи вычисляется по-прежнему так:
jointMatrices{i} = rootRelativeNodeTranslations{jointIdx} * inverseBindMatrices{i};
Анон меня буквально спас от видрил 2
>>В стандарте базовое состояние трансформа может быть задано матрицей
>Это не имеет значения. Матрицу можно разложить на компоненты.
Так и сделаю. Но ведь это странно: авторы формата ведь наперёд должны были подумать о том что будет анимация и менять надо будет отдельные компоненты? Или анимацию прикрутили после создания формата?
> Фундаментально, анимации изменяют компоненты трансформа. У тебя в движке должна быть концепция графа сцены с трансформами.
Это есть, просто "трансформы" для упрощения кода у меня были матрицами 4x4. А оказалось что надо отдельно вычислять элементы трансформаций. Хз зачем это придумано было так. Я бы ещё понял если бы при анимировании базовая матрица изменялась с помощью элементов трансформа из анимации. Но когда заведомо известно что должна происходить замена полная то смысла не видно в таком подходе к вычислениям.
>https://github.khronos.org/glTF-Tutorials/gltfTutorial/gltfTutorial_006_SimpleAnimation.html
Читано-перечитано
Конкретно процитируй место? Я даже уже искал в их обсуждениях когда они формат пилили только - нет там нифига, догадываться нужно
>>В стандарте базовое состояние трансформа может быть задано матрицей
>Это не имеет значения. Матрицу можно разложить на компоненты.
А вот вопрос такой тогда: а есть, например, конкретные ячейки матрицы, которые можно было бы заменить чтобы изменить её вращательную часть и только её? И то же самое для масштабирования и перемещения.
Если да то вопрос был бы снят
Ты переусложняешь. У обновления отдельных есть преимущества, и по другому ты анимацию просто не сделаешь, потому что анимация изменяет только вращение, например.
Локальную матрицу можно эффективно создавать за один раз, а не через умножение 3-х матриц
>У обновления отдельных есть преимущества, и по другому ты анимацию просто не сделаешь, потому что анимация изменяет только вращение, например.
Ну это в манямирке авторов glTF2 так, а вообще анимацию матрицами я сделал (выше было ведь), ничего не мешало авторам именно матрицами хранить анимации.
>Локальную матрицу можно эффективно создавать за один раз, а не через умножение 3-х матриц
Ну это да
>а вообще анимацию матрицами я сделал
Это было видно.
>именно матрицами хранить анимации
Нет. Анимация хранится как сплайн, по которому интерполируются векторы или кватернионы. Во первых, матрицу нельзя интерполировать, во вторых это было бы неэффективно, да и вообще невозможно сделать разные интерполяции перемещения, вращения. В любом случае нужно разложить трансформацию на отдельные компоненты.
>Во первых, матрицу нельзя интерполировать,
Отдельные части трансформации получаешь ведь и интерполируешь? А потом эту матрицу втыкаешь.
Но это не то, что подразумевали авторы стандарта, как оказалось
> во вторых это было бы неэффективно, да и вообще невозможно сделать разные интерполяции перемещения, вращения. В любом случае нужно разложить трансформацию на отдельные компоненты.
См выше, можно было бы не раскладывать
>А потом эту матрицу втыкаешь
Куда ты это втыкал? Нельзя это никуда воткнуть.
Нет смысла хранить локальную матрицу в ноде, потому что она создается из компонентов. А вычисление глобальной лучше отлаживать как можно дальше, чтобы не пересчитывать зря при нескольких измненениях за один кадр.
>>А потом эту матрицу втыкаешь
>Куда ты это втыкал? Нельзя это никуда воткнуть.
Я хранил локальную матрицу для каждой ноды и втыкал, соответственно, вместо оригинальной
>Нет смысла хранить локальную матрицу в ноде, потому что она создается из компонентов.
Смысл есть - экономия на перерасчётах хотя бы, ведь не все ноды участвуют в анимации
> А вычисление глобальной лучше отлаживать как можно дальше, чтобы не пересчитывать зря при нескольких измненениях за один кадр.
Глобальные вообще не относятся к обсуждению: они нужны только для скинов
Хорошо, ещё вопрос, общего организационного плана:
В glTF (ну и вообще при любом способе отрисовки объектов на экране) есть разные меши: просто раскрашенные, текстурированные, а также есть меши со скинами (весами).
По сути я могу все эти разные комбинации рендерить разными шейдерами и этим что-то экономить на условиях внутри шейдеров, которые - ого-го! - исполняются для каждой точки объекта на экране. Технически мне это легко организовать в существующей у меня структуре кода, но нужно ли?
У вас глаз насмотренный, вы знаете как бывает в разных движках. По-вашему, какой вариант лучше? Будет у меня 10к объектов на экране, например - повлияет ли то как сделаны шейдеры?
В glTF (ну и вообще при любом способе отрисовки объектов на экране) есть разные меши: просто раскрашенные, текстурированные, а также есть меши со скинами (весами).
По сути я могу все эти разные комбинации рендерить разными шейдерами и этим что-то экономить на условиях внутри шейдеров, которые - ого-го! - исполняются для каждой точки объекта на экране. Технически мне это легко организовать в существующей у меня структуре кода, но нужно ли?
У вас глаз насмотренный, вы знаете как бывает в разных движках. По-вашему, какой вариант лучше? Будет у меня 10к объектов на экране, например - повлияет ли то как сделаны шейдеры?
>Глобальные вообще не относятся к обсуждению: они нужны только для скинов
Или до следующей проблемы...
Если у тебя граф сцены, то глобальная матрица будет матрицей модели для этого узла. Локальную матрицу нужно создавать только во время расчета глобальной, а глобальную в идеале нужно кешировать и обновлять только когда трансформ родителя изменился.
Я видел самодельный движок где так сделано и понял что хранить нужно как раз локальные матрицы везде. А глобальные создавать только в момент вывода кадра, обходя дерево рекурсивно.
Ну и да, кэшировать никто не запрещает, конечно. И в таком случае кэширование можно прикрутить отдельной сущностью (сам обход дерева тоже кэширует в некотором роде - рекурсивный вызов сохраняет вычисленную на данном этапе "глобальную" матрицу)
Теперь это тред программирования компьютерной графики.
Темы OpenGL/DirectX/Vulkan, 3D математика, алгоритмы компьютерной графики, программирование шейдеров и все прочее.
Постим свои потуги в рисовании треугольников, задаем ответы, получаем вопросы.
Шапка старого треда https://gist.github.com/2ch-gd-opengl/26b94fc6f16100af730d84a3d8bbd557
Предыдущий OpenGL тред 7 https://2ch.hk/gd/res/678945.htm